Random Number Generators and Information Security

From Computing and Software Wiki

(Difference between revisions)

Current revision as of 05:03, 10 December 2007

A random number generator (often abbreviated as RNG) is a device that generates a sequence of numbers without any discernible pattern. A RNG must pass certain statistical tests to be considered valid. There are many applications of randomness, such as gambling, game simulation and, of particular interest to this wikipage, cryptography. The wide use for random numbers has led to many different methods for their generation, but they all fall under one of two categories: physical or computational. Both have advantages and disadvantages, depending on whether efficiency or security is the top priority.^[2]
^[5]

Relevance to Information Security

Random numbers are used in many aspects of computer science. This wiki page discusses the particular relevance of random numbers with information security -- its applications in cryptography.
For example, the Needham-Schroeder Protocol includes random numbers in the message to protect data integrity. A RNG that gives predictable output would make the system vulnerable to replay attacks. Since a system is only as secure as its weakest component, random number generators are a crucial part of information security.
^[1]

Vulnerability to attack

The RNG process is usually a single isolated component easy to locate, making it an attractive target for attackers. If an attacker can predict the sequence of supposedly random numbers, data integrity and confidentiality are compromised. An attack on RNG is difficult to detect by any upstream test of the numbers.^[3] Furthermore, such attacks require only a single access to the system. No data need be sent back in contrast to, for example, a computer virus that steals keys and then e-mails them to some drop point.^Phishing

For example, the RANDU random number algorithm used for decades on mainframe computers was seriously flawed, and as a result a lot of research work of that period is less reliable than it might have been.^[3]

Microsoft uses the CryptGenRandom function to generate random values for its Windows operating system. This function is included in Microsoft's Cryptographic Application Programming Interface, and is used whenever random numbers are needed. It is said to be crytographically secure, but the specifics of the algorithm have not been officially published and verified. Researchers have used reverse engineering to test it and have discovered security concerns. An attacker needs only to steal the state bits once, and then they can persistently violate the security of a CryptGenRandom instance and even determine past random numbers generated. This is a serious problem, since the process can be run backwards once the state bits are known, and information already sent are compromised. For example, if the user has made online purchases from websites such as eBay, the random key used to encrypt credit card information can be recovered by an attacker. Moreoever, the CryptGenRandom function runs in user mode, so anyone with access to a regular user account on a system can easily obtain access to important information such as the state bits.^[3]

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.^[2]

The generation of true random numbers through measuring physical phenomena is based on the theory of entropy. For example, HotBits is an online generator of true random numbers, using timing successive pairs of radioactive decays detected by a Geiger-Müller tube interfaced to a computer. This process is governed by the inherent uncertainty in the quantum mechanical laws of nature.^[6] RANDOM.ORG, on the other hand, looks at variations in the amplitude of atmospheric noise.^[4] Even lava lamps have been used to generate random numbers -- images of the lamps are converted into an unique video stream.^[8]

Pseudorandomness - Computational methods

Computational methods use mathematical formulae or simply precalculated tables to produce sequences of numbers that appear random. Since the computer follows a deterministic algorithm to generate these numbers, they are inherently predictable.

For example, Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub. It generates sequences of random numbers with the following formula: x_n+1 = (x_n)² mod M, where M = pq, p and q are both prime numbers. The developers of this method have proved that it is extremely secure. To crack this algorithm would essentially require factorization of large primes, which is assumed to be mathematically infeasible. With a large M, the output of BBS displays no nonrandom patterns that can be discovered with a reasonable amount of calculation.^[7]

Verdict

Physical Methods are:

Slower than computational methods, since sequences of random numbers are generated in real-time through measuring physical phenomena.
Nondeterministic.
Truly unpredictable; this characteristic "can be traced to the laws of quantum mechanics^[2]", which are unpredictable as we know them.

Computational Methods:

Efficient: long sequences of numbers can be produced very quickly.
Deterministic: given the seed state, any sequence of numbers can be reproduced anytime. This can be an advantage if past sequences are needed at a later date for validation or analysis purposes. However, it may make the system vulnerable to replay attacks (see Vulnerability to Attacks sectiona bove).
Periodicity: all sequences eventually repeat themselves. Despite sounding dubious, this characteristic does not present a practical problem, as the periods of most PRNG's used today are very large and thus sequences do not actually repeat in realistic situations.^[4]

