Random Number Generator

From OSDev Wiki
Jump to navigation Jump to search

Random number generators (RNG) can be implemented in lots of different ways. This article explains some of them.


Entropy

Computers are deterministic devices. If the program is the same and all inputs are the same, the same result will be calculated every time. How, then, can a computer generate random numbers? The computer cannot, but the physical world around it can. Many physical events are random to some degree, or more technically, have some degree of entropy. A sound recording will contain some level of noise even in the best shielded recording rooms on the planet. Humans type on keyboards with an inconsistent timing, and type quasi-random text like the article you are currently reading. Even other computers can provide entropy: while most network traffic is entirely machine generated, the exact relative timing of network packets in the end derives from the moment the power button was pressed, another human action. Therefore the timing and nature of input events can provide us with some entropy.

Types of random number generators

There are multiple ways to divide random number generators; one way is by how the numbers are generated, another is by how they can be used. These are important distinctions: the former may impact how you design your OS, and the latter can make or break the security of your system.

Sources of random numbers

There are two kinds of random numbers: "true" random and pseudo-random.

For "true" random number generation, the system continuously measures a certain set of events that are expected to be random. This can be anything from cosmic radiation and atomic decay, to the timing of user input and clock jitter. Measurements are de-biased and "stirred" into a pool of entropy, from which random numbers can be extracted.

Pseudo-random numbers are generated by an algorithm (a PRNG) that transforms some internal state and calculates an output value upon request. The initial seed can be set, but after that the next state only depends on the previous state. There are many different PRNGs out there, some of which are discussed below.

It is possible to use some "true" random numbers to seed the state of a pseudo-random generator, but this does not make the PRNG "truly random". Depending on the exact algorithm, it may be trivial to predict all next outputs given as few as one previous output. This can have serious implications, as discussed in the next section.

Applications of random numbers

There are roughly two kinds of applications: cryptography, and everything else.

In order to understand the following section, we first should review what cryptographic security means with respect to random number generators. Cryptographers distinguish two types of security: information-theoretic security and computational security. The former of these is the stronger claim. If a cryptosystem is information-theoretically secure, an attacker cannot say anything about an encrypted message without owning the key. Such cryptosystems are rare. Since the attacker must not be able to say anything, everything including patterns, timing and even the length must be hidden. How can one even hide the length of a message? The only choices are to not send the message at all, which defeats the purpose of a cryptosystem, or to send an infinitely long message. So once you start sending, you can never stop.

This is why computational security is the weaker, but more practical kind: the ciphertext must be difficult to find, given some reasonable computing power. This limit is chosen with the expectation that it will not be reached in the coming decades. This also allows the user to "leak" some information about the ciphertext (the length, for example), as long finding the original input remains difficult. These systems usually use some operation that is difficult to invert unless the key is known, such as factoring very large primes. It should be obvious that the key must not be predictable: if an adversary knows what the next outputs will be, it will be very easy for them to guess keys until the correct one is found.

"True" random numbers are the best source for cryptographically-secure randomness, however it is difficult to build a large, quickly-replenished pool of entropy where each source is perfectly de-biased and cannot be influenced by the other sources. To "stretch" the entropy in a way that is difficult to reverse, one can use a cryptographically-secure random number generator (CSPRNG). CSPRNGs guarantee that it is computationally difficult to guess the next output having seen previous results, and, if the generator's state is known, which values preceded the known outputs.

True random number generators

True random number generators use physical devices or phenomena to generate random numbers, whose unpredictability can be traced to the laws of quantum mechanics.

x86 RDSEED Instruction

Newer x86 and x86-64 processors have the instruction RDSEED for generating random numbers. To use RDSEED you will first need to check if the instruction is available. 

mov eax, 7     ; set EAX to request function 7
mov ecx, 0     ; set ECX to request subfunction 0
cpuid
shr ebx, 18    ; the result we want is in EBX...
and ebx, 1     ; ...test for the flag of interest...

If EBX is set to 1 (or ZF is unset), the instruction is available. Then it can be used to generate a 16/32/64 bit random number (depending on the register size used as an argument). If a random number was generated, the Carry flag is set. 

mov ecx, 100   ; number of retries
.retry:
    rdseed eax
    jc .done      ; carry flag is set on success
    loop .retry
.fail:
    ; no random number available
.done:
    ; random number is in EAX

It is up to you and your users to trust RDSEED. Because it is implemented in hardware, it effectively is a black box that may contain all sorts of bugs, or worse, backdoors.

