[hrothgar]

FWIW, I expressed my concerns about the system being used to generate hand records to a few folks in the ACBL: I received a polite response from Keith Wells (the ACBL's "Tournament Technical Analyst") which I have reproduced in full at the close of this post.

If I am reading things correctly, the system is actually much worse than had originally believed.
From my perspective, there are three points of interest wrt the existing system:

1. The seed length that the ACBL uses to generate deals is 2^47
2. The ACBL uses this seed to generate a block of 2,000 sets of hands
3. 16 years ago, folks were able to crack 56 bit DES in roughly 24 hours. (Admittedly, this used dedicated hardware, but between Moore's Law, the relatively short key length, and the glory that is Amazon Web Services...)

In theory, the following should be feasible:

1. Get a set of ACBL hand records.
2. Go home. Brute force the seed
3. Generate the 1,999 hand sets that come after this one and the 1,999 sets that came before it
4. Come the next tournament, plug hand 1 into my Lookup table and extract the remaining hands for this set.

Simply put, re-using a short key for long periods of time is a really bad idea...

Wells states: "With so many of the variables involved in the hand record set creation process kept protected and secure, I doubt anyone will be cracking the security in sufficient time to make use of the data they develop."

It would be nice if Well's understood that most of the complexity of the system is intended to ensure that the random seed is uniformly distributed across the 2^47 length key space, but don't need to be known to crack the resulting system...

_________________________

Hello, Everyone,

I was following this conversation on the Bridgewinners website with some degree of amusement, as the degree of code cracking necessary to accomplish a read of the hand record set within a three hour period (a typical play session) does not currently exist. Here is the description of the program used by ACBL, provided by the programmer, Jim Lopushinsky. This was published in the September 2011 Bulletin.

"The following is an excerpt from a letter to the editor, with a response by Lopushinsky, published in the September 2011 issue of the ACBL Bridge Bulletin that may help shed some light on the dealing program used by the ACBL.

Bill Clough of Lynchburg VA wrote: “The question is whether the ACBL hands are random. Let’s look at some numbers. From the ACBL’s own web site, we can find that a huge number of deals can be generated as the random seed is 2^47, that is 140,737,488,355,328 or 1.4x10^14 possible deals. The seed is equal to the largest possible number of unique deals that can be generated.
“It is true that the total number of possible deals is closer to 2^96, but there are actually 53,644,737,765,488,792,839,237,440,000 or 5.3644x10^28 possible bridge deals.
“Surfing the web a few years back, I found an article that helped to understand these enormous numbers. If you have one atom of gold for each possible bridge deal, a gold cube could be formed 3.9 feet on a side and weigh 19 tons with a value more than $800 million.
“Doing the same for the ACBL deals, the cube of gold formed would be 1/1500 of an inch and weigh .05 microgram – less then the ink of the dot on an “i” – with a value of 1/5000 of a cent.
“So are the ACBL deals random? Yes, of course, they are random – as random as the generating program can make them.”

This was Lopushinsky’s response:
“The writer is correct as to the number of hands that can be generated from one seed, but the seed is arbitrarily assigned for each set of hands.
“The random number generator uses the linear congruential algorithm and 48-bit integer arithmetic. This will generate 2 to the 47th power different numbers before repeating without any outside influence (140,737,488,355,328 numbers).
“Outside influence occurs in the form of manually dealt hands, starting seed numbers, time of day, etc., to make the number of numbers virtually infinite, and to guarantee that the same hand will not be repeated. Ninety-six bits take part in the operation with the high 48 bits acting as the overflow.
“The operation works as follows: The hand record set number is used as the starting seed. This seed is multiplied by day of the month, current minute, current hour, current second, current day of week and current hundredth of second. This number is then multiplied by a large prime number (5DEECE66D in hexadecimal). Thirteen is then added to this. The lower 48 bits is then saved and used as the seed to generate the next random number. The overflow (48 high bits) is then doubled and multiplied by the range requested (1 - 52) and the overflow from this is used as the random number.”

The computer used to run the ACBL hand record generator is a stand alone desktop computer that is not connected to any network. Since Jim's retirement in May, I have been responsible for maintaining our stock of electronic hand records used by our Tournament Directors.

When we need additional hand records, we generate two thousand sets at a time (72,000 deals). The seed deal is manually entered at the beginning of the process, and is not part of any set subsequently produced. Sets are never reused, and the number of the set is not released publicly until after play. The date and time when the hand record was prepared (we keep a five thousand set buffer) does not leave ACBL Headquarters.

With so many of the variables involved in the hand record set creation process kept protected and secure, I doubt anyone will be cracking the security in sufficient time to make use of the data they develop.

Regards,

Keith Wells
ACBL Tournament Technical Analyst

[The_Badger]

hrothgar, on 2016-August-19, 17:31, said:

With so many of the variables involved in the hand record set creation process kept protected and secure, I doubt anyone will be cracking the security in sufficient time to make use of the data they develop.

Regards,

Keith Wells
ACBL Tournament Technical Analyst

Obviously Mr Keith Wells isn't familiar with the work of the NSA (in the USA) and GCHQ (in the UK). Saying in this day and age that something is secure is asking for it to be hacked. Sadly...

[barmar]

The_Badger, on 2016-August-20, 01:31, said:

Obviously Mr Keith Wells isn't familiar with the work of the NSA (in the USA) and GCHQ (in the UK). Saying in this day and age that something is secure is asking for it to be hacked. Sadly...

I think the NSA analysts have more important things to worry about, and aren't going to be using their talents to crack ACBL hand records.

Although if you watched the TV show "The Good Wife", you might wonder. They had a recurring plotline where the NSA was listening in on the conversations at the lead character's law firm.

[hrothgar]

barmar, on 2016-August-20, 20:39, said:

I think the NSA analysts have more important things to worry about, and aren't going to be using their talents to crack ACBL hand records.

I think that a few dozen people at Akamai could crack this system in a relative short amount of time...

[hrothgar]

barmar, on 2016-August-20, 20:39, said:

I think the NSA analysts have more important things to worry about, and aren't going to be using their talents to crack ACBL hand records.

I think that a few dozen people at Akamai are individually capable of cracking this system in a relative short amount of time...

[mycroft]

For privacy reasons I don't post to BW. But I was hoping I would get a chance to point out: TrueRNG I've been waiting for HRNGs to get down to "affordable" for decades; I think we've found it.

I would want to run a bunch of cryptographic (not just statistical) bias tests on this thing, and I bet we'd want to run those tests monthly to guard against hardware degeneration/progressive biasing, but for $50, for 350 kilobits/second of hardware randomness - even if it's slightly biased HWRandomness - turns the issue of "I need 36x96 bits" into "turn the usb stick on" and *can't be worse* than the current situation.

And it certainly removes a good reasoning for any "build a hand from ... games" over "look it up in the Big Book, throw out (but report) the odd set that doesn't map to a page in the Big Book".

"Oh crap, I needed 50x96 bits of randomness to gen this set. That means I can only generate 50 sets/second."

[shyams]

I like hrothgar's post of a few minutes ago, made on Bridgewinners.

I suspect your OP here did not get the requisite response mostly because I (and others like me?) did not understand the cryptographic elements in the body of the text.

However, upon a repeat reading (+ some thinking), I just realised that the entire ACBL "random seeding" process is crazy, and easily hackable.

And although knowledge of their randomisation technique is not needed to reverse-engineer the key, their transparency on this matter -- e.g. that they generate 2000 sets at a time -- is downright crazy and can only help someone who really wants to "break" the process and engineer the hand records in advance.

[MrAce]

I just did not understand the title of this topic and what Richard meant by "improve your bridge scores"
How shall we improve our bridge scores even if I understood (which I do not) all the technical explaining?
Is it OK to show people the weakness of what ACBL uses and tell them to improve their score by simply using this weakness? Or did I totally miss the point, which is more likely, knowing Richard.

[helene_t]

MrAce, on 2016-September-12, 12:30, said:

Is it OK to show people the weakness of what ACBL uses and tell them to improve their score by simply using this weakness?

Yes I think so. Those who have the technical skills to crack the code with Richard's help will also be able to do it without Richard's help. If this is a real problem then the way to address it is to make sure that ACBL takes it seriously.

[barmar]

MrAce, on 2016-September-12, 12:30, said:

I just did not understand the title of this topic and what Richard meant by "improve your bridge scores"
How shall we improve our bridge scores even if I understood (which I do not) all the technical explaining?

You don't need to understand it, you just need a program written by someone who does (just like you don't need to know anything about aerodynamics to fly in a plane). That will allow you to predict the hands coming up in a session, so you'll be playing double dummy. If that doesn't help you improve your results, you need to take up a different game.

[MrAce]

barmar, on 2016-September-13, 08:38, said:

You don't need to understand it, you just need a program written by someone who does (just like you don't need to know anything about aerodynamics to fly in a plane). That will allow you to predict the hands coming up in a session, so you'll be playing double dummy. If that doesn't help you improve your results, you need to take up a different game.

