Adam Back and Ian Brown
The confidentiality of encrypted data depends on the secrecy of the key needed to decrypt it. If one key is able to decrypt large quantities of data, its compromise will be disastrous. We suggest three methods of reducing this vulnerability by using a series of keys to protect information. Short-lifetime keys, automatically generated and securely erased after expiry, limit damage to the lifetime of a compromised key. One-time keys protect only one message. Secure SMTP uses new keys for the exchange of every message. These techniques, used separately or together, increase data security by reducing the information revealed upon the compromise of a private key.
Public key cryptosystems like RSA [9] allow two strangers to communicate privately. Each user has a public key that is widely disseminated, and a private key which they keep secret. A message encrypted with a public key can only be decrypted with the related private key. The confidentiality of all messages encrypted with a public key rests on the secrecy of the associated private key.
Online systems such as Secure IP [2] can create new public/private key pairs for every communication using a system like Diffie-Hellman [5] to negotiate a key. If a private key is compromised, only the specific session it protected will be revealed to an attacker. This desirable property is called forward secrecy. The security of previous or future encrypted sessions is not affected. Private keys are securely deleted after use. Without these keys, there is no way data can be decrypted.
It is more difficult to make store and forward systems like e-mail forward secret, as they rarely make direct connections between a message sender and its recipient. In a typical e-mail encryption system, users create a long-term key pair and publish the public key on their Web page, in a directory, or via other methods. While the use of long-term keys reduces the administrative burden of key distribution, the practice introduces vulnerabilities. If a public key is used for several years, as is common with systems such as PGP [1], compromise of the private key will allow an attacker to decrypt any message captured during that time.
This paper proposes several methods of reducing the vulnerabilities introduced by use of long-term keys. The methods are presented in increasing order of sophistication and security.
Some public-key algorithms allow users to digitally sign data with a private key. Anyone can use the corresponding public key to verify the signature.
Public keys are usually labelled with information on their keyholder. Other users can sign this information, certifying their belief that it is correct. Hierarchical key certification systems use central Certification Authorities to certify many keys. Distributed systems such as PGP can build up a ‘web of trust’ where users certify friends’ and colleagues’ keys.
Identity certificates are expensive to collect, particularly in distributed systems, as they should only be issued after thorough identification of a user. Keys used to sign public keys should therefore be as long-lived as possible. Other applications, like making a contract, also require signatures to be valid for extended periods of time.
Because of the different properties required of encryption keys and signature keys, some systems use separate keys for each purpose. Encryption keys should be replaced as quickly as possible, to minimise risk of later decryption of data, while signature keys tend to require long validity periods. Some public key algorithms provide only digital signatures, or only encryption services, thus necessitating separate keys in any case.
Using a series of encryption keys, each with a short lifetime, reduces the information revealed by the compromise of any one private key because each key protects less data. When a public key expires, the corresponding private key is securely wiped. Once the private key has been deleted, an attacker cannot decrypt captured traffic, even with the key owner's full co-operation. There is a trade-off for the user: the cost of generating and distributing a new encryption key against the security advantage obtained by earlier key expiry.
Key generation is typically a time-consuming operation. A background process could automatically generate a new key when a user’s current key is close to expiration.
For some algorithms there are trade-offs that can speed up key generation with minimal reduction in security. With Elgamal [7], for example, the expensive key component to generate is the public prime modulus. A group of keys can share a common public modulus with no negative security implications other than that the key then presents a fatter target for pre-computation attacks. Multiple forward secret keys can therefore use the same prime modulus with minimal security reduction.
Key distribution can be eased by submitting new keys to key directories, where they will be available for other users to retrieve. Submission and retrieval can be performed automatically by software. Expired public encryption keys can be deleted by users and keyservers to save space.
If there is more than one valid encryption key available for a user, the key nearest its expiration date should be used. This limits the time during which the corresponding private key will be available to an attacker.
The latest versions of PGP allow linked signature and encryption key pairs, but gives them the same validity period. Linked keys with different expiry dates are handled correctly, however. This allows us to implement software which can interoperate with PGP users. Signature keys that are long-lived and certified by other users allow a web of trust to build up. Encryption keys are short-lived and certified by the user's signature key. This solves a problem with previous versions of PGP, where creating a new key pair meant you lost all the certifications of your previous public key. Our software can regularly generate new encryption keys and interoperate with other compliant implementations
Unfortunately, this behaviour is more difficult to implement with X.509 [3] certificates. They do not have an equivalent dual-key certificate format or the ability to have different-lifetime keys present. An X.509 system would require separate certificates for encryption and signature keys, and the ability to retrieve certificates based on their keyUsage extension. This is not supported by most X.509 storage formats.
Taking short-term keys to their logical conclusion, a different key could be used to protect every message. Schneier and Hall [11] suggested a user could make several public keys available in a directory. After a key was retrieved by another user, it would be deleted. This requires message senders to have online access to a directory. Not all e-mail users have this facility.
An off-line scheme is more compatible with the store and forward nature of e-mail. Every time a user sent a message, they could include a new public key for the recipient to encrypt any reply with.
Users would still possess a relatively long-lived encryption key. If Alice were writing to Bob for the first time, she would encrypt her message with his long term key. She would also include a newly created public key. Bob would use this new key the next time he wrote to Alice, and Alice would decrypt it with the associated private key. When Alice sent Bob a new public key and received a reply encrypted with it, she would securely delete the previous private key.
This scheme would use each key pair exactly once if correspondants communicated in sequence. If Bob wanted to send Alice another message before receiving her reply, he would need to use the same public key. Compromise of the associated private key would therefore allow an attacker to decrypt more than one message. This is still a great improvement over keys which are valid for days or longer.
If Alice writes to a large number of people only once or twice, she will generate a large number of private keys that will never be needed. One-time keys should therefore have a short lifetime. As a user's collection of private keys grows, she may wish to reduce the lifetime of new keys.
A secure Simple Mail Transfer Protocol [8] could be used to protect a message from the sender's mail hub directly to its destination. Because the delivery protocols would be interactive, new keys could be generated for the transfer of every message, giving immediate forward secrecy. The use of forward secrecy between mail hubs has a different security focus, as keys reside on a network server and are typically outside the e-mail user's control.
Introducing forward secrecy at the mail hub level does not require extra complexity to be introduced into the mail client and e-mail encryption software. It also avoids the complexity of modifying key servers, as forward secrecy and a second layer of encryption and authentication is provided on a host to host rather than user to user basis. There is some value even in unauthenticated forward secrecy. Mounting an active attack to compromise such a system is far harder than passive eavesdropping. Authentication would require a public key infrastructure to be in place to allow host key authentication.
As host-level public key infrastructures such as Secure DNS [6] are not yet in place, a more practical method would be to make use of the e-mail application's certification model (the PGP web of trust or the hierarchical Certification Authority model). This would move ownership and control of the authentication keys to the user's security domain, rather than host-based security which has different security purposes and threat models.
It is possible to have non-interactive, one way communications between the sending mail client and SMTP host, and between receiving SMTP host and mail client. This matches the store and forward nature of SMTP mail delivery. There may be some local store and forward hops on the way to the secured SMTP delivery over the Internet, and some further local hops after receipt (as shown in figure 1).
The internal mail hubs shown illustrate a typical e-mail delivery system topology inside an organisation. Any communications are one-sided, and do not require replies. The secure mail hubs are SMTP servers which send messages out through the organisation's firewall.
The topology of the communications suggests that the sending mail client can send a message to the secure mail hub inside its organisation, but can’t expect a reply. The receiving secure mail hub can send a message to the receiving mail client, but can’t expect a reply.
An interim solution allowing manual setup of a transport layer secure mail system would be to tunnel SMTP links via SSH (Secure SHell) [12]. SSH has facilities to tunnel arbitrary TCP/IP traffic, so tunnelling SMTP via SSH could be achieved easily and quickly using SSH. The SSH key infrastructure is manually configured. Administrators are expected to put in place SSH asymmetric keys for authentication which are verified by other means. Typically this is by exchange of PGP signed and/or encrypted e-mail. SSH is an application for interactive use (being at core a secure TELNET replacement), and so provides forward secrecy by the use of Diffie-Hellman.
TLS (Transport Layer Security) [4] could also be used to create a secure SMTP system. Again TLS provides forward secrecy, by use of Diffie-Hellman, or by the use of temporary RSA keys. Authentication can be provided by the use of X.509 server and client certificates.
The great advantage of this scheme is that it has forward secrecy between the secure hubs. The keys used to secure this link are discarded after use. The message would be further encrypted inside the link between the secured mail hubs by the sending client, using longer-term keys. An attacker cannot eavesdrop on this ciphertext even if he has the private key needed to decrypt it. The authentication prevents him using a man-in-the-middle attack to obtain the ciphertext.
To compromise the security of the system, the attacker must breach security on one of the mail hubs, avoid detection for the period he is able to obtain ciphertext, and still obtain the recipient's private key.
Ideally, secure SMTP would be combined with short-term encryption keys to provide forward secrecy between mail clients and secure mail hubs. Internal links are generally more secure, however, than Internet connections. It would also allow users more control over the keys providing forward secrecy, maintaining security even after a succesful attack on a secure mail hub.
The three methods outlined all increase the security of encrypted messages, by reducing the information revealed upon the compromise of a private key. Short-term encryption key pairs limit the damage to the lifetime of the compromised key, and can be used with existing software. One-time keys reduce vulnerability to a very small number of messages, but require minor modifications to software.
Secure SMTP uses new keys for every session, but relies on the security of the external mail hub. It can be implemented using the current SMTP standard, but would only be effective when supported by the sender and recipient of a message. It may be simpler to wait for the secure version of the underlying transport protocol - IP - which will protect all higher-level standards rather than requiring separate software for each one. The data being transported can always be further protected with extra security measures.
Short-term keys and secure SMTP would also mitigate the impact of any of the myopic key escrow legislation being pursued by various governments. Intelligence agencies are demanding copies of users' private keys to allow covert surveillance of encrypted messages [10]. They would find it difficult to manage a collection of long-term keys, but virtually impossible if users regularly generated new key pairs or SMTP servers used new keys for every message.
Agencies would instead be required to mount active attacks such as physical compromise of computers. Small, targeted use of such attacks is trivial. Indiscriminate surveillance is not. This is a far healthier state of affairs for a democratic society.
The US administration’s previous attempts to impose escrow schemes have been sunk by industry and citizen protest. We hope techniques such as those described here can help derail any further attempts to turn the Internet into a global surveillance system.
1. Atkins, D., Stallings, W. and Zimmerman, P. PGP Message Exchange Formats. RFC 1991, Aug. 1996.
2. Atkinson, R. Security Architecture for the Internet Protocol. RFC 1825, Aug. 1995.
3. CCITT. Recommendation X.509: The Directory - Authentication Framework. 1988.
4. Dierks, T. and Allen, C. The TLS Protocol. Internet draft draft-ietf-tls-protocol-05.txt. November 1997.
5. Diffie, W. and Hellman, M. New directions in cryptography. IEEE Transactions on Information Theory 22,6 (Nov. 1976), 644-654.
6. Eastlake, D. and Kaufman, C. Domain Name System Security Extensions. RFC 2065, Jan. 1997.
7. Elgamal, T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31,4 (Jul. 1985), 469-472.
8. Postel, J. Simple Mail Transfer Protocol. RFC 821, Aug. 1982.
9. Rivest, R., Shamir, A. and Adleson, L. A method for obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM 21,2 (Feb. 1978), 120-126.
10. Schneier, B. and Banisar, D. The Electronic Privacy Papers: Documents on the Battle for Privacy in the Age of Surveillance. John Wiley & Sons, New York, 1997.
11. Schneier, B. and Hall, C. An Improved E-mail Security Protocol. 13th Annual Computer Security Applications Conference. ACM Press, New York, 1997, pp. 232-238.
12. Ylonen, T., Kivinen, T. and Saarinen, M. SSH Transport Layer Protocol. Internet draft draft-ietf-secsh-transport-03.txt. November 1997.