Random number generator attack

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities (see also nonce).

Quality in the random number generation (RNG) process is almost always required for security, and lack of quality generally provides attack vulnerabilities and so to lack of security, even to complete compromise, in cryptographic systems. The RNG process is particularly attractive to attackers because it is typically a single isolated hardware or software component easy to locate. If the attacker can substitute pseudo-random bits generated in a way he can predict, security is totally compromised, yet generally undetectable by any upstream test of the bits. Furthermore, such attacks require only a single access to the system that is being compromised. No data need be sent back in contrast to, say, a computer virus that steals keys and then e-mails them to some drop point.

Human generation of random quantities

Humans generally do poorly at generating random quantities. Magicians, professional gamblers and con artists depend on the predictability of human behavior. In World War II German code clerks were instructed to select three letters at random to be the initial rotor setting for each Enigma machine message. Instead some chose predictable values like their own or a girl-friend's initials, greatly aiding allied breaking of these encryption systems. Another example is the often predictable ways computer users choose passwords. "See:" Password cracking.

Prominent examples of random number generator security issues

Early versions of Netscape's Secure Socket Layer (SSL) encryption protocol used pseudo-random quantities derived from a PRNG seeded with just three values, the time of day, the process ID, and the parent process ID. These quantities are often relatively predictable, making that version of SSL insecure. The problem was discovered in 1995 by Ian Goldberg and David Wagner [ [http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html DDJ, Jan96: Randomness and Netscape Browser ] ] , who had to reverse engineer the object code because Netscape refused to reveal the details of its random number generation. The SSL RNG was fixed in later releases (version 2 and higher) by more robust seeding.

