\documentclass[times,10pt,twocolumn]{article}
\usepackage{latex8}
\usepackage{times}

\pagestyle{empty}

\begin{document}

\title{An Improved E-Mail Security Protocol}
\author{Bruce Schneier \qquad Chris Hall\\
Counterpane Systems\\
101 East Minnehaha Parkway\\
Minneapolis, MN  55419\\
{\tt \{schneier,hall\}@counterpane.com}}


\maketitle
\thispagestyle{empty}

\begin{abstract}
    Current e-mail security systems base their security on the secrecy of
    the long-term private key.  If this private key is ever compromised, an
    attacker can decrypt any messages---past, present, or
    future---encrypted with the corresponding public key.  The system
    described in this paper uses short term private-key/public-key key
    pairs to reduce the magnitude of this vulnerability.
\end{abstract}

\Section{Introduction}

E-Mail systems such as PGP \cite{Zim95,Sch95,Gar95,Sch96},
PEM \cite{Lin93,Ken93,Bal93,Kal93,Sch95,Sch96},
Entrust \cite{Cur96,Oor96}, and S/MIME \cite{RSA96,Dus96} use hashed
passphrases to protect the private key in a public-key encryption system.
These systems were designed with the intention that the user generates a
public/private key pair, and uses that pair for a long period of time.  If
an attacker manages to obtain the ling-term private key, then the security
of the system is severely compromised; he can use it to decrypt and read
all electronic communications encrypted with the corresponding public key,
past, present, and future.

This sort of attack, while expensive, can be very costly to the victim.
In this paper we focus on protocols which minimize the amount of information
gained by an attacker in the private key.   These are store-and-forward
systems (e.g., as e-mail encryption programs), where the encryption is meant
to protect a message in transit.

\Section{Points of Entry}

Most popular e-mail encryption programs use a combination of public-key and
private-key encryption.  These systems use symmetric-key encryption, such
as DES \cite{NBS77}, IDEA \cite{LMM91}, or Blowfish \cite{Sch94}, to encrypt
the messages and public-key encryption, such as RSA \cite{RSA78} or ElGamal
\cite{ElG85}, to encrypt the key.  Details of the cryptography involved in
these systems can be found in \cite{Sti95,Sch95,Sch96}.

An attacker who wishes to decrypt a message has several ``points of entry''
they can use to try and decrypt the message:
\begin{itemize}
    \item[(1)]  Guess or deduce the one-time symmetric encryption key.
    \item[(2)]  Mathematically derive the recipient's private key.  For RSA,
    this means factoring the recipient's public modulus and using the
    information to deduce the private key.
    \item[(3)]  Obtain the recipient's passphrase which protects their
    private key.  Then, use it to obtain the private key and thus decrypt
    the message.  There are several ways to do this including guessing,
    monitoring keystrokes with a Trojan-horse program introduced into the
    recipient's computer, TEMPEST-based attacks, or even bribing the recipient
    to reveal his passphrase.
\end{itemize}
There are other attacks against the message: attacking the sender's computer
through a variety of means, obtaining a copy of the message after it has
been printed, convincing the receiver (or sender) to send an unencrypted
copy of the message across an insecure network, etc.  This research
concentrates on attacks against the recipient's private key.

If we assume that a one-time symmetric encryption key is truly random (or at
least independent of other one-time encryption keys), then the Attack (1)
will not compromise the entire system.  The attacker will only be able to use
the encryption key that he obtains to decrypt the one message, but that
will not help him to decrypt other messages.  Thus, we are not really
interested in modifying how current systems solve this problem.

Attacks (2) and (3) on the system represent the sort of global attacks
mentioned
above.  If an attacker succeeds in either attack, then he can use the
information hs obtains to decrypt all messages---past, present, and
future---sent
to the recipient.  In addition, some systems have the added weakness that the
attacker can use the information to forge signatures on the recipient's behalf.
It is these ``points of entry'' which we focus on closing (or at least
shrinking).


\Section{Notation}

Before introducing protocols we must first introduce some notation.

\begin{itemize}

