Let’s start by summarising everything we know about his strategy:
- Alex required results from about 24 spins in order to predict future outcomes.
- Agents would wait for the right moment to press the spin button.
- Brendan Koerner was able to trace the origins of the PRNG algorithm – pseudo random number generator (from the mathematical proofs provided by Alex) to the book The Art of Computer Programming.
Disclaimer: the following technical analysis is only speculation on where Aristocrat engineers may have gone wrong, and how Alex may have exploited it.
- The PRNG that might have been used in Aristocrat cabinets
The simplest PRNG algorithm described in The Art of Computer Programming which gives satisfactory results is actually quite simple:
RNG = (a * PreviousRNG + c) mod m
This algorithm, known as Linear Congruential Generator (LCG), is still used as a default PRNG algorithm in many programming languages (e.g. Java).
Could Aristocrat slot machine developers simply have used the default PRNG algorithm provided by the programming language they used? Or could they have used the simplest PRNG which meets the requirement of uniformity?
I think that it’s possible scenario. This default algorithm works and meets the criteria of uniformity of generated random numbers. It might have met all the criteria programmers were working in the requirements specification.
Now let’s speculate on how bold Alex could have exploited this algorithm.
The first step is to get to know the exact parameters of the algorithm (parameters a, c and m). This is the easy part, as these parameters are written in every slot machine. Alex just had to read the binary code from the cabinet memory and decompile it. This is a task which any specialist in microelectronics can do if he is equipped with the proper tools.
But knowing just the a, c and m parameters alone isn’t enough. With the decompilation, you can actually read the parameters of all PRNG algorithms – even the cryptographically secure ones. To be able to predict and exploit the RNG sequence in a real slot machine placed in a casino, you’ll also need to know something else – the current RNG seed value.
Finding the current RNG value
The LCG PRNG (Linear Congruential Generator Pseudo Random Number Generator) algorithm is generally characterized as easily predictable. This means that just by knowing 3 random numbers you are able to calculate a, c, m parameters and easily predict the next numbers in the sequence.
Alex already knew a, c, and m parameters from the decompilation, but he didn’t know the current RNG (Random Number Generator) state value. He was able to observe the produced random numbers indirectly by watching the positions where the reels stopped in recorded spins.
The key point is that logic of a slot game is deterministic and programmed inside the cabinet. So it can be decompiled, reverse-engineered and simulated somewhere else. The game logic usually takes a random number and uses some mathematical operations to determine where each reel should stop.
The slot machine reels usually have around 50 to 100 symbols, three of which are displayed on the screen. The combinations may sometimes repeat, and reels can have a different length, but let’s assume that there are 50 unique combinations on each reel. The random number selects one of these 50 combinations, so just by looking at the first reel in the first spin you can eliminate 49/50 (98%) of potential random numbers.
If you know the outcome of many consecutive random numbers, then you’ll very soon end up with just 1 initial random number which gives the desired outcome for all spins. In fact, the number of spins you need is proportional to the length of the initial random number.
So you just need to simulate all the possible random numbers and… If a slot machine used random numbers which are 64 bits long, then simulating all of them would require too much computational power. So, Alex still needed to get a little unintentional help from Aristocrat’s developers:
- Use a RNG state that is too short (32-bit).
- Use the random number in a way that it can be used to help find the current RNG state.
Too short (32 bit) RNG (Random Number Generator)
Aristocrat MK IV cabinets were developed on a 32-bit ARM 250 processor. If the slot developers decided to also use a 32-bit random number seed, then there are just 4,294,967,296 possible RNG states. It may look like a lot, but current computers are very fast and this number of options can easily be examined by brute force (taking a few seconds on a regular laptop).
However, this option could be less likely. Moreover, a 32-bit random number is too short to cover all possible results in some games (5 reels * 90 symbols).
Using a random number in “an easy to exploit” way
Let’s now assume that there was a 64-bit RNG state in use. How do you use a 64-bit number to deterministically stop 5 reels by 50 symbols each? The easiest approach which preserves uniformity would be the following:
Pos1 = RND modulo 50
Pos2 = (RND / 50) modulo 50
Pos3 = (RND / (50*50)) modulo 50
Pos4 = (RND / (50*50*50)) modulo 50
Pos5 = (RND / (50*50*50*50)) modulo 50
Each reel now uses its share of a random number, and there are no correlations between the individual reels. As long as the random numbers are uniform, then there is a uniform chance of any possible outcome of the game. Therefore, the regulator approves.
Let’s see next the exploitation of the RNG:
If you know the positions of the reels, you can easily calculate the end of a random number (RND mod 50^5):
RndEnd = pos1 + pos2*50 + pos3*50*50 + pos4*50*50*50 + pos5*50*50*50*50*50
Will this help you guess the current state of the RNG? Actually, it will help a lot.
Now you don’t need to simulate all possible random numbers, but only those that end with the value of RndEnd. That is, all random numbers that match the pattern RndEnd + X * 50^5:
1 * 312500000 + RndEnd
2 * 312500000 + RndEnd
3 * 312500000 + RndEnd
So out of 2^64 possible values (1846674407370955161616), only 59029581035 will have to be tested. Both are a huge amount of possible values, but while on an ordinary laptop the simulation of the first would take 544 years, the simulation of the second would be complete in 60 seconds.
In other words, the random number is now known and future rotations can be predicted.
The actual RNG exploitation used by Alex could be different, but possibly has much in common with the process described above.