Random Numbers
Random Numbers
Don’t get your Pseudo and True Random Numbers Mixed Up
Within cryptography random numbers are used to generate things like encryption keys. If the generation of these keys could be predicted in some way, it may be possible to guess them. The two main types of random number generators are:
- Pseudo-Random Number Generators (PRNGs). This method repeats the random numbers after a given time (periodic). They are fast and are also deterministic, and are useful in producing a repeatable set of random numbers.
- True Random Number Generators (TRNGs). This method generates a true random number, and uses some which is random. One approach is to monitor the movements of a mouse pointer on a screen or from the pauses in key-strokes. Overall the method is generally slow, especially if it involves human interaction, but is non-deterministic and aperiodic.
Normally simulation and modelling applications use PRNG, so that the values generated can be repeated for different runs, while cryptography, lotteries, gambling and games use TRNG, as each value which is selected at random should not repeat or be predictable. Eve could thus guess the key created by the method that Bob uses to generate a key. So, in the generation of encryption keys for public key encryption, user’s are typically asked to generate some random activity. The random number is then generated based on this activity.
Computer programs, though, often struggle to generate TRNG, and hardware generators are often used within highly secure applications. One method is to generate a random number based on low-level, statistically random “noise” signals. This includes things like thermal noise and from the photoelectric effect.
Within cryptography, it is important that we are generating values which are as near random, so that Eve cannot guess the random numbers that Bob and Alice are used. With randomness we cannot determine how random the values are by just taking a few samples. For this we need a large number of samples, and make an estimation of the overall randomness.
Hacking a lottery
Unfortunately computers tend to generate PRNGs. Eddie Tipton, who was the computer information security director with the Multi-State Lottery Association from 2003 until 2015, “rigged” the winning numbers in several US states, and where he picked up millions in winnings. While in his post he wrote much of the software used in the lotteries and where he says he took advantage of a loophole in the random number generator.
His defence is that it was not his fault that there was a loophole, and he was just exploiting it. For this, he found that if the draw happened on Wednesdays or Saturdays after 8pm, the numbers could be predictable. He then won in Colorado in 2005, Wisconsin in December of 2007, Kansas in December of 2010 and Oklahoma in 2011.
He also attempted to collect a $16.5 million Hot Lotto ticket in December 2010 in Iowa, but is was rejected as the state would not pay an anonymous claimant. This then led to an investigation of Tipton and his connections. Eddie, himself, did not purchase the tickets, but passed on information to his brother (Tommy).
It is thought they received over $2.2 million with the scheme. It has also led to a lawsuit against Iowa-based Multi-State Lottery Association (and which serves 33 states). It is thus claimed that it did not serve random numbers, and which were used in many online lotteries.
A lottery should always be of the TRNG type. Normally simulation and modelling applications use PRNG, so that the values generated can be repeated for different runs, while cryptography, lotteries, gambling and games use TRNG, as each value should not repeat or be predictable. In the case of the lottery hack, the generation of key was deterministic, where Eve could possibly guess the key created. So, in the generation of encryption keys for public key encryption, users are often asked to generate some random activity, and where a random number is then generated based on this activity. This random number is then used to generate the encryption keys.
Computer programs, though, often struggle to generate truly random numbers, so hardware generators are often used within highly secure applications. One method is to generate a random number based on low-level, statistically random noise signals. This includes things like thermal noise and from the photoelectric effect. If you are interested in random numbers, here is a way to determine if they are random … measure entropy [here].
The Wall
The world is full of scary stories of cyber security, and of cyber criminals coming after you. So sometimes it is just nice to sit down in front of something soothing — like a lava lamp. Ah! Just saying the word “lava lamp” has reduced your stress. Now look at the picture on the right-hand side, and you will have already be in a relaxed state.
In cyber security one of the greatest challenges is to find a truly random number generator, and CloudFlare seems to have found one of the most engaging methods around. In their San Francisco office, they have a wall of 100 lava lamps. But for them it is not just a bit of eye candy, but part of their random number generator infrastructure. Currently they use them to generate random numbers and which is used for around 10% of all Internet traffic.
CloudFlare has dubbed the random number generator — the Wall of Entropy. It was inspired by an engineer at Silicon Graphics who used proposed that fluid movements in lava lamps could be seen a truly random, as it is almost impossible to model the flow. The create the random numbers by taking a photograph of the lamps every few milliseconds, and which will be affected by the light outside and people moving around them. These create small changes which are then used to create the random numbers. This creates 16,384 bits of entropy each time.
The concept of using a lava lamp to generate numbers has been around for a while. In 1996, Landon Curt Noll, Robert G. Mende, Sanjeev Sisodiya at Silicon Graphics defined a patented system called Lavarand (Patent 5,732,138: “Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system.”). And by 2007 lavarnd even had its own site to generate numbers for its users.
In London, CloudFlare they use a dual pendulum system which hangs one pendulum off another, the movements are extremely difficult to predict the movement:
In Singapore they base the generation on radioactive decay, where they have uranium in a glass bell jar. They then use a Geiger counter to measure the release of isotopes over time.
Testing for randomness
There are various tests for randomness. For example, we could define an aver-age value which is half way between the number range, and then determine the ratio of the values above and below the half way value. This will work, but will not show us if the values are well distributed. Along with this we could determine the arithmetic mean of the values, and match it to the centre value within the range of numbers. An improved method to test for the distribution of values is the Monte Carlo value for Pi test. With this method, we take our random numbers and scale them between 0.0 and 1.0. Next we take two values at a time and calculate:
√(x²+y²)
If this value is less than or equal to one, we place in the circle (with a radius of 1), otherwise it is out of the circle. The estimation of PI is then four times the number of points in the circle (M) divided by the total number of points (N). In the figure, the blue points are outside the circle and the yellow ones are inside:
The following is an outline of the code:
import sys
import math
values = [5,125,10,1,32, 101,33, 54,200,230,215,93,50,100,3,6,43]
max=255.0
inval=0
outval=0
ptr=0
print "Values:",values
print "Pairs:"
print "\tX\t\Y\tZ:"
for i in range(0,len(values)/2):
x = (values[ptr]-max/2)/(max/2)
y = (values[ptr+1]-max/2)/(max/2)
z = math.sqrt(x*x+y*y)
print "\t",round(x,3),"\t",round(y,3),"\t",round(z,3)
if (z<1):
inval=inval+1
else:
outval=outval+1
ptr=ptr+2
print "\nInval:",inval," Outval:",outval
print "\nResult: ",4.0*inval/(inval+outval)
A sample run for values of 5, 125, 10, 1, 32, 101, 33, 54, 200, 230, 215, 93, 50, 100, 3, 6, 43 is:
First Five Pairs:
X Y Z:
-0.961 -0.02 0.961
-0.922 -0.992 1.354
-0.749 -0.208 0.777
-0.741 -0.576 0.939
0.569 0.804 0.985
Inval: 6 Outval: 2
Result: 3.0
The closer we get to π (3.14159265359…) the more random the data is. As we are only using just a few points, it looks like the data is a good approximation to being random, but to be sure we would need many more samples.
A demo of this is here.
Conclusions
Random numbers are often not that random, so make sure you have true random ones when you need them, and pseudo when you need them, and don’t get them mixed up.