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

[Robert Ransom]

On 2012-03-12, Watson Ladd <watsonbladd at gmail.com> wrote:
> On Mon, Mar 12, 2012 at 9:04 AM, Robert Ransom <rransom.8774 at gmail.com>
> wrote:
>> 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.
>
> As I understand the tagging attacks of our favorite scavenger they
> repeat a cell, turning it and all following cells in a circuit into
> gibberish. This causes the circuit to close. I don't understand how
> changing keys after each cell affects this attack: we still get
> gibberish when a cell is repeated, precisely because the key changes.

No, They tag a cell by changing a few bits of it.  Because Tor uses
AES128-CTR alone for its relay protocol, the cell reaches the other
end of the circuit with that bitwise difference intact; an honest
relay would reject and ignore the cell (thus causing all further cells
on the circuit to fall into the bitbucket with it -- see tor-spec.txt
section 6.1), but a malicious relay can recognize and remove the tag.


>>>>> 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.
> We can of course not send the nonce with each cell, incrementing on
> successful arrival.
> But why does the MAC key need to be different for each cell? MACs take
> nonces to prevent replay attacks.

For the same reasons that DJB switched to generating a new Poly1305
key (i.e. a new pair (r, s)) for each secretbox operation, rather than
taking the trouble to keep one secret r around and generate a new s by
applying a secret PRF to a non-secret nonce (as Poly1305-AES did):

* Generating and using 32 extra bytes of stream-cipher output with the
message's nonce is cheaper than generating and using 16 bytes of
stream-cipher output with a fixed nonce (for r), then generating and
using 16 extra bytes of stream-cipher output with the message's nonce
(for s), with a typical good stream cipher like Salsa20.

* If an attacker obtains mathematically useful information about r,
the attacker can modify every message which uses that same value of r.
 This becomes much less problematic when each r is used for only one
message (more precisely, when the attacker cannot use information
about the value of r used for one message to obtain information about
the value of r used for any other message).


> Anyway, you probably have something much more final figured out, which
> I should wait to poke holes in when you propose it.

It's not final yet.


Robert Ransom