[messaging] SURBs

[Trevor Perrin]

On Thu, Jun 19, 2014 at 2:15 PM, Brian Warner <warner at lothar.com> wrote:
>
> I think you need one of (SURBs, Hidden Services, a realtime reverse
> channel) to hide a recipient's identity

I'd include broadcast (e.g. alt.anonymous.messages) and PIR (e.g. Pynchon Gate).


[Trevor]:
>> It's interesting you're not proposing a "nymserver" here
[...]
>> I assume that's because you want to limit nym -> Alice traffic for
>> security reasons, so it's safer to dole out SURBs in small quantities
>> to correspondents?
>
> Yeah, small quantities limits the "burst of traffic" attacks that could
> be mounted to try and discover the location of the recipient
> (network-enforced rate-limiting).

If I understand the arguments at [1], eliminating nymservers also
helps against long-term "intersection" aka "statistical disclosure"
attacks.


[Trevor, wrt tackling forward mixing independent from reverse / replies / SURBs]
>> Or at least, it's nice to solve easier problems on the way to harder
>> ones.
>
> Yeah. I guess we should address the "two people who know each other get
> to communicate securely" case before trying to tackle the case where one
> of them doesn't know the other.

While I agree, we should consider the counter-argument from Mixminion
[2] and Sphinx [3] that indistinguishable forward and reverse messages
give more security, so should be co-designed.  From Mixminion:
"""
Since replies may be rare relative to forward messages, and thus much
easier to trace, the Mixminion protocol makes reply messages
indistinguishable from forward messages even for mix nodes.  Thus
forward and reply messages can share the same anonymity set.
"""

I see the benefit, but I'm not sure it's worth the cost.  In
particular, reading [2] and [3] makes me think:
 (a) "tagging attacks" are better handled with separate forward and
reverse formats
 (b) the benefits of indistinguishable forward/reverse traffic are not huge

I argue (a) and (b) below (this is long and and boring, sorry...)


Tagging vs. separate formats
---
Consider a tagging attack against forward messages:  The entry mix can
flip a bit in the message body that is sent to the next mix.  This bit
will stay flipped as subsequent mixes onion-decrypt the body with a
stream cipher, so the recipient can see that the plaintext has a
certain bit flipped and collude with the entry mix to determine the
sender.  This is fixed by putting integrity checks in the
onion-encrypted headers, so mixes can discard tampered messages.

For reverse messages, the sender uses a SURB provided by the recipient
for the headers, so it's impossible for the headers to contain body
integrity checks.  But tagging the message body isn't an attack
against reverse messages, since it doesn't affect recipient anonymity.
So  problem solved.

(You might ask: what about messages between senders and recipients who
both want identity-hiding.  In that case, you could send a forward
message to some middle-person containing a reverse message.  The
middle-person decrypts the reverse mesage and sends it (Mixminion
supports this, combining it with the "crossover" notion - see below).
The above measures against tagging still work).


Tagging vs. a combined format
---
Now consider a combined format.  Forward messages have to be
indistinguishable from reverse messages, so can't use integrity
checks.  That means tagged messages *will* flow through the mix net in
the forward direction.

To prevent this leaking information, MixMaster and Sphinx add some
other mechanisms:
 * The body is processed with a large-block cipher, so that tagging
the input to a mix results in a randomized output.
 * At a designated "crossover" mix in Mixminion (the exit mix in
Sphinx), the input message body is used to decrypt the next
destination.

I think the security argument is:
 * The large-block cipher prevents the crossover mix from detecting
that a message was tagged with a specific value, and undoing the tag
so the message can be processed.
 * If a message is tagged, when it reaches the crossover mix the next
destination is undecryptable.  Thus no later mixes or the recipient
get any information about the tagging.
 * The crossover mix does learn that a tagging - or some sort of
tampering - occurred.  But since the crossover can't link the message
with a recipient, it doesn't matter if the tagging allows the message
to be linked to a sender (and the large-block cipher makes linking to
a specific sender hard, since different taggings can't be recognized).

The last bullet is subtle.  As Mixminion points out, "the choice of
crossover point can still reveal information about the intended
recipient".  If the crossover mix was chosen because it has a
relationship with some recipients but not others, then when it detects
the tagging, it can associate the tagged message with these
recipients.  To prevent this, Mixminion recommends that the crossover
mix should be be placed in the path after sufficient mixing has
already happened to protect the sender's identity, but with some
additional mixes following (Sphinx doesn't support this - the exit mix
is used as a crossover).

Mixminion also discusses the possibility of "multiple-message"
tagging, where the crossover is able to infer that several messages
passing through it might be related (e.g. they arrive at similar
times).  If some of these message are tagged and some are not, the
crossover could learn the destination from the untagged ones.  To
prevent this, Mixminion suggests that senders should choose different
crossover points.

Stepping back, the issue seems to be that crossover mixes are in a
position to learn *something* from the tagged message, so we need to
make complex arguments, and be careful choosing them, to prevent this
being a problem.


Security without a combined format
---
So the mechanisms and security situation wrt tagging are complicated
in the case of a combined format.  Are the benefits of
indistinguishable forward and reverse traffic worth it?

Mixminion argues that it's helpful to combine forward and reverse
traffic since "replies may be rare relative to forward messages, and
thus much easier to trace".

To argue the other way:
 * Due to link encryption, forward and reverse traffic will always be
indistinguishable to outsiders (i.e. anyone but the mixes themselves).
 * A viable mix net might get a lot of security from dummy traffic.
In that case, the dummy traffic could contain both forward and reverse
messages, so a severe imbalance could be avoided.
 * If reverse messages are rarer (perhaps because more users care
about relationship-hiding than identity-hiding), then it might be
acceptable for reverse messages to spend more time in the mix net to
get the same degree of security.

Anyways, I admit this is a hard question, but I think there's decent
arguments for anyone to work on a simple format for forward mixes that
resists tagging attacks (e.g. something like [4]).

Trevor

[1] http://archives.seul.org/mixminion/dev/Oct-2007/msg00010.html
[2] http://mixminion.net/
[3] http://www.cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf
[4] https://eprint.iacr.org/2002/119.pdf