Dedicated hardware

There exist devices dedicated to generating "true" random numbers. These range from the consumer-level TPMs, to PCIe "crypto accelerators". These are a generalization of RDSEED/RDRAND, with the downside that you need additional drivers to interface with the device and that the users may not have such a device installed.

TPMs, or Trusted Platform Modules, are small co-processors that can be installed on modern motherboards. In addition to random number generation, they also provide other trusted computing services. Notably, Windows 11 requires the presence of a TPM. They can also be emulated on the CPU (e.g., Intel PTT or AMD fTPM). As with RDSEED, backdooring may be a concern.

Sampling manually

There are plenty of processes happening with in a running system that are effectively random. Think about all the different interrupts that arrive every second: timers with accuracies of multiple parts-per-million, peripheral I/O, the user interacting with the entire system, and more.

The challenge is finding sources that are (paradoxically) reliably random and difficult to influence and observe from outside. For each of these sources, an estimate must be made of how much entropy they contribute. Measurements add their respective amount of entropy to the pool, while reads decrease the entropy.

Because you have full control of this generation method, you can also incorporate the values generated by hardware generators. You can yourself decide how much entropy you count for these generations, even 0 bits.

When using timing as entropy source, the timestamp read should be as precise as possible. The TSC works well for this. Gauging the entropy gained from that operation requires knowledge of the timing window for the event to occur in and the tick rate of the TSC. For example, if a TSC has a tick rate of 3 GHz and an event has a 10ms window to occur, then the TSC read can have any one of 30 million values, which means the entropy gained from this is ca. 24.8 bits. Were the TSC slower, only 1 GHz, then the entropy would only be ca. 23.2 bits.

Adversarial entropy

If an adversary can somehow observe the state of the entropy pool and contribute their own entropy into the pool, then it is possible that they would provide entropy in such a way as to force the entropy pool into a lower entropy state. A simple example would be an entropy source periodically checking if a certain bit in the pool is set, and then providing entropy until it is clear. This way, for most of the time, that given bit is clear, and the number of possible states the entropy buffer can be in is halved. A more sophisticated attack is described on DJB's blog: https://blog.cr.yp.to/20140205-entropy.html

It is also partly for this reason that it is unwise to expose the entropy pool unmodified if the user requests a random number. If an adversary has access to the pool (either via a dedicated "add-entropy" interface or a sampled event source), it will be very easy to poison it. A common method used to hide the exact state is to hash (parts of) the pool in combination with counter, for instance the entropy counter, and a salt, using a cryptographically secure hashing function like SHA-256. Because these hash algorithms are difficult to invert, its inputs cannot be easily guessed. It is important to do this only if the pool has some entropy left.

Cryptographically secure pseudorandom number generators

Now follow some CSPRNGs. It is important to remember that, as with everything cryptographic, it is best not to homebrew it if you are planning on actually using it. There are many ways things can go wrong, and the more complex the algorithm, the more chances of you making a mistake. Of course, for hobby uses it's perfectly fine; just don't go online banking with your handmade TLS key source.

x86 RDRAND Instruction

RDRAND is slightly older than RDSEED, and provides (what Intel claims to be) a CSPRNG. Its presence is indicated by CPUID leaf 1, ECX bit 30: 

mov eax, 1     ; set EAX to request function 1
mov ecx, 0     ; set ECX to request subfunction 0
cpuid
shr ecx, 30    ; the result we want is in ECX...
and ecx, 1     ; ...test for the flag of interest...

If ECX is set to 1 (or ZF is unset), the instruction is available. Usage is identical to RDSEED: 

mov ecx, 100   ; number of retries
.retry:
    rdrand eax
    jc .done      ; carry flag is set on success
    loop .retry
.fail:
    ; no random number available
.done:
    ; random number is in EAX

It is automatically seeded by the same entropy source that RDSEED reads from, and cannot be seeded manually. It therefore is subject to the same caveats as RDSEED.

Ciphers

It is fairly common to construct a CSPRNG by seeding a secure cipher, such as ChaCha20 and AES, and running many cycles where the output gets re-encrypted together with a running counter. Every once in a while, a new key is created, potentially involving another secure random source.

Writing (and backdooring) a ChaCha20 based CSPRNG may be an interesting article on the subject, and how it can go wrong in surprising ways.

Pseudorandom number generators

Next are various regular PRNGs. These vary in all dimensions of quality, simplicity and speed. Carefully read each explanation!

