RANDOM NUMBERS

Random numbers are repeatedly needed in connection with cryptographic procedures. In the field of smart cards, they are typically used to ensure the uniqueness of a session during authentication, as padding for data encryption and as initial values for send sequence counters. The length of the random number needed for these functions usually lies in the range of 2 to 8 bytes. The maximum length naturally comes from the block size of the DES algorithm. The security of all these procedures is based on random numbers that cannot be predicted or externally influenced. The ideal solution would be a hardware-based random number generator in the card’s microcontroller. However, this would have to be completely independent of external influences, such as temperature, supply voltage, radiation and so on, since otherwise it could be manipulated. That would make it possible to compromise certain procedures whose security relies on the randomness of the random numbers. Current random number generators in smart card microcontrollers are generally based on linear feedback shift registers (LFSRs) driven by voltage-controlled oscillators. Even with the current level of technological development, it is difficult to construct a random number generator immune to external influences (a ‘true random-number generator’, or TRNG) in silicon on a microcontroller die. Consequently, operating system designers frequently take recourse to software implementations. These yield pseudo-random number generators (PRNGs), most of which produce very good (that is, random) random numbers. Nevertheless, they do not generate truly random numbers, since the numbers are computed using strictly deterministic algorithms and thus can be predicted if the algorithm and its input values are known. This is why they are called ‘pseudo-random numbers’. It is also very important to ensure that the cards of a production batch generate different sequences of random numbers, so that the random numbers produced by one card cannot be inferred from those produced by another card from the same batch. This is achieved by entering a random number as the seed number (starting value) for the random number generator when the operating system is completed in each card.

Generating random numbers

There are many different ways to generate random numbers using software. However, since the memory capacity of smart cards is very limited and the time needed to perform the computation should be as short as possible, the number of options is severely restricted. In practice, essentially only methods that utilize functions already present in the operating system are used, since they require very little additional program code. Naturally, the quality of the random numbers must not be adversely affected if a session is interrupted by a reset or by removing the card from the terminal. In addition, the generator must be constructed such that the sequence of random numbers is not the same for every session. This may sound trivial, but it requires at least a write access to the EEPROMto store a new seed number for the next session. The RAM is not suitable for this purpose, since it needs power to retain its contents. One possible means of attack would be to repeatedly generate random numbers until the EEPROMcells holding the seed number fail. Theoretically, this would cause the same sequence of random numbers to then occur in every session, which would make them predictable and thus give the attacker an advantage. This type of attack can easily be averted by constructing the relevant part of the EEPROM as a ring buffer and blocking all further actions once a write error occurs. Another very important consideration for a software random number generator is to ensure that it never runs in an endless loop. This would result in a markedly shorter repeat cycle for the random numbers. It would then be easy to predict the numbers, and the system would be broken. Almost every smart card operating system includes an encryption algorithm for authentication. It is an obvious idea to use this as the basis for a random number generator. In this regard, it is important to realize that a good encryption algorithm mixes the plaintext as thoroughly as possible, so that the plaintext cannot be derived from the ciphertext without knowledge of the key. A principle known as the avalanche criterion says that, on average, changing one input bit should change half of the output bits. This property can be usefully exploited for generating random numbers. The exact structure of the generator depends on the specific implementation. Figure 4.42 illustrates a possible arrangement. This generator uses the DES algorithm with a block length of 8 bytes, with the output value being fed back to the input. Naturally, any other encryption algorithm could also be used. The generator works essentially as follows. The value of a ring buffer element is encrypted by DES using a key unique to the card. The ciphertext so produced is the 8-byte random number. This number, when XORed with the previous plaintext, provides the new entry for the EEPROMring buffer. The generator then moves to the following entry in the cyclic ring buffer. This relationship can be expressed mathematically as RNDn := f (key, RNDn–1).

When the smart cards are completed, a card-specific DES key is stored in each card, and at the same time random seed numbers are entered into the ring buffer, which for example could be a 12 × 8 buffer. The seed numbers ensure that each card produces a unique sequence of random numbers. A 12-stage ring buffer increases the life span of the generator by a factor of 12. Assuming that the EEPROM is guaranteed to have 100,000 write cycles, this generator can produce at least 1,200,000 8-byte random numbers. Erasing and writing eight bytes in the EEPROM takes about 14 ms (2 × 2 × 3.5 ms), and executing the DES algorithm takes about 17 ms at 3.5 MHz if it is implemented in software. The remaining processing time is negligible. The card thus needs around 31 ms to generate a random number. However, if the DES algorithm is computed in hardware (at a typical rate of 0.1 ms/block), a random number could be generated in only 14.4 ms using the described method. Figure 4.43 shows another example of a pseudo-random number generator. This generator is initialized every time the card is reset, which is the only time a write access to the EEPROM occurs. Only RAM accesses are used for the subsequent generation of random numbers, which makes this generator relatively fast.However, the disadvantage of this is that the generator uses a few bytes of RAM for the duration of the session. The statistical quality of this pseudo-random number generator is not very good, but it is adequate for normal smart card authentication procedures. The primary consideration with such procedures is to avoid generating random numbers with short repeat cycles, since that would allow authentication to be compromised by replaying messages from previous sessions. The FIPS 140-2 standard recommends that security modules check their built-in random number generators after every reset using statistical tests. Only after these tests have been successfully completed should the random number generator be released for further use. Current commonly used smart card operating systems rarely include such capability, since it is assumed that due to the deterministic nature of the pseudo-random number generator, the statistics of the generated random numbers will not change significantly. The number of proposals, standards and designs for pseudo-random number generators is simply overwhelming. Some well-known examples are the generators in the X9.17 standard, FIPS 186, the proposals in the Internet RFC 1750 and the arrangements shown by Bruce Schneier [Schneier 96], Peter Gutmann [Gutmann 98a] and Benjamin Jun [Jun 99]. The guiding principle for a random number generator should always be to keep it as simple and easily understandable as possible. Only then is it possible to assess its characteristics and thus determine its quality.