Random Number Generator: Difference between revisions
[unchecked revision] | [unchecked revision] |
(→Rolling your own: Add a TestU01 example) |
m (Bot: Replace deprecated source tag with syntaxhighlight) |
||
(11 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
Random number generators (RNG) can be implemented in lots of different ways. This article explains some of them. |
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 == |
== Types of random number generators == |
||
Line 19: | Line 23: | ||
There are roughly two kinds of applications: cryptography, and everything else. |
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. |
|||
In a cryptographic system it is often necessary to generate values that are absolutely not predictable. If an adversary knows what the next outputs will be, it will be very easy for them to guess the private keys you generate. This will, for example, compromise HTTPS traffic. |
|||
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 [https://en.wikipedia.org/wiki/RSA_(cryptosystem) 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 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. |
||
Line 29: | Line 35: | ||
Newer x86 and x86-64 processors have the instruction RDSEED for generating random numbers. |
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. |
To use RDSEED you will first need to check if the instruction is available. |
||
< |
<syntaxhighlight lang="asm"> |
||
mov eax, 7 ; set EAX to request function 7 |
mov eax, 7 ; set EAX to request function 7 |
||
mov ecx, 0 ; set ECX to request subfunction 0 |
mov ecx, 0 ; set ECX to request subfunction 0 |
||
Line 35: | Line 41: | ||
shr ebx, 18 ; the result we want is in EBX... |
shr ebx, 18 ; the result we want is in EBX... |
||
and ebx, 1 ; ...test for the flag of interest... |
and ebx, 1 ; ...test for the flag of interest... |
||
</syntaxhighlight> |
|||
</source> |
|||
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. |
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. |
||
< |
<syntaxhighlight lang="asm"> |
||
mov ecx, 100 ; number of retries |
mov ecx, 100 ; number of retries |
||
.retry: |
.retry: |
||
Line 49: | Line 55: | ||
.done: |
.done: |
||
; random number is in EAX |
; random number is in EAX |
||
</syntaxhighlight> |
|||
</source> |
|||
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. |
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. |
||
Line 65: | Line 71: | ||
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. |
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 |
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 == |
== Cryptographically secure pseudorandom number generators == |
||
Now follow some CSPRNGs. It is important to remember that, as with |
Now follow some CSPRNGs. It is important to remember that, as with everything cryptographic, it is best <em>not</em> 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 === |
=== x86 RDRAND Instruction === |
||
RDRAND is slightly older than RDSEED, and provides ([https://software.intel.com/content/www/us/en/develop/blogs/the-difference-between-rdrand-and-rdseed.html what Intel claims to be]) a CSPRNG. |
RDRAND is slightly older than RDSEED, and provides ([https://software.intel.com/content/www/us/en/develop/blogs/the-difference-between-rdrand-and-rdseed.html what Intel claims to be]) a CSPRNG. |
||
Its presence is indicated by CPUID leaf 1, ECX bit 30: |
Its presence is indicated by CPUID leaf 1, ECX bit 30: |
||
< |
<syntaxhighlight lang="asm"> |
||
mov eax, 1 ; set EAX to request function 1 |
mov eax, 1 ; set EAX to request function 1 |
||
mov ecx, 0 ; set ECX to request subfunction 0 |
mov ecx, 0 ; set ECX to request subfunction 0 |
||
Line 80: | Line 93: | ||
shr ecx, 30 ; the result we want is in ECX... |
shr ecx, 30 ; the result we want is in ECX... |
||
and ecx, 1 ; ...test for the flag of interest... |
and ecx, 1 ; ...test for the flag of interest... |
||
</syntaxhighlight> |
|||
</source> |
|||
If ECX is set to 1 (or ZF is unset), the instruction is available. Usage is identical to RDSEED: |
If ECX is set to 1 (or ZF is unset), the instruction is available. Usage is identical to RDSEED: |
||
< |
<syntaxhighlight lang="asm"> |
||
mov ecx, 100 ; number of retries |
mov ecx, 100 ; number of retries |
||
.retry: |
.retry: |
||
Line 94: | Line 107: | ||
.done: |
.done: |
||
; random number is in EAX |
; random number is in EAX |
||
</syntaxhighlight> |
|||
</source> |
|||
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. |
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. |
||
Line 103: | Line 116: | ||
[https://www.bentasker.co.uk/blog/software-development/689-writing-a-chacha20-based-csprng Writing (and backdooring) a ChaCha20 based CSPRNG] may be an interesting article on the subject, and how it can go wrong in surprising ways. |
[https://www.bentasker.co.uk/blog/software-development/689-writing-a-chacha20-based-csprng 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 == |
== Pseudorandom number generators == |
||
Line 112: | Line 125: | ||
Taken directly from the [http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf C standard document (p. 347)]: |
Taken directly from the [http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf C standard document (p. 347)]: |
||
< |
<syntaxhighlight lang="c"> |
||
// The following functions define a portable implementation of rand and srand. |
// The following functions define a portable implementation of rand and srand. |
||
Line 127: | Line 140: | ||
next = seed; |
next = seed; |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
This is a fairly standard but mediocre [https://en.wikipedia.org/wiki/Linear_congruential_generator Linear Congruential Generator] (LCG). It returns 15 random bits. |
This is a fairly standard but mediocre [https://en.wikipedia.org/wiki/Linear_congruential_generator Linear Congruential Generator] (LCG). It returns 15 random bits. |
||
Line 158: | Line 171: | ||
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 2<sup>n</sup> possible combinations of registers, the all-zero state is not allowed. Therefore, 2<sup>n</sup> - 1 states is the maximum possible. |
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 2<sup>n</sup> possible combinations of registers, the all-zero state is not allowed. Therefore, 2<sup>n</sup> - 1 states is the maximum possible. |
||
=== Wichmann-Hill === |
|||
In 1982, Brian Wichmann and David Hill [https://doi.org/10.2307/2347988 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: |
|||
<syntaxhighlight lang="c"> |
|||
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); |
|||
} |
|||
</syntaxhighlight> |
|||
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 === |
=== Mersenne Twister === |
||
Line 163: | Line 191: | ||
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: |
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: |
|||
<source lang="c"> |
|||
// MT-19937-64. Declare mt_seed and mt_rand extern in some header |
|||
// Based on mt19937ar.c found here: http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/MT2002/CODES/mt19937ar.c |
|||
<syntaxhighlight lang="c"> |
|||
#include <stddef.h> |
|||
#include <stdint.h> |
#include <stdint.h> |
||
#include <assert.h> |
|||
#ifdef USE32 |
|||
#define W 64 |
|||
typedef uint32_t word_t; |
|||
#define N 312 |
|||
#define |
#define STATE_SIZE 624 |
||
#define |
#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 |
#define LOWER_MASK 0x7fffffff |
||
#define |
#define UPPER_MASK (~(word_t)LOWER_MASK) |
||
static word_t state[STATE_SIZE]; |
|||
#define D 0x5555555555555555ULL |
|||
static size_t index = STATE_SIZE + 1; |
|||
#define S 17 |
|||
#define B 0x71D67FFFEDA60000ULL |
|||
#define T 37 |
|||
#define C 0xFFF7EEE000000000ULL |
|||
#define L 43 |
|||
#define F 6364136223846793005 |
|||
static void seed(word_t s) |
|||
#define MASK_LOW ((1ULL << R) - 1) |
|||
{ |
|||
#define MASK_UPP (~MASK_LOW) |
|||
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 |
static void twist(void) |
||
{ |
|||
static unsigned int index = N + 1; |
|||
for (size_t i = 0; i < STATE_SIZE; i++) |
|||
{ |
|||
static void mt_twist(void) { |
|||
word_t x = (state[i] & UPPER_MASK) | (state[(i + 1) % STATE_SIZE] & LOWER_MASK); |
|||
for (unsigned int i = 0; i < N; ++i) { |
|||
x = (x >> 1) ^ (x & 1? TWIST_MASK : 0); |
|||
state[i] = state[(i + MIDDLE) % STATE_SIZE] ^ x; |
|||
if (x & 1) { |
|||
xa ^= A; |
|||
} |
|||
state[i] = state[(i + M) % N] ^ xa; |
|||
} |
} |
||
index = 0; |
index = 0; |
||
} |
} |
||
static word_t mt_random(void) |
|||
void mt_seed(uint64_t seed) { |
|||
{ |
|||
state[0] = seed; |
|||
index = |
if (index >= STATE_SIZE) |
||
{ |
|||
for (unsigned int i = 1; i < N; ++i) { |
|||
assert(index == STATE_SIZE || !"Generator never seeded"); |
|||
state[i] = F * (state[i - 1] ^ (state[i - 1] >> (W - 2))) + i; |
|||
twist(); |
|||
} |
} |
||
} |
|||
word_t y = state[index]; |
|||
uint64_t mt_rand(void) { |
|||
y ^= (y >> SHIFT1) & MASK1; |
|||
y ^= (y << SHIFT2) & MASK2; |
|||
y ^= (y << SHIFT3) & MASK3; |
|||
y ^= y >> SHIFT4; |
|||
mt_twist(); |
|||
} |
|||
uint64_t y = state[index]; |
|||
y ^= (y >> U) & D; |
|||
y ^= (y << S) & B; |
|||
y ^= (y << T) & C; |
|||
y ^= y >> L; |
|||
++ |
index++; |
||
return y; |
return y; |
||
}</syntaxhighlight> |
|||
} |
|||
</source> |
|||
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 [https://arxiv.org/abs/1910.06437 "It is high time we let go of the Mersenne Twister"]. |
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 [https://arxiv.org/abs/1910.06437 "It is high time we let go of the Mersenne Twister"]. |
||
Line 233: | Line 277: | ||
=== PCG family === |
=== PCG family === |
||
The [https://www.pcg-random.org/ 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 [https://www.pcg-random.org/pdf/hmc-cs-2014-0905.pdf comprehensive paper] describing the generators and Apache 2.0-licensed code is available: https://www.pcg-random.org/download.html. |
|||
The PCG family is a relatively recent addition to the field of PRNGs. |
|||
<!-- This, and next sections are TODO. Tomorrow, probably. It's bedtime --> |
|||
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 [https://pcg.di.unimi.it/pcg.php#claims 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 === |
=== xoshiro family === |
||
Line 244: | Line 289: | ||
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 [http://simul.iro.umontreal.ca/testu01/tu01.html TestU01]'s SmallCrush, Crush and finally BigCrush. These tests are very easy to run and can quickly point out problems, for example: |
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 [http://simul.iro.umontreal.ca/testu01/tu01.html TestU01]'s SmallCrush, Crush and finally BigCrush. These tests are very easy to run and can quickly point out problems, for example: |
||
< |
<syntaxhighlight lang="c"> |
||
#include <unif01.h> |
#include <unif01.h> |
||
#include <bbattery.h> |
#include <bbattery.h> |
||
Line 253: | Line 298: | ||
unsigned int custom_rand(void) { |
unsigned int custom_rand(void) { |
||
// This is a terrible generator! |
// This is a terrible generator! |
||
next = (next * 0x4B4B9656U) ^ (next * |
next = (next * 0x4B4B9656U) ^ (next * 0x565AC3C3U) + 1; |
||
return next * (next - 1); |
return next * (next - 1); |
||
} |
} |
||
Line 262: | Line 307: | ||
unif01_DeleteExternGenBits(gen); |
unif01_DeleteExternGenBits(gen); |
||
} |
} |
||
</syntaxhighlight> |
|||
</source> |
|||
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. |
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. |
Latest revision as of 05:46, 9 June 2024
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.