The following is a message I originally posted to coderpunks. The article
it refers to can be found at
http://www.iacr.org/newsletter/curr/bridge.html
The last IACR newsletter mentions that bridge tournaments are having
trouble generating random deck shuffles, and suggests that the
cryptographic community should in a show of good faith (and, in my
opinion, a display of competence,) help them out.
The most interesting thing about the threat model mentioned for bridge
shuffles is that there is mention of allegations of manipulations to
ensure that there are ample opportunities for both north-south and
east-west, which is very much not in the spirit of the game. This shoves
the threat model into the same category as digital picking of lottery
numbers - it is necessary not only that it be random, but that outside
parties be able to ensure it's randomness.
I believe there is significant published literature on picking of lottery
numbers, but I will give my thoughts on it anyway.
Essentially what's needed is the creation of a single seed. To keep a
single party from manipulating that seed it's necessary for it to be a
composite of randomly chosen seeds from several different counterparties,
done in such a way that any conspiracy of counterparties which misses even
a single one will be incapable of any manipulations.
The simplest way of generating a composite key is to have all
counterparties which participate in seed creation generate their own
random seeds and then xor the results. Doing this verbatim results in a
potential attack in which a counterparty manages to see all other
counterparties's seeds before sending in their own. That can be fixed by
requiring all counterparties to pre-publish the secure hash of their seeds
in a highly public and pre-specified manner, such as putting them on a web
page.
That technique works, but it introduces a potentially herculean task of
keeping track of who published what seeds and for what hands of what
tournaments. That can be fixed by requiring that all seeds be the result
of taking a secure hash of a message describing what they're used for. An
example of such a message might be 'this is the seed message from the
chicago player's bridge club for use in the tournament held in sydney on
august 11, 1999 hand #4, some entropy generated by banging on the keyboard
is: snaoteuhsaoedu, some entropy spat out by my computer's random number
generator is: .lcrid;qzkidrl, the current time is january 3, 1999 12:45 pm
and this generation was done by John Smith.' (my apologies if my fake
bridge vernacular sounds hopelessly inaccurate.)
I believe that technique makes the clerical task of tracking seeds
manageable. The number of times the process needs to be run makes a
human-readable format perfectly reasonable, and doing so adds a
considerable amount of flexibility for altering the requirements of what
be stated in it as processes are modified. In exchange for requiring human
intervention, the need for scrupulous tracking of what seed value goes to
what hand is done away with. In particular repetition of hands across
tournaments is made easily avoidable - a disaster which has actually
happened.
Happily, all the technology I mention here is freely exportable from the
united states.
It is interesting to note that the bit of analysis in the IACR newsletter
said much about how to use the seed to generate a hand and nothing about
the threat model, while I said much about threat model and nothing about
how to use the seed to generate a hand. I will say, however, that feeding
the seed into a pseudo random number generator which isn't
cryptographically secure would be just plain stupid.
-Bram
(yes I use a dvorak layout)
