This past summer I developed a slight obsession with Random Number Generators. I studied and implemented various Generators, as well as Tests used to determine the statistical quality of randomness that a generator produces. I’m planning on uploading most of that code in the upcoming weeks, but for now, I’d like to deal with a little theory.
Something I noticed during my studies was that there was a variety of ways to classify RNG’s:
Distribution (Uniform, Gaussian, etc)
Process (Linear Congruential, Multiply with Carry, etc)
Use (Physical Simulations, Cryptography, Games, etc)
However it seemed to me that you could also organize RNG’s into a Hierarchy. Clearly, some RNG’s are better than others. Some algorithms produce better quality sequences than other algorithms, and hardware random numbers generators (while not always practical or needed) will almost always be better than software.
So I would like to take this time to go over a system that has worked for me in ranking various RNG’s, and I hope you guys find good use for it as well.
The Hierarchy of Random Number Generators
1st Degree – Low Quality
Generators that produce low quality random numbers. These are often used where there just needs to be some variance among the output, with little regard to the quality of these numbers. Often the Generator’s in the standard libraries are this type. These generators often used for debugging purposes, and tend to be fast and easy to implement.
Examples: Pretty much any RNG in a standard library. From C to Java, almost all of them are low quality. Linear Congruential Generators,
2nd Degree – Medium Quality
These are generators which produce sequences that show good local randomness, but do not show the appropriate quality for their entire period. Simply put, they pass standard tests, and for a short sequence, say between 1,000 – 10,000,000 bytes, you would probably not be able to tell it apart from one produced by a true random number generator, but for longer sequences, or with more extensive testing, they would fail.
Examples: These are actually quite common. Most of George Marsaglia’s generators would also qualify.
3rd Degree – High Quality
Generators that produce random numbers that are virtually indistinguishable from a true random sequence. They have a period large enough that for all practical purposes do not repeat. They pass standard tests as well as more extensive and detailed statistical tests.
Examples: Mersenne Twister, Well Equidistributed Long-Period Linear
4th Degree – Cryptographically Secure
These are high quality RNG’s that are also designed to be able to hold up under attack. Stream Ciphers should be of this Degree. I’m well aware that in building a random number generator, there are multiple aspects that must be taken into account in order for it to be secure, but for the moment, I would like to narrow my focus.
a) With a Cryptographically Secure RNG, it should be infeasible to use contemporary technology to crack the generator within a time frame that it would be useful.
b) To “crack” the generator means to recover the internal state with only the output of the generator and knowing the algorithm that produced it.
c) If the internal state should be compromised, it should also be infeasible to use the current state to generate the previous outputs of the generator.
Examples: Fortuna, Blum Blum Shub, AES (using CTR & OFB Mode)
Notice that this definition does not take into account entropy pools, or harvesting entropy. Again, there are many aspects that must be taken into account when designing a practical and secure RNG.
5th Degree – True RNG
Also known as a Hardware RNG, these are generators that derive their output from a physical source. This could any number of sources, such as radiation, atmospheric noice, lava lamps, quantum processes, camera/audio noice, etc.
Just a few points I would like to make:
1. This is a hierarchy, not a classification. The difference between each is a matter of degree, not type. All True RNG’s are Cryptographically Secure RNG’s, but not vice versa. All Cryptographically Secure RNG’s are High Quality RNG’s, but again, not vice versa.
2. I ranked these according to their Unpredictability, which is a combination of the quality of their output, and the difficulty needed in understanding the process that creates the output.
3. All RNG’s are Guilty until proven Innocent. You cannot simply make a RNG and say it is High Quality. You have to test it in order to determine it’s quality. Likewise, you cannot simply build a Hardware Generator and say it’s a True RNG. Does it produce High Quality Output? Is it possible to predict the next output? Until they’ve been tested, all RNG’s are 1st Degree. They must be proven worthy of a higher rank.
I hope you all find this interesting. Please let me know what you think.