Dear All, Rather then get further sucked into a debate that is producing more heat then light about Wegman-Carter, I've decided to make a concrete proposal for how Tor can better protect its streams from manipulation.
Right now Tor encrypts the streams of data from a client to a OR with AES-CTR and no integrity checks. I propose the following: On establishment of a new connection between a client and an OR (using either the Goldman et al paper or ephermental DH) the client and the OR derive a single 16-byte K. The client has an 8 byte counter which starts at 1, the client counter, the OR an 8 byte counter which starts at 0, the OR counter. Each cell from the client to the OR is protected by AES-GCM defined as in the NIST standard, with a 4 byte string "TorC" being used to make our counter 12 bytes. (If you read the standard you will see this is the method for generating nonces recommended). The counter is incremented by 2 each time a packet is sent. Under no circumstances can it go backward. Under no circumstances does an OR or Client accept a packet that reuses a nonce (nonces should be sent along if we make transport unreliable). Under no circumstances are more then 2^64 packets sent. Under no circumstances are packets longer then 2^32 bytes. Following these rules an attacker who sends 2^64 forgery attempts has probability 2^-36 of successfully forging one message. If we limit the attacker to 2 billion forgery attempts (forgery must be online) then the probability of forgery is 2^-68. I think we can live with that. These numbers come from http://cr.yp.to/antiforgery/securitywcs-20050227.pdf. Note that these numbers assume AES is secure, and are theorems if AES is secure.
This proposal is independent from the establishment of streams. This proposal eliminates issues relating to an intermediate node flipping bits in an HTTP request, thereby tagging the traffic, amongst other evil things manipulation can do. If we want more performance the evaluation of a polynomial over GF(2^128) can be replaced by GF(2^130-5), or AES could be replaced by xsalsa20, and the nonce lengthened. Sincerely, Watson Ladd --- "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin
On 2011-11-02, Watson Ladd watsonbladd@gmail.com wrote:
Dear All, Rather then get further sucked into a debate that is producing more heat then light about Wegman-Carter, I've decided to make a concrete proposal for how Tor can better protect its streams from manipulation.
Your proposal is so detailed and concrete that I'm not even going to try to figure out what it means.
I propose Salsa20/8 and CubeHash-256 as our general-purpose stream cipher and message digest for the first new crypto designs (seriously), and I propose that we implement multiple new crypto designs as soon as possible (seriously) so that we know we will get future migrations right.
But if this bikeshedding about the low-level details of cryptographic primitives keeps up, I'm going to design my own stream cipher and message digest.
Right now Tor encrypts the streams of data from a client to a OR with AES-CTR and no integrity checks.
Bullshit. We have a 32-bit-per-cell integrity check at the ends of a circuit.
Robert Ransom
On Wed, Nov 2, 2011 at 12:45 PM, Robert Ransom rransom.8774@gmail.com wrote:
On 2011-11-02, Watson Ladd watsonbladd@gmail.com wrote:
Dear All, Rather then get further sucked into a debate that is producing more heat then light about Wegman-Carter, I've decided to make a concrete proposal for how Tor can better protect its streams from manipulation.
Your proposal is so detailed and concrete that I'm not even going to try to figure out what it means.
I'm going to suggest that we ought to isolate protocol discussions from primitives discussions here. The discussion of how to put together a good relay packet format using a stream cipher and a MAC (or a stream cipher with an authenticating mode of operation) ought to be separable from the discussion of which stream cipher/MAC/authenticating mode we use.
(If it isn't separable -- if the format relies on particular properties of a given primitive -- that strikes me as a point against the format.)
[...]
Right now Tor encrypts the streams of data from a client to a OR with AES-CTR and no integrity checks.
Bullshit. We have a 32-bit-per-cell integrity check at the ends of a circuit.
Let's keep this polite, please. "Not so" is a perfectly fine alternative to "bullshit," and is likelier to keep future conversations productive.
cheers,
On Wed, Nov 2, 2011 at 11:45 AM, Robert Ransom rransom.8774@gmail.com wrote:
On 2011-11-02, Watson Ladd watsonbladd@gmail.com wrote:
Dear All,
[...omitted..]
Right now Tor encrypts the streams of data from a client to a OR with AES-CTR and no integrity checks.
Bullshit. We have a 32-bit-per-cell integrity check at the ends of a circuit.
So let's say that I am a malicious 1st hop and a malicious 3rd hop, and I want to find out. If I have known plaintext I can modify it, say the packet type headers. Then the third router will see nonsense and know that it this circuit is compromised. The second router can detect this with my proposal, it cannot right now. Ends of circuit alone are not enough.
Robert Ransom _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Sincerely, Watson Ladd
On Wed, Nov 02, 2011 at 01:19:52PM -0500, Watson Ladd wrote:
On Wed, Nov 2, 2011 at 11:45 AM, Robert Ransom rransom.8774@gmail.com wrote:
On 2011-11-02, Watson Ladd watsonbladd@gmail.com wrote:
Dear All,
[...omitted..]
Right now Tor encrypts the streams of data from a client to a OR with AES-CTR and no integrity checks.
Bullshit. We have a 32-bit-per-cell integrity check at the ends of a circuit.
So let's say that I am a malicious 1st hop and a malicious 3rd hop, and I want to find out. If I have known plaintext I can modify it, say the packet type headers. Then the third router will see nonsense and know that it this circuit is compromised. The second router can detect this with my proposal, it cannot right now. Ends of circuit alone are not enough.
There may be other virtues to integrity checks besides at the end nodes, but this example is not compelling. All our experiments and analyses have indicated that it is trivial for end nodes to know when they share a circuit. You mention an active adversary, but it is trivial for such an adversary to put a timing signature on traffic detectable at the other end---trivial but unnecessary. My own work showed a passive adversary is sufficient, and Bauer et al. showed that you don't even need to pass application data cells: circuit setup is enough. Despite extensive research, nobody has yet come up with a padding/dropping scheme to resist a passive, let alone active, adversary adequate and practical enough to consider implementing and deploying.
aloha, Paul
On Wed, Nov 2, 2011 at 2:19 PM, Watson Ladd watsonbladd@gmail.com wrote:
On Wed, Nov 2, 2011 at 11:45 AM, Robert Ransom rransom.8774@gmail.com wrote:
On 2011-11-02, Watson Ladd watsonbladd@gmail.com wrote:
Dear All,
[...omitted..]
Right now Tor encrypts the streams of data from a client to a OR with AES-CTR and no integrity checks.
Bullshit. We have a 32-bit-per-cell integrity check at the ends of a circuit.
So let's say that I am a malicious 1st hop and a malicious 3rd hop, and I want to find out. If I have known plaintext I can modify it, say the packet type headers. Then the third router will see nonsense and know that it this circuit is compromised. The second router can detect this with my proposal, it cannot right now.
See https://blog.torproject.org/blog/one-cell-enough ; see also the part in the original Tor design paper where we discuss integrity checking and tagging attacks. See also the three paragraphs near the beginning of section 6.4 in the document under discussion, which say:
""" It's not such an obvious improvement. Including more MACs is more expensive in per-cell overhead. The attacks that we would foil this way but not with Option 3 are not so much better than the the passive or timing-based-active end-to-end attacks that would still remain.
Consider that if option 3 is in place, an end-to-end attacker who wants to do a tagging attack at one node can garble the rest of the circuit and see if the output is garbled at the exit node. But such an attacker could just as easily close the circuit at one of those nodes and watch for a corresponding close event, or even better -- simply pause traffic on that circuit for a while and watch for a corresponding gap at the exit. The only advantage of the garbling attack would be that garbled cells are presumably rarer than circuit closes or traffic pauses, and thus easier to use to distinguish target circuits. But that's still questionable: the other attacks win fine, and the pause attack doesn't risk detection as much.
So why might we want to do this? First, the overhead doesn't need to be as bad as you might first expect (see below). Second, it would be nice to increase the security margin as much as possible: "attacks only get better". """
In summary:
- If you control first and last hops in any currently known deployable low-latency anonymity design, you win already through active and passive timing attacks. (As Paul notes in his mail.) - Xor tagging attacks are strictly easier to detect than timing attacks, since the attacker risks breaking the circuits that they don't in fact control. - Therefore it isn't completely obvious that any attacker actually gets weaker if Tor does hop-by-hop integrity-checking. (Before anybody says "but..." here, please actually go read that blog post :) ) - Moreover, doing whole-cell crypto (as in option 3) lowers the number of bits that you can get out of a tagging attack. So the incremental advantage of option 4 (hop-by-hop integrity checking) over option 3 may be even less than its advantage over current Tor.
- But maybe we should do hop-by-hop integrity checking anyway, since: - Less sophisticated attackers probably would have an easier time implementing tagging attacks than they would implementing timing correlation attacks. - "Attacks get better, not worse." Right now, I can't think of a way to make cell tagging better than active or passive timing attacks. But who knows, maybe we'll be glad later that we added it for some reason if somebody finds a novel attack on some other part of our protocol stack or something. - It's doesn't have to be all that expensive in space to help a lot, and it doesn't seem to be any more expensive in time than the whole-cell-crypto designs of option 3. (It might in fact be cheaper in time, depending.)
This is one of the parts of the document that I wish people would discuss, btw. The conclusions here are not obvious to me, and although I prefer hop-by-hop checking based on the reasons above, I don't think that they're absolutely compelling.
Ends of circuit alone are not enough.
That's certainly worth discussing, but it's not what Robert was disagreeing with. What you said was "Tor encrypts the data ... with no integrity checks." I think that's what he was reacting to.
cheers, -- Nick
-
Nick Mathewson -
Paul Syverson -
Robert Ransom -
Watson Ladd