Online poker is like a dream come true for thousands of players around the world—people who love to play the game but don't live close enough to any legalized gambling locations. Unfortunately, a poor understanding of software and Internet security can quickly turn this dream into a nightmare for everyone involved. Online gaming poses a myriad of security risks. These hazards include various forms of player cheating and the possibility of unfair gaming software, in addition to the risks normally associated with any e-commerce business.
One of those risks surfaced in the software developed by ASF Games: a design flaw allowed a group of security experts at Reliable Software Technologies to cheat at online poker.
The flaw existed in the misuse of an algorithm used to produce a shuffled deck of cards before each round of play. Ironically, the code was publicly displayed at one of the online poker sites that uses the ASF Games software—with the idea of showing how fair the game is to interested players. We used this code to help us predict the complete ordering of every card in the deck in real time. Let me sketch the basic idea.
Given the first five cards in a properly shuffled deck, it’s not possible to predict the remainder. But suppose you knew that the deck was one of only six thousand possible shuffles. It is very likely that each of those shuffles will start with five different cards. As soon as you see the first five cards played, you (or your PC) can search the 6000 possibilities for a match. You now know the order of all the cards, so you also know which cards were dealt to your opponents.
RST exploited the published code to narrow the number of possible shuffles down from approximately 10^{68} (far more than the number of stars in the universe) to approximately 4 billion, then to approximately 86 600,000, and finally to approximately 6,000. Here's how.
The code revealed that the cards were being shuffled using random numbers generated by the Delphi Pascal Random() function. Like most common random number generators, the Random() call uses the Lehmer algorithm to produce streams of pseudo-random numbers. These numbers have many of the mathematical properties associated with random numbers, but they are generated in a completely deterministic manner. It works like this.
Pseudo-random Number Generation
An ideal random number generator would produce a number between 0 and 1, in which every possible value would occur with equal probability. Note that there are an infinite number of values between 0 and 1. But computers do not offer infinite precision— so pseudo-random number generators must behave differently.
typically calculates an integer between 0 and N and returns that number divided by N. The resulting number is always between 0 and 1, but the number of integers between 0 and N limits the number of unique values returned by any pseudo-random number generator. In most common random number generators, N is 2^{32}−1 (approximately 4 billion), which is the largest value that will fit into a 32-bit number. Put another way, there are at most 4 billion possible values produced by this sort of number generator.
Subsequent calls to the generator use the integer result from the previous call to produce a new integer between 0 and N, and then return the new integer divided by N. A number known as the seed is provided to a pseudo-random generator the first time it’s called, in order to get the ball rolling. The seed is also in the range 0 to N. Notice that there is nothing unpredictable about the output of a pseudo-random generator. Each value returned by a pseudo-random number generator is completely determined by the previous value it returned (and ultimately, by the seed that started it all). If we know the integer used to compute any one value, then we know every subsequent value returned from the generator.
Exploiting the Flaw
The shuffling algorithm used in the ASF software always starts with an ordered deck of cards, and then generates a sequence of random numbers used to re-order the deck. In a real deck of cards, there are 52! (approximately 10^{68}) possible unique shuffles. Recall that using a 32-bit random number generator limits the number of possible seeds to approximately 4 billion; since the deck is reinitialized and the generator re-seeded before each shuffle, only 4 billion possible shuffles can result from this algorithm. Four billion possible shuffles is alarmingly less than 52!.
To make matters worse, the algorithm used in this software chooses the seed for the random number generator using the Pascal function Randomize(). This particular Randomize() function chooses a seed based on the number of milliseconds since midnight. There are a mere 86,400,000 milliseconds in a day. Since this number was being used as the seed for the random number generator, the number of possible decks now reduces to 86,400,000. Eighty-six million is alarmingly less than 4 billion.
But that's not all. It gets worse.
There was no need to search through all of the 86,400,000 seeds because they were not being chosen at random—they were based on the clock time. A rough synchronization between the clock running on the server that would be shuffling the cards and the clock used by the exploit drastically reduced the number of potential seeds. Synchronizing to within ten minutes reduces the number of possible seeds to 600,000. And it doesn't take a PC very long to search through 600,000 shuffles.
The next stage of the exploit requires input from the target application. The RST exploit requires five cards from the deck to be known. Our program generates a shuffled deck using each of the 600,000 possible seeds, and then it searches this deck for the five known cards. The chances of a coincidental match are 1 in 380,204,032, which is far larger than the space that is being searched. In the case of Texas Hold’em poker, the program takes as input the two cards that the cheating player is dealt, plus the first three community cards that are dealt face up (the flop). These five cards are known after the first of four rounds of betting and are enough to determine the exact shuffle.
After finding a correct seed once, it is possible to use this information to synchronize the clock used by the exploit program with the server’s clock to within a few seconds, and therefore reduce the number of possible shuffles to only a few thousand. This post facto synchronization enables the exploit program to determine the seed being used by the random number generator, and to identify the shuffle being used during all future games in under one second!
Figure 1 (next page) shows the GUI developed to demonstrate this exploit. The "Site Parameters" box in the upper left is used to synchronize the clocks. The "Game Parameters" box in the upper right is used to enter the five cards and initiate the search. The screen shot shown here is what the GUI displays after the program has determined all of the cards. It shows each of the other player's hands, what the remaining two cards of the flop will be, and who has the strongest hand. All of this is known after only the first of the four rounds of betting!
Lessons Learned
Pascal function Random(). It operates as it was designed to, generating numbers that contain many of the mathematical properties required of random numbers. The fatal flaw was the fact that this function was used for a purpose other than that for which it was designed. Pseudo-random numbers are extremely useful for simulations, in which their repeatability (due to their deterministic nature) is often a very desirable characteristic. Great care must be taken, however, if they are to be used in a situation where predictability is catastrophic.
The misuse of component technology often results in the introduction of security vulnerabilities. Most components are not designed with security in mind. Component testing usually consists only of testing functionality, and does not include an analysis of potential security vulnerabilities. Thus a component that may appear extremely robust after testing may contain functionality that is disastrous from a security perspective.
What makes it difficult to detect security problems is that the functionality of the system is often intact. According to a recent essay by Bruce Schneier, no amount of functional testing can ever uncover a security flaw.
It takes a thorough security analysis of a system to identify these vulnerabilities. And a security analysis is a far different process than a system test. If your designers don't perform a thorough security analysis of a system that needs to protect valuable resources, you can be sure that some of the bad guys will be willing to do it themselves—and snare a Full House at your expense.
Other members of the RST group involved in the development of the gambling exploit are: Brad Arkin, Frank Hill, Scott Marks, and TJ Walls. The Software Security Group is led by Dr. Gary McGraw.