An Analysis of the Degradation of Anonymous Protocols
Summary by Cristina Abad

This paper describes some protocols that have been proposed to provide
anonymous communication over the Internet. It then proves that they all suffer
security degradation when a particular initiator continues communication with
a particular responder across path reformations. The authors also describe
some attacks particular to each protocol.

The attack they identify is called predecessor attack, and it works under the
following assumptions:
· There is a recurring connection between some party that initiates the
sending of a message and the receiver of that message
· There is session-identifying information available to the attacker in the
transported packets that uniquely identifies this recurring connection
· The protocol’s method of selecting the active set must be uniformly random

The attack works as follows: there is one or more attackers in each active set
that is able to associate messages sent with a specific session. Whenever the
attackers are able to determine the specific session, there is some first
attacker that sees the message. The initiator is more likely to send the
message to that first attacker than any other participant. The attackers log
the participant who first sent a message that can be identified as a
transmission to the attackers in that round. At any step, the attackers
identify the participant that has been logged the largest number of times as
the initiator.

Then, they describe specific versions of the generic attack, as can be applied
to different protocols (Crowds, Onion routing, Mix-Nets, DC-Net). For each
they derive upper bounds on the amount of resources an attacker requires to
significantly degrade the anonymity of users.

They also define the set-up attack, in which the initiator always places a
victim node as its direct successor in its routing path. Then, if attackers
attempt to determine the initiator’s identity, all messages will appear to
come from the victim.

The paper concludes by indicating that with DC-Net, only when all pairs of
nodes shared coin-flips does the attack require unreasonable resources to
succeed; but being fully-connected makes it un-scalable and susceptible to
denial-of-service attacks.

======================================

Votes:

Strong Accept --> 2
Accept ---------> 3

======================================