Date: Sat, 19 Sep 2015 18:23:05 +0300 From: Aleksey Cherepanov <lyosha@...nwall.com> To: john-dev@...ts.openwall.com Subject: Re: fast hash early exit vs. large hash list On Sat, Sep 19, 2015 at 04:33:37PM +0300, Solar Designer wrote: > On Sat, Sep 19, 2015 at 12:17:13PM +0300, Aleksey Cherepanov wrote: > > Check against millions of hashes may just need 2 ints, not fully > > stored state. > > Yes, although in Fred's testcase 1.7+ million correct passwords (and > more than that with --fork and some duplication in post-rules > candidates) would proceed all the way to cmp_*() where we'd want to > check the full 128 bits. Testing them with scalar code may consume a > second, which is like a few percent of the total running time, thus is > "significant". ;-) cmp_* might be vectorized too. > > I did not try these formulas, they may be wrong. > > john-devkit produced them for you? Can it produce anything for > reversing beyond step 61? Maybe if you tell it that some input words > are zero? (Just curious of its capabilities.) I wrote them manually. But I plan to add proper reverse into john-devkit (at the moment it can reverse only constants and unary ops but does not consider other words of hash as "known", it should be trivial to implement). I am not sure about readable formulas though. g defines what word is used in what round. The indexes: $ perl -le 'print +(7 * $_) % 16 for reverse 48 .. 63' 9 2 11 4 13 6 15 8 1 10 3 12 5 14 7 0 So it might be affordable to consider index 9 as 0, that's max len = 31. But then, index 2 is used. It would be 0 if max len = 7. It would a constant if len = 8. A constant would ok too. It is possible to assume word with index 2 as any and reverse with all variants producing 2^32 "correct" values for each hash. It is possible to do that "on demand": when password is set with new word, reverse all hashes with this word. But it does not seem right, because other projects reverse more rounds and does not seem to do it at such expenses. So it may be needed to investigate formulas further or to investigate some implementations with "deep" reverse (for instance, Open Source BarsWF that you mentioned). 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.