14

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.

makerofthings7
  • 50,090
  • 54
  • 250
  • 536

1 Answers1

18

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:

Recommendation. The best defense is: don't use MD5! Just stop using it. CAs should use a modern hash like SHA1 or 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.

D.W.
  • 98,420
  • 30
  • 267
  • 572
  • Incredible info. I never knew it worked this way. This has been added to the linked Q&A [Checklist on how to build a CA](http://security.stackexchange.com/questions/15532/how-should-i-configure-my-offline-root-and-intermediate-ca-should-i-implement)? – makerofthings7 Jun 06 '12 at 02:05
  • Does the same advice apply to a cert signed with sha384ECDSA? Anything special I should watch out for with that one? – makerofthings7 Jun 06 '12 at 04:24
  • @makerofthings7, no, this advice primarily targets certs that use MD5. Sha384ECDSA uses SHA384 as its hash algorithm, not MD5. There are no known collision attacks on SHA384 that are practically feasible. The attacks only apply to MD5. Therefore, the attacks don't apply to Sha384ECDSA. That said... like I wrote at the end, you could always use serial numbers anyway for defense-in-depth (e.g., in case someone discovers a new attack on the hash). It's not believed to be necessary, given our current understanding of these algorithms, but I guess it can't hurt. – D.W. Jun 06 '12 at 04:34
  • I found some CRL and OCSP signatures that are MD5. Should I suppose your logic applies there as well too? – makerofthings7 Jun 06 '12 at 12:02
  • @makerofthings7, I don't know! I'd guess yes, the same logic applies. It is possible that the severity might be lower (maybe the only thing that an attacker do is forge a revocation, which is probably much less serious than forging a cert; forging a revocation is primarily a denial-of-service or annoyance attack). These are just guesses, though. – D.W. Jun 06 '12 at 16:25
  • One example may be where the attacker wants to reuse a stolen/hacked key that was revoked. Since the CRLs aren't persisted locally and expire in RAM over time, I think a spoofed CRL could be used to permit what was previously denied, making the CRL worthless. In other words since this is based on DNS & HTTP I would think it means that all the DNS hacks apply. So can I conclude that all HTTP-based (CRL or OCSP) communications are unsecure unless IPSec and DNSSec are used? – makerofthings7 Jun 06 '12 at 16:41
  • If the answer to that previous comment is "Yes" it makes me want to remove every MD5 root cert, and ban any MD5 intermediate from ever touching my system. – makerofthings7 Jun 06 '12 at 16:46
  • Seems that NONCES are used to prevent OSPF replays, Windows server supports it, Windows Clients don't http://technet.microsoft.com/en-us/library/cc770413(v=ws.10).aspx#BKMK_ManagingRevocationConfigurations – makerofthings7 Jun 07 '12 at 17:23