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

[Watson Ladd]

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.
>
>>>> 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.
Anyway, you probably have something much more final figured out, which
I should wait to poke holes in when you propose it.
>
Sincerely,
Watson Ladd


-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin