12.2 Early work

There is some early work in providing anonymity services for electronic mail (e-mail). For example, anon.penet.fi was a simple and easy-to-use anonymous e-mail forwarding service (a so-called anonymous remailer ) that was operated by Johan Helsingius in Finland. ^[6] In short, the anon.penet.fi anonymous remailer was provided by a simple SMTP proxy server that stripped off all header information of incoming e-mail messages before forwarding them toward their destination. In addition, if not already assigned, an alias (i.e., a pseudonym) for the sender of an e-mail message was created. In the outgoing message, the real e-mail address of the sender was replaced by the alias that allowed the recipient(s) of the message to reply to the sender without knowing his or her real identity or e-mail address.

In essence, anon.penet.fi provided sender anonymity by simply keeping the mapping between real e-mail addresses and their aliases secret. The downside of this simple approach was that any user of anon.penet.fi had to trust the service provider not to reveal his or her real identity or e-mail address. This level of trust may or may not be justified. ^[7] In either case, it is difficult for a user to decide whether this level of trust is appropriate for any given service provider. Today, there are several anonymous remailers available for public use on the Internet. ^[8]

A more sophisticated approach to provide anonymity services for e-mail was developed and proposed by David Chaum in the early 1980s [6]. In fact, Chaum introduced the notion of a Chaum mixing network that ”as its name suggests ”is a network consisting of a set of Chaum mixes (or mixes ). Each Chaum mix is an anonymous remailer that has a public key pair and is able to decrypt messages with its private key accordingly . In addition to forwarding incoming e-mail messages, a Chaum mix may also try to hide the relationship between incoming and outgoing messages by reordering , delaying, and eventually padding them to disable or at least complicate traffic analysis.

When a user wants to send a message in a Chaum mixing network, he or she must first choose a route through a series of Chaum mixes M ₁ ; . . . ; M _n to the intended recipient, and then prepare a layered message for delivery. In fact, the first layer includes the name of the recipient and the message encrypted with the public key of the recipient. The second layer includes M _n and the first layer encrypted with the public key of M _n . The third layer includes M _n-1 and the second layer encrypted with the public key of M _n-1 . This continues until the last layer includes M ₁ and the last but one layer encrypted with the public key of M 1. This last layer represents the message that is actually sent out. For example, if n = 3 and the recipient is B, the message that is sent out may look as follows :

M ₁ , { M ₂ , { M ₃ , { B , { message } k _B } k _M3 } k _M2 } k _M1 (12.1)

If this message reaches M ₁ , the Chaum mix uses its private key (i.e., k ^-1 _M1 ) to decrypt { M ₂ , { M ₃ , { B , { message } k _B } k _M3 } k _M2 } k _M1 . The result is split into two parts (i.e., M ₂ and { M ₃ ; { B; { message } k _B } k _M3 } k _M2 ) and the first part is used to route the second part to M ₂ . Similar to M ₁ , M ₂ uses its private key (i.e., k ^-1 _M2 ) to decrypt { M ₃ , { B , { message } k _B } k _M3 } k _M2 . Again, the result is split into two parts (i.e., M ₃ and { B , { message } k _B } k _M3 ) and the first part is used to route the second part to M ₃ . M ₃ , in turn , decrypts { B , { message } k _B } k _M3 using its private key (i.e., k ^-1 _M3 ). The result is B and { message } k _B and as such it can be forwarded to B. Finally, B uses his or her private key (i.e., k ^-1 _B ) to decrypt the message.

If a Chaum mixing network were used to transmit e-mail messages only through one single Chaum mix, this mix would have to be trusted not to reveal the senders and receivers identities (since it sees both of them). In this case, the situation would be comparable to the service provided by anon.penet.fi. Consequently, most people would prefer to forward email messages through two or more Chaum mixes in an attempt to protect themselves against a single mix that may see both the sender and the receiver identities of a particular message. In other words, using two or more mixes keeps the sender anonymous to every mix but the first and the receiver anonymous to every mix but the last. Also, a user s identity is best hidden if he runs his own Chaum mix and directs all of his outgoing e-mail messages through it.

