BBO random generator

[CarlRitner]

 

The general point I'm making is while there may be ways to improve it, what we've got is good enough for our needs and we have more important things to fix.

 

 

Gotcha. Didn't mean to stir things up, it's just anytime I can combine bridge and computer stuff, I enjoy it.

4 trillion boards ought to cover my needs.

[Siegmund]

So, despite the hands dealt being statistically appropriate for hand patterns and HCP, can BBO deal every possible deal, or only 2^32 (4 billion or so)?

I thought one needed 96 bits of entropy to cover all 53,644,737,765,488,792,839,237,440,000 possibilities.

 

Without addressing BBO specifically...

 

Whether you can deal every possible deal is a separate question from how much entropy you have per deal. You can reach every possible deal completely deterministically just by enumerating them -- and if you did something like choosing the (30,000,000,000,000,000,000,000,000,001*n mod 53,644,737,765,488,792,839,237,440,000) th hand from the list to be your nth deal, it would be quite a long time before someone noticed the determinism.

 

There are many possible shuffling routines which can reach all possible deals, but can only "start from" 2^32 places as they work their way through the list.

 

There is a whole subdiscipline of "quasirandom number generators", guaranteed to eventually cover all possibilities and to scatter the first n points as uniformly around the sample space as possible. It's not much talked about now, but once upon a time it was used to do Monte Carlo integration faster and with tighter error bounds than by using pseudorandom numbers.

 

 

How many bits of entropy are used for each new hand addresses a separate question -- how well can the next deal be predicted, given the hands which have been dealt before it?

 

For humans, almost none are needed, if the pattern in which the hands are presented doesn't show any too-obvious trend. To defeat computer prediction of next boards, several bits per hand are desirable, but you can get away with quite a bit less than 96 per hand.

[barmar]

It just occurred to me that the fact that the same RNG is being used for a variety of things in the program effectively ADDS entropy.

 

If the RNG were just being used for dealing hands, and you saw a sequence of several hands, you might be able to calculate where it is in the random sequence, and predict the next set. But if hand dealing can alternate with an unpredictable number of other activities that also use the RNG, you lose your place. You might be able to estimate a range of other random activities that took place between deals, but that will give you a variety of possible deal sequences.

 

To get around this, you would need to somehow eavesdrop on ALL the activities that use the RNG, and know exactly how it's being used, to have a decent chance at predicting sequences.

[Antrax]

That sounds about right. Assuming these unpredictable events are driven by interrupts or user input, that's actually another source of randomness :)

[woefuwabit]

There was a pretty good paper about fair generation of bridge deals written 12 years ago:

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

 

There are two issues with the implementation barmar posted

1. c1=rand()%13; This will be biased towards certain values. A simple way of unbiasing it would be to modify the line to:

do {

c1=rand() & 0xF;

}

while (c1 >= 13);

 

2. Not sure what implementation of rand() the bbo compiler is using but AFAIK most implementations (e.g. GCC, VC) use a LCG with a period of 2^32, which is far below the minimum 2^96 that is required, meaning that it will only be able to deal a very small subset (1 in 2^64) of all the possible bridge hands. You should probably use something like a Mersenne Twister instead which has a period of 2^19937

 

 

Ideally, you would really want to implement something like that Big Deal has done.

1. Generate 512 bits of entropy, which can be reused forever

2. Start counter at 0

3. Hash(Entropy + Counter), I'd recommend using SHA256

4. Map the result to a bridge deal, e.g. using http://bridge.thomasoandrews.com/impossible/

5. Increment counter, go to 3 for next hand

[jandrew]

I sometimes wonder how many angels can REALLY dance on a pin head.

 

:)

 

jandrew

[jandrew]

... ... and if one fell off, would we REALLY notice.

 

jandrew

[barmar]

2. Not sure what implementation of rand() the bbo compiler is using but AFAIK most implementations (e.g. GCC, VC) use a LCG with a period of 2^32

We're using whatever you get with Debian Linux.

[woefuwabit]

We're using whatever you get with Debian Linux.

 

That would be glibc, which uses a LCG with period of 2^31

Since you are on Linux, you have easy access to a strong PRNG in /dev/urandom and should probably just use that. Just add this and replace your calls to rand() with urand():

 

int urand() {
  static FILE* file = fopen("/dev/urandom", "r");
  int random;
  fread(&random, sizeof(random), 1, file);
  return random;
}

[barmar]

The fixes are all pretty obvious, I don't need programming lessons.

 

It's the need to fix it that I'm not so sure of. I think folks are overstating the inadequacies of the current implementation.

[Antrax]

No disrespect intended, I'm sure. It just seems like low-hanging fruit.

[woefuwabit]

No disrespect intended, just showing that the fix is trivial compared to potential issues.

Just remember that because of the birthday paradox, there will be a 50% probability of a deal being repeated after 2^15.5 = 46341 deals. Personally, I'm not comfortable with that, but the prerogative is yours.

[woefuwabit]

I thought about it further and the problem is actually far more serious than I thought.

I can build a database containing all 2^31 possible hands that BBO can deal.

 

After seeing 13 cards (my own), there will be an average ~296 possible distributions for the remaining 3 hands.

 

After seeing 26 cards (mine + dummy's), the exact distribution of the remaining 2 hands can almost always be determined. Occasionally there will be 2 possibilities but that will be very rare. the exact distribution of the remaining 3 hands can be determine ~99.7% of the time.

[Antrax]

I'm not sure that's accurate, because of the existing deal algorithm. If the algorithm were "pick a random number; take that hand from the index of all possible hands" then that would've made sense, but because each card consumes a different amount of randomness, it ends up creating smaller cycles in the larger cycle. I have no clue how to deal with it, and assuming the PRNG is reseeded from time to time, the added randomness from rand() being used for other things makes this attack unlikely.

[woefuwabit]

I'm not sure that's accurate, because of the existing deal algorithm. If the algorithm were "pick a random number; take that hand from the index of all possible hands" then that would've made sense, but because each card consumes a different amount of randomness, it ends up creating smaller cycles in the larger cycle. I have no clue how to deal with it, and assuming the PRNG is reseeded from time to time, the added randomness from rand() being used for other things makes this attack unlikely.

 

It doesn't matter. Because the LCG has 2^31 possible states when you start the generation, there can only be a maximum of 2^31 possible hands generated. Reseeding the LCG will only change the state from one of the 2^31 possible states to another of the 2^31 possible states. The maximum number of different hands that BBO can generate is 2^31, no matter how much entropy you try to introduce to it.

 

I actually underestimated the seriousness of the attack in my previous calculation:

 

There are 52c13 = 52!/(13! * 39!) = 6.35e11 possible 13 card hands

BBO can deal 2^31 = 2.15e9 possible hands

 

That means your 13 card starting hand is enough to determine the distribution of all the remaining 3 hands, 295 out of 296 times. (Not determine ~296 possible distributions as I previously miscalculated)

 

 

Of course, if rand() is called by another thread while we are in the middle of generating a hand, this will throw off the attack. I don't expect this to happen a lot though unless rand() is called by another thread very frequently. Also not certain if the other rand() calls happen in a different thread.

[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]

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]

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]

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]

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]

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.