Communication between an ESMTP client and server consists of a series of commands and responses that are sent along with the email message. We added a new command to this protocol: the XCRYPT command. This command has a number of parameters that allow a client and server to create secret keys.

The input and output functions of sendmail are modified to encrypt and decrypt protocol messages sent. Below, we describe in detail how the XCRYPT command is used, how the keys are created, and how efficiency is addressed using caching.

The XCRYPT Command

We added the XCRYPT command to ESMTP to allow for the exchange of keys for email encryption. It has a number of parameters:

• version strings: the client and server exchange strings, which indicate the version and name of the preferred encryption algorithm(s) to be used (for example, t32_1.0)
• public keys: the client and server exchange public keys to be used in the Diffie-Hellman key agreement scheme
• nonces: both the client and server generate random integers that are hashed with the shared secret key to produce a new session key for each exchange (details below).

An ESMTP session that supports XCRYPT is shown in Table 1. As the table shows, the XCRYPT exchange requires five extra messages to be added to a normal ESMTP session. When a connection is made between two machines that have the ssmail patch installed, the exchange takes place as follows:

Client(a)		Server(b)	Notes
		220 (address)	1. Server introduction
EHLO (address)			2. Client introduction
		250 XCRYPT	3. Server sends services it supports. Includes XCRYPT with version string.
XCRYPT			4. Client sends version string, public key, nonce
		250 XCRYPT	5. Server sends public key, nonce
XCRYPT OK			6. Client XCRYPT verification
		250 XCRYPT OK	7. Server XCRYPT verification
Encryption starts now

Variable/Key	Public/Private	Notes
strong prime (p)	public	768-bit integer (static, shared)
generator (g)	public	value = 2 (static, shared)
private key (r)	private	randomly-chosen 768-bit integer
public key (K)	public	K = (mod p)
shared secret	private	secret = (mod p)
nonces (n)	public	randomly-chosen 80-bit integers