Microsoft uses an unpublished algorithm to generate random values for its Windows operating system. These random quantities are made available to users via the CryptGenRandom utility. In November 2007, Leo Dorrendorf et al. from the Hebrew University of Jerusalem and University of Haifa published a paper titled "Cryptanalysis of the Random Number Generator of the Windows Operating System" [http://eprint.iacr.org/2007/419.pdf] . The paper presented serious weaknesses in the Microsoft approach. The paper's conclusions were based on disassembly of the code in Windows 2000, but according to Microsoft apply to XP as well [ [http://www.computerworld.com/action/article.do?command=viewArticleBasic&articleId=9048438 Microsoft confirms that XP contains random number generator bug ] ] .

The U.S. National Institute of Standards and Technology has published a collection of "deterministic random bit generators" it recommends as NIST Special Publication 800-90 [http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf] . One of the generators, Dual_EC_DRBG, was favored by the National Security Agency. [http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115] Dual_EC_DRBG uses elliptic curve technology and includes a set of recommended constants. In August 2007, Dan Shumow and Niels Ferguson of Microsoft showed that the constants could be constructed in such a way as to create a secret backdoor to the algorithm. [http://rump2007.cr.yp.to/15-shumow.pdf]

In May, 2008, security researcher Luciano Bello revealed his discovery that changes made in 2006 to the random number generator in the version of the openssl package distributed with Debian Linux and other Debian-based distributions, such as Ubuntu, dramatically reduced the entropy of generated values and made a variety of security keys vulnerable to attack. [http://www.debian.org/security/2008/dsa-1571] [http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2008-0166] The security weakness was caused by changes made to the openssl code by a Debian developer in response to compiler warnings of apparently redundant code. [http://cryptogon.com/?p=2635] Key types affected include SSH keys, OpenVPN keys, DNSSEC keys, key material for use in X.509 certificates and session keys used in SSL/TLS connections. Keys generated with GnuPG or GNUTLS are not affected as these programs used different methods to generate random numbers. Non-Debian-based Linux distributions are also unaffected. This security vulnerability was promptly patched after it was reported.

Attacks on software random number generators

Just as with other components of a cryptosystem, a software random number generator should be designed to resist certain attacks. Exactly which attacks must be defended against depends on the system, but here are a few:
* If an attacker obtains most of the stream of random bits, it should be infeasible for them to compute any additional parts of the stream.
* If an attacker observes the internal state of the random number generator, they should not be able to work backwards and deduce previous random values.
* If an attacker observes the internal state of the random number generator, they will necessarily be able to predict the output until enough additional entropy is obtained. However, if entropy is added incrementally, the attacker may be able to deduce the values of the random bits that were added and obtain the new internal state of the random number generator (a state compromise extension attack).
* If an attacker can control the supposedly random inputs to the generator, they may be able to "flush" all the existing entropy out of the system and put it into a known state.
* When a generator starts up, it will often have little or no entropy (especially if the computer has just been booted and followed a very standard sequence of operations), so an attacker may be able to obtain an initial guess at the state.

Attacks on hardware random number generators

A number of attacks on hardware random number generators are possible, including trying to capture radio-frequency emissions from the computer (obtaining hard drive interrupt times from motor noise, for example), or trying to feed controlled signals into a supposedly random source (such as turning off the lights in a lava lamp or feeding a strong, known signal into a sound card).

RNG subversion

Subverted random numbers can be created using a cryptographically secure pseudorandom number generator with a seed value known to the attacker but concealed in the software. A relatively short, say 24 to 40 bit, portion of the seed can be truly random to prevent tell-tale repetitions, but not long enough to prevent the attacker from recovering, say, a "randomly" produced key.

Random numbers typically go through several layers of hardware and software before they are used. Bits may be generated in a peripheral device, sent over a serial cable, collected in an operating system utility and retrieved by a system call. The subverted bits can be substituted at any point in this process with little likelihood of detection.

A hardware circuit to produce subverted bits can be built on an integrated circuit a few millimeters square. The most sophisticated hardware random number generator can be subverted by placing such a chip anywhere upstream of where the source of randomness is digitized, say in an output driver chip or even in the cable connecting the RNG to the computer. The subversion chip can include a clock to limit the start of operation to some time after the unit is first turned on and run through acceptance tests, or it can contain a radio receiver for on/off control. It could be installed by the manufacturer at the behest of his national signals intelligence service, or added later by anyone with physical access. CPU chips with built-in hardware random number generators can be replaced by compatible chips with a subverted RNG in the chips firmware.

Defenses

* Mix (with, for example, xor) hardware generated random numbers with the output of a good quality stream cipher, as close to the point of use as possible. The stream cipher key or seed should be changeable in a way that can be audited and derived from a trustworthy source, e.g. dice throws. The Fortuna random number generator is an example of an algorithm which uses this mechanism.
* Generate passwords and passphrases using a true random source. Some systems select random passwords for the user rather than let users propose their own.
* Use encryption systems that document how they generate random numbers and provide a method to audit the generation process.
* Build security systems with off the shelf hardware, preferably purchased in ways that do not reveal its intended use, e.g. off the floor at a large retail establishment. From this perspective, sound cards and webcams may be a better source of randomness than hardware made for that purpose. "See:" Hardware random number generator.
* Maintain complete physical control over the hardware after it has been purchased.

Designing a secure random number generator requires at least as high a level of care as designing other elements of a cryptographic system.

References

* [http://www.cs.berkeley.edu/~daw/papers/ddj-netscape.html Randomness and the Netscape Browser] ,Ian Goldberg and David Wagner, "Dr. Dobb's Journal", January 1996, pp66–70.

* [http://www.schneier.com/paper-prngs.html Cryptanalytic Attacks on Pseudorandom Number Generators] , J. Kelsey, Bruce Schneier, David Wagner, and C. Hall, Fast Software Encryption, Fifth International Workshop Proceedings (March 1998), Springer-Verlag, 1998, pp. 168-188.

* [http://eprint.iacr.org/2006/086.pdf Analysis of the Linux Random Number Generator] Zvi Gutterman, Benny Pinkas and Tzachy Reinman, in IEEE S&P (Oakland Conference), May 2006, pp. 371-385.

* Randomness Requirements for Security. D. Eastlake, J. Schiller, S. Crocker, RFC 4086 (obsoletes RFC1750), 2006.

* [http://csrc.nist.gov/publications/nistpubs/800-90/SP800-90revised_March2007.pdf Recommendation for Random Number Generation Using Deterministic Random Bit Generators] , Elaine Barker and John Kelsey, NIST Special Publication 800-90. Revised March 2007