Testing random numbers

After a random number generator has been implemented, it is generally necessary to test the quality of the numbers it produces. Fundamentally, there should be a nearly equal number of ones and zeros in the generated random numbers. However, it is not enough to simply print out a few numbers and compare them. Random numbers can be mathematically tested using standard statistical procedures. It is self-evident that a large number of 8-bit random numbers will be needed for such testing. Between 10,000 and 100,000 random numbers should be generated and analyzed in order to arrive at reasonably reliable results. The only way to test this many numbers is to use computerized testing programs. When evaluating the quality of the random numbers, it is also necessary to investigate the distribution of the generated numbers. If this is very uneven, with certain values strongly favored, then exactly these regions can be used for purposes of prediction. This means that Bernoulli’s theorem should be satisfied as closely as possible. This theorem states that the occurrence of a particular number, independent of what has come before it, depends only on the probability of occurrence of the number itself. For example, the probability that a 4 appears when a die is thrown is always 1/6, independent of whatever number appeared on the previous throw. This is also referred to as ‘event independence’. The period of the random numbers, which is the number of random numbers generated before the series repeats itself, is also very important. It must naturally be as long as possible, and in any case longer than the lifetime of the random number generator. In this way, the possibility of attacking the system by recording all random numbers generated for a complete period can be excluded in a quite simple and reliable manner. There are many statistical tests for investigating the randomness of events, but in practice, we can limit ourselves to a few simple tests whose results are easily interpreted. There are also many publications on the subject of testing for randomness [Knuth 97, Menezes 97], as well as corresponding standards [FIPS 141-2, RFC 1750]. One test that is simple to set up and easy to interpret is to count the number of times that each byte value occurs in a large number of random numbers. If the results are displayed graphically as shown in Figure 4.44, they give a good indication of the distribution of the numbers.

If such a diagram is used to investigate 8-byte random numbers, the values plotted on the horizontal axis must still be single-byte or at most two-byte numbers, since the number of samples needed for a statistical analysis would otherwise become extremely large. A good guideline is that every random number should occur approximately four to 10 times for each value in order to obtain reasonably reliable results. In this way, it is possible to quickly see whether the random numbers that have been generated fully exploit the possible bandwidth of the byte. If certain values are strongly favored, this offers an attacker a possible starting point. Unfortunately, this test does not say anything about the order in which the random numbers occur, but only something about their distribution. For example, it would be possible for a ‘random number’ generator to output numbers cyclically from 0 to 255. This would yield an outstandingly uniform distribution, but the numbers would be completely predictable. Other tests must be used to assess this quality criterion for random numbers. Another practical test that yields a simple and quick estimate of the quality of a series of random numbers is to compress the series using a file-compression program. According to Shannon, the degree of compression that is possible is inversely related to the randomness of the set of generated numbers. A significantly more robust test is the very well-known χ2 test. Although it tests the same aspect as the previously described graphic test for even-statistical distribution, it is significantly more exact because it is performed using a mathematical procedure [Bronstein 96]. If the random numbers are assumed to be evenly distributed, the median value and standard deviation can be calculated. The deviation from a normal distribution can then be determined based on a χ2 distribution. From this, it is possible to state a numerical value for the distribution of the random numbers. However, this test cannot be used to draw any conclusions regarding the sequence in which the random numbers occur. Other statistical tests can be used to verify the randomness with which the numbers occur [Knuth 97], such as the Serial Test, which analyzes the periods of patterns that occur in the random numbers. Similarly, the Gap Test analyzes the intervals over which patterns do not occur. The Poker Test should also be used to evaluate the χ2 distribution of patterns that do occur, and the Coupon Collector Test should be used to evaluate the χ2 distribution of patterns that do not occur.

The Spectral Test, which investigates the relationship between each random number and the next following number, also has a certain amount of relevance [Knuth 97]. In the twodimensional version of this test, random numbers and their immediate successors are plotted in an X–Y coordinate system, as shown in Figure 4.45. The three-dimensional version requires the successor to the successor number in addition, as well as a third axis (the Z axis). Ndimensional spectral tests can be performed in a similar manner, but for understandable reasons, they must dispense with graphical representation. At a minimum, the above-mentioned tests must be performed and analyzed in order to achieve a reliable and definitive evaluation of a random number generator. Additional calculations and tests can be used to confirm the results so obtained. Only in this way is it possible to make a reasonably correct assessment of the quality of a set of random numbers. Of course, considering the areas in which random numbers are used in smart card applications, an overly sophisticated random number generator is usually not justified. For instance, the effect on security of being able to predict the random numbers used for authentication would be very slight, since no attack is possible without knowledge of the private key used to encrypt the random number. A more serious problem would, however, arise if it were possible to manipulate the random number generator, for example so that it would always generate the same sequence of random numbers. In this case, an attack based on replaying the numbers would be not only possible but also successful. This would also be true if the period of the random numbers were very short. In each individual case, the primary conditions that the random numbers must satisfy must be carefully considered, since this naturally affects the random number generator. Although a supreme effort here may lead to very high-quality random numbers, it also usually results in increased use of memory space, which is particularly limited in smart cards.