From majordom Tue Mar 4 20:31:08 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08992; Tue, 4 Mar 97 20:31:08 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08972; Tue, 4 Mar 97 20:30:34 EST Date: Tue, 4 Mar 1997 20:30:41 -0500 (EST) From: "Michael G. Reed" To: Wei Dai Cc: David Goldschlag , shamrock@netcom.com, goldschlag@itd.nrl.navy.mil, syverson@nrl.navy.mil, daw@cs.berkeley.edu, mccoy@communities.com, onions@itd.nrl.navy.mil Subject: Re: Onion Routing In-Reply-To: Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- On Tue, 4 Mar 1997, Wei Dai wrote: |>There are no references, other than two pieces of email that describe the |>original idea. It is somewhat similar to Onion Routing, but focuses on |>streams rather than packets. I implemented a prototype, but then realized |>that even with constant bandwidth padding, there are a number of attacks |>possible on my original design. I'm currently trying to (but not really |>devoting much time on it) analyze the protocol more clearly. Onion Routing is stream based as well. It runs on top of TCP. To try to do this at the packet level is ludicrously large overhead (we have a reference to a paper that talked about a prototype system that did it at the IP layer, but there were some BIG problems with overhead and handling ICMP messages that may be bounced back to the sender for any packet sent). |>Besides possible attacks, I'm also concerned about possible abuses of |>anonymous routing systems. Have you thought about how to prevent things |>like hackers breaking into computer systems while maintaining anonymity |>with the Onion Routers? That is a political question, and to date, we have tried to only deal with the technological issues instead of the political ones. As soon as we start dealing with political issues, this thing will fall apart. Back in touch with reality though, we are adding the ability for either end of an anonymous connection to blacklist sites or restrict which protocols they support. I would prefer we follow up this discussion on the onion mailing list. The list is unmoderated (and brand spanking new :-). Send mail to Majordomo@itd.nrl.navy.mil with the line "subscribe onions". This will allow us to better track questions/comments/improvements/etc to the system (ie, make sure no one is out of the loop on possible changes to the system). Thanks! - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMxzMxU8Qx019l0ClAQGDQgP/QQFrJe8rMa7RrqonvFc5Yj3bsQGPVdOE 8511aIq2+MheuWEXITz6yqAlm6uoxF0okClHHQQOQqwIoXoKHG1JMkTRBEwrXsCJ v9fLBY9cBfwpRRSZQsZH8/wRXJPZ+/o6i/ypCRtQ79naOqHuDRrKi/ruw36Z7jIE iO9pxEHZkls= =QQqM -----END PGP SIGNATURE----- From majordom Wed Mar 5 00:22:34 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA13239; Wed, 5 Mar 97 00:22:34 EST Received: from homer.communities.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA13220; Wed, 5 Mar 97 00:22:20 EST Received: from [205.162.51.35] (pericles.communities.com [205.162.51.35]) by homer.communities.com (8.7.5/8.7.3) with ESMTP id WAA27990; Tue, 4 Mar 1997 22:57:08 -0800 X-Sender: mccoy@mail.communities.com (Unverified) Message-Id: In-Reply-To: <199703050150.UAA03701@golem.itd.nrl.navy.mil> References: (message from Wei Dai on Tue, 4 Mar 1997 16:59:24 -0800 (PST)) Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 5 Mar 1997 00:21:20 -0500 To: David Goldschlag From: Jim McCoy Subject: Re: Onion Routing Cc: weidai@eskimo.com, onions@itd.nrl.navy.mil Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk David Goldschlag writes: >The abuse you noted, that hackers can break into systems anonymously, >was pointed out in a somewhat happy way by someone who funds computer >security work. Anonymous connections will force better defense. While it may seem like a poor excuse, I am not sure that the identity and authorization problem is something which the basic system should concern itself with. There are a variety of existing methods which can be attached at the entry and exit points of the system (e.g. SSL client cert, SPKI certs and credentials, etc.) It is not as if re-routing packets through poorly logged systems is that difficult now... >Our first network topology for onion routing is a closed system: you >must enter the network somewhere and that point knows where you've >come from and where you are going. So there is some tracking there. >We have another topology where the network knows who you are at entry, >but not where you are going. That introduces more concerns. But you >still need to identify yourself at entry to the network. Entry and exit authorization and authentication should be, IMHO, a local decision. The exit authorization is probably the most important when considering the hacking aspect, transport and application level gatekeepers would probably be best. The exit point is probably going to be the one shouldering the burden of responsibility for such problems, so making it possible for the exit points to enforce a policy regarding this would probably be the best solution. jim From majordom Wed Mar 5 04:54:04 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA16706; Wed, 5 Mar 97 04:54:04 EST Received: from freya.cs.umass.edu by itd.nrl.navy.mil (4.1/SMI-4.1) id AA16700; Wed, 5 Mar 97 04:53:48 EST Received: from opine.cs.umass.edu (opine.cs.umass.edu [128.119.41.246]) by freya.cs.umass.edu (8.7.6/8.6.9) with SMTP id EAA26696; Wed, 5 Mar 1997 04:53:47 -0500 Message-Id: <331D42AB.3F54@cs.umass.edu> Date: Wed, 05 Mar 1997 04:53:47 -0500 From: Lewis McCarthy Organization: Theoretical Computer Science Group, UMass-Amherst, X-Mailer: Mozilla 3.01Gold (X11; U; OSF1 V3.2 alpha) Mime-Version: 1.0 To: onions@itd.nrl.navy.mil Cc: Wei Dai Subject: Re: Onion Routing / Policy References: (message from Wei Dai on Tue, 4 Mar 1997 16:59:24 -0800 (PST)) Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk David Goldschlag writes: > Anonymous connections will force better defense. Anonymous communication mechanisms seem to produce the nice side effect of encouraging people to make their local policy decisions conscious and explicit. Then they start to realize that widely- deployed security mechanisms are very useful for exercising local control over their electronic interactions with other people. The anonymous remailers have stimulated interest in local mail policy controls. When you yank away the origination information that people took for granted (although it was never truly reliable), they have to face the fact that they're fumbling blindly in the dark until they take positive steps to inform the authorization process. -- Lewis http://www.cs.umass.edu/~lmccarth/lmkey.asc "Overwhelmed by 21 documents? Let LiveTopics guide you!" --AltaVista From majordom Wed Mar 5 05:21:36 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA17078; Wed, 5 Mar 97 05:21:36 EST Received: from freya.cs.umass.edu by itd.nrl.navy.mil (4.1/SMI-4.1) id AA17070; Wed, 5 Mar 97 05:21:28 EST Received: from opine.cs.umass.edu (opine.cs.umass.edu [128.119.41.246]) by freya.cs.umass.edu (8.7.6/8.6.9) with SMTP id FAA26891; Wed, 5 Mar 1997 05:21:27 -0500 Message-Id: <331D4927.FF6@cs.umass.edu> Date: Wed, 05 Mar 1997 05:21:27 -0500 From: Lewis McCarthy Organization: Theoretical Computer Science Group, UMass-Amherst, X-Mailer: Mozilla 3.01Gold (X11; U; OSF1 V3.2 alpha) Mime-Version: 1.0 To: onions@itd.nrl.navy.mil Cc: Wei Dai Subject: Re: Onion Routing / Authentication Points References: (message from Wei Dai on Tue, 4 Mar 1997 16:59:24 -0800 (PST)) Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk Jim McCoy writes: > It is not as if re-routing > packets through poorly logged systems is that difficult now... Agreed -- and I don't really foresee that condition changing. [...] > The exit authorization is probably the most important when > considering the hacking aspect, transport and application level > gatekeepers would probably be best. The exit point is probably going > to be the one shouldering the burden of responsibility [...] For auditing purposes, it seems to be desirable for a host on the apparent return path to be able to check its logs and say "they went that-a-way" after an intrusion. Then the first host (working backwards) that didn't authenticate the prior link (or had its logs detectably wiped) catches some heat. If the first such host turns out to be a .mil then the backdraft is likely to be pretty significant. I guess I'm arguing that an organization has a motive to authenticate both at the latest exit point in its administrative domain, and at the earliest entry point in its admin. domain. These points may be distinct. -- Lewis http://www.cs.umass.edu/~lmccarth/lmkey.asc "Overwhelmed by 21 documents? Let LiveTopics guide you!" --AltaVista From majordom Fri Mar 7 08:04:53 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA24009; Fri, 7 Mar 97 08:04:53 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA23997; Fri, 7 Mar 97 08:04:44 EST Date: Fri, 7 Mar 1997 08:04:52 -0500 (EST) From: "Michael G. Reed" To: onions@itd.nrl.navy.mil Subject: Logging... Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- All- Just a question I wanted to bounce off people: What do you all want to see in terms of logging in a system like this? There are a number of very good arguments on both sides of the fence. Currently, a *LOT* of information is logged, but this is so we can continue to debug the system. By its very nature, this system is a beast to debug, so we do keep a lot around for now. My view is that *ALL* logging that does not report an explicit error in the protocol should be removed. This has the side effect of making it impossible to track a connection back once it is terminated (assuming all core nodes also discard their internal identifiers or reuse them -- I trash them as soon as I can right now and reuse is governed by random probability). If a connection is still in place, then the path can be determined with the help of all core routers taking part in the connection (a bitch even at that, but possible). A few people have commented that 'traceability' may be desirable for legal reasons, but I would argue the contrary. Would it not be possible to consider the system as a Common Carrier in the telephony sense (ie, they cannot be held responsible for the actions of the users, they are merely a conduit that anyone can use) or does this then mandate that we have a way to tap the communications channels (impossible except at the endpoints)? Comments? - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyASeE8Qx019l0ClAQHkvgP/e7JZ65QsX5Ik5WAFlyn+U102c0h+lelH K880Du7bBxIZ8T526akJI7LzFZQY8eNSSqverWl8Jofe4PZ5zWc1pv1VmQKDsCJd SWKw6rfCa92fqXd6nUxzwaWlu5gKbtWkhguFvbobbC38MnQ7z8utgp+I1stIz8vw rdAg+hfYd0E= =brOn -----END PGP SIGNATURE----- From majordom Fri Mar 7 15:11:31 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA16179; Fri, 7 Mar 97 15:11:31 EST Received: from netcom12.netcom.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA16173; Fri, 7 Mar 97 15:11:24 EST Received: from sfbayarea (h96-223.ccnet.com [192.215.96.223]) by netcom12.netcom.com (8.6.13/Netcom) id MAA16670; Fri, 7 Mar 1997 12:11:22 -0800 Message-Id: <3.0.32.19970307121225.006f05a8@netcom9.netcom.com> X-Sender: shamrock@netcom9.netcom.com X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Fri, 07 Mar 1997 12:12:36 -0800 To: "Michael G. Reed" , onions@itd.nrl.navy.mil From: Lucky Green Subject: Re: Logging... Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk At 08:04 AM 3/7/97 -0500, Michael G. Reed wrote: >-----BEGIN PGP SIGNED MESSAGE----- > >All- > Just a question I wanted to bounce off people: What do you all >want to see in terms of logging in a system like this? There are a >number of very good arguments on both sides of the fence. Currently, >a *LOT* of information is logged, but this is so we can continue to >debug the system. Sure. During debugging, logging is required. > By its very nature, this system is a beast to >debug, so we do keep a lot around for now. My view is that *ALL* >logging that does not report an explicit error in the protocol should >be removed. I agree. > This has the side effect of making it impossible to track >a connection back once it is terminated (assuming all core nodes also >discard their internal identifiers or reuse them -- I trash them as >soon as I can right now and reuse is governed by random probability). >If a connection is still in place, then the path can be determined >with the help of all core routers taking part in the connection (a >bitch even at that, but possible). A few people have commented that >'traceability' may be desirable for legal reasons, but I would argue >the contrary. The user should assume that all traffic at all sites not under his direct control is logged except one site. If the system then still provides full untraceability, it is designed well. If not, you need to rework the design. This is just like with Mixmasters. You assume that one Mixmaster is not logging internally, but that it is watched from the outside. You further assume that all other Mixmasters in the chain may be fully compromised. In production mode, the operators should not log anything but exceptions. But the user shouldn't have to rely on this. -- Lucky Green PGP encrypted mail preferred "I do believe that where there is a choice only between cowardice and violence, I would advise violence." Mahatma Gandhi From majordom Sun Mar 9 13:48:47 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA25136; Sun, 9 Mar 97 13:48:47 EST Received: from golem.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA25128; Sun, 9 Mar 97 13:48:38 EST Received: (from goldschl@localhost) by golem.itd.nrl.navy.mil (8.8.5/8.7.3) id NAA01094; Sun, 9 Mar 1997 13:48:31 -0500 (EST) Date: Sun, 9 Mar 1997 13:48:31 -0500 (EST) Message-Id: <199703091848.NAA01094@golem.itd.nrl.navy.mil> From: David Goldschlag To: shamrock@netcom.com Cc: reed@itd.nrl.navy.mil, onions@itd.nrl.navy.mil In-Reply-To: <3.0.32.19970307121225.006f05a8@netcom9.netcom.com> (message from Lucky Green on Fri, 07 Mar 1997 12:12:36 -0800) Subject: Re: Logging... Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk Regarding logs. I agree with Michael that we should remove all logging (except for errors) once we are finished with the limited test. But that doesn't address Shamrock's question: The user should assume that all traffic at all sites not under his direct control is logged except one site. If the system then still provides full untraceability, it is designed well. If not, you need to rework the design. This is just like with Mixmasters. You assume that one Mixmaster is not logging internally, but that it is watched from the outside. You further assume that all other Mixmasters in the chain may be fully compromised. We are essentially doing real-time mixing, under the hypothesis that if there is sufficient traffic, one does not need to delay traffic very much to do good mixing, nor does one need to add padding. If the network is not heavily utilized, we will need to add padding. The unanswered question is what is the balance between the delay needed to do mixing, the utilization level, and padding. If we need to add lots of padding even when the network is heavily utilized, then our approach will not be viable, because it will not use the network efficiently. Our goal is a system that many people will use, but that provides strong protection. If the first onion router in an anonymous connection is compromised, then everything is revealed, since (in our current model) the first onion router knows both endpoints of a connection. If all onion routers but the first in an anonymous connection are compromised, then the connection can be tracked back to the first onion router. If that onion router lives on a firewall and the connection originated from inside the firewall, then the source site will be revealed, but not the particular machine. If connections to that onion router are not hidden, then the set of source machines is revealed also. This weakness applies to mix based remailers also, I think, except that the set of source machines may be larger, because mail may be delayed for a while at the first remailer. If the first onion router and some intermediate onion router in the anonymous connection are not compromised, then it is hard to match incoming to outgoing traffic at the intermediate onion router. Now if attacks can be active, and traffic between nodes can be interrupted, and the uncompromised node does not respond by padding traffic, then more information can be obtained. David. From majordom Sun Mar 9 18:02:47 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA28209; Sun, 9 Mar 97 18:02:47 EST Received: from netcom12.netcom.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA28197; Sun, 9 Mar 97 18:02:37 EST Received: from sfbayarea (h96-131.ccnet.com [192.215.96.131]) by netcom12.netcom.com (8.6.13/Netcom) id PAA27000; Sun, 9 Mar 1997 15:02:33 -0800 Message-Id: <3.0.32.19970309150344.006f0624@netcom9.netcom.com> X-Sender: shamrock@netcom9.netcom.com X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Sun, 09 Mar 1997 15:04:06 -0800 To: David Goldschlag From: Lucky Green Subject: Re: Logging... Cc: reed@itd.nrl.navy.mil, onions@itd.nrl.navy.mil, raph@acm.org, jeremey@veriweb.com Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk At 01:48 PM 3/9/97 -0500, David Goldschlag wrote: > >Regarding logs. I agree with Michael that we should remove all >logging (except for errors) once we are finished with the limited >test. But that doesn't address Shamrock's question: When are you going to make the source available? I have talked with a number of folks that are interested in running (improved) onion routers. [We discussed Onion Routers, Pipe-Net, and Raph Levien's new proposal at yesterday's monthly Cypherpunks meeting. I am cc'ing some of the participants.] >We are essentially doing real-time mixing, under the hypothesis that >if there is sufficient traffic, one does not need to delay traffic >very much to do good mixing, nor does one need to add padding. I believe this hypothesis can not be safely made. Traffic patterns vary widely, depending on the time of day and other factors. The attacker doesn't need much correlation to conduct traffic analysis. The system should be secure from traffic analysis even when there are only two users on the network. This can be achieved by moving the first proxy on the user's machine and keeping the data streams constant within each segment of the network. > If the >network is not heavily utilized, we will need to add padding. The >unanswered question is what is the balance between the delay needed to >do mixing, the utilization level, and padding. If we need to add lots >of padding even when the network is heavily utilized, then our >approach will not be viable, because it will not use the network >efficiently. Our goal is a system that many people will use, but that >provides strong protection. Using the Pipe-Net approach, the load on the network remains constant until the pipe is saturated. [Note that the heavier the network usage, the less padding is added. If the network is fully utilized, no padding is added.] If you are correct in your assumption that the network will be widely used than using a Pipe-Net approach will not add much overhead. If however there will be times of low network usage, the constant bandwidth pipes will protect the users that use the network at that time. One question may be what to do if the load saturates the pipe. If that happens, you can add delays. As long as the last proxy is on the user's machine, these artificial delays won't create a traffic analysis opportunity. >If the first onion router in an anonymous connection is compromised, >then everything is revealed, since (in our current model) the first >onion router knows both endpoints of a connection. No router should ever know more than the previous and the next router. Except of course the "router" sitting on the user's machine, which would simply be a client side HTTP proxy. >If the first onion router and some intermediate onion router in the >anonymous connection are not compromised, then it is hard to match >incoming to outgoing traffic at the intermediate onion router. Now if >attacks can be active, and traffic between nodes can be interrupted, >and the uncompromised node does not respond by padding traffic, then >more information can be obtained. That's why padding is a must. [Raph, I would encourage you to post your system to this list. It addresses a different set of problems, but they are certainly related to the issue of anonymous web browsing.] -- Lucky Green PGP encrypted mail preferred "I do believe that where there is a choice only between cowardice and violence, I would advise violence." Mahatma Gandhi From majordom Mon Mar 10 04:39:31 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA06061; Mon, 10 Mar 97 04:39:31 EST Received: from einstein.veriweb.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA06054; Mon, 10 Mar 97 04:39:20 EST Received: (from jeremey@localhost) by einstein.veriweb.com (8.8.5/8.6.9) id BAA09519; Mon, 10 Mar 1997 01:42:57 GMT Message-Id: <3323671D.7E9F12DE@veriweb.com> Date: Mon, 10 Mar 1997 01:42:53 +0000 From: Jeremey Barrett Organization: VeriWeb Internet Corp. X-Mailer: Mozilla 3.01 (X11; U; Linux 2.0.11 i586) To: shamrock@netcom.com Cc: David Goldschlag , reed@itd.nrl.navy.mil, onions@itd.nrl.navy.mil, raph@acm.org Subject: Re: Logging... References: <3.0.32.19970309150344.006f0624@netcom9.netcom.com> Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- Lucky Green wrote: > > At 01:48 PM 3/9/97 -0500, David Goldschlag wrote: > > > >Regarding logs. I agree with Michael that we should remove all > >logging (except for errors) once we are finished with the limited > >test. But that doesn't address Shamrock's question: > > When are you going to make the source available? I have talked with a > number of folks that are interested in running (improved) onion routers. > > [We discussed Onion Routers, Pipe-Net, and Raph Levien's new proposal at > yesterday's monthly Cypherpunks meeting. I am cc'ing some of the > participants.] > > >We are essentially doing real-time mixing, under the hypothesis that > >if there is sufficient traffic, one does not need to delay traffic > >very much to do good mixing, nor does one need to add padding. > > I believe this hypothesis can not be safely made. Traffic patterns vary > widely, depending on the time of day and other factors. The attacker > doesn't need much correlation to conduct traffic analysis. This is true, plus even in peak traffic periods, you probably will not get "even" traffic. It will likely be bursty, or at least it _may_ be bursty. So traffic analysis may or may not be possible based on the time of day and luck of the draw. It would be best to be resistant to traffic analysis always, as Lucky suggests. Timing attacks are a concern, though probably hard to implement. If I can watch traffic entering and leaving the (core) nodes, then I can pretty well guess, for any given load, who's going where. i.e. if it takes 3 seconds for a request to enter the network at one point and pop out at another, then an educated guess about who's talking to who requires no active attack. That's not to say it's easy. This also is not affected by constant traffic, unless the constant traffic is sufficiently "real" traffic that outbound (to "real" hosts) connections are created so fast that differentiating them is hard. Having large numbers of routers certainly makes this much more difficult. > > The system should be secure from traffic analysis even when there are > only two users on the network. This can be achieved by moving the first > proxy on the user's machine and keeping the data streams constant > within each segment of the network. > > > If the > >network is not heavily utilized, we will need to add padding. The > >unanswered question is what is the balance between the delay needed to > >do mixing, the utilization level, and padding. If we need to add lots > >of padding even when the network is heavily utilized, then our > >approach will not be viable, because it will not use the network > >efficiently. Our goal is a system that many people will use, but that > >provides strong protection. > > Using the Pipe-Net approach, the load on the network remains constant > until the pipe is saturated. [Note that the heavier the network usage, > the less padding is added. If the network is fully utilized, no padding > is added.] If you are correct in your assumption that the network will > be widely used than using a Pipe-Net approach will not add much > overhead. If however there will be times of low network usage, the > constant bandwidth pipes will protect the users that use the network at > that time. > > One question may be what to do if the load saturates the pipe. If that > happens, you can add delays. As long as the last proxy is on the user's > machine, these artificial delays won't create a traffic analysis > opportunity. I don't see what can be learned from a saturated net. If all the data is real and the net is running at full capacity, then that's optimal. > > >If the first onion router in an anonymous connection is compromised, > >then everything is revealed, since (in our current model) the first > >onion router knows both endpoints of a connection. > > No router should ever know more than the previous and the next router. > Except of course the "router" sitting on the user's machine, which would > simply be a client side HTTP proxy. In this case, the client side proxy is the first router. It's compromise is equal to compromising the first router in the net if no client side proxies exist. > > >If the first onion router and some intermediate onion router in the > >anonymous connection are not compromised, then it is hard to match > >incoming to outgoing traffic at the intermediate onion router. Now if > >attacks can be active, and traffic between nodes can be interrupted, > >and the uncompromised node does not respond by padding traffic, then > >more information can be obtained. > > That's why padding is a must. Agreed. But again, if you take the core Pipe-Net (by core I mean not counting client side proxies) routers and consider them one black box, then timing things entering and leaving the black box is dangerous, if the number of such things is manageable. BTW I'm very sleepy, so shoot anything that's incoherent or blatantly obvious :-) Jeremey. - -- =-----------------------------------------------------------------------= Jeremey Barrett VeriWeb Internet Corp. Crypto, Ecash, Commerce Systems http://www.veriweb.com/ PGP Key fingerprint = 3B 42 1E D4 4B 17 0D 80 DC 59 6F 59 04 C3 83 64 =-----------------------------------------------------------------------= -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyNnIS/fy+vkqMxNAQFrPAP/YdCkOf8x9mXuX4at77VrHhVZeHaw4Bat up03pc4P0n0c/7N8SqUVZYzISXSFILgkUXdcHmcFOHkr+bU/gX20L6k+F9NUD4qN dZNBlSkhu+ylAxXaXkH7hX2+J8oyj1RmfGEjkil7AVmxBAdTj5FZFxz2P/+u12tS PVpEh4h+GIQ= =6Zbs -----END PGP SIGNATURE----- From majordom Mon Mar 10 07:05:14 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08001; Mon, 10 Mar 97 07:05:14 EST Received: from einstein.veriweb.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA07988; Mon, 10 Mar 97 07:05:04 EST Received: (from jeremey@localhost) by einstein.veriweb.com (8.8.5/8.6.9) id EAA09665 for onions@itd.nrl.navy.mil; Mon, 10 Mar 1997 04:08:49 GMT Message-Id: <33238945.54014F73@veriweb.com> Date: Mon, 10 Mar 1997 04:08:37 +0000 From: Jeremey Barrett Organization: VeriWeb Internet Corp. X-Mailer: Mozilla 3.01 (X11; U; Linux 2.0.11 i586) To: onions@itd.nrl.navy.mil Subject: Onion routing: thoughts References: <3.0.32.19970309150344.006f0624@netcom9.netcom.com> Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- Since I just joined the list, I'm gonna recap what's in my head and what I think the issues are. Please add or remove items if necessary: Some potential problems with onion routing as described in the "Hiding Routing Information" paper (some of these are addressed in the paper itself): o The assumption that usage will be constant and high may not be not valid o Traffic analysis in a non-optimal (i.e. not evenly utilized all the time) net will not be difficult (just follow the packets) The solution to this seems to be constant utilization by simply sending data all the time, real or not. o Timing attacks are effective during low-use of the net, even if the net is saturated with fake data. (If a manageable number of routers exist. Large numbers make this more difficult). One possible solution to this would be the initiator sending a bunch of fake onions around, so that the endpoint cannot easily be indentified. Unfortunately, this might involve _alot_ of fake onions. However, as the usage of the net increased, the number of fakes required would decrease. o Some information may be obtained by denial of service attacks at particular points. Depending on the number of connections at the moment, etc, it may be possible to induce a traceable chain of "destroy" messages. This again argues for constant data streams between routers. Some other thoughts: All in all, I think a "Pretty Good Onion Router" is a good idea. I would love to be able to hit web sites without them knowing where I'm coming from, where the performance is good and I'm fairly secure in the knowledge that only someone really determined and skilled could trace me, if at all. So my suggestion is that once a "Pretty Good Onion Router" system is in place, then we focus on making it as bulletproof as possible. Have "boomerang" (my term, dunno if a real one exists) routes been considered? A boomerang route would be forward-only. i.e. rather than an onion containing the responder's proxy node as the endpoint, it would contain itself. Then the onion would describe a forward-only path from a router back to itself. The responder's proxy node would get a slightly different packet, identifying it as "the" node. Rather than specify both forward and reverse crypto operations, only forward would be specified. All operations up to the responder's proxy node would be decryption, all subsequent operations would be encryption. This might have several benefits: o The endpoint, even with no dummy data being sent around, is more difficult to identify. o Intermediate nodes could be given fake responder requests, and return data along the circuit just as the real one does. The real data would be indistinguishable from the fake. This would also further compliate endpoint determination, since all the routers appear to be endpoints. o Looking at it, the real endpoint is no different at all from the fake ones, if fake endpoint requests are sent to all routers. The initiator would need to include a connection id for each router, so the correct data could be indentified. Some drawbacks: o The initiator must receive all the fake data as well as the real. (this might also be a feature) o Generating fake requests may not be easy (at least to always be believable). What gets sent _to_ the fake connections as "data"? (for HTTP, what URL do you ask for?) o This may not work very well (or not any better anyway) for anything other than HTTP, NNTP, or similar. (I can't see this working well for telnet) o Other as-yet-unforseen things I'm too tired to think of. Responses and flames please :-) Jeremey. - -- =-----------------------------------------------------------------------= Jeremey Barrett VeriWeb Internet Corp. Crypto, Ecash, Commerce Systems http://www.veriweb.com/ PGP Key fingerprint = 3B 42 1E D4 4B 17 0D 80 DC 59 6F 59 04 C3 83 64 =-----------------------------------------------------------------------= -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyOJTy/fy+vkqMxNAQFs3gP9GkH3OZMp5RTHUvPTaDO62WChgyxs7Hgd WCfBILuMZkdH6Wx+/YYTNqFflnMr0J8eQ8r6d3i/hct0b0Zdjs2p2txXPL3vwSdF ncf5NhUcOnFJh8JucjKtblzuP5E1xSdBC49afIg4HL4kHiUxEr2xAaUkLRlFvmac ADCVb1GKoYA= =CDew -----END PGP SIGNATURE----- From majordom Mon Mar 10 11:14:16 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA20199; Mon, 10 Mar 97 11:14:16 EST Received: from golem.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA20170; Mon, 10 Mar 97 11:13:54 EST Received: (from goldschl@localhost) by golem.itd.nrl.navy.mil (8.8.5/8.7.3) id LAA01552; Mon, 10 Mar 1997 11:13:48 -0500 (EST) Date: Mon, 10 Mar 1997 11:13:48 -0500 (EST) Message-Id: <199703101613.LAA01552@golem.itd.nrl.navy.mil> From: David Goldschlag To: onions@itd.nrl.navy.mil Cc: jeremey@veriweb.com In-Reply-To: <33238945.54014F73@veriweb.com> (message from Jeremey Barrett on Mon, 10 Mar 1997 04:08:37 +0000) Subject: Re: Onion routing: thoughts Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk Thanks for your summary. Here is our position about onion routing. Onion routing provides four mechanisms: (1) Mechanisms for maintaining the topology of the network. (2) Onion routers that support anonymous connections that reliably carry data bidirectionally between some first onion router and some last onion router. (3) An onion creation mechanism that defines and creates the anonymous connection. (4) Interfaces between the anonymous connections and other applications. We currently provide application level proxies for HTTP, SMTP, and RLOGIN, and anonymizing versions of those proxies. Other interfaces may collect data at the IP level. Currently, our onion creation mechanism lives on the first onion router, but it does not need to. There are trade-offs associated with the location of that mechanism. There are three ways to add extra data into the onion routing network. Onion routers do not pad data in an anonymous connection. That can be done outside the system. Onion routers do not introduce extra anonymous connections to confuse traffic analysis. That too can be done outside the system. Our implementation of onion routing does define a padding cell that can carry dummy traffic between two onion routers. Our onion routers do not produce such cells, but do ignore such cells. Our position on padding is that constant utilization of an onion routing network may not be necessary to complicate traffic analysis. We still have to validate this hypothesis. If constant utilization is necessary, the system will not scale well, will use network resources inefficiently, and will not be widely adopted. It may be necessary to smooth out utilization through the three padding approaches described above, and onion routing provides an infrastructure within which these questions can be answered and solutions explored. Our goal is not pretty good onion routers. Our goal is a communications infrastructure that is resistant to traffic analysis, that can efficiently deliver traffic throughout the network, and that will be widely deployed. David. From majordom Mon Mar 10 15:40:18 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA04398; Mon, 10 Mar 97 15:40:18 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA04382; Mon, 10 Mar 97 15:40:08 EST Date: Mon, 10 Mar 1997 15:40:14 -0500 (EST) From: "Michael G. Reed" To: onions@itd.nrl.navy.mil Subject: Re: Logging... In-Reply-To: <3.0.32.19970309150344.006f0624@netcom9.netcom.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- NOTE: Cc's trimmed since the onions mailing lists contained all the people addressed initially. On Sun, 9 Mar 1997, Lucky Green wrote: |>When are you going to make the source available? I have talked with a |>number of folks that are interested in running (improved) onion routers. The source will be made available when we can make it available. The first cut of tests will be with binary only distribution and these tests are SOLELY for the purpose of getting some hard numbers on the performance of the system and identifying some of the bottlenecks -- there is only so much I can do in my lab, and only so many people have $25k machines at their disposal to run tests...we need some real-world numbers on real-world systems, on the real-world Internet. The system, as it is written today, will most likely undergo some major structural changes (some are already planned, some more will probably become evident once we get some more numbers on system performance) in the weeks to come and it is far to premature to distribute source widely. |>[We discussed Onion Routers, Pipe-Net, and Raph Levien's new proposal at |>yesterday's monthly Cypherpunks meeting. I am cc'ing some of the |>participants.] Which cypherpunks meeting are you referring to? DC? Bay Area? Where? We would be interested in hearing those discussions and participating in the future if possible...the more feedback we can get, the better the system will be. |>>We are essentially doing real-time mixing, under the hypothesis that |>>if there is sufficient traffic, one does not need to delay traffic |>>very much to do good mixing, nor does one need to add padding. |> |>I believe this hypothesis can not be safely made. Traffic patterns vary |>widely, depending on the time of day and other factors. The attacker |>doesn't need much correlation to conduct traffic analysis. This is true, but this also assumes that said attacker has sniffers at the entry to *EVERY* onion-router on the internet...miss only one and you have a problem. We are not suggesting that padding is not necessary. Certainly, there will be times (lots of times) we need to pad data. *BUT* just throwing padding at the problem does *NOT* solve it (this has been shown). |>The system should be secure from traffic analysis even when there are only |>two users on the network. This can be achieved by moving the first proxy on |>the user's machine and keeping the data streams constant within each |>segment of the network. Keeping data streams constant on the Internet is infeasible unless they are of such pathetically low bandwidth as to make them unusable. Simply put, at the layer of the network stack we are operating at, and given the current congestion on the major backbones (including packet loss), I think it is a pipe-dream (pardon the pun) to think you will be able to hit constant (full) bandwidth with padding. In terms of moving the onion creation to the local machine, that is possible (and even defined) in our system. As a matter of fact, that is one of the fundamental shifts that we are looking at making in the system, and it is documented in some detail in the papers. |>One question may be what to do if the load saturates the pipe. If that |>happens, you can add delays. As long as the last proxy is on the user's |>machine, these artificial delays won't create a traffic analysis opportunity. Ah, but *WHERE* do the delays appear? Anywhere down the length of the circuit for which you have no information about utilization and therefore you much rely on the system to throttle you down...the problem does not go away simply by moving the last hop. |>>If the first onion router in an anonymous connection is compromised, |>>then everything is revealed, since (in our current model) the first |>>onion router knows both endpoints of a connection. |> |>No router should ever know more than the previous and the next router. |>Except of course the "router" sitting on the user's machine, which would |>simply be a client side HTTP proxy. Yes, and in the topology you just described, the "router" on the user's machine is the first onion-router, thus only it knows the whole path. - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyRxs08Qx019l0ClAQEDuQP+JO/z0X09htcPTYAfbbZgXv1evH2QbzyU BsESObmrczv5VpuyIPiOzDwgsrX6GXc9aRM3gPyktU8VqOFn9ggBSW7S/2MfRSXE bP7JWtM80ese3vJjIiJuoNf1hZySoiNe1sG1StXDRw6wxdtzuwGNZ339nLm3j14O N3BBD7JJrf0= =A/Mi -----END PGP SIGNATURE----- From majordom Mon Mar 10 15:56:31 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA05166; Mon, 10 Mar 97 15:56:31 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA05160; Mon, 10 Mar 97 15:56:22 EST Date: Mon, 10 Mar 1997 15:56:32 -0500 (EST) From: "Michael G. Reed" To: onions@itd.nrl.navy.mil Subject: Re: Onion routing: thoughts In-Reply-To: <33238945.54014F73@veriweb.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- On Mon, 10 Mar 1997, Jeremey Barrett wrote: |> o The assumption that usage will be constant and high may not be not |> valid This is true. We really do not know what the demand will be yet for the service, but if you look at how overloaded the Anonymizer is most of the time, I think we can assume it will be moderate at the least. |> o Traffic analysis in a non-optimal (i.e. not evenly utilized all |> the time) net will not be difficult (just follow the packets) |> The solution to this seems to be constant utilization by simply |> sending data all the time, real or not. As I said before, simple padding does not solve the problem. The onion routers themselves know what is pad and what is not (unless you create dummy connection and pad through the connections in which case the first and last onion router knows it pad but not the intermediates and this doesn't solve the link-level padding problem). |> o Timing attacks are effective during low-use of the net, even if |> the net is saturated with fake data. (If a manageable number of |> routers exist. Large numbers make this more difficult). |> |> One possible solution to this would be the initiator sending |> a bunch of fake onions around, so that the endpoint cannot |> easily be indentified. Unfortunately, this might involve _alot_ |> of fake onions. However, as the usage of the net increased, the |> number of fakes required would decrease. Simply having more endpoints to the system does not increase the difficulty to track coincidences...you need data moving into and out of the overall network to make it more difficult. Either dummy services, or just meaningless requests on pre-defined protocols. |> o Some information may be obtained by denial of service attacks at |> particular points. Depending on the number of connections at the |> moment, etc, it may be possible to induce a traceable chain of |> "destroy" messages. This again argues for constant data streams |> between routers. The "Destroy flurry" that we describe when a thick-pipe goes down is a problem, but it's one that we haven't been able to come up with a good solution for. We have a couple of possibilities (including delaying the destruction of the circuits that went through that thick pipe and dropping them at random intervals thereafter), but are still looking at that. |> All in all, I think a "Pretty Good Onion Router" is a good idea. |> I would love to be able to hit web sites without them knowing |> where I'm coming from, where the performance is good and I'm fairly |> secure in the knowledge that only someone really determined and |> skilled could trace me, if at all. So my suggestion is that once |> a "Pretty Good Onion Router" system is in place, then we focus on |> making it as bulletproof as possible. While "Pretty Good" might be good enough for some, we are really looking to get this right, get a RFC out there, and get this thing deployed world-wide as soon as possible. That doesn't allow for "Pretty Good". It means we do some experimenting now, draw on the best and brightest that are available, and get input from people during this initial period to DO IT RIGHT THE FIRST TIME. Of course this means it won't be out next week, but I think the general population would prefer something that works the first time than an evolution of shoddy systems that really were never right. |> Have "boomerang" (my term, dunno if a real one exists) routes |> been considered? A boomerang route would be forward-only. i.e. |> rather than an onion containing the responder's proxy node as the |> endpoint, it would contain itself. Then the onion would describe |> a forward-only path from a router back to itself. The responder's |> proxy node would get a slightly different packet, identifying |> it as "the" node. Rather than specify both forward and reverse |> crypto operations, only forward would be specified. All operations |> up to the responder's proxy node would be decryption, all subsequent |> operations would be encryption. I'm not sure I follow this completely (or what the motivation is for it completely), can you elaborate some more on it? Thanks! - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyR1g08Qx019l0ClAQFudAQApnaTxMg9h23v8VWk06QBlq6D0oa1i/xK fITKJUZuRs+WVDZMhhCVouEDggsBZL4o6yQ15TMbnCDx9rpi+LIA7CZom3UtZf7T pi1/1o9WPI9Q++EnRA1x+xkoVaKiXhMTR0e+8Ic0L/mzOjK+/y+2nXVDeiUJaJXR pf4vnaOBRuQ= =D7Gv -----END PGP SIGNATURE----- From majordom Mon Mar 10 16:55:22 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08201; Mon, 10 Mar 97 16:55:22 EST Received: from golem.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08189; Mon, 10 Mar 97 16:55:14 EST Received: (from goldschl@localhost) by golem.itd.nrl.navy.mil (8.8.5/8.7.3) id QAA01659; Mon, 10 Mar 1997 16:55:09 -0500 (EST) Date: Mon, 10 Mar 1997 16:55:09 -0500 (EST) Message-Id: <199703102155.QAA01659@golem.itd.nrl.navy.mil> From: David Goldschlag To: onions@itd.nrl.navy.mil Subject: discussion points Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk Hi, We are planning to release code this week for testing. Testsers have to agree not to redistribute code. Soon we hope to put the code on a site that will re-distribute within the US. It would be useful to start a discussion about what we are trying to hide and what may do that hiding. I'm looking for communication models, attack models, carefully stated requirements, and justified solutions. For example, precisely what do we by "assume only a single uncompromised onion router?" As another example, if two sites connect (encrypted) to remote onion routers at roughly the same time, it is more likely that they are communicating than if they didn't connect at roughly the same time. This is hard to protect against. Do we need constant utilization or is smoothing sufficient? Do we want to add noice to individual connections? Do we want terminal onion router to terminal onion router padding (noise connections)? Do we want padding between neighboring onion routers? I'm looking to leverage off the expertise in this list, so we can build strong hiding around the onion routing infrastructure. Thanks, David. From majordom Mon Mar 10 17:05:15 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08718; Mon, 10 Mar 97 17:05:15 EST Received: from einstein.veriweb.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08680; Mon, 10 Mar 97 17:05:02 EST Received: (from jeremey@localhost) by einstein.veriweb.com (8.8.5/8.6.9) id OAA10237; Mon, 10 Mar 1997 14:08:35 -0800 Message-Id: <3324865F.1512DC9A@veriweb.com> Date: Mon, 10 Mar 1997 22:08:31 +0000 From: Jeremey Barrett Organization: VeriWeb Internet Corp. X-Mailer: Mozilla 3.01 (X11; U; Linux 2.0.11 i586) To: "Michael G. Reed" Cc: onions@itd.nrl.navy.mil Subject: Re: Onion routing: thoughts References: Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- Michael G. Reed wrote: > > |> o Timing attacks are effective during low-use of the net, even if > |> the net is saturated with fake data. (If a manageable number of > |> routers exist. Large numbers make this more difficult). > |> > |> One possible solution to this would be the initiator sending > |> a bunch of fake onions around, so that the endpoint cannot > |> easily be indentified. Unfortunately, this might involve _alot_ > |> of fake onions. However, as the usage of the net increased, the > |> number of fakes required would decrease. > > Simply having more endpoints to the system does not increase the > difficulty to track coincidences...you need data moving into and out of > the overall network to make it more difficult. Either dummy services, > or just meaningless requests on pre-defined protocols. I agree. But more endpoints does mean you have to monitor more points of entry/exit to identify coincidences reliably. > > |> All in all, I think a "Pretty Good Onion Router" is a good idea. > |> I would love to be able to hit web sites without them knowing > |> where I'm coming from, where the performance is good and I'm fairly > |> secure in the knowledge that only someone really determined and > |> skilled could trace me, if at all. So my suggestion is that once > |> a "Pretty Good Onion Router" system is in place, then we focus on > |> making it as bulletproof as possible. > > While "Pretty Good" might be good enough for some, we are really > looking to get this right, get a RFC out there, and get this thing > deployed world-wide as soon as possible. That doesn't allow for > "Pretty Good". It means we do some experimenting now, draw on the > best and brightest that are available, and get input from people > during this initial period to DO IT RIGHT THE FIRST TIME. Of course > this means it won't be out next week, but I think the general > population would prefer something that works the first time than an > evolution of shoddy systems that really were never right. I agree completely. I intended "Pretty Good" in the spirit of PGP. There is a danger of trying to solve _too_ much and never getting anything done. That's not to say I think that will happen here. > > |> Have "boomerang" (my term, dunno if a real one exists) routes > |> been considered? A boomerang route would be forward-only. i.e. > |> rather than an onion containing the responder's proxy node as the > |> endpoint, it would contain itself. Then the onion would describe > |> a forward-only path from a router back to itself. The responder's > |> proxy node would get a slightly different packet, identifying > |> it as "the" node. Rather than specify both forward and reverse > |> crypto operations, only forward would be specified. All operations > |> up to the responder's proxy node would be decryption, all > |> subsequent operations would be encryption. > > I'm not sure I follow this completely (or what the motivation is for it > completely), can you elaborate some more on it? Thanks! > Instead of a connection with two endpoints, the idea is a connection with only one (obvious) endpoint. The first router, let's say on the user's machine, creates an onion which identifies a chain of routers such that it (the first router) is the _endpoint_ of the route. Now it sends a "data" message along the route. The router which receives a data message in the clear (after applying the crypto operation) is the one which goes and satisfies the data request. Once the data is retrieved, it applies an outgoing crypto operation and sends the data along the route, still in the forward direction. No messages travel backwards. A simple analogy is a circle as opposed to a line. I can see a few potential advantages here: o The node which actually satisfies the data request cannot be identified simply by being the terminating node of a connection, since the terminating node is the same as the first router. o You can't "follow" packets to one end or the other because they always complete the route back to the sender. o Rather than "destroy" messages in the event a router in the circuit dies, "reroute" messages could be used. The reroute messages would make their way along the circuit, resulting in the first router sending another onion, such that the previous "endpoint", which may have data waiting to send on the route, is still identified as the endpoint. The identity of the "endpoint" router is still not given away. In a point to point route, if destroy messages can be traced, then the endpoint is identified. o This scheme may make sending dummy traffic better/easier. I'm throwing this idea on the table, not necessarily suggesting it's use. I'm not entirely sure what the consequences of it would be, I need to think about it more. The idea is somewhat analagous to nym.alias.net and similar nym servers, where the nym is the "endpoint", the remailer path to the nym is the route up to the "endpoint", and the reply block is the route after the "endpoint". I put "endpoint" in quotes because it is not the actual end of the route. Any thoughts welcome. Jeremey. - -- =-----------------------------------------------------------------------= Jeremey Barrett VeriWeb Internet Corp. Crypto, Ecash, Commerce Systems http://www.veriweb.com/ PGP Key fingerprint = 3B 42 1E D4 4B 17 0D 80 DC 59 6F 59 04 C3 83 64 =-----------------------------------------------------------------------= -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMySGYi/fy+vkqMxNAQFSGgQAja2167/+biJTY4AphGhTK4IunI7GJvmQ S7wJrxQD6z/W9kaDK105xLwkdx7WyHUol6NycU6CZlL5PeCFpcOr9q9CI1j6IUOE kX1RnO46o7lAaAi+sdKbesJoZbx1/8nWs9AoobKfk7+Kz26VUPWRo492BYYKRrf5 pz2TjasgBF8= =FRIa -----END PGP SIGNATURE----- From majordom Mon Mar 10 17:16:00 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA09228; Mon, 10 Mar 97 17:16:00 EST Received: from einstein.veriweb.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA09222; Mon, 10 Mar 97 17:15:53 EST Received: (from jeremey@localhost) by einstein.veriweb.com (8.8.5/8.6.9) id OAA10255; Mon, 10 Mar 1997 14:19:24 -0800 Message-Id: <332488E9.69573EE3@veriweb.com> Date: Mon, 10 Mar 1997 22:19:21 +0000 From: Jeremey Barrett Organization: VeriWeb Internet Corp. X-Mailer: Mozilla 3.01 (X11; U; Linux 2.0.11 i586) To: "Michael G. Reed" Cc: onions@itd.nrl.navy.mil Subject: Re: Onion routing: thoughts References: Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- Michael G. Reed wrote: > > I'm not sure I follow this completely (or what the motivation is for it > completely), can you elaborate some more on it? Thanks! > I don't think my last explanation was so clear either. Simply put: the return path from responder to initiator need not be the same as the path from initiator to responder. Probably the best way to do this is for the initiator to identify himself as the endpoint in the onion he sends around. Jeremey. - -- =-----------------------------------------------------------------------= Jeremey Barrett VeriWeb Internet Corp. Crypto, Ecash, Commerce Systems http://www.veriweb.com/ PGP Key fingerprint = 3B 42 1E D4 4B 17 0D 80 DC 59 6F 59 04 C3 83 64 =-----------------------------------------------------------------------= -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMySI6y/fy+vkqMxNAQEH7gP/ZfvoJ3jaASrIggKTAptVCYFU/r0fBU/K 6YmX0AqVjNWJdeiv+xmonnhNCVnjdSvdV1Rmi1rSz6syQ6O/Z/mWTerBV5/tMMzW tcz6YDQ+f6M7I5ZB2Ck2EyOubIeP9pguMPvsKu17dee/1V0zN9CkZqdAPkNGnsaa nB+Q+PNbY/4= =MgJ+ -----END PGP SIGNATURE----- From majordom Mon Mar 10 17:38:36 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA10100; Mon, 10 Mar 97 17:38:36 EST Received: from carnap.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA10094; Mon, 10 Mar 97 17:38:30 EST From: syverson@itd.nrl.navy.mil (Paul Syverson) Received: (from syverson@localhost) by carnap.itd.nrl.navy.mil (8.8.5/8.7.3) id RAA09625; Mon, 10 Mar 1997 17:38:28 -0500 (EST) Date: Mon, 10 Mar 1997 17:38:28 -0500 (EST) Message-Id: <199703102238.RAA09625@carnap.itd.nrl.navy.mil> To: jeremey@veriweb.com Subject: Re: Onion routing: thoughts Cc: onions@itd.nrl.navy.mil X-Sun-Charset: US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk > > I don't think my last explanation was so clear either. Simply put: the > return path from responder to initiator need not be the same as the > path from initiator to responder. Probably the best way to do this is > for the initiator to identify himself as the endpoint in the onion > he sends around. > That's one possibility. Another that is mentioned in some of our papers but won't appear on the first code release is a reply onion. Basically, this is an onion that the initiator can send to a particular responder (or broadcast or multicast it from the far end of an onion route, or even post anonymously). It identifies the first node to which it should be sent and, when used, creates an anonymous connection back to the initiator. Once the connection is established, it is as if the initiator had created it (in terms of how data is processed). The advantage here is that the initiator need not identify himself to give the responder a different route back to himself. And, he need not trust the responder to protect the anonymity of that route. We have mostly considered this from the perspective of allowing, e.g., replies to email, especially after the initial connection is gone. Or, allowing replies to anonymously posted requests. You raise an interesting idea that I don't recall previously discussing with my colleagues: viz using a reply onion in the context of the connection through which it was sent. aloha, Paul From majordom Mon Mar 10 19:07:55 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA12338; Mon, 10 Mar 97 19:07:55 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA12332; Mon, 10 Mar 97 19:07:48 EST Date: Mon, 10 Mar 1997 19:07:54 -0500 (EST) From: "Michael G. Reed" To: onions@itd.nrl.navy.mil Subject: Re: Onion routing: thoughts In-Reply-To: <199703102238.RAA09625@carnap.itd.nrl.navy.mil> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- On Mon, 10 Mar 1997, Paul Syverson wrote: |>> I don't think my last explanation was so clear either. Simply put: the |>> return path from responder to initiator need not be the same as the |>> path from initiator to responder. Probably the best way to do this is |>> for the initiator to identify himself as the endpoint in the onion |>> he sends around. |>> |>That's one possibility. Another that is mentioned in some of our papers |>but won't appear on the first code release is a reply onion. |>Basically, this is an onion that the initiator can send to a particular |>responder (or broadcast or multicast it from the far end of an onion |>route, or even post anonymously). It identifies the first node to which |>it should be sent and, when used, creates an anonymous connection back |>to the initiator. Once the connection is established, it is as if the |>initiator had created it (in terms of how data is processed). The |>advantage here is that the initiator need not identify himself to give |>the responder a different route back to himself. And, he need not |>trust the responder to protect the anonymity of that route. We have |>mostly considered this from the perspective of allowing, e.g., replies |>to email, especially after the initial connection is gone. Or, |>allowing replies to anonymously posted requests. You raise an |>interesting idea that I don't recall previously discussing with my |>colleagues: viz using a reply onion in the context of the connection |>through which it was sent. Actually, we did entertain the possibility of asymmetric routes at one time but discarded them for a couple of reasons: 1) In your earlier argument, you said something to the effect "each onion router decrypts his layer and the onion-router that gets plaintext knows he has to respond" -- PROBLEM. How do you know you have plaintext? Imbedded CRC or Hash in each DATA cell? This is a *LOT* of overhead, (cell data payload is 44 bytes -- to accommodate ATM, we would need to decrease this for every byte of hash stored...not the kind of tradeoff I really want to make right now), and potentially buys you nothing (there is the finite chance that a still encrypted cell could hash correctly and match causing an onion router to mis-think he's the recipient...small, but possible chance). This actually came up when we considered how to send in-band commands within DATA cells to control intermediate onion routers. The idea was shot down since we could figure out how to do it without adding another cell type (which we didn't want to do since it would expose information and be trackable by onion-routers along the route). 2) Crypto Overhead. Remember, we're think real-time, or near real-time applications here. We already spend a staggering amount of time on our RSA operations...this is still true even with hand coded assembly implementations for the V9 UltraSparc architecture and running it on dual processor Ultra2 machines...Five RSA encrypt operations is already a major burden, but ten would probably be unbearable...if this is only for padding/garbage data and is not done too frequently, it would be acceptable, but for every connection, I think it would kill us via the crypto overhead. Now if we move to hardware for the crypto, or if the pentium assembly version proves to be faster (we think it should be on a comparable MHz machine, but have yet to try to port this to Solaris x86), this may no longer be the case. 3) The longer the chain, the higher the probability that any one "thick pipe" going down will kill your connection. Plus, you start to run into the possibility of going through a think pipe multiple times REALLY killing overall system bandwidth by just bouncing back and forth. I'm not saying 5 hops is the magic number (really, I don't even remember how we came up with 5 in the current implementation, but it seemed like a good count at the time), but I would be *VERY* surprised if anyone suggested less than 5 hops, and many more doesn't seem to buy you that much. Remember, you only need to trust that ONE onion router out there in the world that you route through is behaving to have a secure connection (that and, of course, the first node being uncompromised). If you can't trust 40% on the onion routers in the world (really 20% if you don't include your first hop which you must trust with your life :-), then we have a larger problem to deal with. I'm not degrading the idea, it has some interesting applications that the system could probably use...these were just the reasons we shot it down before in our discussions...if I've missed anything (or there is a good counter argument), please clue me in :-) This is the kind of discussions we're hope to happen -- ones that open doors that we missed, or shed some light to you all as to why we made some of our design decisions. Thanks! - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMySiX08Qx019l0ClAQE2BAP/W+cTwtA1M7xmyzCi6Iytx59oPPInN2jb AH/oall/0NMoOFEivMG7lCroEu/flOmOH4WUx7mTdtVVsVrR+l9+uqHgngT9UB+z P2OKLSJxGFZeEbXOgVf3SNTwa8+8XO//yjp7fhNcpyNiI+RsA7cwcyEUVSEDjmCl az05sCe/MpU= =/9PH -----END PGP SIGNATURE----- From majordom Mon Mar 10 21:04:48 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA14634; Mon, 10 Mar 97 21:04:48 EST Received: from mail.eskimo.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA14628; Mon, 10 Mar 97 21:04:39 EST Received: from eskimo.com (eskimo.com [204.122.16.13]) by mail.eskimo.com (8.7.6/8.6.12) with SMTP id SAA05083 for ; Mon, 10 Mar 1997 18:04:27 -0800 (PST) Date: Mon, 10 Mar 1997 18:03:26 -0800 (PST) From: Wei Dai To: onions@itd.nrl.navy.mil Subject: Re: Onion routing: thoughts In-Reply-To: <199703101613.LAA01552@golem.itd.nrl.navy.mil> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk On Mon, 10 Mar 1997, David Goldschlag wrote: > Our position on padding is that constant utilization of an onion > routing network may not be necessary to complicate traffic analysis. > We still have to validate this hypothesis. If constant utilization is > necessary, the system will not scale well, will use network resources > inefficiently, and will not be widely adopted. I think it should be easy to show that constant utilization is necessary. It is the case for Chaum's Mix-Net (see http://www.eskimo.com/~weidai/traffic.txt), and Onion Routing seems closely related. I am convinced that anonymous routing cannot be relatively efficient. Indeed it may be worse than you expect - to defend against certain active attacks (that introduce errors into the network and analyze their propagation and correction) it may be necessary to propagate errors throughout the network so that local errors are made global. > Our goal is not pretty good onion routers. Our goal is a > communications infrastructure that is resistant to traffic analysis, > that can efficiently deliver traffic throughout the network, and that > will be widely deployed. Since you are so serious about getting it right the first time, I think a formal proof of security for your protocol would be extremely helpful. It could be done, perhaps, by following the approaches of David Chaum (for DC-Net) and Dan Simon (for Mix-Net). The proof for Onion Routing may be much more difficult, but it would be especially useful considering the large range of possible attacks and the ease of overlooking a protocol flaw. Whether or not an anonymous routing system will be widely deployed is not simply a technical issue. I think it also depends on political realities and economic incentives. I am glad (but also very curious) that the Navy should show so much interest in it. Certainly it improves the chances quite a bit. Wei Dai From majordom Tue Mar 11 02:43:55 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA20833; Tue, 11 Mar 97 02:43:55 EST Received: from freya.cs.umass.edu by itd.nrl.navy.mil (4.1/SMI-4.1) id AA20827; Tue, 11 Mar 97 02:43:45 EST Received: from opine.cs.umass.edu (opine.cs.umass.edu [128.119.41.246]) by freya.cs.umass.edu (8.7.6/8.6.9) with SMTP id CAA27693 for ; Tue, 11 Mar 1997 02:43:44 -0500 Message-Id: <33250D30.167E@cs.umass.edu> Date: Tue, 11 Mar 1997 02:43:44 -0500 From: Lewis McCarthy Organization: Theoretical Computer Science Group, UMass-Amherst, X-Mailer: Mozilla 3.01Gold (X11; U; OSF1 V3.2 alpha) Mime-Version: 1.0 To: Onion Routing Mailing List Subject: Re: Onion routing: thoughts References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk Wei Dai writes: > I am convinced that anonymous routing cannot be relatively efficient. > Indeed it may be worse than you expect - to defend against certain > active attacks (that introduce errors into the network and analyze > their propagation and correction) it may be necessary to propagate > errors throughout the network so that local errors are made global. In the general case, I suspect this is true. One general type of tactic of an active traffic analyst is to cause some parts of the anonymizing network to offer different service quality than others for a spell, and deduce information from the results. Any active attacker worth its salt can always degrade service quality somewhere in the anon-net. So any successful defensive attempt to balance the service quality across all the nodes must involve adjusting some nodes' service quality downwards to meet the current minimum level. In the worst case a node somewhere has crashed (i.e. suspended service for a long time period relative to the usual delivery interval), in which case it seems that the entire anon-net needs to grind to a halt temporarily. (Some out-of-band mechanism must communicate updated local service quality information reliably and quickly.) As the anon-net scales up, the mean-time-to-mandated-temporary-failure of the whole anon-net soars, assuming independent node failures. Experience with the Mixmaster network, at least, suggests that the mean-time-to-failure of a single node may be surprisingly short in practice. [...] > by following the approaches of David Chaum (for DC-Net) > and Dan Simon (for Mix-Net). [...] Can you give pointers to Dan Simon's work regarding MIXes? I didn't realize he had looked at this. -- Lewis http://www.cs.umass.edu/~lmccarth/lmkey.asc Onion recipes: http://www.plntationprod.com/Documents/recipe.html From majordom Tue Mar 11 16:47:26 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA27366; Tue, 11 Mar 97 16:47:26 EST Received: from einstein.veriweb.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA27358; Tue, 11 Mar 97 16:47:15 EST Received: (from jeremey@localhost) by einstein.veriweb.com (8.8.5/8.6.9) id NAA10929; Tue, 11 Mar 1997 13:50:49 -0800 Message-Id: <3325D3B6.10ED6A29@veriweb.com> Date: Tue, 11 Mar 1997 21:50:46 +0000 From: Jeremey Barrett Organization: VeriWeb Internet Corp. X-Mailer: Mozilla 3.01 (X11; U; Linux 2.0.11 i586) To: "Michael G. Reed" Cc: onions@itd.nrl.navy.mil Subject: [LONG] Re: Asymmetric routes References: Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- Michael G. Reed writes: > Actually, we did entertain the possibility of asymmetric routes at one > time but discarded them for a couple of reasons: > > 1) In your earlier argument, you said something to the effect "each > onion router decrypts his layer and the onion-router that gets > plaintext knows he has to respond" -- PROBLEM. How do you know you > have plaintext? For one, you know you are the responder. So on any given route, if you're the responder, then you must have plaintext. Alternatively, one bit in the data itself would do. > Imbedded CRC or Hash in each DATA cell? This is a > *LOT* of overhead, (cell data payload is 44 bytes -- to accommodate > ATM, we would need to decrease this for every byte of hash > stored...not the kind of tradeoff I really want to make right now), > and potentially buys you nothing (there is the finite chance that a > still encrypted cell could hash correctly and match causing an onion > router to mis-think he's the recipient...small, but possible chance). > This actually came up when we considered how to send in-band commands > within DATA cells to control intermediate onion routers. The idea was > shot down since we could figure out how to do it without adding > another cell type (which we didn't want to do since it would expose > information and be trackable by onion-routers along the route). If a small header is prepended to the data and then treated as data in crypto operations, no information should be leaked. Certainly a hash or CRC just to figure out if you have plaintext would be bad and wasteful. Perhaps I'm missing something though. Here's what I've got in my head at the moment. Please point out flaws. I'm not sure myself that this is useful. It may only be interesting. :-) o Initiator creates a circular route back to himself by sending a simple onion (no "reply" onion as such) which traces a route back to himself. No other router is aware of being the responder. o Data messages look like this: ----------------- | HDR | DATAMSG | ----------------- Where HDR is the "visible" header (routers use this to identify the message as "data". DATAMSG looks like this: ------------------ | DATAHDR | DATA | ------------------ Where DATAHDR is 1 byte or so. Basically just bits set or not set. One of the bits is the plaintext bit. Another would be the ignore bit. Maybe other stuff. o The initiator choose one of the routers on the circuit as the responder. The initiator applies crypto operations to the data message to send such that the chosen responder gets plaintext. Included with the first data message is a set of crypto operations for the chosen responder to apply to any data it sends along the route. (or perhaps that is the only data in the first data message). o Using 2 intermediate hops (not including initiator or responder), data messages look like this: -------------------------------------------- | HDR | DATAHDR | DATAHDR | DATAHDR | DATA | -------------------------------------------- Since the initiator has applied 3 crypto operations to the final DATAHDR and DATA, neither intermediate router knows who has the plaintext. And the initiator has applied 2 crypto operations to the second DATAHDR, so the first intermediate router doesn't know what the second has either. Both the first and second DATAHDR fields are 0 (or at least the plaintext bit and ignore bits are not set). The third DATAHDR has the plaintext bit set. Again, this is just an onion with layers being peeled off (but no RSA). Padding could be added to make it difficult to deduce the number of hops. o When the responder gets the data message, it applies the normal crypto operation and obtains plaintext. The responder immediately passes the same data message along the rest of the route by applying the "reply-block" crypto operations in succession, and creating the necessary DATAHDR fields (which involves applying the correct number of crypto operations to them as well). In the DATAHDR which will reach the initiator, the plaintext _and_ ignore bits are set. The only knowledge the responder gains is the length of the return route. o The initiator gets the same data message it sent to the responder, but now with both plaintext and ignore bits set. It discards and does not forward the message. o When the responder has data ready to send to the initiator, it constructs DATAHDR's again, but with the plaintext bit and _not_ the ignore bit set (in the last DATAHDR). o Much the same process repeats, but the responder is now acting like the initiator. The initiator gets the response data, and gives it to the application or whoever. It also sets the ignore bit and sends the data back to the responder, who discards it. In this way, all messages always complete the circuit, making the responder difficult to identify. In fact, it is difficult to distinguish a response from a request (I realize these terms are more applicable to HTTP-like protocols than things like telnet). The same route can be reused, even with different responders. > > 2) Crypto Overhead. Remember, we're think real-time, or near > real-time applications here. We already spend a staggering amount of > time on our RSA operations...this is still true even with hand coded > assembly implementations for the V9 UltraSparc architecture and > running it on dual processor Ultra2 machines...Five RSA encrypt > operations is already a major burden, but ten would probably be > unbearable...if this is only for padding/garbage data and is not done > too frequently, it would be acceptable, but for every connection, I > think it would kill us via the crypto overhead. Now if we move to > hardware for the crypto, or if the pentium assembly version proves to > be faster (we think it should be on a comparable MHz machine, but have > yet to try to port this to Solaris x86), this may no longer be the > case. Yes, double the RSA operations is a problem. If routes can be reused significantly, this is less of a problem. > > 3) The longer the chain, the higher the probability that any one > "thick pipe" going down will kill your connection. Plus, you start to > run into the possibility of going through a think pipe multiple times > REALLY killing overall system bandwidth by just bouncing back and > forth. I'm not saying 5 hops is the magic number (really, I don't > even remember how we came up with 5 in the current implementation, but > it seemed like a good count at the time), but I would be *VERY* > surprised if anyone suggested less than 5 hops, and many more doesn't > seem to buy you that much. Remember, you only need to trust that ONE > onion router out there in the world that you route through is behaving > to have a secure connection (that and, of course, the first node being > uncompromised). If you can't trust 40% on the onion routers in the > world (really 20% if you don't include your first hop which you must > trust with your life :-), then we have a larger problem to deal with. > The longer the route, the more potential it will fail. That is always going to be the case. Breaks in the chain can be rerouted around so that no data is lost (if the mechanisms are in place. i.e. the initiator would need to send a connection identifier as part of the data to the responder. Then the same identifier could be used to replace the route with another). For remailers, I rarely use more than 3 hops. I'm not sure what the magic number is for onion routers, but 5 seems reasonable. Jeremey. - -- =-----------------------------------------------------------------------= Jeremey Barrett VeriWeb Internet Corp. Crypto, Ecash, Commerce Systems http://www.veriweb.com/ PGP Key fingerprint = 3B 42 1E D4 4B 17 0D 80 DC 59 6F 59 04 C3 83 64 =-----------------------------------------------------------------------= -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyXTuC/fy+vkqMxNAQHM3QQAhL80OEO0oSGLMcjRMBuiOfRYxefmxZ9f 9LoE9gC7GyQkaE9RL5ikmPpZjJgR8+3ydHZGu9skfSFBltL2rDLk6eK0iv9p8IGB 97oO4JuX/jMAa7epY/wfWl0MjfUoqcIK4hUFEaGCYcTiZiBvlm+P7l+i8qAYwgst v3N2vUvU2G8= =ORQz -----END PGP SIGNATURE----- From majordom Tue Mar 11 19:02:25 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA02225; Tue, 11 Mar 97 19:02:25 EST Received: from freya.cs.umass.edu by itd.nrl.navy.mil (4.1/SMI-4.1) id AA02219; Tue, 11 Mar 97 19:02:18 EST Received: from opine.cs.umass.edu (opine.cs.umass.edu [128.119.41.246]) by freya.cs.umass.edu (8.7.6/8.6.9) with SMTP id TAA24274 for ; Tue, 11 Mar 1997 19:02:17 -0500 Message-Id: <3325F288.31DF@cs.umass.edu> Date: Tue, 11 Mar 1997 19:02:16 -0500 From: Lewis McCarthy Organization: Theoretical Computer Science Group, UMass-Amherst, X-Mailer: Mozilla 3.01Gold (X11; U; OSF1 V3.2 alpha) Mime-Version: 1.0 To: Onion Routing Mailing List Subject: Simon et al.'s work on anonymous networks Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk Answering my own question, I noticed Dan Simon's Crypto `96 paper "Anonymous Communication and Anonymous Cash", which concentrates on the latter topic. It includes a reference to a STOC `93 paper by Rackoff & Simon: "Cryptographic Defense Against Traffic Analysis". -- Lewis http://www.cs.umass.edu/~lmccarth/lmkey.asc "Overwhelmed by 21 documents? Let LiveTopics guide you!" --AltaVista From majordom Wed Mar 12 04:40:26 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA11927; Wed, 12 Mar 97 04:40:26 EST Received: from ccnet4.ccnet.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA11920; Wed, 12 Mar 97 04:40:17 EST Received: from sfbayarea.ccnet.com (h108-14-139.ccnet.com [199.108.14.139]) by ccnet4.ccnet.com (8.7.1/8.6.12) with SMTP id BAA28696 for ; Wed, 12 Mar 1997 01:41:26 -0800 (PST) Message-Id: <3.0.32.19970312014106.007053dc@netcom9.netcom.com> X-Sender: shamrock@netcom9.netcom.com X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Wed, 12 Mar 1997 01:41:28 -0800 To: onions@itd.nrl.navy.mil From: Lucky Green Subject: Re: discussion points Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk At 04:55 PM 3/10/97 -0500, David Goldschlag wrote: > >Hi, > >We are planning to release code this week for testing. Testsers have >to agree not to redistribute code. Soon we hope to put the code on a >site that will re-distribute within the US. I am a US citizen living in the US and would appreciate any source you have. >It would be useful to start a discussion about what we are trying to >hide and what may do that hiding. I'm looking for communication >models, attack models, carefully stated requirements, and justified >solutions. Seems I am going to have to write that paper after all... >For example, precisely what do we by "assume only a single >uncompromised onion router?" Assume the adversary monitors all in and outgoing connections. Further assume, the adversary operates all but one core onion router. >As another example, if two sites connect (encrypted) to remote onion >routers at roughly the same time, it is more likely that they are >communicating than if they didn't connect at roughly the same time. >This is hard to protect against. That's where constant bandwidth _will_ make the difference. >Do we need constant utilization or is smoothing sufficient? Smoothing is insufficient. Traffic analysis is a statistical attack. With "smoothing" you just force the attacker to obtain more data. >Do we want to add noice to individual connections? Absolutely. >Do we want terminal onion router to terminal onion router padding >(noise connections)? That might be a good idea. But don't look at it as noise. If the circuits will be constantly saturated, as you predict, padding will not be needed. >Do we want padding between neighboring onion routers? Sure. > >I'm looking to leverage off the expertise in this list, so we can >build strong hiding around the onion routing infrastructure. I don't know anybody that has longer and deeper thought about these issues than the subscribers to this list. Onion routing is a good idea. It just needs to take some other research into account. -- Lucky Green PGP encrypted mail preferred "I do believe that where there is a choice only between cowardice and violence, I would advise violence." Mahatma Gandhi From majordom Wed Mar 12 07:45:38 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA15792; Wed, 12 Mar 97 07:45:38 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA15786; Wed, 12 Mar 97 07:45:31 EST Date: Wed, 12 Mar 1997 07:45:40 -0500 (EST) From: "Michael G. Reed" To: onions@itd.nrl.navy.mil Subject: Re: discussion points In-Reply-To: <3.0.32.19970312014106.007053dc@netcom9.netcom.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- On Wed, 12 Mar 1997, Lucky Green wrote: |>>For example, precisely what do we by "assume only a single |>>uncompromised onion router?" |> |>Assume the adversary monitors all in and outgoing connections. Further |>assume, the adversary operates all but one core onion router. If this is the assumption, then everything is a moot point. If some adversary operates all but one core onion router he KNOWS with 100% certainty where the connection originated though. Then it is only a matter of time and watching (how carefully it can be watched may vary) that onion router or doing other statistical attacks on the (now) known plaintext coming out of all of the nodes before he knows everything. This is ludicrous. If you really can't trust some percent of the onion routers out there in the world (even half), then the whole effort is a waste in the first place. By "trust" I don't mean completely trust in that you would use them as your first hop, but trust at least to the level that they are not actively attacking you and are behaving relatively well. You only need one completely honest node farther down stream to make the link passively untraceable (and depending on the implementation one may be sufficient to make it actively untraceable, but I'm not positive about that). |>>As another example, if two sites connect (encrypted) to remote onion |>>routers at roughly the same time, it is more likely that they are |>>communicating than if they didn't connect at roughly the same time. |>>This is hard to protect against. |> |>That's where constant bandwidth _will_ make the difference. No, constant bandwidth makes absolutely NO difference in this situation. This is an attack which looks at coincidences of NEW connections going IN TO and OUT OF the network...not data flow within the network, but timing on new connections. Bandwidth means nothing here. |>>Do we need constant utilization or is smoothing sufficient? |> |>Smoothing is insufficient. Traffic analysis is a statistical attack. With |>"smoothing" you just force the attacker to obtain more data. See my next message regarding bandwidth concerns... |>>Do we want to add noice to individual connections? |> |>Absolutely. This can be done a number of ways including: 1) letting the higher level protocol do it, 2) Inserting it into DATA cells somehow (possibly by having cells with illegal lengths...only the last router would be able to determine this, which might, in turn, give you some more information to attack the connection), or 3) Adding a new cell type (BAD idea since it introduces markers that can be tracked independent of the other cell types). To somewhat quote Monte Python, "#3 is right-out". Furthermore, I really have to think some more about #2 before I would consider adding it. #1 is by far the best, but we are trying to coexist with UNMODIFIED internet applications, so this is difficult. |>>Do we want padding between neighboring onion routers? |> |>Sure. Inter-node padding does not solve the problem of "bad" nodes. It will help confound external observers, but a bad node will always know what is padding on node to node padding. End to end padding could be hidden from all but the last node, and protocol padding could be hidden from all nodes. |>I don't know anybody that has longer and deeper thought about these issues |>than the subscribers to this list. Onion routing is a good idea. It just |>needs to take some other research into account. Research or practical experience? We are researchers. That is our job description. That is what we get paid to do. There are more PhD's walking around this base than some college campuses. We publish constantly in academic circles, we attend conferences, we participate in the larger academic world. Please do not assume that since we work for the government that we are uninformed, undereducated, GAK-loving idiots. What we lack is the practical experience in this area -- most of what we do is theory, theory, theory...very little applied (at least in the computer security area). Thus the prototype where we've already learned a great deal about where the theoretical models break down in the real world. Thus all the discussions with people running other MIX variants in the world (both in research labs and actually out there on the Internet). Thus the need for a wider participation and the push for a general RFC that can be accepted by the whole Internet community. Please don't view this as an "us vs. them" environment...we want the same level (and possibly even higher level) of security that you want out of this system...help us do that. Sorry for the venting, but I've received one to many emails in the last two weeks from very uninformed people that have just rubbed me the wrong way. - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyaleE8Qx019l0ClAQFsEwP9EklbraP0303MgkTFVHu8mxvy0Vlh3spY Cw6MCrr0ntwQyGwYucrUuLXtl/3t3rTnyESdaYNxFzHdCiDZVJIMAizwyM8gN6ue 9rkW0uL4iIxZxSWqWFeD2kn1NjnrJC6dSZNQvuTTglyz1MIJd+Kbzb/ebbR3waBm 2b15LsJItzo= =Lz6C -----END PGP SIGNATURE----- From majordom Wed Mar 12 08:59:35 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA19068; Wed, 12 Mar 97 08:59:35 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA19060; Wed, 12 Mar 97 08:59:28 EST Date: Wed, 12 Mar 1997 08:59:37 -0500 (EST) From: "Michael G. Reed" To: Onion Routing List Subject: Bandwidth/Padding/etc... Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- All, There have been a number of discussions about padding and bandwidth usage. I just want to point out some technical arguments that we need to consider when designing how the system will pad and to what extent padding can be achieved. First is that we are running on top of a reliable delivery mechanism of which we have little, if no, control -- namely TCP/IP. We do not have direct access to the outbound wire like a real router does, so saying things like "we will use or pad to 100% bandwidth" is really meaningless. Padding "to full network or link capacity" only makes sense in terms of actual control of the wire. Since we cannot achieve real control of the wire in our implementation, we need to look at a different definition. One possible solution is to place onion routers on dedicated links to the Internet. Not really likely, and not really a viable option. Another solution is to predefine and reserve some amount of guaranteed capacity between nodes. While this is possible with ATM and will be possible with IPv6 in general, it is not possible on the current Internet. So again, we need to weaken our definition of what capacity and usable bandwidth are. If we do "data smoothing", we can fluctuate bandwidth with available capacity of the Internet. I'm not talking real short term smoothing, but prolonged smoothing where we change individual link utilization over time with regard to how much traffic we are sending, and how much traffic exists on the physical links outside of our system. I think data smoothing offers a more robust system than just enforcing a hard capacity since that hard capacity would have to be based on the slowest, most unreliable link in the system. Remember, we are running on top of TCP/IP...there will be packet loss, packet rerouting, packet retransmission. We need the ability to back-off nodes, or else we run the risk of swamping network links in our effort to attain perfect utilization of whatever capacity we define. What it all really comes down to is what our threat model is, and what we can do on the existing Internet. I think it is unreasonable to wait for IPv6, or to say we will only deploy on ATM clouds. Furthermore, I think it is unreasonable to enforce artifically low link capacities because of one bad link somewhere. I urge people to comment on all of this. - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMya2zU8Qx019l0ClAQE/eAP/YsHo3ciKtimwgVvkDRKNlHHQJw3v3JNG Gy6v8chwYkFkLfi2iUKqceC3lqd4GyBuvpLULTSMUEP/tvoNQVezTd8SUkMQeHlA TOp+Jr7g+EKlSyS+I6UzJK2nyvr7i3Tq/+9PDngCbcar82jJJX8fioQ8zUQJi825 I8nzndORkC8= =GFSM -----END PGP SIGNATURE----- From majordom Wed Mar 12 14:58:29 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA09150; Wed, 12 Mar 97 14:58:29 EST Received: from callisto.hip.berkeley.edu by itd.nrl.navy.mil (4.1/SMI-4.1) id AA09127; Wed, 12 Mar 97 14:57:55 EST Received: (from raph@localhost) by callisto.hip.berkeley.edu (8.6.12/8.6.12) id LAA06135; Wed, 12 Mar 1997 11:58:48 -0800 Message-Id: <33270AF3.26B6B0D@acm.org> Date: Wed, 12 Mar 1997 11:58:43 -0800 From: Raph Levien X-Mailer: Mozilla 3.0 (X11; U; Linux 1.2.13 i586) Mime-Version: 1.0 To: Onion Routing List Cc: eric@remailer.net Subject: Vulnerabilities of anonymous routing Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk I wanted to put in my two cents on some of the topics here, even though I'm a bit swamped right now. I'll start with a few comments about what it means to successfully analyze anonymized traffic, outline a few attacks that seem fruitful, add a few words about "constant bandwidth" and (for those who have the patience) end with an invitation. It seems to me that the best way to model traffic analysis is _distinguishability_. Is it possible to distinguish, from observable traffic patterns, the case when Alice is browsing Bob's homepage from the case when Alice is not? More formally, what is the probability that an adversary would make the correct guess. If that's significantly better than chance, then traffic analysis is in some sense feasible. Of course, the powers of the adversary depend on what we're trying to model (passively observing some traffic, observing all traffic, actively inserting traffic, operating compromised onion routers, etc.). This may seem like an obvious definition of traffic analysis, but it gets us closer to the way cryptographic primitives are defined (PRNGs come to mind), and has some implications for how to prove resistance to traffic analysis. More on this later when I touch on constant bandwidth. Now for some attacks. The first attack assumes passive observing of traffic volume at all endpoints. No assumptions are made about the center portion. Thus, the central portion can be implemented as onion routing, DC-nets, or whatever, and is modelled simply as a probability distribution of time delays. For anonymous Web browsing, performance dictates that the mean is fairly small (on the order of a few seconds), and the random nature of onion routing mixing suggests that a Gaussian distribution will be fairly accurate. Given these assumptions, traffic analysis reduces to a signal processing problem - separating the signal from the noise. The signal is right there for all to see (a bump in traffic at Alice, followed by a bump in traffic a few seconds later at Bob), but may possibly be obscured by the noise. A first cut at the problem is simply to calculate a correlation matrix of all inputs to the network with all outputs. To improve the accuracy of the correlation, the input events are convolved (in time) with the model of the anonymizing network. This convolution also makes it easy to deal with discrete event traffic flows as opposed to continuous flows. The resulting correlation matrix will contain the desired signal, but will also contain quite a bit of noise. In particular, correlations between patterns of browsing will cause spurious positive signals in the matrix (more concretely, if Alice browses the Dilbert page every morning when she gets to work, and Bob browses CNN, then the correlation matrix will show positive numbers for Alice/CNN and Bob/Dilbert). I haven't gone into the math, but I think it should be possible to remove much of this cross-correlation noise. Most crudely, the cross-correlation noise will be concentrated in low frequencies, so it should be possible to simply filter it out. On the other hand, we're assuming that all traffic volumes are known, so it should be possible to estimate the cross-correlations accurately and correct for them. Eric Hughes has suggested entropy optimization techniques (of roughly the same kind as used to reconstruct images in computed tomography), and it seems likely that this approach would be fruitful. As a research topic, the next obvious place to look is the information content in Web browsing patterns. The low frequency components will be dominated by noise, and the high frequency components (i.e. finer than a few seconds) will be filtered out by the mixing process. I believe that there is still plenty of information content in between, but ultimately this has to be determined empirically. Adding active attacks can help. The present-day Web makes these quite easy. For example, Java applets which refresh information periodically are becoming popular. It would be easy for such an applet to modulate the timing so as to maximize the information content and minimize cross-correlation with other traffic patterns. No doubt the design of CDMA phones can provide design inspiration. One characteristic of this attack is that integration over longer time periods helps. In general, the signal will scale linearly with the number of samples, while the noise will only scale as the square root. Thus, by doing a million samples, you gain a factor of a thousand in signal to noise ratio. Just as with Paul Kocher's timing attacks, merely adding noise to the signal (i.e. random delays) does not protect against the attack. Thanks to Eric Hughes for many of the ideas presented here. The second attack uses reliability information. This attack is devastating against anonymous servers, much more so than anonymous browsers. However, in the Web today, the distinction between servers and browsers is not airtight. I'll describe the attack for servers first and then touch on how to make browsers act as servers. The assumption for this attack against servers is that the adversary has access to reliability information for both the physical nodes and the pseudonymous servers. This assumption is quite reasonable. Reliability information for the pseudonymous servers must be public information, because either you can access the page or you can't. In addition, onion routing forces the reliability information of physical nodes to be public information, otherwise it would be impossible to build onions that had a high probability of working. (experience with the remailer list highlights this fact - even with fairly decent statistics gathering, and with all information fully public, the reliability of chains of 5 remailers is usually no higher than 90-95% - see http://kiwi.cs.berkeley.edu/remailer-chains for the current stats) Again, traffic analysis is performed by correlating the reliability info for the physical and pseudonymous servers. It's possible to do even better than plain correlation, though, because if the physical server is down, the corresponding pseudonymous server _must_ also be down. Thus, when a physical server goes down, the list of pseudonymous servers that are still up can be excluded from the possibile pseudonymous server associated with that physical server. If this exclusion process narrows down the list of possible servers to one, then that's much stronger evidence than merely a high correlation. This particular type of analysis makes it particularly difficult to overwhelm the signal with noise. If the servers are quite unreliable, then there's lots of signal to analyze. On the other hand, by making the servers very reliable, you also eliminate the noise. If only one server is down at any given time, it becomes trivial to analyze them. Thus, I consider this attack to be among the most fruitful when it is feasible. Now, how to generalize this attack to browsing? One easy way I can think of is to apply the same Java applet technique, only this time geared to detecting sudden disruptions. For example, the applet could cause the browser to reload a small HTML file periodically, functioning as a watchdog. To distinguish server failures from people getting bored with the page they're watching, the applet sends a message to the server when it terminates normally. Thus, whenever a physical server goes down, the applet's server looks for the watchdog sequences to suddenly cease. If these are fairly rare events, and if there are many simultaneous connections, it would count as strong evidence. I can envision somewhat less effective passive attacks too, for example based on Markov models of typical browsing behavior. Again, if typical browsing behavior can be distinguished from sudden disruptions of service, that's all the leverage needed for traffic analysis. Many of these ideas in this second attack are due to Lewis McCarthy. Now for some discussion of constant bandwidth. As I see it, the main idea of constant bandwidth is to make it impossible, by definition, to distinguish between different patterns of traffic. To extend the random number analogy, they are the analog of truly random numbers (i.e. a flat distribution of probabilities) as opposed to pseudorandom numbers (i.e. a highly uneven distribution, but hopefully one which cannot be distinguished from a flat one). The analogy to Paul Kocher's timing attacks is again instructive. The distinguishability criterion is helpful, I believe. As long as the signal is made indistinguishable on some level (for example, calling write() on the socket at a constant rate, with a constant number of bytes), it doesn't matter if there are variations on other levels (for example, IP variability). Thus, I think that the discussion of needing IPv6 or ATM is moot. To address some of the points that Michael made about "us vs. them," I'm very happy to see the NRL doing this research. I have no doubt that you guys have what it takes to pull this project off. I'm also happy to see that your goal is to resist serious traffic analysis (as opposed to hiding browsing patterns from your little sister). We cypherpunks have been thinking about these problems for quite some time, as they are central to our agenda, but too often we sit around and talk about them rather than actually building things. However, it seems clear that the problem of building an anonymous network strongly resistant to traffic analysis is _hard,_ quite a bit harder than your Oakland paper draft seems to credit. If you're going to make the claim that the system you build is resistant in this way, then you'll also have to show how it holds up against very best attacks that can be mounted, not just the straightforward marker tracking attack as described in section 6 of the Oakland draft. As promised, finally an invitation. I think it would be great if the onion routing people could get together with a group of cypherpunks who have put some thought into this problem. Since the onion routing people will be in the Bay Area for Oakland, and since most of the relevant cypherpunks live here (with Lewis McCarthy being the most notable exception), I'd like to organize a dinner at my apartment sometime during the Oakland conference. I live about six blocks from the Claremont hotel where the conference is held, and I'm willing to try some onion recipes. I think this would really give us the chance to talk seriously about network anonymity, and get to know each other better. I've got to get back to writing my paper now. I probably won't have time in the next couple of weeks to respond to followups, but hope to be able to do so after I get back from out of town. Raph P.S. One correction to the Oakland draft. The discussion of anonymous reply mail in section 9 seems to me to be inaccurate. The nymservers implement an "encrypted reply block" which seems to me to be fully analogous to reply onions. In this model, the nymserver functions as the "client proxy", mapping human-readable e-mail addresses to encrypted reply blocks, while the other remailers in the chain simply forward and encrypt the mail statelessly. Under the assumption that passing through a remailer really hides the connection (i.e. discounting the traffic correlation attacks outlined above), it suffices that a single remailer be uncompromised to protect the traffic. From majordom Wed Mar 12 15:46:15 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA11284; Wed, 12 Mar 97 15:46:15 EST Received: from carnap.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA11278; Wed, 12 Mar 97 15:46:09 EST From: syverson@itd.nrl.navy.mil (Paul Syverson) Received: (from syverson@localhost) by carnap.itd.nrl.navy.mil (8.8.5/8.7.3) id PAA10646 for onions@itd.nrl.navy.mil; Wed, 12 Mar 1997 15:46:05 -0500 (EST) Date: Wed, 12 Mar 1997 15:46:05 -0500 (EST) Message-Id: <199703122046.PAA10646@carnap.itd.nrl.navy.mil> To: onions@itd.nrl.navy.mil Subject: A quick observation on terminology X-Sun-Charset: US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk I've noticed that many postings treat `traffic analysis' as including (at least) confirming that Alice and Bob are communicating given that one specifically targets them as potential communicants. If this is standard terminology, so be it. If it's not set in stone, however, I think this should be called something like traffic pattern confirmation. Analysis is determining who is talking to whom (or who is Alice talking to, or who is talking to Bob). Compare `cryptanalysis', which usually does not include confirming correct guesses of keys or discovering keys by exhaustively rejecting bad guesses. Traffic analysis (sensu stricto) and traffic pattern confirmation may both be important to guard against, but they are distinct threats. aloha, Paul P.S. Email may be the most efficient mechanism ever devised for creating offense where none was intended. If we start telling each other how smart (or dumb) we are, things will probably quickly degenerate to... well, to the usual level of email discussions. Sincerely, Paul Syverson Floral Park-Bellerose (Elementary) School Class of 1970 From majordom Wed Mar 12 17:20:10 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA16071; Wed, 12 Mar 97 17:20:10 EST Received: from ccnet4.ccnet.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA16037; Wed, 12 Mar 97 17:19:56 EST Received: from sfbayarea.ccnet.com (h108-14-159.ccnet.com [199.108.14.159]) by ccnet4.ccnet.com (8.7.1/8.6.12) with SMTP id OAA07020 for ; Wed, 12 Mar 1997 14:21:04 -0800 (PST) Message-Id: <3.0.32.19970312132106.006e1adc@netcom9.netcom.com> X-Sender: shamrock@netcom9.netcom.com X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Wed, 12 Mar 1997 14:21:03 -0800 To: Onion Routing List From: Lucky Green Subject: Re: Bandwidth/Padding/etc... Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk At 08:59 AM 3/12/97 -0500, Michael G. Reed wrote: > If we do "data smoothing", we can fluctuate bandwidth with >available capacity of the Internet. I'm not talking real short term >smoothing, but prolonged smoothing where we change individual link >utilization over time with regard to how much traffic we are sending, >and how much traffic exists on the physical links outside of our >system. I think data smoothing offers a more robust system than just >enforcing a hard capacity since that hard capacity would have to be >based on the slowest, most unreliable link in the system. The idea of "smoothing" has merit. When it was first mentioned, I thought you were talking about a high frequency smoothing. But if you mean by smoothing a low frequency smoothing, say adding and removing available bandwidth along well established daily usage patterns, then smoothing may not provide the attacker with more information than a constant bandwidth pipe would. > What it all really comes down to is what our threat model is, >and what we can do on the existing Internet. I think it is >unreasonable to wait for IPv6, or to say we will only deploy on ATM >clouds. Furthermore, I think it is unreasonable to enforce >artifically low link capacities because of one bad link somewhere. I >urge people to comment on all of this. Agreed. It all comes down to the treat model. I assume a very resourceful adversary that can monitor the entire network, or at least large parts of it. The adversary in my threat model also can conduct active attacks. What is your threat model? As to the link capacity, I believe the core routers should be on high capacity links that can be assumed to be mostly stable. The link between a core router and the user's proxy must of course be assumed to be unstable. -- Lucky Green PGP encrypted mail preferred "I do believe that where there is a choice only between cowardice and violence, I would advise violence." Mahatma Gandhi From majordom Wed Mar 12 17:20:14 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA16082; Wed, 12 Mar 97 17:20:14 EST Received: from ccnet4.ccnet.com by itd.nrl.navy.mil (4.1/SMI-4.1) id AA16043; Wed, 12 Mar 97 17:19:59 EST Received: from sfbayarea.ccnet.com (h108-14-159.ccnet.com [199.108.14.159]) by ccnet4.ccnet.com (8.7.1/8.6.12) with SMTP id OAA07025; Wed, 12 Mar 1997 14:21:06 -0800 (PST) Message-Id: <3.0.32.19970312142049.00710208@netcom9.netcom.com> X-Sender: shamrock@netcom9.netcom.com X-Mailer: Windows Eudora Pro Version 3.0 (32) Date: Wed, 12 Mar 1997 14:21:04 -0800 To: "Michael G. Reed" , onions@itd.nrl.navy.mil From: Lucky Green Subject: Re: discussion points Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk At 07:45 AM 3/12/97 -0500, Michael G. Reed wrote: >If this is the assumption, then everything is a moot point. If some >adversary operates all but one core onion router he KNOWS with 100% >certainty where the connection originated though. Not necessarily. Assume for a moment the uncompromised router is the node a user's proxy connects into. The attacker knows all incoming plaintext data for all the users who connect to the uncompromised node. Depending on how many users connect to that node, and how many of them keep the connection up most of the time, the attacker may or may not be able to determine the ultimate browser. >|>>As another example, if two sites connect (encrypted) to remote onion >|>>routers at roughly the same time, it is more likely that they are >|>>communicating than if they didn't connect at roughly the same time. >|>>This is hard to protect against. >|> >|>That's where constant bandwidth _will_ make the difference. > >No, constant bandwidth makes absolutely NO difference in this >situation. This is an attack which looks at coincidences of NEW >connections going IN TO and OUT OF the network...not data flow within >the network, but timing on new connections. Bandwidth means nothing >here. Upon re-reading your original post, I agree that constant bandwidth amongst the routers will not help against a passive attacker in this case. What will help, however, is constant bandwidth between the user's proxy and the first core router. If the user makes a connection to an onion router in the morning and leaves it up until the evening, the passive attacker learns nothing. Other than your work hours, that is :-) [about noise] >This can be done a number of ways including: 1) letting the higher >level protocol do it, 2) Inserting it into DATA cells somehow >(possibly by having cells with illegal lengths...only the last router >would be able to determine this, which might, in turn, give you some >more information to attack the connection), or 3) Adding a new cell >type (BAD idea since it introduces markers that can be tracked >independent of the other cell types). To somewhat quote Monte Python, >"#3 is right-out". Furthermore, I really have to think some more >about #2 before I would consider adding it. #1 is by far the best, >but we are trying to coexist with UNMODIFIED internet applications, so >this is difficult. Of course you want to interoperate with unmodified Internet applications. That's why you should use a client side proxy. What happens at the other side of the proxy is yours to choose. It could be as simple as a steam cipher into which the proxy xor's the data. [Client side proxies are the future. My thanks go to Jim McCoy for convincing me of that. In fact, the average user's machine will probably run multiple chained proxies for the same protocol: An onion routing proxy to access the network, followed by SafePassage to increase SSL strength from 40 to 128 bit, followed by a decrypting proxy for webpages that are stored encrypted, followed by CookieCutter, to get rid of unwanted cookies, etc. That's four chained proxies for HTTP alone. [As a side bar, proxies@communities.com is the list where we are currently discussing specs for a "universal" client side proxy that allows for dynamic loading of proxy modules.] >|>>Do we want padding between neighboring onion routers? >|> >|>Sure. > >Inter-node padding does not solve the problem of "bad" nodes. Agreed. >It will >help confound external observers, but a bad node will always know what >is padding on node to node padding. End to end padding could be >hidden from all but the last node, It might help to think of the "last node" as something that resides on the user's machine. >and protocol padding could be >hidden from all nodes. Wouldn't that require a proxy on the accessed website? >|>I don't know anybody that has longer and deeper thought about these issues >|>than the subscribers to this list. Onion routing is a good idea. It just >|>needs to take some other research into account. > >Research or practical experience? We are researchers. That is our >job description. That is what we get paid to do. There are more >PhD's walking around this base than some college campuses. We publish >constantly in academic circles, we attend conferences, we participate >in the larger academic world. Please do not assume that since we work >for the government that we are uninformed, undereducated, GAK-loving >idiots. The mere fact that you are working on Onion Routers proves that you have a clue and are none of the things that you seem I am assuming. I assure you, I am not assuming any of the traits you mention. > What we lack is the practical experience in this area -- most >of what we do is theory, theory, theory...very little applied (at >least in the computer security area). Thus the prototype where we've >already learned a great deal about where the theoretical models break >down in the real world. Thus all the discussions with people running >other MIX variants in the world (both in research labs and actually >out there on the Internet). Thus the need for a wider participation >and the push for a general RFC that can be accepted by the whole >Internet community. Please don't view this as an "us vs. them" >environment...we want the same level (and possibly even higher level) >of security that you want out of this system...help us do that. Which is exactly the reason why I am talking with you, published your URL to the relevant mailing lists, and convinced people I knew to be knowledgable about this topic to subscribe to this list. This is not an "us vs. them" for any person on the list that I know. And I probably know most, if not all subscribers (other than the one's from NRL, whom I first met at FC'97). Most of the non-NRL subscribers on this list are, or have been, subscribers to the Cypherpunks mailing list. The overriding goal was to secure the communications infrastructure and achieve privacy by preventing the adversary from gaining information about an individual or corporation by being able to read or traffic analyze the communications. Classical COMSEC. The old Cypherpunks and the US Navy are facing the same problem and are therefore looking at similar solutions. You need broad public use of the system to provide you with cover traffic and we want to see such a system deployed to provide the citizens with privacy. We are allies, not enemies. It is in this spirit of cooperation that we are pointing out issues with your design that some of us believe require fixing before the system can achieve our common goal. We all want to see the best design possible to be deployed, because we all know that no other design will ever achieve the broad penetration that we seek. Let's all work together on making that design a reality. Thanks, -- Lucky Green PGP encrypted mail preferred "I do believe that where there is a choice only between cowardice and violence, I would advise violence." Mahatma Gandhi From majordom Thu Mar 13 08:02:54 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA06969; Thu, 13 Mar 97 08:02:54 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA06959; Thu, 13 Mar 97 08:02:42 EST Date: Thu, 13 Mar 1997 08:02:52 -0500 (EST) From: "Michael G. Reed" To: Onion Routing List Subject: Re: [LONG] Re: Asymmetric routes In-Reply-To: <33271F49.595B884E@veriweb.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- On Wed, 12 Mar 1997, Jeremey Barrett wrote: |>Another possible implementation would be for the initiator to supply |>"prebuilt" DATAHDRs to the responder. Then the initiator would only |>need to supply one crytpo operation/key to the responder. The responder |>can still tell the length of the return route from the size of the |>DATAHDRs it gets, but does not have the keys to encrypt. Actually, |>the initiator could fool the responder and append several bogus DATAHDRs |>if necessary, eliminating even that possibility. The overhead is |>getting ugly here, given 44-byte messages. This looks like it would work, and as long as you didn't need to do it too frequently the overhead may be acceptible. Given the level of complication we've just described in the last few messages, I'm reluctant to jump to impliment this though...I'm not entirely sure how much power we gain from this change or how much better this defeats our threat model. Looks like it gives us a lot more robustness against node failure, but I'm not sure what else it gives us. - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyf7AE8Qx019l0ClAQFIzwP9FwaIKhZ5UP/517UoZ6Rl6SzyJUbEKpUY D6TpI1C4co1yKlF9MO3MM4oOjGPzadXS2QzznnRQ3pvtZRtUdxGuTSywRXQ0M7mL qQ690MfxWvlGZwQOOrD6mUOks9mBCEz0KOMjXQyxTB7sudh+TNL1PGfg3PUel++v UVbm8EPDMTI= =3vid -----END PGP SIGNATURE----- From majordom Thu Mar 13 08:20:16 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA07754; Thu, 13 Mar 97 08:20:16 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA07742; Thu, 13 Mar 97 08:20:06 EST Date: Thu, 13 Mar 1997 08:20:15 -0500 (EST) From: "Michael G. Reed" To: Onion Routing List Subject: Re: discussion points In-Reply-To: <3.0.32.19970312142049.00710208@netcom9.netcom.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- On Wed, 12 Mar 1997, Lucky Green wrote: |>>No, constant bandwidth makes absolutely NO difference in this |>>situation. This is an attack which looks at coincidences of NEW |>>connections going IN TO and OUT OF the network...not data flow within |>>the network, but timing on new connections. Bandwidth means nothing |>>here. |> |>Upon re-reading your original post, I agree that constant bandwidth amongst |>the routers will not help against a passive attacker in this case. What |>will help, however, is constant bandwidth between the user's proxy and the |>first core router. If the user makes a connection to an onion router in the |>morning and leaves it up until the evening, the passive attacker learns |>nothing. Other than your work hours, that is :-) True. This would be a slightly different implementation than we currently have since every connection to a proxy generates a new connection into a core onion router (ie, unless the protocol allows for sequencing request over one socket, you have N sockets for N requests...HTTP 1.1 allows for this). This design is different than our original design (oh, about 9 months ago) where proxy and core were one process, and some of our testing to date has pointed out that it was (probably) a mistake to make this division (the division was made since the fundamental core architecture is not application specific, so people could write new proxies and have them talk to the network without having to replace core onion routers...only add the proxy -- while nice from a theoretical perspective, every time we go up and down the IP stack (even on the same machine) and have more system calls, our efficiency goes down. We may ultimately roll the well established proxies into the core onion routers and still allow for new (experimental) proxies to connect as they do now. Comments? |>[about noise] |>>This can be done a number of ways including: 1) letting the higher |>>level protocol do it, 2) Inserting it into DATA cells somehow |>>(possibly by having cells with illegal lengths...only the last router |>>would be able to determine this, which might, in turn, give you some |>>more information to attack the connection), or 3) Adding a new cell |>>type (BAD idea since it introduces markers that can be tracked |>>independent of the other cell types). To somewhat quote Monte Python, |>>"#3 is right-out". Furthermore, I really have to think some more |>>about #2 before I would consider adding it. #1 is by far the best, |>>but we are trying to coexist with UNMODIFIED internet applications, so |>>this is difficult. |> |>Of course you want to interoperate with unmodified Internet applications. |>That's why you should use a client side proxy. What happens at the other |>side of the proxy is yours to choose. It could be as simple as a steam |>cipher into which the proxy xor's the data. [Client side proxies are the |>future. My thanks go to Jim McCoy for convincing me of that. In fact, the |>average user's machine will probably run multiple chained proxies for the |>same protocol: |> |>An onion routing proxy to access the network, followed by SafePassage to |>increase SSL strength from 40 to 128 bit, followed by a decrypting proxy |>for webpages that are stored encrypted, followed by CookieCutter, to get |>rid of unwanted cookies, etc. That's four chained proxies for HTTP alone. |>[As a side bar, proxies@communities.com is the list where we are currently |>discussing specs for a "universal" client side proxy that allows for |>dynamic loading of proxy modules.] Great idea, but isn't that going to be a little heavy on the overhead? Also, how are you handling the parsing/tokenizing of HTML? Right now it looks like our anonymizing proxies does some of these all wrapped up in one (cleans up the data stream, routes through onion routing, and certainly we could add end to end crypto like stronger SSL). |>>It will |>>help confound external observers, but a bad node will always know what |>>is padding on node to node padding. End to end padding could be |>>hidden from all but the last node, |> |>It might help to think of the "last node" as something that resides on the |>user's machine. I was thinking more in terms of the other end of the pipe (ie, the end away from the user would know it had got padding). |>>and protocol padding could be |>>hidden from all nodes. |> |>Wouldn't that require a proxy on the accessed website? Not necessarily. It could just make bogus requests to that website. The last node will not be able to determine a valid request from a bogus request since they are both legitimate....we're just ignoring the response of the later when it get's back to the original requestor. |>The mere fact that you are working on Onion Routers proves that you have a |>clue and are none of the things that you seem I am assuming. I assure you, |>I am not assuming any of the traits you mention. Great! :-) Really though, I was just venting at no one in particular... most of the email that had stroked me the wrong way was from people that are not on the list and really don't want to bother being on the list because they don't want to help/contribute but are VERY quick to jump to conclusions and criticize something they don't understand. We *REALLY* do appreciate all the comments we've gotten from the list in the past week or so here (for one thing, it has fundamentally shaken a few of us with regard to some of our base assumptions about the threat model...), keep them coming :-) - -Michael -----BEGIN PGP SIGNATURE----- Version: 2.6.2 iQCVAwUBMyf/FE8Qx019l0ClAQHP0QP6A6fc8Kx5X/SZ2nYOU0Gbs97aMgxEHuuw 0mF3dXVvWi0VeelW6CrUwdnCnam2Y8qWXfRCUh2JgqWj9QBdIXxhehO3ZG/cc3IG GXNgHfd3Himb0YLwvqv4TaONrEggHJJzSQDqoGNkN9mQZ5W4VXV8o9bfHYvvymUp soBTNiHMAg8= =ZygT -----END PGP SIGNATURE----- From majordom Thu Mar 13 08:33:12 1997 Return-Path: Received: by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08325; Thu, 13 Mar 97 08:33:12 EST Received: from banana-jr.itd.nrl.navy.mil by itd.nrl.navy.mil (4.1/SMI-4.1) id AA08302; Thu, 13 Mar 97 08:32:59 EST Date: Thu, 13 Mar 1997 08:33:08 -0500 (EST) From: "Michael G. Reed" To: Onion Routing List Subject: Re: Bandwidth/Padding/etc... In-Reply-To: <3.0.32.19970312132106.006e1adc@netcom9.netcom.com> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Sender: owner-onions@itd.nrl.navy.mil Precedence: bulk -----BEGIN PGP SIGNED MESSAGE----- On Wed, 12 Mar 1997, Lucky Green wrote: |>The idea of "smoothing" has merit. When it was first mentioned, I thought |>you were talking about a high frequency smoothing. But if you mean by |>smoothing a low frequency smoothing, say adding and removing available |>bandwidth along well established daily usage patterns, then smoothing may |>not provide the attacker with more information than a constant bandwidth |>pipe would. Yes, lower frequency is what I had envisioned...it could even done at different levels (ie, general bandwidth could follow one pattern per 24x7 usage and then we could allow for some deviations in time if really high usage...essentially allow us to push the threshold up a little more if we really need it and then gradually fall back down to the 24x7 rolling threshold). |>Agreed. It all comes down to the treat model. I assume a very resourceful |>adversary that can monitor the entire network, or at least large parts of |>it. The adversary in my threat model also can conduct active attacks. What |>is your threat model? I believe David is currently writing up our threat model (Aren't you Dave :-), so it should be out there soon. |>As to the link capacity, I believe the core routers should be on high |>capacity links that can be assumed to be mostly stable. The link between a |>core router and the user's proxy must of course be assumed to be unstable. I like the sound of that, but I'm wondering if we really can get the high-bandwidth/stable/geographically and locally diverse requirements met for core