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

[Jon Callas]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

They don't need a cryptographically secure PRNG. They do need a number of attributes that are easier obtained in a cryptographic PRNG than a lot of others.

My first advice is not to say "cryptographically secure" because that's going to frighten them off and set up their mental shields that you then have to knock down or go around. 

Then talk about goals that they pretty obviously want:

(1) They want a basic level of non-hackability. For example, it would be bad if knowing my cards I could then determine everyone else's cards in that hand. It would also be bad if knowing all 52 cards in hand N, you could then predict future hands.

(2) You want the hands to be evenly distributed at some level. Mathematically, I'm saying that you want the output to be pseudorandom, but that might be too much of a rat hole.

A linear-congruential generator fails both of those, badly, as others have stated.

LCG generators tend to generate in pairs. By that I mean that if you plot on a graph a bunch of (X,Y) pairs as points, you'll see a dark line go up the diagonal. This is bad because it means that you're creating skew in the hands. There will be clusters of cards that go together.

LCG generators can be hacked by knowing part of the output stream. It is *completely* reasonable that someone can see part of a hand and be able to tell the whole hand. It isn't even hard, go search "break linear congruential generator" and you'll find handy references complete with code to do it for you.

Moreover, as others have stated, 48 bits isn't enough. Not only is it a lot smaller than all the possible hands (and yes, that might not be strictly a requirement, but it sure would be nice to have), but it would be possible to precompute all possible hands and then just use that information to look up the hand based on a few convenient parameters like suit count and high card(s). I did a back-of-the-envelope calculation on constructing that, and it's less than a nice sports car today, in 2016. One of my parameters was that an 8TB drive costs costs $250. You can make it cheaper by using 4TB drives, or cloud storage. But more importantly, the cost of doing this is a lot less five years from now than it is today. The major point is that it's completely affordable for a cheating team to do it with each member contributing $10K-$25K. Worse, this would be a *great* Ph.D. thesis topic.

I feel I must also state that 5DEECE66D is not a large prime number, it is a only 32 bits in size which makes it not large, and it's not even prime. (Bigprimes.net can factor it in javascript.) Yeah, it's a nit and irrelevant.

The easy way to fix this is just to use /dev/random or equivalent on whatever computer they have.

If they want:

(a) A basic level of transparency. The ability to show the community your card dealing system isn't favoring anyone. 

or

(b) A basic level of reproducibility. The ability to be able to go back and say that yes, this hand was generated the right way and not tampered with. 

then /dev/random doesn't meet those goals because it will give non-reproducible results. I think some level of basic audit is a good idea, but I can accept that "we're the ACBL, you just gotta trust us" might be the way they roll. 

But if they do want those properties, there are easy fixes. My sketch is: 

* Take all the seeds they normally do: the hand record set number, date and time, and throw in something like a quote or witticism. 

* Hash them all with SHA-256 to get your first random number, which I will call R_0.

* Then for each R_{n+1} successor, hash N concatenated with all the seeds, and R_n.

I already gilded the basic lily of R_{n+1} = hash(R_n), and we could have a huge discussion of more ways to gild it.

Bottom line -- just toss out what they're doing and use /dev/random or equivalent, and you're good. The only problem you have is the auditability issue which they don't have now. They're already saying that a trusted team is fine. But as things stand, it's possible for a team to cheat by hacking the dealing system, either by hacking the generation system or just making a rainbow table of all possible hands.

	Jon



-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 3.3.0 (Build 9060)
Charset: us-ascii

wsBVAwUBV7uTgfaTaG6hZJn9AQhYLwf/T+ZVwlZVp3CszpaifxHSBe4FMHe2p7bn
1sniodbLfiaD7ESqg3yJOsS9x9r25XHegeDw7mxiXWKz0A6pxeyXnfzu23mRgs0B
zrCfWrw0Mjd3AybpAdIso8W30jI56Fb7DhqUpWJ7lhT+E+UMdQ6yojvrhtQvey7o
DBU0Bx0V/Wyf+1Nyg8mxM1IqGDDmH7SABbyW601HcdpLYlfgxCS/vpCZuzhYXkDh
Iq8KoX1fes9/EkPFvv4Ptcnw738d+SV+NFQTsIZHuwf7sU8pY6EWP/ElFwuC5KnR
BpWOopQLwBg2oEgFwc9+EMBLYiV+qc2N6jTPjyIC3WEc/nTDKfkD3g==
=Kr4z
-----END PGP SIGNATURE-----