[850] in cryptography@c2.net mail archive
Re: forward secrecy and email protocols
daemon@ATHENA.MIT.EDU (Nick Szabo)
Thu May 15 22:15:47 1997
From: szabo@netcom.com (Nick Szabo)
To: aba@dcs.ex.ac.uk (Adam Back)
Date: Thu, 15 May 1997 18:59:09 -0700 (PDT)
Cc: mab@crypto.com, cryptography@c2.net
In-Reply-To: <199705091315.OAA02228@server.test.net> from "Adam Back" at May 9, 97 02:15:27 pm
Adam Black:
> I understand the US DMS (Defense Messaging System) has use-once public
> keys distributed by a keyserver. Each user submits many keys. Each
> key is handed out once, and discarded. When the keys are all used up
> the user submits another set. The user certifies the use-once keys
> with a persistent signature key.
This is still "interactive", in the sense that there is still is a
"session", a sequence of key generation, distribution, message
encryption and transmission, message decryption, and (for
forward secrecy) key destruction. That this "session" lasts
a much longer period of time buys us more flexibility in choosing
the time in which we send our message. But it costs us a much
longer period during which we must protect the private key. This
gives rise to the need for a secure persistent store, then a secure
way to wipe the private key from this store. We achieve forward
secrecy from the time of destruction if the key hasn't been
compromised during this longer period.
By restricting ourselves to one key pair per message, instead of one per
user per validity period (of typically months to years), we greatly
reduce the exposure from compromise, from many ciphertexts to
one ciphertext. This is achieved at a high cost: if a typical recipient
would receive M encrypted messages during a normal key pair
lifetime, the costs of key generation, and bandwidth and storage
for key distribution, increase by a factor of M.
Fortunately, if we don't like that extreme we can choose a range
of tradeoffs between resource usage and ciphertext exposure: have
keys that are good for M' messages, so that the increased resource
usage is only M/M', and only M' instead of M ciphertexts
are exposed per key compromise.
> I'm not sure I like this approach because it requires the sender to be
> online to ask for a new public key on each communication, before
> encrypting.
This is unacceptable, but I propose a solution: Alice gets a
_batch_ of N of Bob's M'-use public keys from the key server,
which she can then use for her next N*M' messages to Bob,
within the validity period of keys in that batch. The resource
tradeoff: it saves Alice a factor of up to N*M' queries to the
key server. In return it increases the key storage requirements
of Alice and the key server by a factor of N. Since many of
these keys will likely expire unused, the key generation time,
and key server storage and bandwidth requirements, will
be somewhat increased.
This batching eliminates per-message traffic analysis at the
key server. To eliminate all traffic analysis, Alice should
get the keys directly from Bob via remailer.
> [denial of service attack]
The key sever might also query Bob for new keys when it runs
out of old ones, eliminating this attack in terms of running out
of keys, although network resources can still be stressed.
For the keys server or Alice to query Bob for keys, Bob must
be running a server, which may be impractical in some environments.
Nick Szabo
http://www.best.com/~szabo/
szabo@best.com