\item[] {\bf Sophie Germain prime.}  A Sophie Germain prime of first order
    is a prime $p$ such that $2p+1$ is also prime.  For second order Sophie
    Germain primes, $2(2p+1)+1=4p+3$ is also prime and a similar pattern
    holds for general $n$-order primes.

\item[] {\bf $E_k(P)$.}  The encryption of the plaintext $P$ with a
    symmetric encryption algorithm and key $k$.

\item[] {\bf $D_k(C)$.}  The decryption of the ciphertext $C$ with a
    symmetric encryption algorithm and key $k$.

\item[] {\bf $GF(p^n)$}  The Galois Field with $p^n$ elements.
\end{itemize}


\Section{Multiple Encryption Keys}

In RSA, knowledge of the private exponent is equivalent to knowledge of the
factorization of the modulus \cite{Sti95}.  Every message encrypted with the
public exponent is vulnerable if the attacker gains knowledge of the private
exponent.  One solution to this problem is to use multiple short-lived
public/private key pairs.  Thus, a key pair could be valid for a short period
of time, say a day, or valid for only one message.  Then an attacker who
deduces
the private key for decrypting one message can decrypt a few other messages at
best, i.e. only those other messages sent during the lifetime of the key pair.

For RSA, picking a new key pair means picking a new modulus in addition to
picking
new public/private exponents.  This involves generating two large prime
numbers,
and can be a costly operation on most computers \cite{Sch95,Zim95}.  Hence,
RSA
may not be suitable for this kind of e-mail encrytion scheme.

There are actually several possible solutions to short-lived public/private
keys.  In addition to using RSA with different exponents and moduli, one
can also use a form of Diffie-Hellman key exchange first published in the
SKIP protocol \cite{AMP96}.  Consider the following protocol in which Alice
publishes several public keys for people to use to send messages to her:

\begin{itemize}
    \item[(1)]	Alice chooses a first-order Sophie Germain prime $p$ and a
	primitive element $g$ of the multiplicative group of the field
$GF(2p+1)$.
    \item[(2)]   Alice chooses several random exponents $e_1,\ldots,e_k$ and
    computes $PK_i=g^{e_i}\pmod{p}$ for $i=1,\ldots,k$.
    \item[(3)]	Alice assigns a lifetime to each key so that at most two
    keys are valid at any point in time, and every key is valid for only a
    short period of time, say a day.  Alternatively, the key could only be
    good for one message.
    \item[(4)]	Alice publishes the $PK_i$, lifetimes, $p$, and $g$ as her
	public keys and stores the $e_i$ as her private keys.
\end{itemize}

Note that in Step (2) Alice is essentially performing the first half of a
Diffie-Hellman key exchange.  Now suppose that Bob wishes to send a message
to Alice.  He performs the following steps:

\begin{itemize}
    \item[(5)]  Bob selects a public key from Alice.  If the keys have short
    lifetimes, he selects the one with the appropriate lifetime.  If they keys
    are one-time keys, he selects the next key in the list (and then Alice's
    computer deletes it from the list).
    \item[(6)]	Bob chooses a random exponent $e_b$ and computes
    $PK_b=g^{e_b}\pmod{p}$.
    \item[(7)]	Bob computes $k=PK_i^{e_b}\pmod{p}$ and uses the result as
    the private encryption key for the message he wishes to send.
    \item[(8)]	Bob encrypts his message $M$ with the key $k$ and sends
    $PK_i,PK_b,E_{k}(M)$ to Alice.
\end{itemize}

Once Alice receives the message she performs the following steps:

\begin{itemize}
    \item[(9)]	Alice looks up the private key $e_i$ that corresponds to
    the $PK_i$ in the message sent to her by Bob.
    \item[(10)]	Alice checks the lifetime of the key against the time that
	Bob sent the message.  If she doubts that the message was sent
while the
	key was valid, then she can choose whether or not to decrypt the
message.
	If she no longer has the decrypting key because she threw it away when
	it expired, then she can simply ask Bob to resend the message.
    \item[(11)]	She computes $k=PK_b^{e_i}\pmod{p}$ and uses the result to
    decrypt the message Bob sent her: $M=D_{k}(E_{k}(M))$.
\end{itemize}

If Alice wants to she can even choose a different Sophie Germain prime for
each public key she publishes.

