[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Thu, 28 Jun 2012 21:00:46 +0200
From: Tavis Ormandy <taviso@...xchg8b.com>
To: john-dev@...ts.openwall.com
Subject: Re: md5 internals question
Solar Designer <solar@...nwall.com> wrote:
> Hi Tavis,
>
> On Thu, Jun 28, 2012 at 08:41:18PM +0200, Tavis Ormandy wrote:
> > (password="AAAA")
> >
> > 41 41 41 41 80 00 00 00 00 00 00 00 00 00 00 00 [input + 1 bit] 00 00 00
> > 00 00 00 00 00 00 00 00 00 00 00 00 00 [padding] 00 00 00 00 00 00 00 00
> > 00 00 00 00 00 00 00 00 ... 00 00 00 00 00 00 00 00 00 00 08 00 00 00 00
> > 00 [length]
>
> Almost. This will also contain the length in bits, so fewer of the octets
> will be 00.
>
Ahh, I knew that, I just randomly used an 8 to signify instead of doing it
properly :-)
> > If you have a lookup table for states for inputs length {0..15}, you can
> > take a final R64 state and precompute something like a R10 state to
> > compare it to, and save 60% of the work? (because the only unknown bits
> > mixed in during the later rounds are either zero, or from the appended
> > length).
>
> Not quite. Although the 64-byte block looks almost like what you wrote,
> the 32-bit words from it are actually processed in different order in
> different ones of the four 16-step rounds. Here's the last one:
>
> /* Round 4 */ STEP(I, a, b, c, d, GET(0), 0xf4292244, 6) STEP(I, d, a, b,
> c, GET(7), 0x432aff97, 10) STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15)
> STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21) STEP(I, a, b, c, d, GET(12),
> 0x655b59c3, 6) STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10) STEP(I, c, d,
> a, b, GET(10), 0xffeff47d, 15) STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21)
> STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6) STEP(I, d, a, b, c, GET(15),
> 0xfe2ce6e0, 10) STEP(I, c, d, a, b, GET(6), 0xa3014314, 15) STEP(I, b, c,
> d, a, GET(13), 0x4e0811a1, 21) STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6)
> STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10) STEP(I, c, d, a, b, GET(2),
> 0x2ad7d2bb, 15) STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21)
>
> So I think that at most 15 steps may be reversed.
Thanks, that makes sense, 15 of 64 rounds still sounds like a win of several
Mc/s!
> > I can have a go at implementing a raw-md5-ng if someone more familiar
> > with MD5 confirms this.
>
> It would be great if you give faster MD5 as well.
>
> Thanks,
>
> Alexander
>
I will try, expect some code on the weekend :-)
Tavis.
--
-------------------------------------
taviso@...xchg8b.com | pgp encrypted mail preferred
-------------------------------------------------------
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.
