Internet Gambling Exploit

[gem () RSTCORP COM (Gary McGraw)]

Online Gambling Software Flaw

Playing poker is risky by nature, but playing online poker for real
money may be more of a gamble than you ever expected. The Software
Security Group at Reliable Software Technologies (www.rstcorp.com) has
discovered a serious flaw in the implementation of Texas Hold 'em Poker
that is distributed by ASF Software, Inc. (www.asfgames.com).  We were
able to develop a program that exploits this flaw and is capable of
determining the exact ordering of every card in a shuffled deck; this
computation can be performed in real-time, during the playing of an
actual poker game.  This exploit enables someone to know every card that
each player has been dealt and what cards will be coming up during the
rest of the hand.  Given this information, even the weakest of poker
players should know when to hold'em, and when to fold'em.

Unlike most casino games, poker is played against other players, not
against the house.  This means that when someone is cheating at poker,
innocent people are hurt by the cheater's unscrupulous actions. ASF
Software has been notified of the flaw in their system and has taken
corrective actions.  The exploit that Reliable Software Technologies
developed no longer functions, however the potential for people to take
advantage of flaws in online gambling software remains.

The flaw existed in the algorithm used to produce a shuffled deck of
cards before each round of play.  Ironically, the code was publicly
displayed at www.planetpoker.com/ppfaq.htm with the idea of showing how
fair the game is to interested players (the page has since been taken
down).  The algorithm 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,
however they are generated in a completely deterministic manner.  This
means that given a particular starting point (the random number
generator's "seed") the sequence of numbers generated will follow an
easily calculated pattern.

The shuffling algorithm used in this software always started with an
ordered deck of cards, and then generated a sequence of random numbers
that were used to re-order the deck.  The seed for a 32-bit random
number generator must be a 32-bit number, meaning that there are just
over 4 billion possible seeds.  This constrains the algorithm to being
able to produce only slightly more that 4 billion possible decks of
cards; a number much smaller than the 52 factorial (52 * 51 * 50 * ...
1) combinations possible in a real deck of cards. The resulting number
is close to 2^225.

To make matters worse, the algorithm chose the seed for the random
number generator using the Pascal function Randomize().  The Randomize()
function chose a seed based on the number of milliseconds since
midnight.  Since there are only 86,400,000 milliseconds in a day, and
this number was being used as the seed for the random number generator,
the number of possible decks was now reduced to 86,400,000.

By synchronizing our program with the system clock on the server
generating the pseudo-random number, we were able to further reduce the
number of possible combinations down a number on the order of 200,000
possibilities.  Searching through this set of shuffles is trivial and
can be done on a PC in real time.

The exploit that RST developed required that five cards from the deck
were known, and the rest of the deck could then be deduced.  In Texas
hold'em poker, this meant that the program took as input the two cards
that a player is dealt, plus the first three community cards that are
dealt face up (called the flop).  These five cards are known after the
first of four rounds of betting.

The program then generated shuffled decks of cards until it found a deck
that contained these five cards in the proper positions.  Since the
Randomize() function is based on the server's system time, it was not
very difficult to guess a starting seed with a fair degree of accuracy.
After finding a correct seed once, it is then possible to synchronize
the exploit program with the server to within a few seconds.  This
synchronization enables the exploit program to accurately guess the seed
being used by the random number generator, and to identify the deck of
cards being used during all futureystem user must
be convinced that such risks have been mitigated.

At Reliable Software Technologies, our mission in the Software Security
Group is to stamp out insecure code before it is placed in service.
Members of the group involved with the Gambling exploit are: Brad Arkin,
Frank Hill, Scott Marks, Matt Schmid, and TJ Walls.  The Software
Security Group is led by Dr.Gary McGraw.

Gary McGraw and Matt Schmid
Reliable Software Technologies
http://www.rstcorp.com
{gem,mschmid}@rstcorp.com