Applications of Randomness - Cryptography

Cryptography

A ubiquitous use of unpredictable random numbers is in cryptography which underlies most of the schemes which attempt to provide security in modern communications (e.g., confidentiality, authentication, electronic commerce, etc.).

For example, if a user wants to use an encryption algorithm, it is best that they select a random number as the key. These numbers must have high entropy for any attacker, thus increasing attack difficulty. With low entropy numbers used as keys (i.e., relatively easily guessable by attackers), security is likely to be compromised. For example, if a simple 32 bit linear congruential pseudo-random number generator of the type supplied with most programming languages is used as a source of keys, then there will only be some four billion possible values produced before the generator repeats itself. A suitably motivated adversary could simply test them all; this is practical as of 2010, using readily available computers. Even if a linear congruential RNG is used with 1000-bit parameters, it is a simple exercise in linear algebra to recover the modulus m, and the constants a and b, where x' = ax +b (mod m), given only five consecutive values. Even if a better random number generator is used, it might be insecure (i.e., its starting value, the seed) might be guessable, producing predictable keys and reducing security to nil. (A vulnerability of this sort was famously discovered in an early release of Netscape Navigator, forcing the authors to quickly find a source of "more random" random numbers). For these applications, truly random numbers are ideal, and very high quality pseudo-random numbers are necessary if truly random numbers are unavailable.

Truly random numbers are absolutely required to be assured of the theoretical security provided by the one-time pad — the only provably unbreakable encryption algorithm. Furthermore, those random sequences cannot be reused and must never become available to any attacker, which implies a continuously operable generator. See Venona for an example of what happens when these requirements are violated when using a one-time pad.

For cryptographic purposes, one normally assumes some upper limit on the work an adversary can do (usually this limit is astronomically sized). If one has a pseudo-random number generator whose output is "sufficiently difficult" to predict, one can generate true random numbers to use as the initial value (i.e., the seed), and then use the pseudo-random number generator to produce numbers for use in cryptographic applications. Such random number generators are called cryptographically secure pseudo-random number generators, and several have been implemented (for example, the /dev/urandom device available on most Unixes, the Yarrow and Fortuna designs, server, and AT&T Bell Laboratories "truerand"). As with all cryptographic software, there are subtle issues beyond those discussed here, so care is certainly indicated in actual practice. In any case, it is sometimes impossible to avoid the need for true (i.e., hardware) random number generators.

Since a requirement in cryptography is high entropy (i.e., unpredictability to an attacker), any published random sequence is a poor choice, as are such sequences as the digits in an irrational number such as the φ or even in transcendental numbers such as π, or e. All are available to an enterprising attacker. Put another way, in cryptography, random bit streams need to be not only random, but also secret and hence unpredictable. Public or third-party sources of random values, or random values computed from publicly observable phenomena (weather, sports game results, stock prices), are almost never cryptographically acceptable, though often tempting and too often used by the unwary. They permit easier attacks than attacking the cryptography.

Since most cryptographic applications require a few thousand bits at most, slow random number generators serve well—if they are actually random. This use of random generators is important; many informed observers believe every computer should have a way to generate true random numbers.

Read more about this topic:  Applications Of Randomness