Re: Reply blocks and tagging protection: a third variant

[Roger Dingledine <arma@mit.edu>]

On Tue, Apr 09, 2002 at 09:16:23AM -0400, George Danezis wrote:
>This property could be
>implemented by a "strip N and decode using payload" operation but I think
>it is unnecessary to provide more general operations than strictly
>necessary (unless there are other reasons).

Ok. I'll try to summarize all of this here, so we're all on the same
track.

Bob wants to anonymously send mail to the pseudonym 'Alice' using Alice's
reply block. Alice's reply block traverses path A. Bob wants to traverse
path B first.

So Bob adds[1] some hops describing path B to the hops describing path
A, adds his payload M, and sends it into the network. It proceeds as a
normal forward message (at every hop, the mix should pull off a layer,
check the hash of the header[2], and put some junk towards the end of
the header), until it gets to the Crossover Point (the point at which
it has finished traversing B), at which the Crossover Mix changes[3]
the header. At the same time as that changing process, he takes a hash
of the rest of the message[4] and decrypts the new header with that
hash. The message then proceeds as usual until it hits a hop that says
"I'm the end, send the payload to alice@foo.com."

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

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 regrow 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 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?] 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.]

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

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

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

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