This kind of system provides a way to minimize the number of encrypted
messages that are common to any public/private key pair.  The fewer
messages tied to a key pair, the fewer messages that can be decrypted if
an attacker recovers the private key.

Once Alice has a way of generating multiple encryption keys she still needs
a way of distributing them.  After generating a list of one-time public
encryption keys Alice can sign each of them with her long-term signature
key and then upload them to a server.  Ideally the server should accept
network-based requests to obtain a public key for Alice.  Once it receives
such a request it should pick the current key from Alice's list, according
to the lifetimes specified by Alice, and sends it to the recipient.  When a
key expires the server should throw away the key in order to conserve space.


\Section{Key Management}

Whether a user has one private decryption key or many, key management is a
difficult issue.  Rather than forcing a user to memorize their private
decryption key, current systems allow the user to chose a passphrase which
the system then uses to encrypt the private decryption key.  Then, whenever
the user wants to decrypt a message sent to him, he uses his passphrase
to decrypt the private decryption key and then decrypt the message.


\SubSection{Multiple Passphrases}

The other attack we mentioned was guessing the user's passphrase.  In most
systems, the user's passphrase is not directly used to encrypt their private
key.  Rather, the passphrase is hashed with a salt and the resulting hash
is used.  Thus, there are actually two different attacks against the
passphrase:

\begin{itemize}
\item[1.]	Guess the encryption key used to encrypt a particular
private key.
This amounts to guessing all or part of the result of hashing the actual
passphrase with the salt.
\item[2.]	Guess the actual passphrase.  Then given any salt, the
attacker can
deduce the corresponding encryption key.
\end{itemize}

The former attack is clearly no harder than the latter because it is trivial
to find the salted hash of the passphrase given the passphrase and salt value.
However, if a cryptographic hash function is used, then the first attack is not
equivalent to the second, i.e. an attacker cannot easily derive other salted
hash values of the passphrase given one salted hash value.  This suggests that
we could encrypt multiple private keys with the same passphrase as long as we
used a different salt for each exponent.  The system would be more secure than
if we used the same salt for each key.

While using different salts protects against the first attack, it does not
protect against the second attack.  An alternative approach is to use an
entirely different passphrase for each private key.  Since each public/private
key pair is used to encrypt only one message, each message will be independent
of every other message in an attack on the passphrase.  If an attacker manages
to guess a passphrase, then s/he can only use it to find one private key and
hence decrypt only one message.

However, there is a difficulty with the latter suggestion.  Each passphrase
has to be remembered.  For even a moderate number of public/private key
pairs this can be a fairly daunting task.  People are likely to forget some
of their passphrases, or choose passphrases that are similar.  The former
has the disadvantage that someone would not be able to decrypt all messages
sent to them, and the latter has the disadvantage that an attacker may be
able to derive other passphrases with only a little bit of effort once they
obtain one.  A mix of the above two solutions seems to provide the best
solution.

A user uses one passphrase to protect several private keys.  For each key,
they use a different salt.  Since the salt and passphrase are used to
generate an encryption key for each private key, the different salts
protect the user against the first attack listed above.  If the user
minimizes the number of private keys they protect with each passphrase,
then they also minimize the amount of damage done when an attacker guesses
a passphrase.  Since not every private key is protected by the same
passphrase, the user gains partial protection against the second attack
listed above.

If the system is designed properly, then the user could have to remember
only one or two passphrases at any point in time.  Each time the user
generates a new set of public/private key pairs they can choose a new
passphrase to protect the set.  As the set of keys expire the user can
throw them away until the entire set is empty.  Since a user really only
needs to generate a new set when their most of the keys from the previous
one are about to expire, they only need to keep track of at most two sets
of keys at any point in time.


\Section{Conclusion}

As we point out in previous sections, current encryption programs have the
common weakness that obtaining a user's private encryption key can cause
extensive damage.  We pointed out the various ways that an attacker can learn
the private encryption key and also gave suggestions as to how to minimize the
damage done by the respective attacks.  In general, our suggestions amount to
minimizing the amount of information that is protected by an encryption key.
When combined with long term signature keys, a powerful e-mail security system
can be written.

