1

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?

  • 2
    The collision attacks against MD5 and SHA1 work only on same-size messages. – CodesInChaos Oct 13 '17 at 8:01
  • This question might be better suited to crypto.SE. (This comment posted via review.) – Adam Katz Oct 19 '17 at 15:37
6

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)

  • Good point. Can't believe I missed that. Though I still think that padding the result is worth it, since it gives you the great upsides I've mentioned above. Also, you would just have to redefine salting to be more than just appending to the data a fixed length, you just append until the data has a constant length. Also, many times hash functions are used for signing data which doesn't have a secret length. It would be much more relevant for those uses. – Omer Oct 12 '17 at 20:06
  • @Omer What about cases where you don't know in advance how long a file someone's gonna want to hash? Pad every file to 64 gb, just to be safe? If you wanted to store the plaintext length in your DB and have your application check it, that could be ok in the cases you mention, but it's a hard sell that it should be done in the crypto primitive. – Mike Ounsworth Oct 12 '17 at 20:15
  • You only have to pad when the length is secret. Can't think of any other use case other than passwords, in which case you can simply pad to 256 bytes or something small like that. – Omer Oct 12 '17 at 20:18
  • @Omer Passwords are the only really common case maybe, but I thought about it for a bit, I could certainly construct you a case where the input in really long, variable length, and the length leaks sensitive info. – Mike Ounsworth Oct 12 '17 at 20:32
  • 1
    hash functions are often used for data anonymization. Leaking the length may in many cases, effectively deanonymize the data. – Lie Ryan Oct 13 '17 at 1:50
4

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.

  • You answered the exact same thing as Mike. I already replied with more questions. Hash functions are not just for passwords, and for passwords you can always pad (instead of salting with a fixed length, salt with a dynamic length so all passwords have the same length) to keep the length secret. – Omer Oct 12 '17 at 20:20
  • @Omer: First, my first paragraph is different to what Mike said. Also, see updated answer. – Steffen Ullrich Oct 12 '17 at 20:22
  • So replying to your first paragraph: So don't call it a hash function, call it hash+size, deviating from the original definition of a hash function is expected, because I'm proposing something new. I want to know why this idea is bad. – Omer Oct 12 '17 at 20:26
  • @Omer: I don't think the idea is bad but I think if you make the hash longer anyway then there are better ways to use these additional bits, i.e. use these for a stronger real hash instead for length information. – Steffen Ullrich Oct 12 '17 at 20:28
  • I don't know enough about attacks on hash functions, but for some reason in my memory I remember I read on people causing collisions to some functions by appending specially crafted data to the real data, in a way that doesn't modify the hash. It was only possible to do it by appending data, not by modifying the existing data. Appending will cause a length change, and what I'm proposing will allow a detection of this. – Omer Oct 12 '17 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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