On the difficulty of generating random numbers

Random number generation

There are two different types of random number generators — pseudo-random number generators (PRNGs) and true random number generators (TRNGs). A PRNG is a deterministic algorithm that produces seemingly random numbers. It needs a seed as an initial value, and will produce the same “random” sequence for a fixed seed. Applications such as games, simulations, and cryptography use such generators. A TRNG is a device that generates truly random numbers. In contrast to a deterministic algorithm, a TRNG utilizes physical processes, such as thermal noise (utilized in the RPG100 circuit), quantum phenomena, and so on.

A PRNG is much faster than a TRNG, hence it is common to generate a seed using a TRNG to initialize a PRNG. After that, the PRNG generates the random numbers. In the Linux kernel /dev/random uses an entropy pool to generate random data. This may be used to generate cryptographic keys, or nonces used in different algorithms.

Randomness in practice

As stated earlier, random numbers are useful in cryptographic algorithms. Elements in cryptographic algorithms that usually must be random include nonces used in ciphers and protocols, secret keys, values in authentication protocols, and so on.

Assume we design an embedded system and implement a security feature for user authentication. The authentication mechanism requires nonces, which shall be a random number and we do not have a hardware TRNG available. How could we approach the problem? A naive solution could be to use the rand function in C, initialized with a seed, generated from throwing a couple of dice, as below.

#include <stdlib.h>

#define RANDOM_SEED 42

int main()
{
    srand(RANDOM_SEED);
    int r = rand();

    /* Create secret keys and stuff using rand */
}

This poses a major problem: every time a user reboots the system, rand produces the same sequence. One solution is to measure the thermal noise over a resistor, using the noise to generate randomness. Another is to utilize that some I/O pins are floating, hence the pins do not have a well defined voltage potential. The floating value may be sampled and used in the randomness generation.

One of the challenges in the Capture the Flag event co-organized by Debricked at Lund University included an example of this problem. The goal was to access a generic IoT device by providing a correct password. The device randomly generates a valid password each time a user tried to log in (resembling 2FA).

Attacks on randomness

There have been several attacks on security implementations. Here we highlight two famous events:

PlayStation 3 signature fail

The Sony PS3 uses the DSA algorithm to digitally sign software. To generate a signature, we calculate the tuple, (r, s), as follows

Where x is the private key, H is a hash function, and k is a random number. Consequently, Sony’s implementation led to k being fixed. Given two signatures for two different messages (m_A, m_B), we can calculate the secret key as,

The researchers calculated the private key of the PS3 to

46 DC EA D3 17 FE 45 D8 09 23 EB 97 E4 95 64 10 D4 CD B2 C2

NSA backdoored DRBG

In 2006, NIST standardized the Dual Elliptic Curve Deterministic Random Bit Generator, Dual_EC_DRBG, algorithm for generating random numbers. It was believed that the NSA backdoored the algorithm, in order to be able to decrypt TLS and SSH traffic across the web. The outcome of the Snowden leaks confirmed this in 2013. Subsequently, NIST removed the algorithm from the standard the following year.

What is randomness anyway?

Imagine flipping a coin. When the coin is in the air, we choose heads or tails hoping the outcome is in our favour. It should not matter what we choose, since the outcome is assumed to be random, right? If we can measure the initial state of the coin, we can predict the outcome of the toss, due to the coin obeying the laws of physics. We can then ask ourselves, if we can measure everything is anything really random? Scientists believe that true randomness exists due to quantum mechanics, but there is no proof.

A famous opponent to the Copenhagen interpretation of quantum mechanics, Albert Einstein, once said “God does not play dice“.