The Standard's Example

Taken directly from the C standard document (p. 347): 

// The following functions define a portable implementation of rand and srand.

static unsigned long int next = 1;  // NB: "unsigned long int" is assumed to be 32 bits wide

int rand(void)  // RAND_MAX assumed to be 32767
{
    next = next * 1103515245 + 12345;
    return (unsigned int) (next / 65536) % 32768;
}

void srand(unsigned int seed)
{
    next = seed;
}

This is a fairly standard but mediocre Linear Congruential Generator (LCG). It returns 15 random bits.

It is based on this recurrence formula 

 Xn+1 = (aXn + c) mod m

where the modulus m is the maximum number of random values the LCG can produce. For the example in the C standard, a = 1103515245, c = 12345 and m = 232 (implicitly). The quality of the LCG depends heavily on these values and finding good values is difficult. Wikipedia has a list of common parameters.

Fibonacci random number

A special "remake" of the Fibonacci sequence can be used to generate random numbers. This is done by having 4 "seeds", which start off as really weird values (e.g. 45, 80, 22, 32). The seed() function adds a new seed to the end of the sequence, and erases the first one (the seeds are referred to as A, B, C and D). The rand() function just returns the sum of the seeds, and calls seed() with the result. Glidix is a good example of this RNG implementation.

Linear Feedback Shift Register

A Linear Feedback Shift Register (LFSR) is a simple way to generate a very long sequence of random numbers, given a non-zero seed. The idea is as follows: an n-bit LFSR has n bits (either 0 or 1). Initially, the register is filled with an n-bit seed. For each next value to be generated, "tap" certain bits from the register and XOR them together. Feed the resulting binary value into the left-most bit, shifting all bits one position to the right. The bit that is shifted out of the LFSR on the right-most side is the generated random bit.

The sequence of bits that an LFSR can produce will eventually repeat, but by choosing the XOR'ed bits carefully the period of the LFSR can be increased to up to 2n - 1 bits. This means that after a sequence of 2n - 1 bits, the same sequence will be returned. However, this is a property that all pseudo-random number generators have: without changing the seed, they will eventually repeat themselves.

The following is an example of an 16-bit LFSR using bits 11, 13, 14 and 16 XOR'ed together as its input. The period of this LFSR is 65535 bits, so it will generate a pseudo-random sequence of 65535 bits before the sequence repeats itself. The next bit produced by the LFSR is 1 (the value of bit 16) and the next input bit is 0. 

            1                                       11      13  14      16
          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
INPUT --> | 0   1   0   0   0   1   0   0   1   1   1   1   0   0   0   1 | --> OUTPUT
          +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+

INPUT = bit 11 XOR bit 13 XOR bit 14 XOR bit 16

Larger (and smaller) LFSR's are also possible. Smart people have derived polynomials that will ensure that given any non-zero input, the period of the LFSR is as large as it can be (2n - 1). Such a polynomial is written as x16 + x14 + x13 + x11 + 1. For this example polynomial for n = 16, bits 16, 14, 13 and 11 must be XOR'ed together and provided as input, counting from the left and starting with 1. Polynomials for other values of n can be found here on Wikipedia and on page 5 of this PDF document.

Note that the seed must never be zero. This also means that it is never possible for all registers to have bit value zero, and that of the 2n possible combinations of registers, the all-zero state is not allowed. Therefore, 2n - 1 states is the maximum possible.

Wichmann-Hill

In 1982, Brian Wichmann and David Hill proposed to combine three linear congruential generators, then normalizing and summing the results to get a number uniformly distributed between 0 and 1. A common instance is: 

static uint16_t seed[3]; /* seed with numbers between 1 and 30000 */
float wichmann_hill(void) {
  seed[0] = (171 * seed[0]) % 30269;
  seed[1] = (172 * seed[1]) % 30307;
  seed[2] = (170 * seed[2]) % 30323;
  return fmod(seed[0] / 30269.0 + seed[1] / 30307.0 + seed[2] / 30323.0, 1.0);
}

This version is known to have a period of just shy of of seven trillion (the least common multiple of 30268, 30306, and 30322).

Mersenne Twister

The Mersenne Twister is an incredibly popular PRNG and is available on most platforms; for example, it is part of the set of generators required by the C++11 standard library. An implementation of the 64-bit MT-19937 version in C is as follows:

Implementation according to Wikipedia: 

