Not a Game of Random() Chance

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 ⁶⁸ (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 ³²−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