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