Analysis of the Relative Severity of Tagging Attacks: Hey hey, ho ho! AES-CTR mode has got to go!
A cypherpunk riot brought to you by: The 23 Raccoons
Abstract
Gather round the dumpster, humans. It's time for your Raccoon overlords to take you to school again.
Watch your step though: You don't want to catch any brain parasites[0].
Introduction
For those of you who do not remember me from last time, about 4 years ago I demonstrated the effect that the Base Rate Fallacy has on timing attacks[1]. While no one has disputed the math, the applicability of my analysis to modern classifiers was questioned by George Danezis [2] and others. However, a close look at figure 5(a) of [3] shows it to be empirically correct[4].
Recently, Paul Syverson and I got into a disagreement over the effectiveness of crypto-tagging attacks such as [5]. He asked me to demonstrate that they were more powerful than active timing attacks (which I've done in [6]), and to measure just how much more powerful they were (which is shown in this work). At least I think that's what he was asking. His paragraphs were very looooooong...
Anyway, out of the goodness of my little Raccoon heart, I asked my brethren to help me complete this proof ahead of schedule. We're worried about you guys. You be gettin sloppy with da attack analysis, yo (brain parasites??). And when ya get sloppy, the Raccoons pick up the scraps and multiply.
And, as you'll see below, you're not gonna like it when we multiply. It means more work for you. (But you probably should have realized that in the first place).
The Amplification Potential of Tagging
Crypto-tagging attacks like [5] provide for an amplification attack that automatically boosts attack resource utilization by causing any uncorrelated activity to immediately fail, so the attacker doesn't have to worry about devoting resources to uncompromised traffic.
Those of you who are already familiar with [5], stay with me. The authors of [5] apparently did not realize the amplification power of their attack, either. Despite my teasing above, I can see why you dismissed them initially.
The crypto-tagger achieves amplification by being destructive to a circuit if the tagged cell is not untagged by them at the exit of the network, and also by being destructive when a non-tagged cell is "untagged" on a circuit coming from a non-tagging entry. It transforms all non-colluding entrances and exits into a "half-duplex global" adversary that works for the tagger to ensure that all traffic that he carries goes only through his colluding nodes.
Imitating a Tagging Attack with Timing Attacks
The crux of the argument against fixing crypto-tagging attacks is that they can be imitated by an active adversary using timing attacks.
To imitate a tagging attack, the attacker attempts to achieve circuit killing amplification by using timing to try to determine which circuits are not flowing to colluding nodes, and kill them.
The imitated tagging attack has two steps. First, the two colluding endpoints correlate all candidate matches together and kill all other circuits off. Then, they embed a more thorough active timing signature into the remaining circuits to determine the sure matches.
We contend that this first step has very little timing information available due to the need to close circuits before streams are opened (which happens after just a couple cells). Certainly not enough to establish 0-error across a large sample size. Even so, in the analysis we'll be generous and concede a very low false positive rate could still be possible. It turns out not to matter that much, as long as it's non-zero.
So let's analyze each step of the imitating attack in turn.
Imitating Tagging: Circuit Killing Step
In the first pass of the imitating attack, the adversary performs an initial correlation of new circuits, and then kills the ones that don't correlate. So let's do the base rate analysis[1] for the correlation, shall we?
The probability that an arbitrary pair of circuit endpoints seen through the c/n colluding nodes belongs to the same circuit is equal to (c/n)^2 times the probability of picking an arbitrary matching pair of circuit endpoints out the network's 's' streams (1/s^2).
Pk(M) = (c/n)^2 * (1/s)^2
From my previous work in [1], we have the effect of the base rate on
this attack:
Pk(M|C) = Pk(C|M)*Pk(M)/(Pk(M)*Pk(C|M) + Pk(~M)*Pk(C|~M))
For every actual match, the adversary can expect to have 1/Pk(M|C) additional matches predicted by the correlater.
If you churn through some more analysis, you can see that the probability Pk(~M|~C) of correctly killing non-matching circuits is pretty high (but is still a function of c/n). In other words, the adversary is pretty sure that the circuits he does kill are irrelevant. Since everyone around here likes to assume the correlating adversary is all-powerful, we doubt we need to show their strength in this avenue. Let's just assume Pk(~M|~C) = 1, and no true matches are killed early.
Now for the numbers. Being a Raccoon, I am limited by the precision of my trusty rusty squirrel-skull abacus[7], so I'll give the imitating adversary several benefits of the doubt here to keep the math more simple. You can re-calculate at home on a high precision calculator without these assumptions if you like.
First, let's just assume for the ease of analysis that the imitating adversary gets to behave globally in the first step and set c=n for it (relax Paul, this assumption is in your favor). After all, maybe the NSA has some tricks up their sleeve with respect to global timing analysis that we don't know about. If we don't give the imitating adversary this bonus, the base rate just gets too small to manage and crypto-tagging wins by a landslide because of its free "half-duplex global" property. It would take all of the excitement right out of our proof!
Pk(M) = (n/n)^2 * (1/s)^2 = 1/s^2
To toss the imitating adversary another bone (since they keep falling off of my abacus anyway), and because a 0.0006 false positive rate "is just a non-issue"[8], we'll give those chumps an extra 0. They deserve it, they need it, and we're feeling generous. Hey, maybe they even can successfully encode some timing information between the first two cells on a circuit.
Pk(C|~M) = 0.00006 Pk(C|M) = 0.99994 = 99.994%
As if that weren't enough, we'll *still* use only s=5000 concurrent streams, even though over the past 4 years of network growth, that is now an absurdly low number.
Pk(M) = (1/5000)^2 = 4*10^-8
Plugging everything in:
Pk(M|C) = 0.99994*4*10^-8/(0.99994*4*10^-8 + (1-4*10^-8)*0.00006)) Pk(M|C) = 0.000666
1/Pk(M|C) => 1501 extra circuits survive for every true match.
The imitating adversary sure seems to be carrying a lot of extra traffic at this point (roughly 1501 times as much as he wants), even though we made three seriously large (to the point of being erroneous) assumptions in his favor. Stay tuned for the exciting conclusion to see what he'll do with it.
Imitating Tagging: Active Timing Attack Step (at 100% accuracy)
After filtering, the imitating adversary then moves on to use an active timing attack to determine the true matches. Let's walk through the base rate analysis to see what they will look like.
The probability of picking an arbitrary, random endpoint match is proportional to the number of remaining endpoints, which should trend towards the fraction of the colluding capacity times the number of total endpoints:
Pi(M) ~= O((c/n) * (1/s^2))
Technically, there is a correction we need to do for the increased prior probability of matches being present due to the filtering step above, but we're going to ignore that for now, because we'll just give the adversary 100% accuracy for this stage. We do not believe a 0-error active timing attack would survive analysis (see the Future Work section), but Paul was quite insistent, and it also simplifies analysis.
So here you go, Paul:
Pi(C|M) = 1 Pi(C|~M) = 0 Pi(M|C) = 1*Pi(M)/(Pi(M) + 0*(1-Pi(M)) Pi(M|c) = 1
With this level of accuracy, Pi(M) is irrelevant. The base rate loses this one (but only because the error rate is contrived).
Now, how many of the network's total circuits does the adversary actually compromise? Well, the adversary is carrying c/n of the network traffic, but only Pk(M|C) of those circuits are actually valid candidates for matching.
Of those, Pi(M|C) are discovered by the active timing attack (all of them).
Pi(compromise) = c/n * Pk(M|C) * Pi(M|C) Pi(compromise) = c/n * 0.000666
Ok, not bad. The imitating adversary seems to beat the expected O((c/n)^2) for end to end 0-error attacks for some values of c. So it might be a good idea. Sometimes.
Let's check in with our crypto-tagger and see how he's doing.
Full Analysis of the Crypto-Tagging Attack
The most direct and intuitive route to calculate the base rate Pc(M) for the crypto-tagger is through the observation that the "half-duplex global" adversary is killing all traffic such that the all of the 's' streams that flow through the adversary's nodes are fully compromised.
Pc(M) = (1 / ((c/n)*s))^2 Pc(M) = (n/c)^2 * (1/s)^2
Ugly looking base rate, but it doesn't matter, because the crypto-tagger can in fact encode arbitrary bit strings in his tags without even resorting to timing. Bit string encoding was not actually discussed in [5], but our crack research team of 23 Raccoons doesn't see why it isn't possible.
Therefore, the crypto-tagger's Pc(M|C) ends up 1.0. But unlike the imitating tagger, the crypto-tagger doesn't need any gifts from Raccoons to achieve his success rate.
Pc(C|M) = 1 Pc(C|~M) = 0 Pc(M|C) = 1*Pc(M)/(1*Pc(M) + 0*(1-Pc(M)) Pc(M|C) = 1
To calculate the probability of compromise of an arbitrary circuit chosen from the entire network, we need to get a measure on the number of circuits that flow through the adversary's nodes.
The most direct and intuitive way to calculate this probability is to realize that the "half-duplex global" adversary created by the crypto-tag ensures that all of the c/n network capacity deployed by the attacker carries only fully compromised circuits. Therefore, the attacker can expect to compromise c/n of the circuits on the network.
The probability of compromise network-wide is then:
Pc(compromise) = Pc(M|C) * c/n Pc(compromise) = c/n
In other words, the attack expects to compromise (c/n)*s of the network's total concurrent streams. So much for O((c/n)^2).
If even just one of the major exit relays became compromised or coerced to implement a crypto-tagging attack (or hey, just did it for the lullz!), the consequences would be devastating, and invisible to users.
Crypto-Tagger vs Imitating Tagger
Let's compare the two probabilities of compromise:
Pi(compromise) = Pc(compromise)*Pk(M|C) Pc(compromise) = Pi(compromise)/Pk(M|C) Pc(compromise) = Pi(compromise)*1501
So even with a 100% accurate active timing attack and several very liberal assumptions in favor of the imitating adversary, the crypto-tagger compromises 1501 *times* as many circuits with the same attack capacity. That's some nice amplification.
Moreover, the crypto-tagger has a compromise rate of c/n, which obliterates the O((c/n)^2) expected compromise rate that c/n-carrying adversaries are supposed to be capable of compromising.
Sounds like it's time to swap out AES-CTR in favor of a self-authenticating cipher[9] amirite??. OCB mode, anyone?
Future work
We can further elaborate the above analysis to take in more realistic error rates for active timing attacks. Such an exercise might be instructive, but we believe it is not necessary to properly evaluate imitating tagging versus crypto-tagging. It will only make the imitating tagger look worse, and everybody should realize by now he's just a poser anyway.
----------------------------- 0. https://en.wikipedia.org/wiki/Baylisascaris_procyonis 1. http://archives.seul.org/or/dev/Sep-2008/msg00016.html 2. https://conspicuouschatter.wordpress.com/2008/09/30/the-base-rate-fallacy-an... 3. http://www.cl.cam.ac.uk/~sjm217/papers/pet07ixanalysis.pdf 4. https://lists.torproject.org/pipermail/tor-talk/2012-March/023592.html 5. http://www.cs.uml.edu/~xinwenfu/paper/ICC08_Fu.pdf 6. https://www.eff.org/pages/tor-and-https 7. http://www.youtube.com/watch?v=ERwqbdAIY04 8. https://blog.torproject.org/blog/one-cell-enough 9. https://en.wikipedia.org/wiki/Authenticated_encryption 10. Look, I used more citations this time!
On 2012-03-11, The23rd Raccoon the.raccoon23@gmail.com wrote:
The crypto-tagger achieves amplification by being destructive to a circuit if the tagged cell is not untagged by them at the exit of the network, and also by being destructive when a non-tagged cell is "untagged" on a circuit coming from a non-tagging entry. It transforms all non-colluding entrances and exits into a "half-duplex global" adversary that works for the tagger to ensure that all traffic that he carries goes only through his colluding nodes.
I wonder what the 'bandwidth authorities' would think of exits that close circuits which They don't control: https://gitweb.torproject.org/torflow.git/blob/HEAD:/NetworkScanners/BwAutho...
Sounds like it's time to swap out AES-CTR in favor of a self-authenticating cipher[9] amirite??. OCB mode, anyone?
OCB is patented, and also crap. http://cr.yp.to/papers.html#pema is the right way to get a MAC (see also http://cr.yp.to/papers.html#poly1305 and http://cr.yp.to/papers.html#aecycles).
But http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf and an end-to-end MAC is more likely as a solution to the end-to-end tagging attack, because (a) per-hop MACs would take up much more space in each cell and disclose the length of a circuit to the exit node, and (b) with per-hop MACs, if you can get a forgery accepted (which happens with probability 2^(-n), where n is the number of bits in the MAC, for any MAC that Tor could use), you know with probability 2^(-n) that the next hop is the last one.
(This sucks, because polynomial-evaluation MACs are faster and more fun than most hash functions that would be suitable for BEAR/LION/LIONESS.)
Robert Ransom
On Sun, Mar 11, 2012 at 8:32 PM, Robert Ransom rransom.8774@gmail.com wrote:
On 2012-03-11, The23rd Raccoon the.raccoon23@gmail.com wrote:
But http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf and an end-to-end MAC is more likely as a solution to the end-to-end tagging attack, because (a) per-hop MACs would take up much more space in each cell and disclose the length of a circuit to the exit node, and (b) with per-hop MACs, if you can get a forgery accepted (which happens with probability 2^(-n), where n is the number of bits in the MAC, for any MAC that Tor could use), you know with probability 2^(-n) that the next hop is the last one.
You are going to have to be careful and explain this to me. I get the leaking the length of a circuit and position in the chain. But we use length 3 circuits in the current client node all the time, and if you weren't the start or the end, you are the middle. The forgery acceptance probability for Poly1305 is 2^-128. Forgery is not going to happen.
I also don't see what Bear/Lionness gets us. It does solve problems with losing sync. It does so at a cost of determining when identical ORs are sent, which happens a lot: think multiple http requests. 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.
It's preeminently possible I am missing something.
(This sucks, because polynomial-evaluation MACs are faster and more fun than most hash functions that would be suitable for BEAR/LION/LIONESS.)
I concur: we do need to keep an eye on performance. Saturate commodity bandwidth with commodity hardware!
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 2012-03-12, Watson Ladd watsonbladd@gmail.com wrote:
On Sun, Mar 11, 2012 at 8:32 PM, Robert Ransom rransom.8774@gmail.com wrote:
But http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf and an end-to-end MAC is more likely as a solution to the end-to-end tagging attack, because (a) per-hop MACs would take up much more space in each cell and disclose the length of a circuit to the exit node, and (b) with per-hop MACs, if you can get a forgery accepted (which happens with probability 2^(-n), where n is the number of bits in the MAC, for any MAC that Tor could use), you know with probability 2^(-n) that the next hop is the last one.
You are going to have to be careful and explain this to me. I get the leaking the length of a circuit and position in the chain. But we use length 3 circuits in the current client node all the time, and if you weren't the start or the end, you are the middle. The forgery acceptance probability for Poly1305 is 2^-128. Forgery is not going to happen.
Non-truncated Poly1305 takes 16 bytes per relay, so it would eat up at least 48 bytes per 512-byte cell, and more on 4-hop circuits (which Tor clients do build fairly often) and hidden-service rendezvous circuits. Non-truncated Poly1305 is not going to happen.
I also don't see what Bear/Lionness gets us. It does solve problems with losing sync. It does so at a cost of determining when identical ORs are sent, which happens a lot: think multiple http requests.
What do you mean by "ORs"?
(The BEAR/LION key would likely be different for each cell that a relay processes.)
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).
Robert Ransom
On Sun, Mar 11, 2012 at 10:45 PM, Robert Ransom rransom.8774@gmail.com wrote:
On 2012-03-12, Watson Ladd watsonbladd@gmail.com wrote:
On Sun, Mar 11, 2012 at 8:32 PM, Robert Ransom rransom.8774@gmail.com wrote:
But http://www.cl.cam.ac.uk/~rja14/Papers/bear-lion.pdf and an end-to-end MAC is more likely as a solution to the end-to-end tagging attack, because (a) per-hop MACs would take up much more space in each cell and disclose the length of a circuit to the exit node, and (b) with per-hop MACs, if you can get a forgery accepted (which happens with probability 2^(-n), where n is the number of bits in the MAC, for any MAC that Tor could use), you know with probability 2^(-n) that the next hop is the last one.
You are going to have to be careful and explain this to me. I get the leaking the length of a circuit and position in the chain. But we use length 3 circuits in the current client node all the time, and if you weren't the start or the end, you are the middle. The forgery acceptance probability for Poly1305 is 2^-128. Forgery is not going to happen.
Non-truncated Poly1305 takes 16 bytes per relay, so it would eat up at least 48 bytes per 512-byte cell, and more on 4-hop circuits (which Tor clients do build fairly often) and hidden-service rendezvous circuits. Non-truncated Poly1305 is not going to happen.
I also don't see what Bear/Lionness gets us. It does solve problems with losing sync. It does so at a cost of determining when identical ORs are sent, which happens a lot: think multiple http requests.
What do you mean by "ORs"?
I ment cells: brain glitch.
(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.
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.
Robert Ransom _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
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.
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
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.
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
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
On Mon, 12 Mar 2012 09:40:18 -0500 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').
The most adequate solution described in:
"Duplexing the sponge: single-pass authenticated encryption and other applications" Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche
http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/DA...
This is a SHA-3 workshop finalist Keccak, a universal cryptoprimitive (not only hash) in special duplexing mode: stream encryption and authentication in one pass.
I hope NIST and cryptocommunity choose it as a new standard.
Thus spake Robert Ransom (rransom.8774@gmail.com):
On 2012-03-11, The23rd Raccoon the.raccoon23@gmail.com wrote:
The crypto-tagger achieves amplification by being destructive to a circuit if the tagged cell is not untagged by them at the exit of the network, and also by being destructive when a non-tagged cell is "untagged" on a circuit coming from a non-tagging entry. It transforms all non-colluding entrances and exits into a "half-duplex global" adversary that works for the tagger to ensure that all traffic that he carries goes only through his colluding nodes.
I wonder what the 'bandwidth authorities' would think of exits that close circuits which They don't control: https://gitweb.torproject.org/torflow.git/blob/HEAD:/NetworkScanners/BwAutho...
I've been worried about various types of path biasing/circuit failure attacks for a while, but sadly the the bandwidth authorities are not something that can be relied upon as the only thing to defend against them. The bandwidth authorities are not a security measure. It is possible to deceive them.
The only way for measurements to be resilient to deception is to deploy decentralized measurement such as Eigenspeed, but Eigenspeed's passive measurements are unable to properly measure high bandwidth relays, so someone needs to research decentralized active measurement and/or a hybrid solution of Eigenspeed and the bandwidth authorities, and figure out how to blend in circuit failure into the measurements, too.
I believe Nikita's group was the first to publish about path biasing in Tor through circuit failure (http://research.microsoft.com/~gdane/papers/ccs0255-borisov.pdf), and is also the source of the EigenSpeed work. I prod him every once and a while to try out his Eigenspeed as a defense against his path biasing attack, but haven't heard much about it.
That said, the bandwidth authorities will actually compensate for this attack if the bwauthcircs=1 consensus parameter is set. Right now, the parameter is not set, because it is part of the PID feedback experiment that is currently disabled. Circuit failure statistics are still being recorded for posterity though. There are some high capacity relays exhibiting high rates of circuit failure right now, but that could also be CPU overload.
I can turn the bwauthcircs=1 parameter back on independent of the PID feedback and see what happens, but if we could solve this with crypto, that would be better I think.
On Mon, Mar 12, 2012 at 5:38 PM, Mike Perry mikeperry@torproject.org wrote:
Thus spake Robert Ransom (rransom.8774@gmail.com):
On 2012-03-11, The23rd Raccoon the.raccoon23@gmail.com wrote:
The crypto-tagger achieves amplification by being destructive to a circuit if the tagged cell is not untagged by them at the exit of the network, and also by being destructive when a non-tagged cell is "untagged" on a circuit coming from a non-tagging entry. It transforms all non-colluding entrances and exits into a "half-duplex global" adversary that works for the tagger to ensure that all traffic that he carries goes only through his colluding nodes.
I wonder what the 'bandwidth authorities' would think of exits that close circuits which They don't control: https://gitweb.torproject.org/torflow.git/blob/HEAD:/NetworkScanners/BwAutho...
I've been worried about various types of path biasing/circuit failure attacks for a while
Sorry, but path biasing is also a different class of attack than tagging.
That said, the bandwidth authorities will actually compensate for this attack if the bwauthcircs=1 consensus parameter is set. Right now, the parameter is not set, because it is part of the PID feedback experiment that is currently disabled. Circuit failure statistics are still being recorded for posterity though. There are some high capacity relays exhibiting high rates of circuit failure right now, but that could also be CPU overload.
Here, let me help you out by scrawling some ascii-art drawings to calculate what constitutes excessive amounts of circuit failure. In the path biasing attack, we've got three nodes. Let's call the nodes A, B, and C. I'll label the links to the nodes 0, 1 and 2. Let's assume as usual that the adversary controls c/n of path selection. The < symbols indicate a node choice opportunity on the part of clients.
--- 0< --- A --- 1< --- B ---- 2< ---- C -------
Each point 0, 1, and 2 is a point where the adversary can alter your path choice. Let's just assume 0 is a safe route for now, and does not bias node selection.
If node A (or node A's ISP) is biasing choice of B on link 1, node A must fail 1 - c/n of the circuits that go through it in order to ensure that B is chosen from colluding nodes. It can only allow c/n of the circuits to get through to B (since B is represented by any of the adversary's c/n nodes).
Similarly, node B must fail an additional 1 - c/n of the circuits that attempt to extend through it. It too, can only allow c/n of the circuits to get through to C.
That means that the adversary has to fail 1 - (c/n)^2 of client circuits that attempt to use node A, and it's middle nodes B must fail 1 - c/n of clients circuits to ensure colluding node C is chosen. So node A has to fail a lot of circuits. Even for a c/n = 20% adversary, node A has to fail 96% of all circuits that attempt to use it.
However, in tagging, the adversary has a direct communication channel to node C via the tag.
----0< --- A ---- 1< ---- C -----
In this case (ignoring link 0), the adversary only has to close c/n of the circuits that attempt to use it, giving a total circuit failure rate of just 1 - c/n. For an adversary that controls 20% of the network, this means failing 80% of the circuits that attempt to use node A.
So, if you have a way to measure circuit failure reliably, you can in fact detect the tagging attack, up to a point. It will be significantly easier to detect full 3-hop path bias than 2. It would be a good idea to solve tagging for this reason.
I can turn the bwauthcircs=1 parameter back on independent of the PID feedback and see what happens, but if we could solve this with crypto, that would be better I think.
Is this even possible without revising the circuit level protocol? We looked through the spec and didn't see anything that allows the network to migrate to alternate cipher choices easily..
How quickly can the migration be done?
Otherwise, I suggest everybody start keeping track of their circuit failure rates though major nodes....
Thus spake The23rd Raccoon (the.raccoon23@gmail.com):
So, if you have a way to measure circuit failure reliably, you can in fact detect the tagging attack, up to a point. It will be significantly easier to detect full 3-hop path bias than 2. It would be a good idea to solve tagging for this reason.
Ok, I've filed parent ticket https://trac.torproject.org/projects/tor/ticket/5456 for dealing with all of this mess.
I can turn the bwauthcircs=1 parameter back on independent of the PID feedback and see what happens, but if we could solve this with crypto, that would be better I think.
Turns out I was wrong here. There's a bug in the bwauths that prevent us from doing this properly right now: https://trac.torproject.org/projects/tor/ticket/5457
Turtles all the way down...
Is this even possible without revising the circuit level protocol? We looked through the spec and didn't see anything that allows the network to migrate to alternate cipher choices easily..
How quickly can the migration be done?
Pretty slowly, it turns out. We're going to need a new circuit protocol and we need to decide if we want to do per-hop MACs or use self-authenticating ciphers. I created a child ticket for the proposals that will help us figure this out.
https://trac.torproject.org/projects/tor/ticket/5460 if you're interested in following them.
Otherwise, I suggest everybody start keeping track of their circuit failure rates though major nodes....
I created a child ticket for this, too: https://trac.torproject.org/projects/tor/ticket/5458
I also created https://trac.torproject.org/projects/tor/ticket/5459 for building a network scanner to detect this collusion.
It's going to be a long while before all of this stuff gets done though, I bet. We're waaay overloaded here, development wise. We can barely keep up with our Sponsor workload, let alone fix surprise monstrous issues like this one. We'd love the help!
But still, thanks for taking the time to report this (and also for providing the proofs!).
On Sun, Mar 11, 2012 at 10:28:04PM +0000, The23rd Raccoon wrote:
Analysis of the Relative Severity of Tagging Attacks: Hey hey, ho ho! AES-CTR mode has got to go! A cypherpunk riot brought to you by: The 23 RaccoonsAbstract
Gather round the dumpster, humans. It's time for your Raccoon overlords to take you to school again.
Watch your step though: You don't want to catch any brain parasites[0].
Introduction
For those of you who do not remember me from last time, about 4 years ago I demonstrated the effect that the Base Rate Fallacy has on timing attacks[1]. While no one has disputed the math, the applicability of my analysis to modern classifiers was questioned by George Danezis [2] and others. However, a close look at figure 5(a) of [3] shows it to be empirically correct[4].
Recently, Paul Syverson and I got into a disagreement over the effectiveness of crypto-tagging attacks such as [5].
I just wanted to let you know that I'm neither ignoring nor forgetting about this thread and its ilk, just insanely busy with other things. It's now clear that I'm unlikely to pick up thinking about this topic again until c. mid-May. Sorry for any inconvenience/annoyance my dropping out of and into the discussion may cause.
aloha, Paul
-
Mike Perry -
Paul Syverson -
Robert Ransom -
The23rd Raccoon -
unknown -
Watson Ladd