[tor-dev] Analysis of the Relative Severity of Tagging Attacks
The23rd Raccoon
the.raccoon23 at gmail.com
Sun Mar 11 22:28:04 UTC 2012
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-and-the-traffic-analysis-of-tor/
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!
More information about the tor-dev
mailing list