Unpredictability of X.509 serial numbers

Question

About X.509 certificates serial numbers the RFC 5280 says:

The serial number MUST be a positive integer assigned by the CA to each certificate. It MUST be unique for each certificate issued by a given CA (i.e., the issuer name and serial number identify a unique certificate). CAs MUST force the serialNumber to be a non-negative integer.

There is no mention of the security concerns with the serial number generation. What are the good practices? Is there any security issues with predictable (for instance sequential or based on the certificate generation date) serial numbers?

Answer 1

A non-random serial number does not imply, by itself, a security issue with the signature scheme, but, as @Jack points out, it can be used to leverage an attack. On a general basis, signature algorithms begin by hashing the input message with a given hash function; if the message or hashing process is fully controlled by the attacker, then collision resistance of the hash function becomes an important issue. On the other hand, with some randomness inserted by the signer (e.g. a random serial number, added by the issuing CA of a certificate), the signature ought to be resistant to mere collision attacks, and, ultimately, work on preimage resistance (and MD5, with all its shortcomings, still appears to be optimally resistant to preimages).

Such randomness should be inserted in an "appropriate" way, which depends on the internal structure of the hash function. Halevi and Krawczyk have specified a generic way which should be good for all hash functions, and called it RMX. It has resulted in an Internet Draft and NIST Special Publication SP-800-106. Noteworthy points are:

• RMX is meant to be applied on any binary message, but it requires generation of some random value, to be transmitted along with the message.
• Since the hashing process is modified, the signer and verifier must be aware of RMX, right at the beginning of message processing.
• RMX includes a description of how to extract the random value from the first half of a DSA/ECDSA signature (the "$r$" value, which does not depend on the signed message). This is meant to save bandwidth and be compatible with existing data formats (which do not have room for an extra "random value"), but it makes signature more complex, since the "$r$" value must then be generated before hashing the input message -- which can be cumbersome in systems where the hashing is externalized, in another module than the one holding the signature private key.
• This is a recommendation which has not yet found its way in any notable standard.

Using a random serial number is the "poor man's randomized hashing" which has the fine property of being fully compatible with existing X.509 certificate verifiers (the hashing process and the certificate formats are not altered in any way) and many CA already implemented it, albeit not for protection against collision attacks. In a certificate, the serial number occurs "early enough" in the structure, with some big fixed elements between it and the public key (namely, subject and issuer names, validity dates...), so that it suffices, with existing MD-based hash functions (MD5, SHA-1...), to prevent leverage of collision attacks. Also, a long enough random serial number ensures uniqueness with overwhelming probability without having to look up anything in a database. For proper interoperability, use a positive serial number less than $2^{159}$ (this ensures that the value encoding, as specified in ASN.1 DER, will fit in 20 bytes).

Completely unrelated to collisions and signatures, but relevant for security, predictable serial numbers leak business information. As Peter Gutmann states it in his X.509 Style Guide (an old but fun and not completely obsolete text):

by using sequential numbers a CA ends up revealing just how few certs it's actually signing (at the cost of a cert per week, the competition can find out exactly how many certs are being issued each week)

Answer 2

Predictable serial numbers were used (along with serious weaknesses in MD5) to create a rogue CA certificate in 2008. Randomizing the serial numbers would have prevented this attack.
And, obviously using a sequential serial number reveals the number of certificates signed, and requires careful state management.

In general I would say using a large (large enough that collisions are unlikely, say 128 or 160 bit) randomly generated number is best current practice, as otherwise all fields in the certificate are either known or predictable to an attacker, which may make it easier for weaknesses in the primitives (hashes or signing mechanisms) to be exploited, as it was with the MD5 attack.