tag prevention again (was: Thoughts on MixMinion archives)

[Zooko <zooko@zooko.com>]

Folks:

Welcome to Len!

I continue to be quite excited about the mixminion project.  Thanks a lot for 
reading the archives and writing so much useful perspective and suggestions.  
It's reassuring to see that an independent design group came to some of the 
same conclusions.

 Len wrote:
>
> * number of hops to be secure vs. reliable
> 
> There was concern that about having enough header slots that half of that
> number would be enough nodes for a secure chain. I think that 8 is a fine
> number. Remember, if the chain is so long that it is almost guaranteed to
> be unreliable, it doesn't matter that it is secure. People won't use it.
...
> * forward messages must not be generally distinguishable from replies
> 
> I'm of this opinion strongly, which is why I like the crossover point
> system.


I just have one comment right now, because I see people converging on a 
position (two-headers-swap technique) for a mistaken reason.

The mistake is the idea that the two-headers-swap technique is more 
efficient than the two-payloads technique.

When I first understood George's two-headers (swap) technique, I thought it 
was a brilliant hack that kept the tag prevention and the directional 
indisinguishability of my two-payloads technique while optimizing away the 
2X message expansion of the two-payloads technique.

I still think that it is brilliant, *but* it isn't at all clear that two-
headers (whether swap version or strip version) is an efficiency win over 
two-payloads.

Assume, for a moment, that when you decide to use two-headers-swap instead of 
two-payloads, you double the length of the chain.  You do this in order that 
the security in the new scheme will be unarguably *at least* as good in the 
old.

Now, AFAICT, both schemes use the *same* amount of the underlying bandwidth 
(the resources owned and managed by the remops) to achieve the same amount of 
overlying bandwidth (to carry the same number and size of anonymous messages).
So the new scheme hasn't helped with efficiency at all AFAICT.

But the two-headers scheme suffers more than the two-payloads one does in 
terms of latency and reliability.


Okay, so can revisit the idea that we have to have chains "twice as long" in 
order to safely do the two-headers-swap technique.  We could have one measure 
of security, K, which is the number of hops before the swap so it measures our 
safety against tagging attacks, and another X, which is the total number of 
hops.  (For the current design I think that X must always be 2K.)  Anyway, you 
could argue that if K is less than the total hops from the old system, that 
your security is still almost as good, because the only added weakness 
requires an active attack by the Kth node (the swap node), and you can choose 
the swap node more carefully and so forth.

This might help, but the safety analysis is more complicated.  It is harder to 
tune your "performance vs. safety" trade-off in the two-headers system, 
because your safety is a function of K,  but your reliability is a function of 
X (in fact it is P^X, where P is the per-hop reliability).


Okay, I feel like I might be missing something about the efficiency of the two-
headers-swap system, but here is my current understanding of the tradeoffs:

 * safety:

Two-payloads and two-headers tie.  I'm still unsure of the safety of normal 
old distinguishable directionality.  Not that if one of them proves 
insufficiently reliable, then users will "tune down" their safety in order to 
get reliability, so that one will lose on safety.

 * bandwidth:

Normal old system wins.  I think two-payloads actually wins over two-headers 
(I haven't explained why I think this -- it has to do with retrying and 
fragmentation which we haven't designed yet).

 * latency:

Normal old system wins.  Two-payloads definitely wins over two-headers.

 * reliability:

Normal old system wins.  Two-payloads probably wins over two-headers.

 * simplicity:

Normal old system wins.  Two-payloads IMHO wins over two-headers, but maybe 
it's just easier for me to understand because I invented it.


Okay, so if only normal-old-system were safe it would be the clear winner.  
I'm tempted to try to "fix" its safety with dummy traffic and so forth, but 
I don't think that's a very good approach -- taking a dangerous choice for 
efficiency reasons and then trying to patch it -- when it can be avoided.

Therefore, my current preference is for the two-payloads technique, since it 
beats normal-old technique on safety and I *think* beats two-headers on the 
other issues.


Regards,

Zooko

Zooko.Com -- Security and Distributed Systems Engineering