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

[Moxie Marlinspike]

On 09/28/2010 05:24 PM, Sai wrote:
> 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?

MD5 (as with all cryptographic hash functions derivative of MD4) uses a
merkel-damgard construction to iteratively process blocks of a message.
 The output of each block serves as the IV for the compression function
on the subsequent block.  The output of the entire function is simply
the output from the round on the final block.  So if I have a hash, I
can easily extend it to include another block of data just by using the
block that I'm given as the IV for another compression round.

Yes, you need to know the length of the message because, in the case of
MD5, the final block is padded with the 64bit length of the original
message.  So in order to extend the hash, the data that you're extending
it with needs to start with however many padding bytes + that length
value.  Again, I don't know anything about the context of this
situation, but a secret, IP address, port, and timestamp are all
generally fixed length values, so it seems possible to know exactly what
padding was included in the final round that you're given, or that a
situation might arise when you happen to have that information
available, or that (at worst) this is easier to guess than a 128bit secret.

Including the secret again at the end does not make this situation
worse, because as an extension attacker I then have the problem of not
knowing the secret which I need to append at the end of my extension
data.  Simply including the secret at the end and not the beginning
increases susceptibility to malleability attacks.

Whether extending a hash would be useful in this situation, or whether
it's possible to determine the length of the original message are
unknown to me.  But usually when people truncate hashes or include a
secret at the beginning and end, this is what they're trying to prevent.
 But again, it looks like this is an attempt to generate a MAC for some
data, in which case I'd suggest using HMAC instead.

- moxie

-- 
http://www.thoughtcrime.org