Can You Crack The Lottery, and Write Your Name in Sand?
If you play roulette, you should know that, on average, you will lose money. This is because of the ‘0’ number, and which changes the odds to be in the favour of the casino. As we have 37 numbers, of which 18 are black, the bet for black gives the odds of:
Odds = 18/37 = 0.484
Which means that you have a slightly lower than 50/50 chance of winning. If your stake was $100, then after 37 spins, you will be, on average, $100 down.
What is random?
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 it 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 the 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]:
Cracking a random number?
And so, if we can get an edge on the creation of the random number, we could end up millionaires. Thus our random numbers should not really leak any information back on the seeds that we have used to generate the numbers, otherwise, an adversary could guess how they were generated and perhaps guess future ones.
Well, let’s look at a random number generator, and see if we can hack it?
Xoroshiro128+ is one of the fastest Pseudorandom number generators (PRNGs). It was created in 2016 by David Blackman and Sebastiano Vigna and requires two 64-bit unsigned integers as seeds [sample run]:
Seed 1: 74254124354025
Seed 2: 74398021324531
0 0x8732c65698dcL '\xdc\x98V\xc62\x87'
1 0x5f111e6e4815f86L '\x86_\x81\xe4\xe6\x11\xf1\x05'
2 0xc6f92404ee3bbe46L 'F\xbe;\xee\x04$\xf9\xc6'
3 0x4e6fb549d473d685L '\x85\xd6s\xd4I\xb5oN'
4 0xb8d3732bf3fc92ceL '\xce\x92\xfc\xf3+s\xd3\xb8'
5 0x584ddf04552308daL '\xda\x08#U\x04\xdfMX'
6 0x5b25d45d6350e6a8L '\xa8\xe6Pc]\xd4%['
7 0x9dd6e25a5f4c2964L 'd)L_Z\xe2\xd6\x9d'
8 0x4c3b9cfaff5d8368L 'h\x83]\xff\xfa\x9c;L'
9 0xb49f882106f12258L 'X"\xf1\x06!\x88\x9f\xb4'
And so we take two random seed values, and can then produce a random sequence. The code is here:
But, watch, I can determine some random messages
Seeds (12367730189591718825, 18127581570428703238)
0 0xa7351c7982cf3daf '¯=Ï\x82y\x1c5§'
1 0x656c707041206e41 'An Apple'
2 0x7961442041 'A Day'
3 0xb2f3ab65f678cf83 '\x83Ïxöe«ó²'
4 0x473c44a6c92818b7 '·\x18(É¦D<G'
5 0xd632d96cc745bd4a 'J½EÇlÙ2Ö'
6 0x4266815dbc316054 'T`1¼]\x81fB'
7 0xbe92a8de48abd944 'DÙ«HÞ¨\x92¾'
8 0x48183e8df662ee45 'Eîbö\x8d>\x18H'
9 0x66c9ff1266a00f05 '\x05\x0f\xa0f\x12ÿÉf'
The code-cracker uses the Microsoft Z3 library:
Can you generate your own name in Xoroshiro128+? Here’s mines: