Chapter 10. Anonymous Remailers

10.1. Dr. Anon to You

Host:	On this week's show, we have Anonymous, that one-named wonder who is in the class of artists like Madonna, Micheangelo and the Artist Formerly Known as Prince, who are so big they can live on one name alone. He, or perhaps she, is the author of many of the most incendiary works in the world. We're lucky we could get him or her on the show today, even though he or she would only agree to appear via a blurred video link. [beat] Mr. Anonymous (or should I say Ms. Anonymous?), it's great to have you on the show.
Anon:	Make it Dr. Anonymous. That will solve the gender problem. I was just granted an honorary doctorate last June.
Host:	Congratulations! That must be quite an honor. Did they choose you because of your writings? It says here on my briefing sheet that you've written numerous warm and romantic novels like the Federalist Papers. Great stuff.
Anon:	Actually, the Federalist Papers weren't a book until they were collected. It really wasn't a romantic set of papers, although it did have a rather idealistic notion of what Congress could be.
Host:	Sexual congress. Now that's a euphemism I haven't heard for a while. You're from the old school, right? That's where you got the degree?
Anon:	Well…
Host:	This explains why you're so hesitant to get publicity, right? It's too flashy.
Anon:	No. It's not my style. I prefer to keep my identity secret because some of what I write can have dangerous repercussions.
Host:	What a clever scheme! You've got us all eating out of your hand. Every other author would fall over himself to get on this show. We're just happy to be talking with you.
Anon:	I was a bit hesitant, but my publisher insisted on it. It was in the contract.
Host:	Do you find it hard to be a celebrity in the modern age? Don't you feel the pull to expand your exposure by, say, doing an exercise book with Cher? She's got one name too. You guys would get along great. You could talk about how the clerk at the Motor Vehicles department gives you a hard time because you've left a slot on the form blank.
Anon:	Well, that hadn't crossed my mind.
Host:	How about a spread in Architectural Digest or InStyle? They always like to photograph the famous living graciously in large, architecturally challenging homes. Or how about Lifestyles of the Rich and Famous? They could show everyone where and, of course, how you live. It's a great way to sell your personality.
Anon:	Actually, part of the reason for remaining anonymous is so that no one shows up at your house in the middle of the night.
Host:	Oh, yeah, groupies offering themselves. I have that problem.
Anon:	Actually to burn the place down and shoot me.
Host:	Oh, okay. I can see you doing a book with Martha Stewart on how to give a great masquerade party! You could do some really clever masks and then launch it during Mardi Gras in New Orleans. Have you thought about that?
Anon:	No. Maybe after I get done promoting my latest book. It's on your desk there. The one exposing a deep conspiracy that is fleecing the people. Money is diverted from tax accounts into a network of private partnerships where it fills the coffers of the very rich.
Host:	What about a talk show? I guess I shouldn't ask for competition. But you could be a really spooky host. You could roam the audience wearing a big black hood and cape. Just like in that Mozart movie. Maybe they could electronically deepen your voice so everyone would be afraid of you when you condemned their shenanigans. Just like in the Wizard of Oz.

It would be really hot in those robes under the lights, but I could see you getting a good share of the daytime audience. You would be different.

Anon:	My book, though, is really showing the path toward a revolution. It names names. It shows how the money flows. It shows which politicians are part of the network. It shows which media conglomerates turn out cheerful pabulum and “mind candy” to keep everyone somnolescent.
Host:	Whoa! Big word there. Speaking of big words, don't you find “Anonymous” to be a bit long? Do you go by “Anon”? Does it make you uncomfortable if I call you “Anon”? Or should I call you “Dr. Anon”?
Anon:	Either's fine. I'm not vain.
Host:	I should say not. Imagine not putting your name on a book as thick as this one. Speaking of vain, are you into horse racing? I wanted to ask you if you were the person in that Carly Simon song, “You're so vain, you probably think this song is about you.” She never told anyone who it was about. I thought it might be you. The whole secrecy thing and all.

10.2. Anonymous Remailers

There are many reasons why people would want to write letters or communiqués without attaching their names. Some people search for counseling through anonymous suicide prevention centers. Other people want to inquire about jobs without jeopardizing their own. Then there are the times that try our souls and drive us to write long, half-mad screeds that ring with the truth that the people in power don't want to hear. These are just a few of the reasons to send information anonymously. Even a high government official who is helping to plan the government's approach to cracking down on cryptography and imposing key escrow admitted to me over lunch that he or she has used pay phones from time to time. Just for the anonymity.

Much of what we do, or did in the past, is largely anonymous. Keeping track of who did what when is a waste of time. People only recorded data that made sense and the rest was quickly forgotten providing a cloud of forgiveness that covered the past.

On the Internet, anonymous remailers are one solution for letting people communicate anonymously. These mail programs accept incoming mail with a new address and some text for the body of the letter. They strip off the incoming header that contains the real identity of the sender and remail the content to the new address. The recipient knows it came from an anonymous remailer, but they doesn't know who sent it there.

In some cases, the remailer creates a new pseudonym for the outgoing mail. This might be a random string like “an41234”. Then it keeps a secret internal log file that matches the real name of the incoming mail with this random name. If the recipient wants to reply to this person, they can send mail back to “an41234” in care of the anonymous remailer who then repackages the letter and sends it on. This allows people to hold a conversation over the wires without knowing each other's identity.

There are many legitimate needs for services like this one. Most of the newspapers that offer personal ads also offer anonymous mailboxes and voicemail boxes so that people can screen their responses. People may be willing to advertise for a new lover or friend if the anonymous holding box at the newspaper gives them a measure of protection. Some people often go through several exchanges of letters before they feel trusting enough to meet the other person. Or they may call anonymously from a pay phone. There are enough nasty stories from the dating world to make this anonymous screening a sad, but very necessary, feature of modern life.^[1]

¹¹Strangely enough, in the past people would rely on knowing other people extensively as a defense against this type of betrayal. People in small towns knew everyone and their reputations. This type of knowledge isn't practical in the big city, so complete anonymity is the best defense.

Of course, there are also many controversial ways that anonymous remailers can be used. Someone posted copyrighted documents from the Church of Scientology to the Internet using an anonymous remailer based in Finland [Gro95]. This raised the ire of the church, which was able to get the local police to raid the site and force the owner to reveal the sender's name. Obviously, remailers can be used to send libelous or fake documents, documents under court seal, or other secret information. Tracking down the culprit depends on how well the owner of the remailer can keep a secret.

There are a wide variety of anonymous remailers on the Internet and the collection is growing and shrinking constantly. One current source of a good list can be found at http://www.chez.com/frogadmin/. These also include pointers to the software and instructions on how to start up your own remailer.

10.2.1. Enhancements

There are a number of ways that the anonymous remailers can be enhanced with features. Some of the most important ones are:

Encryption The remailer has its own public-key pair and accepts the requests in encrypted form. It decrypts them before sending them out. This is an important defense against someone who might be tapping the remailer's incoming and outgoing lines of a remailer.

Latency The remailer will wait to send out the mail in order to confound anyone who is watching the traffic coming in and out. This delay may either be specified by the incoming message or assigned randomly.

Padding Someone watching the traffic in and out of a remailer might be able to trace encrypted messages by comparing the size. Even if the incoming and outgoing messages are encrypted with different keys, they're still the same size. Padding messages with random data can remove this problem.

Reordering The remailer may get the messages in one order, but it doesn't process them in the same first-in-first-out order. This adds an additional measure of secrecy.

Chaining Remailers If one anonymous remailer might cave in and reveal your identity, it is possible to chain together several remailers in order to add additional secrecy. This chain, unlike the physical basis for the metaphor, is as strong as its strongest link. Only one machine on the list has to keep a secret to stop the trail.

