Date: Sun, 13 Sep 2015 16:06:20 +0300 From: Solar Designer <solar@...nwall.com> To: john-dev@...ts.openwall.com Subject: Re: experiment with functions to reject computed hashes 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? > 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? 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 usually incur, since your filter is less than 50% effective as you say. 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). 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. 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.