On 2012-03-12, Watson Ladd watsonbladd@gmail.com wrote:
On Mon, Mar 12, 2012 at 9:04 AM, Robert Ransom rransom.8774@gmail.com wrote:
On 2012-03-12, Watson Ladd watsonbladd@gmail.com wrote:
On Sun, Mar 11, 2012 at 10:45 PM, Robert Ransom rransom.8774@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