[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <mpro.m6dmrk0053wdc0gvc.taviso@cmpxchg8b.com>
Date: Fri, 29 Jun 2012 13:33:20 +0200
From: Tavis Ormandy <taviso@...xchg8b.com>
To: john-dev@...ts.openwall.com
Subject: Re: Re: md5 internals question
Simon Marechal <simon@...quise.net> wrote:
> On 06/28/2012 09:00 PM, Tavis Ormandy wrote:
> > Thanks, that makes sense, 15 of 64 rounds still sounds like a win of
> > several Mc/s!
>
> Actually you can reverse a bit more than this, because you only need a
> single value between a, b, c or d to compare with. You might want to check
> an example of that in NT_fmt_plug.c for MD4 IIRC.
>
OK, I've had time to study it now. I think Solar took this into account with
his 15 round figure, and I think if I limit input to <= 15 characters, his
number is correct.
If we select D from round 64, we can predict all the bits that influence it
without knowing the input back until A48. This is because it mixes in W bits
at R60 from W[4] (all zero), R56 from W[8] (all zero), R52 from W[12] (all
zero), and finally R48 from (unfortunately) W[0], which is part of the input
message and cannot be predicted.
So we manage to skip 3 rounds that mix in input bits, and so for the common
case only have to do 48 rounds!
Additionally, I have some nice ideas to improve the SIMD performance. I see
no reason this cannot hit 30-40 Mc/s on my slow xeon.
One final question, I would need to limit input to 15 chars (or 16, but
would require two comparisons), would this make it useless to everybody
else? (I work in security, but I do vulnerability research, so never need to
crack passwords. I'm primarily interested in the optimization challenge).
What sizes are typical salts? What is the absolute minimum input size I
would need to support to be useful outside of rawmd5?
I will work on it over 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.