I know that would improve my results.

You are missing my point. When said I do not understand all the technical language, I meant I do not understand whether what Richard says is accurate or not. In BW he wrote something similar and other coders replied to him in same language that I do not understand, that he is wrong. And that if he is correct, how will that help me to improve my score legally. As far as I know, cracking the ACBL code and predict hands, is not legal. Or is it?

[barmar]

MrAce, on 2016-September-13, 10:09, said:

And that if he is correct, how will that help me to improve my score legally. As far as I know, cracking the ACBL code and predict hands, is not legal. Or is it?

No one is claiming that this is a legal way to improve your scores. His title was clearly meant sarcastically, since this is obviously cheating. It wouldn't have been as much fun if he'd titled it "A new way to cheat".

As for whether it works, see the thread he started this morning with Nicholas Hammond's message about how some people have successfully cracked the dealer.

http://www.bridgebas...ummer-vacation/

[MrAce]

barmar, on 2016-September-13, 12:52, said:

No one is claiming that this is a legal way to improve your scores. His title was clearly meant sarcastically...
http://www.bridgebas...ummer-vacation/

Yeah I got that but late. Sarcasm in a non native language and on internet is something I almost always catch late.

You may find it funny but at some point I thought, Richard sees this like a "road bike racing" where contenders practice on the type of loop ahead of time of the competition. And that he thinks it is OK (as long as the hands they predict by cracking the code are not exact hands but similar) So one can look and see, lets say no slam hands in the set, can easily throw to trash all slam tools and prepare with a more suitable system..etc. I thought, wrongly, that he is wrong about this being OK. Only thing that did not make sense about my understanding, the author was Richard and as far as I know him, that should not be OK for him.

