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 [EMAIL PROTECTED]
