6.1.3. Traditional Pseudo-random Sequences

This section talks about traditional sources of deterministic or "pseudo-random" numbers. These typically start with a "seed" quantity and use simple numeric or logical operations to produce a sequence of values. Note that none of the techniques discussed in this section is suitable for cryptographic use. They are presented for general information.

[KNUTH] has a classic exposition on pseudo-random numbers. Applications he mentions are simulations of natural phenomena, sampling, numerical analysis, testing computer programs, decision making, and games. None of these have the same characteristics as the sorts of security uses we are talking about. Only in the last two could there be an adversary trying to find the random quantity. However, in these cases, the adversary normally has only a single chance to use a guessed value. In guessing passwords or attempting to break an encryption scheme, the adversary normally has many, perhaps unlimited, chances at guessing the correct value. Sometimes the adversary can store the message to be broken and repeatedly attack it. Adversaries are also be assumed to be aided by a computer.

For testing the "randomness" of numbers, Knuth suggests a variety of measures, including statistical and spectral. These tests check things like autocorrelation between different parts of a "random" sequence or distribution of its values. But these tests could be met by a constant stored random sequence, such as the "random" sequence printed in the CRC Standard Mathematical Tables [CRC]. Despite meeting all the tests suggested by Knuth, that sequence is unsuitable for cryptographic us, as adversaries must be assumed to have copies of all commonly published "random" sequences and to be able to spot the source and predict future values.

A typical pseudo-random number generation technique is the linear congruence pseudo-random number generator. This technique uses modular arithmetic, where the value numbered N+1 is calculated from the value numbered N by

V    = ( V  * a + b )(Mod c)
 N+1      N

The above technique has a strong relationship to linear shift register pseudo-random number generators, which are well understood cryptographically [SHIFT*]. In such generators, bits are introduced at one end of a shift register as the Exclusive Or (binary sum without carry) of bits from selected fixed taps into the register. For example, consider the following:

  +----+     +----+     +----+                      +----+
  | B  | <-- | B  | <-- | B  | <--  . . . . . . <-- | B  | <-+
  |  0 |     |  1 |     |  2 |                      |  n |   |
  +----+     +----+     +----+                      +----+   |
    |                     |            |                     |
    |                     |            V                  +-----+
    |                     V            +----------------> |     |
    V                     +-----------------------------> | XOR |
    +---------------------------------------------------> |     |
                                                          +-----+

   V    = ( ( V  * 2 ) + B  XOR  B ... )(Mod 2^n)
    N+1         N         0       2

The quality of traditional pseudo-random number generator algorithms is measured by statistical tests on such sequences. Carefully-chosen values a, b, c, and initial V or carefully-chosen placement of the shift register tap in the above simple process can produce excellent statistics.

These sequences may be adequate in simulations (Monte Carlo experiments) as long as the sequence is orthogonal to the structure of the space being explored. Even there, subtle patterns may cause problems. However, such sequences are clearly bad for use in security applications. They are fully predictable if the initial state is known. Depending on the form of the pseudo-random number generator, the sequence may be determinable from observation of a short portion of the sequence [SCHNEIER, STERN]. For example, with the generators above, one can determine V(n+1) given knowledge of V(n). In fact, it has been shown that with these techniques, even if only one bit of the pseudo-random values are released, the seed can be determined from short sequences.

Not only have linear congruent generators been broken, but techniques are now known for breaking all polynomial congruent generators [KRAWCZYK].