Random Number Generators and Information Security

From Computing and Software Wiki

(Difference between revisions)
Jump to: navigation, search
 
(21 intermediate revisions not shown)
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>
-
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>
+
[[Image:Rng.png]]<sup>[5]</sup><BR>
-
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>
+
-
 
+
== Relevance to Information Security ==
== Relevance to Information Security ==
-
Random numbers, or pseudo-random numbers, are used in many aspects of computer science. This wiki page discusses the particular relevance of random numbers with cryptography.<BR>
+
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>
-
[[Image:crypt.JPG]]
+
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>
-
For example, the Needham-Schroeder Protocol depends on a good random number generator for truly unpredictable numbers, which are used to protect messages from attackers. A random number generator that gives predictable output would render the protocol entirely meaningless. 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>
-
[[Image:NSprotocol.JPG]]
+
== Vulnerability to attack ==
== 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>
+
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>
-
=== Examples of inadequate random number generators ===
+
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>
-
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 ===
+
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>
-
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 ==
-
=== True randomness ===
+
=== True randomness - Physical methods ===
-
==== 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>
-
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>
+
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>
-
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>
+
=== 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<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 ===
=== 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>
-
== Cryptographically secure pseudo-random number generators ==
+
<BR>Computational Methods:
-
A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography.<BR>
+
<UL><LI>Efficient: long sequences of numbers can be produced very quickly.
-
Many aspects of cryptography require random numbers, for example:<BR>
+
<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).
-
<ul>
+
<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>
-
<li>Key generation
+
-
<li>Nonces
+
-
<li>Salts in certain signature schemes, including ECDSA, RSASSA-PSS.  
+
-
<li>One-time pads
+
-
</ul>
+
-
The "quality" of the randomness required for these applications varies. For example creating a nonce in some protocols needs only uniqueness. On the other hand, generation of a master key requires a higher quality, such as more entropy. And in the case of one-time pads, the information-theoretic guarantee of perfect secrecy only holds if the key material is obtained from a true random source with high entropy.<BR>
+
-
Ideally, the generation of random numbers in CSPRNGs uses entropy obtained from a high quality source, which might be a hardware random number generator or perhaps unpredictable system processes — though unexpected correlations have been found in several such ostensibly independent processes. From an information theoretic point of view, the amount of randomness, the entropy that can be generated is equal to the entropy provided by the system. But sometimes, in practical situations, more random numbers are needed than there is entropy available. Also the processes to extract randomness from a running system are slow in actual practice. In such instances, a CSPRNG can sometimes be used. A CSPRNG can "stretch" the available entropy over more bits.<BR>
+
-
When all the entropy we have is available before algorithm execution begins, we really have a stream cipher. However some crypto system designs allow for the addition of entropy during execution, in which case it is not a stream cipher equivalent and cannot be used as one. Stream cipher and CSPRNG design is thus closely related. <ref>Wikipedia: Cryptographically secure pseudorandom number generator <http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator></ref>
+
-
=== Requirements ===
+
<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>
-
The requirements of an ordinary PRNG are also satisfied by a cryptographically secure PRNG, but the reverse is not true. CSPRNG requirements fall into two groups: first, that their statistical properties are good (passing statistical randomness tests); and secondly, that they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker.<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>
-
Every CSPRNG should satisfy the "next-bit test". The next-bit test is as follows: Given the first k bits of a random sequence, there is no polynomial-time algorithm that can predict the (k+1)th bit with probability of success higher than 50%. Andrew Yao proved in 1982 that a generator passing the next-bit test will pass all other polynomial-time statistical tests for randomness.<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.
-
Every CSPRNG should withstand 'state compromise extensions'. In the event that part or all of its state has been revealed (or guessed correctly), it should be impossible to reconstruct the stream of random numbers prior to the revelation. Additionally, if there is an entropy input while running, it should be infeasible to use knowledge of the input's state to predict future conditions of the CSPRNG state.<BR>
+
-
Example: If the CSPRNG under consideration produces output by computing bits of π in sequence, starting from some unknown point in the binary expansion, it may well satisfy the next-bit test and thus be statistically random, as π appears to be a random sequence. (This would be guaranteed if pi is a normal number, for example.) However, this algorithm is not cryptographically secure; an attacker who determines which bit of pi (ie the state of the algorithm) is currently in use will be able to calculate all preceding bits as well.
+
-
Most PRNGs are not suitable for use as CSPRNGs and will fail on both counts. First, while most PRNGs outputs appear random to assorted statistical tests, they do not resist determined reverse engineering. Specialized statistical tests may be found specially tuned to such a PRNG that shows the random numbers not to be truly random. Second, for most PRNGs, when their state has been revealed, all past random numbers can be retrodicted, allowing an attacker to read all past messages, as well as future ones. CSPRNGs are designed explicitly to resist this type of cryptanalysis. <ref>Wikipedia: Cryptographically secure pseudorandom number generator <http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator></ref>
+
== Conclusion ==
== 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.
 +
== See Also ==
== 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 ==
== External Links ==
 +
[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 ==
== References ==
-
<references />
 
1. Bishop, M. 2004. Introduction to Computer Security. Prentice Hall PTR.<BR>
1. Bishop, M. 2004. Introduction to Computer Security. Prentice Hall PTR.<BR>
-
2. Wikipedia. 2007. Retrieved November 27, 2007. <http://wikipedia.org><BR>
+
2. [http://en.wikipedia.org/wiki/Random_number_generation Wikipedia: Random Number Generation]. 2007. Retrieved November 27, 2007.<BR>
-
3. Haahr, M. 2007. Random.org. Retrieved November 27, 2007. <http://www.random.org><BR>
+
3. [http://en.wikipedia.org/wiki/Random_number_generator_attack Wikipedia: Random number generator attack]. 2007. Retrieved November 27, 2007.<BR>
 +
4. Haahr, M. 2007. Random.org. Retrieved November 27, 2007. [http://www.random.org Random.org]<BR>
 +
5. [http://casoilresource.lawr.ucdavis.edu/drupal/node/371 California Soil Resource Lab]. 2007. Retrieved November 27, 2007.<BR>
 +
6. [http://www.fourmilab.ch/hotbits/ HotBits]. 2007. Retrieved November 27, 2007.<BR>
 +
7. [http://en.wikipedia.org/wiki/Blum_Blum_Shub Wikipedia: Blum Blum Shub]. 2007. Retrieved November 27, 2007.<BR>
 +
8. [http://www.lavarnd.org Lavarnd]. 2007. Retrieved November 27, 2007.<BR>
 +
 
-
--[[User:Caoff|Caoff]] 18:30, 2 December 2007 (EST)
+
--[[User:Caoff|Caoff]] 11:58, 09 December 2007 (EST)

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]
Image:Rng.png[5]

Contents

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.
Image:NSprotocol.JPG[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: xn+1 = (xn)2 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.

See Also

Payment Card Industry Data Security Standard
The Mitnick attack
Anti-spam Systems and Techniques
Electronic Voting Systems
Biometrics in Information Security
Biometric Systems and Security Design Principles
Honeypot
Piggybacking
Security and Storage Mediums
Operating Systems Security
Autocomplete
Internet Cookies and Confidentiality
Identity Theft

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)

Retrieved from "http://wiki.cas.mcmaster.ca/index.php/Random_Number_Generators_and_Information_Security"
Personal tools