• The server sends the initial introduction, which contains such information as the machine name and the version of sendmail being used.
• The client sends an EHLO (extended hello) command along with its address. Sending EHLO (rather than SMTP's HELO) indicates that the client sendmail uses ESMTP.
• The server responds to EHLO by providing a list of the ESMTP services that it supports, using XCRYPT to indicate encryption. It also sends the version string (), which reports its available encryption algorithms.
• The client then provides its version string (), which includes the chosen encryption algorithm, along with its public key () and nonce (). This provides the server with enough information to create the shared secret key used for encryption (detailed below).
• The server sends its public key () and nonce (), which the client uses to create the shared secret key.
• If there are no problems with the exchange, the client sends XCRYPT OK. Failure is indicated by XCRYPT FAIL. Should a FAIL be sent in either direction, the session will continue, but the mail will be sent unencrypted.
• If there are no problems on the server side, the server sends XCRYPT OK (else XCRYPT FAIL).

If the server is not capable of using the XCRYPT command, it is not mentioned in the list of supported services. Thus, the client will not respond with its XCRYPT command. Should the client be unable to support the XCRYPT command, this service (as sent by the server) is ignored, and the session continues normally, without encryption.

Creating Shared Secret Keys

Once the necessary information has been exchanged via the XCRYPT commands in ESMTP, the client and server use it to calculate shared secret keys used in encrypting the mail transfer. There are a number of components used in the calculation of the encryption keys, shown in Table 2.

The shared secret is generated using the Diffie-Hellman key agreement [3]. The client a and the server b share a strong prime p and a generator g. The prime and generator are hard-coded into ssmail - they are the values generated for IPSec [13]. For the private keys (, ) both parties select a randomly-generated 768-bit integer that must remain secret. To minimize the risks of an attacker discovering the private keys while they are useful, the keys are regenerated every two hours (this default value can be configured as required).

The client and server generate their public keys using their private key values. The client's public key is , while the server's is . These public keys are exchanged in the XCRYPT transfer described above. To generate the shared secret, the client computes , and the server computes . These two computations yield the same value, a number that must be kept private from other parties. Computing this shared secret is relatively expensive.

At this stage, email could be encrypted using the shared secret. However, for two reasons, there is another step in the process. As detailed below, ssmail is designed to avoid recalculating the shared secret unless absolutely necessary, which ensures that the encryption process is as fast as possible. We wish to be able to reuse the shared secret if the same client/server pair communicate again before either party's public key has changed. This is not a valid solution on its own. Re-using a key is an insecure practice: it increases the likelihood than an attacker could decrypt mail, particularly if a stream cipher is used in the encryption.

To avoid this problem, ssmail uses nonces (numbers used only once in the protocol) to ensure that a fresh private session key is generated for every exchange. The client and server exchange 80-bit randomly-selected integers. The shared secret and both nonces are passed through the Secure Hash Algorithm (SHA-1) [12] to make a 160-bit key. Messages sent from client to server use the first 80 bits as the key, and the last 80 bits are used as the key for the server to client messages.

The Encryption Algorithm

The 80-bit secret keys maintained by the client and server can be used in conjunction with any number of cryptographic algorithms. Originally, ssmail supported SOBER, a stream cipher developed by Greg Rose [15]. SOBER was specifically designed to support fast software encryption. This version of ssmail was never widely deployed, and so SOBER has been replaced. Instead, there are two algorithms supported:

• arrsyfor (compatible with RC4) [16]
• t32 (a faster and stronger derivative of the SOBER cipher) [14]

Increasing Efficiency

Speed was a major concern when designing ssmail. Because ssmail encryption is taking place on mail servers that typically handle a large volume of mail, a slow cryptographic system could paralyse a server. The slowest part of our implementation is the Diffie-Hellman computation of the shared secret (that is, computing ). To avoid recalculating this value for every ESMTP session, we use a cache. Every time a connection is made, each party stores the other party's public key and the shared secret in a cache. If this same machine is contacted later, the costly Diffie-Hellman calculation may not have to be performed again.

The format of the cache is as follows:

Each time a connection is made, this cache is checked. First, the timestamp on this machine's own key pair is checked, and if it is too old (two hours by default), a new key pair is created and the cache is purged. Otherwise, if the other party's public key is found, then the shared secret is reused, saving an expensive recalculation. The shared secret is then passed through a secure hash computation with the nonces, but this calculation is fast. This makes computing a session key feasible for every connection.

If the public key is not found in the cache, then the shared secret is calculated with this new public key, then hashed to produce a session key. The public key and corresponding shared secret are stored in the cache for possible future use.

When a machine updates its private key, the shared secrets in the cache become invalid, as they were based on calculations performed with an outdated (different) key. The cache is simply cleared of all entries.

This caching method vastly increases the speed of encryption for a small network of machines that send mail mostly to each other (such as large corporate mail servers communicating with each other).

Performance

We performed two sets of tests on ssmail. Both tests evaluated sendmail 8.8.8 with ssmail extensions. The SSLeay library [18] version 0.9.0 generated random numbers to perform the Diffie-Hellman calculations and to perform the SHA-1 secure hash function.

The first tests were performed on ssmail with SOBER as the encryption algorithm. The test machine had a Pentium 100 MHz microprocessor and ran Linux 2.0.0. These results are based on sendmail receiving a plain text email of around 64 kilobytes with the key cache already primed (that is, no Diffie-Hellman computation).

Tests on normal sendmail (without ssmail) showed that 63.9% of program time was spent in the collect() function, which reads command input from the network socket. With ssmail installed, this increased to 66%, with total running time increasing by less than 5%. The collect() function performed almost half of the 128,000 calls to crypto_fgetc(), the function that delivers decrypted text using the SOBER algorithm. Similar results were found for sending email as well.

These results may vary for mailers other than sendmail 8.8.8, as sendmail makes extensive use of single character input and output. Other mailers with different methods of text processing, such as line-based methods, may have different overheads.

It must be noted that the Diffie-Hellman computation will slow down mail processing. This computation is performed every two hours (depending on the configuration), and whenever a new machine is contacted. On the Linux machine, this computation took approximately 0.5 seconds of CPU time.

Another set of performance measurements were undertaken after implementing the two new cipher methods (arrsyfor and t32). In the following discussion, all measurements were done on a COMPAQ DeskPro (Pentium Pro) at 233 MHz, compiled with gcc -O3 on Linux 2.0.33.

One of the authors' mail traffic for just over two weeks was analyzed to try to estimate the effect of caching on the Diffie-Hellman computation. Over a period of 372.6 hours, 1,322 email messages were received with a mean size of 14,671 bytes (median 2,950 bytes). Of these, 994 were delivered by the corporate mail hub machine. In the following analysis, we assume the worst possible case. For example, we assume that a new Diffie-Hellman key would have to be computed every two hours. (This could occur if messages arrived steadily.) Furthermore, we assume that none of the communications with other machines (other than the corporate mail hub) were able to use the cached information. This is unlikely, but possible if all other machines sent at most one message each per two-hour cache period.

Let us consider the effect of caching on the Diffie-Hellman calculations. In the case of the corporate mail hub, one calculation is done every two hours, giving 187 key calculations over the test period. This leaves 807 messages sent efficiently using the cache. We must also consider the messages from other machines (assumed to miss the cache), a total of 328. Out of 1322 messages, 515 required the Diffie-Hellman computation, while 808 did not. Thus, the cache saved over 60% of these computations. This is a conservative estimate, and the benefit to the mail hub machine itself could be expected to be much greater.

Each Diffie-Hellman computation took 0.3387 s. Amortized over all email messages, this was an average of 0.1317 s per email message. This is a similar order of magnitude to the total processing time for an average message. Using lightweight Diffie-Hellman key agreement and an aggressive caching strategy adds little overhead to mail processing.

Once the shared secret has been calculated or retrieved from the cache, the session keys must be derived, the encryption algorithm must be keyed independently for each direction, and the traffic must be encrypted. Ignoring the command dialog, the bulk of the encryption applies to the email message contents. Table 3 shows the CPU time in µs taken for the various steps of each of the currently supported encryption algorithms. (Note that t32 is still undergoing changes to make it more secure, and thus its performance is likely to change slightly in the near future.)

SOBER, as used in the earlier round of testing, was somewhat less efficient than arrsyfor, so the total running time of sendmail with the new version of ssmail is expected to increase by less than 3% (not counting the Diffie-Hellman computation).

Related work

There have been a number of projects developed to protect email from eavesdroppers. Our own work was inspired by John Gilmore's Secure Wide Area Network (S/WAN) project [5]. S/WAN is designed to protect IP traffic by adding IPSec protocol support to personal computers. This differs from our work by providing network-layer encryption that can protect more kinds of traffic than just email transmissions. However, ssmail offers a simple and fast solution for email protection that can be easily installed. This is an alternative for systems that cannot handle the overhead of IPSec protocols.

Paul Hoffman has proposed an SMTP extension for privacy and authentication using SSL [7]. If authentication is not used, then his solution is very similar to ssmail. However, Hoffman's scheme has no support for the caching of the shared secret value, which leads to greater overhead from increased public-key calculations.

There have been a number of projects that proposed to embed encryption programs in mail user agents. For example, Paul Leyland and Piete Brooks proposed a secure email project for the JANET network that would imbed PGP into mail user agents [9]. Putting encryption into the user agent rather than the transport agent requires more applications to be modified. Furthermore, they found that the PGP key servers would be unable to keep up with demand.

It is worth mentioning that there have been proposed extensions to SMTP for authentication. John Myers has put forth a system in which the client and server perform an authentication protocol exchange at the start of an SMTP session [11]. As ssmail is not intended to perform authentication, Myers' extension deals with a completely separate issue. It is possible that both SMTP extensions could be used by those systems that demand authentication and privacy and are prepared to handle the protocol overhead.

Limitations

While ssmail provides an effective solution for email privacy, it is has some limitations. Due to the multi-process nature of sendmail, the cache used to speed up key generation is stored on disk. The shared secret stored here is vulnerable to being retrieved and used to decrypt future email transmissions. Should this risk be considered too great, a trade-off in efficiency could be made. The disk cache can be turned off, resulting in a new shared secret for every exchange (but with the cost of the Diffie-Hellman computation). Note, however, that the email itself would also be exposed while stored on the compromised machine. We class this as an active attack, and hence outside the scope of our work.

Because SMTP transfers usually follow similar patterns, certain bytes generated by the encryption algorithm can be determined. For example, a "MAIL From:" command is followed by a "RCPT To:" command. Knowing this plaintext could provide enough information to allow an eavesdropper to determine such facts as the length of the recipient's email address. Any good encryption algorithm should minimize the information leaked from an encrypted session. However, this weakness is worth attention to ensure that the algorithm chosen does not fall prey to this threat.

Another limitation comes from the nature of store-and-forward transfer of email. Mail messages may pass through many servers en route to their destination. ssmail decrypts mail at each server before re-encrypting it for forwarding, so the mail remains unencrypted in the queue. As mail could be stored for an arbitrarily long time, this is a point of vulnerability. One way to reduce this threat is to use another program to encrypt mail during storage in the queue.

Future work

At the time of writing, ssmail is in a beta test version. There are a number of features that we intend to add or improve. We would like to replace the SSLeay random number generator with Peter Gutmann's package [6], which appears to be stronger. ssmail has already been extended to support t32 and RC4, an experience that indicates that porting other stream cipher algorithms should prove straightforward. Lastly, further analysis of traffic characteristics from a major mail hub would prove valuable for better estimating the saving from key caching.

Conclusions

We designed and implemented a fast, non-intrusive method for protecting large quantities of email against passive eavesdropping. We have supplied ESMTP with a key exchange command and added encryption algorithms to sendmail.

Our method has three main advantages:

• ssmail gives users privacy without requiring them to know how to use encryption packages correctly
• ssmail does not add excessive delay to email transmissions
• ssmail does not require widespread deployment of public key infrastructure

Availability

Contact Greg Rose <ggr@qualcomm.com> for information on availability of ssmail. We have implemented it as a patch to sendmail in order to prevent sendmail itself from being restricted by export regulations. At the time of writing, export licenses have been granted for recipients in five countries including the Czech Republic.

References

Author Information

Damian Bentley is currently studying self-modifying computer viruses for honours at the Australian National University. Previously Damian has worked for CSIRO and DSTO (Australian Scientific/Defence research organizations), and for QUALCOMM Australia on cryptography. More details about Damian and his work can be found at https://mehta.anu.edu.au/~bendchon, or he can be emailed at <bendchon@mehta.anu.edu.au>.

Greg Rose joined QUALCOMM in July 1996 as a senior staff engineer and manager, working on cryptography and authentication for the GlobalStar satellite communication project and the CDMA cellular phone system, and to set up the office of QUALCOMM Australia. He is enjoying work immensely. Greg is also Vice President of USENIX. He can be contacted by email at <ggr@qualcomm.com>, and his personal web page is https://people.qualcomm.com/ggr.

Tara Whalen is a researcher investigating network security at the Communications Research Centre Canada. Other research interests include wireless and mobile computing, human-computer interfaces, and social implications of computing. Tara holds an MMath in Computer Science from the University of Waterloo. She can be contacted at <tara.whalen@crc.ca>.