[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: Reply-block based pseudonym systems are broken? [Was: Re: SURB-Format]

[message reformatted to show quoting correctly.]

On Sun, Oct 21, 2007 at 11:52:17AM -0700, jeffery statin wrote:
> On Mon, 18 Jun 2007, Len Sassaman wrote:
>> However, reply-block based pseudonym systems are broken, completely. If
>> that might influence your direction with this, you may want to consider
>> those problems.
>> Nick's work in The Pynchon Gate (WPES, 2005) demonstrates that nym
>> servers, even SURB-based ones, that are based on mixes and reply blocks
>> fall victim to intersection attacks within a month's worth of traffic
>> *sent to the nym*. (Probably even more quickly now, based on the rise of
>> spam in the last few years.)
>> (See Section 4.2 of that paper, available here:
>> http://www.cosic.esat.kuleuven.be/publications/article-620.pdf )
> link: http://archives.seul.org/mixminion/dev/Jun-2007/msg00001.html
> How trivial is this type of attack?

It's an intersection attack, and it requires that you watch a lot of
nyms and a lot of recipients well enough to tell when the nyms are
getting messages and when messages are arriving at the recipients.  If
you can do that, you can notice that recipient X gets more messages
when Nym A sees higher traffic, and deduce that X is probably the
holder of Nym A.

The math to actually carry out the attack is trivial; a 10-year-old
child could do it.

Now, this attack is pretty obvious: the question before I did the
simulation reported in that paper was, "How much data does the
attacker need in order to link a nym"?  The answer seemed to be,
"distressingly little".

Read the paper to learn more.

The obvious defenses are as described in the paper at
      http://freehaven.net/doc/e2e-traffic/e2e-traffic.pdf :
increased delay variance, constant-rate message padding, etc.  They're
all expensive, and none is perfect.

>  What does this mean for the current state and future of MixMaster
> and MixMinion?

My first reaction is: Nothing.  Neither one is a nymserver. ;)

My second reaction is: Assuming that the results hold, one
of the more obvious ways to use reply blocks may be a bad idea.  Now
let's suppose that there *are* no good applications for reply blocks:
in this case, it might be better to stick with Type II indefinitely,
or with a variant of Type II that fixed some of the issues addressed
by Type III without jumping through the hoops that Type III does to
implement SURBs.  (Personally, though, I believe that there are still
reasonable applications for reply blocks.)

(BTW, if you've run into any web pages that capitalize the second M in
Mixminion, you probably shouldn't trust them.  They clearly haven't
read the Mixminion webpage or documentation closely enough to learn
how to spell it. ;) )

>  What is the dev stage of "The Pynchon Gate"?

There's a decent specification.  There's a guy who said he'd write it,
but I haven't seen any code so far.  If somebody else with time sits
down and writes it, that'd be grand too.

Personally, I worry that any full-padded solution like this could lose
enough users to resource demands and performance overheads as to
outweigh its anonymity gains.  But that's the sort of worry that can
only be confirmed or disproved by building the thing and seeing what

Nick Mathewson

Attachment: pgpczdEdNhA5E.pgp
Description: PGP signature