Design and Analysis of /dev/random, a Pseudorandom Number Generator

The ability to produce random numbers is an important aspect of many cryptographic applications. This document examines a method of constructing an algorithm that behaves in a non-deterministic manner in order to produce unpredictable outputs. Specifically, this paper examines the design of the pseudo random number generator /dev/random. 1 PRNG’s and the importance of randomness In many cryptographic applications, security relies on random numbers. Designers have built systems assuming the availability of random looking numbers to use as nonces [2], session keys, and salts to name a few. If the randomness of these values are compromised, then the security of the application is likewise compromised. A few years ago, a security flaw was found in the Netscape browser [4]. Netscape’s implementation of SSL, a cryptographic protocol, was broken by attacking the pseudo random number generator (PRNG). The security of SSL relied on the unpredictability of the secret key, which was generated by the PRNG. Once this was compromised, an eavesdropper could decode encrypted communications. 1.1 What ”random looking ” means Consider a programmer implementing a cryptographic protocol that requires a random number. The implementor may define ”random looking ” as something quite different then the designer of the protocol. The security may be relinquished should the programmer implement the protocol with a random 1 number generator that is not as cryptographically strong as intended by the designer. A formal notion of what it means to be random is required to clarify the ambiguous nature of the definition of ”random looking”. A formal notion that is often used is as follows; Define S to be the set integers in the range 0...2 n − 1. Let s ∈ S. Given that each of the different values in S have equal probability, then if probability that an adversary can determine the value of s is 1/2 n, then s is defined as random. Due to the birthday attack, an adversary on average would have to try 2 n−1 values before guessing s [5].