Wei Dai wrote:
On Thu, Nov 02, 2000 at 10:14:24AM -0500, Adam Shostack wrote:
Actually, I'm unconvinced that even pipenet style padding is sufficient. Looking at the work on traffic analysis thats been done, we're in about 1970. We have one time pads (dc-nets), and some other stuff, but we don't have a DES to analyze. We have an adversary who has spent a long time learning how to do this well.
I'd prefer if people talked about PipeNet style traffic scheduling instead of PipeNet style traffic padding. What's really important to PipeNet security is that the timing of packets don't leak information, and padding is just a part of what's necessary to achieve that kind of timing. So I'd agree with you that padding by itself isn't sufficient, but I'd be interested in hearing more if you think PipeNet as a whole isn't sufficient.
For those that don't know about PipeNet Wei has a description here [1]. PipeNet is a synchronous mix-net where users stay connected and consume bandwidth 24x365 to avoid revealing when they are using it. PipeNet's synchronous behavior would be implemented on top of TCP with it's best-effort service by using the following scheduling algorithm (from [1]): | Each node expects one packet from each link id in each time unit. | Extra packets are queued for processing in later time units. | However, if a node does not receive a packet for a link id in a | particular time unit, it stops normal processing of packets for that | time unit and queues all packets. This ensures that any delay is | propagated through the entire network and cannot be used to trace a | particular connection. This is to defend against active attacks delaying packets to observe the effect on the network and hence trace routes. However I think this scheduling algorithm would have the side effect of making this variant of PipeNet very vulnerable to DoS attacks. Any user can arbitrarily delay packet delivery for the entire network by ceasing to send packets. It would also seem that performance would degrade badly to effectively the performance of the worst ping time link. (PipeNet uses mixing at each node.) Perhaps there are some engineering trade-offs you could make if you were to try to practically implement PipeNet. Adam [1] http://www.eskimo.com/~weidai/pipenet.txt
For those that don't know about PipeNet Wei has a description here [1]. PipeNet is a synchronous mix-net where users stay connected and consume bandwidth 24x365 to avoid revealing when they are using it.
My isp would start charging me extra if I surpassed my monthly ul/dl limit. Is this realistically feasible with today's infrastructure? ________________________________________________________________________ Total Internet Privacy -- get your Freedom Nym at http://www.freedom.net
On Sun, 5 Nov 2000, Adam Back wrote:
| Each node expects one packet from each link id in each time unit. | Extra packets are queued for processing in later time units. | However, if a node does not receive a packet for a link id in a | particular time unit, it stops normal processing of packets for that | time unit and queues all packets. This ensures that any delay is | propagated through the entire network and cannot be used to trace a | particular connection.
This is to defend against active attacks delaying packets to observe the effect on the network and hence trace routes.
However I think this scheduling algorithm would have the side effect of making this variant of PipeNet very vulnerable to DoS attacks. Any user can arbitrarily delay packet delivery for the entire network by ceasing to send packets.
It also limits the ability of Pipenet to scale. Basically, the more people you get, the longer the time periods become (because every node has to send every other node a packet, and it takes longer to receive a million packets than it takes to receive a dozen). Once you are down to being able to send only one packet per hour to any particular place, you are effectively scrod as far as getting anything done. Routing through other pipenet nodes is possible, of course, but all the net sources and sinks of data would quickly either overload with queued packets, or be forced to inundate the whole system with nulls on a very regular basis. I've been looking at a mode where nodes are considered "located" relative to each other in some kind of fake coordinate space - not necessarily correlated with physical location. Once you introduce a coordinate space, you can use concepts of direction to help route things. Break up the coordinate plane with a compass rose into sixteen semi-octants, and each round, you transmit to your nearest neighbor in each octant and also to randomly selected ones at medium, long, and very long distance. That way, you can guarantee that if you're not contacting the intended recipient of a packet you're forwarding this round, you will at the very least be contacting a node that's "closer" to the intended recipient than yourself. If you consistently route the packet to any node closer than you, without overshooting, it is guaranteed to arrive in a finite number of hops (overshooting may be feasible in practice, but I haven't been able to prove this property where overshooting is allowed. However, a limited number of overshoots ought to be okay - that's more effective in the average case and reverts to the provable case after the allowed overshoots run out. ). I think it would defeat traffic analysis, because the selection of who sends packets to whom is perfectly random each time, subject to the vagaries of the coordinate space. The analysts could tell who your closest neighbors were in the coordinate space, and could eventually build up a model of the coordinate space and figure out your coordinates in it - but no other information is revealed by the selection of whom you transmit to each time. If you wanted to keep the locations fluid, you could hash all the coordinates each night at midnight GMT. Bear
At 11:55 PM 11/5/00 -0500, captain_kirk@beta.freedom.net wrote:
For those that don't know about PipeNet Wei has a description here [1]. PipeNet is a synchronous mix-net where users stay connected and consume bandwidth 24x365 to avoid revealing when they are using it.
My isp would start charging me extra if I surpassed my monthly ul/dl limit. Is this realistically feasible with today's infrastructure?
Only one of the ISPs I deal with has a traffic limit, and that probably only gets counted for hits to my web pages, not from my dialup connection. Some higher-speed connections have limits, some don't, but again it's more common for hosting service than for transit service. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639
On Sun, Nov 05, 2000 at 10:11:54PM -0500, Adam Back wrote:
For those that don't know about PipeNet Wei has a description here [1]. PipeNet is a synchronous mix-net where users stay connected and consume bandwidth 24x365 to avoid revealing when they are using it.
PipeNet's synchronous behavior would be implemented on top of TCP with it's best-effort service by using the following scheduling algorithm (from [1]):
| Each node expects one packet from each link id in each time unit. | Extra packets are queued for processing in later time units. | However, if a node does not receive a packet for a link id in a | particular time unit, it stops normal processing of packets for that | time unit and queues all packets. This ensures that any delay is | propagated through the entire network and cannot be used to trace a | particular connection.
This is to defend against active attacks delaying packets to observe the effect on the network and hence trace routes.
However I think this scheduling algorithm would have the side effect of making this variant of PipeNet very vulnerable to DoS attacks. Any user can arbitrarily delay packet delivery for the entire network by ceasing to send packets.
It would also seem that performance would degrade badly to effectively the performance of the worst ping time link.
That is all true. I guess what you meant by "insufficient" is in terms of performance and defense against DoS attacks, not defense against traffic analysis. If that's the case then I agree with you. I think a protocol that has good performance, defense against DoS attacks, and defense against traffic analysis may not exist. There may not even be a viable protocol that trades off between these properties. The reason I have this suspicion is from a consideration of what the choices are when a node does not receive a packet in the time period that it expects to receive it. PipeNet chooses to propagate the delay to everyone else, and gets bad performance and defense against DoS attacks. Freedom chooses to propagate the delay to no one else, and gets bad defense against traffic analysis. I don't see what else you can do that would avoid both of these problems. There is a hope, however, that the performance and DoS problems of PipeNet could be solved in the future through other means. The performance issue is easier, since it just requires the underlying network to have better reliability and guarantee of service. The DoS problem could be solved if the underlying network is protected against DoS. Then we can require each user to place a large deposit on each node, which would be used to compensate everyone else for any delay caused by that user.
Adam Back wrote:
| Each node expects one packet from each link id in each time unit. | Extra packets are queued for processing in later time units. | However, if a node does not receive a packet for a link id in a | particular time unit, it stops normal processing of packets for that | time unit and queues all packets. This ensures that any delay is | propagated through the entire network and cannot be used to trace a | particular connection.
This is to defend against active attacks delaying packets to observe the effect on the network and hence trace routes.
I don't understand the necessity of this. if the amount of traffic is a constant anyway, a delay would vanish at the first node. e.g. my upstreams provider sends out x bytes every time unit, no matter whether or not he gets anything from me. when I stop sending, nothing in his traffic pattern changes.
For those that don't know about PipeNet Wei has a description here [1]. PipeNet is a synchronous mix-net where users stay connected and consume bandwidth 24x365 to avoid revealing when they are using it.
My isp would start charging me extra if I surpassed my monthly ul/dl limit. Is this realistically feasible with today's infrastructure?
You simply set (if it's set-able) the connection to whatever limits you need to. -- A quote from Petro's Archives: ********************************************** "Despite almost every experience I've ever had with federal authority, I keep imagining its competence." John Perry Barlow
At 03:00 AM 11/6/00 -0500, Bill Stewart wrote:
At 11:55 PM 11/5/00 -0500, captain_kirk@beta.freedom.net wrote:
My isp would start charging me extra if I surpassed my monthly ul/dl limit. Is this realistically feasible with today's infrastructure?
Only one of the ISPs I deal with has a traffic limit, and that probably only gets counted for hits to my web pages, not from my dialup connection.
Some higher-speed connections have limits, some don't, but again it's more common for hosting service than for transit service. Thanks!
Any Pipenet++ should be designed such that ul/dl limits can be respected and then forgotten. At least until everyone gets flat rate Mbps service. Remember when "1 megapixel, 10 MIPS, 10 MB RAM" was drooled after? BTW, given your real limits Captain, what rates do you estimate are feasible, Sir? [Not actually a facetious query...]
participants (8)
-
Adam Back
-
Bill Stewart
-
captain_kirk@beta.freedom.net
-
David Honig
-
petro
-
Ray Dillinger
-
Tom Vogt
-
Wei Dai