Communications of the ACM
Certified Mail: the Next Challenge For Secure Messaging
The term "secure messaging" refers to the ability to provide data confidentiality, data integrity, data origin authentication, and non-repudiation of origin services for email. The technologies to provide these services are cryptography in general, and data encryption, digital envelope, and digital signature mechanisms in particular (see, for example, [6]). There are many schemes for secure messaging on the Internet, including, for example, Pretty Good Privacy (PGP), OpenPGP, and Secure Multipurpose Internet Mail Extensions (S/MIME) [7]. Furthermore, many email user agents either natively implement these schemes or can be extended with plug-ins to implement them.
Given this background, one could argue that secure messaging is a solved problem. Unfortunately, this is not yet the case; there are still several missing pieces. For example, the public-key infrastructure (PKI) and the related directory services required to access and retrieve public keys and digital certificates of communicating peers are not readily available. Furthermore, the certificate revocation problem is widely ignored, and the deployment of Web-based messaging has made the problem of how to securely store and use private keys more challenging. Consequently, the deployment of secure messaging has turned out to be slower than expected. It is, however, still possible and likely that end-to-end secure messaging schemes will be deployed and used in the future (similar to the way we routinely use letter envelopes to protect the confidentiality of postal deliveries). In the meantime, server-based and proxy-based approaches and solutions, such as PGP Universal, are reasonable and powerful intermediate steps.
Consider the situation in which almost everyone uses a secure messaging scheme and the implementations thereof are interoperable. Do we still have security concerns and corresponding requirements? Of course. No implementation will be free of bugs, and sooner or later some of these bugs will be found and exploited. Also, key management remains the Achilles heel of any security scheme, including schemes for secure messaging. Consequently, we will see attacks that exploit vulnerabilities in the way keys are managed and in the implementations thereof.
From a more general point of view, one could argue that a secure messaging scheme, such as PGP, OpenPGP, or S/MIME, protects the recipient against a sender claiming not to be the source of the message, but it does not protect the sender against a recipient claiming not to have received the message. The technical term for this requirement is "non-repudiation of receipt" (see, for example, ISO/IEC 7498-2). The sender wants some evidence (information that either by itself or when used in conjunction with other information establishes proof about a specific event or fact) that the recipient has in fact received the message. Otherwise, the recipient can always accept or drop the message at will.
Contrary to PGP and OpenPGP, the developers of S/MIME have thought about non-repudiation of receipt and have specified signed receipts (and some other enhanced security services) in RFC 2634. S/MIME signed receipts, however, assume fair participants in the sense the recipient provides a receipt if the sender asks for it. This assumption is somehow difficult, for if one could assume fair participants, then there would be no need for receipts in the first place. In any case, S/MIME signed receipts are not widely deployed, and the lack of evidence for message receipt is still a missing piece in the infrastructure required for the widespread and more professional use of email. This may change if a SMTP message delivery status notification mechanism, such as the one specified in RFC 1891 and RFC 1894, or a message-tracking mechanism, such as the one specified by the IETF Message Tracking Protocol (MSGTRK)1 WG, is put in place (the corresponding protocol is specified in an Internet Draft). Much remains to be accomplished, particularly for a message-tracking protocol, because such a protocol must be implemented by the originating and receiving user agents, as well as by any message transfer agent along the message delivery path. Furthermore, the lack of cryptographic protection makes it simple to spoof messages and to repudiate any participation in a later message exchange. For similar reasons, the message delivery notifications we get from a Microsoft Exchange server are not particularly useful, as they don't necessarily cross domains and can be spoofed easily.
The notion of certified mail and technologies to provide certified mail services in an efficient and effective (secure) way represents the next challenge for secure messaging. Here, I give a brief overview of existing technologies and solutions, and also discuss their usefulness and appropriateness for large-scale deployment on the Internet.
The provision of non-repudiation services (including non-repudiation of receipt) is a difficult research-grade problem (see, for example, [11]). In addition to the conventional security properties of a cryptographic protocol, such as completeness and soundness, a certified mail protocol must also be fair. It is fair if it provides the originator and the recipient with valid irrefutable evidence after the execution of the protocol, without giving one party an advantage over the other at any stage. Consequently, the fairness property requires that the execution of the protocol ensures the message and the proof of receipt are available to the recipient and originator, respectively. The protocol must be fail-safe in the sense that incomplete execution of the protocol will not result in a situation where the proof of receipt is available to the originator but the message is not available to the recipient, or vice versa.
One way to deal with the certified mail problem is to examine and draw some conclusions from the paper world. Certified (or registered) paper mail uses the notion of a signed receipt. More specifically, the post office (or the postman representing the post office) does not release a mail delivery unless the recipient signs a receipt. A receipt is a signed statement that may be efficient as evidence for dispute resolution. It is returned to the originator or archived by the post office for later use. In either case, it can be used as evidence to prove that the originator sent a paper mail item to the recipient and that the recipient actually received a mail delivery. It should be noted, however, that it is still up to the arbitrator to value the evidence. Moreover, the evidence only certifies that the originator sent some paper mail to the recipient (not a particular message). This weak binding between the evidence and the paper mail actually being certified is pervasive through almost all paper authentication methods and is one of the major drawbacks and shortcomings of handwritten signatures (as compared to digital signatures). As I will explain, the binding between the evidence and the mail being certified can be strengthened in the digital world. In either case, there must be some sort of arbitration framework for addressing disputes related to non-repudiation. More specifically, if a dispute arises in relation to a non-repudiable data exchange, an agreed arbitrator trusted by all parties may be called upon to resolve it. A certified mail protocol must also address dispute resolution.
Technologies and Solutions
On a high level of abstraction, there are two major classes of schemes to address the certified mail problem: schemes that require the existence of a trusted third party (TTP), and schemes that don't require the existence of a TTP (because they are self-enforcing). Let's begin with the second class. There are basically two classes of certified mail schemes that don't require a TTP: schemes based on a simultaneous secret exchange, and schemes based on trusted systems. It turns out that neither is appropriate to provide certified mail services on the Internet.
Certified mail schemes based on trusted systems look fine in theory, but their usefulness and security are often overestimated.
Simultaneous secret exchange. From a theoretical point of view, the certified mail problem refers to the problem of how to simultaneously exchange a message and a proof of receipt between two mutually distrusting parties (the originator and the recipient of the message). This problem is conceptually similar to other problems, such as contract signing or simultaneously exchanging digitally signed data. Protocols for the simultaneous exchange of secrets have been studied for two decades and many proposals have been made in the cryptographic literature [4, 5]. In short, a simultaneous secret exchange scheme assumes that parties A and B each possess a secret, a and b (each n-bits long). It is further assumed that each secret represents some value to the other party and that parties are willing to trade secrets with each other. A simultaneous secret exchange protocol is then executed in two phases:
- In the first phase, A and B commit to their secrets by exchanging f(a) and g(b) for some predefined one-way functions f and g. Consequently, A cannot recover b from g(b) and B cannot recover a from f(a).
- In the second phase, A and B release a and b bit-by-bit (until all n bits are released).
A simultaneous secret exchange protocol must be complete, sound, and fair (the fairness property ensures that the computational effort required to obtain each party's remaining secret portion is approximately equal at any stage during the protocol execution). Certified mail protocols based on a simultaneous secret exchange are theoretically interesting because they allow two parties to simultaneously exchange a message and a proof of receipt in absence of a third party (whether trusted or not). From a practical point of view, however, the protocols are disadvantageous because they are highly interactive; that is, they require many messages to be exchanged between participants. Also, their security is based on the assumption that A and B have equal or very similar computing power (this assumption is neither realistic nor desirable). The first disadvantage is particularly worrisome, because interactive protocols are not appropriate for Internet applications that are asynchronous in nature, such as email.
Trusted systems. Some schemes make use of trusted systems consisting of special hardware and/or software to provide a fair exchange between the originator and the recipient. In all of these schemes, the originator provides the message via trusted systems that do not allow the recipient to read the message until he or she sends back a receipt.
Certified mail schemes based on trusted systems look fine in theory, but their usefulness and security are often overestimated. In practice, many of these schemes are vulnerable and susceptible to reverse engineering and hacking. Consequently, they cannot provide any assurance and useful evidence of message delivery (even if they use cryptographic techniques). In fact, the existence of a TTP is replaced with software that provides some trusted functionalityan assumption even more difficult to make. As of this writing, schemes based on trusted systems cannot be considered as real candidates for the provision of certified mail services on the Internet. This may change if systems compliant with the specifications of the Trusted Computing Group (TCG),2 such as Microsoft's Next-Generation Secure Computing Base (NGSCB),3 are available and widely deployed. However, this is not yet the case and it is questionable whether such systems will ever be widely deployed in the mass market of personal computing systems [8].
It is clear that neither schemes based on a simultaneous secret exchange nor schemes based on trusted systems are appropriate to provide certified mail services for the Internet. Against this background, the use of TTPs seems advantageous, and various schemes have been proposed that make use of inline, online, or offline TTPs.
Inline TTPs. An inline TTP acts as an intermediary between the originator and one or several recipients. As such, it takes the message from the originator and forwards it to each intended recipient, possibly returning a receipt to the originator. Consequently, the inline TTP intervenes directly in a non-repudiation service. Several proposals have been made [1, 2]. Also, there are many certified mail products and services that employ Web servers as inline TTPs. Some of these products and services use the Secure Sockets Layer (SSL) or Transport Layer Security (TLS) protocol to cryptographically secure communications between the user's browser and his or her mail store.
The main advantages of inline TTPs for certified mail are simplicity, full control by the TTP (regarding the message flows), and the possibility to provide sender anonymity services. On the other hand, there are at least two disadvantages that must be considered with care:
- An inline TTP may become a performance bottleneck, especially for large messages and/or messages that are sent to many recipients;
- Most schemes require the users to completely trust the inline TTPs not to reveal and/or misuse the messages.
The first disadvantage can be addressed by using online TTPs that do not necessarily handle the entire messages. The second disadvantage can be addressed by encrypting the message key in a way that is not decryptable by the TTP (that is, encrypted with the recipient's public key). In this case, however, the message key must be logically (cryptographically) linked to the message it encrypts. Both improvements can be captured by the use of online TTPs.
Online TTPs. Similar to an inline TTP, an online TTP must be actively involved in every execution of a certified mail protocol (and must also be available during the exchange of a message and a receipt). The online TTP, however, does not necessarily have to forward the entire message. Instead, it may only deal with signaling information, such as cryptographic keys and/or receipts sent back to the originator. Again, several proposals have been made. For example, the first patent was granted in the early 1980s,4 and many other proposals have been made since then [3, 12].
Since they don't handle the entire message, schemes that make use of online TTPs are more efficient than schemes that make use of inline TTPs. However, the use of online TTPs does not necessarily address the second disadvantage of inline TTPs, namely that the users have to completely trust the TTP. In theory, this disadvantage can be addressed by encrypting a message outside the certified mail protocol. For example, in [10] it is argued that an originator can always encrypt a message outside the certified mail protocol, but then all the TTP can certify is that the recipient received an unintelligible bucket of bits (since it does not see the message in the clear). If the originator and the recipient encrypt their messages on an end-to-end basis, the TTP simply acts as a relay station between them, and the receipts it generates may not be particularly useful (this is similar to the paper world). Note, however, that it is possible to encrypt a message not decryptable by the TTPand to logically (cryptographically) link to the message key in some meaningful way. One possibility is to derive the message key from the message using a cryptographic hash function. Another possibility is to use dual signatures, as described, for example, in [9].
Offline TTPs. Contrary to inline or online TTPs, an offline TTP is not required for the exchange of the message and the receipt. It is required only in the exceptional case, such as if the recipient claims not to have received the message, or the originator claims not to have not received the receipt. Schemes that make use of offline TTPs for the fair exchange between two mutually distrusting parties are very useful and important building blocks for synchronous applications with stringent real-time requirements. Due to their increase in message flows, however, they are less useful for asynchronous applications, such as email in general, and certified mail in particular.
Conclusion
In this article, I argued that the lack of evidence for message receipt is a missing piece in the infrastructure required for the widespread and more professional use of email, and that the provision of certified mail services provides the next challenge for secure messaging on the Internet. Contrary to a system for postal mail delivery, a system to provide certified mail services can be logically and operationally separated from the message delivery and handling systems. Furthermore, a certified mail service for the Internet is transparent to and may complement a secure messaging scheme, such as PGP, OpenPGP, or S/MIME. This transparency is similar to paper mail, where certified mail can also be signed and enveloped in a way that is transparent to the mail certification service, meaning that the mail certification (or registration) service provider must not necessarily be aware of the delivery's content. I overviewed, briefly discussed, and put into perspective the technologies and solutions that can be used to provide certified mail services on the Internet. Among these approaches, the use of online TTPs is appropriate. This is in contrast to many certified mail services provided on the Internet (most of these services use Web servers that act as inline TTPs). It will be interesting to see whether these services meet the scalability and trust requirements of Internet users.
References
1. Bahreman, A., and Tygar, J.D. Certified electronic mail. In Proceedings of the Internet Society Symposium on Network and Distributed System Security (San Diego, Feb. 1994). Internet Society, 319.
2. Coffey, T. and Daiha, P. Non-repudiation with mandatory proof of receipt. Computer Communication Review 26, 1 (Jan. 1996), 617
3. Deng, R.H., et al., Practical Protocols for Certified Electronic Mail, Journal of Network and Systems Management 4, 3 (1996), 279297
4. Even, S., Goldreich, O., and Lempel, A. A randomized protocol for signing contracts. Commun. ACM 28, 6, (June 1985), 637647
5. Luby, M., Micali, S., and Rackoff, C. How to simultaneously exchange secret bit by flipping a symmetrically-biased coin. In Proceedings of FOCS `83: the IEEE Symposium on the Foundations of Computer Science (Tucson, Nov. 1983). IEEE Computer Society Press, 2330.
6. Oppliger, R. Introduction to Modern Cryptography. Artech House, Norwood, MA, to appear in 2005.
7. Oppliger, R. Secure Messaging with PGP and S/MIME. Artech House, Norwood, MA, 2001.
8. Oppliger, R. and Rytz, R. TCPA, Palladium, and NGSCB: Does trusted computing remedy the personal computer's security problems. IEEE Security & Privacy, to appear in 2004.
9. Oppliger, R. and Stadlin, P. A certified mail system (CMS) for the Internet. Computer Communications, to appear in 2004.
10. Schneier, B. and Riordan, J. A certified e-mail protocol. In Proceedings of ACSAC `97: the Annual Computer Security Applications Conference (San Diego, Dec. 1997). IEEE Computer Society Press, 232238.
11. Zhou, J. Non-repudiation in Electronic Commerce. Artech House, Norwood, MA, 2001.
12. Zhou, J. and Gollmann, D. A Fair Non-repudiation Protocol. In Proceedings of the IEEE Symposium of Security and Privacy (Oakland, CA 1996). IEEE Computer Society Press, 5561.
Footnotes
1www.ietf.org/html.charters/msgtrk-charter.html.
2The TCG is the successor organization to the Trusted Computing Platform Alliance (TCPA). Further information can be found at www.trustedcomputinggroup.org.
©2004 ACM 0002-0782/04/0800 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2004 ACM, Inc.