Anonymous Posters This machine will post the contents to a newsgroup anonymously instead of sending them out via e-mail.

Each of these features can be found in different remailers. Consult the lists of remailers available on the net to determine which features might be available to you.

10.2.2. Using Remailers

There are several different types of anonymous remailers on the network and there are subtle differences between them. Each class was written by different people and they approached the details in their own way. The entire concept isn't too challenging, though, so everyone should be able to figure out how to send information through an anonymous remailer after reading the remailer's instructions.

One of the more popular remailers in history was run by Johan Helsingius in Helsinki, Finland, at [email protected] until legal troubles exhausted his patience. Composing e-mail and sending it through the remailer was simple. You created the letter as you would any other, but you addressed it to [email protected]. At the top of the letter, you added two fields, X-Anon-Password: and X-Anon-To:. The first held a password that you used to control your anonymous identity. The second gave the address to which the message would go. Here's a short sample:

When the message arrives in Finland, the remailer strips off the header and assigns an anonymous ID to my address [email protected]. The real name and the anonymous name are placed in a table and bound with a password. You don't need to use a password, but this adds security. Anyone with a small amount of technical expertise can fake mail so that it arrives looking like it came from someone else. The password prevented anyone from capturing your secret identity. If they did't know your password, then they could't assume your identity.

The password was also necessary for dissolving your identity. If you wanted to remove your name and anonymous identity from the system, then you needed to know the password. This remailer placed a waiting period on cancellation because it did't want people to come in, send something anonymously, and then escape the flames. If you send something, then you should feel the heat, was the philosophy— a philosophy that eventually wore out the welcome.

If you wanted to post anonymously to a newsgroup, you could put the newsgroup's name in the X-Anon-To: field like this:

Figure 10.1. A screenshot of the Windows program Private Idaho. You can use it to send encrypted or anonymous mail.

This would get posted under your anonymous identity. If someone wanted to respond, they could write back through the remailer. It would protect your identity to some degree.

10.2.3. Using Private Idaho

One of the nicer e-mail packages for the Windows market is Private Idaho, first written by Joel McNamara The original program is still available as freeware, but some of the more advanced development is now bundled as a US$30 product. (www.itech.net.au/pi/)

Private Idaho is just a shell for composing the email message and encrypting it with the necessary steps. The final product can be handed off directly to an SMTP server or to another email package like Eudora. The original product was just a shell for handling many of the chores involved in choosing a path, handling the keys, and encrypting the message. The latest is more of a full-fledged tool.

You can get copies of the original software directly from www.es-kimo.com/&jtilde;oelm/pi.html and versions of the latest from www.itech-.net.au/pi/.

10.2.4. Web Remailers