The basic difference between PRNGs and TRNGs can be explained with the analogy of rolling a die. PRNGs produce sequences of numbers using mathematical formulae or precalculated lists (ie. someone performed many trials and recorded the results), and output numbers from the sequences (ie. the next number on the pre-recorded list). The numbers appear random, but they are really predetermined.^[4] If an attacker obtains the algorithm (the list of numbers) and the seed state (the starting number), he or she can predict every "random" number in the sequence.
TRNGs measure physical phenomena (ie. actually rolling the die and reading out the number).^[4] They are as unpredictable as the physical phenomenon used. Even if the attacker knows how the numbers are generated and obtains a record of past numbers, he or she cannot predict the next number with any certainty.
Both methods have their advantages and disadvantages. When efficiency is a priority, such as in simulation and modeling applications, computational methods are more appropriate. When unpredictability is crucial, such as in the case of data encryption, physical generators are generally preferred.

Conclusion

To fully understand information security, we must understand how each component of the system works. Random number generators are an important part of any information security system because of their relevance in cryptography. To protect data integrity and confidentiality better, a RNG that produces fast and truly unpredictable random numbers is crucial. The RNGs in use today all have advantages and disadvantages. They are far from perfect and are still being improved today.

External Links

RANDOM.ORG
HotBits
Lavarnd
Psychic Science
GraphPad Software
Research Randomizer
The pLab Project

References

1. Bishop, M. 2004. Introduction to Computer Security. Prentice Hall PTR.
2. Wikipedia: Random Number Generation. 2007. Retrieved November 27, 2007.
3. Wikipedia: Random number generator attack. 2007. Retrieved November 27, 2007.
4. Haahr, M. 2007. Random.org. Retrieved November 27, 2007. Random.org
5. California Soil Resource Lab. 2007. Retrieved November 27, 2007.
6. HotBits. 2007. Retrieved November 27, 2007.
7. Wikipedia: Blum Blum Shub. 2007. Retrieved November 27, 2007.
8. Lavarnd. 2007. Retrieved November 27, 2007.

--Caoff 11:58, 09 December 2007 (EST)

