Random Number Generators and Information Security
From Computing and Software Wiki
| Line 10: | Line 10: | ||
[[Image:NSprotocol.JPG]] | [[Image:NSprotocol.JPG]] | ||
| - | == Vulnerability == | + | == Vulnerability to Attack == |
| + | 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. <ref>Wikipedia: Random number generator attack <http://en.wikipedia.org/wiki/Random_number_generator_attack></ref> | ||
| + | |||
| + | === Examples of Inadequate Random Number Generators === | ||
| + | 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, 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.<BR> | ||
| + | Microsoft uses an unpublished algorithm to generate random values for its Windows operating system. These random quantities are made availabe 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 the Microsoft approach. The paper's conclusions were based on based on disassembly of the code in Windows 2000, but according to Microsoft apply to XP as well.<BR> | ||
| + | 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. 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 secret backdoor to the algorithm. <ref>Wikipedia: Random number generator attack <http://en.wikipedia.org/wiki/Random_number_generator_attack></ref> | ||
| + | |||
| + | === 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:<BR> | ||
| + | <ul> | ||
| + | <li>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. | ||
| + | <li>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. | ||
| + | <li>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). | ||
| + | <li>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. | ||
| + | <li>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. <ref>Wikipedia: Random number generator attack <http://en.wikipedia.org/wiki/Random_number_generator_attack></ref> | ||
| + | </ul> | ||
| + | |||
| + | === 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). <ref>Wikipedia: Random number generator attack <http://en.wikipedia.org/wiki/Random_number_generator_attack></ref> | ||
== Two Kinds of Randomness == | == Two Kinds of Randomness == | ||
Revision as of 21:09, 2 December 2007
A random number generator (often abbreviated as RNG) is a computational or physical device designed to generate a sequence of numbers or symbols that lack any pattern, i.e. appear random. Computer-based systems for random number generation are widely used, but often fall short of this goal, though they may meet some statistical tests for randomness intended to ensure that they do not have any easily discernible patterns. Methods for generating random results have existed since ancient times, including dice, coin flipping, the shuffling of playing cards, the use of yarrow stalks in the I Ching, and many other techniques.
The many applications of randomness have led to many different methods for generating random data. These methods may vary as to how unpredictable or statistically random they are, and how quickly they can generate random numbers.
Before the advent of computational random number generators, generating large amount of sufficiently random numbers (important in statistics) required a lot of work. Results would sometimes be collected and distributed as random number tables. <ref name="wikiRNG">Wikipedia: Random Number Generation</ref>
Contents |
Relevance to Information Security
Vulnerability to Attack
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. <ref>Wikipedia: Random number generator attack <http://en.wikipedia.org/wiki/Random_number_generator_attack></ref>
Examples of Inadequate Random Number Generators
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, 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 availabe 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 the Microsoft approach. The paper's conclusions were based on 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. 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 secret backdoor to the algorithm. <ref>Wikipedia: Random number generator attack <http://en.wikipedia.org/wiki/Random_number_generator_attack></ref>
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. <ref>Wikipedia: Random number generator attack <http://en.wikipedia.org/wiki/Random_number_generator_attack></ref>
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). <ref>Wikipedia: Random number generator attack <http://en.wikipedia.org/wiki/Random_number_generator_attack></ref>
Two Kinds of Randomness
True Randomness
Physical Methods
The earliest methods for generating random numbers - dice, coin flipping, roulette wheels are still used today, mainly in games and gambling as they tend to be too slow for applications in statistics and cryptography.
Some physical phenomena, such as thermal noise in zener diodes appear to be truly random and can be used as the basis for hardware random number generators. However, many mechanical phenomena feature asymmetries and systematic biases that make their outcomes not truly random. The many successful attempts to exploit such phenomena by gamblers, especially in roulette and blackjack are testimony to these effects.
There are several imaginative sources of random numbers online. A common technique is hashing a frame of a video stream from an unpredictable source. Most notable perhaps was Lavarand which used images of a number of lava lamps. Lithium Technologies uses a camera pointed at the sky on a windy and cloudy day. Random.org has a more obvious approach of listening to atmospheric noise. Details about how they turn their input into random numbers can be found on their respective sites.
Completely randomized design falls within the category of true random number generation. The generation of true random numbers outside the computer environment is based on the theory of entropy. Sources of entropy include nuclear decay and atmospheric conditions. HotBits uses radioactive decay, while Random.org uses radio noise to generate randomness.<ref name="wikiRNG"/>
Examples
Pros and Cons
Pseudo-Randomness
Computational Methods
Examples
Pros and Cons
Verdict
Conclusion
See Also
External Links
References
<references />
1. Bishop, M. 2004. Introduction to Computer Security. Prentice Hall PTR.
2. Wikipedia. 2007. Retrieved November 27, 2007. <http://wikipedia.org>
3. Haahr, M. 2007. Random.org. Retrieved November 27, 2007. <http://www.random.org>
--Caoff 19:00, 1 December 2007 (EST)
