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!