Join Bridge Winners
Cracking ACBL hand records revisited

I have a copy of the code that cracks ACBL hand records so was curious on how fast I could make it.

I rented two machines on the Amazon Computing Cloud (only two because the results came out faster than I could keep up).

The next entries show the elapsed time to find the random 2^48 seeds used at the Charlotte Regional in October using these two computers. The format of the hand record is MMDDHHSS (the ACBL hand records are at http://live.acbl.org/handrecords/R1610056/MMDDHHSS - replace MMDDHHSS with the value below), followed by the first 4 hexadecimal digits of the 48 bit seed and the number of seconds it took to find the seed on these two computers:

10241300 - 0x7e15 - 15 seconds

10241900 - 0x7f59 - 19 seconds

10250900 - 0x9c85 - 46 seconds

10251300 - 0x6829 - 48 seconds

10251900 - 0x5401 - 53 seconds

10260900 - 0x8178 - 39 seconds

10261300 - 0xa608 - 16 seconds

10261900 - 0x52bf - 22 seconds

10270900 - 0xfcfe - 38 seconds

10271300 - 0xb871 - 30 seconds

10271900 - 0x7bac - 40 seconds

10280900 - 0xeb2f - 45 seconds

10281300 - 0xed85 - 33 seconds

10281900 - 0x3e3a - 39 seconds

10290900 - 0x6beb - 51 seconds

10291300 - 0x3b24 - 46 seconds

10291900 - 0xfeed - 9 seconds

Clearly this is a lot quicker (~ 2500x) than the ACBL claim of "an hour on 50 computers". An average of ~ 36 seconds for two computers - 72 seconds for 1 computer.

For any given hand record set, using one computer on the Amazon cloud, we can find a key in a maximum of 16 minutes. Using two computers, this drops to 8 minutes etc. The average time will be half the maximum time. In addition to the cryptography implementations errors found by someone else, I found an additional cryptography implementation error that reduced the search space even further (this makes at least three implementation errors). I also made some performance enhancements to the original code for running on the cloud. Using two computers, this was the elapsed time for the brute force crack of some of the hand records:

10270900 - 247 seconds

10271300 - 189 seconds

10271900 - 277 seconds

Once we had a sufficient number of hands from a tournament, it was possible to do some additional crypt-analysis on the shuffled hand_0 which acts as the original seed for the hand records for multiple tournaments. Given that crypt-analysis it was possible to provide some feedback to the original algorithms to reduce the search space even more and to be able to crack hand records in under a minute using two computers. It appears that this may apply to a set of hands for a tournament (or more). More work on this crypt-analysis is needed to verify that this will work with other tournaments.

The number of seeds is 2^48=281,474,976,710,656 (281 trillion). The cracking algorithm can process on a single rentable machine almost 2 trillion keys/second (with prior knowledge of other hand record seeds from the tournament) or 290 billion keys/second with no prior knowledge

The process is

1. Perform cryptanalysis on hand_1, hand_2 to reduce the search space. This is now automated.

1b. Incorporate additional information from tournament if known (makes it ~ 8 times faster) to reduce the key space further.

2. Brute force the key for hand_1 to hand_2 within a reduced key space.

3. Given a key for hand_1, hand_2, it is trivial (< 15 seconds on a simple computer) to work out the key from hand_2 to hand_3.

4. Provide hand_1 and the keys for hand_1->hand_2 and hand_2 -> hand_3 to generate the remaining hands.

The average computing cost to find the first key for a general hand record set is under $2. Maximum cost is under $4.

If seeds from other events in the tournament are known, the average cost drops to under 30c.

The goal was to see what was needed to crack a key in under 15 minutes - about the time between rounds in a pairs event. The answer is one computer and an average of $2. Probably within the budget of most players.

25 Comments
Getting Comments... loading...
.

Bottom Home Top