\begin{thebibliography}{99}
\setlength{\itemsep}{-1ex}\small

\bibitem{AMP96} A. Aziz, T. Markson, H. Prafullchandra, "Simple
Key-Management for Internet Protocols (SKIP)," Internet-Draft, work in
progress, August 1996.
%{\tt ftp://ds.internic.net/internet-drafts/draft-ietf-ipsec-skip-07.txt}

\bibitem{Bal93}  D. Balenson, ``Privacy Enhancement for Internet
Electronic
Mail: Part III---Algorithms, Modes, and Identifiers,'' RFC 1423, Feb 1993.

\bibitem{Dus96} S. Dusse, ``S/MIME Message Specification: PKCS Security
Services for MIME,'' IETF Networking Group Internet Draft, Sep 1996.
%{\tt ftp://ietf.org/internet-drafts/draft-dusse-mime-msg-spec-00.txt}

\bibitem{ElG85}  T. ElGamal, ``A Public-Key Cryptosystem and a Signature
Scheme Based on Discrete Logarithms,'' {\it IEEE Transactions on Information
Theory,} V. IT-31, n. 4, 1985, pp. 469--472.

\bibitem{Cur96}  I. Curry, ``Entrust Overview, Version 1.0,'' Entrust
Technologies, Oct. 96.
%{\tt http://www.entrust.com/downloads/overview.pdf}

\bibitem{Oor96}  P.C. van Ooorschot, ''Standards Supported by Entrust,
Version 2.0,'' Entrust Technologies, Dec 1996.
%{\tt http://www.entrust.com/downloads/standards.pdf}

\bibitem{Gar95} S. Garfinkel, {\it PGP: Pretty Good Privacy}, O'Reilly
\& Associates, 1995.

\bibitem{Kal93}  B.S. Kaliski, ``Privacy Enhancement for Internet
Electronic
Mail: Part IV---Key Certificates and Related Services,'' RFC 1424, Feb 1993.

\bibitem{Ken93}  S.T Kent, ``Privacy Enhancement for Internet Electronic
Mail: Part II---Certificate Based Key Management,'' RFC 1422, Feb 1993.

\bibitem{LMM91}  X. Lai, J. Massey, and S. Murphy, ``Markov Ciphers and
Differential Cryptanalysis,'' {\it Advances in Cryptology---CRYPTO '91},
Springer-Verlag, 1991, pp. 17--38.

\bibitem{Lin93}  J. Linn, ``Privacy Enhancement for Internet Electronic
Mail: Part I---Message Encipherment and Authentication Procedures,'' RFC 1421,
Feb 1993.

\bibitem{NBS77}  National Bureau of Standards, NBS FIPS PUB 46, ``Data
Encryption Standard,'' National Bureau of Standards, U.S. Department of
Commerce, Jan 1977.

\bibitem{RSA78}  R. Rivest, A. Shamir, and L. Adleman, ``A Method for
Obtaining Digital Signatures and Public-Key Cryptosystems,'' {\it
Communications
of the ACM}, v. 21, n. 2, Feb 1978, pp. 120--126.

\bibitem{RSA96}  RSA Data Security, Inc., ``S/MIME Implementation Guide
Interoperability Profiles, Version 2,'' S/MIME Editor, Draft, Oct 1996.
%{\tt ftp://ftp.rsa.com/pub/S-MIME/IMPGV2.txt}

\bibitem{Sch94}  B. Schneier, ``Description of a New Variable-Length
Key,
64-Bit Block Cipher (Blowfish),'' {\it Fast Software Encryption, Cambridge
Security Workshop Proceedings}, Springer-Verlag, 1994, pp. 191-204.

\bibitem{Sch95} B. Schneier, {\it E-Mail Security,} John Wiley \& Sons,
1995.

\bibitem{Sch96}  B. Schneier, {\it Applied Cryptography, Second
Edition},
John Wiley \& Sons, 1996.

\bibitem{Sti95}  D. Stinson, {\it Cryptography Theory and Practice},
CRC Press, 1995, pp. 138--145.

\bibitem{Zim95} P. Zimmermann, {\it The Official PGP User's Guide}, MIT
Press, 1995.

\end{thebibliography}

\end{document}

