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

[Ray Dillinger]

On 08/22/2016 07:20 AM, Salz, Rich wrote:
> 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?

A bridge hand contains more than enough information to uniquely
determine the state of the PRNG at the time of its creation.

There is a bit more additional snark than you mentioned.  First
the addition to the seed after multiplication appears to be 11
rather than 13.  Second the RNG output is being used to select
the next card from *each* of 2000 decks before going back to
the first deck, so when you see any single hand you are looking
at every 2000th output of the the PRNG rather than sequential
outputs of the PRNG.  The guy setting up the system probably
thought this made it more secure.  However, with an LCG this
is easy to solve.

The decks before shuffle are sorted in sequence ace through king
of each suit in order hearts, clubs, diamonds, spades.

I've cracked this same problem before in the context of an online
poker system that was losing money and the operator didn't
understand why - except he was only using a 32-bit seed and
the PRNG built into the MSVC compiler.

FWIW, There are a bit more than 8 x 10^67 different permutations
of a 52-card deck.  Which is to say, about 226 bits of state.
If you want fair shuffles - even remotely fair - use at least
256 bits of state for a PRNG to deal a single deck.  That will
mean there isn't enough information in any single hand to
narrow down the state of the RNG when it was dealt in any way
useful to a player.

If you want every possible set of 2000 deals, you will need
to start with a PRNG having 512kbytes of state - which is
a bit ridiculous but easy to do.  In practice one would use
a CSPRNG with 2k or 4k state - This could deal only a tiny
fraction of all possible combinations of 2000 hands, but by
any means we currently understand nobody could work out which
ones.

If you regard it as really important (on the same order as
nuclear launch codes), you'd use a TRNG such as the one
built into /dev/random on modern computer systems.  The TRNG
could deal all possible sets of 2000 hands, but on most
systems demanding 512kbytes of random bits at once would
mean it might block for a while (more than a second, less
than an hour) gathering bits from hardware sources like
internal temperature fluctuations, bus, disk, and cache
latency, turbulence inside hard drives, etc.

If the machine has been running for at least an hour since
bootup, the output of /dev/urandom ought to be indistinguishable
for any practical purpose from the output of /dev/random.

Sigh.  The more I deal with this the more I hate the word
"Random."  Trying to define it rigorously is like trying to
nail jelly to a tree and the phrasing leads people to believe
it's a property of a number rather than of a sequence.
"Entropy" in the non-physics sense is even worse.  I think
I prefer talking about "Predictability" rather than
"Randomness"  because it at least leads to the right concept
(property of a sequence) and the right questions: predictable
to whom, by what means, and with what available information?

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160822/c6a27e83/attachment.sig>