<div class="gmail_quote">On Tue, Sep 28, 2010 at 2:24 PM, Sai <span dir="ltr">&lt;<a href="mailto:noisebridge@saizai.com">noisebridge@saizai.com</a>&gt;</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>
&lt;<a href="mailto:moxie@thoughtcrime.org">moxie@thoughtcrime.org</a>&gt; wrote:<br>
&gt; Without knowing the context of this construction, I&#39;d guess that it&#39;s<br>
&gt; for preventing an extension attack.  Using the hmac construction would<br>
&gt; be better, and I&#39;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&#39;t know the length. Doubling the salt<br>
doesn&#39;t add any entropy - if anything, it reduces it by half, because<br>
you&#39;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&#39;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, &quot;x&quot; and &quot;xy,&quot;</div><div><br></div><div>MD5(&quot;x&quot;) = finalize( md5_state(null, &quot;x&quot;) )</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 &quot;xy.&quot;</div><div><br></div><div><div>MD5(&quot;xy&quot;) = finalize( md5_state(null, &quot;xy&quot;) )</div></div><div><div><div>MD5(&quot;xy&quot;) = finalize( md5_state(md5_state(null,&quot;x&quot;), &quot;y&quot;) )</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(&quot;x&quot;), they can trivially run MD5(that_state, &quot;whatever they want&quot;) and submit it.  (Why do you need to know the length?  It&#39;s a part of the finalize step.)</div>
<div><br></div><div>If you attach a(nother) secret to the end of it, you&#39;ve taken a fairly straightforward attack and turned it into another expensive brute force attack, since they can&#39;t get the final machine state.  And you&#39;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&amp;l=1">http://lmgtfy.com/?q=understanding+hash+length-extension+attacks&amp;l=1</a></div>
</div>-- <br>Josh Myer 650.248.3796<br> <a href="mailto:josh@joshisanerd.com">josh@joshisanerd.com</a><br>