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>

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>

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:crypt.JPG]] [[Image:NSprotocol.JPG]]^[1]

[[Image:NSprotocol.JPG]]^[1]

== Vulnerability to attack ==

== Vulnerability to attack ==

The RNG process is usually a single isolated component easy to locate, making it an attractive target for attackers. Once the RNG process is cracked, 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]]

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]]

=== Examples of inadequate random number generators ===

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]<BR><BR>

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

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

<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.^[3]</ul>

 

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

== Two kinds of randomness ==

== Two kinds of randomness ==

=== True randomness - Physical methods ===

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

 

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

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

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 ===

=== 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.<BR><BR>

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.<BR><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_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.^[8]

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 ===

=== Verdict ===

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.

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.