How does adding a random serial number improve a certificate's security?

Question

This article says:

"Finding collisions is a tricky process, since it requires you to muck with the bits of the public key embedded in the certificate (see this paper for more details). Also, Microsoft could have prevented this somewhat by adding a random serial number to the cert, which they didn't do."

My question is how does adding a random value to a certificate improve security? Couldn't the attacker simply generate a serial number to create a MD5 collision?

Update:

Here is information on how Microsoft implements randomization in a CA key. I'm not sure of the benefits and drawbacks of each.

Configure Serial Number Generation

In a Windows 2000 CA, two types of fixed-length serial numbers are generated. The registry can be modified to generate one or the other type. The default serial number is (from high to low): a DWORD from GetTickCount() + a USHORT CA cert index (0 to start) + a DWORD RequestId (10 bytes/20 hexadecimal digits). The alternate form is: one byte derived from the registry + a DWORD RequestId + 8 bytes of CryptGenRandom output + a USHORT CA cert index + a DWORD RequestId (19 bytes/38 hexadecimal digits).

To enable the alternate form and set the byte derived from the registry, use the following command:

    certutil –setreg ca\HighSerial 0x33 

The byte value specified will be modified to clear the sign bit and to set a bit in the high nibble to work around serial number encoding ambiguity bugs in certain non-Microsoft PKI applications.

In a Windows Server 2003 CA, three types of fixed-length serial numbers are generated. The default and alternate forms are the same as in Windows 2000. The Windows 2000 alternate form uses a new random 8 bytes generated by CryptGenRandom for each serial number. The new alternate form for Windows Server 2003 uses a fixed random 8 bytes from CryptGenRandom, generated during the first attempt to issue a certificate, and saved in the registry as 8 bytes of fixed CryptGenRandom output + a USHORT CA cert index + a DWORD RequestId (14 bytes/28 hexadecimal digits).

To enable the new alternate form in the registry, use the following command:

   certutil –setreg ca\HighSerial 0xffffffff 

Since the fixed random 8 bytes from CryptGenRandom are encoded as a string and saved in the registry, you could set them directly and cause them to be used for new serial numbers. In fact, any length hexadecimal string could be set in the registry (but there must be an even number of digits). The number of bytes used from the registry will be reduced if it would overflow a total of 19 bytes for the serial number. The high byte is manipulated as described previously to avoid problems with certain non-Microsoft applications. The IETF standards specify a maximum of 20 byte serial numbers.

Answer 1

Short answer. The benefit is from an unpredictable serial number, not from any old serial number.

Indeed, a sequential serial number adds no security, as it is easily predictable. But randomizing the serial number (so it is hard to predict) does make it harder to exploit the known collision attacks on MD5 to get a forged certificate. Let me explain.

Background. When a CA issues a cert, it includes a signature on MD5(P), for some certificate payload P that includes a public key, a domain name, and a serial number. The known collision attacks on MD5 allow the attacker to choose two values P and Q that have the same MD5 hash. This can be used to attack CAs that use MD5, as follows. The attacker uses the MD5 collision attacks to find P,Q with the following property: P is a benign certificate payload that the CA would willingly sign (e.g., a cert for some new domain that the attacker controls), but Q is an evil certificate payload that the CA would never sign (e.g., a cert for microsoft.com). The attacker sends a cert request corresponding to P to the CA; the CA signs it and returns the signed cert; and then the signature on this cert will also be a valid signature on Q.

Note that this attack requires the attacker to predict the value of the serial number that'll be used when the CA signs the cert for P. If serial numbers are assigned sequentially, this prediction task is easy. But if serial numbers are (say) a cryptographically-random 128-bit number, then the attack no longer applies. Therefore, some have suggested using random serial numbers as a mitigation.

Further details. See the following research paper for more details:

• Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate, Marc Stevens and Alexander Sotirov and Jacob Appelbaum and Arjen Lenstra and David Molnar and Dag Arne Osvik and Benne de Weger, CRYPTO 2009. Website: http://www.win.tue.nl/hashclash/rogue-ca/

Recommendation. The best defense is: don't use MD5! Just stop using it. CAs should use a modern hash like SHA256 or SHA2. They should never use MD5 when issuing certs.

But if for some reason you are forced to use MD5, randomizing your serial numbers is a reasonable mitigation. Actually, using a random serial number might not be a bad idea, no matter what hash algorithm you use, as a form of belt-and-suspenders defense-in-depth.