[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-ID: <mpro.m6cbwt009iaj400sk.taviso@cmpxchg8b.com>
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.
