Why are non-collision-resistant hash functions considered insecure for signing self-generated information

Question

Let we have a hash function that is second preimage resistant but not collision-resistant.

Then an adversary can create a pair of different messages M and M', M is benign and M' is malicious, for both of which the signature will be valid.

I don't understand why it is an issue in the setting where signatures are used to authenticate origin of data created by the same entity. So if one signs some software he claims "I have created this content myself, if it contains malware, blame me". And for keys: "this public key has a corresponding private key, I have access to it".

If one crafts a collision and signs self-generated data ... he still claims the above statements.

So should such hash functions be considered secure for things like self-signed certificates and code signing?

Answer 1

Digital signatures are designed to do three things:

1. Ensure the integrity of the data that has been signed
2. Create some degree of non-repudiation by the signer
3. The purpose you mentioned, which is to authenticate the origin of the message

The biggest issue with hash functions that are susceptible to collisions is that you very quickly lose the first design goal. If two different messages can have the same signature, then you can't know which are genuine.

So, what's the big deal if I can sign two different messages with the same signature? You still know they both came from me and can hold me accountable, right? Well, perhaps. There are certainly some cases where this can be abused, but we're going to ignore them because they aren't the real issue. The real issue is where you can craft two messages that will have the same signature and the submit one of them for someone else to sign.

The canonical example here is a x.509 (SSL/TLS) certificate request. In this case, a poorly designed certificate signing process can be leveraged to induce a Certificate Authority to sign a certificate for one subject or with one set of properties (like an end-entity certificate), only to have the signature collide with the signature for a second certificate also generated by the attackers that would not have been issued for a subject the attackers don't control, or for a CA cert, and that rogue cert can now benefit from the perfectly valid signature associated with first, benign certificate.

Answer 2

Xander's answer is fundamentally correct: the issue is getting someone else to sign a benign message and use the signature for the malicious one. It is worth noting that although when you make a collision you don't get to decide on the messages directly, you often do get to decide on part of the message. For example I couldn't persuade you to sign "My name is KOLANICH" and swap it for "My name is Josiah": the hashes are vanishingly unlikely to match. However I might be able to get you to sign "Please pay account number X $50 for shoes with reference code ZZZZZZZZZZ." and then replace it with "Please pay account number X $50000 with reference code YYYYYYYYYY." In this scenario I choose whichever Y and Z I need to get the collision.

An additional reason that they are considered insecure is a canary in a coal mine situation. It is easier to find a collision than to find a second preimage; strictly so because if you had a second preimage attack you automatically have a collision, but not vice versa. However, even though having a technique for finding a collision doesn't directly give you second preimages, it does suggest that there is some regularity to the hash function that is likely to surface vulnerabilities which would with further research allow finding preimages.

Answer 3

Well, in theory you would be right. In some very specific cases those hashes would not be completely broken.

However, you would need to be extra cautious, and supposedly some "self-generated" data could actually be insecure. Would you consider the check's written by the accountant to be self-generated by the accountant? Apparently yes, but it actually contains externally controlled data that could be used to produce a signature of a different content.

So should such hash functions be considered secure for things like self-signed certificates and code signing?

You don't really verify self-signed certificates, so you could ignore the hash function used.

On the other hand, I wouldn't consider it secure for code signing. You are probably using external libraries, so a third party could have prepared a library that, when compiled, allowed it to replace a block of code with a malicious one that collides with it.

Please note that although in some specific cases a "broken hash" may work, given that we have perfectly fine non-broken hash functions, that don't need such careful detail, it is much better to use them when possible.

And finally, do remember attacks only get worse with time. The security margin of that function is much severed than of collision resistant ones. An attack that one day seemed unfeasible, or a hash function that was "only" not collision-resistant, not-too-long after may be further broken with a new discovery, forcing you to need to change it real quick.