Schneier on Security

Roger • October 13, 2006 10:47 PM

@Robert:

it seems to me that I’d just use Excel and the randbetween() function if I needed a five-digit random number.

Robert, random numbers are a much bigger topic than that!

The problem which the RAND table was addressing is that computer “random number” functions actually return “pseudo-random numbers”, that is, they are generated by a mathematical formula which is intended to produce a series that “looks random” and has no obvious structure.

However there are several significant problems that can occur with these pseudorandom number generators, or PRNGs.

• Firstly, given the same “seed” or starting value, they always produce the same output sequence. This can usually be mitigated by using the system clock as the seed.
• Secondly, having a finite state, they are necessarily periodic, i.e. will eventually repeat. Many have a period on the order of 2^32, which is good enough for many purposes but not for large scale simulations or computer security. Cryptographic ones usually have a period of 2^64, 2^128, or even more. Some inferior ones have a period of the order of 2^15 which is really only good enough for games.
• Thirdly, while they may not have any “obvious” structure, the fact that they are generated from a formula means that they must have some type of structure. Often this will not correlate in any significant way with the simulation you are running but sometimes it will, and then seriously pathological results will arise. An infamous example of this is that one type of very popular PRNG, the linear congruential random number generator or LCRNG, tends to produce successive values which defines points on a small set of (n-1) hyperplanes in some n-dimensional space. If an LCRNG is used in a careless manner to simulate random positions in space or space time, it can produce totally spurious results. In other example, the FFT of many PRNG sequences show obvious “spectral lines”.

When we ask for random numbers there are at least six types of problems we commonly want to solve:

• in some security protocols, we often require a number that must be unpredictable even by a very smart opponent. In this case, the number must be generated with a significant amount of “truly random” entropy. The usual process is to combine every available source of difficult-to-guess (high entropy) data, using an entropy-preserving formula (i.e. one that makes the final number as difficult to guess as correctly guessing all of the input numbers). There also exist hardware RNG modules which generate “true” RNs directly from unpredictable physical processes, like thermal noise in a transistor.

• in other security protocols, we require a large number of random numbers, such that the opponent cannot guess the next one after having seen all the previous ones. The solution to this is a “cryptographically strong pseudorandom number generator” or CSPRNG. Finding any structure in a good CSPRNG sequence is as difficult as breaking an underlying cipher. However, CSPRNGs tend to be much slower than regular PRNGs. For more information see:
  http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

• in many applications, we only require that the numbers be “well distributed” across their range, and not repeat within the application domain. An LCRNG of adequate period is usually sufficient for this, which–along with simplicity and speed–is why they are so common in computer software.

• for statistics and simulations, we require that successive numbers do not correlate in any measureable way with parameters under test. It may also be desireable that the sequence can be easily reproduced by colleagues. This is the problem which the RAND tables were intended to address.

• in a very small number of security protocols, we don’t care about the opponent predicting the number, but we want to be able to prove to him that WE couldn’t predict it. The RAND tables have also been used for this purpose. Numbers generated in this way are called “nothing up my sleeve numbers”. An interesting article on this topic can be found at:
  http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

• finally, in large scale statistics and simulations, we need numbers without pathological correlations, but we need a really enormous number of them. CSPRNGs have been used for this purpose but provide additional unnecessary assurances and are often too slow. The state of the art in this area is the Mersenne twister, see:
  http://en.wikipedia.org/wiki/Mersenne_twister
  The Mersenne twister is not cryptographicaly secure but it has a huge period, very little correlation, and is pretty fast.

Prior to 2003 the rand() generator in Excel was a defective modification of an LCRNG and known to have a number of quite serious defects, and a period of only 2^24. A much improved version was shipped in Excel 2003 (although with a bug not fixed until Jan 2004). In this version, rand() is the mod 1.0 sum of three 15 bit LCRNGs scaled to [0,1), and is fairly good as such things go, good enough for most non-security purposes except large scale simulations. The period is just under 2^45.

I do not know the function behind randbetween() but one source states it was not updated in 2003 and is still based on the older, defective rand() function.

Roger • October 14, 2006 1:00 AM

@Rob:

Has anyone analysed the RAND corporation’s Random number list to determine it’s randomness?

Yes; in the book’s introduction, the results of some of RAND’s own validation tests are given, and so it was known to be less-than-perfect even when it was published. However the biases are too small to matter for most purposes.

I assume that it’s small size would not allow you to determine it’s period.

As it is generated from a hardware source of randomness which–under present understanding of quantum mechanics–is believed to be truly random, the sequence should be aperiodic.

What about their technique? Can it be faulted?

There are a couple of possible criticisms.

First, they are really vague about the “random frequency pulse source” which is the real heart of the machine. It is widely belived to have been a Geiger counter mounted near a radioactive source of suitable size (presumably somewhere on the order of 30 microcuries), but this doesn’t seem to have been actually recorded, and references to the machine’s statistical quality “running down” after “one month of continuous operation without adjustment” tends to suggest otherwise. It is possible that the pulse generator was actually some sort of astable oscillator. In that case, it may well have been chaotic rather than random, making analysis of the rest of the processing, and consequent quality of the output “randomness”, much more difficult. Additionally a chaotic oscillator might tend to end up synchronising with some accidental external driving field, which would make its output highly predictable.

A second point is that a 5 bit counter was driven from the pulse source and sampled once per second. In other words, each sample was the 5 least significant bits in the count of events in the last second. However a count of randomly distributed events over a set period is not uniformly distributed, it is a Poisson distribution. Reducing the count modulo 32 will largely correct this bias, but perhaps not entirely; the standard deviation in this case is about 320, only ten times the modulus, so once can easily see residual biases (on the order of a few percent) remaining.

Next, there is a curious anomaly in the process of converting 5 bit numbers to digits base 10. Basically the numbers are reduced modulo 10, but because 32 is not evenly divisible by 10, we have to discard some samples so as to avoid bias. To avoid bias only 2 values (e.g. 30 and 31) need to be discarded, however they actually discard 12. Since this would increase by 50% the duration of an operation which must have taken on the order of a fortnight, it must have been reasonably important; but so far as I know there has never been an explanation why. What was wrong with counts in the twenties?

Finally, to correct for biases that were detectable when the machine had “run down”, they summed pairs of digits modulo 10 (this is what is meant by “rerandomization of the basic table”). The reason was that this “transformation was expected to, and did, improve the distribution in view of a limit theorem to the effect that sums of random variables modulo 1 have the uniform distribution over the unit interval as their limiting distribution.”

This is correct so far as it goes but contains two hidden assumptions. Firstly, that theorem is only true if the two random variables are independent. That would seem like a reasonable assumption if they, say, generated two tables of a million digits each and then digitwise summed them. But what they actually did is produce one table of a million digits and then sum each digit with the one 50 places behind it (what they did with the first 50 isn’t mentioned, I presume they wrapped around). So if any correlations in the device were capable of lasting across 50 seconds, the procedure is not mathematically valid, even if the output “looks” more random. Worse, because this trick produces the same number of output digits as input, it follows that the entropy per digit in the output cannot be any higher than the input. Since the entropy per digit of a biased distribution is less than a uniform one, it follows that the output sequence is just as biased as the input, only in a more complicated way.

In practice they seem to be plenty good enough for most purposes.