Re: Forward and reply messages

[David Hopwood <david.hopwood@zetnet.co.uk>]

-----BEGIN PGP SIGNED MESSAGE-----

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

Yes, I probably wrote them off a bit too hastily.

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

Yes, I was wrong about this. If the header is decrypted with a key depending on
the payload, then although the crossover node can detect the tagging, it won't
be able to link it to a particular reply block.

I'll have to think about the effect for forward-only paths some more; I have
a nagging feeling that there's something I'm missing.

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

Exactly. I'd rather be able to eliminate as many tagging attacks as possible
before we start discussing path selection and batching strategies, rather than
having all of these interact in complicated ways.

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

Oh, right, I'd misread the description of strip. It is the same as replace
(so I've changed "replace" to "[strip]" below).

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

You're right, ignore this. The header needs to be have been encrypted in a way
that depends on the payload; just including junk that depends on the payload
isn't sufficient.

> > > 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 [strip] operation in a path; that's what
> > I meant by [strip] 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 [strip] in the forward part of a forward-then-reply).
> 
> Why is that not possible? It would seem that the strip [] 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.

I'd assumed that there was only going to be one value of N, for exactly
the reason you state:

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

Right, that's the conclusion I eventually came to.

> > Other than that, there's very little to choose between swap [and strip].
> 
> 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)

For a reply block yes. For forward onions the "required length" is L_MESSAGE.

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

Since the headers are variable-length, the payload can just be part of the
innermost header. When constructing a reply, the innermost header for the
forward part of the path is the reply block (encrypted in a way that depends
on the payload) followed by the random-looking payload.

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

Right, although one reason for adding some reply hops at the end is just to
prevent easy traffic analysis of received messages as forward or reply.
For that purpose, not many hops are needed.

[stuff about the balance of forward and reply messages snipped; I'll have
to think about that]

- -- 
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5  0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPMcW4DkCAxeYt5gVAQFg0ggAvwUJb0pjr+fOZK3B/RvuwFqiRMZQp2K/
Ycc2fYHnsG+MTTPE5waQaOh7PLifpKNBXNFF/3JA0La+gXq8jyfQHhkKoGA4mU87
V+2NHEde+M+rZ/WcMooPedwdYylzr9bhvt4K6s52K3g58ifhtWqv/8xg48O+vY9D
+g1LrTPM1fHylprXW/ixdwrrJCxtSayyfY3iTk14a4Ed8M4DPCQLMrbuLX+B8QAa
HCE7sJW5j9YlxXgYZ6LLPLwmM2yiGPQ+RH5zA+4ZbVNnW4urKoanK9RNRSdinm2t
IvQ9og5JOg3ZkIJOjzu7AHBoOkag1ajTMe/FvB+5l4oOV5NSHZWfhA==
=vj4d
-----END PGP SIGNATURE-----