-----BEGIN PGP SIGNED MESSAGE-----
Date: Fri, 03 Nov 1995 00:44:02 -0800 From: tcmay@got.net (Timothy C. May) Subject: Re: video as a source of public randomness
At 6:23 AM 11/3/95, JMKELSEY@delphi.com wrote:
This seems like a potential source of a stream of public random bits. If these can be authenticated and matched, this kind of thing can be useful in a lot of protocols. For example, if there is some
I'm not sure what you mean by "public random bits"...I don't plan to share my random bits with anyone, nor do I see any need for "public" random bits (except for some well-known situations involving statistical testing, for which certain PRNGs are actually preferable to "real" random numbers).
Imagine there is a stream of totally random bits over which neither Alice nor Bob has any control. We can use this to make a lot of interactive protocols non-interactive. Suppose we have a protocol where we need a random challenge from Bob. Alice sends a message to Bob starting the protocol, stating that the public random bit stream is currently at bit i, and committing to use the n-bit string starting at position (i+t) as the challenge. The t parameter here needs to be large enough to ensure that Bob receives and logs the message before the public random bit stream outputs bit i+t. Alice proceeds with the protocol, using the n-bit string starting at bit (i+t) as the challenge. She sends the resulting message to Bob. No interaction was required of Bob--he merely had to log the times of the messages, and keep track of the public random bits. This could be really useful implementing noninteractive digital cash schemes, I think, because the merchant wouldn't have to send anything back. (The merchant can also be very hard to track down by following the messages, since these messages of Alice's can be encrypted under his public key and posted to a newsgroup or something, though this implies really large values of t.) Naturally, this only works if Alice and Bob get the same random string, and if it's not possible for anyone to alter the public random bit string either one receives. For large-scale applications, the way to do this is probably to put a hardware RNG into a communications satellite, and devote one channel to continuous digitally-signed packets of random data. For smaller-scale or underground applications, it might be sufficient to use some digitized transmission that would probably not be worth the trouble for an attacker to alter, even if one could. For example, if we used the entire digital video feed off some major satellite, it would be enormously expensive to take control of that for any length of time, to attack some protocol. To prevent simple attacks, we can hash the digitized input, and we can make each shared random packet dependent on previous packets by some relation like random_packet[i+1] = SHA1(random_packet[i],SHA1(digital_video_packet[i])).
And so there's no confusion, when I said "like a noisy channel (t.v. channel, for example)" I meant a snowy, noisy picture such as one gets with rabbit ears on top of the set, especially when the channel is an unused one. It is unlikely in the extreme that any attacker could deduce the snowy pixel values used in the distillation of entropy.
I was just thinking of the unintended entropy in the stuff going on on the screen. Static would mess this idea up, though there are some ways to recover.
But back to the subject of "public random bits." Could you elaborate on what you mean by this? (I assume you don't mean a one time pad that Alice and Bob share, since that is really a separable issue from video as a source of randomness. Only one of them will generate the pad, and will then securely communicate it to the other.)
No, of course not. Public random bits can be used in the derivation of a shared key, to prevent replay attacks in key-exchange protocols, but you certainly wouldn't want to use the public random bits directly as key material!
--Tim May
Note: Please respond via e-mail as well as or instead of posting, as I get CP-LITE instead of the whole list. --John Kelsey, jmkelsey@delphi.com PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36 -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCUAwUBMJqtkUHx57Ag8goBAQGWRgP1HES4nQiWRx0P31bi94g5MI8pSEwf5CZu 0RlWLyCl5CLB6PKu7bJDqiyHIBBJ90qqvJvZB740QHVxoRKycOD459nMWjiQXcnA 70Aq8gR+ZYCivsJLJfhKxoxuT+s/VyYVMB7mSfqGIGHHErbXHR4oA2T+Owmm8POi WDr4w3OjyQ== =3QHQ -----END PGP SIGNATURE-----