
MessageID: <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: johndev@...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 64byte block looks almost like what you wrote, the 32bit words from it are actually processed in different order in different ones of the four 16step 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 rawmd5ng 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.