[Cryptography] Bridge hand record generator cracked

Mon Sep 12 15:05:29 EDT 2016

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 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160912/87e8fac7/attachment.html>