length-extension and Merkle-Damgard hashes

[Jeremy Hansen]

See Section 3.3 of Coron, Dodis, Malinaud and Puniya's "A New Design
Criteria for Hash-Functions". They address this and several other
problems with the M-D construction in this paper submitted to the 2005
NIST Hash Workshop. (http://cs.nyu.edu/~puniya/papers/nist.pdf)

Jeremy

> -----Original Message-----
> From: owner-cryptography at metzdowd.com 
> [mailto:owner-cryptography at metzdowd.com] On Behalf Of Travis H.
> Sent: Sunday, January 28, 2007 1:34 PM
> To: Cryptography
> Subject: length-extension and Merkle-Damgard hashes
> 
> So I was reading this:
> http://en.wikipedia.org/wiki/Merkle-Damgard
> 
> It seems to me the length-extension attack (given one 
> collision, it's easy to create others) is not the only one, 
> though it's obviously a big concern to those who rely on it.
> 
> This attack thanks to Schneier:
> 
> If the ideal hash function is a random mapping, 
> Merkle-Damgard hashes which don't use a finalization function 
> have the following property:
> 
> If h(m0||m1||...mk) = H, then h(m0||m1||...mk||x) = h(H||x) 
> where the elements of m are the same size as the block size 
> of the hash, and x is an arbitrary string.  Note that 
> encoding the length at the end permits an attack for some x, 
> but I think this is difficult or impossible if the length is 
> prepended.
> 
> --
> The driving force behind innovation is sublimation.
> -><- <URL:http://www.subspacefield.org/~travis/>
> For a good time on my UBE blacklist, email john at subspacefield.org.
> 

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com