After reading this document about MD5 collision attacks, I still don't understand how collisions can make digital signatures insecure. In the paper, the researchers created two files with the same hash, one innocent and one malicious. The malicious party first sends the good file, gets it signed, and then copies the signature to the bad file to be used against the victim. My question is this: since it is impossible to create a collision without a giant jumbled mess somewhere in the file (though not necessarily immediately visible to the user, for example if preceded and followed by """ in a Python file), why can't users simply ensure that files don't contain blocks of seemingly random bytes if they're digitally signed? For example, why can't SSL certificates hash with MD5 and then use client-side code to verify they don't have any weird strings in them?
-
$\begingroup$ How do you distinguish a 'weird string' from a RSA public key? $\endgroup$– ponchoMar 27, 2015 at 0:18
-
$\begingroup$ @poncho There would be a special field in the certificate for the public key, the length of the key is known so anything longer would signal fraud, and anything anywhere else would signal fraud. $\endgroup$– Elliot GorokhovskyMar 27, 2015 at 0:24
-
$\begingroup$ A collision 'jumbled mess' could occur entirely within where the RSA public key would appear in the certificate; given that an RSA public key looks like seemingly random bytes, how do you propose that the client-side code determine that someone didn't use those random bytes to create a collision? $\endgroup$– ponchoMar 27, 2015 at 1:48
-
2$\begingroup$ @René G: it is intractable to factor the 2048-bit product of two unknown random 1024-bit primes; however there is sizable hope to factor a random 2048-bit integer with moderate effort. $\endgroup$– fgrieu ♦Mar 27, 2015 at 6:55
-
3$\begingroup$ See section 5.3: Constructing colliding certificates of "MD5 considered harmful today - Creating a rogue CA certificate" $\endgroup$– Maarten Bodewes ♦Mar 27, 2015 at 14:17
3 Answers
Manual detection of such blobs of random bytes is rather easy to circumvent, as soon as the file is either too long or non-human-readable. So for something like this to work, you would need to automate the process.
The problem is, that it's really hard to find a valid ruleset on what is a blob of random bytes and what is valid data.
An automatic detection algorithm would have to understand all file formats that should be checked. So lets say, that program could detect a Python triple-quoted comment. Now you let it check a Java file. Java does not do triple-quoted comments, but instead uses /* do denote multiline comments. So your checker does not understand that. Or you could let it check a JPEG-file, which just looks like random bytes, if your checker does not understand JPEG.
Also, triple-quoted strings with random bytes often serve a real purpose, e.g. if you have a look at get-pip.py, it has a blob of Base64-encoded binary at the end, which contains a full installation of pip. Or any RSA-keys, they also look like random bytes and it would be really easy to put something into these fields, that causes an MD5 collision.
Of course all the above comments are valid (rogue certificates, fake-websites, ...), but here's another story:
Let's assume you to buy, let's say a house.
You are lazy and want to sign the contract digitally.
The person, selling you the house presents you with a valid certificate and even is so nice to sign the contract you're going to sign.
Now you sign the contract with your qualified electronical signature using your 2048-bit RSA key and an MD5 hash.
You agree to pay ~200k dollar for the house.
Now, after a few years, you get sued because you've paid the 200k dollars.
The seller now claims you have signed a contract saying, you're willing to pay 300k dollars and presensts a valid signature of you to the court.
Now you're screwed, because of a simple MD5-collision, which can not be detected by detection of "weird" strings.
Reference Paper
Sometimes the users might want to sign a jumbled mess :).
A better solution is to look for differential characteristics that you find in constructed collisions. If the conditions hold, then the message was very likely constructed in a collision attack, as the probability of bits randomly meeting the conditions are very low.
Marc Stevens wrote a collision detection library which checks for differential characteristics for MD5 and SHA-1 collision attacks.
