3.7.3 True randomness and pseudo-randomness

Modern algorithms such as Yarrow [99] or Fortuna (see chapter 10 of [65]) generate secret keys for use in cryptographic algorithms and protocols by accumulating entropy from several True Random Number Generators (TRNGs) and combining it using hash functions (see Chapter 11, Hash Functions and Message Authentication Codes) and block ciphers (see Chapter 14, Block Ciphers and Their Modes of Operation).

A TRNG generates random numbers based on the randomness of a physical process such as thermal noise, the photoelectric effect, or other quantum phenomena. Such processes are unpredictable in principle and therefore offer high entropy. For cryptographic purposes, unpredictability is the most important feature of a TRNG. Figure 3.4 illustrates the working principle of a TRNG.

Figure 3.4: Basic architecture of a TRNG. A physical process S is used as a source of randomness. The fluctuations in S are converted into raw bits using an analog-to-digital (A/D) converter. The raw bits are post-processed to ensure sufficient entropy, for instance, by taking several raw bits and XORing them into a single bit. The resulting bit sequence is subjected to a built-in test T that ensures that the TRNG works as specified. If T passes successfully, the TRNG outputs a random number n

A good TRNG example is the well-known online service random.org, which offers true random numbers on the internet. These numbers are generated from atmospheric noise captured by a radio and post-processed to ensure high entropy. Atmospheric noise is caused by natural atmospheric processes, for example, lightning discharges in thunderstorms [183].

Another illustrative example is provided by the wall of lava lamps in the lobby of the San Francisco office of the cloud service provider Cloudflare. A video feed of this wall is used to generate additional entropy that is made available to the production system [45]. Because the flow of a lava lamp is highly unpredictable, the luminance values of the pixels in the video feed can serve as entropy sources.

Unfortunately, as these examples show, the generation of truly random bits is an inefficient (and expensive) procedure in most practical environments. Fortunately, pseudo-random number generators can be used to mitigate the problem.

A Pseudo-Random Number Generator (PRNG), shown in Figure 3.5, is a deterministic algorithm that takes a comparably short sequence of truly random numbers or bits and outputs a much longer sequence of numbers or bits that appears to be random. Clearly, PRNG output is not really random. Ideally, however, an attacker cannot efficiently distinguish the output of a PRNG from a truly random sequence of the same length.

Figure 3.5: Basic architecture of a PRNG. The PRNG takes a comparably short seed s, i.e., a short sequence of truly random numbers or bits, and uses a deterministic algorithm A to produce a longer sequence of numbers n′

Apart from looking like a random sequence, for a Cryptographically Secure Pseudorandom Number Generator (CSPRNG), unpredictability is the most important feature, just like for TRNGs. In this context, unpredictability means that even if part of the output sequence becomes known, Eve still cannot predict the next number in the sequence.

3.8 Summary

In this chapter, we have introduced the most important cryptographic notions and concepts revolving around keys, including entropy and randomness. We have seen that we should use different keys for different purposes and that they should be regularly updated. We also learned that the length of a key should depend on the half-life of the information the key is supposed to protect.

In the next chapter, we will see how keys are used together with cryptographic algorithms to encrypt and decrypt secret messages. We will even see an example of a truly unbreakable cipher.