If hash functions append the length, why does length extension attack work? [duplicate]

Question

I have understood that it's trivial to reconstruct the internal state of a hasher for many hash functions, if one only knows the output hash. Then, one can append data after the original data and obtain a valid hash for the original data plus the appended data.

However, recently I became aware that hash functions including MD5, SHA1, etc. actually append the length.

If hash functions append the length, why doesn't that stop the length extension attacks? For a good hash function, if the attacker knows hash(message || length), there should be no way to obtain hash(message) to be able to calculate hash(message || appended_data) which would allow calculating hash(message || appended_data || total_length).

Related: Understanding the length extension attack ...although the related question doesn't discuss appending of the length which MD5, SHA1, etc. do.

Answer 1

Let hash be the raw hash function, as you're referring to. You mentioned that the attacker knows hash(message || length), but to be more precise, they know hash(message || padding || length). Let full_hash be the proper hash with padding and length, i.e. full_hash(message) = hash(message || padding || length).

You're correct that if the attacker knows hash(message || padding || length), then they can't compute hash(message || appended_data).

But they can compute hash(message || padding || length || appended_data || actual_padding || actual_length) which is equal to full_hash(message || padding || length || appended_data), which may be enough for an attack. The inner padding and length become "garbage" which can be ignored depending on the attack scenario.

In order to carry out the attack, start from hash(message || padding || length) (i.e. the original hash), use it as the initial state for the hash, and then feed the remaining data (appended_data || actual_padding || actual_length).

Answer 2

You should think of the attack as being directed against the hash function as a whole. What you are calling

$$\mathrm{hash}(\mbox{message} + \mbox{length})$$

is really

$$\mathrm{Hash}(\mbox{message})$$

where I've used the capitalization to distinguish the two. $\mathrm{Hash}$, not $\mathrm{hash}$, is the actual "hash function", and this is what is subject to attack - you're extending the length of its input, i.e. just "$\mathrm{message}$" here. And yes, the distinction between the two is important, and consequential to the security properties:

All Merkle-Damgård based hash functions do have an upper limit, because appending the message length simplifies the security proof and the backdoor-resistance of the function and they usually use a fixed-length encoding of the length.

Hence, $\mathrm{hash}$ is actually an internal part of the hash function, not the hash function proper, despite appearances to the contrary. Its security properties are not the same.

Crypto is like that - seemingly-insignificant changes can have major effects. It's fussy. The "security landscape" in algorithm space is more like a smattering of isolated points or perhaps even a fractal, rather than a nice, smooth surface or connected volume, thus sensitive to small perturbations around any given point. It's an Art par excellence, and why one never trusts ciphers or other cryptographic items from anyone but the grand masters. All of them are beautiful works of art, and they should be marveled at with all the feeling of seeing a Picasso, or M.C. Escher's, or others such, and with just as much deep appreciation of the skilled and delicate hands that went into making them.