@@ Line 1: / Line 1: @@
-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.<BR>
+A '''random number generator''' (often abbreviated as RNG) is a device that generates a sequence of numbers without any discernible pattern. A RNG must pass certain statistical tests to be considered valid. There are many applications of randomness, such as gambling, game simulation and, of particular interest to this wikipage, cryptography. The wide use for random numbers has led to many different methods for their generation, but they all fall under one of two categories: physical or computational. Both have advantages and disadvantages, depending on whether efficiency or security is the top priority.<sup>[2]</sup> <BR>
+[[Image:Rng.png]]<sup>[5]</sup><BR>
-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.<BR>
+== Relevance to Information Security ==
+Random numbers are used in many aspects of computer science. This wiki page discusses the particular relevance of random numbers with information security -- its applications in cryptography.<BR>
+For example, the Needham-Schroeder Protocol includes random numbers in the message to protect data integrity. A RNG that gives predictable output would make the system vulnerable to replay attacks. Since a system is only as secure as its weakest component, random number generators are a crucial part of information security.<BR>
+[[Image:NSprotocol.JPG]]<sup>[1]</sup>
-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><BR>
+== Vulnerability to attack ==
+The RNG process is usually a single isolated component easy to locate, making it an attractive target for attackers. If an attacker can predict the sequence of supposedly random numbers, data integrity and confidentiality are compromised. An attack on RNG is difficult to detect by any upstream test of the numbers.<sup>[3]</sup> Furthermore, such attacks require only a single access to the system. No data need be sent back in contrast to, for example, a computer virus that steals keys and then e-mails them to some drop point.<sup>[[Phishing]]</sup>
+For example, the RANDU random number algorithm used for decades on mainframe computers was seriously flawed, and as a result a lot of research work of that period is less reliable than it might have been.<sup>[3]</sup>
-== Relevance to Information Security ==
+Microsoft uses the CryptGenRandom function to generate random values for its Windows operating system. This function is included in Microsoft's Cryptographic Application Programming Interface, and is used whenever random numbers are needed. It is said to be crytographically secure, but the specifics of the algorithm have not been officially published and verified. Researchers have used reverse engineering to test it and have discovered security concerns. An attacker needs only to steal the state bits once, and then they can persistently violate the security of a CryptGenRandom instance and even determine past random numbers generated. This is a serious problem, since the process can be run backwards once the state bits are known, and information already sent are compromised. For example, if the user has made online purchases from websites such as eBay, the random key used to encrypt credit card information can be recovered by an attacker. Moreoever, the CryptGenRandom function runs in user mode, so anyone with access to a regular user account on a system can easily obtain access to important information such as the state bits.<sup>[3]</sup><BR><BR>
-[[Image:crypt.JPG]]
-[[Image:NSprotocol.JPG]]
-== Vulnerability ==
+== 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.<sup>[2]</sup><BR>
-== Two Kinds of Randomness ==
+The generation of true random numbers through measuring physical phenomena is based on the theory of entropy. For example, HotBits is an online generator of true random numbers, using timing successive pairs of radioactive decays detected by a Geiger-Müller tube interfaced to a computer. This process is governed by the inherent uncertainty in the quantum mechanical laws of nature.<sup>[6]</sup> RANDOM.ORG, on the other hand, looks at variations in the amplitude of atmospheric noise.<sup>[4]</sup> Even lava lamps have been used to generate random numbers -- images of the lamps are converted into an unique video stream.<sup>[8]</sup>
-=== 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.<BR>
-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.<BR>
+=== Pseudorandomness - Computational methods ===
+Computational methods use mathematical formulae or simply precalculated tables to produce sequences of numbers that appear random. Since the computer follows a deterministic algorithm to generate these numbers, they are inherently predictable.
-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.<BR>
+For example, Blum Blum Shub (BBS) is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub. It generates sequences of random numbers with the following formula: x<sub>n+1</sub> = (x<sub>n</sub>)<sup>2</sup> mod M, where M = pq, p and q are both prime numbers. The developers of this method have proved that it is extremely secure. To crack this algorithm would essentially require factorization of large primes, which is assumed to be mathematically infeasible. With a large M, the output of BBS displays no nonrandom patterns that can be discovered with a reasonable amount of calculation.<sup>[7]</sup>
-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"/><BR>
-==== Examples ====
-==== Pros and Cons ====
-=== Pseudo-Randomness ===
-==== Computational Methods ====
-==== Examples ====
-==== Pros and Cons ====
 === Verdict ===
+Physical Methods are:
+<ul><li>Slower than computational methods, since sequences of random numbers are generated in real-time through measuring physical phenomena.
+<li>Nondeterministic.
+<LI>Truly unpredictable; this characteristic "can be traced to the laws of quantum mechanics<sup>[2]</sup>", which are unpredictable as we know them.</ul>
+<BR>Computational Methods:
+<UL><LI>Efficient: long sequences of numbers can be produced very quickly.
+<LI>Deterministic: given the seed state, any sequence of numbers can be reproduced anytime. This can be an advantage if past sequences are needed at a later date for validation or analysis purposes. However, it may make the system vulnerable to replay attacks (see Vulnerability to Attacks sectiona bove).
+<LI>Periodicity: all sequences eventually repeat themselves. Despite sounding dubious, this characteristic does not present a practical problem, as the periods of most PRNG's used today are very large and thus sequences do not actually repeat in realistic situations.<sup>[4]</sup></UL>
+<BR>The basic difference between PRNGs and TRNGs can be explained with the analogy of rolling a die. PRNGs produce sequences of numbers using mathematical formulae or precalculated lists (ie. someone performed many trials and recorded the results), and output numbers from the sequences (ie. the next number on the pre-recorded list). The numbers appear random, but they are really predetermined.<sup>[4]</sup> If an attacker obtains the algorithm (the list of numbers) and the seed state (the starting number), he or she can predict every "random" number in the sequence.<BR>
+TRNGs measure physical phenomena (ie. actually rolling the die and reading out the number).<sup>[4]</sup> They are as unpredictable as the physical phenomenon used. Even if the attacker knows how the numbers are generated and obtains a record of past numbers, he or she cannot predict the next number with any certainty.<BR>
+Both methods have their advantages and disadvantages. When efficiency is a priority, such as in simulation and modeling applications, computational methods are more appropriate. When unpredictability is crucial, such as in the case of data encryption, physical generators are generally preferred.
 == Conclusion ==
