Join Bridge Winners
ACBL and USBF hand records are (plausibly) insecure

<I wrote a more tongue in cheek version of this post yesterday which was removed from the site. Steve Weinstein suggested that, if I was truly concerned about this topic, I should write a more serious post. So, here we go…>

I believe that the system that the ACBL uses to electronically generate hands for its tournaments is plausibly insecure.

  • I believe that players can build a system that will take a hand dealt during a session as input and immediately output all of the remaining hands that will be played. 
  • The cost of implementing such a system should be small enough as to be viable for an interested party 

This statement is not just my opinion, but rather, this reflects the judgement of a number of cryptographers and security professionals who I consulted with over the past few days.

I am not the right person to implement a new secure system. With this said and done, my understanding is that the primary problem with the existing implementation is with the quality of the pseudo random number generator. The ACBL could trying to patch their existing dealer program by swapping out the linear-congruential generator that is currently being used for a different source of randomness. [I have attached one recommendation at the close of this thread]. Alternatively, I would strongly recommend standardizing on existing software used by other NBOs. My understanding is that several of them use an open source program called Big Deal that was specifically designed to address these concerns. https://sater.home.xs4all.nl/doc.html

What is the threat model?

The ACBL’s dealing program is using a type of pseudo random number generator called a linear-congruential generator (lcg). While small and relatively efficient, this prng does not have good statistical properties and “must not be used for cryptographic applications”. Not only is the lcg a poor choice of algorithm for a dealing program, the specific implementation that the ACBL is using is only able to generate a relatively small number of unique outputs. The combination enables an attack of the following form:

  1. The adversary gains access to code that maps the output from the prng a bridge deal. This code could be easily reverse engineered from a few sets of hand records. Easier yet, you could compromise the source code. 
  2. Next the adversary generates a rainbow table. This table maps bridge hands to the seed that was used to generate them. The adversary can now look at a bridge hand, instantaneously retrieve the state of the prng, and predict future hands for this session. It might be possible to predict multiple sessions. 

If a hand is on Vugraph, it becomes trivial for a compatriot to access the rainbow table. Alternatively, a player could send a text from a toilet stall or some such. I should note: I haven’t gone to the time and bother to build a working implementation. With this said and done, I would estimate that the cost to do so is somewhere between $10K and $50K. This is inexpensive enough that I believe that some players might choose to cheat. Given that this problem can be easily addressed by switching over to a different dealing program it would seem prudent to do so.

FWIW, I am attaching the comments made by Jon Callas regarding the security of the ACBL’s existing implementation. https://en.wikipedia.org/wiki/Jon_Callas

http://www.metzdowd.com/pipermail/cryptography/2016-August/029969.html

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.

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.

20 Comments
Getting Comments... loading...
.

Bottom Home Top