COMMAND

    Internet Gambling

SYSTEMS AFFECTED

    Gamblers :-)

PROBLEM

    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 has
    discovered a serious flaw in the implementation of Texas Hold  'em
    Poker that is distributed by  ASF Software, Inc.  Gary  McGraw was
    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

        http://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  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.   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.

SOLUTION

    Fixed by new version.