[4943] in cryptography@c2.net mail archive
Re: Bridge
daemon@ATHENA.MIT.EDU (bram)
Wed Jun 23 12:29:17 1999
Date: Tue, 22 Jun 1999 22:08:45 -0700 (PDT)
From: bram <bram@gawth.com>
To: "Arnold G. Reinhold" <reinhold@world.std.com>
Cc: cryptography@c2.net, coderpunks@toad.com
In-Reply-To: <v04011700b3960167090f@[24.218.56.100]>
On Tue, 22 Jun 1999, Arnold G. Reinhold wrote:
> At 6:32 PM -0700 6/22/99, bram wrote:
> >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.
> >...
>
> I think it would be good if the bridge folk slowed down a bit and tried to
> separate the problem from their ideas on how to solve it.
It sounds from that article like the bridge folk know very well what their
problem is, but have no idea how to solve it. The ideas expressed in the
previous post were mine.
> What is the time line they need. I.e. if the start of the tournament is
> time zero. What is the earliest time the hands can be prepared and what is
> the latest time?
Given the way tournaments work now, it would be perfectly okay for
considerable preperation to be done beforehand, and just the final deck
assembling to be done on the day of the tournament.
> How many hands do you need per tournament?
My total ignorance of bridge may be showing here, but I believe it's less
than 100.
> How are hands created now?
It says in that url I referred to.
> There are 52! bridge hands, so a random hand has
> log2(56!) = 226 bits of entropy or 68 decimal digits worth. Are they
> generating that much entropy per hand now? If so, how?
Generating that much entropy would be pointless. All that's needed is
enough entropy to be unguessable in the seed and a cryptographically
secure pseudo raandom number generator.
> How much hardware can one assume?
I think guessing that someone at the tournament might posess a
programmable PDA and the ability to type is more than reasonable.
> Would a public seed selection session immediately prior to the tournament
> be acceptable? (I have in mind publiclly scanning in the morning's stock
> market report or some such)
That technique alone wouldn't help, since the whole point is to keep the
hands secret, but it could be used as an extra bit of information to xor
into the seed.
I was thinking something along the lines of three different bridge clubs
mailing in their seed to the tournament and someone there xoring all of
them.
Actually, now that I put it that way pre-publication seems like a bit of
overkill - the chances of there being a fake sealed envelope are pretty
small, and if one is sent in fraudulently it will probably be a duplicate
and be easy enough to clear up with a phone call.
In that vein, pre-publication of authentication codes can be added onto
just about any protocol for this later on.
Also, I now realize that all hands at a single tournament could be
generated off the same seed (duh!)
So, the technique I mentioned previously can be simplified by making the
original message get only hashed once, rather than twice, and getting rid
of the pre-publication. I think the hashing the message trick is still
necessary for keeping the same random garbage from being used in multiple
tournaments though.
We still haven't discussed actual entering of the seed value - I think
encoding using capital letters and digits would be a good idea. That makes
36 characters, which can be brought down to an even 32 by dropping 0, O,
6, and G. Anybody have any other suggestions? For something hand-entered,
an ECC might be a pretty good idea.
-Bram
