Pseudo Random Number Generators

Introduction

In Random - What does that actually mean? we discovered what it means for a number or sequence to be random. We also talked about how important randomness is in our modern world. What we did not talk about however, is how to generate such a truly random number.

Generating Randomness

There are a few ways to generate random numbers. You could take some radioactive isotope and place it in front of a Geiger counter. The elapsed time between two "ticks" is random and can be used to generate a random number or sequence. You could also measure the time interval between to keystrokes on a keyboard. While most people type at a fairly constant frequency, the difference if measured in micro seconds is still variable enough to be a good source of randomness.
There are more ways like these that can be used to generate a random number. However, all of them have one problem in common: They are slow.

To get around that restriction, a pseudo random number generator (PRNG) can be used. A PRNG is an algorithm that takes a seed value and then produces an evenly distributed sequence of numbers that appears random. However, it is not actually random. In fact, if you use the same seed value to start the generator, you will get the exact same sequence, every time.

That poses a potential problem. While for statistical simulations it might not matter or it might even be beneficial if you can reproduce the same sequence of "random" numbers, in cryptography it is potentially disastrous. Remember, the strength of most cryptographic algorithms is based on the key. If the key can be predicted, the encryption is easy to crack.

Most PRNGs use a comparatively short seed. That means, if the PRNG algorithm that was used to generate the key is known, the complexity of guessing the correct key is reduced to guessing the correct seed.

To be able to be used in cryptography, a PRNG needs to fulfill this additional requirement over the statistical randomness required by every PRNG: It needs to pass the next-bit test. That means that it is computationally infeasible to predict the next bit, even if all previously generated bits (but not the seed) are known. A PRNG that passes the next-bit test is called a Cryptographically Secure Pseudo Random Number Generator or CSPRNG.

The PRNG in your programming language of choice is most likely a linear congruential generator. That algorithm is easy to implement and very fast. It passes all statistical randomness requirements. However, it does not pass the next-bit test as it is easy to calculate the parameters and state based on enough previously generated values.

A common way to build a CSPRNG is to use a secure block cipher (like AES) and run it in counter mode. Counter mode means, that a known unique sequence of numbers (like 1, 2, 3, 4, 5...) is encrypted one at a time. An actual implementation is a little more complicated, but this is the basic functionality.

Some sources, like Wikipedia mention an additional requirement: A CSPRNG needs to pass the state compromise test. That means that even if the current state of the generator is known, it is computationally infeasible to calculate the bits that were generated already. However, the common literature does not mention this requirement (e.g. Handbook of Applied Cryptography (Discrete Mathematics and Its Applications) or Applied Cryptography: Protocols, Algorithms, and Source Code in C). The same Wikipedia entry goes on to mention that a secure block cipher in counter mode is a valid CSPRNG. However, such a generator does not pass the state compromise test.

Summary

Truly random numbers are hard to get by. While methods to generate or rather capture true randomness exists, they are usually slow. A pseudo random number generator can be used to generate a sequence of numbers that looks random. However, in a cryptographic context only cryptographically secure pseudo random number generators should be used.