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

[Jerry Leichter]

[A couple of posts factoring the multiplier]
The quality of a LCG (for appropriate use, which this is not) does *not* require a prime multiplier.  (That was the advice many, many years ago before anyone really did a proper analysis.  There are bad primes and good non-primes.)

The "48 bit state" looked familiar, and indeed a table at https://en.wikipedia.org/wiki/Linear_congruential_generator confirms that (with the correction of an additive constant of 11 rather than 13) this is exactly the generator used in Posix and glibc rand48 (some variants of each, actually) and Java's java.util.Random.  However, these generators return bits 47-16 of the full product before reducing the next state mod 2^48 - important since the bottom bits of any LCG are the "least random".  The English description of what the bridge dealing program does isn't clear enough to me to understand if it's taking this essential step.

Note that these generators (as specified in Java and Posix) have been analyzed are among the best for LCG's for the given modulus - *which isn't saying much*, since *no* LCG is considered good for serious statistical/simulation work any more.

As many have commented, if you want any degree of security and fairness in such a generator, you need much more state.  For the purpose at hand, the standardized MT19937 Mersenne Twister would be a reasonable choice:  Period 2^19937-1, 2.5KB of internal state, good theoretical properties, passes a wide variety of statistical tests - and implementations are widely available.  Considered "slow" by modern standards, but for this usage, it hardly matters.

Generating an initial state this large is tricky.  Given the use case, shuffling a deck of cards and typing in the sequence of cards should be sufficient, and then adding some checkable but unpredictable data - e.g., the first paragraph of the first article on some pre-chosen Web page.  (There are some issues if this initializes only a fraction of the bits in the state, as states with many initial 0 bits are problematic for some number of cycles; the literature discusses the need to run the generator a bit to mix the state).  Using a Web page assumes Web access, but you could instead use the local newspaper, saving it for a later cross-check.

Or go fully automated and use /dev/rand to determine the initial state.

However the initial state is determined, it could be recorded, with its SHA256 checksum published at the beginning of the tournament, and the full initial state published at the end.  This would allow anyone to check that the deals were fairly generated.  (These are overkill, but given that it's a program doing the work - why not?)

                                                        -- Jerry