What I did on my summer vacation

[hrothgar]

Folks might find the following of interest (Please note, I was not the one who operationalized the crack, however, did the the initial leg work to run this all down. Then, as is oft the case, having satisfied myself that this was pretty easy, pointed some other folks in the right direction and sat back and watched the fireworks)

 

Begin quote

___________

 

 

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

[helene_t]

You do realize that the response to this will be to revert to hand shuffling? :)

[johnu]

You do realize that the response to this will be to revert to hand shuffling? :)

 

No need to change in the ACBL for most knockout and Swiss events. It requires too much technology to have computer dealt hands in those events :rolleyes:

[aawk]

If you only can win in bridge by cheating you are no bridge player but that aside no need to make it easy for them.

 

If you need just 3 boards to find out what the rest of the set would be it is simple to counter this problem.

 

After a board is dealed the random numbers sequance used to shuffel the deck has to chance.

 

So add to the code a extra line that wil do this and the problem is solved.

 

For example use the clock as a extra random generator.

 

random number x time = random number used to shuffle

 

457643 x 112234 (the time was 11 : 22 : 34) = ??

 

The cheaters now also need to know the exact time each board was shuffeld. If they can crack this code (will be hard) it will take a lot of extra time for a computer to find out what the random numbers used to shuffle are.

[msjennifer]

A very nice presentation on an equally interesting subject.Sir,I envy you.You must have extremely enjoyed your vacation.Wish you go on more vacations like this one and more frequently..

[Vampyr]

No need to change in the ACBL for most knockout and Swiss events. It requires too much technology to have computer dealt hands in those events :rolleyes:

 

True, but oddly this is not the case in very many other countries.

[hrothgar]

If you only can win in bridge by cheating you are no bridge player but that aside no need to make it easy for them.

 

If you need just 3 boards to find out what the rest of the set would be it is simple to counter this problem.

 

After a board is dealed the random numbers sequance used to shuffel the deck has to chance.

 

So add to the code a extra line that wil do this and the problem is solved.

 

For example use the clock as a extra random generator.

 

random number x time = random number used to shuffle

 

457643 x 112234 (the time was 11 : 22 : 34) = ??

 

The cheaters now also need to know the exact time each board was shuffeld. If they can crack this code (will be hard) it will take a lot of extra time for a computer to find out what the random numbers used to shuffle are.

 

Couple silly questions:

 

How much variance is there in the amount of time that it takes a computer to deal hand?

Why might this be important?

 

<As a rule, seed selection for pseudo random number generators is more complicated than it might seem. In general, it's a much better practice to use a prng with the properties that you want than constantly reseeding a bad prng hoping that this will make it better>

[zillahandp]

Well done food for thought. I think i have a solution but not telling obviously.

[hrothgar]

Well done food for thought. I think i have a solution but not telling obviously.

 

I have a solution as well.

Switch to Big Deal.

[aawk]

Couple silly questions:

 

How much variance is there in the amount of time that it takes a computer to deal hand?

Why might this be important?

 

<As a rule, seed selection for pseudo random number generators is more complicated than it might seem. In general, it's a much better practice to use a prng with the properties that you want than constantly reseeding a bad prng hoping that this will make it better>

 

 

Ok here another try.

 

If a set for example of 16 boards is shuffeld in less then a second shuffel 8 sets and pick 2 boards of each set. Will that solve the problem ?

[msjennifer]

Ok here another try.

 

If a set for example of 16 boards is shuffeld in less then a second shuffel 8 sets and pick 2 boards of each set. Will that solve the problem ?

Personally,I feel that this solution shall be convenient as well as successful.

[hrothgar]

Ok here another try.

 

If a set for example of 16 boards is shuffeld in less then a second shuffel 8 sets and pick 2 boards of each set. Will that solve the problem ?

 

No

 

You are adding to the number of steps, but not adding new sources of entropy

The operations that you are describing are just as easy in both directions

[shyams]

Ok here another try.

 

If a set for example of 16 boards is shuffeld in less then a second shuffel 8 sets and pick 2 boards of each set. Will that solve the problem ?

