length-extension and Merkle-Damgard hashes

Amir Herzberg herzbea at macs.biu.ac.il
Wed Jan 31 11:37:08 EST 2007

Travis H. wrote:
> 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.
>
This is the well known classical attack against the naive Merkle's
construction, which does NOT use either an IV (for the 1st block), or
MD-strengthening (append the length appropriately, etc.). Which is why
hash functions use a fixed IV for the first block, or append length or
otherwise encode the end block, or, most often, do both (as e.g. in
SHA1, MD5).

Prepending the length [without an IV], btw, is not necessarily a good
solution.

For example, let's assume, for simplicity, that the length (in blocks)
is encoded as 20 bits, prepended to the first block; and say the
input/output block length is L, and for simplicity, assume a compression
function from 2L to L (so the minimal input length is 2L). Let TWO be
the 20-bit encoding of the number 2, and let THREE be the 20-bit
encoding of the number 3.

Repeat until you find a collision (which you will, soon enough...):

- Pick a random (2L-10)-bits string $r\in_R \{0,1\}^{2L-10}$.
- Let H=h(THREE || r)
- If TWO=[first 20 bits of H] then, for every block $x\in \{0,1\}^L$, we
have \$h(H||x)=h((THREE||r)||x), i.e. a collision.

Best, Amir

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