[freehaven-dev] Re: carnivore concerns

[Roger Dingledine <arma@MIT.EDU>]

On Mon, Jul 31, 2000 at 04:23:05PM -0400, Nick Feamster wrote:
> Hi Roger,
> 
> what exactly do you mean by a more paranoid mix configuration?  Seems as
> though a mixnet operating at the transport or application layer will be
> susceptible to link-level compromise regardless of topology.  What
> exactly does this imply? 
> 
> Interested,
> Nick

By configuration, I mean the method chosen to combine mix nodes into
a mix network or cascade.  As Pfitzmann showed us at the conference,
there are a number of traffic analysis attacks that can be used if there
are constraints in the system. The specific one he gave as an example
was if users can pick their own paths through the network, and paths
are fixed-size: he showed that in the vast majority of cases, having
one honest mix in the path was not nearly enough:

Alice --  Mix1 --------      Mix6 -- Bob's recipient
                       \    /
                        Mix5
                       /    \
Bob   --  Mix3 -- Mix4       Mix7 -- Mix8 -- Alice's recipient


In this scenario, users can pick their own paths, and paths are
fixed-length at 4. Mix5 is the honest mix. The adversary can watch
the others.

Alice chooses Mix1->Mix5->Mix7->Mix8.
Bob chooses Mix3->Mix4->Mix5->Mix6.

By watching how many hops the message takes before and after Mix5, our
adversary can distinguish which message coming out of Mix5 corresponds
to the ones coming in.

While this looks like a particularly trivial (and easy to fix) example on
the surface, I think it instead demonstrates how little we understand
traffic analysis and how many different sorts of attacks we might
introduce into a system even from a simple-sounding idea like letting
users pick their own paths from the mix network.

We can't simply solve the problem by saying "use a mix cascade, not a
network" because the underlying issue -- can an adversary distinguish
messages based on characteristics of the messages or protocols? -- is
still not answered. For all I know, even running your message through
a compromised mix node is giving him a good shot at figuring out your
endpoints, particularly in a case like Free Haven where servers reuse
their mixnet addresses.

--Roger