Re: Forward and reply messages

[Roger Dingledine <arma@mit.edu>]

I'm going to give the swap/strip approaches a few more gasps of breath,
before we let them die.

On Tue, Apr 23, 2002 at 05:44:17PM +0000, David Hopwood wrote:
> > Because the swap operation involves decrypting the second header
> > with a hash of the second header and payload, then even a malicious
> > crossover point can't determine what the second leg is if anything has
> > been tampered.
> 
> Hmm, that's correct for forward-only messages (note that the resulting header
> can also depend on the rest of the message for the "strip" and "replace"
> options, so this is not specifically an advantage for "swap").

True.

> However, it halves the effective number of nodes on the path, since an
> attacker now only needs to control *either* all of the nodes before, or
> all the nodes after the crossover point, plus the crossover node itself.
> Also, if fixed but secret paths are used, then the attacker gains some
> information about the first half of Alice's path even if he can't immediately
> break the second half; this information could then be used in subsequent
> attacks.

Good point.

> So it's definitely not clear that this is better than having forward and
> reply messages distinguishable: in the latter case, you could double the
> number of messages and get (roughly) the same size of anonymity sets, but
> still have the full effect of the chosen path length for each message, and
> therefore potentially lower latency for a given security/paranoia level.
> 
> Also, the attack still works against forward-then-reply messages (note that
> you can't swap twice on the forward part of a forward-then-reply path). That's
> the most serious problem IMHO.

Actually, it's not clear to me that the attack still works. If the first
leg goes over the forward path and the second leg goes over the reply
path, then
* If the message is tagged in the first leg, the reply leg will be
  obliterated, so the adversary will never know it was meant to go to
  the reply leg. Since the swap operation happens at the end of the
  first leg, at a node the sender chooses (rather than the receiver),
  then the receiver can't learn anything by doing tricky things like
  having his reply leg start on a never-used-for-anything-else node.
* If the message is not tagged, then as before, it is successfully
  anonymized against the receiver and observers.

So if this defense works, then we're actually not wasting *any* hops
when anonymizing mail to reply blocks.

(But you're right -- if Alice sends 10 anonymized mails to Bob's reply
path, and Bob tags 5 of them when they leave Alice, and Bob owns his
reply path and Alice uses the same route to anonymize herself and Bob
owns the end of the route she chooses, then Bob will see that 5 incoming
messages are garbled and 5 go to his reply path. That's scary -- scary in
a way that we in the research community have never been able to quantify
well. Hm. Perhaps this is a strong argument against using the same path
for multiple messages. Bleah. What do others think here?)

> As far as I understand, 'strip' shunts the message to the left so that part
> of the message that was previously in the body (equivalently, the second header)
> is now in the main header. This is not the same as 'replace', which changes
> part of the main header. (The changed part could depend on the payload of the
> message, for example using PRF(key, seed_in_header XOR hash(payload).)

The 'strip' operation could better be described as 'strip and regrow'. The
idea is to throw away the bottom (rightmost) chunk of the header and
regrow it with predictable junk (using the padding seed derived from
the master secret in that hop's header). Its only purpose is to get rid
of the junk generated by the first leg, so the second leg (built by the
receiver) can do integrity-checks on the header.

Like swap, strip can also do a decryption of the whole header (before
or after regrowing) with a key based on the hash of the payload, to kill
the message if the payload has been tagged.

So it seems that strip and replace are very similar if not the same.

> > What I can't solve is that if the second leg is built by the receiver and
> > the first leg is built by the sender, then the 'replace' operation needs to
> > happen at the end of the first leg but creating pseudo-random junk based on
> > what the second leg expects.
> 
> Yes. The sender could set
> seed_in_header = seed_from_reply_block XOR hash(payload), for instance.

I'm not sure what this buys us. We need to use the hash(payload) in such
a way that it destroys the information about the next hop if the payload
has been tagged. It's not sufficient to just cause a tagged payload to
make the node generate incorrect padding and let the next hop (the one
that's first in the reply leg) drop it.

> > So when you make a reply block you also need to separately include a seed
> > for generating the junk that the reply block expects.
> 
> Yes, but that's only a minor complication.

Fair enough.

> > So it seems klunkier than swap.
> 
> It's possible to have more than one 'replace' operation in a path; that's what
> I meant by 'replace' being more flexible (unfortunately, this doesn't help to
> fix the attack against forward-then-reply messages, because it's still not
> possible to have more than one replace in the forward part of a forward-then-reply).

Why is that not possible? It would seem that the strip (or replace)
operation can say "drop and regrow the bottom N hops in the header",
so you could include several strips with varying N's over the course of
the path.

But I am wary of allowing more than one value for N, since it makes
messages distinguishable from one another ("that node saw a strip 4,
and that node saw a strip 8. I bet the strip 4 was earlier in its path
than the strip 8.")

Further, if the strip operation *always* involves decrypting based on
the hash of the payload (since the strip at the crossover point must ---
otherwise an attacker could distinguish whether we're at the crossover
point), then there cannot be any strips inside a reply path, because
the author of the reply path doesn't know the payload.

So while you can do more than one strip, it doesn't seem like it's
actually very useful.

> Other than that, there's very little to choose between swap, strip, and replace.

Agreed.

[vast snip while i continue thinking about it]
> A reply block is contructed in the same way as a forward-only onion,
> except for the length. To construct any onion:
> 
>  1. Work out the total length taken up by per-hop headers and overhead.
>  2. Fill a buffer starting from that index with arbitrary padding to the
>     required length [dark blue in the diagram].

Specifically, the required length of a header (L_HEADER)

>  3. For each layer from outer- to innermost, decrypt that padding in the
>     same way as would be done by a node [light blue], filling at the end
>     with deterministic padding [magenta].
>  4. For each layer from inner- to outermost, encrypt the per-hop headers
>     [green for the public-key-encrypted parts, yellow for symmetrically
>     encrypted], and include a MAC of the ciphertext [input shown by the
>     red lines] in a field of each header.

Somewhere in here, if it's the instructions for constructing any onion,
should be "attach your payload if you've got one". I would guess it's
step 2b?

> Note that no special processing is needed at the crossover point for a
> forward-then-reply message; from the point of view of the sender, the
> reply block just forms the first part of the plaintext of an ordinary
> forward message.

It's certainly tempting. I need to think about it some more, eg in terms
of proportions of forward vs reply messages seen on the network. Indeed,
somebody sending a forward message cannot afford to make any of the
hops look like replies --- or at least, for each hop that looks like a
reply, he does not gain the anonymity he thinks he gains, due to tagging
vulnerabilities.

So if we assume half the messages in the network are forward messages, and
each reply message also is sender-anonymized, then 1/4 of the messages
on the network are replies. I'm not sure any of those assumptions
are reasonable, but if they are, it would seem you should send an
all-reply message for every all-forward message you send, to even
out the proportions? Are there going to be issues with being able to
distinguish dummies?

I'll sleep on it another night. Other opinions, or clarifications,
appreciated.

--Roger