[Cryptography] Real-world crypto/PRNG problem: Bridge
rsalz at akamai.com
Mon Aug 22 10:20:14 EDT 2016
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
More information about the cryptography