Re: Reply blocks and tagging protection: a third variant

[Roger Dingledine <arma@mit.edu>]

On Wed, Apr 10, 2002 at 01:04:13PM -0400, George Danezis wrote:
> I think I need some clarifications on the "strip" scheme:
> - The header that gives the "strip N" order does not know the secrets in 
> side the A-onion. How can it produce junk that when appended to the 
> A-onion will pass the hash test?
> - (related) Since the creator of the B-onion does not know the secrets in 
> the A-onion how can he create junk that *when encrypted* with the secrets 
> in A will pass the hash test.

Yeah. Hm. It complicates things a bit more, but Nick and I have come up
with some clarifications that might actually work.

Basically, you need an extra step in the header.

Bob -> 1 -> 2 -> 3 -> 4     -> 5' ->     5 -> 6 -> 7 -> 8 -> Alice

Alice gives Bob the A-onion (5-8), from which Bob can read 5. Alice also
gives Bob a master secret key which can be used to generate the junk
that the A-onion is expecting. So basically Bob takes the A-onion and
builds a path 1-4, and then adds a crossover hop at 5' (same node as 5)
which does the strip. Since Bob adds that hop 5', he can make sure the
hash it's expecting works out. That hop 5' does a "strip" operation
(strip is a type, just like fwd and drop), which consists of
A) decrypt the rest of the message with the hash of the payload
B) throw away the bottom 8 hops, and rebuild them with junk based on
the master secret.
Since Alice also knows the master secret that 5' will use, her hashes
can anticipate it.

So basically, strip and swap are starting to converge into the same
design. This is really good. The main difference is that strip seems
like it wastes a header if there's a crossover point (and perhaps most
importantly, it requires Alice to package some more bits (the master
secret) along with the reply onion), and swap seems like it forces you
to make a crossover point if you're using more than 8 hops.
More on that below.

>You touch here a very interesting issue. Tagging attacks, as they exist in
>the current "strip"/"swap" proposals, and the proposals before are really
>"traffic confirmation" attacks. That means that the attacker can not use
>them to trace a message through the network but only to confirm a
>suspicion they already have. In that sense even the "swap"/"strip"
>proposals will leak some information, and I do not think that we can
>completely protect against that.
[snip]
>I think it is essential that all messages contain a crossover point,
>otherwise forward only messages are still vulnerable to tagging attacks.
>Crossovers are there to basically protect the forward path since the SURB
>path is not affected by tagging (the final result is encrypted anyway).

Actually, I don't see how tagging attacks can do traffic analysis even
in forward-only mails, if we're using bear. Basically they can't learn
if they tagged it unless they own the last hop, and plenty of mail is
plausibly random-looking anyway (assuming all delivery info is in the
header), so they'll never really be able to tell which one they tagged. I
believe it's still a traffic confirmation issue, not a traffic analysis
issue (if we use bear).

Agree/disagree?

Also, we might want to consider having "extra" headers no matter whether
we choose swap or strip, in order to have enough delivery information
for delivery types that want lots of information. Basically, there should
be no problem having a type in a header that says "and go read the next
128 bytes too, and use that".

At this point I'm willing to agree that swap is better than strip,
unless we come up with more arguments/problems in either direction.
And it's still not clear to me whether we need a crossover point to ensure
resistance to traffic analysis. (We need one to attach reply onions to
forward onions; and it might be a good idea to use them always if we're
going to use them sometimes; but I'm not convinced tagging attacks are
the problem we think they are (if we're using bear.))

--Roger