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

[Zooko <zooko@zooko.com>]

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


The reason header-swap messages are still partially (statistically) 
distinguishable is that a mutually-anonymous chain is longer (having 2K hops) 
than a sender-anonymous chain (having K hops), but each has exactly one swap 
hop.

Therefore, when your node processes a message and that hop is a swap, then you 
know the message is more likely to be a sender-anonymous ("forward") message.

In addition, if the message is *not* a swap, then you know the message is more 
likely to be a mutually-anonymous message.

I asked my wife^H^H^H^Hmathematics consultant Amber O'Whielacronx to quantify 
this and she says the following.  (Note that I asked her to distinguish 
between sender-anonymous and mutually-anonymous messages, ignoring recipient-
anonymous, although the same argument applies to that kind but with less 
dramatic advantages to the attacker.)

------- begin included math
P(1-way) = p
P(2-way) = 1-p
P(swap | 1-way) = 1/k
P(swap | 2-way) = 1/2k


P(swap) = P(swap | 1-way) P(1-way) + P(swap | 2-way) P(2-way)
              = p/k + (1-p)/2k = (p+1)/2k

P(1-way and swap) = P(1-way) P(swap | 1-way) = p/k

P(1-way | swap) = P(1-way and swap)/P(swap) = (p/k)/((p+1)/2k) = 2p/(p+1)

This is < 1/2 when p < 1/3, and > 1/2 when p > 1/3


P(not swap) = 1 - (p+1)/2k

P(1-way and not swap) = P(1-way) P(not swap | 1-way) = p(1-1/k)

P(1-way | not swap) = P(1-way and not swap)/P(not swap)
                                   = p(1-1/k)/(1-(p+1)/2k) = 2p(k-1)/(2k-p-1)

This approaches p from below as k approaches infinity
------- end included math

I then plugged in a couple of sample numbers:

P(1-way | swap) where P=1/2 is 2/3.  That means that if sender-anonymous and 
mutually-anonymous messages are sent in equal proportion to one another, that 
when your node observes a swap message, there is a 2/3 chance that the message 
is a sender-anonymous message.  This is one of the values of P that yields the 
highest "advantage" -- the node's chance of being right using this technique 
minus the chance of being right by blindly guessing in whichever way P leans.

P(1-way  | not swap) where P=1/2 and K=4 is 0.46.  That means that if sender-
anonymous and mutually-anonymous messages are sent in equal proportion to one 
another, then when your node observes a non-swap message, there is a 0.54
chance that the message is a mutually-anonymous message.


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.

I know that we have a good design for keeping that kind of information hidden 
in the headers themselves, but the paper does not mention whether an attacker 
can learn that kind of information by other means such as traffic analysis.  
(And he *can* learn some such information from traffic analysis, if 
I understand the current design correctly.)


Regards,

Zooko

Zooko.Com -- Security and Distributed Systems Engineering