[Antrax]

Ah yes, I understand now. Because we're stuck in Z_{(1 << 32)} it doesn't matter what element we start from. Hmm.
[edit]
I don't see why another thread is relevant. I think each thread has its own state of the PRNG in the TLS. Otherwise rand() is a serialization point, and thus would kill performance assuming BBO's code isn't single-threaded.

[gwnn]

Antrax, on 2012-October-09, 22:10, said:

Intuitively, hand-dealing depends on the algorithm used, but from my experience, people usually just do a couple of riffle shuffles. Those tend to leave clumps intact, especially as the cards age. That would result in hands with wilder shape and an uneven distribution of HCP, as people tend to do things like clear suits and cash out, which cause HCPs and suits to bunch together at the end of play.

Not really, for example if there are 8 spades in a row in the deck, it will result in each player having at least a doubleton in spades. I have never seen anyone dealing even "two by two" for bridge. OK sometimes people deal 5-5-3 but that is specifically to make deals wilder (of course with a real random shuffle 5-5-3 dealing is indistinguishable from 1-1-1-1...).

[woefuwabit]

I've looked at the glibc source code, and the state is stored in a global variable, not TLS.
Also, I've found out that while the LCG code is still in glibc, the latest version now defaults to what looks like a Lagged Fibonacci Generator instead, with j=3 and k=31. I think the theoretical max period is under 2^62. Also, unlike LCG, different seeds should produce a different set of numbers.

[Antrax]

So rand() is a serialization point under glibc? Sounds like the quality of randomness isn't the worst concern.

[mycroft]

Barry, I do agree with you re: BBO. If I hadn't made that clear, I'm sorry.

I really am worried, however, about tournaments "that matter": any time you have a sponsor who can buy an open team, you have a sponsor that has the free cash to build a hand generator. I can't believe that any sponsors *WOULD*, but it's at least as likely as cellphone shenanigans, per person with enough cash to have a (cell phone | hand cracker).

I guess the only time that would be an issue in BBO is online GNT Superflights or the like. Possibly, BBO Junior tournaments, too - the "hacker culture" leads to trying to do that for the challenge of doing it. Please note I'm using the *real* meaning of the word hacker, not "cracker"...

[dwar0123]

woefuwabit, on 2012-October-18, 05:17, said:

I've looked at the glibc source code, and the state is stored in a global variable, not TLS.
Also, I've found out that while the LCG code is still in glibc, the latest version now defaults to what looks like a Lagged Fibonacci Generator instead, with j=3 and k=31. I think the theoretical max period is under 2^62. Also, unlike LCG, different seeds should produce a different set of numbers.

So we are good than? Assuming BBO is using the default LFG, there doesn't seem to be a realistic attack that can be setup against it.

[woefuwabit]

mycroft, on 2012-October-18, 10:55, said:

I really am worried, however, about tournaments "that matter": any time you have a sponsor who can buy an open team, you have a sponsor that has the free cash to build a hand generator. I can't believe that any sponsors *WOULD*, but it's at least as likely as cellphone shenanigans, per person with enough cash to have a (cell phone | hand cracker).

I guess the only time that would be an issue in BBO is online GNT Superflights or the like. Possibly, BBO Junior tournaments, too - the "hacker culture" leads to trying to do that for the challenge of doing it. Please note I'm using the *real* meaning of the word hacker, not "cracker"...

I'm fairly sure tournaments "that matter" since 2000 (when the paper I linked to was released) have been doing it 'the right way'. It was used in the 2000 World Bridge Olympics in Maastrict. They were dealt using Big Deal (the reference implementation) and imported into the Duplimate. The Duplimate dealing software has since been updated to use Big Deal's algorithm too, and most tournaments should at least be using that as the deal generator.

[woefuwabit]

dwar0123, on 2012-October-18, 13:47, said:

So we are good than? Assuming BBO is using the default LFG, there doesn't seem to be a realistic attack that can be setup against it.

The attack against LCG probably won't be usable against LFG, but the characteristics of LFG leads to other forms of attack. If you can recover the seed value, then you will only need to generate up to maybe the first 1 million possible deals. The seed can be recovered by brute-force, all you need is a complete deal, ideally one that was generated as early as possible after the system has been seeded which will allow you to recover the seed faster. This can be made even faster if seeding is done the common way - using time, in which case you can narrow down the search space if you know approximately when the server was restarted.

[barmar]

mycroft, on 2012-October-18, 10:55, said:

I guess the only time that would be an issue in BBO is online GNT Superflights or the like. Possibly, BBO Junior tournaments, too - the "hacker culture" leads to trying to do that for the challenge of doing it. Please note I'm using the *real* meaning of the word hacker, not "cracker"...

A few districts have started using BBO for their GNT tournaments. However, I believe they have proctors monitoring the players. So even if it's technically possible to predict hands, they'd also have to get the predictions to the players without the proctors noticing.

[mycroft]

Well, I know the proctors for the D18GNT in Calgary very well, and did when I played in them. Kind of have to unless they're not bridge players; we're sort of an incestuous group.

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.

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


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.

[woefuwabit]

mycroft, on 2012-October-19, 15:41, said:

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.

Quote

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]

woefuwabit, on 2012-October-20, 02:41, said:

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]

Antrax, on 2012-October-20, 03:36, said:

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

Well, what BigDeal uses is a http://en.wikipedia....umber_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]

mycroft, on 2012-October-19, 15:41, said:

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]

barmar, on 2012-October-21, 23:31, said:

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]

barmar, on 2012-October-21, 23:31, said:

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

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.