Do we need hardware random number generators?

| Comments (0) | COMSEC SYSSEC
Recently there was an extensive discussion going on on the Cryptography mailing list about how to build cheap hardware based random number generators. For those of you who aren't crypto or comsec specialists, the background goes something like this: most cryptographic protocols require a reliable source of numbers which are unpredictable to your adversary 1. For instance, in SSL/TLS the client (your browser) generates a random cryptographic key and sends it to the server encrypted under the server's public key. If the attacker can predict that random key, then he can decrypt the connection, as was famously shown by Wagner and Goldberg. So, having good randomness is important.

As I mentioned previously, standard procedure in comsec applications is to use a cryptographically secure PRNG which is seeded with data which is unpredictable to the attacker. But this still leaves us with the question of how we're going to seed the PRNG. The most common thing to do is to seed it with system events (network packets, drive timings, etc.). In principle, of course, this isn't entirely unpredictable: if you were on the same network as the target machine you could observer packets; if you knew the layout of the drive, you might be able to predict how long things would take, etc. (and older PRNGs that weren't wired into the OS used fewer sources of randomness). In any case, these sources aren't physically random the way that, say, radioactive decay is. There's a nontrivial contingent of the security community which is extremely interested (some would say obsessed) in physical/hardware random sources of randomness. [This goes back at least to von Neumann's famous statement about those who consider arithmetical methods of producing random numbers being in a state of sin.] The thread I'm pointing to above has a variety of suggestions for cheap external hardware randomness sources.

My general intuition is that while this sort of thing doesn't do any harm, it's not really necessary either. The amount of entropy you actually need to have a secure system is surprisingly small: 80-128 bits is enough in most situations, and most systems gather that kind of entropy in the normal course of business. For instance, in a system with a GUI, just collecting the low order (odd/even) bit of each mouse click coordinate gets you to 128 bits in 64 clicks, which isn't much. Even on unattended systems, there's probably enough timing randomness in hard drive behavior to get you to 128 bits relatively randomly. Even in cases where there aren't any unobservable behaviors and the PRNG is basically broken, the effort to reverse engineer the state of the PRNG becomes near prohibitive very quickly, as is the case with the Debian PRNG and DHE vs. RSA [*]. I'm not aware of any evidence that well-designed OS-based PRNGs like /dev/random are vulnerable because of insufficient entropy gathering.

1. Technical note: not as many as you'd think, though. Many protocols use random numbers in contexts where only unique numbers are required. For instance, in SSL/TLS and IKE it's standard practice to use cryptographically random nonces (called "Random" in TLS). However, the security guarantees of the protocol apply as long as the numbers are unique—you could probably just use a counter. The advantage of using long random numbers is that you don't need to store counter state to ensure uniqueness.

Leave a comment