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

[Robert Ransom]

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

>> (The BEAR/LION key would likely be different for each cell that a
>> relay processes.)
> Different how: if we simply increment the key we still remain open to
> replay attacks.

The paper proves that BEAR and LION are 'secure' if the two (three?)
parts of the key are 'independent'.  Choosing the subkeys
independently is too expensive for Tor, but the standard way to
generate 'indistinguishable-from-independent' secrets is to feed your
key to a stream cipher (also known as a 'keystream generator').
Incrementing that stream cipher's key after processing each cell would
indeed prevent replay attacks (unless the stream cipher is something
really horrible like RC4), but it's probably easier to just take the
next 2n (3n?) bytes of keystream.

>>> 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).
> So we need to include nonces with each cell, which we need to do anyway.

No -- each cell needs a different nonce.  Hopefully the nonce won't
need to be sent with every cell.

(End-to-end out-of-order delivery, non-reliable delivery, and
variable-sized relay cells are unlikely to happen soon, even after a
UDP-based link protocol is added to Tor, because they make end-to-end
tagging much easier.)


Robert Ransom