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!