CDR: link padding & traffic analysis (Re: ZKS -- the path to world domination)

Adam Back adam at cypherspace.org
Wed Nov 22 20:12:19 PST 2000


Obfuscation writes:
> Adam Back writes:
> > It's as strong as we could make it.  Private interactive
> > communications are a hard problem.  As Wei and I were discussing in
> > the "PipeNet protocol" thread in the last couple of weeks, there are 4
> > main properties you're trying to optimise over:
> >
> > 1. security (resistance to traffic analysis)
> > 2. performance
> > 3. bandwidth efficiency (cost)
> > 4. DoS resistance
> >
> > It appears pretty hard to get more than one of these properties with
> > theoretical optimality.  PipeNet gets the first one with good
> > theoretical security, but none of the others are good.  Freedom makes
> > an engineering tradeoff which does reasonably on all 4.
> 
> What about adding link padding?  Can you say something about why
> this doesn't help, or costs too much?

So the attack you described without link padding involves the attacker
either:

- eavesdropping on all links into and out of the network (untargetted
attack)

- or eavesdropping on a targetted or suspected user

  - and then eavesdropping on all exit nodes
  - or, on selected web sites you think the user visits

- or trying to work backwards from an exit node or web site to a user

  - by eavesdropping on entry nodes

If the attacker can observe those things, he can observe the effects
of network congestion because freedom is not synchronous.  (Making
freedom synchronous would adversely affect performance and make it
much more vulnerable to DoS.)  The attacker therefore already has the
necessary taps to match up congestion patterns between the client to
first hop link and the exit node or web site request.

If congestion is too noisy or uniform to discern anything, he can go
create some selective congestion by ping flooding (or inducing more
plausibly deniable types of congestion) on that link.  And observe the
effects.  He can very easily hide the source of his congestion
attempts by creating it using the freedom network.

The attacker can also substitute the need for extensive network taps
by measuring congestion inside the freedom network to narrow down
where a user is coming from.  Any unpriviledged user can measure
congestion in real time using the freedom protocol by creating routes
over all combinations of hops, pairs of hops and triples of hops.
This may allow a user to work backwards from an exit node to an entry
node with only one network tap.

So the main cost increase for the attacker of link padding is the
complexity of the analysis.  But it doesn't add many bits.  It would
probably be easiest to do what the Onion Routing analysis used: plot
some graphs of the timing data.  You would probably be able to
visually see the traffic analysis patterns.  Automating the analysis
would be a little harder due to the noise.


Next the cost of link padding.  Clearly it costs.  ISPs use "bandwidth
aggregation" figures to estimate their bandwidth requirements based on
online users.  This figure means what percentage of their modem
bandwidth a user uses while online (not 56 kbits on a 56kbaud modem
because the user pauses between downloads etc).  This figure varies
and changes over time.  With a bandwidth aggregation factor of 6:1 it
would cost 6 times as much bandwidth.  On top of that you don't want
to change bandwidth utilisation in response to demand or you leak
information about routes opening and closing.  So you need to have
some surplus padding available for users to use as they open
connections.


So how does one fix it if link padding alone doesn't work?  As I
suggested doing this efficiently and practically is an open problem.
PipeNet style synchronous works, or latency padding (which comes to
the same thing), but as discussed earlier these have pretty severe
performance implications.

So the challenge is, to find a more efficient hybrid or alternate
design which retains as much as possible PipeNet or DCNet security
properties, but improves performance and reduces bandwidth costs, if
such networks exists.

Adam

> Without it, someone monitoring your system can see which ZKS node you are
> talking to.  If they then monitor that node they can see that whenever
> you send an incoming message, there comes an outgoing message, so they
> can see the next node you are talking to, and so on.
> 
> With link padding, they couldn't do this.  They'd have to interrupt
> your data stream and then monitor *all* the outgoing traffic from *all*
> the ZKS nodes and see which one got interrupted.  This sounds like a
> much more expensive attack.  It is an active attack as well, while the
> previous one is passive and could be done by a Carnivore system.





More information about the cypherpunks-legacy mailing list