<div class="gmail_quote">On Tue, Sep 28, 2010 at 2:24 PM, Sai <span dir="ltr"><<a href="mailto:noisebridge@saizai.com">noisebridge@saizai.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">On Tue, Sep 28, 2010 at 4:17 PM, Moxie Marlinspike<br>
<<a href="mailto:moxie@thoughtcrime.org">moxie@thoughtcrime.org</a>> wrote:<br>
> Without knowing the context of this construction, I'd guess that it's<br>
> for preventing an extension attack.  Using the hmac construction would<br>
> be better, and I'd guess he confused this with hmac.<br>
<br>
</div>Could you explain? AFAICT extension attack is when you know<br>
hash(cyphertext) and length(cyphertext) you can predict<br>
hash(cat(cyphertext, padding)) for some special padding without<br>
knowing the cyphertext.<br>
<br>
But with a salted hash, you don't know the length. Doubling the salt<br>
doesn't add any entropy - if anything, it reduces it by half, because<br>
you'd know the padding is even, whereas it could otherwise be odd.<br>
<br>
Am I missing something?<br>
<font color="#888888"><br></font></blockquote><div><br></div><div>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.</div>
<div><br></div><div>So, given two messages, "x" and "xy,"</div><div><br></div><div>MD5("x") = finalize( md5_state(null, "x") )</div><div><br></div><div>The null there is a set of initial conditions for this run of the MD5 state machine.</div>
<div><br></div><div>Now, consider "xy."</div><div><br></div><div><div>MD5("xy") = finalize( md5_state(null, "xy") )</div></div><div><div><div>MD5("xy") = finalize( md5_state(md5_state(null,"x"), "y") )</div>
</div></div><div><br></div><div>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.)</div>
<div><br></div><div>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.</div>
<div><br></div><div>This is the high-level hand-wave-y explanation by a math guy, not a crypto guy; for all the fun details, </div><div><a href="http://lmgtfy.com/?q=understanding+hash+length-extension+attacks&l=1">http://lmgtfy.com/?q=understanding+hash+length-extension+attacks&l=1</a></div>
</div>-- <br>Josh Myer 650.248.3796<br> <a href="mailto:josh@joshisanerd.com">josh@joshisanerd.com</a><br>