Tuesday, December 30, 2008

Not all MD5 certs are vulnerable

UPDATE: Gah, I missed this on the first read through. They also point out that some CAs randomize their serial numbers.

I've been looking into certificates. Not all of them are vulnerable to this attack because some of them randomize their serial numbers. This shows that the solution to the attack isn't necessarily to switch from MD5 to SHA-1 (although that's a good idea). SHA-1 is also theoretically vulnerable in the near future. I would suggest that it's equally a problem that certs are vulnerable to birthday attacks (regardless of algorithm) as well as weaknesses in MD5.

This attack can only work when the contents that will be hashed are predictable. However, certificates contain two fields that are chosen by the certificate authority. One is the "serial number", the other is the "validity period".

The hackers chose Equifax/RapidSSL, because Equifax allows the hacker to predict these fields. Each time they issue a certificate, Equifax simple increments the number by one. Since they issue another certificate every few minutes, you cannot be guaranteed to guess the number the first try. In this attack, the attackers had to apply for several certificates before the predicted sequence number.

However, the serial number can be ANYTHING. It just has to be unique for every certificate, but it doesn't even have to be a number. Any text field will do.

Thawte uses what appears to be a random value. The following is a picture of certificate from Thawte:

What we see in this picture is that Thawte uses an essentially random 16-byte value of "6E:57:69:0A:10:4F:AA:FF:81:74:F8:38:8B:08:0D:F1", instead of the Equifax, which uses a simple number like "643015".

If hackers cannot predict this number, then they cannot create the necessary "hash collision", and this attack won't work. That's because the sequence number comes BEFORE the hacked portion of the certificate, not AFTER. Even using the weak MD5 hash algorithm, properly randomized serial numbers will stop this attack. Instead of calling this "MD5 considered harmful", they should have called it "Birthday Attacks against certs considered harmful".

However, I'd suggest the real way to solve this is to randomize only the lower 8-bits of the sequence number. That way, hackers will have to buy 256 certificates in order to get the correct one. This means more profit for the CA. Step 1: insecure MD5 certs. ... Step 3: Profit!


Unknown said...

I am an EE, but kind of a security hobbyist. What they are creating is a fake CA right? How does your browser know if the Serial Number generated is not correct if the signature verifying it is correct?

In other words I don't see how a random Serial Num helps anything. The signature matches the content and the root CA and thats what counts right?

Robert Graham said...

The browser doesn't check the serial number.

They don't create ONE fake certificate, they create TWO certificates: one fake, one real.

They get the real certificate signed.

However, the signature will cover not only the requested certificate, but also some fields determined by Verisign: the serial number and time period for when the certificate is valid. The hackers have to know the values of these fields in order to make their fake and real certificate hash to the same value.

This is because it's a "birthday attack". Duplicating an existing hash is difficult, equivalent to 128-bit crypto. Creating two new documents with the hash is easier, only 64-bit crypto. The weaknesses in MD5 reduce that even more, to roughly 50-bit crypto, which can be solved in a couple days using 200 playstations.

If the hackers cannot predict the serial number that will be assigned by the certificate authority, then they cannot predict what the hash is going to be, and they cannot do the birthday attack.

dreyercito said...

Just one comment. From my point of view it does not matter that the serial number is before or after the part that can be modified by the attacker, it is still information that will appear in the final certificate and that will have to be signed (and that will affect the output of the hashing algortithm used). Right?

Robert Graham said...

Right. It doesn't matter where the serial number is, it just matters that it has to be covered by the eventual hash.

Unknown said...

There are a number of possible methods to gain access to someone’s voicemail illicitly. In the UK at least, given the original police inquiry into the News of the World scandal, mobile network operators improved their security mechanisms to increase protection of users.

RapidSSL said...

Won't make any difference with serial numbers, you should be covered only eventual hash.