[Noisebridge-discuss] Anti-piracy / anti-Pirate Bay law currently in Congress [drama]

Josh Myer josh at joshisanerd.com
Tue Sep 28 21:51:11 UTC 2010


On Tue, Sep 28, 2010 at 2:24 PM, Sai <noisebridge at saizai.com> wrote:

> On Tue, Sep 28, 2010 at 4:17 PM, Moxie Marlinspike
> <moxie at thoughtcrime.org> wrote:
> > Without knowing the context of this construction, I'd guess that it's
> > for preventing an extension attack.  Using the hmac construction would
> > be better, and I'd guess he confused this with hmac.
>
> Could you explain? AFAICT extension attack is when you know
> hash(cyphertext) and length(cyphertext) you can predict
> hash(cat(cyphertext, padding)) for some special padding without
> knowing the cyphertext.
>
> But with a salted hash, you don't know the length. Doubling the salt
> doesn't add any entropy - if anything, it reduces it by half, because
> you'd know the padding is even, whereas it could otherwise be odd.
>
> Am I missing something?
>
>
Yes: the part about how MD5 works on the inside, which makes
length-extension possible.  It's got a state machine which churns through
the message, basically checksumming in a very complicated fashion.  Then, to
get the final hash out, it runs it through a finalize function that wraps up
that state a bit.

So, given two messages, "x" and "xy,"

MD5("x") = finalize( md5_state(null, "x") )

The null there is a set of initial conditions for this run of the MD5 state
machine.

Now, consider "xy."

MD5("xy") = finalize( md5_state(null, "xy") )
MD5("xy") = finalize( md5_state(md5_state(null,"x"), "y") )

So, if an attacker can get the machine state that represents the input to
finalize() that yields what they know to be MD5("x"), they can trivially run
MD5(that_state, "whatever they want") and submit it.  (Why do you need to
know the length?  It's a part of the finalize step.)

If you attach a(nother) secret to the end of it, you've taken a fairly
straightforward attack and turned it into another expensive brute force
attack, since they can't get the final machine state.  And you've added more
unknown input text for them to churn through.

This is the high-level hand-wave-y explanation by a math guy, not a crypto
guy; for all the fun details,
http://lmgtfy.com/?q=understanding+hash+length-extension+attacks&l=1
-- 
Josh Myer 650.248.3796
 josh at joshisanerd.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.noisebridge.net/pipermail/noisebridge-discuss/attachments/20100928/c002de33/attachment-0003.html>


More information about the Noisebridge-discuss mailing list