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
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.