December 2003 - cypherpunks-legacy

Mixmaster and remailers
by lcottrell＠popmail.ucsd.edu 17 Dec '03

17 Dec '03

Here is a text version of an essay on Mixmaster and remailers in general. I am going to try to put this in HTML and stick it on my home page. If you want the original Mac version (distributed at today's San Diego Cypherpunks meeting) let me know (Word 5.0). The list software has been balking when I try to post in MIME encoded. The figures will be in the HTML, and are in the Mac version. -------------------------------- **Cypherpunk remailers. The structure of current remailer messages is a nested set of encrypted messages. Each message is encrypted to a remailer. The message contains the instructions for each remailer (such as where to send the message next) and the message to be forwarded. Each remailer removes a layer of encryption, and accompanying instructions, takes any requested actions, and sends the message on to the next destination. Figure 1 The figure above graphically represents a message that will be sent through 3 remailers (A,B,C) and finally to Bob. The boxes represent encryption, with the name of the person to whom the message is encrypted is outside the upper left corner of the box. One important fact is immediately clear from this diagram; the message shrinks after each hop. Cypherpunk remailers do several things: Send a message to another email address or post it to a new group. Accepts encrypted messages with instructions for processing hidden inside the encrypted envelope. Strip of all (or at least some) mail headers. Add new headers (like subject lines). Remove some information from the end of the message. Encrypt part of the message using a key specified in the message. Some but not all remailers can also do the following: Hold messages for some fixed or random time (latency). Reorder messages keeping a fixed minimum number in the remailer at all times. **Attacks on Cypherpunk remailers. Since anonymous remailers are designed to prevent traffic analysis, the best way to understand their weaknesses is to study various attacks that an opponent might use against them. I will assume a very powerful opponent, both to present a worst case scenario, and because it is possible to resist these attacks using second generation remailers. *Threat model. I assume that an attacker is able to record the contents of all messages into and out of all remailers, along with the times they arrive and depart. All messages are monitored as they leave the sender's machine, and as they arrive at the destination. The attacker is able to send an unlimited number of messages through the remailers, including previously intercepted messages. Messages can also be prevented from arriving at their destinations (denial of service). The attacker has compromised some (but not all) of the remailers, and knows the source, destination, and contents of all messages passing through the compromised remailers. This set of attacker abilities and resources is the threat model. *Trivial Attacks. >From the threat model it is prima facie obvious that unencrypted messages can be tracked, so I will consider only encrypted communications. The use of only one remailer is also insecure. If that remailer is compromised, you have no security because the operator knows both the originating and final addresses. *Reordering. Chains of remailers with encryption are better, but still vulnerable. Messages can be traced through these remailers, because incoming messages are forwarded directly after processing. When a message arrives, another leaves immediately. With no further information the attacker knows that these are the same message despite any precautions that may have been taken. This can even be done retroactively using mail logs (if those are kept). This is the biggest problem with standard Cypherpunk remailers. The first fix proposed was to delay incoming messages for some random length of time. If this time were longer than the time between message arrivals, then it would be impossible to know (with certainty) which incoming message corresponded to which outgoing message. This proposal Is weak in several respects. The exact amount of protection provided by latency is unknown. It depends on the traffic through the remailer at that time. If there are many messages arriving in the average holding time, then the identity of the message is reasonably well disguised, but if there is very little traffic (due to normal fluctuations, network outages, or denial of service attacks) then little or no protection is provided. To provide some minimum level of protection, considering only normal traffic variations, the latency must be much larger than it would have to be at times maximum traffic. Although reordering solves this problem, it also opens up another possible attack. Reordering always involves keeping some number of messages in the remailer at all times. These messages are called the message "pool." The most efficient reordering scheme is to keep N messages in the pool, and to send out one of the (N+1) messages in the pool (including the one that just arrived) chosen at random. Unfortunately this scheme is susceptible to a "spam" attack. An attacker sends many more than N messages to the remailer. These messages will displace all the real messages in the pool, leaving only messages which the attacker can recognize.If many more than N messages are sent to a remailer then the its pool of messages will contain only planted messages (which can be recognized). If the attacker sends another batch of messages after your message arrives, your message will be flushed back out of the pool. Since the attacker can recognize his own message, yours will be obvious. Combining latency and reordering gives some resistance to this attack. Rather than sending out one message from the pool each time a new message arrives, periodically all but N messages in the pool are sent. If, during an average period, several real messages have arrived then even if the pool of messages if flushed out, there will be more than just your message mixed in with the attacker's messages. If the attacker combines the spam with a denial of service attack, then your message would be the only non-attacker message again. There is nothing you can do if the attacker can ensure that yours is the only message traversing the entire network of remailers. With ideal remailers your message could be any one of the messages passing through any remailer at the same time. If yours is the only message passing through the remailer network, then you are toast. *Size & Distinguishability. Suppose now that your message is chained through remailers that are delaying and reordering at every hop. Your messages can still be tracked by size. By default messages decreases in size by a small (and approximately known) amount at each hop. Even if your message is well mixed with the other messages in the remailer, and even if they are all different sizes, they are still distinguishable. It is possible to have the remailer remove padding from the message at each hop, but this only to decreases the size of the message, and only to a minimum established by the size of the actual message you want to send. You are also limited by the fact that extremely large messages will stand out, since your message must change size by a large fraction of its own size at each hop to ensure maximum confusion. While removing padding at each step makes traffic analysis much more difficult, it does leak information. All messages that leave a remailer larger than your message was when it arrived are known not to be yours, and if the use of this feature is unusual, then your message will stand out as being the only one to change size by a nonstandard amount. The solution is clear; All messages should be exactly the same size. *Replay attacks Unfortunately reordered, indistinguishable messages, can still be tracked. This attack can be used to follow a message to its final destination, or to backtrack from the end to the original sender. Both of these techniques use a type of spam attack. To trace a message forward through the chain of remailers, the attacker captures your message and sends many copies of it to the first remailer. Many identical messages will then emerge from the remailer and move on to the next remailer. This bump in remailer traffic will show the rout of the message. When it becomes too dispersed from reordering, the message can be captured between two remailers, and many copies re-introduced at that point. To prevent this attack remailers must refuse to send any message more than once. This can be done by including a random ID number for each hop, which the remailer records. Unfortunately this places large storage demands on the remailer, but the impact can be limited if old IDs are removed from the list, or the remailer's key is changed periodically (at which point the list can be cleared). A better solution is to require anonymous ecash postage in each layer. If the message is resent, then the cash has been doubly spent, and the remailer would refuse to send it. This also has the benefit of making spams expensive, and of motivating remailer operators to provide superior services. **Mixmaster. The only type 2 remailer is Mixmaster. Its design philosophy is strongly influenced by Chaum's paper on digital mixes (the origin of its name). Below is a diagram of the structure of a Mixmaster packet. Rather than 4 there are actually 20 headers. Messages are sent as one or more packets (messages consisting of multiple packets are called multi-part messages). Figure 2 When remailer A gets this message, it will decrypt the PGP encrypted packet at the top, and check to see if it has seen the ID number before. If so, the message is discarded. The first header (before decryption) is added to the end of the list of headers, and all the others are shifted up one. All headers and the body packet (the section at the end with the text to be sent) are decrypted with the IDEA key in the header. This reveals a PGP encrypted header for the next remailer at the top, and obscures the old top header (now at the bottom of the stack). The header for the last remailer in the chain contains a flag indicating that it is the last hop, and if it is part of a multipart message. If this packet contains the entire message (it is not a multi-part message), the body is decrypted and the plain text is placed in the reordering pool, ready to be sent on. If it is only one part of the message, the Message ID number is used to identify the other parts as they arrive. When all the parts have arrived the message is reassembled, and placed in the pool. If not all parts arrive within some time limit, then the message is discarded. Only the last remailer in the chain can see that a group of remailer packets are all part of a single message. To all the others, they are completely independent. All Mixmaster packets are exactly the same length, and all bits are encrypted with an IDEA key at every hop, so no information about the identity of the message is visible to the observer. Even a compromised remailer can only know the previous and next locations in the chain. It can not know how many hops have preceded it, or how many will follow (unless it is the final hop). These messages are rather large. Each of the 20 headers are 512 bytes, and the body is 10k. The plain text is compressed to minimize the need for multipart messages, which offer somewhat less security because all parts follow the same chain of remailers. *Future features In the near future the Mixmaster user front end will allow the individual packets of a multipart message to be routed independently. Mixmaster remailers that indicate that they can accept socket connections will exchange messages directly. The messages will be superencrypted with an IDEA key derived from a Diffie-Hellman key exchange. This provides forward security against remailer operators being asked to decrypt intercepted messages. **Nothing is perfect. Even if you are using a perfect network of remailers, you can still be tracked. Only so many messages pass through the network of remailers in any given day. If Alice sending a message usualy correlates with Bob receiving a message, it is likely that she is sending messages to him. This was discussed in some detail in several messages by Hal and Louis Cypher. One defense is to send dummy messages in to the remailer "bramble" so your messages correlate with everything. These must be sent at random times so that your real messages do not stand out. -------------------------------------------------- Lance Cottrell who does not speak for CASS/UCSD loki(a)nately.ucsd.edu PGP 2.6 key available by finger or server. Encrypted mail welcome. Home page http://nately.ucsd.edu/~loki/ Home of "chain" the remailer chaining script. For anon remailer info, mail remailer(a)nately.ucsd.edu Subject: remailer-help "Love is a snowmobile racing across the tundra. Suddenly it flips over, pinning you underneath. At night the ice weasels come." --Nietzsche

1 0

Re: link encryption and anonymous interactivity (Was: "Subway" remai
by lcottrell＠popmail.ucsd.edu 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- >This gives me an idea. Imagine a server that allows you to open a >low bandwidth (let's say around 100 cps, in order to reduce costs) >link-encrypted telnet session with it, and provides you with a number >of services, for example a link-encrypted talk session with another >user. You'll need to maintain the link 24 hours a day to defend >against statistical analysis, and of course you can chain a number of >these servers together in a way similiar to chaining remailers. > >This scheme seems to provide untracibility while getting around the >latency cost problem of remailers, thus allowing users to talk to each >other in real time, anonymously. > >Wei Dai > I like this. One complication comes to mind with chaining. You can not set up the whole chain at once. That would give it all away. In some sense you are only mixed with other people who build these "chain links" at the same time. Since you are only likely to build one or two (once built there is no reason to take it down), you want to build it very slowly to allow many links to be built out of the machine you are connected to before you build your link out the next machine in the chain. Also, if other people take their chains down, you must too, or I suspect that there will be some information pointing to the only chain not to have changed (this would only be statistical). I am not so sure about this last argument though. -Lance Cottrell -----BEGIN PGP SIGNATURE----- Version: 2.6 iQCVAwUBLyi3R1Vkk3dax7hlAQFKnQP9FMKTQ+mEmICIPNXOasd2O/SDy4B4yJtv uMX1AcS8jYSoDLUqf1+j6yGj3NW++5sr/6qNE5+DXpOpc3c3plCoiFIRSL8Ir4dw WmW9J2GBtz5pJEjWWnlCfeqvDnaHmleCDnaGv6vo3+sZJrxn/NpUEoHiduLn+yg8 poIBFxw8B6Y= =2X/2 -----END PGP SIGNATURE----- -------------------------------------------------- Lance Cottrell who does not speak for CASS/UCSD loki(a)nately.ucsd.edu PGP 2.6 key available by finger or server. Encrypted mail welcome. Home page http://nately.ucsd.edu/~loki/ Home of "chain" the remailer chaining script. For anon remailer info, mail remailer(a)nately.ucsd.edu Subject: remailer-help "Love is a snowmobile racing across the tundra. Suddenly it flips over, pinning you underneath. At night the ice weasels come." --Nietzsche

1 0

Re: Even more unix holy war. Was "Clinton freezes U.S. assets .."
by cactus＠seabsd.hks.net 17 Dec '03

17 Dec '03

-----BEGIN PGP SIGNED MESSAGE----- - -----BEGIN PGP SIGNED MESSAGE----- Do you have any sort of life whatsoever, James? Writing a gazillion K of flamage on your hot-button topic du jour, especially when you keep lying about wanting to end the thread, is a total waste of your time, esp. if you believe people will read the spew. (I'm half believing that you're going to call me a collectivist because I imply that one writes so that others will read). I've simply never heard of anybody caring. - - -- Todd Masco | "life without caution/ the only worth living / love for a man/ cactus(a)hks.net | love for a woman/ love for the facts/ protectless" - A Rich Cactus' Homepage - -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBLyiAKhNhgovrPB7dAQFRJAQAkGwvDaHc6FbNsZXglVOuH0I6b79MLqaN cI0rPN2xIwC8w+/cL/jFNaFZDlp4/V1/AZARQaFpY+MMuLsFMBL20c1jAfws/qXO EVFKEWNlRPDo1D85fxvNwT36J+YsLc+PB5ewWlR6AYysh+QBYzZOUhUXJsAo+Lka Kn1PAKFDiZM= =lPZy - -----END PGP SIGNATURE----- - --- [This message has been signed by an auto-signing service. A valid signature means only that it has been received at the address corresponding to the signature and forwarded.] -----BEGIN PGP SIGNATURE----- Version: 2.6.2 Comment: Gratis auto-signing service iQBFAwUBLyi47yoZzwIn1bdtAQFmWwF/UuqPF693wVp6GlI/mkKypPkyyB8thivm WePmowpndywBGGVhtWiVMcZWzqDGEFo2 =Npk+ -----END PGP SIGNATURE-----

1 0

Even more unix holy war. Was "Clinton freezes U.S. assets .."
by jamesd＠com.informix.com 17 Dec '03

17 Dec '03

Todd Masco wrote: > Do you have any sort of life whatsoever, James? [....] > is a total waste of your time, > esp. if you believe people will read the spew. > > I've simply never heard of anybody caring. If you don't care then why are you flaming me, instead of deleting all the posts which I have clearly labeled as being what they are. As to why it is vast and voluminous pile of shit, the answer is because unix is a vast and voluminous, and I was flamed for failing to to give examples of how unix is user hostile. Any report on the defects of unix is necessarily lengthy. I would send off a letter, and get back to work, then immediately unix would bite me again, and I would jump in and send off another letter. The letters kept coming because unix kept biting me. If I had been working on my PC, which refrains from wantonly destroying files and presents the most used options near the top of menus, etc, I would have peaceably ignored this whole silly issue. Indeed I would not have been able to think of a single concrete example of unix user hostility. --------------------------------------------------------------------- | We have the right to defend ourselves | http://www.catalog.com/jamesd/ and our property, because of the kind | of animals that we are. True law | James A. Donald derives from this right, not from the | arbitrary power of the omnipotent state. | jamesd(a)netcom.com

1 0

re: Wei Dei: monitoring
by rkmoore＠iol.ie 17 Dec '03

17 Dec '03

>How would you get access to the trunks? Not that difficult for an intelligence agency. >Aren't they mostly optic fibers now? Can be tapped. >Also, since Internet traffic is growing at a geometric rate, the probability of anyone or any organization having the capacity to monitor and process ALL of Internet traffic should be very small and decreasing. That's what super-computers are for (besides chaos modelling). -rkm --- Richard K. Moore - rkmoore(a)iol.ie - Wexford, Ireland - fax +353 53 23970

1 0

hacker search
by an158409＠anon.penet.fi 17 Dec '03

17 Dec '03

US Marshals On Trail Of Hacker WASHINGTON, D.C., U.S.A., 1995 JAN 26 (NB) -- The US Marshals Service is on the trail of a computer hacker who disappeared after being convicted of one electronic crime and charged with another. Authorities say they are trying to locate Kevin David Mitnick, 31, originally from Sepulveda, California. Deputy US Marshal Kathleen Cunningham told Newsbytes the Marshals Service has had a probation violation warrant for Mitnick since November 1992, and almost caught up with him in Seattle last October. Cunningham said Mitnick is a ham radio enthusiast and is believed to use a scanner to keep track of police in the area where he is hiding. "(Local police) didn't use radio security so as soon as his address was mentioned he was out of there. He just left everything." Cunningham said authorities were able to get quite a bit of information about Mitnick from the things he abandoned when he fled the Seattle location. Mitnick is considered an expert at gaining control of computers to monitor or use communications systems and knows how to manufacture false identities using computers. While still a teenager Mitnick was charged with "cracking" the North American Air Defense Command computer and of using a modem to control telephone switching centers in New York and California. A story last summer in The New York Times reported Mitnick listened in on phone calls and reprogrammed the home telephone of one individual so that each time the phone was picked up a recording asked the phone user to deposit 25 cents. Mitnick was charged with electronically stealing $1 million in secure software from Digital Equipment Corp. causing the company to spend $160,000 to close up the gaps in its computer security. Upon conviction in that case Mitnick was placed on supervisory probation in 1992. He disappeared later that year after he was charged with illegally cracking into Pacific Bell's computers. He is also reportedly a suspect in an incident in which someone illegally accessed the computer at Britain's Loughborough University. An information sheet about Mitnick says that, although he is not considered a dangerous criminal, his activities are costing millions of dollars in the public and private sectors. "Sensitive information illegally accessed by Mitnick would cause continued financial hardship to these various corporations if the information is ever disseminated to others." The document warns authorities who might come in contact with Mitnick to be very cautious and letting him get his hands on any personal information about officers. "He possesses an amazing ability to disrupt one's personal life through his computer knowledge, i.e., TRW's (credit ratings), phone service, etc." warns the US Marshal's Service. When contacted by Newsbytes, spokesperson Dave Fletcher at the Federal Bureau of Investigation Press Office in Washington DC said the FBI does not hold a warrant for Mitnick's arrest. The fugitive warrant held by the US Marshal's Service describes Mitnick as being a Caucasian, 5 feet 11 inches tall with a fair complexion, blue eyes, brown hair, and wearing glasses. (Jim Mallory/19950126/Press contact: US Marshal's Service, 202-307-9000) ------------------------------------------------------------------------- To find out more about the anon service, send mail to help(a)anon.penet.fi. Due to the double-blind, any mail replies to this message will be anonymized, and an anonymous id will be allocated automatically. You have been warned. Please report any problems, inappropriate use etc. to admin(a)anon.penet.fi.

2 1

Re: Oops, Correction: one big error in "Even more unix holy war."
by Bill O'Hanlon 17 Dec '03

17 Dec '03

On Fri, 27 Jan 1995 13:19:01 +0800 jamesd(a)com.informix.com wrote: -------- > > source code variables. > > On this I was of course totally wrong: > > Unix has symbolic debugging equal to DOS/Windows. > I was under the false impression that it only had > C code interpretation. > > This is an error -- what I said was true for C++, but > then in Windows we too are forced to primarily use > interpretation to debug C++. C++ symbolic debuggers > are not up to acceptable capabilities in either system. > > Sorry. It just gets worse and worse. James, the debugging environment I've been referring to, and the product I've been debugging is written in C++. Let me be perfectly clear, here: The product is an embedded processor. I'm running a development environment on a Sun workstation. The code running on the processor is written in C++. The debugger is a symbolic debugger, and it can do breakpoints on lines of code, displays of expressions involving symbolic names, and all of the other points about debuggers that I recall you making. The code uses all C++ features quite heavily. There is no C or C++ interpretation involved. The environment is freely available.

1 0

Re: "Subway" remailers
by xpat＠vm1.spcs.umn.edu 17 Dec '03

17 Dec '03

maher(a)kauai.UCSD.EDU (Kevin E. Maher) writes: > I think what you've described is essentially a "secondary" >remailer, one which only communicates with other remailers in messages >of a fixed size. I'm pretty sure mixmaster can do this, and additionaly >can split a message into chunks and send them on their way via differen >paths. > > If I've misinterpreted what you were describing, please correctme. Hmmm... think of an egg carton, filled with anywhere between zero and twelve eggs. Each egg has its own itinerary as to how many stops it wants to make at other remailers, and whether it wants to change cartons. The eggs would be entire messages, and could "get off" at any particular stop, or at a random stop (based on # of rides(hops?)). The entire carton would be encrypted from one stop to the next. I would anticipate that the single-message architecture of the cpunk remailer would be retained, and that "riding the subway" would be an optional feature. Of course with "passenger" exchange and waiting you essentially get the mixmaster effect, except you are blind to the actual pathway. (remember the MX-missle system, which planned on moving ICBMs from launch site to launch site in an underground matrix of tunnels?) The only thing you would see from the outside is regular pulses of large cargo-carrying (or not) message containers. It might be a partial cover-traffic solution as well, though you still have to worry about entering and exiting the subway system, it's just that it somewhat breaks the identifiable direct traffic-trace links. An even more advanced feature could allow an individual to submit an entire container (loaded with different messages) to the subway system (although this may give an attacker clues about any weakness in randomizing pathways internal to the system, for users utilizing default features). Imagine only submitting one or two messages a day that delivered twenty-five. That might really furrow a traffic analyst's brow. More or less that extends the subway paradigm outside the ring of the system, at least partially, I would guess. I am unsure if there is an existing term for this, but how about "composite mail" containing "aggregate messages"? ------------------------------------------------------------------ P M Dierking |

1 0

RE: Get ready to start breaking rocks for Herr Klinton
by John Douceur 17 Dec '03

17 Dec '03

>From: Sandy Sandfort <sandfort(a)crl.com> .... >With his arms control policy background and current familiarity >with crypto as non-exportable munition, Phil Zimmermann is a >shoo-in for a seat on the president's Arms Proliferaton Board. >Hell, he ought to be the Chairperson! This may have been intended tongue-in-cheek, but I think this is an excellent idea. Think Phil would be interested in the position? How could we get this going? JD

1 0

Re: "Subway" remailers
by xpat＠vm1.spcs.umn.edu 17 Dec '03

17 Dec '03

maher(a)kauai.UCSD.EDU (Kevin E. Maher) writes: > I think what you've described is essentially a "secondary" >remailer, one which only communicates with other remailers in messages >of a fixed size. I'm pretty sure mixmaster can do this, and additionaly >can split a message into chunks and send them on their way via differen >paths. > > If I've misinterpreted what you were describing, please correctme. Hmmm... think of an egg carton, filled with anywhere between zero and twelve eggs. Each egg has its own itinerary as to how many stops it wants to make at other remailers, and whether it wants to change cartons. The eggs would be entire messages, and could "get off" at any particular stop, or at a random stop (based on # of rides(hops?)). The entire carton would be encrypted from one stop to the next. I would anticipate that the single-message architecture of the cpunk remailer would be retained, and that "riding the subway" would be an optional feature. Of course with "passenger" exchange and waiting you essentially get the mixmaster effect, except you are blind to the actual pathway. (remember the MX-missle system, which planned on moving ICBMs from launch site to launch site in an underground matrix of tunnels?) The only thing you would see from the outside is regular pulses of large cargo-carrying (or not) message containers. It might be a partial cover-traffic solution as well, though you still have to worry about entering and exiting the subway system, it's just that it somewhat breaks the identifiable direct traffic-trace links. An even more advanced feature could allow an individual to submit an entire container (loaded with different messages) to the subway system (although this may give an attacker clues about any weakness in randomizing pathways internal to the system, for users utilizing default features). Imagine only submitting one or two messages a day that delivered twenty-five. That might really furrow a traffic analyst's brow. More or less that extends the subway paradigm outside the ring of the system, at least partially, I would guess. I am unsure if there is an existing term for this, but how about "composite mail" containing "aggregate messages"? ------------------------------------------------------------------ P M Dierking |

1 0