Random number generator attack
Encyclopedia
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 protocol
s 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.
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
.
and are less than random, and so that version of SSL was found to be insecure as a result. The problem was notified 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 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.
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.
In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony
to sign software for the PlayStation 3
game console. The attack was made possible because Sony failed to generate a new random nonce
for each signature.
s 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).
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.
Designing a secure random number generator requires at least as high a level of care as designing other elements of a cryptographic system.
Randomization
Randomization is the process of making something random; this means:* Generating a random permutation of a sequence .* Selecting a random sample of a population ....
is typically employed. Modern cryptographic protocol
Cryptographic protocol
A security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
s often require frequent generation of random quantities (see also nonce
Cryptographic nonce
In security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
).
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
Computer virus
A computer virus is a computer program that can replicate itself and spread from one computer to another. The term "virus" is also commonly but erroneously used to refer to other types of malware, including but not limited to adware and spyware programs that do not have the reproductive ability...
that steals keys
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
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 IIWorld War II
World War II, or the Second World War , was a global conflict lasting from 1939 to 1945, involving most of the world's nations—including all of the great powers—eventually forming two opposing military alliances: the Allies and the Axis...
German code clerks were instructed to select three letters at random to be the initial rotor setting for each Enigma machine
Enigma machine
An Enigma machine is any of a family of related electro-mechanical rotor cipher machines used for the encryption and decryption of secret messages. Enigma was invented by German engineer Arthur Scherbius at the end of World War I...
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
Password cracking
Password cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password...
.)
Nevertheless, in the specific case of playing mixed strategy games, use of human gameplay entropy
Entropy
Entropy is a thermodynamic property that can be used to determine the energy available for useful work in a thermodynamic process, such as in energy conversion devices, engines, or machines. Such devices can only be driven by convertible energy, and have a theoretical maximum efficiency when...
for randomness generation was studied by Ran Halprin and Moni Naor
Moni Naor
Moni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His adviser was Manuel Blum....
.
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 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 entropyInformation entropy
In information theory, entropy is a measure of the uncertainty associated with a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message, usually in units such as bits...
and are less than random, and so that version of SSL was found to be insecure as a result. The problem was notified 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
Ian Goldberg
Ian Avrum Goldberg is a cryptographer and cypherpunk. He is best known for breaking Netscape's implementation of SSL , and for his role as Chief Scientist of Radialpoint , a Canadian software company...
and David Wagner, who had to reverse engineer
Reverse engineering
Reverse engineering is the process of discovering the technological principles of a device, object, or system through analysis of its structure, function, and operation...
the object code
Object code
Object code, or sometimes object module, is what a computer compiler produces. In a general sense object code is a sequence of statements in a computer language, usually a machine code language....
because Netscape refused to reveal the details of its random number generation (security through obscurity
Security through obscurity
Security through obscurity is a pejorative referring to a principle in security engineering, which attempts to use secrecy of design or implementation to provide security...
). 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 uses an unpublished algorithm to generate random values for its Windows operating system. These random quantities are made available to users via the CryptGenRandom
CryptGenRandom
CryptGenRandom is a cryptographically secure pseudorandom number generator function that is included in Microsoft's Cryptographic Application Programming Interface. In Win32 programs, Microsoft recommends its use anywhere random number generation is needed...
utility. In November 2007, Leo Dorrendorf et al. from the Hebrew University of Jerusalem
Hebrew University of Jerusalem
The Hebrew University of Jerusalem ; ; abbreviated HUJI) is Israel's second-oldest university, after the Technion – Israel Institute of Technology. The Hebrew University has three campuses in Jerusalem and one in Rehovot. The world's largest Jewish studies library is located on its Edmond J...
and University of Haifa
University of Haifa
The University of Haifa is a university in Haifa, Israel.The University of Haifa was founded in 1963 by Haifa mayor Abba Hushi, to operate under the academic auspices of the Hebrew University of Jerusalem....
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.
The U.S. National Institute of Standards and Technology
National Institute of Standards and Technology
The National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory, otherwise known as a National Metrological Institute , which is a non-regulatory agency of the United States Department of Commerce...
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
Dual EC DRBG
Dual_EC_DRBG or Dual Elliptic Curve Deterministic Random Bit Generator is a controversial pseudorandom number generator designed and published by the National Security Agency. It is based on the elliptic curve discrete logarithm problem and is one of the four PRNGs standardized in the NIST...
, was favored by the National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
.http://www.wired.com/politics/security/commentary/securitymatters/2007/11/securitymatters_1115 Dual_EC_DRBG uses elliptic curve technology
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
and includes a set of recommended constants. In August 2007, Dan Shumow and Niels Ferguson of Microsoft
Microsoft
Microsoft Corporation is an American public multinational corporation headquartered in Redmond, Washington, USA that develops, manufactures, licenses, and supports a wide range of products and services predominantly related to computing through its various product divisions...
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
OpenSSL
OpenSSL is an open source implementation of the SSL and TLS protocols. The core library implements the basic cryptographic functions and provides various utility functions...
package distributed with Debian
Debian
Debian is a computer operating system composed of software packages released as free and open source software primarily under the GNU General Public License along with other free software licenses. Debian GNU/Linux, which includes the GNU OS tools and Linux kernel, is a popular and influential...
Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
and other Debian-based distributions, such as Ubuntu
Ubuntu (operating system)
Ubuntu is a computer operating system based on the Debian Linux distribution and distributed as free and open source software. It is named after the Southern African philosophy of 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.
In December 2010, a group calling itself fail0verflow announced recovery of the ECDSA private key used by Sony
Sony
, commonly referred to as Sony, is a Japanese multinational conglomerate corporation headquartered in Minato, Tokyo, Japan and the world's fifth largest media conglomerate measured by revenues....
to sign software for the PlayStation 3
PlayStation 3
The is the third home video game console produced by Sony Computer Entertainment and the successor to the PlayStation 2 as part of the PlayStation series. The PlayStation 3 competes with Microsoft's Xbox 360 and Nintendo's Wii as part of the seventh generation of video game consoles...
game console. The attack was made possible because Sony failed to generate a new random nonce
Cryptographic nonce
In security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
for each signature.
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 generatorHardware random number generator
In computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. Such devices are often based on microscopic phenomena that generate a low-level, statistically random "noise" signal, such as thermal noise or the photoelectric effect or other...
s 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 generatorCryptographically secure pseudorandom number generator
A cryptographically secure pseudo-random number generator is a pseudo-random number generator with properties that make it suitable for use in cryptography.Many aspects of cryptography require random numbers, for example:...
with a seed value
Random seed
A random seed is a number used to initialize a pseudorandom number generator.The choice of a good random seed is crucial in the field of computer security...
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
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
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
Central processing unit
The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...
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 cipherStream cipherIn cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
, 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 FortunaFortuna (PRNG)Fortuna is a cryptographically secure pseudorandom number generator devised by Bruce Schneier and Niels Ferguson. It is named after Fortuna, the Roman goddess of chance.- Design :Fortuna is a family of secure PRNGs; its design...
random number generator is an example of an algorithm which uses this mechanism. - Generate passwords and passphrasePassphraseA passphrase is a sequence of words or other text used to control access to a computer system, program or data. A passphrase is similar to a password in usage, but is generally longer for added security. Passphrases are often used to control both access to, and operation of, cryptographic programs...
s 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 cardSound cardA sound card is an internal computer expansion card that facilitates the input and output of audio signals to and from a computer under control of computer programs. The term sound card is also applied to external audio interfaces that use software to generate sound, as opposed to using hardware...
s and webcamWebcamA webcam is a video camera that feeds its images in real time to a computer or computer network, often via USB, ethernet, or Wi-Fi.Their most popular use is the establishment of video links, permitting computers to act as videophones or videoconference stations. This common use as a video camera...
s may be a better source of randomness than hardware made for that purpose. See: Hardware random number generatorHardware random number generatorIn computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. Such devices are often based on microscopic phenomena that generate a low-level, statistically random "noise" signal, such as thermal noise or the photoelectric effect or other...
. - 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.