john-dev - Re: fast hash early exit vs. large hash list

Follow @Openwall on Twitter for new release announcements and other news

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20150919091713.GA12559@openwall.com>
Date: Sat, 19 Sep 2015 12:17:13 +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 02:33:21AM +0200, magnum wrote:
> On 18/09/15 17:25, Solar Designer wrote:
> >For raw-md5, we currently have early exit before the last 3 steps.
> >Aside from this being extremely far from what state of the art fast
> >hash crackers do in terms of steps reversal,
> 
> Can we reverse any more without considering the actual candidate (or its
> length)? I doubt the shared functions are suitable for hard-core reversal.
> It might be better to do so in formats like the -ng ones that doesn't use
> shared code. Or at least do them first.

Just some formulas for you convenience:

Original algo:
[...]
elif 48 <= i <= 63:
    F = C ^ (B | (~D))
    g = (7 * i) % 16
dTemp = D
D = C
C = B
B = B + rol((A + F + K[i] + M[g]), s[i])
A = dTemp

Reversed algo for last round ([abcd]64 consist hash, [abcd]63 are for
previous state):

i = 63
b63 = c64
c63 = d64
d63 = a64
g = 9
a63 = ror(b64 - c64, s[i]) - (d64 ^ (c64 | (~a64)) + k[i] + m[g])

So, not considering candidate (m), we know b63, c63, d63.

And for other rounds:

i = 62
b62 = c63
c62 = d63
d62 = a63
g = 2
a62 = ror(b63 - c63, s[i]) - (d63 ^ (c63 | (~a63)) + k[i] + m[g])

Similarly, we know b62, c62 here.

i = 61
b61 = c62
c61 = d62
d61 = a62
g = 11
a61 = ror(b62 - c62, s[i]) - (d62 ^ (c62 | (~a62)) + k[i] + m[g])

Similarly, we know b61 here. b61 becomes a64 in the end. So it is
possible to check 1 int 3 rounds earlier. Check of 2 ints needs 1 more
round.

Check against millions of hashes may just need 2 ints, not fully
stored state.

I did not try these formulas, they may be wrong.

Thanks!

-- 
Regards,
Aleksey Cherepanov

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.