[tor-dev] Analysis of the Relative Severity of Tagging Attacks

Robert Ransom rransom.8774 at gmail.com
Mon Mar 12 03:45:10 UTC 2012

On 2012-03-12, Watson Ladd <watsonbladd at gmail.com> wrote:
> On Sun, Mar 11, 2012 at 8:32 PM, Robert Ransom <rransom.8774 at gmail.com>
> wrote:

>> But http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf and an
>> end-to-end MAC is more likely as a solution to the end-to-end tagging
>> attack, because (a) per-hop MACs would take up much more space in each
>> cell and disclose the length of a circuit to the exit node, and (b)
>> with per-hop MACs, if you can get a forgery accepted (which happens
>> with probability 2^(-n), where n is the number of bits in the MAC, for
>> any MAC that Tor could use), you know with probability 2^(-n) that the
>> next hop is the last one.
> You are going to have to be careful and explain this to me. I get the
> leaking the length of a circuit and position in the chain. But we use
> length 3 circuits in the current client node all the time, and if you
> weren't the start or the end, you are the middle. The forgery
> acceptance probability for Poly1305 is 2^-128. Forgery is not going to
> happen.

Non-truncated Poly1305 takes 16 bytes per relay, so it would eat up at
least 48 bytes per 512-byte cell, and more on 4-hop circuits (which
Tor clients do build fairly often) and hidden-service rendezvous
circuits.  Non-truncated Poly1305 is not going to happen.

> I also don't see what Bear/Lionness gets us. It does solve problems
> with losing sync. It does so at a cost of determining when identical
> ORs are sent, which happens a lot: think multiple http requests.

What do you mean by "ORs"?

(The BEAR/LION key would likely be different for each cell that a
relay processes.)

> Losing semantic security is a Bad Thing. I'll freely admit there are
> issues with incorporating a leak of circuit length into the protocol,
> as well as possibly (depending on details of TLS) leaking what lengths
> end where to a global adversary.

An end-to-end MAC inside the BEAR/LION wrapper should provide all the
security properties we need (note that the MAC key would also need to
be different for each cell).

Robert Ransom

More information about the tor-dev mailing list