If one were worried about an adversary powerful enough to monitor several Chaum mixes in a network simultaneously , one would also have to worry about timing and other correlation attacks. In an extreme case, consider the situation in which a Chaum mixing network is idle until a message is sent out and forwarded to its recipient. Then even though an adversary can t decrypt the layered encryption, he or she can still locate the route just by watching the active parts of the network and analyzing the data traffic accordingly. Chaum mixing networks have been designed to resist such attacks using queues to batch, reorder, and process incoming messages. In fact, each mix may keep quiet ” absorbing incoming messages but not retransmitting them ”until its outbound buffer overflows, at which point the mix emits a randomly chosen message to its next hop. However, due to the real-time constraints of some applications, the batching , reordering, and processing of data messages in queues is not always possible. As discussed below, this is particularly true for the WWW.

One question arises immediately with regard to the use of anonymous remailers and corresponding services: how can the recipient of an (anonymous) e-mail message reply to the sender? The answer is that the recipient can t unless explicitly told how to do so. A simple technique is to tell the recipient to send a reply to a certain newsgroup, such as alt.anonymous.messages, with a specific subject field, such as 12345example . The reply can then be grabbed by the sender from the appropriate newsgroup. This approach of replying is yet untraceable but also expensive and unreliable. A more sophisticated technique uses the knowledge of how to build an untraceable forward route from the sender to the recipient, to build an inverse untraceable backward route from the recipient to the sender. In general, the forward and backward routes are independent (they can be completely identical, partially identical, or completely disjunct). According to this technique, the sender computes a block of information that is used to anonymously return a response message from the recipient to the sender. This additional block of information is sometimes also referred to as a return path information (RPI) block. The RPI block must be sent with the original message and some padding data from the sender to the recipient. It is then used by the recipient to build a corresponding backward route or return path. This technique was prototyped by IBM Research in a system called BABEL [7].

Anonymous remailers are fairly well understood today. Unfortunately, the lessons learnt cannot be directly applied to the WWW, because the characteristics of e-mail and the WWW are inherently different:

First, the WWW is an interactive medium, while e-mail is store-and-forward. This basically means that a delay of several hours is acceptable for e-mail (most of the time).
Second, e-mail is a push technology, meaning that the sender of an e-mail message initiates a data transfer, possibly without the knowledge or consent of the recipient (the existence of e-mail bombing attacks illustrates this point fairly well). By contrast, the WWW is a pull technology, meaning that the recipient must explicitly request data being transferred from the sender.

The first difference implies that full featured Chaum mixing networks are unacceptable (or at least difficult to use) for HTTP data traffic. Nevertheless, the second difference also offers some possibilities to improve security (in terms of anonymity). For obvious reasons, the security of an anonymity-providing system, such as a Chaum mixing network, increases as the number of available and publicly accessible cooperating nodes (i.e., Chaum mixes) increases . In the realm of e-mail, operators of anonymous remailers have often come under fire when their services were abused by people sending threatening letters or unacceptable spam (refer to anon.penet.fi discussed earlier in this chapter). In fact, the undesirability of handling irate users causes the number of anonymous remailers to stay considerably low, potentially impacting the anonymity of the overall system. By contrast, a Web server can t initiate a connection with an unwilling browser and send it data when no request was made. This consensual nature of the Web should cause fewer potential node administrators to become discouraged, and therefore lead to corresponding increases in cooperating nodes.

Last but not least, it is important to note that Web proxy servers are often well suited to implement anonymity services because of their caching capabilities (to improve network performance). The very fact that data is being cached at some proxy servers makes it less likely that requests are forwarded all the way to the destination server. This makes traffic analysis more complicated, and harder to accomplish.

^[6] According to a press release on February 20, 1995, over 7,000 messages were forwarded daily, and the alias database contained more than 200,000 entries.

^[7] On February 8, 1995, based on a burglary report filed with the Los Angeles police, transmitted by Interpol, the Finnish police presented Helsingius a warrant for search and seizure. Bound by law, he complied, thereby revealing the real e-mail address of a single user.

^[8] A list of currently available anonymous remailers is maintained , for example, at http://anon.efga.org/Remailers .