Everyone who's confused about the threat model for bridge shuffle creation
should check out http://www.iacr.org/newsletter/curr/bridge.html
There are three major things which could be gotten out of using
cryptographic technology -
1) The ability to print a short seed in a newspaper/online so that people
can reproduce all the shuffles without having to communicate the position
of every last card individually.
2) A process which makes it impossible for the producer of shuffles to
build ones which look the way they want rather than random.
3) An interface which makes it very difficult to accidentally use shuffles
intended for a different tournament.
I'll start with my thoughts on (1).
Someone pointed out that it isn't necessary to have a cryptographically
large number of bits in the seed - it just has to destroy any obvious
statistical pattens in the data, which using a cryptographically strong
pseudo random number generator will do, and have enough possibilities that
the humans playing in the tournament are unlikely to ever have seen a hand
before. Forty bits is a reasonable number for that, even if it causes some
people existential angst (sorry Lewis.)
The reason to pick a number as low as 40 is that it makes the number of
keystrokes necessary to enter it as small as possible. I suggested earlier
that five bits can be encoded in a single character by using letters and
digits without 0,O,6 and G. Using that technique, 40 bit is eight
characters. I think it would be prudent to include an error correcting
code with that of another four characters, designed so that if any two
characters were entered wrong it could correct them and if three
characters were entered wrong it could complain. That way there would be
considerable margin for error when communicating and tying in codes, and
the chances of any random bunch of characters being accepted would be very
small, without creating a particularly bad keystroking burden. I think it
makes sense to by convention express the characters in groups of four -
like this: GN8G DB3R Q4RS. That way it would even be practical to read a
seed off on the radio.
I don't know off the top of my head how to do an ECC like that, does
anybody have a good online reference? It seems like it should be a pretty
standard non-cryptographic ECC.
It makes sense to use a single seed not just for one hand but for an
entire tournament, or at least one day of a tournament (I have no idea if
tournaments are multi-day or not.) One could generate all the shuffles
directly off the stream which comes form the seed, but generating hand
number 20 on a PDA might start to take a while. I think a much more
reasonable way of doing that is to treat the stream generated by the
original seed as a series of seeds for individual hands, that way it takes
about the same amount of time to generate any hand number, no matter how
late it is.
Some anonymous person posted code for generating shuffles based on RC4.
Unfortunately, I think we really want to avoid using encryption-based
technlogy anywhere in this thing, because of export laws from the US and
local laws other places. It would make a lot more sense to use a PRNG
based on SHA1 or RIPEMD160.
Reducing the size of the seed impacts the way in which pre-publication of
the seed material is done, but doesn't make it impossible. What it does
limit is the number of different participants which can contribute to the
seed generation process without making it practically inauditable. I think
having three contibutors of seed material and a single independent
collator (probably whoever's running the tournament) is emminently
reasonable for the bridge tournament threat model.
Given that list of participants, I think it would be best to implement the
system without pre-publication and auditing first, and add that on later.
Even without the auditing, a breach would require collusion on the
part of one of the entropy providers and the collator, which is still a
huge improvement over how things are done now. With auditing the threat
model is greatly improved, but that's something which can be done later
without any change to the system built beforehand, and it's important to
get something working without excess difficulties.
As for auditing's effect on (3) above, I think for the time being that can
be done by using software with a UI which makes it very difficult to send
the wrong seed to the wrong place. The easiest way to do that is to attach
a description of the use of a seed to the seed and never, ever separate
them. That's essentially what allowing for auditability would enforce, but
it should be done from the beginning just for usability reasons.
-Bram
