
MessageID: <mpro.m6ccta00kflhc00sk.taviso@cmpxchg8b.com> Date: Thu, 28 Jun 2012 21:00:46 +0200 From: Tavis Ormandy <taviso@...xchg8b.com> To: johndev@...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 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. 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 rawmd5ng 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.