[Cryptography] Real-world crypto/PRNG problem: Bridge

Christian Huitema huitema at huitema.net
Mon Aug 22 13:34:34 EDT 2016


48 bits of state is obviously not enough for generating decks of bridge.

Given a 52 card deck, there are about 5.36E28 possible decks, 6.35E11 possible hands, and 5.16E21 possible pairs of hands. This implies that each deck can reveal more than 95 bits of information. So, clearly, one can use a deck as an oracle to guess the 48 bits of state of their PNRG. A pair of hands, such as the player and the dummy, reveals 72 bits of information, and that too is enough to get an oracle for the 48 bits of state of the PNRG. 

When playing bridge, a player only sees his own hand during the bidding phase, but when the bidding concludes, the hand of the highest bidder's partner is displayed on the table, becoming the "dummy". So, we can have a situation where when the game play begins, a player can look at his own hand and at the dummy, use a powerful computer, retrieve the state of the PNRG, and accurately predict the hands of the two other players. 

Once the PNRG stat has been predicted once, just looking at one hand is enough to re-synchronize the state the PNRG and predict the deck.

If they want to generate 72000 hands, they need at least 112 bits of state. 

-- Christian Huitema




> -----Original Message-----
> From: cryptography [mailto:cryptography-
> bounces+huitema=huitema.net at metzdowd.com] On Behalf Of Salz, Rich
> Sent: Monday, August 22, 2016 7:20 AM
> To: cryptography at metzdowd.com
> Cc: Willey, Richard <rwilley at akamai.com>
> Subject: [Cryptography] Real-world crypto/PRNG problem: Bridge
> 
> Forwarding for a colleague.
> 
> I have a (semi) practical question for the cryptographers in the house.
> 
> The American Contract Bridge League is following some god-awful practices in
> (electronically) generating the hands that are being used for major
> tournaments.
> 
> 1. They are not using cryptographically secure pseudo random number
> generators
> 2. They are using the same seed to generate enormous numbers of sets of
> hands (76,000) at a time
> 3. Hand records are public after the fact, so folks get to see the output of the
> process
> 
> The random number generator itself only generates 2^48 bits so a brute force
> attack seems pretty simple, however, this presumes that I have the code to
> turn output from the PRNG --> hands.
> 
> Assume for the moment that I didn't have this information. Rather, all that I
> have is a (number of) sets of ordered output from the hand generator. How
> difficult do folks think it would be to be able to crack the dealing program itself?
> (I can think of some potential implementations that would be neigh impossible.
> For example, if each deal were to map to a unique integer with a random
> assignment between integers and deals you'd probably need to know the
> complete mapping to figure anything out. However, the actual program was
> written decades back and almost certainly uses some kind of deterministic
> process)
> 
> Any ballpark estimates how difficult this would be to crack?
> 
> Here is a description of the PRNG (I believe that this is a "linear congruential
> generator" and is not considered to be cryptographically secure)
> 
> The random number generator uses the linear congruential algorithm and 48-
> bit integer arithmetic. This will generate 2 to the 47th power different numbers
> before repeating without any outside influence (140,737,488,355,328
> numbers).
> 
> Outside influence occurs in the form of manually dealt hands, starting seed
> numbers, time of day, etc., to make the number of numbers virtually infinite,
> and to guarantee that the same hand will not be repeated. Ninety-six bits take
> part in the operation with the high 48 bits acting as the overflow.
> 
> The operation works as follows: The hand record set number is used as the
> starting seed. This seed is multiplied by day of the month, current minute,
> current hour, current second, current day of week and current hundredth of
> second. This number is then multiplied by a large prime number (5DEECE66D in
> hexadecimal). Thirteen is then added to this. The lower 48 bits is then saved
> and used as the seed to generate the next random number. The overflow (48
> high bits) is then doubled and multiplied by the range requested (1 - 52) and the
> overflow from this is used as the random number.
> 
> And here is some additional snark that that ACBL's tech guy threw in for good
> measure
> 
> "The computer used to run the ACBL hand record generator is a stand alone
> desktop computer that is not connected to any network. Since Jim's retirement
> in May, I have been responsible for maintaining our stock of electronic hand
> records used by our Tournament Directors.
> 
> When we need additional hand records, we generate two thousand sets at a
> time (72,000 deals). The seed deal is manually entered at the beginning of the
> process, and is not part of any set subsequently produced. Sets are never
> reused, and the number of the set is not released publicly until after play. The
> date and time when the hand record was prepared (we keep a five thousand set
> buffer) does not leave ACBL Headquarters.
> 
> With so many of the variables involved in the hand record set creation process
> kept protected and secure, I doubt anyone will be cracking the security in
> sufficient time to make use of the data they develop."
> --
> Senior Architect, Akamai Technologies
> IM: richsalz at jabber.at Twitter: RichSalz
> 
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography



More information about the cryptography mailing list