[1301] in cryptography@c2.net mail archive
Using satellite feeds to get shared pseudorandom numbers
daemon@ATHENA.MIT.EDU (John Kelsey)
Sun Aug 3 17:17:33 1997
To: "Perry's crypto list" <cryptography@c2.net>
From: John Kelsey <kelsey@plnet.net>
Date: Sun, 03 Aug 97 15:34:40 CDT
-----BEGIN PGP SIGNED MESSAGE-----
[ To: Perry's Cryptography List; sci.crypt ## Date:21-Jul-97 ##
Subject: Using satellite feeds to get shared pseudorandom numbers ]
I'm sure this has been invented before, but I haven't seen it
published anywhere, and I think it has particular relevance with
respect to various potential laws against some kinds of services
(particularly involving various ecash and gambling systems). (I
may have posted something about it before, though I don't think
so.)
Suppose Alice and Bob want to establish a shared pseudorandom
seed for some kind of game they're playing--perhaps a combat
simulation that uses random numbers to decide the effectiveness
of some weapon. The straightforward way to do this is something
like this:
1. Alice forms random number R_0 of 160 bits and sends
hash(R_0) to Bob.
2. Bob forms random number R_1 of 160 bits and sends R_1 to
Alice.
3. Alice sends R_0 to Bob.
4. Alice and Bob now use R_0 XOR R_1 as the seed to some
strong pseudorandom number generator, such as three key
triple-DES in OFB64 mode.
This works very well. If both Alice and Bob accept that hash(X)
can't be inverted in a timely way, and that triple-DES in OFB64
mode is a good enough PRNG, then they will accept that they are
sharing a pseudorandom stream under neither party's control.
However, this still leaves us with some problems:
a. There's no surprise left in the pseudorandom stream. That
is, they have to do this protocol each time they want to have
some unpredictable numbers.
b. Alice can occasionally fake a communications failure with
Bob in the third step, when she sees that the resulting
pseudorandom stream will be really disasterous for her. This is
fixable, but it's ugly.
c. In general, Alice and Bob need a pretty good channel
between them to keep getting unpredictable outcomes that both
believe are not being controlled by either party. In the case
of a game that required unpredictable random values several
times a minute, we would have a high-volume stream of data going
back and forth in a predictable pattern. Note that this would
strain the security of many low-quality anonymous channels,
especially the kind that might be used for realtime
communications.
The anonymous channels are important, of course, to prevent
tracing of the participants by local authorities, thieves who
might want to demand a cut of the winnings, nosy neighbors, etc.
One really neat solution is to use existing digital streams
which are somewhat unpredictable and out of the control of
either party. The protocol now looks like this:
1. Alice and Bob agree on a starting time T, an unpredictable
digital channel C, and a crunch factor, Z. This is all open,
since there's no way for either of them to take advantage of
this.
2. Alice chooses a 160-bit random number, R_0, and sends
hash(R_0) to Bob.
3. Bob chooses a 160-bit random number, R_1, and sends R_1 to
Alice.
4. Alice and Bob both generate a shared triple-DES key, K_*,
from R_0 XOR R_1, hash(R_0,R_1), etc.
5. At time T, they both start listening to channel C. They
encrypt the bit stream under K_* in CBC mode, using triple-DES.
6. They apply the crunch factor Z by XORing each Z blocks of
ciphertext together to get one block of pseudorandom output.
7. They use these pseudorandom outputs as needed.
Note that Z must be set high enough that neither Alice nor Bob
can expect to predict a single block, even given the previous
CBC state and the general context of what's going on the
channel. If either can start predicting output blocks, then we
lose the advantage of this.
Now, note that the first part of this protocol could be done
anywhere--including simply defining some standard set of T, C,
and Z selections. The second part, in a modified form, can be
done via telephone or pager. This implies that it will be very
hard to intercept or regulate what can be done with these
pseudorandom numbers. One obvious use for this is for the random
challenges required for various kinds of digicash. Another is
for random bits to be used in some gambling or other proscribed
game.
--John Kelsey, Counterpane Systems, kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBM+RhPUHx57Ag8goBAQFHiQP+MF+WPL9PRzWPRuajjwSkYuS2z57H+iCU
0wMsxTlMWJMPwjXw3VJxGw3Ao12ewU5buQP1klfC7HUDCETHPGji2fbw7jOeiZJP
e4zJD1M/rTTSvhQL1HBHnTOHL4xcV9q6iXfMdNSZESqsY7M7h5LhOVzbRLXxHjvC
N2e/hI04cc4=
=qktD
-----END PGP SIGNATURE-----
--John Kelsey, Counterpane Systems, kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
