Re: Reply blocks and tagging protection: a third variant

[George Danezis <gd@theory.lcs.mit.edu>]

Dear All,

On Wed, 10 Apr 2002, Roger Dingledine wrote:
> Ok. I'll try to summarize all of this here, so we're all on the same
> track.
> 

I will try to follow the summary and address the issues of Nick's email in 
here as well.

> 
>  [in sync up to here]
>
> This approach is robust against tagging attacks:
>   During path B:
>     Tagging the header is detected by the next honest hop
>     Tagging the payload causes the Crossover Mix to be unable to decipher
>       the next hop, and thus unable to learn where the message was going.
>   During path A:
>     Tagging the header is detected by the next honest hop
>     Tagging the payload cannot be detected because the hops of path A
>       *encrypt* the payload, so it will just look random anyway.
>       [I'm assuming that delivery information does not need to be in
>        plaintext in the payload. Indeed, I can't see how that can work
>        with our crypto, anyway.]
> 

This is not always true. When the routing information of path A is a 
forward path the operation is in fact decryption (of the message that the 
sender has encrypted before). Therefore a tagging attack is possible but 
will achieve nothing: The message has already traveled through path B 
securely therefor it is not linkable to any sender (or to any recipient 
assuming that the final recipient of a forward message is in the payload)

> Now, you'll notice there are four points in the summary paragraph where
> I'm vague about how the process works. George and I have different ideas
> of what to do there.
> 
> The "swap" approach:
> [1] You build an onion just with the hops in path B. You also
> layer-encrypt the A-onion with the secrets specified in the B-onion. Then
> you just put the two onions adjacent to each other. Together they are
> the header.
> [2] Actually, you only check the hash of the first half of the header. The
> junk goes at the end of the first half of the header. The second half
> of the header just hangs out getting unwrapped at each step.
> [3] You swap the first half of the header with the second half. Now
> this new second half is the one that just hangs out getting unwrapped
> at each step.
> [4] Specifically, he hashes both the payload and the second half of the
> header. That way he verifies that neither of them has been modified.
> 
> The "strip" approach:
> [1] You start with the A-onion, and you add layers to it like normal.
> [2] Check the hash of the whole header as normal.
> [3] The information in that hop specifies how much of the bottom of the
> header to throw away and re grow with junk. Alice knew the value of this
> junk when calculating the hashes inside the A-onion, so all the hashes
> will work out.
> [4] Just the hash of the payload.
> 

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.

> I think both of these ideas will work. We need to figure out which one
> is simpler, or which is safer. Some observations:
> 
> * The strip approach can be used multiple times in a given path. So
> if you see a strip operation, you're not sure you're at the Crossover
> Point. Perhaps the person is just sending a forward message but threw
> in a strip as cover. However, because the strip operation involves
> decrypting with a hash of the payload, a reply block cannot include a
> strip operation except at the beginning. So if you see a strip operation,
> you know you're on the B-path or at the Crossover Point.
> 
> * On the other hand, I believe the swap approach can be used at most
> once in a path. [is this right? or could you rig the cryptosystem to
> encrypt and then decrypt so the header becomes valid again? even so,
> would it be akin to a one-time pad?] 

I think this is correct, there can only be one crossover point.

> So when you see the swap operation,
> by definition you are at the Crossover Point. If you're tracing a message
> and you see it hit a Crossover Point, then later down the chain you can
> rule out all the messages which are Crossover Point messages.
> [This is kind of an exotic attack, but it *is* a security difference
> between the two.]

It is indeed a security difference. Of course this attack is only possible 
for someone who controls the crossover mix, and some other mixes on the 
path. A variant of this attack is I think applicable to the "strip" 
method (although since there might be many strips it goes not provide as 
much information).

> 
> * With the strip approach, the reply-block author can specify the
> number of hops used. If they choose 8, then it's just like the swap
> approach. (They don't need to use all 8; the person using the reply block
> can't tell how many of the hops are actually used.) If they choose 4,
> they leak information about the security of the reply block. If they
> choose 16, they prevent people from anonymously replying to the reply
> block. Is this a bug or a feature?
> 

I think we should have a standard size of 1/2 the total header for all 
SURBS. But I may be biased because as Roger points out his is quite close 
to the "swap" method.

> * On first glance, it seems that if your path does not contain a Crossover
> Point, then you are vulnerable to tagging attacks. But they obviously
> can't tag headers since they're integrity-checked. If they tag the
> payload and it's encrypted, they'll never be able to see the tag. If they
> tag the payload and it's plaintext, then it will look encrypted. If the
> adversary knows the target always receives plaintext mail at noon each
> day, he might tag a suspected incoming message and confirm that he sees
> no plaintext mail. But that's equivalent to just dropping the mail rather
> than tagging it! Are there better attacks here, or is tagging just solved?
> 

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.

> * If you're using the swap approach and you want a forward path that
> uses more than 8 hops, then your path must include a Crossover Point. But
> with the strip approach you don't need one.
> 

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

> Please list other differences and comparisons here. I'm sure this isn't
> all we should be looking at.
> 
> I'm off to bed,
> --Roger

I think we are progressing here. I am quite happy with the above 
comparisons, and I do not have strong feelings about the "strip" or "swap" 
methods (as long as we are not able to find any other attacks on them). 

I am leaving on the 12th for San Francisco, so I will be off line for a 
few days. I hope to have some meating with Roger and discuss about this 
project a bit more over a drink.

Yours,

George