Random number generator attack

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 girlfriend's initials, greatly aiding Allied breaking of these encryption systems. Another example is the often predictable ways computer users choose passwords (see password cracking). Nevertheless, in the specific case of playing mixed strategy games, use of human gameplay entropy for randomness generation was studied by Ran Halprin and Moni Naor. ==Attacks==

Software RNGs Just as with other components of a cryptosystem, a software random number generator should be designed to resist certain attacks. Some attacks possible on a RNG include (from): ; Direct cryptanalytic attack: when an attacker obtained part of the stream of random bits and can use this to distinguish the RNG output from a truly random stream. ; Input-based attacks: modify the input to the RNG to attack it, for example by "flushing" existing entropy out of the system and put it into a known state. ; State compromise extension attacks: when the internal secret state of the RNG is known at some time, use this to predict future output or to recover previous outputs. This can happen when a generator starts up and has 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. Hardware RNGs 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 their 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. • Maintain complete physical control over the hardware after it has been purchased. The hardware should be kept at one place or location and need no other transmission to peer-to-peer hardware. Attacks are on the line in the network not the hardware itself. Designing a secure random number generator requires at least as high a level of care as designing other elements of a cryptographic system. ==Prominent examples==

Predictable Netscape seed Early versions of Netscape's Secure Sockets Layer (SSL) encryption protocol used pseudo-random quantities derived from a PRNG seeded with three variable values: the time of day, the process ID, and the parent process ID. These quantities are often relatively predictable, and so have little entropy and are less than random, and so that version of SSL was found to be insecure as a result. The problem was reported to Netscape in 1994 by Phillip Hallam-Baker, then a researcher in the CERN Web team, but was not fixed prior to release. The problem in the running code was discovered in 1995 by Ian Goldberg and David Wagner, who had to reverse engineer the object code because Netscape refused to reveal the details of its random number generation (security through obscurity). That RNG was fixed in later releases (version 2 and higher) by more robust (i.e., more random and so higher entropy from an attacker's perspective) seeding. Microsoft Windows 2000/XP random number generator Microsoft used an unpublished algorithm to generate random values in older versions of 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. The paper presented serious weaknesses in Microsoft's approach at the time. The paper's conclusions were based on disassembly of the code in Windows 2000, but according to Microsoft applied to Windows XP as well. Microsoft has stated that the problems described in the paper have been addressed in subsequent releases of Windows, which use a different RNG implementation. One of the generators, Dual_EC_DRBG, was favored by the National Security Agency. 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 kleptographic backdoor in the algorithm. In September 2013 The New York Times wrote that "the N.S.A. had inserted a back door into a 2006 standard adopted by N.I.S.T... called the Dual EC DRBG standard", thereby revealing that the NSA carried out a malware attack against the American people. In December 2013, Reuters reported that documents released by Edward Snowden indicated that the NSA had paid RSA Security $10 million to make Dual_EC_DRBG the default in their encryption software, and raised further concerns that the algorithm might contain a backdoor for the NSA. Due to these concerns, in 2014, NIST withdrew Dual EC DRBG from its draft guidance on random number generators, recommending "current users of Dual_EC_DRBG transition to one of the three remaining approved algorithms as quickly as possible." MIFARE Crypto-1 Crypto-1 is a cryptosystem developed by NXP for use on MIFARE chips. The system is proprietary and originally the algorithm has not been published. Upon reverse engineering of the chip, researchers from the University of Virginia and the Chaos Computer Club found an attack on Crypto-1 exploiting a poorly initialized random number generator. Debian OpenSSL 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, reduced the total entropy to the process id and made a variety of security keys vulnerable to attack. The security weakness was caused by changes made to the openssl code by a Debian developer in response to compiler warnings of accessing uninitialized memory. ==See also==