-== References ==
+To fully understand information security, we must understand how each component of the system works. Random number generators are an important part of any information security system because of their relevance in cryptography. To protect data integrity and confidentiality better, a RNG that produces fast and truly unpredictable random numbers is crucial. The RNGs in use today all have advantages and disadvantages. They are far from perfect and are still being improved today.
-<references />
-. Bishop, M. 2004. Introduction to Computer Security. Prentice Hall PTR.<BR>
-. Wikipedia. 2007. Retrieved November 27, 2007. <http://wikipedia.org><BR>
-. Haahr, M. 2007. Random.org. Retrieved November 27, 2007. <http://www.random.org><BR>
 == See Also ==
+[[Payment Card Industry Data Security Standard]] <BR>
+[[The Mitnick attack]] <BR>
+[[Anti-spam Systems and Techniques]] <BR>
+[[Electronic Voting Systems]] <BR>
+[[Biometrics in Information Security]] <BR>
+[[Biometric Systems and Security Design Principles]] <BR>
+[[Honeypot]] <BR>
+[[Piggybacking]] <BR>
+[[Security and Storage Mediums]] <BR>
+[[Operating Systems Security]] <BR>
+[[Autocomplete]] <BR>
+[[Internet Cookies and Confidentiality]] <BR>
+[[Identity Theft]] <BR>
 == External Links ==
---[[User:Caoff|Caoff]] 19:00, 1 December 2007 (EST)
+[http://www.random.org RANDOM.ORG] <BR>
+[http://www.fourmilab.ch/hotbits/ HotBits] <BR>
+[http://www.lavarnd.org/ Lavarnd] <BR>
+[http://www.mdani.demon.co.uk/para/random.htm Psychic Science] <BR>
+[http://www.graphpad.com/quickcalcs/randomN1.cfm GraphPad Software] <BR>
+[http://www.randomizer.org/ Research Randomizer] <BR>
+[http://random.mat.sbg.ac.at/ The pLab Project] <BR>
+== References ==
+. Bishop, M. 2004. Introduction to Computer Security. Prentice Hall PTR.<BR>
+. [http://en.wikipedia.org/wiki/Random_number_generation Wikipedia: Random Number Generation]. 2007. Retrieved November 27, 2007.<BR>
+. [http://en.wikipedia.org/wiki/Random_number_generator_attack Wikipedia: Random number generator attack]. 2007. Retrieved November 27, 2007.<BR>
+. Haahr, M. 2007. Random.org. Retrieved November 27, 2007. [http://www.random.org Random.org]<BR>
+. [http://casoilresource.lawr.ucdavis.edu/drupal/node/371 California Soil Resource Lab]. 2007. Retrieved November 27, 2007.<BR>
+. [http://www.fourmilab.ch/hotbits/ HotBits]. 2007. Retrieved November 27, 2007.<BR>
+. [http://en.wikipedia.org/wiki/Blum_Blum_Shub Wikipedia: Blum Blum Shub]. 2007. Retrieved November 27, 2007.<BR>
+. [http://www.lavarnd.org Lavarnd]. 2007. Retrieved November 27, 2007.<BR>
+--[[User:Caoff|Caoff]] 11:58, 09 December 2007 (EST)

Random Number Generators and Information Security

From Computing and Software Wiki

Current revision as of 05:03, 10 December 2007

Contents

Relevance to Information Security

Vulnerability to attack

Two kinds of randomness

True randomness - Physical methods

Pseudorandomness - Computational methods

Verdict

Conclusion

See Also

External Links

References

Views

Personal tools

Navigation

Search

Toolbox