Forward secrecy

[hughes@ah.com (Eric Hughes)]

   Hate to pick nits here, but isn't the acquisition and use of a public key
   "teaching" your machine to read Tim's "language"?

I agree.  Each public key creates a different encoding, or a different
language, as it were.  These encodings/languages are all related, but
mutually incomprehensible.  Encryption software has the capability to
read any of these languages because it is multi-purpose software.

Because the software is multipurpose, however, there is a greater need
for forward secrecy.  Forward secrecy is the property that an
intercepted communication cannot be read because the secret keying
material, however generated, has been destroyed by the time such
keying material is sought after.  For example, in a secure telephone,
forward secrecy begins when you hang up the phone, because the key
inside it, generated, say, by a D-H key exchange, is destroyed when
you put down the receiver.

For PGP and PEM, forward secrecy begins when you destroy all copies of
your private key.  This will leave you without a private key, of
course, and so should be done only after a key change.  The forward
secrecy also applies to the (previous) holder of the private key.  If
your only copy of encrypted email, for example, that you have after
you destroy your private key is just the encrypted email, then you
won't be able to read your own mail.  Therefore, all old traffic
addressed to a public key needs to be re-encrypted or kept in
plaintext.

This is one of the main reasons for periodic key changes, to achieve
forward secrecy for email.  After I change keys and destroy my old
private key, now the _only_ way to decrypt the messages is to derive
the private key from the public key--in RSA, to factor the modulus.
This is computational forward secrecy.  

Diffie-Hellman key exchange also yields computational forward secrecy,
because the session key generated can be derived assuming a device to,
say, take discrete logs on the order of the size of the modulus.

If messages have been intercepted and logged, no seizure of equipment
will yield the private key.  Forward secrecy protects you, therefore,
from violence, be that the procedurally mitigated violence of the
courts or the arbitrary violence of another party.

Here, then, is the connection back to the original issue.  The courts
distinguish between acts of speech (fifth amendment protection) and
supplying objects, such as a subpoena provide the key to a safety
deposit box.  As Marc Rotenberg once put it to me, the court cannot
require you to incriminate yourself, but they can require you to
participate in your own downfall.  Forward secrecy protects you
against court order, because you cannot be held in contempt of court
for not providing something that doesn't exist.  If you destroy your
keys in a timely fashion, your exposure is limited to the time since
the last key change.

Needless to say, there's no real standard software support for forward
secrecy for email.  A good cryptographic system should store the
plaintext of an encrypted communication in a separately encrypted
place.  On Unix, one can use Matt Blaze's CFS to keep all of one's
mail on, but even then there's no support for keeping encrypted mail
around in such a way that allows you to prove, _without using the
private key_, which will be destroyed at some time, that a particular
ciphertext matches any particular plaintext.

Consider PGP, where the outer wrapper can only be decrypted with a
private key.  Once that public key is gone, that message is now
useless even as verification for anything, unless the session key is
also stored separately.  If you have the session key, the encrypted
session key can be generated by an application of the public key, and
verified to match.

Assuming you have the public key, that is.  If the public key has been
published, then you can safely assume that it can be retrieved.  To
achieve unconditional forward secrecy, however, requires that the
public key _never_ be published, but only given to correspondents.  In
this situation, one achieves unconditional forward secrecy when you
destroy both private and public keys and all your correspondents
destroy the public keys.

An aside: in a two cipher system, you only get the unconditional
security with respect to the public key cipher.  The secret key cipher
(like IDEA) is still only computationally protected, since the entropy
of the plaintext is not maximal.  This, however, is still an
advantage, since there's more uncertainty about the long term security
of the algebraically based public key ciphers than there is about the
secret key ciphers.

Now, as far as I know, there's _NO_ support anywhere for preventing
the correspondent to publishing the private key.  Even software which
was not informationally secure, which simply flagged a public key as
"not for further distribution", would be a help, since it would then
require custom software in order to distribute.  At the very least it
would allow mutually trusted parties to prevent accidents.

Another technique would be to develop a keying system in which
distribution of public keys were tied to the public keys of the
correspondent.  This might not prevent (informationally) the key from
being distributed, but one would want to it identify the distributor.

Eric