Re: [tor-talk] Strong anonymization in a fixed group of participants

["Edward Z. Yang" <ezyang@xxxxxxx>]

Hello Nick,

Thanks for the reply.

> The system you describe is approximately a one-hop mix, with Tor layered in
> front of the mix to prevent the mix (the leader in your design) from
> learning who submitted which message.  So the security against learning
> group membership will reduce to the security of Tor; the security against
> the leader learning who sent what reduces to the security of Tor; and the
> security against a third party learning who sent what reduces to breaking
> Tor *and* breaking a one-hop mix.

Right.  But it is possible Tor is insecure against attacks that don't matter
in practice for its ordinary use case, but matter here.

> (Incidentally, there's an extensive literature on how to build mixes: it
> turns out that "delay a random interval" isn't optimal.)

I am not sure a mix network is the right primitive here: in the usual
formulation (ala Chaum), anonymity requires at least one mix server be honest.
In the case of a one-hop mix, this is no good, because you're entirely
depending on the mix server being honest.  So we want a protocol which is
robust against malicious mixers (or we should use more hops--but this
particular use-case wants to minimize hops because every hop costs
transaction fees.)

My particular formulation nominates a leader, but really the one-hop
mix should be thought of as a multiparty computation.

> To answer your original question though, it would help to know the threat
> model!

Sorry!  Here is the threat model for the mix:

    - We expect the protocol to function correctly when all participants
      are honest but curious.
    - In the case of a minority of actively attacking participants,
      it would be good if the protocol resisted this attack, but we
      are also OK with a protocol abort (so DOS by participants is OK).
      Corrupt output is not acceptable, but if the protocol aborts
      loss of anonymity of the random string is not a problem, since
      it can be revoked and we can try again with a new random string.
    - In the case of a majority of actively attacking participants (Sybil
      attack), the protocol is permitted to fail to provide anonymity silently.
      We screwed in this case anyway, because if the adversary controls all of
      the nodes involved in the mix, even if the protocol is carried out by a
      trusted mixer he can still deanonymize.
    - The mix protocol should be completely resistant to outside attackers, including
      attackers with full access to network traffic.

The anonymity set is the participants of the mix.

We want to layer this on top of the traditional Tor threat model,
in the case where a user would like to act on behalf of a pseudoanonymous
entity anonymously (the pseudoanonymous entity is the participant in
the protocol).  In this case we don't care if we're weak against
a traffic analysis attack on the Tor network itself.

> Tor will provide anonymity in this case so long as no adversary has
> compromised or controls enough of the network to observe a message as it
> enters and exits.  But if an attacker sees the same message entering and
> exiting the tor network, they can (probabilistically) match them based on
> size and timing.  This doesn't give the attacker a win against your
> protocol though (IIUC) unless they also defeat the leader's mixing.

Wouldn't this be protected by adding the timing delay, and stipulating
all of the messages be constant size? (I guess I also don't see why
a random timing delay is not optimal.)  I think I do want this protocol
to be robust against this attack, because in general the participants
of the protocol may *not* be anonymous (since it is one-hop).

> Other systems to look into here will come from the general anonymous
> communications literature. DC-nets are great for low-volume broadcast among
> a small number of participants, if you don't care about performance or
> DoS-robustness.  Or since what you're talking about already incorporates a
> mix, you could look at other mix designs for ideas.  Have a look through
> http://freehaven.net/anonbib if you haven't already.

That is a very nice list of papers.  I will do some reading into DC-nets;
what is your favorite paper describing their implementation?

Edward
_______________________________________________
tor-talk mailing list
tor-talk@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk