Join Bridge Winners
ACBL and USBF hand generators are demonstrably insecure

A little under a month ago, I kicked off a couple threads here on Bridgewinners discussing the possibility that someone might be able to crack the hand generation program that both the ACBL and the WBF are using.  I also started some discussions on the topic with some the cryptographers here at work.  In turn, some of them posted to one of the cryptography groups.

Roughly three weeks later, there is a operation program available to crack ACBL hand records.

  • Given three consecutive boards, all the remaining boards for that session can be determined.
  • The program can be easily parallelized.  This analysis can be finished while sessions are still running
this would permit the following type of attack:
  • A confederate watch boards 1-3 of the USBF team trials on vugraph
  • The confederate uses Amazon web services to crack all the rest of the boards for that session
  • The confederate texts the hands to a players smart phone
  • The player hits the head, whips out his smart phone, and ...
Here's three additional points to consider
  1. It took roughly three weeks for someone to go from an original idea to an operational program.  The ACBL has been using this program for decades
  2. There's a lot of folks who get paid an awful lot of money to compete in events like the team trials, the Spingold, the Vanderbilt, etc.

The European's use a program called "Big Deal" to securely generate hands.  Big Deal was specifically designed to be proof against this sort of attack.

Yesterday, I received a communication from Jan Martel indicating that the ACBL will be shifting over to use Big Deal.  They are commiting to do so by the Spring and hope to do so in time for the major events this fall.  Given the source, I would not be surprised to discover that the USBF will be doing the same.

For anyone who cares, here is the post announcing the crack. http://www.metzdowd.com/pipermail/cryptography/2016-September/030231.html

I have included the text here as well

________________

On Monday August 22, 2016 there was a post on the Cryptography mailing list (see http://www.metzdowd.com/pipermail/cryptography/2016-August/029965.html) about the American Contract Bridge League (ACBL) encryption algorithm used to generate hand records for its tournaments. This same algorithm is used by the Canadian Bridge Federation (CBF) and the United States Bridge Federation (USBF).

This Bridge algorithm has been cracked.

Earlier this month (September 2016) I was shown code (not written by me) that successfully performs a brute force search on the 2^48 key space. It has taken some time to verify this claim, along with checking which organisations are affected.

The crack requires three consecutive hands. Once you have a key from one hand to the next, it takes a few seconds to find the key from the second to the third. Given both keys, one can find out all the remaining hands in the set.

As a test, I selected hands from the last National tournament of the American Contract Bridge League (ACBL), the Canadian Bridge Federation (CBF) and from the recent United States Bridge Federation (USBF) Mixed Pairs Championship. In all cases, it is possible, given three consecutive hands, to reasonably quickly find keys which could be verified by printing the remaining hands and comparing to the hands on the Internet.

As a final test, I selected hands from a recently concluded ACBL tournament. I am currently in Poland for the Bridge World Championship. The ACBL event was played on Saturday, September 10, 2016. The complete hand record was cracked in under 2 hours.

The code takes 50 hours to run on a single general purpose computer. The published ACBL algorithm makes it open for parallel processing. 50 computers would find the key within an hour. A key will be found, on average, in half the time.

Bridge events are typically either pair (team of 2) events, or team (team of 6, but only 4 playing at any time) events.

For pair events, a player would need to excuse themselves to the toilet, upload 3 hands, and come back later for all remaining hands. Given a typical pairs movement of two boards/round, this will work if sitting North/South. East/West will typically need to have played just over half the boards before they have 3 consecutive boards before they have sufficient data for a crack.

For high level team events, it is common to field a team of 6, with two players sitting out. The events in question are normally shown live on the Internet so you have immediate access to hand records as they are played. For example, the recent USBF Mixed Teams was 4 quarters of 15 boards. After the first quarter - typically about 2 hours long - the team can substitute players. The hand records for the first two quarters of the last USBF trials are at http://usbf.org/docs/vugraphs/MUSBC2016/hands/MUSBC2016_F_Q1&2.PDF. These hands have been cracked. The same key was used for each quarter within a half. If you have the key for the first quarter, you can generate the hands for the second quarter. A team would have about 90 minutes after seeing the first three hands on the Internet to crack the hands. The pair that substitutes in would have full knowledge of the hands in the quarter they are about to play.

I had speculated it would take about 1-2 weeks to write code to do the crack. The author(s) did it in less time than that. One must therefore assume that there are probably other cracks out there, but not public. There is some evidence (sorry, can't reveal - wish I could!) that some private crack-code already existed and has been used in tournaments.

Responsible disclosure: I have waited to post these details until I was certain that the various organisations have had time to prepare to change their procedures.

I met with the USBF President today. On my suggestion he had meetings last week with representatives from the World Bridge Federation (WBF) who use a more secure program - Big Deal. USBF will implement Big Deal and has plenty of time to do this. I don't have any CBF contacts, if they are in Wroclaw, ask them to contact me and I'll introduce them to the people they need to meet.

For ACBL, they already have a replacement ready in house. The ACBLscore+ replacement for ACBLscore contains code that uses the industry standard Big Deal and not the home-grown ACBL solution. To help ACBL with its transition, I created a video for them, https://www.youtube.com/watch?v=i2nxCzIniPc. It should take less than an hour to get the new system up and running from the original source code. It is possible to automate the task so you don't have to use manual typing/clicks. If I have enough time I will create the script for ACBL, but this is very simple code so they should be able to do this by themselves.

I have not asked the author(s) if it is possible to generate hand records for events not played yet, i.e. to use the hand record for one event to predict the hand records for future sessions.

This is a text book case of a failure to understand how to write cryptographic code which opened up the implementation of dealing cards to some simple cryptanalysis.

After all the various organisations have stopped using the broken algorithm, I'll see what details I can make public. At the moment I have the metaphoric ACBL 'keys to the kingdom' but do not plan to use them. I'd like to thank those that wrote the code; at the moment they wish to remain anonymous. Also to thank them for choosing to make this information public, rather than profit from it.

Nicolas Hammond

185 Comments
Getting Comments... loading...
.

Bottom Home Top