Forward and reply messages

[David Hopwood <david.hopwood@zetnet.co.uk>]

-----BEGIN PGP SIGNED MESSAGE-----

Roger Dingledine wrote:
> David Hopwood wrote:
> > Count me in. I have lots of notes on a mix-net design derived from Babel
> > that I never had time to write up properly.
> 
> Great. I've added you to the list. George and I are off to the pet2002.org
> workshop for tomorrow and Monday, and then I'll be at cfp2002.org til next
> Saturday. Mixminion discussion will probably pick back up around then.

I was busy last week as well, but I found time to read the archives (which
were very interesting).

[...]
> > Forward messages are completely authenticated and non-malleable; for reply
> > messages only the header can be authenticated (but that is enough to
> > prevent tagging attacks, I think).
> 
> We've been working on the problem of making forward and reply
> messages indistinguishable at all points, [...]

The problem with that is:

 - Reply messages can't be made non-malleable over the full message.
 - Therefore, if forward and reply messages are indistinguishable to nodes,
   forward messages also can't be made non-malleable over the full message.
 - If forward messages aren't fully non-malleable, then there is a traffic
   confirmation tagging attack that works regardless of the number of hops
   on the path:

   The attacker is the message recipient, Bobby. The sender is Alice; for
   simplicity assume that Alice keeps on sending messages to Bobby until
   the attack works. Bobby selects a set of messages as they enter the mix
   network, that may or may not contain one of Alice's messages. He tags
   them by altering the message bodies. Then he can test whether any message
   he receives is tagged, in which case it must be in the set (assuming
   Bobby is the only attacker). Repeat until the intersection of all
   possible senders is only { Alice }.

Using a large-block cipher for the symmetric encryption helps by ensuring
that tagging a message only carries one bit of information, but it's not
sufficient. The attack works for both forward-only and forward-then-reply
messages, and it also works if a small number of the intermediate nodes
check non-malleability of the full message (as George suggested), provided
those nodes are controlled by Bobby (since in that case each tagged input
message can be re-tagged when it is output).

Of course Bobby is a fairly powerful attacker. Nevertheless, IMHO it's
important to prevent this attack, because I think that preventing it is
necessary if we're going to prove any more general security properties.
If we prove the mix-net secure against traffic confirmation attacks where
the recipient can also modify messages and colludes with some subset of
nodes, then it's automatically secure against weaker attacks. If we
don't, then it's not clear how to prove anything useful at all.

(There may be an analogy here to proving the security of an encryption
scheme by proving left-or-right security: the latter is effectively defined
in terms of resistance to a "confirmation attack", but it implies security
against a very wide range of attacks.)

Always ensuring full non-malleability for forward messages at each hop
solves the problem, because any attacker would have to control all of the
nodes on the forward path, and we have to assume that isn't the case
anyway. For reply messages, the recipient created the reply path, and so
gains nothing from being able to tag messages on that part of the path.

(I'm glossing over some details here. In particular, reply messages have
to be encrypted and random-looking on the last hop in order for the reply
path to be secure against parties other than the recipient, although that
doesn't prevent them from being encapsulated in an ordinary SMTP email.
I.e. recipients of messages using reply blocks will need Mixminion software
to decrypt, but do not necessarily need to run a node.)

Incidentally, there is another alternative to the 'swap' and 'strip'
methods described in the archive, that makes forward and reply messages
indistinguishable; it has a 'replace' operation that replaces part of
(say, the last half of) the message header with pseudo-random junk. This
would be more efficient in message size than 'swap', and slightly more
flexible than 'strip', but since it still doesn't prevent the traffic
confirmation tagging attack, it's not what I would recommend.

In any case, having distinguishable forward and reply messages is not so
bad. If we arrange that exactly half of the messages are of each type (e.g.
by doubling the length of forward-only paths and making those messages look
like reply messages on the second half of the path), then it only halves
the size of the anonymity sets. The effect of that is pretty easy to analyse,
and can be partly compensated by adding more cover traffic.

Another advantage of not trying to make forward and reply types
indistinguishable is that in that case we can do without a variable-length
block cipher (I think).

> and on allowing somebody using a reply block to add a reasonable anonymizing
> path (for two-way anonymity).

Yes, I've been assuming that is necessary (for single-use reply blocks; I
don't think multi-use reply blocks can be made secure).

> (And you're right, I can't tell much from just the diagram. I'll wait
> for the notes. :)

I'll talk about my design in another post.

- -- 
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPMDZkTkCAxeYt5gVAQHPGAf+OI/arQTkZh4TdnPkv+e2jADH2yYT0r6w
7mXuYMiUtx+plNCjyh/wNEPaZXWSApysdP2C8mTeTerKtXjm4TlvuvKi/pM+SenL
tG2rJwgzyZNjH2CLMaP1098sx+HYMJB8Zv01UAA/sId3HKht0ODDWqYK9Ept+koq
/v4xZgJczTctIO2XF0Oymgvu77JbStNR2UKT2TIqBC6N2BAQ/j7x5Rcl1/1x607L
Lfz2FMv0ir9cAhIownG2BTZmxc1R05tpxDVdL/D71I2vrI9flwLgoXBYv+/+H896
QkSGt1lxHnDN87isfdwUM6NFWbsZm0HQXm6KlNSvaNL7GQKsjwd6FQ==
=OSfa
-----END PGP SIGNATURE-----