Monthly Archives: November 2013

A word or two about random number generators.

Random number generators are pieces of code that provide a stream of “Random Numbers.”

First of all, it must be mentioned that there are no such things as random numbers in real life. Is 5 more or less random than 10? Are either of those more or less random than 121? The question is meaningless. There’s nothing intrinsically random about a number and no way to measure the randomness of a particular number. What so-called random number generators do in real life is to generate sequences of numbers which appear to be randomly selected.

There is an alphabet soup of abbreviations people use when talking about these, and it turns out that understanding exactly what the capabilities of a random number generator are and how they differ from each other in capabilities is parallel to understanding a selected set of these abbreviations, so I’m going to start by just listing and explaining them.

The general class of thing we’re talking about is the random number generator, so all of these abbreviations end in the sequence “RNG” for Random Number Generator. Or, depending on the size of the number people intend to read, RBG for Random Bit Generator.

Some of them are good for crytographic applications, and the abbreviations for those start with “CS” for Cryptographically Secure, or depending on the writer they can start with just “S” for Secure.

Now between the optional “CS” and the trailing “RNG” comes a third thing; it can be the letter “P” marking the results as Pseudo-Random or equivalently the letter “D” marking the method as Deterministic, or it can be the letter T marking the results as Truly-Random.  A deterministic random number generation process always produces a pseudo random result. Unfortunately, a lot of writers will leave one or the other of these letters out, calling out one case as special by designating it with a letter and the other case as the default by not designating it with a letter. As a result, if you see “CSRNG” you don’t know whether it’s truly random or pseudo-random unless you know which case a particular author is leaving out.

So here’s the alphabet soup:

 

Abbreviations Description
RNG,RBG Random Number Generator. With no further information given it can be any of these types.
PRNG,DRNGPRBG,DRBG Pseudo-Random Number Generator. This is a generator which has some internal state, and each time a number is produced, the internal state changes. The primary attribute of a PRNG is that if you start with the same initial state, then exactly the same sequence of numbers will be produced. Nothing has been said about whether this is a cryptographically secure generator or not; In principle it could be something so simple that if someone who knows which generator it is sees one output they will know its state and be able to predict all subsequent outputs immediately, such as a counter.
CSPRNG,SPRNG,CSDRNG,SDRNG,CSPRBG,SPRBG,

CSDRBG,SDRBG

Cryptographically Secure Pseudo Random Generator: This will produce a sequence which is completely predictable and repeatable if you know its internal state, but which cannot be predicted by anyone who does not know the internal state — even if that person has watched the entire output from the time it was started to the current time. CSPRNGs are often used as stream ciphers; you take your plaintext, one unit at a time, and modular-add the output of a CSPRNG, and the result is the ciphertext. At the other end, your correspondent using the same CSPRNG with the same initial state simply takes your ciphertext, modular-subtracts the output of his CSPRNG, and gets the plaintext.
CSTRNG, STRNG This is a “Secure True Random Number Generator” – it has entropic or chaotic inputs which, in theory, make it impossible to predict the next value, and also has internal state which allows it to buffer, whiten, and mix the output of its entropic inputs and to produce an output at any time. It is also cryptographically secure, which means that there is no known method of predicting it. Cryptographic Security is a statement of negative knowledge, so it’s important to remember that some kind of mathematical discovery could cause something that used to be Cryptographically Secure to cease to be so. You can’t verify that something is Cryptographically Secure and then rely on it forever; you have to keep checking to make sure that nobody has made a discovery yet that allows an attacker to figure it out.
TRNG This is a “True Random Number Generator” – it has or is an entropic or chaotic input which, in theory, makes it impossible to predict the next value, but may be subject to biases or patterns that need to be corrected for, or subject to limitations such as how often it produces a value. For example, it may change only once per minute, or have a bell-curve distribution instead of a uniform distribution, or may favor a particular output so much that it occurs every third time it’s used. This is also called an “entropy source”. Its output must be “whitened” before it becomes useful.
CSRNG,SRNG,CSRBG,SRBG This is a “Cryptographically Secure Random Number Generator” It might be a CSTRNG or a CSPRNG as above, and the writer simply hasn’t told you which. He or she assumes you will get that from context.

For any internal state of finite size, a PRNG will at least in theory eventually repeat. However, it is possible to build a PRNG that never actually repeats using only 3492 bits of state. By this I mean that if you want a different number every Planck Instant for the entire time from the Big Bang to the Heat Death of the universe, you’ll need 3491 bits of state to represent enough different numbers. The Planck time is about 5.391 * 10-44 seconds, and it is now believed that the universe eventually gets to be about 1 * 101000 years old. You can do the math yourself if you want.