Wouldn't it be easier to upgrade the dealing software so that it is no longer subject to brute force attacks?

 

There are readily available solutions on the market. Instead of contorting one's process into a variety of shapes, it may be best to abandon it and replace with a stronger process.

[helene_t]

Alternatively, make the blocks sufficiently small that nobody will be playing a board after having had time to crack the code using a different board from the same block. A block size of 8 boards or so would probably be safe.

[Rain]

No need to change in the ACBL for most knockout and Swiss events. It requires too much technology to have computer dealt hands in those events :rolleyes:

 

 

Spingold early round, GNT early round(s), all hand shuffled too!

 

So ACBL is changing to Big Deal too right?

[hrothgar]

So ACBL is changing to Big Deal too right?

 

Yes

[aawk]

No

 

You are adding to the number of steps, but not adding new sources of entropy

The operations that you are describing are just as easy in both directions

 

 

If it is not possible to randomnize a random generator we cannot solve the problem and have to accept it is possible to cheat.

[mycroft]

functional processes do not increase entropy. Using the same PRNG to make decisions in a functional process does not increase entropy unless reseeded.

 

Only real randomness does anything but improve obscurity, and obscurity is not security.

 

This is an insanely difficult thing for non computer security people to understand (and a moderately difficult thing for computer security people to understand, viz all the "stupid mistakes" in the breaches we keep hearing about), because for poor humans, making a problem 30 times harder tends to move it from doable to impossible. If the thing can be cracked by one computer in minutes, and is strongly parallelisable, making that problem 30 times harder could be as little as doubling the time (and remember that on average, one of these kinds of problems takes half as long as worst case to solve, because there's a brute force component) and adding a (one-time) few thousand bucks to the tool's hardware cost. 2^30 times harder, now...

 

Note that "true randomness" is also very difficult for non-computer-security people to understand. And the reason we still use PRNGs is not that true randomness is impossible or it's too expensive, but because it's usually too slow. But 36x96 bits is nothing - that's one moderately secure SSH key. 2048x2048 needed per second; now we need to get "close enough".

 

With true randomness being available for significantly less than the profit from a single session of a moderately sized sectional, there is absolutely zero reason to do anything else than "use true randomness".

 

tl;dr: "Why can't they..." "Because the real answer is cheaper, and actually secure."

[hrothgar]

If it is not possible to randomnize a random generator we cannot solve the problem and have to accept it is possible to cheat.

 

Comment the first: It is possible to get real entropy. You just don't seem to understand how to do so.

 

Comment the second: You seem to assume that security is binary. "If something is not perfectly secure then it is possible to cheat."

 

While this notion might be true, it is not interesting, nor is it how security professionals look at the world.

 

Take a look at how safes are rated.

No one sells a safe that claims to be perfectly secure. Rather, people sell safes that have ratings.

 

"An adversary who has access to tools of type foo (grinders, hammers, drills) should need at least 90 minutes to break through this safe."

"An adversary who has access to tools of type bar (a thermal lance, high explosives) should need at least 10 minutes to break through this safe."

 

The same goes for trying to secure a dealing program.

 

We don't need to make th system perfectly secure.

Rather, we need to make it difficult enough to break that the cost of cracking the system in a useful length of time would exceed the value of the benefits.

[aawk]

Comment the first: It is possible to get real entropy. You just don't seem to understand how to do so.

 

Comment the second: You seem to assume that security is binary. "If something is not perfectly secure then it is possible to cheat."

 

While this notion might be true, it is not interesting, nor is it how security professionals look at the world.

 

Take a look at how safes are rated.

No one sells a safe that claims to be perfectly secure. Rather, people sell safes that have ratings.

 

"An adversary who has access to tools of type foo (grinders, hammers, drills) should need at least 90 minutes to break through this safe."

"An adversary who has access to tools of type bar (a thermal lance, high explosives) should need at least 10 minutes to break through this safe."

 

The same goes for trying to secure a dealing program.

 

We don't need to make th system perfectly secure.

Rather, we need to make it difficult enough to break that the cost of cracking the system in a useful length of time would exceed the value of the benefits.

 

 

 

 

If a safe cracker cannot open a safe he will take it home where he or she has more time. So making it harder to crack the safe is no solution because the can download the shuffling program and crack all the barriers you put in place at home.

 

You said the need at least 3 boards to crack the code so if you restart the random generater after 2 boards are shuffled the problem must be solved.

 

If this does not solve the problem it means that the random generator used is not realy random and that is the problem which has to be fixed.

[barmar]

If a safe cracker cannot open a safe he will take it home where he or she has more time. So making it harder to crack the safe is no solution because the can download the shuffling program and crack all the barriers you put in place at home.

He has to be able to move the safe.

 

Similarly, if you can crack the hand records at home, that's not much help because the event where those hands are being used will be over. Consider the scenario Nicholas described: you go to the restroom after the first round, somehow manage to send all 3 hands (with every spot card correctly specified) to your computer at home in the minute or so you have between rounds, then go back to the restroom an hour later to download the hand records for the remaining boards.

 

I think this crack is more theoretical than practical. On the other hand, it's so easy for ACBL to switch to Big Deal, there's no reason not to do it, to remove all concerns.

[shyams]

Consider the scenario Nicholas described: you go to the restroom after the first round, somehow manage to send all 3 hands (with every spot card correctly specified) to your computer at home in the minute or so you have between rounds, then go back to the restroom an hour later to download the hand records for the remaining boards.

 

There was a practical & quite scary application to Nicholas's scenario which he discovered.

 

USBF tournaments involve 4, 6 or 8 sessions of 15 boards each -- these are numbered 1-30. If the sit-out pair inputs boards 1-3 of session 1 and uses the code to crack it, they will know all remaining boards not only of session 1 (boards 1-15) but also of session 2 (16-30)! This can be done every time (take boards 1-3 of session 3 to get full knowledge of every card in session 4).

 

There may have been other scenarios where one set of boards spills over two or more sessions.

[Vampyr]

Can someone explain to me exactly how boards can be predicted? If you have the seed, how exactly does one board relate to the next?

[hrothgar]

He has to be able to move the safe.

 

Similarly, if you can crack the hand records at home, that's not much help because the event where those hands are being used will be over. Consider the scenario Nicholas described: you go to the restroom after the first round, somehow manage to send all 3 hands (with every spot card correctly specified) to your computer at home in the minute or so you have between rounds, then go back to the restroom an hour later to download the hand records for the remaining boards.

 

I think this crack is more theoretical than practical. On the other hand, it's so easy for ACBL to switch to Big Deal, there's no reason not to do it, to remove all concerns.

 

Barry, the problem is trivial to parallelize.

 

If I am willing to spend enough on AWS, I can crack the boards in a matter of minutes.

 

In turn, this means that when I go to the bathroom after playing board 4 in the USBF team trials, I can get all the rest of the boards for this round

[hrothgar]

Can someone explain to me exactly how boards can be predicted? If you have the seed, how exactly does one board relate to the next?

 

There are at least two ways to implement this attack.

 

First of all, given modern computer resources, the search space is relative small.

 

The simplest attack is for me to enumerate the output of the hand generator for every possible seed.

I build a rainbow table and we're off to the races.

 

A slightly more complicated attack is to take advantage of the flawed nature of the LCG being used to generate random numbers

 

"LCGs should not be used for applications where high-quality randomness is critical. For example, it is not suitable for a Monte Carlo simulation because of the serial correlation (among other things). They also must not be used for cryptographic applications; see cryptographically secure pseudo-random number generator for more suitable generators. If a linear congruential generator is seeded with a character and then iterated once, the result is a simple classical cipher called an affine cipher; this cipher is easily broken by standard frequency analysis.

 

LCGs tend to exhibit some severe defects. For instance, if an LCG is used to choose points in an n-dimensional space, the points will lie on, at most, (n!m)1/n hyperplanes (Marsaglia's Theorem, developed by George Marsaglia). This is due to serial correlation between successive values of the sequence Xn. The spectral test, which is a simple test of an LCG's quality, is based on this fact."