Date: Tue, 24 Jan 2012 01:45:20 +0400 From: Solar Designer <solar@...nwall.com> To: john-dev@...ts.openwall.com Subject: Re: best approach to cmp_all and cmp_one Hi Samuele, On Mon, Jan 23, 2012 at 10:03:55PM +0100, Samuele Giovanni Tonon wrote: > sorry to bring back another question about cmp_all and cmp_one. Why, the question is entirely appropriate and your progress at improving your code is desirable. There's nothing for you to be sorry for. > however: if cmp_all get another call before a crypt_all i will just read > garbage; would be good on having a global semaphore to avoid a > clEnqueReadBuffer if there's hasn't been any previous crypt_all or there > are more elegant ways to solve the problem ? Having a global flag (not a semaphore) is in fact what I'd recommend. You may call it, say, have_full_hashes. Set it to 0 in crypt_all() (because you only read 1/5 - 32 bits out of 160 bits per hash, right?) In cmp_all(), you just use your partial hashes - cmp_all()'s return value does not need to be precise (non-zero means that there _might_ be matches). You do not need to access this flag there, nor to retrieve the full hashes. Ditto for cmp_one(). However, in cmp_exact() you do need to check the flag and if it's still 0, then retrieve the full hashes from the GPU (all of them at once) and set the flag. This means that subsequent calls to cmp_exact(), if any, will not need to retrieve anything. > second: i was thinking on getting the i-th hashes instead of the whole > buffer but i discovered cmp_one goes incremental, let me explain by an > example > > suppose NUM_KEYS is 1000 and cmp_all(1000) is called and > b == outbuffer[i] is TRUE for 995, then cmp_one will be called like that: > cmp_one(0) > cmp_one(1) > ..... > cmp_one(995) and password is found. > wouldn't be best to have cmp_one start at 995 and incrementing until > NUM_KEYS is reached instead of starting from the beginning or to do that > there will be side effects or a major rewrite of the code ? There should be no need to do that. cmp_all() should give false positives infrequently enough that we should be able to afford doing things non-optimally in that case. In case cmp_all()'s false positives are too frequent, you should instead increase the size of your partial hashes. For example, if your max_keys_per_crypt is 0x10000, you load 0x10000 of same-salt hashes for cracking, and your partial hashes are 32-bit, then false positives become very frequent (not cmp_all()'s, but get_hash*() and cmp_one()'s, though - since cmp_all() is not used on this many loaded hashes). Since your cmp_exact() is very expensive, you should deal with this by increasing the partial hash size - e.g., to 48 bits. Sure, increasing the partial hash size may have a performance penalty of its own in your case. This is normally not the case for CPU-only code, where larger partial hashes only consume more RAM, whereas their effect on performance through them also consuming more cache space is minimal. Also, cmp_exact() is normally not that expensive. But in your case it is and thus a slightly larger partial hash size may be justified. As I wrote in another posting, I am actually considering merging some or all of the hash comparisons into crypt_all(). This would let you use specialized algorithms if you like - even offload the comparisons to the GPU, which is part of the plan for the formats interface rework that I am considering. > next question: saltless password. > > cmp_all is not called for saltless password due to 1. , Sometimes it is - for low hash counts. > so instead you get cmp_one and get_hash_xxx . > This unfortunately makes me have 4 clEnqueReadBuffer which are quite > expensive and do something like that. As I wrote above, please use a global flag and please read the entire buffer at once - in cmp_exact(). For get_hash*() and cmp_one(), just use partial hashes that you already have. It is OK for cmp_one() to have false positives - this is why we also have cmp_exact(). > to solve this problem i'd have to revectorize the opencl output, There should be no need. Just use large enough partial hashes so that cmp_exact() is infrequent enough and you can afford to fetch the entire buffer there. Indeed, a lot of this is still non-optimal - starting with generating candidate passwords on the CPU - but my proposals above is what still fits in the current formats interface best. Like I said, a longer-term plan is to rework the interface, but the above is what you probably want to do for now. 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.