Shouldn't popular cryptographic hash functions encode the length of the input data in the output?

Question

EDIT2: This discussion was reduced to "are collisions actually harder to create when you add a length constraint?" which is more relevant to the Crypto exchange. I will create a question there and link it when it exists. Thanks for everyone who participated in the discussion

EDIT: The term "Collision attack" in Wikipedia seems to only talk about finding any random collision, I meant to say "Preimage attack".

It would seem like a good idea to me, because it would prevent all collision attacks that require the attacker to modify the length of the data. The attacker would have to find a collision with the exact same length, which is obviously much harder than finding a general collision.

Collision attacks usually require the attacker to modify the length of the data (by appending more blocks to the existing data or something like that), don't they?

The only downside I see to this is that it will require the hash results to be longer (the way I see it only by 2-4 bytes being "The length of the data modulo 2^16-2^32" should be about enough) so not by much.

This of course doesn't have to be part of the hash function itself, it could just be a general security recommendation: "Verify the expected length of the data, not just that it matches the calculated hash, to prevent many forms of collision attacks".

Though I've never heard this recommendation said or mentioned before, even though the way I see it, it makes a lot of sense.

So, in general, I'm asking here: Why is this not a good idea? Should it be encoded in hash functions so it's automatically applied by anyone using those functions, or should it be a general security recommendation that is up to the user of the hash function to implement on his own, separately from the hash function?

Or maybe I'm completely missing something that makes this idea ridiculous?

Answer 1

You're missing another downside: it tells the attacker the length of the plaintext.

In some cases this is considered sensitive information. If I'm brute-forcing passwords, for example, you're telling me that I can skip trying all passwords except those of the specified length. Cool, thanks.

---

Collision attacks usually require the attacker to modify the length of the data (by appending more blocks to the existing data or something like that), don't they?

I believe you're describing a length extension attack. The real cryptographers would probably roast me for saying this, but I naively have a possible solution of padding the massage prior to hashing (at which point you can drop the whole length encoding and just use a traditional hash function): _(really, don't go building software based on this, I don't guarantee that it's secure).

hash( 0*(256 - (len(msg)%256) ) || msg)

Then when the attacker tries to do a length extension attack by concatenating msg2 to the end:

hash( 0*(256 - (len(msg||msg2)%256) ) || msg||msg2)

they will have a different number of padding 0's, which changes the massage prefix and totally breaks the length extension attack.

(The more I think about this, the less I want to stand behind the idea. I should probably spend some time googling "length extension attack mitigation" rather than sitting here and speculating)

Answer 2

A cryptographic hash function is designed to have large changes to the output even on small changes to output. By adding some bytes describing the length of the input you change this assumption, since these length bits will only create small changes to the output on small changes to the input.

Apart from that you actually leak important information about the input as Mike Ounsworth already pointed out. Essentially you tell the attacker not only how long the input will be but also that there is definitely some value that long which results in this hash. This greatly reduces the space the attacker has to brute-force in order to get the same hash result - which in case of passwords is all which is needed since a collusion is not required.

But even in the case where you care about a preimage it is not clear that the bits you add to encode the length would not be more useful instead in extending the strength of the hash itself in order to avoid a preimage attack. While it might help in cases where the input must be shorter than the hash itself and thus preimages are unlikely I think these bits are better used for a longer real hash in case the input is longer then the hash output because same-length preimages are much more likely then.

The attacker would have to find a collision with the exact same length, which is obviously much harder than finding a general collision.

Is it really that obviously harder? I would agree that it is harder if the input is shorter than the hash since it is a problem of finding preimages at such a small size. But if the input is much larger than the hash (i.e. like with certificates) I doubt that requiring a specific length really adds additional complexity to finding a preimage, unless there is some inherent weakness in how the hash is constructed.