6
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by forest, kelalaka, AleksanderRas, Maeher, Maarten Bodewes Jul 27 at 22:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ what does hash(message || length) mean? $\endgroup$ – Vasu Deo.S Jul 22 at 18:19
  • 3
    $\begingroup$ Remember, it's all just bits. Your message || length is my message <that happens to end with length>. $\endgroup$ – TLW Jul 23 at 4:32
  • 1
    $\begingroup$ @VasuDeo.S || is sometimes used to denote string concatenation. For example many sql flavors use || $\endgroup$ – Giacomo Alzetta Jul 23 at 8:21
  • $\begingroup$ @GiacomoAlzetta Thanks for telling this info $\endgroup$ – Vasu Deo.S Jul 23 at 8:29
18
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ You forgot the padding there. $\endgroup$ – SEJPM Jul 22 at 17:21
  • $\begingroup$ @SEJPM I'm guessing "length" refers to "MD length padding" in this case. $\endgroup$ – forest Jul 22 at 18:32
  • 1
    $\begingroup$ Not convinced, that kind of derivation can only be made if you already know that the plaintext is extended by padding followed by the encoding of the length. Likely only persons that understand length attacks already know that this is the case. I think SEJPM makes a valid point and the answer should be extended or adjusted. $\endgroup$ – Maarten Bodewes Jul 22 at 18:39
  • 2
    $\begingroup$ I don't think that mentioning padding helps understanding the issue, but I expanded my answer in an attempt to be more precise and clear. $\endgroup$ – Conrado Jul 22 at 20:11
3
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.