A number of web sites offer remailers for reposting information. Adding one level of anonymity is easy for web designers to include and many do. Some of the most popular are now pay services. The Anonymizer (http://www.anonymizer.com/) offers tools for both sending anonymous email and browsing the web anonymously. They deliberately keep few log files that might be used to break the veil of secrecy. After the September 11,2001 attacks on the World Trade Center and the Pentagon, the company made news by offering to help anonymous tipsters turn in the terrorists. The site argued that if the terrorists were ruthless enough to kill 5,000, they would not hesitate to track down and kill anyone who turned them in.

Many people use the free email services like Hotmail, Popmail, Excite, or Netscape as pseudononymous drop boxes. These services may work well for basic situations, but they often keep voluminous log files that can reveal the identity of user. Some, like Microsoft's Hotmail, are pushing new services such as the Passport in an effort to assign fixed identities to people.

10.3. Remailer Guts

Designing the inside of a remailer is fairly easy. Most UNIX mail systems will take incoming mail and pass it along to a program that will do the necessary decoding. Repackaging it is just a matter of rearranging the headers and re-encrypting the information. This process can be accomplished with some simple scripts or blocks of C code. Moving this to any platform is also easy.

Designing better, smarter remailer systems is more of a challenge. Here are some of the standard attacks that people might use to try to follow messages through a web of remailers:

In and Out Tracking The attacker watches as messages go in and out of the remailer and matches them up by either order or size. The defense against this is to keep n messages in an internal queue and dispense them in random order. The messages are either kept all the same size or randomly padded at each iteration.

Remailer Flooding Imagine that one remailer receives a letter and the attacker wants to know where it is going. The remailer keeps n letters in its queue and dispenses them randomly. The attacker can send n messages to the remailer just before the message in question arrives. The attacker knows the destination of her own n messages, so she can pick out the one message different from the flow. If the messages are sent out randomly, then the attacker must send another n messages to ensure that subsequent messages won't confuse her.

One defense against this approach is remailer broadcasting. Instead of sending each subsequent message to a particular remailer using one-to-one mail delivery, the remailer would broadcast it to a group of other remailers. Only one remailer would have the right key to decrypt the next address. The others would simply discard it.

Replay Attack An attacker grabs a copy of the message as it goes by. Then it resends it later. Eventually the letter will make its way through the chain of remailers until it arrives at the same destination as before. If the attacker keeps track of all of the mail going to all of the destinations and replays the message several times, then only one consistent recipient will emerge. This is the destination.

The best solution is to require that each message contain an individual ID number that is randomly generated by the sender. The remailer stores this ID in a large file. If it encounters another message with the same ID, then it discards the message. The size of this ID should be large enough to ensure that two IDs will almost certainly not match if they're chosen at random.

Forged Mail Attack It is relatively easy to fake mail sent to an SMTP. Someone could pretend to be you when they sent the anonymous message containing something illegal. If the police were willing to pressure the remailer operator into revealing names, then you could be fingered for something you didn't do.

The passwords used by many remailers are a good defense against this problem. The anonymous remailer won't send along mail that is supposed to be from a certain site unless the correct password is included. A more sophisticated system would require that the mail be signed with the correct digital signature.

The State may, and does, punish fraud directly. But it cannot seek to punish fraud indirectly by indiscriminately outlawing a category of speech, based on its content, with no necessary relationship to the danger sought to be prevented. —From the majority opinion by Justice Stevens in Joseph McIntyre v. Ohio Election Committee

Each of these solutions came from a paper by David Chaum [Cha81] that describes a process called a mix. The details of this paper were used as the architecture for the most sophisticated type of remailer currently operating on the Net. Lance Cottrell wrote Mix-master, a UNIX-based program that will send anonymous mail packages using the more robust structure described in the paper.

The main difference is in the structure of the address information. The first class of remailers packaged their data up in nesting envelopes. Each remailer along the chain would open up an envelope and do the right thing with the contents. Mixmaster maintains a separate set of addressing blocks. Each travels through the entire chain of remailers. It is more like a distribution list that offices often use to route magazines through a list of different recipients. Each recipient crosses off its name after it receives it.

There are two advantages to arranging the contents of the messages in this form. The first is that there is no natural reason for the size of the messages to shrink. If the outer envelopes are merely stripped off, then the size of the letter will shrink. This can be compensated by adding padding, but getting the padding to be the right size may be complicated because of the different block sizes of ciphers like DES. The second advantage is reduced encryption time. The block of the encryption does not have to be encrypted or decrypted for each stage of the remailer chain. Only the address blocks need to be manipulated.

Imagine that a message will take five hops. Then the header for a Mixmaster will contain a table that looks something like this if all of the encryption was removed:

Remailer's Entry	Next Destination	Packet ID	Key
Bob	Ray	92394129	12030124
Ray	Lorraine	15125152	61261621
Lorraine	Carol	77782893	93432212
Carol	Gilda	12343324	41242219
Gilda	Final Location	91999201	93929441

The encryption was removed to show how the process works. This header specifies that the mail should go from the remailer run by Bob, to Ray to Lorraine to Carol to Gilda before heading to its final destination. The Packet ID is used by each remailer to defend against replay attacks.

There are two types of encryption used in Mixmaster. First, each entry in the header is encrypted with the public key of the remailer. So the Next Destination, the Packet ID, and the Key for Ray are encrypted with Ray's public key. Only the rightful recipient of each re-mailer will be able to decode its entry.

The second encryption uses the keys stored in the table. The best way to understand it is to visualize what each remailer does. Here are the steps:

1. Decodes its packet using its secret key. This reveals the next destination, the ID, and the Key.
2. Uses its Key to decrypt every entry underneath it. Mixmaster uses triple DES to encode the messages.
3. Moves itself to the bottom of the list and replaces the remailer name, the destination information, and the ID with a random block of data. This obscures the trail.

If this is going to be repeated successfully by each remailer in the list, then the initial table is going to have to be encrypted correctly. Each entry in the header will need to be encrypted by the key of each of the headers above it. For instance, the entry for Carol should look something like this:

I was the shadow of the waxwing slain by the false azure of the window pane. —John Shade in Pale Fire

Bob's remailer will strip off the first level of encryption indicated by the function E^12030124, Ray's will strip off the second and Lorraine's will strip off the third. The final block left is encrypted by Carol's public key.

When the header finally arrives at the last destination, each block will have been re-encrypted in reverse order. This forms something like the signature chain of a certified letter. Each step must be completed in order and each step can only be completed by someone holding the matching secret key. The final recipient can keep this header and check to see that it was processed correctly.

The last key in the chain, in this case the one in the entry for Gilda, is the one that was used to encrypt the message. There is no reason for the remailer to decrypt the message at each step.

Mixmaster currently appends a block of 20 header entries to the top of each entry. Each block takes 512 bytes. If the letter is only going through five remailers, for instance, then the others are filled with random noise. Each entry in the table contains a bit that identifies it as a “final” hop. If that bit is set, then the key is used to decrypt the main block.

The main block of each message is also kept the same size. If a current message is too short, then padding is added until it is 20k long. If it is too long, then it is broken into 20k blocks. This size is flexible, but it should be set to a constant for all messages. This prevents anyone from identifying the messages from their size or the change of size.

Mixmaster software and much more information can currently be found at obscura.com.

10.3.1. Other Remailer Packages

One of the nicest, feature-rich programs for UNIX-based machines is Mailcrypt, written in emacs-lisp for use with the popular GNU Emacs program distributed by the GNU project. The software, created by Patrick LoPresti, will handle all of the basic encryption jobs for mail including encrypting outgoing mail, decrypting incoming mail, and evaluating signatures. The software interacts with the major UNIX mail reading programs like MH-E, VM, and Rmail.

The software also includes a good implementation that will create chains of remailers. When you choose this option, it will automatically create a nested packet of encrypted envelopes that will be understood by the remailers on the list maintained by Raph Levien.

You can create lists of possible remailer chains for future use. These can either be hard coded lists or they can be flexible. You can specify, for instance, that Mailcrypt should choose a different random ordering of four remailers everytime it sends something along the chain. You could also request that Mailcrypt use the four most reliable remailers according to the list maintained by Raph Levien. This gives you plenty of flexibility in guiding the information. To get Mailcrypt, go to http://cag-www.lcs.mit.edu/mailcrypt/.

Mailcrypt also makes it easy to use pseudonyms very easily. You can create a PGP key pair for a secret identity and then publicize it. Then if you want to assume a name like Silence Dogood, you could send off your messages through a chain of remailers. The final readers would be able to verify that the message came from the one and only original Silence Dogood because they would be able to retrieve the right public key and check the signature. Some people might try and imitate him or her, but they would not own the corresponding secret key so they couldn't issue anything under this pseudonym.

Another program developed just for chaining together the necessary information for remailers is Premail written by Raph Levien. The software is designed as a replacement for Sendmail, the UNIX software that handles much of the low-level SMTP. Premail can take all of the same parameters that modify its behavior including an additional set of commands that will invoke chains of remailers. So you can drop it in place of Sendmail any place you choose.

Premail has several major options. If you just include the line key: user_id in the header with the recipient's user_id, then Premail will look up the key in the PGP files and encrypt the file using this public key on the way out the door. If you include the header line Chain: Bob; Ray; Lorraine, then Premail will arrange it so that the mail will head out through Bob, Ray, and Lorraine's anonymous remailers before it goes to the final destination. You can also specify an anonymous return address if you like by adding the Anon-From: field to the header. Premail is very flexible because it will randomly select a chain of remailers from the list of currently operating remailers. Just specify the number of hops in a header field like this: Chain: 3. Premail will find the best remailers from Raph Levien's list of remailers.

10.3.2. Splitting Paths

The current collection of remailers is fairly simple. A message is sent out one path. At each step along the line, the remailers strip off the incoming sender's name and add a new anonymous name. Return mail can follow this path back because the anonymous remailer will replace the anonymous name with the name of the original sender.

This approach still leaves a path—albeit one that is as strong as its strongest link. But someone can certainly find a way to discover the original sender if they're able to compromise every remailer along the chain. All you need to know is the last name in the chain, which is the first one in the return chain.

A better solution is to use two paths. The outgoing mail can be delivered along one path that doesn't keep track of the mail moving along its path. The return mail comes back along a path specified by the original sender. For instance, the original message might go through the remailer [email protected] which keeps no records of who sends information through it. The recipient could send return mail by using the return address in the encrypted letter. This might be [email protected]. Only someone who could decode the message could know to attack [email protected] to follow the chain back to the sender.

The approach defends against someone who has access to the header which often gives the anonymous return address. Now, this information can be encoded in the body. The plan is still vulnerable because someone who knows the return address [email protected] might be able to coerce Fred into revealing your name.

A different solution is to split up the return address into a secret. When you opened an account at freds.remailer.com, you could give your return address as R¹. This wouldn't be a working return address, it would just be one half of a secret that would reveal your re-turn address. The other half, R², would be sent along to your friends in the encrypted body of the letter. If they wanted to respond, they would include R² in the header of their return letter. Then, freds-.remailer.com could combine R¹ and R² to reveal the true return address.

The sender's half of the return address can arrive at the anonymous drop box at any time. The sender might have it waiting there so the letter can be rerouted as soon as possible or the sender might send it along three days later to recover the mail that happened to be waiting there.

This split secret can be created in a number of different ways. The simplest technique is to use the XOR addition described in Chapter 4. This is fast to implement, and perfectly secure. The only practical difficulty will be converting this into suitable ASCII text. email addresses are usually letters and some punctuation. Instead of creating a full 8-bit mask to be XORed with the address, it is probably easier to think of offsets in the list of characters. You could come up with a list of the 60-something characters used in all email addresses and call this string, C. Splitting an email address would consist of doing the following steps on a character-by-character basis:

1. Choose a new character from C. Store this in R¹. Let x be its position in C.
2. To encode a character from the email address, find the character's position in C and move x characters down x. If you get to the end, start again.
3. Store this character in R².

The reverse process is easy to figure out. This will produce a character-only split of the email address into two halves, R¹ and R². R¹ is deposited at an anonymous remailer and attached to some pseudonym. R² is sent to anyone whom you want to respond to you.

They must include R² in their letter so the remailer can assemble the return address for you.

An even more sophisticated approach can use the digital signature of the recipient. The initiator of the conversation could deposit three things at the return remailer: the pseudonym, one half of the return address, R¹, and the public key of the person who might be responding. When that person responds, they must send f^e (R²). This is the other half of the secret encoded with the private key. The remailer has the corresponding public key so it can recover R² and send the message on its way.

The systems can be made increasingly baroque. A remailer might want to protect itself against people banging down its door asking for the person who writes under a pseudonym. This can be accomplished by encrypting the remailer's files with the public keys of the recipient. This is better explained by example. Imagine that Bob wants to start up an anonymous communication channel with Ray through freds.remailer.com. Normally, freds.remailer.com would store Bob's return address, call it B, and match it with Bob's pseudonym, maskT-AvEnGrr. Naturally, someone could discover B by checking these files.

freds.remailer.com can protect itself by creating a session key, kⁱ, and encrypting it with Ray's public key, f^ray (kⁱ). This value is sent along to Ray with the message. Then it uses kⁱ to encrypt B using some algorithm like triple DES before discarding kⁱ. Now, only Ray holds the private key that can recover kⁱ and thus B. freds.remailer.com is off the hook. It couldn't reveal B even if it wanted to.

This solution, unfortunately, can only handle one particular ongoing communication. It would be possible to create different session keys for each person to whom Bob sends mail. This increases the possibility that B could be discovered by the remailer who keeps a copy of B the next time that mail for maskT-AvEnGrrcomes through with a session key attached.

10.4. Anonymous Networks

Anonymous remailers move single packets. Some will fetch web-pages anonymously. It should come as no surprise that ambitious programmers extended these ideas to provide seamless tools for routing all packets to the Internet. They have essentially created TCP/IP proxies that encrypt all data leaving the computer and then bounce it through a network of servers that eventually kick it out into the Internet at large.

Each of these systems offer a great deal of anonymity against many attackers. The packets from all of the users form a cloud that effectively obscures the begining and the end of each path. None of the solutions, however, are perfect against omniscient and omnipotent attackers who can monitor all of the nodes in the network while probing it with their own packets. Each of the systems has some definite strengths but a few weaknesses that may be exploited in extreme cases.

The Freedom Network drew heavily on the inspiration of the Onion Routing Network developed at the Naval Research Labs by Paul Syverson, Michael Reed and David Goldschlag. [SRG00, STRL00, SGR97, RSG98] See Section 10.7.

10.4.1. Freedom Network

Zero Knowledge Systems designed and built the Freedom Network, a collection of servers joined by a sophisticated protocol for encrypting packets. The network lasted until 2001 when the company shut it down for financial reasons. The network remains one of the most ambitious tools for providing privacy on the Internet.

The network consisted of a collection of Anonymous Internet Proxies that would decrypt and encrypt messages while forwarding the data on to other proxies. If a computer wants to establish a path to the Internet, it takes these steps:

1. At the center of the network is the NISS or the Network Information Status Server, a central computer that maintains a list of operating AIPs and their public keys.
2. The computer takes a list of these machines and chooses a random path through a collection of machines. This may use information about distance and load to optimize the process. Shorter chains offer better service while longer chains offer more resistance to detection. Chains running through different countries may offer some extra legal protection.
3. The computer uses Diffie-Hellman key exchange to negotiate a key with each AIP in the chain.
4. The data going out the chain is encrypted with each key in turn. If f^k is the encryption function using key k, then f^{k 1} (f^{k 2} (… f^kn (data))) is sent down the chain. kⁱ is the key for the i — th AIP in the chain.
5. Each AIP receives its packet of data and uses the negotiated session key to strip away the top layer before passing it on.
6. The last AIP in the chain sends the packet off to the right destination.
7. The return data follows the same chain in reverse. Each AIP uses the session key to encrypt the data.
8. The computer strips away the n layers.

Zero Knowledge refers to this process as telescope encryption. The actual process is more involved and sophisticated. Providing adequate performance while doing so much encryption is not an easy trick.

10.4.2. PipeNet

PipeNet is another anonymous network created by Wei Dai. It also rests on a network of computers that route encrypted packets. The principle difference lies in the synchronized mechanism for coordinating the flow of the packets. At each clock step, all of the computers in the network receive a packet, perform the necessary encryption, and then pass it on. If a packet does not arrive, one is not sent.

This solution prevents an omniscient attacker from watching the flow of all of the packets in the hope to figuring out who is communicating with whom. In the Freedom network, a heavy user may inadvertantly give away their path by shipping a large amount of data along it. The omniscient attacker may not be able to break the encryption, but jus counting the size of the packets could reveal the destination. Ideally, a large user base would provide enough cover.

The PipeNet's strict process for sending information ensures that each link between machines only carries the same amount of information at each step. The data moves along the chain in a strictly choreographed process like soldiers marching across the square.

This process, however, has its own weaknesses. If one packet is destroyedor one node in the network locks up, the entire chain shuts down. If data doesn't arrive, it can't go out. [BMS01]

10.4.3. Crowds

The Crowds tool developed by Michael Reiter and Aviel D. Rubin offers a good mechanism for webbrowsing that provides some of the same anonymity as the Freedom Network or PipeNet, but without as much security. It's simplicity, however, makes it easy to implement and run. [RR98]

The protocol is very simple. Each computer in the network accepts a URL request for a document on the web and it makes a random choice to either satisfy the request or pass it along to another randomly selected user. If you want to see a document, your request may pass through a number of different people before finally being fetched from the right server and passed back through the chain.

This process offers a high degree of anonymity, but not one that can begin to fool an omniscient attacker watching all sites. The simplicty offers a strong amount of confusion. Your machine may receive a request from Alice, but there's no way to know if Alice is actually interested in the information itself. Her machine may just be passing along the request from someone else who might be passing it along from someone else etc. Each individual in the chain can only know that someone out there is interested in the information, but they can't be certain who that person is.

10.4.4. Freenet

One of the most ambitious and successful anonymous publication systems is Freenet, a peer-to-peer network originally designed by Ian Clarke. The project itself is highly evolved and open source distributions of the code are available from freenet.sourceforge.net. [CSWH00, Cla99]

The system distributes information across a random collection of servers donating their spare diskspace to people seeking to publish documents. The network has no central server that might be compromised so all searches for information fan out across the network. Each machine remembers a certain amount about previous searches so it can answer requests for popular documents.

Each document is known within the network by three different keys which are really 160-bit numbers created by applying the SHA hash function. If you want to retrieve a document, you ask for it with one of the three key numbers. The search process is somewhat random and unorganized, but also resistant to damage to the network. Here are the steps:

1. You start a search by specifying the key value and a “time to live” number which limits the depth of the nodes you want to search.
2. You choose one node in the network to begin the search.
3. This node checks to see if the key matches any files stored locally. If there's a match, the node returns the file.
4. If there's no local match, the node checks a cache of recent searches. If the key is found there, the node retrieves the document. In some cases, this document is already stored locally. In others, the node must return to the original source to retrieve it.
5. If there's no match, the server asks another in a chain and the process repeats. At each step, the “time to live” counter is reduced by one. When it reaches zero, the search fails.

The caching of this depth-first search speeds up the retrieval of the most popular documents.

The keys assigned to each document are generated in three different ways. The author begins by assigning a title to the document, T. This string of characters is converted into a keyword-signed key. This value is hashed by computing SHA(T) and then used to both encrypt and sign the document. Using SHA(T) to encrypt the document ensures that only someone who knows T can read a file. The individual servers can hold any number of files each encrypted by the hash of their titles, but only the person who knows the title can read them. This provides a certain amount of deniability to the server owner who never really understands the material on their hard disk.

The hash of the title is also used as the seed to a pseudo-randomly driven public/private key generation routine. While most public keys are chosen with true random sources, this algorithm uses the hash of T to ensure that everyone can generate the same key pair if they know T. This public key is then used to sign the document providing some assurance that the title and the document match.

This mechanism is far from perfect. Anyone can think up the same title and an attacker may deliberately choose the same title for a replacement document. Freenet fights this by creating a signed subspace key connected to the author posting the document. The creation of this key is a bit more involved:

1. First the author publishes a public key bound to their identity.
2. The public key and the title are hashed independently.
3. The results are XOR'ed together and hashed again: SHA(SHA(T)⊕ SHA(public key)).
4. The private key associated with the public key is used to sign the file.
5. The file is published with both the signed subspace key and the signature.

Retrieving the file now requires knowing both T and the public key of the author. Only the author, however, knows the private key so only the author can generate the right signature.

A third key, the content-hash key, is created by hashing the entire document. The author can decide which keys to include with the document when publishing it.

Obviously maintaining some central index of keys, documents and the servers holding them would make life easier for everyone including those who seek to censor the system. Freenet avoids this process, but does take one step to make the searching process easier. When new documents are inserted into the network, the author places them on servers which hold similar keys. The storing procedure searches the network looking at similar keys and then places the document there.

10.4.5. OceanStore

One of the more ambitious projects for persistent, robust, distributed storage is OceanStore developed by a large group of faculty and students at the University of California at Berkeley. Many of the basic ideas and the flavor of the project are clearly inspired by the Freenet project, but embellished with more sophisticated tools for upgrading and duplicating documents. [KBC⁺00]

The most significant addition is a mechanism for ensuring that documents aren't destroyed when they are updated. Blocks of new data can be inserted into documents and these changes propagate through the network until all copies are current. The mechanism also contains a more sophisticated routing structure to speed the identification and location of documents. All of these details are beyond the current scope of the book.

10.5. Long term storage

Anonymous remailers normally do their work in a few split seconds, deliver their message to the right person, and then move on. What if we want a send a message that lasts? What if we want to post a message where it will be available for a long time? You could always buy a server, pay for a connection and keep paying the bills but that may not work. Controversial material can be shut down with many different types of legal challenges and most server farms aren't willing to spend too much time or energy against determined opponents.

This technique is becoming increasingly controversial because the algorithms are used to store and exchange copyrighted music and video files.

10.5.1. Eternity Server

One solution is to split up the document into many pieces and store these piece on many computers, a suggestion that Ross Anderson explored in his design for an Eternity server.[And96a] The design outlines several of the tricks that might allow a network of n machines to store m files and allow the file's owner to both pay the cost of storage and recover the files when necessary.

In the system, each file, Fⁱ, is given a name, Nⁱ, and stored on a set of servers, {S^j, S^k, …} with these steps:

1. A general key, key, is chosen.
2. The key for encrypting the data for server S^j is computed from h(key + name(S^j)) where name(S^j) is some function that generates a name for a server like the DNS system.
3. A unique name for each file is computed with h(Nⁱ, name(S^j)). The data is stored under this unique name on S^j.
4. A random amount of padding is added to Fⁱ in a way that can be easily removed. It might consist of appending the true length of the file to the beginning of the file and then adding extra random information to the end.
5. The file is encrypted for S^j with this key and sent to the server.

This stores a separate copy on the set of servers. Each copy is encrypted with a different key and each copy has a different length.

Another option is to split each file up into smaller, standard sizes, a technique that eliminates the need for padding while introducing more complexity. It is also possible to add the secret sharing technique from Chapter 4 to add the requirement that any k parts of the file must be recovered before the file can be found. This would eliminate some of the need for encryption.

Anderson imagines paying the server owners, a process that can involve increasingly complex amounts of anonymous payment. He imagines that each server might submit a bill every so often to some central payment office. This could be audited to prevent an errant server from claiming to be storing a file without actually doing so. One technique would be for the central office to send the server a challenge nonce, c, and ask the server to compute a keyed hash, h(c, Fⁱ) to prove that they know the data in Fⁱ. This audit would require the central auditing office have a copy of Fⁱ and the key used to scramble it, key. If the auditing passes, the payment office would send the right money to the server.

Searching for the file could be accomplished by broadcasting Nⁱ to all of the servers, asking them to compute h(Nⁱ + name(S^j)), and see if they have the file. This might help someone recover a file after some time or allow a central payment mechanism to figure out who to pay for storage.

James Aspnes, Joan Feigenbaum, Aleksandr Yampolskiy, and Sheng Zhong consider some of the theoretical aspects of All or Nothing Entanglement in [AFYZ04].

10.5.2. Entanglement

One technique for preventing the destruction of some documents is to tie their existence to other documents so that one can't be deleted without others being destroyed in the process. Some say that the future of the documents becomes entangled.

Here's a simple algorithm for mixing the fate that is based on some of the simplest secret sharing algorithms from Chapter 4. Given a file, F, break it into n parts F¹ + F² + …+Fⁿ so that F can only be reconstructed by someone who holds all n − 1 pieces. (Let + stand for exclusive-or.) Ordinarily, n − 1 pieces would be built with a random number source. In this case, let's choose parts of other documents for these pieces.

That is, let P¹, P², P³,… be a sequence of parts to documents that acts as the storage for the entangled documents. To store F, use these steps:

1. Choose a set of n − 1 parts from the set of m parts of files previously locked away in storage, P¹, P², P³,… P^m. Use some random number generator driven by the file name. This might mean using h(key+name(F)) as a seed where key is an optional key and name(F) is some name given to the file. Call these P^r1, P^r2, P^r3 … where r¹, r²,… represents the choices made by the random number generator driven by h(key + name(F)).
2. Compute P^{m +1} = F + P^{r 1} + P^{r 2} + … + P^{rn − 1}.
3. Create a table entry that links P^{m +1} with name(F).

This solution makes it impossible to delete a file without endangering some of the files that were stored after it. There are still some weaknesses from this approach. The table linking P^{m +1} with name(F) lets someone know exactly which block to delete to destroy the file. It won't be possible to tell which other files are endangered unless there's no key used to compute the sequence of random blocks chosen for each file, r¹, r²,….

One possible solution is to use a hash table^[2] with holes for k blocks P¹ … P^k. In the beginning, all of the blocks are initialized to be empty. Then a random collection of blocks are filled with random numbers so that there will be random data to be used for the n − 1 blocks used to store a file.

²²In this case, the word hash is used as a data structure designer might use it, not a cryptographer.

A keyed random number sequence, r¹, r²,…, is still used to select the parts, but it is modified to take into account the fact that many of the blocks may hold no data. In this case, the n − 1 parts used in the secret sharing algorithm will be the first n − 1 full parts identified by the random number sequence. That is, P^{r 1} and P^{r 2} might be unfilled yet, but P^{r 3} and P^{r 4} have random data available either from another file or from the initial seeding of random information. So we use those two parts. The final part, F + P^{r 1} + P^{r 2} + … + P^{rn − 1}, is not stored at P^{m +1}, but at the first empty part identified by the random number stream, in this case, P^{r 1}.

This technique eliminates the need for any table linking P^{m +1} with the name for the file, but it adds other complexity. It is possible to identify the empty and full blocks when the file is being stored but this will change as more blocks are added to the mixture. One solution is to add some additional information to the final part that includes the name of the file, perhaps encrypted with a key, and the locations of the n − 1 part needed to assemble the final part. The file could then be recovered by computing the random number stream, r¹, r²,…, and testing each part identified by the stream until the final part is found. The name attached to the final part will make it possible to identify it and the locations of the n − 1 parts stored with that name will make it possible to recover the entire file.

An approach like this is still vulnerable to some simple denial-of-service attacks like storing a large number of garbage files. This will make it much more likely that deleting one file will not damage anything of value.

10.6. Publius

Another popular tool for storing documents securely is the Publius system designed by Marc Waldman, Aviel D. Rubin and Lorrie Faith Cranor.

The system uses secret sharing algorithms to split up a document between n different servers so that any m pieces are sufficient to recover it. The tool uses a protocol for recovering the document that rests on top of HTTP making it possible for it to work fairly innocuously with standard webservers. The solution is notable because it offers the publisher and only the publisher an opportunity to delete and update the documents after they're distributed.

Publius is named after the pseudonym chosen by Alexander Hamilton, James Madison, and John Jay. [Pub88] They chose the pseudonym from the name of Publius Valerius Publicola, a prominent Roman consul known for helping establishing a republic.

A server, Sⁱ, holds a document, F under a name, N^i,j by storing the following:

1. A share of a symmetric cipher key, key, call it keyⁱ. This is constructed by using a secret sharing algorithm to split the key into n parts so that any m are sufficient to recover it.
2. The result of encrypting F with some strong symmetric cipher, ENC(F,key). (The published paper stores the same encrypted version on all servers, but it might make sense to add another layer of encryption so that the encrypted version is different on all servers.)
3. A name by which the part will be known. In this case, nameⁱ = h(F, kⁱ). The original paper shortens the result of h by splitting the result of the hash function in half and XORing the two parts together.
4. A password that will give the creator the ability to delete and update the block of data stored here. In this case, the password itself is not stored, but the hash of the password concatenated with the server's name: h(Sⁱ, password).

Storing the file involves encrypting it at least once with a random key and splitting the key up between the servers. Recovering it involves retrieving at least m shares of the key and the copies of the encrypted file before decrypting them.

In the original version, the n servers are chosen from the names themselves: nameⁱ mod servers where servers is a static number of servers in the system. If by some coincidence, the various values of nameⁱ only choose a small subsection of the set of servers, a different key is chosen until the parts will be distributed successfully.

This process makes it possible to create short URLs produced by concatenating the values of nameⁱ into one manageable block of text. Here's one of the original URLs from the paper:

The values of nameⁱ are BASE64encoded and separated by equals signs. Any user recovering a document would choose a subset of m names and compute nameⁱ mymod servers to identify where the parts might be stored before requesting them.

The password allows the creator to change the stored data by proving knowledge of the password, perhaps by sending

where nonce is a random string concatenated with the current time. When the server validates the result by duplicating the calculation, the server can either delete the file entirely or just add an update.

The original paper suggests using a new URL to store any updated content, effectively replacing an old file with a completely new version with a new name and new URL. Any request for an old URL would receive a copy of the new URL. The client would compare the new URLs delivered by the m servers and, if the new URLs match, request the new URL. Another technique is to add a list of changes to the original file, a newtermdiff that adds the changes. This could also be encrypted by key and stored along side. The client package would be responsible for integrating these changes after recovering the original file and the diff.

The original Publius system also embedded a flag in the URL which would effectively say, “This URL can't be updated.” If this flag appeared in the URL, the client would refuse to follow any redirections offered by the servers. This could prevent any redirection by a man in the middle. Publishing the diffs alongside would not be affected to some system wide redirection.

10.7. Onion Routing

One of the most successful anonymous routing tools is the Onion Routing protocol built by by Paul Syverson, David Goldschlag, Michael Reed, Roger Dingledine and Nick Mathewson. The protocol has been revised and extended since its introduction in 1996 and it is implemented by a rich collection of tools including a version of the Firefox browser.

The system can protect a user from an eavesdropper tracking their browsing by sending the requests through a series of randomly chosen proxy servers. Each link in the path is encrypted with a different layer of encryption a process that gives the protocol its name. Each proxy server along the chain will strip off its layer of encryption until the last proxy server will spit out an unencrypted packet of data to the eventual source. All of the proxy servers along the path can confound an eavesdropper by making it impossible to know which data is coming and which is going. Anyone watching a user may see only encrypted data leaving the machine and encrypted data returning effectively making it impossible to track where the packets go and who sends back a response.

The security of the system depends heavily on the confusion provided by the network of proxy machines— a network that is said to include at least 1000 servers at some times. If an eavesdropper can't watch all of the machines, then the eavesdropper may not be able to track where requests go. Encrypted requests enter the cloud on the edges and emerge somewhere else as cleartext data going to the real destination. Matching the clients with the cleartext requests that eventually emerge is not an easy task. [DS03, Ser07]

A powerful eavesdropper, though, can often figure out information from watching carefully. An omniscient eavesdropper can often match clients with the cleartext packets that leave the cloud of proxy servers by timing them. If an encrypted packet enters from Alice's machine at 10:30, 10:32, and 10:35 and some cleartext packets of the same general size leave a distant proxy at 10:31, 10:33, and 10:36, then there is a good chance that those were Alice's packets. The quality of this analysis depends heavily on the performance of the network and the number of other users. A fast network that doesn't introduce very large delays will also make the matching process more precise.

The system is also vulnerable to other accidental leaks of data. If a proxy server shuts down for some reason then it will break all of the paths that use it. All of the clients that used it will need to renegotiate new paths, effectively identifying some of the past traffic. This won't link up people immediately, but it can be revealing if it is repeated several times.

There is also one inherent limitations to the protocol that is often forgotten: onion routing only protects information to the last proxy in the chain. After that, the last proxy will communicate in the clear with the final destination for the data packet. Some suggest that the people who volunteer to operate the last proxies in the chain, the edge servers, may be doing so to peek at all of the data flowing past.

This won't tell them who initiated the data packet, but it will give them a view of the data itself and this can be quite useful. This problem can be reduced by using SSL to negotiate a separate encrypted channel between the sender and the final destination for the data.

10.7.1. Establishing a Circuit

The Onion Routing protocol buids its circuits up step by step by negotiating with each step along the circuit. Here are the steps involved in building the chain illustrated in Figures 10.2 and 10.3:

Figure 10.2. A simple circuit established between Alice's and Bob's computers might pass through two proxies, alpha and beta. This circuit will be hidden by the confusion of the network described in Figure 10.3.

Figure 10.3. The circuit between Alice and Bob from Figure 10.2 will be hidden by the traffic between all of the other circuits flowing through the network of proxies. In this case, S^alpha is the entry node and S^beta is the exit node. There will probably be other servers in between in an actual example, but they are elided here.

1. Alice decides she wants to send some packets of data to Bob using the Onion Routing network.
2. She chooses server S^alpha at random from a list of servers that accept incoming circuits. This is often called the entry node.
3. Alice and S^alpha negotiate a key. The latest version of the Onion Routing software uses ElGamal key exchange with established Diffie-Hellman keys because it has proven to be faster than the RSA algorithms used in the original version. Call this key^{alice, alpha}. [ØS07a]
4. Alice now has a secure path between her computer and S^alpha. She can extend this by choosing another server at random from the network, S^beta.
5. Alice does not communicate with S^beta directly; she uses S^alpha as her proxy. S^beta doesn't even know that Alice exists because all of Sbeta's communications are with S^alpha. Alice negotiates a key by sending her half of the key establishment protocols through her encrypted tunnel with S^alpha who sends them on to S^beta on her behalf. Let's call the result of this negotiation: keyalice, beta.
6. After Alice completes the key negotiation process with S^beta, she checks the signature on key^alice,beta provided by S^beta. This prevents S^alpha from cheating and pretending to open up a new circuit for S^beta or just setting up a fake man-in-the-middle attack.
7. If the circuit was longer, Alice would repeat this negotiation phase with a number of servers in the circuit.
8. Alice now has a circuit constructed with S^beta, her proxy for the general Internet also called the exit node. If she sends out a packet, it will be S^beta that delivers it to the final destination and it will be S^beta that will accept any communication for her as her proxy.

This description leaves out a number of details of how the negotiation is accomplished but they can be found in the original papers. [ØS07a, DMS04, SRG00, STRL00, SGR97, RSG98]

After building these keys, Alice now has a way to communicate with Bob. A round trip might look like this:

1. Alice encrypts the packet of data, M, with key^alice,beta producing E^{keyalice,beta} (M).
2. Alice encrypts this encrypted packet again with key^alice,alpha producing: E^{keyalice,alpha} (E^{keyalice,beta} (M))
3. Alice sends this to S^alpha.
4. S^alpha strips away the outer layer to get E^{keyalice,beta} (M) and sends this to S^beta.
5. S^beta strips away the inner layer and uncovers M. This packet of data could be any low-level TCP packet like an HTTP web page request.
6. S^beta sends off M and gets back any response, call it R.
7. S^beta encrypts the response with the key shared with Alice producing: E^{keyalice,beta} (R) and pass this on to S^alpha.
8. S^beta encrypts the response with the key shared with Alice producing: E^{keyalice,alpha} (E^{keyalice,beta} (R)) and pass this on to Alice.
9. Alice strips away both of the layers of encryption to get R.

This process is often called telescoping, a reference to the old collapsible spyglasses built from nesting tubes.

10.7.2. More Indirection: Hidden Services

The basic Onion Routing system hides the identity of one end of a conversation, call it the client, from the other by passing the bits through a cloud of proxies. There's no reason why the system can't also hide the destination, the so-called server, from the client if the proxy servers in the middle of the cloud can be trusted to keep some secrets about the destination of the information. This is a reasonable assumption if the number of proxies is large and the eavesdropping capabilities of any adversary are small.

The latest versions of the system can also offer hidden servers through the cooperation of special proxy nodes acting as rendezvous points, directory servers, introduction points, and valet servers. All of these live on top of the normal network of entry nodes and exit nodes, often with the same machine offering multiple services. The directory server contains a list of hidden servers out on the network and the introduction points that will act as their proxies and hide their existence. When a connection is established, the rendezvous points will act as a midway point, hiding the identies of the client and the now hidden server from each other.

Here is the rather complicated first structure for hiding hidden servers behind multiple layers of introduction as illustrated by Figure 10.4 [ØS07b].:

Figure 10.4. The circuit between a client (Alice) and a hidden server (perhaps Bob) will work through an introductory server (marked “intro”), a directory server and a rendezvous server (marked “meet”). The dashed lines aren't directly part of the protocol; they just indicate that the normal onion routing encryption is the basis for the interaction. [ØS07b]

1. When a hidden server wants to join the onion network, it looks around for an introduction point. When it finds a trustable server that will do the job, it sets up a secure link and waits.
2. The hidden server tells the directory server about the introduction point. This directory server can assign a special name much like the DNS system used for normal domains. In practice, the domains with the suffix .onion are used to indicate these addresses.
3. When Alice wants to find the hidden server, she sends the .onion address to the directory server which sends her to the introduction point.
4. Alice shops around for a rendezvous point to act as the mid point for the communications. (This is marked as “meet” in Figure 10.4 to save space.) Note that the rendezvous point will not ordinarily know who Alice may be because the communication is hidden by the chain of proxies in the circuit that Alice established with the rendezvous point. So Alice will need to identify her connection with some sort of pseudonym. Note, this could be a weak point if Alice is able to control the rendezvous point too.
5. Alice begins a key negotiation with the hidden server and forwards this information with the location of the rendezvous point to the introduction point.
6. The introduction point passes this information on to the hidden server who then decides whether to complete the key exchange and meet at the rendezvous point.
7. Assuming the hidden server likes Alice's request, it will set up its own tunnel to the rendezvous point and tell the rendezvous point that it wants to communicate with Alice. Well, it won't know Alice by name. It will only know Alice's pseudonym.
8. The rendezvous point will notify Alice that the hidden server wants to talk too.
9. Alice completes the key negotation with the hidden service and she now has a secure link to the hidden server without knowing who the hidden server happens to be.

This entire exchange is a bit like the kind of negotiation that teenagers use in courting when asking their friends to find out if so-and-so likes me. If the entire onion network is trustworthy, the link is trustworthy too. The rendezvous point doesn't know the identity of either the client (Alice) or the server because the layers of proxies in between hide this information. Also, the introductory server and the directory server won't know the hidden server because the layers of proxies hid the sender during the initiation. The directory server just knows that there's some hidden server out there with a name and an identity.

Still, this has limitations. Imagine someone decides to operate a hidden server good-stuff.onion. Once the name becomes known and passed around among people, there's no easy way for the original owner of good-stuff.onion to prevent someone else from setting up shop and broadcasting the name to directory servers. How will the directory server know which is the rightful owner of the name? If the battles over domain services are brutal when privacy isn't involved, they're close to impossible when it's not possible to identify people.

One solution is to tie the identity to some public key not a domain name like good-stuff.onion. Only the person who created the original key pair should be able to lay claim to this public key later. The only problem is that this key is not as easy to remember as the simple domain name good-stuff.onion.

This problem can be reduced but not eliminated if the directory servers have a long memory and maintain long, stable connections with the onion routing network. They can link the domain name with the public key when the entry is created and as long as they honor this link, the network will be able to find one and only one hidden server that is the original owner of good-stuff.onion. Only the owner of a matching key can re-establish the link.

The usual problems of timing attacks are also possible in this world. If a user can control how a rendezvous point re-broadcasts information to a hidden server, a sophisticated client might be able to identify a hidden server by noting when the data leaves the rendezvous point and when it arrives. If the data packets leave and arrive in a pattern that stands out from the noise, it would be possible to find a hidden server in much the same way that an eavesdropper can identify both sides of a communication.

If hidden servers don't introduce enough layers of indirection and proxied communication, then you might also look to valet nodes. These replace the directory servers with a cloud of flexible, irregular servers that know the right introduction points. After a hidden server negotiates a connection with an introduction point, the introduction point turns around and finds some valet nodes on its own. The hidden server doesn't contact a directory server and it doesn't broadcast its own information. This reduces the weakness posed by a directory server.

How does the client find a valet node? The information for connecting with the valet node and the various public keys for negotiating a tunnel with the introduction point are bundled together and circulated, perhaps out of the network.

10.7.3. Stopping Bad Users

Bad users of the onion routing network can ruin the reputation of other users. The Wikipedia, for instance, often blocks TOR exit nodes complete because some people have used the network to hide their identities while defacing the wiki's entries. Is it possible to build up anonymous reputations for users that follow them from visit to visit, effectively banning the bad user? There are no simple solutions because there's little way to establish that a new user to the system isn't someone who acted poorly in the past. But it is possible to put some hurdles in the way by giving returning users some additional powers if they present some form of anonymous credentials.

One straight-forward solution is to use some form of certificates signed with a blind signature, a technique that borrows from some of the early solutions for building anonymous digital cash. [SSG97, DMS03] When you register, you get an anonymous coin to be spent redeeming services in the future. If you behave well, you can get a new coin when you turn in the old one.

Section 12.5.1 uses blind signatures for zero knowledge proofs.

For the sake of simplicity, let the coin be some random number, m, chosen by the newly arriving user who wants to be anonymous in the future. When registering for the service, the user doesn't present m per se, just m after being modified by some blinding factor, a value that is chosen differently depending on the digital signature algorithm that will be used to certify the coin. In the case of an RSA signature, this would be another random value b encrypted by the public key. The signature will reverse this encryption allowing the blinding factor to be stripped out later:

1. Alice wants to register for anonymous access to the server— a process through which the server might ask for a real identity. This happens outside the TOR cloud.
2. Alice downloads the server's public key. In the case of RSA, this would be a modulus n and an exponent e.
3. Alice chooses a random blinding factor b and a random serial number for the coin, m, computes b^e m mod n and sends this to the server while registering.
4. The server responds by signing this value. In the case of RSA, that means computing (b^e m mod n)^d mod n = b^de m^d mod n = bm^d mod n where d is the corresponding private exponent. The server returns this to Alice.
5. Alice strips out the blinding factor. In the case of RSA, this means multiplying by b^-1 mod n. This produces m^d mod n, a valid digital signature on m that was produced without revealing m to the server.

Alice is free to use this anonymous token at any time by submitting both m and m^d mod n at any time. (The server might impose time limits by changing the values of the public and private keys, d, e, and n, from time to time.) If Alice behaves well, she can get another anonymous token by working through the same algorithm again with a new serial number, m'. The server would keep track of the spent serial numbers to prevent reuse.

There are limitations to this approach too. The server must make a decision about Alice's behavior before giving her a new coin for another visit. If Alice's misbehavior comes to light after this coin is generated, well, there's nothing that can be done. The chain of abuse will continue.

A more robust algorithm called Nymble proposes a way of constructing the coins so they can be linked together. It adds, in essence, a trap door to the blinding mechanism that is minded by a separate reputation server. If bad behavior comes to light, the service can approach the reputation server and ask it to spring open the trap door. This will allow the server to ban the bad person when they return. [JKTS07]

The field of digital cash is a rich world of mathematical techniques for settling debts anonymously. All of the algorithms are much more sophisticated and secure than the simple one presented here. See [CFN93, Way95b, Way97a] and many others.

The actual algorithm is too complicated to describe in this space, but it is based on a technique known as hash chains, a sequence of values produced by repeatedly hashing a number. That is, m⁰ is chosen at random and then mⁱ = h(m^{i − 1}). This technique might be combined with the anonymous coin by presenting mⁱ with the anonymous coin on the first visit. The server does not need to renew the service at each visit by providing another anonymous coin because it can use the hash chain to keep track of the good users.

On the next trip, Alice presents m^{i − 1} to the server which verifies it by looking at to see that h(m^{i − 1}) = mⁱ. If it does, the server discards mⁱ and replaces it with m^{i − 1} on the list of hash chains corresponding to good anonymous users. If problems emerge later, the server just shuts down a particular chain. Bad behavior is banned again.

10.8. Anonymous Auction Protocols

In anonymous and semi-anonymous networks, it is often difficult to conduct traditional business when the traditional solution requires some form of identification. Auctions, for instance, usually demand that all of the interested parties appear before each other so everyone can watch the action. Real estate auctions are held on the steps of the court house for just this reason. When people want to remain anonymous during an auction, they usually need to send some proxy or rely on the auction house to keep their identity a secret.

Ross Anderson and Frank Stajano showed how the Diffie-Hellman key exchange algorithm could be extended to offer anonymous bidding over a network. [SA00] Their auction takes place continuously and requires the various bidders to chime in with their bids at the right time, much like a traditional auction held in a hall. The identities, though, are hidden from each other and even from the seller too. When a winner is finally chosen, the seller and the buyer can quickly establish an encrypted communication channel to negotiate when and how to trade the goods for cash. If the goods are digital, the buyer and seller don't even need to reveal their identities to each other.

In the original paper, the i^th round of the auction begins at time it where t is the amount of time between rounds. For the sake of simplicity, let the price be f(i). Since this is a Diffie-Hellman-based protocol, the group must also choose some prime p and a generator g for the field.

If buyer j wants to pay f(i), they choose a random number, x^i,j, and announce g^xi,j mod p at time it. The seller chooses one of the submitted values, perhaps at random or perhaps by choosing the first to arrive if it can be determined fairly. This becomes the winning bid at time i.

The seller announces the chosen value and broadcasts it. If the seller wants to be clever, the seller can also choose a random value, yⁱ, construct a key from g^yi mod p and g^xi,jyi mod p, and encrypt a message. Each of the bidders can try to read the message but only the bidder who wins round i will succeed.

This continues until there's only one winning bidder left standing. The bidder who wins round i will usually drop out of round i + 1 to avoid being duped into continuing bidding because there's no easy way to for an anonymous bidder to see when there are no other bidders. When no bids arrive for a round, the seller and the buyer can establish a key and begin any negotiations to exchange the goods. If physical items and real cash are part of the transaction, this will usually involve stripping away the anonymity from each other. But the losing bidders don't find out any information.

Anderson and Stajano point out, often humorously, that there are many ways for bidders to ensure that the auction is honest. While the bidders are kept anonymous, they can claim ownership of a bid by revealing a value of x^i,j.

It is possible to extend the protocol to remove the requirement to hold the bidding in rounds by allowing each bidder to include their maximum bid. The bidder can also sign this with their private key, x^i,j and g^xi,j mod p. If this can be reliably distributed to all bidders, perhaps through a system like the Dining Cryptographers' network (see Chapter 11), then the seller can choose a winning bid through a dutch auction.

10.9. The Future

In the short-term future, every machine on the Internet will be a first-class citizen that will be able to send and receive mail. The best solution for active remailers is to create tools that will turn each SMTP port into an anonymous remailer. To some extent, they already do this. They take the incoming mail messages and pass them along to their final destination. It would be neat, for instance, to create a plug-in MIME module for Eudora or another email program that would recognize the MIME type “X-Anon-To:” and resend the mail immediately.

To a large extent, these tools are not the most important step. The tools are only useful if the remailer owner is willing to resist calls to reveal the hidden identity.

There is also a great need for anonymous dating services on the Net. Although many of the remailers are clothed in the cyberpunk regalia, there is no doubt that there are many legitimate needs for remailers. An upscale, mainstream remailer could do plenty of business and help people in need of pseudonymous communication.

10.10. Summary

The Disguise The path between sender and recipient is hidden from the recipient by having an intermediate machine remove the return address. More sophisticated systems can try to obscure the connection to anyone who is watching the mail messages entering and leaving the remailing computer.

How Secure Is It? Basic anonymous remailers are only as secure as the strongest link along the chain of remailers. If the person who runs the remailer chooses to log the message traffic, then that person can break the anonymity. This may be compelled by the law enforcement community through warrants or subpoenas.

The more sophisticated remailers that try to obscure traffic analysis can be quite secure. Anyone watching the network of remailers can only make high-level statements about the flow of information in and out of the network. Still, it may be quite possible to track the flow. The systems do not offer the unconditional security of the dining cryptographers networks described in Chapter 11.

Digital Mixes must also be constructed correctly. You cannot use RSA to sign the message itself. You must sign a hash of the message. [PP90] shows how to exploit the weakness.

How to Use the Software The Cypherpunks archive offers all of the software necessary to use chaining remailers or Mixmaster. The WWW pages are the easiest options available to most people.

Further Reading

• There are a number of different products available now from companies offering various levels of anonymous and pseudonymous accounts. Some include MuteMail (mute-mail.com), HushMail (hushmail.com), Guardster (guard-ster.com), Safe Mail, (safe-mail.net), and Anonymizer (anonymizer.com). These operations are often secure, but they have been known to turn over subscriber information and, in some cases, decryption keys in response to subpoenas. [And07] HushMail, for instance, says that it will not release information without a subpoena from the Supreme Court of British Columbia, Canada, a significant legal hurdle but one that can be met.
• George Danezis, Roger Dingledine and Nick Mathewson have an anonymous remailer, Mixminion, that uses Mixlike routing to obscure the content and path of the messages. The latest version is available from mixminion.net. [DDM03]
• MorphMix is a tool developed by Marc Rennhard and Bernhard Plattner that asks each user's node to actively contribute to the mix, a choice that helps force the network infrastructure to scale while also requiring a mechanism for ranking the reputation of the users.[RP04, TB06]
• Salsa, a tool from Arjun Nambiar and Matthew Wright, selects the nodes in a path in a random way in order to prevent an attacker from infiltrating the circuits. This forces the attacker to control a significant proportion of the nodes in order to have a good chance of intercepting a message. [NW06]