Hacking Bridge-Hand Generation Software

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 …

Tags: cheating, cryptography, games, hacking

Posted on September 16, 2016 at 12:12 PM • 10 Comments

Comments

My Info • September 16, 2016 12:52 PM

Ok, first of all, I know nothing about cards, although I do think Bruce’s S olitaire cipher is extremely cool, (and the “bias” discovered in it is probably irrelevant for actual hand use,) so I’m going to sound like an idiot here, but for as long as I can remember there has been a bridge column in the newspaper. (That’s the key to the S olitaire cipher, by the way…)

But as far as I am concerned, once a card game becomes so “professional” that the house has to keep all hands of all players under surveillance, the game is so stacked that I’m just not even interested in getting started.

Maybe I’ll just have to buy a deck of cards at the dollar store and figure out that S olitaire cipher. I wouldn’t put any more money than that in a card game anyway lol.

John Macdonald • September 16, 2016 2:34 PM

@My Info – the record of the hands is not for security but to make a bridge tournament be fair. Every hand is played multiple times, and a team’s score is not based on what specific cards they happen to be dealt, but how their result compares to that of other peope who had the same cards. They have been doing this for many decades, going back to before they used computers to generate the hands. The security involved is in keeping the generated hand records secret until they are actually seen at the table – obviously ACBL is using poor technique for its “random” hand generation.

Interestingly, when computer-dealt hands were first used in the late 60s and early 70s, people complained about the more extreme distribution of cards that were happening. The problem was that human dealt hands were often not shuffled well enough – so, the deck would have runs of adjacent cards of the same suit more often that chance: that means that each player gets a nore equal number of cards in each suit and less cases of short suits than they should.

Steinar H. Gunderson • September 17, 2016 11:10 AM

I wonder, why does it need three full rounds? The state of the PRNG seems to be 48 bits, and a sorted bridge deal contains a bit over 95 bits of information (the number of possible deals should be 52C13 * 39C13 * 26C13 * 13C13), so one would believe one should be plenty, especially since the program appears to work by brute force.

My Info • September 17, 2016 11:59 AM

@ John Macdonald

I refuse to play cards on the Sabbath day on this forum, but nevertheless I will address your points as well as I can.

First, I do understand that bridge hands have been analyzed in great deal for many years. I read the newspaper as well as anyone else. I don’t buy the argument that the element of chance can be completely removed from the game; but to the extent it can, the situation is like the analysis of chess positions, where a vast library of opening moves has been developed over the years. That kind of situation is still enough to take the fun out of the game for me.

Second, you left a real jaw-dropper and a deal-breaker for me:

The security involved is in keeping the generated hand records secret until they are actually seen at the table …

That is not going to happen in a card game when money is involved.

Third, hand shuffling: I am a novice at this but I notice that people have varying skill levels at shuffling a deck of cards by hand. Theoretically it should be a matter of the number of times the deck of cards is cut and riffled back together before it is considered adequately mixed. Let’s say an absolute minimum of eight to ensure the possibility of an adequate separation of any two cards that were adjacent in the deck before the shuffle. Some people like me are very clumsy at this, but some people have so much skill that their “shuffle” is completely deterministic and they actually know where every card is throughout the entire operation.

Fourth, computer shuffling: these computers are accessible over some kind of network and money is involved. And the house doesn’t want to deal any hands it doesn’t know how to play to its advantage.

Fifth, the surveillance: actually my comment was more apropos poker or other games where a real “house” has both a stake in the game at the table and total surveillance of all hands, whereas the rules of the game would require the players to keep their hands secret from each other. This is not unlike the Goldman-Sachs moral quandary of managing conflicts of interest between its private investment and corporate banking divisions.

Jim H • September 17, 2016 8:57 PM

@ My Info,

Not a big fan of Vegas, are ya? 🙂

Interesting analogies…

My Info • September 18, 2016 11:54 AM

@Jim H

Nah, last time I was in Vegas, someone in a white car with dark shaded windows tried to run me over in a parking garage. No — wait, that was the previous time — last time, I just bought a tank of gas and rolled right on through till I was clear out of the county (although I might’ve pulled over and slept some somewhere but a rattlesnake trying to get in my car woke me up) — I don’t think I even wanted to buy anything to eat or drink there.

TomTrottier • September 19, 2016 1:47 AM

To avoid cheating, big ACBL tourneys state “Contestants are not permitted to be in possession of any electronic Communication devices while they are competing.”

WhiskersInMenlo • September 20, 2016 11:44 AM

This is a good example of responsible bug reporting.
Once discovered the software blunders were fixed and
after the revision was distributed was the flaw disclosed
to a wider community.

Competitive contract bridge is a big deal for those that
are into it. This report has a number of lessons for
any programmer or manager of software.

Anon • September 24, 2016 4:21 AM

@TomTrottier: “electronic”. Good – here’s a piece of paper and a pen…

Alan • September 25, 2016 1:59 AM

@Steinar, after reading the email thread linked in the original post, I imagine that the hand generation program is something like this:

deck = [AS, KS, QS, ..., 2S, AH, KH, ... 2H, AD, KD, ..., 2D, AC, ..., 2C]
# Do a Fisher-Yates shuffle.
for i in range(52):
    j = random(52 - i)  # Insecure PRNG: linear congruential generator
    swap(deck[i], deck[i + j])
north_hand = sort(deck[0:13])
east_hand = sort(deck[13:26])
south_hand = sort(deck[26:39])
west_hand = sort(deck[39:52])

By sorting the cards (by suit, then by rank within each suit), it’s tricky to recover the order that the cards were dealt. Because of this, although each hand has a touch over 95 bits of information, it’s tricky to go from that back to the 48 bits that the PRNG was seeded with. I haven’t thought this all the way through, but I suspect that’s why just looking at 48 bits of output isn’t enough to find the seed.

Schneier on Security

Hacking Bridge-Hand Generation Software

Comments

Leave a comment Cancel reply