#include <stddef.h>
#include <stdint.h>
#include <assert.h>

#ifdef USE32
typedef uint32_t word_t;
#define STATE_SIZE  624
#define MIDDLE      397
#define INIT_SHIFT  30
#define INIT_FACT   1812433253
#define TWIST_MASK  0x9908b0df
#define SHIFT1      11
#define MASK1       0xffffffff
#define SHIFT2      7
#define MASK2       0x9d2c5680
#define SHIFT3      15
#define MASK3       0xefc60000
#define SHIFT4      18
#else
typedef uint64_t word_t;
#define STATE_SIZE  312
#define MIDDLE      156
#define INIT_SHIFT  62
#define TWIST_MASK  0xb5026f5aa96619e9
#define INIT_FACT   6364136223846793005
#define SHIFT1      29
#define MASK1       0x5555555555555555
#define SHIFT2      17
#define MASK2       0x71d67fffeda60000
#define SHIFT3      37
#define MASK3       0xfff7eee000000000
#define SHIFT4      43
#endif

#define LOWER_MASK  0x7fffffff
#define UPPER_MASK  (~(word_t)LOWER_MASK)
static word_t state[STATE_SIZE];
static size_t index = STATE_SIZE + 1;

static void seed(word_t s)
{
    index = STATE_SIZE;
    state[0] = s;
    for (size_t i = 1; i < STATE_SIZE; i++)
        state[i] = (INIT_FACT * (state[i - 1] ^ (state[i - 1] >> INIT_SHIFT))) + i;
}

static void twist(void)
{
    for (size_t i = 0; i < STATE_SIZE; i++)
    {
        word_t x = (state[i] & UPPER_MASK) | (state[(i + 1) % STATE_SIZE] & LOWER_MASK);
        x = (x >> 1) ^ (x & 1? TWIST_MASK : 0);
        state[i] = state[(i + MIDDLE) % STATE_SIZE] ^ x;
    }
    index = 0;
}

static word_t mt_random(void)
{
    if (index >= STATE_SIZE)
    {
        assert(index == STATE_SIZE || !"Generator never seeded");
        twist();
    }

    word_t y = state[index];
    y ^= (y >> SHIFT1) & MASK1;
    y ^= (y << SHIFT2) & MASK2;
    y ^= (y << SHIFT3) & MASK3;
    y ^= y >> SHIFT4;

    index++;
    return y;
}

Some implementations automatically seed the generator with seed 5489, but this will (obviously) lead to the same outputs at every initialization.


It outperforms all PRNGs listed above, but it is rather slow due to its large state size. It also has problems in some statistical areas. See "It is high time we let go of the Mersenne Twister".

PCG family

The PCG family is a relatively recent addition to the field of PRNGs. The simplest version uses an LCG with a permutation operator to scramble the output. It was built to pass as many statistical tests as it could, while still staying small and fast. There is a comprehensive paper describing the generators and Apache 2.0-licensed code is available: https://www.pcg-random.org/download.html.

Note that the site claims that PCG's outputs are more difficult to predict than those of other PRNGs and that that means that PCG is more secure. It is possible to predict some generators after only three outputs, so it should not be considered "hard to break" and definitely not "more secure". The predictability of a non-cryptographically-secure PRNG is usually not a problem.

xoshiro family

Like PCG, the xoshiro and related xoroshiro families are fairly new PRNGs.

Rolling your own

If you are still not satisfied, you may want to build your own PRNG. You can do this in a fairly trial-and-error way by writing something that looks good and subjecting it to automated statistical testing suites such as TestU01's SmallCrush, Crush and finally BigCrush. These tests are very easy to run and can quickly point out problems, for example: 

#include <unif01.h>
#include <bbattery.h>

#include <stdint.h>

static uint32_t next = 1;
unsigned int custom_rand(void) {
    // This is a terrible generator!
    next = (next * 0x4B4B9656U) ^ (next * 0x565AC3C3U) + 1;
    return next * (next - 1);
}

int main(void) {
    unif01_Gen *gen = unif01_CreateExternGenBits("custom_rand", custom_rand);
    bbattery_SmallCrush(gen);  // or bbattery_Crush or bbattery_BigCrush
    unif01_DeleteExternGenBits(gen);
}

SmallCrush will report that this generator failed 12 out of 15 statistical tests. The other tests, which are also much slower, are therefore not necessary.

Retrieved from "https://wiki.osdev.org/index.php?title=Random_Number_Generator&oldid=27595"