[cherdano]

Timo, I think it's helpful to understand the general thinking in the computer security community.

The idea is that if there is a flaw like that, then someone will find out. And someone will work out how to break it. Therefore, unless the flaw is fixed, there is a problem. Hence you notify the responsible people of this flaw privately. But it is also necessary to make such flaws public fairly soon afterwards. Otherwise, the responsible parties do not have enough incentive to fix the flaw. And in the mean time, the bad guys will find out.

I.e., it is generally accepted that publicizing such a flaw is the responsible thing to do (after you have given the responsible parties a bit of time to react).

This line of thinking seems quite accurate in the case at hand. After what had been previously known, it was clear that someone could work out how to break this. And indeed, someone has done so.

However, it was not clear to me that the ACBL was given enough time to respond. Arguably, they should have been alerted to this potential vulnerability by hrothgar, but based on the replies he got, the responsible person at the ACBL had neither the expertise to understand this flaw, nor the common sense to realise that hrothgar wasn't talking non-sense.

[mycroft]

Absolutely anything that isn't "generate 96 bits of randomness, 36 times a set, map 1-to-1 with bridge hands (and throw out, but report on, generations that are outside the bounds of the set of bridge hands)" is less secure, and more easily breakable, than that. Absolutely anything that isn't "true, hardware-based" (counting humans as hardware for this purpose) randomness is more easily breakable. Anything that involves "pseudorandom number generators" (literally, functions designed to be hard to follow without the initial seed, but also that will generate random-looking results) is more easily breakable than true randomness (because you are limited to the initial seed, everything else is formula).

"Keeping the algorithm secret" is such a waste of time and effort (and, given that most algorithms are stupidly insecure; it's amazing what isn't insecure given current computing power - usually the only thing keeping it "secure" is secrecy; see what just happened) compared to using true randomness.

I posted something above that, while I wouldn't trust it without a whole bunch of tests for missile launch codes, is certainly so much closer to secure than any "algorithm", including a PRNG - for $50 plus shipping.

Yes, the mathematician in me is also concerned that the current algorithm does not even start with enough randomness to reliably deal all possible single hands, never mind sets of 36. But I will never play 2^23 hands in my lifetime, never mind a million times that. Practically, it isn't an issue (but in theory, theory is the same as practise. In practise, however, that's a nice theory).

[hrothgar]

Cherdano is (largely) correct regarding my motivations.

With this said and done, the only thing that is necessary for the ACBL to address this flaw is for them to switch away from their existing hand generation program and start using "Big Deal" like most every other place in the world does.

Perhaps the ACBL would have benefitted from more time, however, they managed to tick me off...

[cherdano]

hrothgar, on 2016-September-13, 14:48, said:

Cherdano is (largely) correct regarding my motivations.

With this said and done, the only thing that is necessary for the ACBL to address this flaw is for them to switch away from their existing hand generation program and start using "Big Deal" like most every other place in the world does.

Perhaps the ACBL would have benefitted from more time, however, they managed to tick me off...

Agreed. Given the initial response you got, I somehow doubt that they would have reacted without public pressure anyway.

However, what ticked me off was Nic Hammond's assertion that the ACBL would have no problem fixing this issue immediately, since they could just switch over to ACLBscore+, and therefore didn't need advance warning. Now suddenly the legitimate issue of pressuring the ACBL to fix this flaw is mixed up his own complicated and partly personal issue about ACBLscore+.
It's wrong on various levels, and unprofessional. To me, it adds another layer of credibility to the claim that the ACBL was wise to get out of bed with Nic Hammond while it could.

[shyams]

cherdano, on 2016-September-13, 14:58, said:

However, what ticked me off was Nic Hammond's assertion that the ACBL would have no problem fixing this issue immediately, since they could just switch over to ACLBscore+, and therefore didn't need advance warning. Now suddenly the legitimate issue of pressuring the ACBL to fix this flaw is mixed up his own complicated and partly personal issue about ACBLscore+.
It's wrong on various levels, and unprofessional. To me, it adds another layer of credibility to the claim that the ACBL was wise to get out of bed with Nic Hammond while it could.

+1. I got the same sense from reading Nic's message quoted by hrothgar.

[hrothgar]

shyams, on 2016-September-13, 15:01, said:

+1. I got the same sense from reading Nic's message quoted by hrothgar.

I don't disagree (and think that this really detracted from his point)

More importantly, the ACBL can also solve the problem simply by swapping their hand generator to Big Deal

https://sater.home.xs4all.nl/doc.html