Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Date: Thu, 28 Jun 2012 20:41:18 +0200
From: Tavis Ormandy <taviso@...xchg8b.com>
To: john-dev@...ts.openwall.com
Subject: md5 internals question

Hi, forgive my ignorance of MD5 internals, I know SHA-1 in detail but I only
know MD5 at a high level.

>From what I understand, there is no plaintext expansion preprocessing used
as in SHA-1, where the input bits are mixed evenly throughout W[]. This
suggests short messagees will have an expansion W[] like this
(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]

(In SHA-1 the bits would be distributed throughout).

This seems to suggest you can take the early-exit trick I used in the
raw-sha1-ng to an extreme.

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

I havn't tested this theory, and AFAICT I don't think you're doing anything
like that in sse-intrinsics.c, even though it sounds like 20Mc/s for free!

I can have a go at implementing a raw-md5-ng if someone more familiar with
MD5 confirms this.

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.