[Cryptography] Real-world crypto/PRNG problem: Bridge

[Nicolas Hammond]

My first post. I am a bridge player. I have been involved with computer 
security since 1989. I have also done some crypto work in my past - 
cryptography and cryptanalysis as a consultantfor a TLA but I do not 
claim to be an expert in the field.

1. The bridge problem was solved in 2000.

The European Bridge League (EBL) and the World Bridge Federation (WBF) 
use a program called Big Deal (https://sater.home.xs4all.nl/doc.html). 
This was released in September 2000, including the source code.

A bridge hand can be represented by 2^96 bits.

Big Deal uses a 160 bit algorithm, 64 bits are thrown away each time. 
Details are on its web site.

I have no connection with Big Deal. I recommend its use.

2. The American Contract Bridge League (ACBL) uses their own software. I 
am an ACBL member. Their dealing program was written by a recently 
retired long-time ACBL employee Jim L. Jim wrote about the algorithm in 
2011 in the monthly magazine. Jim wrote most of his code in Pascal, he 
probably wrote the dealing algorithm about 20-30 years ago. It would 
have been written to run on DOS. It is possible it has since ported to 
Windows. This is public knowledge, but is helpful background 
information.  Jim is a great guy, self taught programmer, who 
single-handedly wrote all the code that ACBL uses for scoring at 
clubs/tournaments. I have no reason to believe Jim has any background in 
cryptography.

3. Hand records are available after an event, both in printed form and 
on-line. This is the hand record from last ACBL event I played in that 
had hand records:
http://live.acbl.org/handrecords/NABC162/07281931
Ignore the date - Dec 31 1969 - that's a bug - Jim did not write the 
code to display hand records online! It was played on July 28, 2016. The 
printed form at tournaments normally include the unique set number.

4. The recent interest in ACBL hand records started on August 17, when 
someone posted on a Bridge site about Doerre/Klebanov finding a flaw in 
GnuPG's mixing functions. I doubt ACBL uses GnuPG. I posted on August 22 
that I thought it would be 1-2 weeks of work to write a cracking tool. 8 
days ago.

5. As an ACBL member, I have to be make sure I do not violate their Code 
of Disciplinary Regulations (CDR) - 
http://web2.acbl.org/documentLibrary/play/CDR.pdf. In reading this, 
decoding hand records during an event is not allowed, but doing analysis 
of hand record data after an event does appear to be not prohibited (!). 
Hand records are not copyright, I would be doing an analysis of the 
output from a program, not reverse engineering an existing program. 
However, to avoid any possible problems with the CDR, let me talk in 
hypotheticals.

6. Hypothetically, one night last week I could not fall asleep so at 
11pm I decided to look at this problem. After two hours of coding, I 
fell asleep. Hypothetically.

7. My hypothetical program, clab_crack, can, hypothetically, examine 
592,000,000 keys per second on my 3 year old laptop. The problem is to 
find a key, 2^48. A little bc:

2^48
281474976710656
. / 592000000
475464
. / 3600  # 3600 seconds in an hours
132
. / 24      # 24 hours in a day
5

So it takes about 5 days. Key checking is great for parallel processing. 
I have some older machines laying around the house so I find, 
hypothetically, that with 2 laptops, 2 servers, all 2+ years old, that 
they can, hypothetically run at 256, 592, 880, 536 million operations 
per second. I have some Raspberry Pis, but they would be slow - 4 
million/second. Pis do not like >32 bit programming. Of course, this is 
all early work, if I have a hypothetical program I would do the obvious 
code optimization. If this was serious work, I'd look at assembly etc. 
For simple stuff, I would write my hypothetical program in C. A couple 
of low end Internet servers run around 250 million ops/second. With 
little effort, I find I might have enough machines to crank around 2688 
million ops/second. Hypothetically.

2^48
281474976710656
. / 2688000000
104715
. / 3600
29

Down to about 29 hours, for equipment I have readily available.

If I did have this hypothetical program, I would probably rent some 
computing engines on the Internet. Cheap internet servers give me 
250M/second. Or I could buy some more modern CPUs that will probably 
give me 1,000M/second. My 4 year old server can theoretically process 
880M/second. Let's say I buy 500 modern computers, to give me an 
additional 500,000M/second. Probably $500/computer - don't need much: 
cpu/motherboard/network cable. Hmm. $250K. Little pricey. Perhaps I 
should look at renting computing engines on Internet. If I bought the 
computers (and some sponsors spend less than this each yeat on their 
bridge habit).

2^48
281474976710656
.  / 502688000000
559

Down to 10 minutes.

A bridge session is typically 3 hours long. Typically 24-28 boards. Any 
information on any hand that I am about to play is useful. Being able to 
know exactly what cards anyone everyone has is .... very useful.

Recently the #1, #2 players in the world - Fantoni/Nunes were banned for 
5 years because they were caught on video passing a single bit of 
information to each other approximately once every fifteen minutes.

8. If I did write this hypothetical program, there is now an interesting 
ethics question. Every other time I have found a zero day vulnerability, 
I would report it, it would be silently fixed, and no-one is any the 
wiser. These involved either OS problems, or security for bank-related 
software so reporting was important. Even though the ACBL CDR appears to 
allow for post-processing, it is possible it could be argued that even 
writing a tool to crack the code is falling foul of the CDR. So I have 
to have plausible deniability about having such a tool. In other words, 
I can never admit that I have it - if I did. Hypothetically.

9. There is a 7 day bridge tournament in Atlanta that starts later 
today. I am going, and intend to play in some events, but not any events 
that use hand records. It will be interesting to see what additional 
information is on the printed hand records as I have only looked at 
on-line hand records.

10. The United States Bridge Federation (USBF) selects teams to 
represent the US in international competition. They use hand records 
from the ACBL. Almost certainly they will stop using ACBL hand records, 
probably before their next tournament. I am not a current USBF member, 
but have been in the past and have played in their events. ACBL will be 
slower to change.

Off-topic: If you got this far, and are not already a bridge player, 
consider learning to play. If you like crypto work, there is a good 
chance you like solving problems. Every bridge hand is a series of 
problems to solve. See www.acbl.org for more details.

11. The dumbest thing any bridge player could do if they wrote such a 
tool would be to write about it. Far best to keep quiet about it and use 
it at tournaments. How would you ever get caught? There are bridge 
players now who write down every card of every player at the table for 
every hand they ever play and walk around with their notebook, so I 
would become one of those players. Go to bathroom, upload the data for 
the current event to my secure Internet server. In a few minutes I would 
have access to all the hands that have yet to be played. Assuming that 
this hypothetical program exists.

12. What could ACBL do to see if such a program exists? They could post 
parts of a hand record set on their web site, not current hands or ones 
from their current 2000 set and ask to see if anyone can break the 
hands. For example, list the first 6 boards of a set and ask if anyone 
can work out the remaining 30 boards. By making this a public 
'competition' it avoids all problems with their CDR as long as they 
state that anyone who cracks the code will not be guilty for any 
possible CDR violations. If anyone cracks the code, then ACBL know that 
they need to replace their system. If, hypothetically, I did have such a 
program, I can't tell them, because of possible CDR violation. Hmm. Of 
course, all of this is hypothetical anyway.

13. Bridge is a ~ $100M/year business in the US. ACBL does about $15-20M 
in revenue. The remainder is income to ACBL Units, ACBL Districts, 
Clubs. Anyone with the ability to generate hand records of events in 
progress would have the "keys to the kingdom". There are several bridge 
professionals who claim they make > $100K/year. Imagine what this 
hypothetical program might be worth.

14. Fortunately I am white-gloved. Have been my entire career. So if I 
did have this tool, my ethics are such that I would never use it during 
a live event nor sell it. If I win a bridge event, it will because I 
have done well, not because I have cheated. But because of the CDR, 
clab_crack is currently a mythical tool - it may, or may not, exist.

15. The most interesting part might be the cryptanalysis. I remember 
reading Jim's article 5 years ago and thinking the implementation seemed 
flawed, but did nothing at the time. Anyone with a little background in 
crypto can look at what has been described and see some of the flaws in 
implementation.

16. The RSA conference is February 13-17, 2017. If ACBL and USBF stop 
using their own dealing software by then, I'll consider speaking about 
it as it is an interesting problem - real world, ~$100M/year business, 
cryptanalysis, ability to won National championships/rights to represent 
the US in world competition.


-- 
Nicolas Hammond
nicolas at njh.com