[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20120628185205.GA24112@openwall.com>
Date: Thu, 28 Jun 2012 22:52:05 +0400
From: Solar Designer <solar@...nwall.com>
To: Tavis Ormandy <taviso@...xchg8b.com>
Cc: john-dev@...ts.openwall.com
Subject: Re: md5 internals question
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.
> 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.
> 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
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.
