Date: Tue, 22 Mar 2011 04:42:24 +0300 From: Solar Designer <solar@...nwall.com> To: john-users@...ts.openwall.com Subject: Re: GSOC - GPU for hashes On Mon, Mar 21, 2011 at 03:17:21AM +0100, ?ukasz Odzioba wrote: > About fast hashes, I suppose that the only way to do it right is try > to implement both versions (in multiple variants), make benchmarks and > then choose the most appropriate one. Some hashes are known to be so fast that it's obvious that having candidate passwords generated on the CPU will create a major bottleneck, up to the point where delegating hashing to the GPU provides little speedup (if at all). So for those the choice will be obvious before we start. Yet in terms of development and usability it does make sense to implement things the easy way first, then proceed from there. In fact, folks already did it (with OpenCL) for a few fast hashes: http://openwall.info/wiki/john/patches see "OpenCL support for cracking NT, raw-MD4, raw-MD5 and raw-SHA1 hashes" by Alain Espinosa, Dhiru Kholia, Samuele Tonon. > I found FPGA hash crackers on > the Internet. From architectural point of view it might be good idea > to use similar solutions. Theoretically, yes, but I am unaware of a good one (from this point). One of the advantages of JtR is that it generates candidate passwords in a nearly optimal order (more likely passwords first, based on available statistics). As soon as we offload some of that to the GPU, we either make the order in which candidate passwords are tried less optimal (e.g., the last 2 characters always cover the entire ASCII range, even though many uncommon character combinations would be better tried at a later time) or we do complicated and not-so-fast processing on the GPU (besides implementation complexity, we might introduce a new bottleneck for hashes that are truly fast rather than just medium-speed). "Competing" tools (and timings) to look at are: http://hashcat.net/oclhashcat+/ http://hashcat.net/oclhashcat/ Of course, we must not reuse any code from there (nor from anywhere else, unless appropriately licensed). The timings for oclHashcat+ suggest that their on-GPU rule engine is fast enough that it is not a bottleneck. We should be able to achieve something similar, and for JtR's incremental mode as well. Also, they show that "md5crypt $1$" and "phpass $P$9" are slow enough that it is acceptable not to move the rule engine onto the GPU for those, unless there are many fast GPUs per CPU. Of course, further speedup is achieved with such a move, so it would be desirable to make eventually, but it's not required for the first implementation that would be of practical use. Thus, we can treat these hashes as "slow". > In Poland summer break starts in July, and before that we've got egzams. > Q5) Will it be a problem to distribute work in 33:67 properties rather > than 50:50? I'd prefer 67:33 (and I think Google prefers this too), especially given that our major opportunity to test this stuff is on July 29-31 (and we need some users already familiar with the JtR/GPU stuff before then): http://contest.korelogic.com However, our mentoring capacity may be the bottleneck anyway, so we may use this as an opportunity to dedicate more time to other students before July. > Q6) Is there any JtR code documentation(I saw user doc)? It would be > helpful to get familiar with sources. JtR's internal interfaces are documented in the .h files. So if you see a function in some .c file that is not "static", then it is exported for use by other source files and there should be a comment on it in the .h file. Besides comments on the interfaces, there are also some comments throughout the code - these are generally for things that I thought were especially non-obvious. Other than that, I'm afraid that there's no documentation. If/when you have specific questions, please ask on john-dev. I might respond by adding source code comments specifically on things that you found non-obvious, which will help others as well. Similarly, when you find something non-obvious but then figure it out on your own, it'd be very nice of you to propose source code comments to add (maybe submit these as patches: post them to john-dev). If you're good at creating programmers' documentation, we'd appreciate it if you start writing some, maybe on our wiki: register for an account and create a page like http://openwall.info/wiki/john/development/program-structure (it does not exist yet), or whatever would be the appropriate name for the content you'd be adding. Oh, there's already this wiki page: http://openwall.info/wiki/john/development which currently has little info (and I don't recommend using an IDE), yet it's where you'd add link(s) to your new sub-page(s) to... or you may start by adding your content right to the "development" page, to be moved to sub-page(s) when there's enough content for that. That's up to you. > Q7) I found yours application template and it's the only thing that > "detailed description" must contain, can I add something to it? Of course. Please do add other relevant info you might have. We'd appreciate it! > Q8) Today i am going to library for Bruce Schneier's "Applied > Cryptography". Are there any good books related to the topic, which I > should look for? As Samuele has correctly pointed out, this task is not so much about cryptography as it is about optimization of algorithms and code. I think you'll "learn this" from reading of existing source code, from your own attempts at producing efficient implementations, and from discussions on john-dev (you'll need to bring topics up and ask questions). Thanks, Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.