[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20150913130620.GA1018@openwall.com>
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.
