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 2159 (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)