Re: header-swap isn't perfectly indistinguishable (was: problem in 3.2 "Replies")

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

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

Zooko wrote:
> Thanks to George and Nick for answering my mail about 'problem in 3.2
> "Replies"'.
> 
> I understand the design now.  I am working on a document which derives the
> current header-swap design by stepwise refinement from a very simple starting
> design, where each step is motivated by an item from a list of explicit
> desiderata.  That document will not be ready in time for the imminent
> submission deadline, and I don't think that the paper needs it.
> 
> There is however one detail that this process has revealed which is worth
> looking at right now.
> 
> It concerns indistinguishability within a processing node.  Basically, perfect
> (statistical) indistinguishability in the header-swap method is not possible
> without forcing all chains be the same length (which would be twice as long as
> one-way-anonymous chains need to be).

I'm not convinced there is really any problem with forcing all chains to be
the same length; the extra hops for forward messages still contribute to
anonymity, so they are not wasted.

[Aside: 'path', 'route' (as noun) and 'chain' (as noun) seem to be synonyms.
We should standardise on one, e.g. 'path' as in mix-acc.]

Consider any synchronous design (e.g. a pure cascade, or a batch synchronous
design with any combination of cascade and free route parts), with a fixed
path length \ell. Make the first \ell/2 of the hops authenticate the whole
message, and the last \ell/2 the header. This is the "distinguishable" approach,
but note that what is distinguishable is first-half vs. last-half messages,
*not* forward messages vs. replies. In a synchronous network the position on
the route is not secret anyway.

Note also that increasing the path length in this case does not have much
effect on latency, which is primarily determined by the batch period (and how
many times a message is delayed to the next batch). It does have an effect on
reliability for forward-only messages, but the reliability is no worse than
for replies.

Direct SMTP replies can also be made indistinguishable from other messages
by having the Reply-To: node create a forward onion (even though it won't
actually provide anonymity for the replier).

Tagging is not possible for the first half of the path. It is for the second
half, but that is not a problem because for a reply message the tagging is
only detectable by the recipient (who created the onion), and for a forward
message the first half of the path already provides unlinkability. Also, if we
decrypt the second half payloads with an SPRP and use a structure like this:

                                       |
  random secret free route -> cascade1 -> cascade2 -> random secret free route
                                       |
                                    halfway

then tagging a message mangles it and does not give any information about
future free routes, so in that case we get the full security benefit of the
longer path length.

> There is one further issue about indistinguishability: the swap occurs at a
> semi-predictable point along the chain, so if the attacker can guess anything
> about how many hops a message has already taken from its source or how many
> hops it will take to its destination then this further contributes to the
> distinguishability.

Not only that; for asynchronous networks there are other attacks that rely on
knowing where a message is in the path, so the fact that the swap (or strip)
reveals that the message is half-way along the path is undesirable. E.g. the
first attack in section 4.2 of [disad-free-routes] applies when all but one
MIX in the first half of the path is untrustworthy. For synchronous networks
there is no attack.

- -- 
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

iQEVAwUBPNhavDkCAxeYt5gVAQG9wQgAvwbnaxalmh8wVNtPQNlO08p1CHmUKE1X
fkD54Ag/KmET3DqoeYwyhlYlvHL/+V6sfChaz40lGIQ5AuDnSnw86ZC2fT+8JiR+
uAeDOsxGroFt7YNGLZKYLYrb0/tcU59pxhejM9fUQjn307DaOrIS4Lk4mu0mr6mx
P1NjL6iQBi2JA28JJz0Oy8MWIxka7scByOwlbrm7mNLNd77Y2wq0ul9z8rw+DQjj
mOq5RC2Tf2xVHzOgENa5g0JYxw664E4meJgyZmqnk8YG8+7x+7DPhu2X5h7J7uEC
Shh9EPLdbeg7xmjEO7BamtyDENWgsUej7KMLvH6O+ot5fBe9EkJEqQ==
=XUcE
-----END PGP SIGNATURE-----