[827] in cryptography@c2.net mail archive
Tea Leaves: Ephemeral Shared Entropy
daemon@ATHENA.MIT.EDU (Nick Szabo)
Wed May 14 23:06:58 1997
From: Nick Szabo <szabo@best.com>
To: cryptography@c2.net
Date: Wed, 14 May 1997 18:42:14 -0700 (PDT)
If Alice meets Bob at a party, how many bits of entropy can they privately generate
to use for future remote communications between them? What I'm after
is "shared entropy": unguessable numbers known only to Alice and Bob.
With this we can construct an add-on to public key cryptosystems which
provides forward secrecy and parallel fallback mechanisms for confidentiality and
authentication.
Some examples of shared entropy:
* Reading the tea leaves. This ephemeral visual pattern contains a
signficant amount of entropy in a digitized, sharp black & white still.
The technique has value as a traditionally recognized, visceral, face-to-face
"protocol", and is faster than lava lamps. :-) Alice and Bob swish the leaves,
drain the tea, take the photo. They might hide the cup from others in the
room and provide a local light source. They then download the digitized
photograph to their laptops, digest down to the expected amount of true
entropy, encrypt using the previous shared data digest as a key (so that we
have a kind of "chaining mode" between "readings", and even between separate
face-to-face meetings of Alice and Bob). Repeat the process with more
"readings" until the desired entropy is obtained. Wash out the last pattern.
Drink tea.
Alice and Bob might keep the photographs to cross-check against the digest
and personal memory later, to detect if somebody who gained access to their
personal data altered the shared entropy. If this is not a
concern, or forward secrecy is required, the photos should be deleted immediately
after their digest has been taken.
* Scrawling with a mouse, radiation counting devices, etc. on a laptop
with a shared link between Alice and Bob. Not as hip as tea leaves but
perhaps more practical.
* Most biometrics (palm readings, fingerprints, retina scans, etc.) don't
have novel entropy across readings. Voice (e.g., conversations, songs)
has some, but what is entropic within readings but repetitive between
(e.g., the general voice pattern) is non-confidential entropy and would have
to be filtered out.
Such "readings" might of course be associated with a PGP key-signing party.
The shared entropy might be expanded using a PRNG such as Blum-Blum-Shub
into a very large supply of pseudorandom numbers for for keying purposes.
Hal Finney also suggests recycling entropy using one-way hash functions.
I don't propose using shared entropy as a replacement for key distribution using
public keys, but rather as an adjunct, a second layer of protection. When
Alice and Bob communicate via public key, they would now encrypt using two symmetric
keys, one encrypted via public key and transmitted with the message,
the other used in the encryption and then destroyed. Tandem use of the symmetric
keys may take one of the following forms:
* encryption of the transmitted key with the rederived key, before the
message is encrypted
* superencryption of the message
* combination into one very large key, so that even if one part of the
key were known, the encryption is still unbreakable
Indeces into this shared data are derived from the transmitted
symmetric key to construct the untransmitted key. The receiver must
rederive the untransmitted key, using these indeces and its own synchronized
shared data.
The shared data bits used in the key are destroyed, by the sender upon encryption,
by the receiver upon decryption, to provide forward secrecy. (My thanks to Hal
Finney for clarifying the existence of this property, which is perhaps the most
valuable part of this system). One attack to be addressed here is
whether the bits can be reconstructed from the surrounding bits in the PRN stream:
if so we'd have to fall back to selecting key bits from the original true
entropy, or to recycling via one-way hash functions, or find a way to select keys
from the PRN stream without this fill-in-the-blanks property.
If Alice and Bob share keys at the party as well, this protects against the
man-in-the-middle attack. Otherwise, a MITM could still spoof Alice and Bob using fake
public keys, but could not determine the plaintext of their messages when encrypted
as outlined above. A challenge-response protocol (such as zero knowledge proof) using
the shared entropy, combined with self-certified exchange of the true public
keys, would unmask the MITM as an entity using fake public keys. If the
MITM disrupted these messages he would also be unmasked. But this is
gratuitous functionality, since while at the party Alice and Bob can simply
swap public keys. The main value-add here is fallback authentication: a thief would
have to steal both Bob's private key _and_ the entropy shared with Alice,
or a cryptanalyzer would have to break both, in order to commit identity fraud,
spoofing Bob to Alice.
So a general benefit, besides forward secrecy, we get is that we have independent
parallel mechanisms for confidentiality and authentication between Alice and Bob if the
public key system breaks down (key escrow, timing attacks, bad PRNG, ...). Of course,
similar breakdowns could happen to the shared entropy system, but if implemented
with independent algorithms it gives us a fallback already in place. The
more radically different the backup is, from the ground up, the more likely its
failures will occur for independent reasons.
If Alice and Bob don't have the opportunity to meet face to face, they
might each generate random numbers from their own sources, which
are shared via a "fair coin flip" protocol during a forward-secret session.
The security of the generated numbers would depend on the security of this
initial session, of course.
Nick Szabo
szabo@best.com
http://www.best.com/~szabo/
