Random numbers are essential for cryptography, including the encryption of web connections with SSL. Most system administrators are aware of where the “randomness” comes from on Linux servers: /dev/random and /dev/urandom, but, if a new study presented at the Black Hat conference is right, developers and system administrators may not recognize the limitations of these mechanisms for generating random numbers, which could hinder the effectiveness of encryption methods like SSL.
To understand the problem, you need to have a handle on two related but distinct terms: entropy and randomness. Essentially, entropy concerns how uncertain a particular outcome is. The more unpredictable an outcome, the higher the entropy. If you deal from an unshuffled deck of cards, the hands are predictable — the entropy is low. With a well-shuffled deck of cards, the hands are very difficult to predict — shuffling increases entropy. A sequence of numbers with high entropy is inherently unpredictable.
Randomness can be thought of as the quality of uncertainty over a period of time; a truly random set of numbers has no predictable pattern over an infinite period.
Computers are incapable of true randomness. They’re deterministic machines that by their nature cannot generate truly random numbers. That creates something of a pickle for cryptography, which requires random numbers. Modern computers produce pseudo-random numbers, the quality of which depends on the quality of the entropy available to the system.
Pseudo-random number generators are relatively easy to understand at a high-level. They take a known good source of entropy and use it as a seed for a set of algorithms that produce a pseudo-random number. The more entropy and the better its quality, the better the pseudo-randomness. The output isn’t truly random, but it’s “random enough” with a good source of entropy that it would be impractical to figure out the pattern. Entropy is usually generated from a series of “entropy” sources — often hardware inputs like mouse movements, keyboard presses, disk I/O, and other sources.
For a variety of reasons laid out in the study, the quality of the entropy made available through /dev/urandom is frequently quite low, which impacts the quality of the pseudo-random numbers generated by the system.
Cryptographic algorithms need randomness to generate keys, otherwise the keys would be predictable and useless. OpenSSL uses its own pseudo-random number generator, which takes data from /dev/urandom for its seed.
Additionally, OpenSSL only seeds its random number generator when it starts up. That’s alright when it is only generating the occasional key, but if you hook it up to a web server and ask it to generate thousands of keys a day for HTTPS connections, the random numbers aren’t likely to be as unpredictable as is desirable — there will be predictable patterns, which, in theory at least, could allow an attacker to guess the keys.
So, there’s a two-fold problem. OpenSSL may be getting poor random data to seed its own pseudo-random number generator, and it’s reusing the same seed. Mod_ssl will try to mix things up, but it doesn’t do a very good job and its attempts at adding extra entropy into the system are essentially useless.
In reality, this isn’t likely to pose a problem for the average eCommerce store, but it seems that because most of us don’t have a clue of the quality or origin of the entropy that goes into pseudo-random number generators, our efforts at cryptography aren’t nearly as reliable as we think they are.