"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?
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.