The chronicles of the kings of Norway has it that King Olaf Haraldsson the Saint disputed the possession of the Hísing island with his neighbour the King of Sweden. They decided to settle the dispute peacefully with a game of dice. After agreeing that the winner would be the one with the highest score, the King of Sweden threw the dice first.
–Twelve! I won! No need to throw the dice, King Olaf.
As he shook the dice in his hands, Olaf the Saint replied:
–There are still two sixes left in the dice and it will not be difficult for God, my Lord, to make them appear again on my behalf.
The dice flew and two sixes came out again. Once more, the king of Sweden rolled the dice and again he rolled two sixes. When it was Olaf the Saint’s turn, one of the dice rolled broke in two, one half showing a 6 and the other a 1, making a total of 13. As a result, the ownership of the island was awarded to Norway and both kings remained friends.
Randomness plays a fundamental role in all games of chance. And what might surprise you most: cryptography could not exist without randomness. In this article you will discover how randomness is used in cryptography and how to obtain random numbers, a task, as you will see, not easy at all.
What is Randomness?
There are so many definitions of randomness that we could fill a book with them. In cryptography the following interpretation is common, which I quote from Bruce Scheneier:
Randomness refers to the result of a probabilistic process that produces independent, evenly distributed and unpredictable values that cannot be reliably reproduced.
I would like to highlight the following three ingredients that every randomness generator must exhibit in order to be used with guarantee in “cryptographic salads”:
- Independence of values: there is no correlation between the values generated. For example, if you toss a coin (without trickery) into the air and it comes up heads nine times in a row, what is more likely, heads or tails on the tenth toss? Well, the probability is still 1/2, because the result of one toss is independent of the previous toss.
- Unpredictability: even if you get bored looking at values and more values, you can’t predict the next value with a higher probability than random, no matter how long the preceding sequence was. Again, coins, dice and roulettes are excellent random generators because, no matter how many theories you come up with, you won’t know what’s going to happen next (assuming they’re not loaded).
- Uniform distribution: I’m sure that while you were reading the chronicle of King Olaf the Saint you were thinking: “Impossible! How can two sixes go out four times in a row? And you are right to doubt, because the probability of this sequence is (1/36)-(1/36)-(1/36)-(1/36) = (1/36)4 = 0.00000059537… or 1 in 1.67 million. It is not likely that this sequence will occur, but it is possible. In fact, if you roll the dice a billion times it would appear about 600 times on average. Randomness as we imagine it manifests itself in large numbers, not in small numbers. The more values generated, the more we expect to see all possible sequences, distributed evenly, without any kind of bias.
The problem with randomness is that you’re never sure. Were the dice of the Nordic kings loaded? Did it happen, just by chance, that an improbable sequence happened that day? There is evidence of randomness that dictates with very high confidence whether or not a generator is random, but you can never be absolutely sure. In fact, there is a wide range of statistical test sets (NIST, Test01, Diehard, ENT, etc.) that try to rule out sequences that do not verify certain statistical properties, although they cannot guarantee perfect randomness.
How Are Random Numbers Generated?
Yes, but how do you generate random numbers on a computer? In order not to complicate things, let’s limit ourselves to two approaches:
- True Random Number Generator (TRNG): require a natural source of randomness. Designing a hardware device or software program to exploit this randomness and produce a number sequence free of bias and correlation is a difficult task. For example, thermal noise from a resistor is known to be a good source of randomness. TRNGs can also collect entropy in a running operating system through the use of connected sensors, E/S devices, network or disk activity, system registers, running processes, and user activities such as keystrokes and mouse movements. These system- and human-generated activities can function as a good source of entropy but can be fragile and manipulated by an attacker. In addition, they are slow to produce random numbers.
- Pseudo-random number generators (PRNG): unfortunately, most natural sources are not practical due to the inherent slowness of process sampling and the difficulty of ensuring that an opponent does not observe the process. Moreover, it would be impossible to reproduce, which would require two copies of the same sequence: one for Alice and one for Bob, which entails the almost insurmountable difficulty of getting them to both. Therefore, a method is required to generate randomness that can be implemented in software and that is easily reproducible, as many times as necessary. The answer lies in pseudo-random number generators: an efficient and deterministic mathematical algorithm to transform a short and uniform string of k length, called the seed, into a longer, uniform-looking (or pseudo-random) output string of l >> k length. In other words:
“A pseudo-randomness generator uses a small amount of true randomness to generate a large amount of pseudo-randomness”
What Is the Use of Randomness in Cryptography?
Randomness is difficult to generate and difficult to measure. Nevertheless, it is a key ingredient for the success of any cryptographic algorithm. Look at the different roles that randomness can play in making cryptography secure:
- Encryption keys: to encrypt a message you need an encryption key, both for secret key algorithms and public key algorithms. If this key is easy to guess, what a rip-off! A fundamental requirement for the secure use of any encryption algorithm is that the key is selected randomly (or as randomly as possible). In fact, one problem faced by ransomware is how to generate random keys to encrypt victims’ files. The best encryption algorithm in the world is worthless if the key is revealed. It is recommended to use a hardware device to generate them, such as the TPM on Windows systems or an HSM.
- Initialization Vectors: Block cipher algorithms use a random initial value, called the initialization vector (IV), to start the cipher of the first block and ensure that the same message encrypted with the same key will never yield the same value, as long as a different IV is used. This value can be known, but not predictable. Again, it is therefore critical to use random (and unpredictable) values to avoid repetition. And once again, it is recommended to use hardware devices to generate them.
- Nonces: a nonce is a number used once in a secure communication protocol. And what use can these fleeting nonces be? In a similar way to that explained with the initialisation vectors, nonces ensure that even if the same messages are transmitted during a communication, they will be encrypted in a completely different way, which avoids reproduction or reinjection attacks. In fact, nonces usually work as IVs: a nonce is generated and encrypted with the secret key to create the IV. They are also used in authentication protocols, such as in HTTPS, or for proof of work systems, such as in Bitcoin.
- Salts: salt is another random value commonly used when storing passwords in a database. As you may know, passwords should never be stored in clear: any attacker who accesses the user table would see the passwords! The password hash could be stored instead. But what if two passwords are the same? They will be given the same hash! If an attacker steals the database and sees many identical password hashes, bingo! He knows that they are easy passwords, the ones everyone chooses when they are not careful. On the other hand, you can pre-compute huge tables of known password hashes and search for those hashes in the stolen database. To avoid these problems, a random value is added: salt. From now on, the password hash will not be saved, but the salt and the password hash concatenated with the salt: H( password || salt). Therefore, two identical passwords will result in two different hashes as long as the salt is random. Likewise, attacks that pre-calculated hashes of known passwords are no longer useful. Like nonces, salts don’t have to be secret, but they do have to be random. Another typical application of salts is in key derivation functions from passwords (KDF). A very simple scheme consists of repeating n times the hash of a password and a salt:
key = Hn( password || salt )
- Filling: the famous RSA public key encryption algorithm is deterministic, i.e. the same message encrypted with the same key will always yield the same cipher text. That can’t be! It is necessary to randomise the message in clear. How? By adding random bits very carefully, in what is known as the OAEP scheme, which transforms traditional RSA into a probabilistic scheme. Similarly, to avoid the malleability of RSA encryption in digital signatures, the PSS scheme adds randomness.
- Blind signatures: to get a person to digitally sign a document, but without being able to see the content of the signed document, random values that “blind” the signer are also used, hiding the content of the message to be signed. Subsequently, once the random value is known, the value of the signature can be verified. This is the digital equivalent of signing a document by placing a tracing paper over it: it prevents the document to be signed from being seen, but perfectly transfers the signature to the document. And who would want to sign something without seeing it first? These blind signature protocols are used, for example, in electronic voting and digital money applications.
Without Randomness There Is No Security
Random numbers are of critical importance in cryptography: they are the very basis of security. Cryptography cannot be incorporated into products and services without random numbers. An inadequate random number generator can easily compromise the security of the entire system, as confirmed by the long list of vulnerabilities due to poor randomness. Therefore, the choice of the random generator must be taken carefully when designing any security solution. Without good randomness there is no security.
