BBO random generator

[woefuwabit]

We're talking people who can buy a team for the Superflight, and buy a computer program that can do this kind of prediction. Buying the proctor isn't that much more of a shift in belief.

 

The program to do the prediction probably isn't worth much. I could write it for free as proof of concept, but as I've described it in my last post, it is so trivial there's no need for a proof of concept. The hardest part about it is determining when the server is restarted and trying to obtain the earliest deal as possible that was generated after the server comes up.

 

In response to woufuwabit and Maastricht, I like that idea; I think that the BigDeal seed should be printed on the hand records so that it can be after-the-fact independantly confirmed that the hands that were generated were the hands that match that seed, and so the pattern of seeds can be analyzed. And that the BigDeal seed isn't generated from 32-bit prng, but by 96*log2(36) bits of /dev/urandom or equivalent.

 

The original version of BigDeal uses 160-bit pure random speed. In the original DOS version, this is obtained by collecting entropy from asking the operator to enter random stuff on the keyboard. In the Windows version, entropy is collected by asking the operator to move the mouse around. The Duplimate version also collects entropy from the speed of the Duplimate operators. Since most of these programs are expected to run on Windows these days, they don't have access to /dev/urandom

 

The deals are then generated not by PRNG, but by applying a cryptographical hash on the the seed appended with a counter. Original version of BigDeal uses RIPEND-160 which returns a 160bit value, which is truncated down to 96 and mapped to particular hand. Of course, occasionally the value is higher than ~5.36e28 so that value is dropped and it looks for the next counter value.

 

Now, BigDeal recommends that instead of generating a new seed in between sessions (which can be time consuming), the seed is reused and the counter value is stored for the next session. This works great, of course, if the seed is not leaked, but of course would not work in the case you mentioned where the seed is to be published. I'm not sure if BigDeal has been updated since 12 years ago, I would think it would be a good idea these days to use more entropy bits together with a more modern cryptographical hash such as SHA-2 or SHA-3. So ideally the hand record would also include a link to the source code of the generator used... especially since I know of two different methods to map values to hands (Anderson's and Pavlicek's).

[Antrax]

The deals are then generated not by PRNG, but by applying a cryptographical hash on the the seed appended with a counter.

You seem quite knowledgeable, so I'll bite: what's the difference?

[woefuwabit]

You seem quite knowledgeable, so I'll bite: what's the difference?

Well, what BigDeal uses is a http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator so it is also considered a PRNG, just not one of the commonly used types that are not secure. The common non-secure PRNGs used (LCG, LFG, MT) can have their states easily determined from the values that they generate.

[barmar]

I reiterate that I can't see any sponsor *doing* this; I just work in Computer Security and have to think like a paranoid.

Then surely you're also familiar with the principle of risk assessment. You don't need to put a piggy bank in a safe deposit box.

 

This is just bridge, not national security.

[woefuwabit]

Then surely you're also familiar with the principle of risk assessment. You don't need to put a piggy bank in a safe deposit box.

This is just bridge, not national security.

 

Part of risk assessment is determining the cost of mitigating the risk. Here, the cost is next to zero. Just applying a few simple changes, rebuild, deploy.

 

The risk is very real though, and the BBO deal generator is vulnerable to the attack I have described earlier. It doesn't require a genius or a lot of resource to perform the attack. With the first generated deal of the session, one can determine the seed in a matter of minutes (or instantaneously if the approximate server start time is known), allowing future deals to be predicted. With an early (not first) deal it would take longer to find the seed, but it is within practical time.

 

Since 2000, all hands randomly generated for tournaments and club games using the Duplimate dealer adhere to these 3 requirements.

 

1. The generator must be able to deal all 53,644,737,765,488,792,839,237,440,000 possible bridge hands

2. The generator must be able to deal all the above hands with the exact same probability

3. It must be impossible to predict deals even after knowing all the deals in the session

 

The BBO deal generator fails all 3 requirements.

[mycroft]

Then surely you're also familiar with the principle of risk assessment. You don't need to put a piggy bank in a safe deposit box.

 

This is just bridge, not national security.

Absolutely. As I have *repeatedly* said, when it is "just bridge", I don't care what happens. There are much easier ways to cheat than following the PRNG.

 

But I do think that the chance of this happening is about as likely as, oh I don't know, figuring out where to put one's pen after writing in one's score, or leaning on the table with one arm in the other hand, or perhaps there's something about tap-dancing. I've heard that, for events that aren't "just bridge", that we do things to defend against that...

[OldPlayr]

A lot of nit-picking about random number generation. Gotta love the internet community :P

 

Random functions are certainly good enough for dealing bridge hands!

 

I'd be more concerned about online opponents cheating with IM, SKYPE, phone conversation, or sitting in the same room. I know that this is common in online poker. Most college kids will tell you that.

 

I'd never play big money poker or bridge online.