Date: Sun, 13 Sep 2015 17:04:56 +0300 From: Aleksey Cherepanov <lyosha@...nwall.com> To: john-dev@...ts.openwall.com Subject: Re: experiment with functions to reject computed hashes On Sun, Sep 13, 2015 at 04:06:20PM +0300, Solar Designer wrote: > On Sun, Sep 13, 2015 at 03:34:09PM +0300, Aleksey Cherepanov wrote: > > I was curious if it is possible to make a function to reject computed > > hashes useless for us. Such function has to: > > - never reject hashes from given set, > > - reject as many as possible other hashes. > > We're already doing that with bitmaps and hash tables, and just > yesterday I posted on other related ideas. How is your idea different? > Do you mean rejecting before hash computation is finished? Even if so, > we already have the crypt_all()/get_hash*()/cmp_all()/cmp_one() vs. > cmp_exact() split. Do you mean checks that are not effective enough > (don't eliminate enough candidates) to postpone them until after > crypt_all() returns, so that you want to do them inside crypt_all() > before proceeding to more effective (yet also non-final) checks? The tables are aimed to cut down some hashes before bitmap. They are not aimed to replace bitmap. I had this idea earlier, so thread about Judy arrays just triggered experiments. > > So generated function can reject almost half of candidates using ~7 > > sse instructions (not counting load of tables but counting final > > &0x0..0ff), cracking 32 hashes. > > Isn't it more effective to go for bitmap lookups right away? Could not it be faster with higher number of hashes? I guess size of vectors matter much more. > If cracking only 32 hashes, we can have the bitmap small enough that > it's in L1 cache yet is very effective. Of course, it'd be 4 lookups if > cracking 4 hashes per 128-bit SIMD vector. Is your "7 instructions" for > all 4? Even if so, it's not 7 vs. however many we'd need for bitmap > lookups, but rather it's 7 plus at least 50% of the effort that we > since your filter is less than 50% effective as you say. "7 instructions" is for the whole vector, not for each value in vector. But probability is for separate values. Having 50% probability and 4x vector, full reject would occur only in 1/16 cases. 85% and 4x vectors would give full rejection in 50% cases. So with 85% and 4x vector, it would be 1 check in 50% and 1 check + 4 lookups in other 50%. Trickier code might separate probabilities. So I think there are a few cases when the tables might be useful: - if reject ratio is close to precise, to replace bitmaps, - if lookups are very slow, - if check cost + (1 - reject probability) * vector size * lookup cost < vector size * lookup cost (and that's all without respect to time of building tables.) > And you say you're "not counting load of tables" (constants into SIMD > registers?), which is going to cost too (we usually don't have spare > registers across the entire hash computation). The tables are not really constants, they should be computed at moment when all hashes are loaded. I guess it would be 1 movdqa per table. > I think most speedup when cracking few hashes is possible through > reversing of steps, which we're not doing yet. Until we do that, it's > premature to optimize hash comparisons for that same special case. My tables does not interfere with reversing (like bitmap do not interfere). I think it is a separate question. But faster hashes would benefit from this mostly because slower hashes spend most time computing (and they are probably salted, so checks against sets of 1 hash are more expectable). So yes, there are other, more promising ways to improve fast hashes. Thanks! -- Regards, Aleksey Cherepanov
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.