Reducing vulnerability to private keycompromise
Adam Back and Ian Brown
The confidentiality of encrypted data depends on thesecrecy of the key needed to decrypt it. If one key is able todecrypt large quantities of data, its compromise will bedisastrous. We suggest three methods of reducing thisvulnerability by using a series of keys to protect information.Short-lifetime keys, automatically generated and securely erasedafter expiry, limit damage to the lifetime of a compromised key.One-time keys protect only one message. Secure SMTP uses new keysfor the exchange of every message. These techniques, usedseparately or together, increase data security by reducing theinformation revealed upon the compromise of a private key.
Introduction
Public key cryptosystems like RSA [9] allow two strangers tocommunicate privately. Each user has a public key that is widelydisseminated, and a private key which they keep secret. A messageencrypted with a public key can only be decrypted with therelated private key. The confidentiality of all messagesencrypted with a public key rests on the secrecy of theassociated private key.
Online systems such as Secure IP [2] can create newpublic/private key pairs for every communication using a systemlike Diffie-Hellman [5] to negotiate a key. If a private key iscompromised, only the specific session it protected will berevealed to an attacker. This desirable property is calledforward secrecy. The security of previous or future encryptedsessions is not affected. Private keys are securely deleted afteruse. Without these keys, there is no way data can be decrypted.
It is more difficult to make store and forward systems likee-mail forward secret, as they rarely make direct connectionsbetween a message sender and its recipient. In a typical e-mailencryption system, users create a long-term key pair and publishthe public key on their Web page, in a directory, or via othermethods. While the use of long-term keys reduces theadministrative burden of key distribution, the practiceintroduces vulnerabilities. If a public key is used for severalyears, as is common with systems such as PGP [1], compromise ofthe private key will allow an attacker to decrypt any messagecaptured during that time.
This paper proposes several methods of reducing thevulnerabilities introduced by use of long-term keys. The methodsare presented in increasing order of sophistication and security.
Encryption and signature keys
Some public-key algorithms allow users to digitally sign datawith a private key. Anyone can use the corresponding public keyto verify the signature.
Public keys are usually labelled with information on theirkeyholder. Other users can sign this information, certifyingtheir belief that it is correct. Hierarchical key certificationsystems use central Certification Authorities to certify manykeys. Distributed systems such as PGP can build up a web oftrust where users certify friends andcolleagues keys.
Identity certificates are expensive to collect, particularlyin distributed systems, as they should only be issued afterthorough identification of a user. Keys used to sign public keysshould therefore be as long-lived as possible. Otherapplications, like making a contract, also require signatures tobe valid for extended periods of time.
Because of the different properties required of encryptionkeys and signature keys, some systems use separate keys for eachpurpose. Encryption keys should be replaced as quickly aspossible, to minimise risk of later decryption of data, whilesignature keys tend to require long validity periods. Some publickey algorithms provide only digital signatures, or onlyencryption services, thus necessitating separate keys in anycase.
Short-term encryption keys
Using a series of encryption keys, each with a short lifetime,reduces the information revealed by the compromise of any oneprivate key because each key protects less data. When a publickey expires, the corresponding private key is securely wiped.Once the private key has been deleted, an attacker cannot decryptcaptured traffic, even with the key owner's full co-operation.There is a trade-off for the user: the cost of generating anddistributing a new encryption key against the security advantageobtained by earlier key expiry.
Key generation is typically a time-consuming operation. Abackground process could automatically generate a new key when ausers current key is close to expiration.
For some algorithms there are trade-offs that can speed up keygeneration with minimal reduction in security. With Elgamal [7],for example, the expensive key component to generate is thepublic prime modulus. A group of keys can share a common publicmodulus with no negative security implications other than thatthe key then presents a fatter target for pre-computationattacks. Multiple forward secret keys can therefore use the sameprime modulus with minimal security reduction.
Key distribution can be eased by submitting new keys to keydirectories, where they will be available for other users toretrieve. Submission and retrieval can be performed automaticallyby software. Expired public encryption keys can be deleted byusers and keyservers to save space.
If there is more than one valid encryption key available for auser, the key nearest its expiration date should be used. Thislimits the time during which the corresponding private key willbe available to an attacker.
The latest versions of PGP allow linked signature andencryption 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 caninteroperate with PGP users. Signature keys that are long-livedand certified by other users allow a web of trust to build up.Encryption keys are short-lived and certified by the user'ssignature key. This solves a problem with previous versions ofPGP, where creating a new key pair meant you lost all thecertifications of your previous public key. Our software canregularly generate new encryption keys and interoperate withother compliant implementations
Unfortunately, this behaviour is more difficult to implementwith X.509 [3] certificates. They do not have an equivalentdual-key certificate format or the ability to havedifferent-lifetime keys present. An X.509 system would requireseparate certificates for encryption and signature keys, and theability to retrieve certificates based on their keyUsageextension. This is not supported by most X.509 storage formats.
One-time keys
Taking short-term keys to their logical conclusion, adifferent key could be used to protect every message. Schneierand Hall [11] suggested a user could make several public keysavailable in a directory. After a key was retrieved by anotheruser, it would be deleted. This requires message senders to haveonline access to a directory. Not all e-mail users have thisfacility.
An off-line scheme is more compatible with the store andforward nature of e-mail. Every time a user sent a message, theycould include a new public key for the recipient to encrypt anyreply with.
Users would still possess a relatively long-lived encryptionkey. If Alice were writing to Bob for the first time, she wouldencrypt her message with his long term key. She would alsoinclude a newly created public key. Bob would use this new keythe next time he wrote to Alice, and Alice would decrypt it withthe associated private key. When Alice sent Bob a new public keyand received a reply encrypted with it, she would securely deletethe previous private key.
This scheme would use each key pair exactly once ifcorrespondants communicated in sequence. If Bob wanted to sendAlice another message before receiving her reply, he would needto use the same public key. Compromise of the associated privatekey would therefore allow an attacker to decrypt more than onemessage. This is still a great improvement over keys which arevalid for days or longer.
If Alice writes to a large number of people only once ortwice, she will generate a large number of private keys that willnever be needed. One-time keys should therefore have a shortlifetime. As a user's collection of private keys grows, she maywish to reduce the lifetime of new keys.
Secure SMTP
A secure Simple Mail Transfer Protocol [8] could be used toprotect a message from the sender's mail hub directly to itsdestination. 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 secrecybetween mail hubs has a different security focus, as keys resideon a network server and are typically outside the e-mail user'scontrol.
Introducing forward secrecy at the mail hub level does notrequire extra complexity to be introduced into the mail clientand e-mail encryption software. It also avoids the complexity ofmodifying key servers, as forward secrecy and a second layer ofencryption and authentication is provided on a host to hostrather than user to user basis. There is some value even inunauthenticated forward secrecy. Mounting an active attack tocompromise such a system is far harder than passiveeavesdropping. Authentication would require a public keyinfrastructure 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 tomake use of the e-mail application's certification model (the PGPweb of trust or the hierarchical Certification Authority model).This would move ownership and control of the authentication keysto the user's security domain, rather than host-based securitywhich has different security purposes and threat models.
It is possible to have non-interactive, one way communicationsbetween the sending mail client and SMTP host, and betweenreceiving SMTP host and mail client. This matches the store andforward nature of SMTP mail delivery. There may be some localstore and forward hops on the way to the secured SMTP deliveryover the Internet, and some further local hops after receipt (asshown in figure 1).
The internal mail hubs shown illustrate a typical e-maildelivery system topology inside an organisation. Anycommunications are one-sided, and do not require replies. Thesecure mail hubs are SMTP servers which send messages out throughthe organisation's firewall.
The topology of the communications suggests that the sendingmail client can send a message to the secure mail hub inside itsorganisation, but cant expect a reply. The receiving securemail hub can send a message to the receiving mail client, butcant expect a reply.
An interim solution allowing manual setup of a transport layersecure mail system would be to tunnel SMTP links via SSH (SecureSHell) [12]. SSH has facilities to tunnel arbitrary TCP/IPtraffic, so tunnelling SMTP via SSH could be achieved easily andquickly using SSH. The SSH key infrastructure is manually configured. Administratorsare expected to put in place SSH asymmetric keys for authenticationwhich are verified by other means. Typically this is by exchange ofPGP signed and/or encrypted e-mail. SSH is an application forinteractive use (being at core a secure TELNET replacement), and soprovides 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 bythe use of temporary RSA keys. Authentication can be provided by theuse of X.509 server and client certificates.
The great advantage of this scheme is that it has forwardsecrecy between the secure hubs. The keys used to secure thislink are discarded after use. The message would be furtherencrypted inside the link between the secured mail hubs by thesending client, using longer-term keys. An attacker cannoteavesdrop on this ciphertext even if he has the private keyneeded to decrypt it. The authentication prevents him using aman-in-the-middle attack to obtain the ciphertext.
To compromise the security of the system, the attacker mustbreach security on one of the mail hubs, avoid detection for theperiod he is able to obtain ciphertext, and still obtain therecipient's private key.
Ideally, secure SMTP would be combined with short-termencryption keys to provide forward secrecy between mail clientsand secure mail hubs. Internal links are generally more secure,however, than Internet connections. It would also allow usersmore control over the keys providing forward secrecy, maintainingsecurity even after a succesful attack on a secure mail hub.
Conclusion
The three methods outlined all increase the security ofencrypted messages, by reducing the information revealed upon thecompromise of a private key. Short-term encryption key pairslimit the damage to the lifetime of the compromised key, and canbe used with existing software. One-time keys reducevulnerability to a very small number of messages, but requireminor modifications to software.
Secure SMTP uses new keys for every session, but relies on thesecurity of the external mail hub. It can be implemented usingthe current SMTP standard, but would only be effective whensupported by the sender and recipient of a message. It may besimpler to wait for the secure version of the underlyingtransport protocol - IP - which will protect all higher-levelstandards rather than requiring separate software for eachone. The data being transported can always be further protectedwith extra security measures.
Short-term keys and secure SMTP would also mitigate the impactof any of the myopic key escrow legislation being pursued byvarious governments. Intelligence agencies are demanding copiesof users' private keys to allow covert surveillance of encryptedmessages [10]. They would find it difficult to manage a collectionof long-term keys, but virtually impossible if users regularlygenerated new key pairs or SMTP servers used new keys for everymessage.
Agencies would instead be required to mount active attackssuch as physical compromise of computers. Small, targeted use ofsuch attacks is trivial. Indiscriminate surveillance is not. Thisis a far healthier state of affairs for a democratic society.
The US administrations previous attempts to imposeescrow schemes have been sunk by industry and citizen protest. Wehope techniques such as those described here can help derail anyfurther attempts to turn the Internet into a global surveillancesystem.
References
1. Atkins, D., Stallings, W. and Zimmerman, P. PGP MessageExchange Formats. RFC 1991, Aug. 1996.
2. Atkinson, R. Security Architecture for the InternetProtocol. RFC 1825, Aug. 1995.
3. CCITT. Recommendation X.509: The Directory - AuthenticationFramework. 1988.
4. Dierks, T. and Allen, C. The TLS Protocol. Internet draftdraft-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 NameSystem Security Extensions. RFC 2065, Jan. 1997.
7. Elgamal, T. A Public Key Cryptosystem and a SignatureScheme Based on Discrete Logarithms. IEEE Transactions onInformation 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 forobtaining Digital Signatures and Public Key Cryptosystems. Communicationsof 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 SecurityProtocol. 13th Annual Computer Security ApplicationsConference. 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.
