Random numbers should not be generated
with a method chosen at random
- Donald Knuth
The Art of Computer Programming
Volume II: Seminumerical Algorithms
Random numbers are a primitive element not only to cryptographers, but Computer Scientist and Programmers in general. What is desired is a method which produces a pseudo random stream of numbers fast which are cryptographically secure. However, the goals are diametrically opposed - pseudo random sequences can be produced quickly, or can be produced strongly; but usually not quickly with properties which resist Cryptanalysis.
This article will examine the applications of Pseudo Random Number Generators. Topics covered will include:
There are seven downloads available with this article. The downloads are presented at the end of the article.
In his prolific work The Art of Computer Programming, Volume II: Seminumerical Algorithms, Donald Knuth identifies the following common situations in which one may require random numbers:
Simulation and sampling are self explanatory. Numerical Analysis uses random numbers to solve complicated problems. For example, a Predator/Prey model using differential equations. Four is equally obvious. Taking from Knuth on item five, Decision Making:
There are reports that many executives make their decisions by flipping a coin or by throwing darts, etc. It is also rumored that some college professors prepare their grades on such a basis. Sometimes it is important to make a completely "unbiased" decision. Randomness is also an essential part of optimal strategies in the theory of matrix games.
The human ear can distinguish between synthesized music (generated from a computer) versus that of an artist. The artist will have small deviations in rhythm which makes the music more pleasing. Additionally, a small bit of randomness makes computer generated graphics appear softer. Note the rigid structure below of the left image versus the softness of the right image. Below the right image was produced with a filter which added a small random amount noise. In Signal Processing, this is known as Anti-Aliasing.
|
|
|
No Random Noise |
Random Noise |
To further impress aesthetics upon the reader, Adobe Photoshop employs random numbers in many of its filters, including Blur, Distort, and Noise.
|
Adobe Photoshop Filters |
Finally, recreation would include shuffling cards or rolling dice.
Taking frm NIST, FIPS 140-2:
Random Number Generators fall into one of two classes: deterministic and nondeterministic. A deterministic RNG consists of an algorithm that produces a sequence of bits from an initial value called a seed. A nondeterministic RNG produces output that is dependent on some unpredictable physical source that is outside human control.
Note that layman generally refer to the nondeterministic generator as a 'true random number generator'.
There are two types of deterministic random number generartors from which a programmer may choose:
Pseudo Random Number Generators would include generators such as Linear Congruential Generators and Mersenne Twisters. They are generally good at quickly providing a uniformly distributed stream over the interval [0, 1). They offer little to no cryptographic security.
Cryptographically Secure Pseudo Random Number Generators have additional properties which make them suitable for use in Cryptography. Cryptographic uses would include:
A Nonce is a number or bit string used only once. It is a pseudo random number issued in an authentication protocol to ensure that old communications cannot be reused in replay attacks. To ensure that a nonce is used only once, it should be time-variant (including a suitably granular timestamp in its value), or generated with enough random bits to ensure a probabilistically insignificant chance of repeating a previously generated value.
The One Time Pad (invented circa 1917) is an encryption algorithm where the plaintext is combined with a random key or "pad" that is as long as the plaintext and used only once. A modular addition is used to combine the plaintext with the pad. For binary data, the operation XOR amounts is the equivalent. If the key is truly random, never reused, and kept secret, the one time pad provides perfect secrecy.
Though NIST does not currently recognize any nondeterministic RNGs, one may use a deterministic RNG to seed a cryptographically secure pseudo random number generator. Taking from FIPS 140-2:
Until such time as an Approved nondeterministic RNG standard exists, nondeterministic RNGs approved for use in classified applications may be used for key generation or to seed Approved deterministic RNGs used in key generation
NIST provides tests which allows one to develop heuristics for determining the of the quality of the sequence from the generator inquestion. Included for download are NIST Validation Suite, FIPS 140-2, and and FIPS 186. Additionally, the reader may want to examine ANSI 9.17, Appendix C (Approved Random Number Generators for FIPS 140-2, Security Requirements for Cryptographic Modules).
Also of interset is NIST SP800-90, Recommendation for Random Number Generation Using Deterministic Random Bit Generators. Some conservative cryptographers do not recommend using Dual_EC-DRBG (the elliptic curve variant) but does recommend using CTR_DRBG or Hash_DRBG. Schneier's article can be found at Did NSA Put a Secret Backdoor in New Encryption Standard?
In a random sequence, on would expect each of the ten decimal digits to occur approximately 1/10 times. Should the radix be 2 (digits of either 0 or 1), each digit should represent approximately 50% of the sequence.
Testing involves differentiating good sources from poor choices. For example, the binary stream ...1111111110000000000... would perform ideally with a simple Frequency test, but fail at advanced tests such as Runs, Longest Runs in a Block, and Cumulative Sums. A counter intuitive point with the presented binary stream is that it is a valid sequence of random numbers. Each stream is as equally likely to occur as any other in an unbiased generator.
Below the reader will find various tests which should be used when evaluating the effectiveness of a generator. The reader should refer to NIST's Guide to the Statistical Tests and Knuth's The Art of Computer Programming for a complete description.
In addition, NIST's SP800-22, A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications should be consulted. NIST's site includes software for testing the generator.
NIST requires a PRNG pass 16 statistical tests. The tests are listed below with a brief description.
Knuth sates a random sequence should pass 13 statistical tests. Tests which are not included in NIST's requirements are listed below.
Cryptographically Secure RNGs share an Achilles' heel with the other pseudo random number generators - both require an starting seed as an input. Should the secret seed become compromised, an adversary can generate the entire output sequence instantly by using the same algorithm.
In 1995 David Wagner, then a graduate student at Berkeley, and fellow student Ian Goldberg cracked the random number generator used by the Netscape web browser to secure online transactions. The pair determined that Netscape was constructing its seeds using easily predicted numbers, such as the time of day.
Key derivation functions are used (among others) to derive keys from secret passwords or passphrases. For guidance one can use RFC 2898, Password-Based Cryptography Specification. In addition, the .NET platform provides Rfc2898DeriveBytes, which is part of System.Security.Cryptography.
Key derivation functions are often used in conjunction with non-secret parameters to derive a keys from a common secret value. A KDF may also be used to ensure that derived keys have other desirable properties, such as avoiding weak keys in some specific encryption systems.
Key derivation functions are also used in applications to derive keys from secret passwords or passphrases, which typically do not have the desired properties to be used directly as cryptographic keys. In such applications, it is generally recommended that the key derivation function be made deliberately slow so as to frustrate brute force attack or dictionary attack on the password or passphrase input value.
Such use may be expressed as Dk = KDF(Key, Salt, Iterations) where Dk is the derived key, KDF is the key derivation function, Key is the original key or password, Salt is a random number which acts as cryptographic salt, and Iterations refers to the number of iterations of a sub-function. The derived key is used instead of the original key or password as the key to the system. The values of the salt and the number of iterations (if it isn't fixed) are stored with the hashed password or sent as plaintext with an encrypted message.
The Standard C++ rand() function uses a linear congruential generator. It offers a uniformly distributed bit stream quickly when the parameters m, a, c, and X0 are appropriately chosen. The LCG offers no Cryptographic Security.
X0 is colloquially referred to as the seed, often using the system time. The generator obtains numbers by using the following recurrence relation:
Xn+1 = (aXn + c) mod m
The values chosen for the generator in Microsoft's Visual C++ environment
are shown below. Note that the & 0x7FFF is performing the
modular reduction.
return (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
Joan Boyar's PhD dissertation, Inferring Sequences Produced by a Linear Congruential Generator Missing low-order Bits is an interesting read. The astute reader should realize there probably exists an online gaming site using an insecure system. Note that this is a different attack than Wonging (named after Stanford Wong, a former IBM researcher and professional gambler), which is basically a card counting system.
First proposed by Miller, Lewis, and Goldman in 1969, this generator is is a linear congruential generator with c=0. The refinement of dropping the constant resulted in a Multiplcative Generator:
Xn+1 = aXn mod m
Park and Miller suggest the values of a = 75 = 16807, m = 231-1 = 2147483647. 231-1 produces a period of 231-2. Other valuse of a exist when using 231-1: 48271 and 69627. No other values should be used.
There are many fast random number generators available for use as a replacement to the standard C/C++ library's rand() and srand() funtions. The reader should familiarize themselves with Random Number Generators: Good Ones Are Hard To Find. Steve Park provides the source code to the Lehmer generator at his Random Number Generator webpage. Park's code provides additional PRNGs based on the following distributions (these generators are referred to as Non Linear Congruential Generators):
A Mersenne Twister, developed in 1997 by Makoto Matsumoto and Takuji Nishimura would also fall under this category. An interesting factiod in the world of computer viruses is that 30 viruses use the generator. It is speculated one author is responsible for these viruses.
CryptGenRandom() generates a requested number of bytes for
the user. GenCryptRandom() is an excellent source of entropy on
Windows since it is available for all Operating Systems except NT 3.51 and
earlier, and Windows 95 (SR1) and earlier.
The latest seed value for CryptGenRandom is stored in the
Windows Registry under the key \SOFTWARE\Microsoft\Cryptography\RNG\Seed of
the HKEY_LOCAL_MACHINE hive. The seed is developed by the Operating Systems
using various system parameters. For example, on a Windows CE device, the
following will be used:
CeGetRandomSeed) GetCurrentProcessId) GetCurrentThreadId) GetTickCount) GetLocalTime) GlobalMemoryStatus) GetStoreInformation) After the seed is developed, it undergoes two cryptographic transforms: an MD4 hash and a RC4 encryption for additional mixing and chopping.
Sample 1 demonstrates using the Windows API to acquire pseudo random
values. To remove the burden of an SDK, the program uses
LoadLibrary() and GetProcAddress().
Please see the
related article, Compiling and Integrating
Crypto++ into the Microsoft Visual C++ Environment. This article is based
upon basic assumptions presented in the previously mentioned article. It also
addresses most problems encountered with projects from Command Line to MFC
(Errors C1083, C1189, LNK1104, LNK2001, and LNK2005). Additionally, it
provides some tips and other niceties for using the Crypto++ Library.
LC_RNG is a Linear Congruential RNG. Though this generator
has no cryptographic value, it does allow one to reproduce results when
debugging a program. Additionally, it is generally faster at generating a
byte block (or stream). If one seeds the LCG with 0x00, a steady stream of
0x80 is the result. This seed value produces a period of 1. Other seeds
perform as desired. Sample 1 may be used to compare the results of various
seed values of Linear Congruential Generators.
The RandomPool behaves similar to an LCG in that the same
seed produces the same results. However, unlike LC_RNG, the
cipher behind the RandomPool is currently
MD5<SHA>. randpoool.cpp provides typedef
MDC<SHA> RandomPoolCipher. Then RandomPool would be
initialized and used as follows (as demonstrated in Sample 3):
// Must be at least 16 for RandomPool const unsigned int SEEDSIZE = 16; byte pcbSeed[ SEEDSIZE ]; // Scratch Area const unsigned int BLOCKSIZE = 16 * 8; byte pcbScratch[ BLOCKSIZE ]; ... // Random Pool Initialization CryptoPP::RandomPool rng( SEEDSIZE ); rng.Put( pcbSeed, SEEDSIZE ); // Use rng.GenerateBlock( pcbScratch, BLOCKSIZE );
An auto seeded random pool was suggested by Leonard Janke, which Wei Dai
later incorporated into Crypto++. AutoSeededRandomPool uses the
RandPool design from PGP. It is suitable for all cryptographic
purposes including generating keys and IVs. Depending on the Operating
System, the generator will be seeded using the following:
CryptGenRandom() by way of a Cryptographic Service
Provider /dev/urand /dev/rand Sample 4 trivially demonstrates using an AutoSeedeRandomPool.
// Scratch Area const unsigned int BLOCKSIZE = 16 * 8; byte pcbScratch[ BLOCKSIZE ]; // Construction AutoSeededRandomPool rng; // Random Block rng.GenerateBlock( pcbScratch, BLOCKSIZE );
Unlike LG_RNG and RandomPool,
AutoSeededX917RNG does not require seeding. However, one must
specify an approved Block Cipher as a template parameter. The two ANSI 9.17
approved ciphers are 3-key Triple DES and SHA1. Sample 5 demonstrates use
with SHA1.
// Scratch Area const unsigned int BLOCKSIZE = 16 * 8; byte pcbScratch[ BLOCKSIZE ]; // Construction AutoSeededX917RNG< DES_EDE3 > rng; // Random Block rng.GenerateBlock( pcbScratch, BLOCKSIZE );
The following table should be applied when chosing a Random Number Generator in practice.
In addition to the previously mentioned, various FIPS standards recognizes other cryptographically secure generators. As the reader should now realize, a Cryptographically Secure Pseudo Random Number Generator wraps a deterministic generator in a difficult problem. FIPS 186-3 approves the Digital Signature Algorithm (DSA) and Elliptic Curve DSA (ECDSA) as CSPRNGs.
This section is included for pandectic resaons. I hope the reader will appreciate (and sometimes enjoy) the shortcomings.
The Middle Square Method of generation was proposed by John von Nuemann. The generator was used from 1946 to the mid 1950s. Keep in mind that in 1946, the computer was 1 year old. The generator suffered from the fact it converged to a sequence of 0s too quickly; and once at 0, it was latched at 0.
RANDU was a congruential generator supplied by IBM for use on it's mainfame computers. The choice of a=65539 and m=231 proved to be a poor choice. When the authors of Numerical Recipies in C generated a sample and plotted the planes, only 11 planes existed (where there should have been on the order of m1/k, where k is the number of random numbers chosen plotted in three dimensional space. The generator suffered from Correlation in k-space. The IBM representative stated:
We guarantee that each number is random individually, but we don't guarantee that more than one of them is random.
In 1992, physicists discovered that even "high-quality" random-number generators, can yield incorrect results under certain circumstances. In preparation for simulating the three-dimensional Ising model, researchers tested the package on the two-dimensional version, which has a known answer. The result was incorrect. [1]
This article presented the reader with with various choices for a pseudo
random number generator based on the problem domain. Should the reader
require a source for Simulation or Sampling, choose an LCG. If the reader
requires strength, choose the Win32 API, AutoSeededRandomPool, or
AutoSeededX917RNG. If the reader requires Cryptographic Security, choose an
AutoSeededX917. And finally, if the reader requires entropy, use
Win32 API or AutoSeededRandomPool.
In addition, other generators exist (some of which are exposed in Crypto++). For example, the Blum Blum Shub CSPRNG produces a bit sequence based on Quadratic Residues. The generator will remain cryptographically secure as long as Integer Factorization remains hard. It has yet to be determined where Integer Factorization lies in Complexity Theory.
[1] The Bias of Random-Number Generators, http://www.sciencenews.org/articles/20030927/mathtrek.as, accessed November 2007.
| You must Sign In to use this message board. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
