Slashdot Mirror
Remote RSA Timing Attacks Practical
David Brumley and Dan Boneh writes "Timing attacks are usually used to attack weak computing devices such as smartcards. We show that timing attacks apply to general software systems. Specifically, we devise a timing attack against OpenSSL. Our experiments show that we can extract private keys from a OpenSSL-based server such as Apache with mod_SSL and stunnel running on a machine in the local network. Our results demonstrate that timing attacks against widely deployed network servers are practical. Subsequently, software should implement defenses against timing attacks. Our paper can be found at Stanford's
Applied Crypto Group."
OK, so we know now that SSL servers may be vulerable. Can this sort of an attack be used against personal encryption, a la pgp?
Great, and this after I've been bragging about my 'not-breakable for a billion years' 2048-bit key.
$mouth . $foot
--Bennett Prescott
Former Lord Of Packets
Pity this didn't appear BEFORE the Paul Kocher post.
The simple truth is that interstellar distances will not fit into the human imagination
- Douglas Adams
Is one smart cookie. He's also the only prof I wouldn't take a class from because it wasn't webcast. In other words you can't pause and rewind his live lectures. He talks real fast. And tilts his head at a 30 degree angle to his left.
According to this kiddy looking article, I don't think you're vulnerable if you have caching off.
Hacking the Network
That summary is so buzzword-rich I feel compelled to purchase a product, if one were offered.
The article says that they "can extract private keys from an OpenSSL-based web server". That doesn't sound like a compromise to the RSA algorithm. They just got the private key.
-phish
Is there an english translation of this anywhere? I read the paper and there's lots of impressive looking formula's and stuff in there but I don't see how figuring out how long it takes to decrypt/encrypt something can tell you what it is. Doesn't make sense to me.
just randomize the timing in every reply... a few NOOPs?
or am i missing something?
it would seem to me that the encryption/ decryption process has no self-awareness of what is a short and long time to reply. therefore, maybe you need another process to watch the time it takes to reply. it could average it over time and provide some sort of super-lengthening of the time it takes to reply so that long replies can be made to look shorter than an artifically lengthened short reply?
because if you just lengthen the short replies, doesn't that still reveal something since a really long reply will still show a spike?
if replies happen on the order of 5-50 nanoseconds naturally (hypothetically speaking), and you lengthen the short replies so that the range becomes something like 35-50 nanoseconds, then that could still reveal something.
so what is needed is maybe a superlengthening of replies so that 5-50 nanoseconds becomes 100-200 nanoseconds? only that way could you hide the difference between a 5 nanosecond and a 50 nanosecond reply completely, no?
doesn't this have implications though on overall speed? or are the times still so tiny it really doesn't matter?
intellectual property law is philosophically incoherent. it is your moral duty to ignore it or sabotage it
These timing attacks are very different from those executed against an embedded device, such as a smart chip, in that the attack against the smart chip aims to disrupt the device and cause it to skip one or more instructions in order to breach the security. These attacks instead use timing attacks as an oracle which allows the malicious hacker to make thousands of guesses against the insecure server, knowing that the timing of the response will eventually give away the key. For instance, by sending a specially crafted packet to one of these vulnerable SSL servers, one will be able to deduce from the timing whether a given bit in the private key is a 0 or a 1, simply by looking at how much time it takes to respond (on the average, for that particular crafted input). You can see how this could be a bad thing.
Although this could be a very nasty threat today for machines within a small, predictable network distance from the attacker, there is hope. In the 2.5 kernel, developers have begun adding features that randomize round trip latency for packet reponses. This means that these systems will not serve as good oracles for an active attacker because the timings generated by the randomization feature will not approximate an even (normal) distribution. This means that even by averaging them out, it will not be possible to determine from the timing of a cryptographic response whether (say) the bit is a zero or a one.
This vulnerablility has actually been discussed as a possiblility for the past few years (mostly within the CERT "members only" club) but it was not until recently that a practical exploit was published. So if your keys were compromised before this went public, perhaps one of the blackhats figured the trick out first. :(
Wouldn't this type of attack be feasible on the Xbox instead of trying to factor the key? You even have access to the hardware so very precise timing could be done.
Just a thought.
It seems that this is severe when the attacker is very "close" in network terms to the server. It relies on the time difference when multiplying numbers in OpenSSL.
So, if you are "far" away from the SSL server, I suppose this attack isn't as "good".
All this talk about closeness and goodness really just means we're using smoke and mirrors.
OpenSSL needs to figure out how to be completely mundane with any input string from the client.
This sounds a lot like the weakness discovered last month by the LASEC folks in Switzerland ...
Why don't all the OpenSSL folks sue these guys under the DMCA? It's good enough for Adobe, it should be good enough for Open Source folks, right?
the bit about MS palladium being a security risk is very intersting also very ironic.
The war with islam is a war on the beast
The war on terror is a war for peace
my.domain.org daily insecurity output for Fri Feb 21 03:15:01 PST 2003
/etc/security.local:
Running
Package openssl-0.9.6g has a weak-encryption vulnerability, see http://www.openssl.org/news/secadv_20030219.txt
Awesome furniture, accessories and cabinetry in Santa Rosa, CA: http://humanity-home.com/
if it makes you feel better, the TLS standard was a mix of MS PCT and SSL :)
The war with islam is a war on the beast
The war on terror is a war for peace
According to the conclusion at the end of the article:
"We devised and implemented a timing attack against OpenSSL { a library commonly used in web
servers. Our experiments show that, counter to current belief, the timing attack is eective when
carried out between two machines in a local network. Similarly, the timing attack is eective
between two processes on the same machine and two Virtual Machines on the same computer. We
hope these results will convince designers of crypto libraries to implement defenses against timing
attacks as described in the previous section."
So it looks like it is only useful against machines on the local network, which means you would have to have a comprimised machine on the network to launch the attack from. Possible yes, but it's not has simple has querying a remote system over the internet (I would assume that the unknown latency would render a timing attack useless, but couldn't use you use a traceroute to determine the latency and compinsate? Just a thought..) Anyway, I don't expect there to be 1,000s of comprimised servers by tommorow...
I am aware that there is currently an effort to find the private key for the xbox. When I saw this headline I immediately wondered if the xbox is vulnerable. I assume it is not because it is only doing client encryption?
I thought they were talking about things like DDOS attacks and what not.
If they were, I was going to say, that slashdot is THE most effective time attack ever. The time between a posting on slashdot and the webserver the story is on going down... remarkible..
IANACE (crypo expert)
The attack works by measuring the time it takes for an SSL server to encrypt things. By causing the SSL server to do lots of encrypting of known things, you can derive a private key. Apparently, this must be repeated many times and is highly dependent on timing. Thus, it's not fast and network latency, high server load, etc. will reduce the effectiveness of the attack. Further, subtle environment differences prevent an obvious "script kiddy" level implementation of this attack. A relevant quote from the paper:
As we will see, the performance of our attack varies with the exact environment in which it is applied. Even the exact compiler optimizations used to compile OpenSSL can make a big difference.
A solution to this might be to implement a small random delay before the server returns cyphertext to the client, no? A few extra milliseconds here and there would probably be sufficient.
Maw! Fire up the karma burner!
This is a case of being able to closely inspect the details of a system, and finding a way to penetrate it.
It's no coincidence these tests werent done with MSFT products.
Happy Hacking, everybody! The end of Open Source!
but it looks like you're appending your foot to your mouth. If you want to put your foot in your mouth, I'd try something like $mouth = 'foot' or something. Thanks.
That reads like The Hobbit!
um, that really wasn't funny.
$x='S24;r)>63/* h@<5+oZ)32"5cz';$me='phroggy'x$];
$x=~y+ -xz+\0-Tx+;print$_^chop$me for split'',$x;
Is there even a reason to be concerned with this when ROT-13+ is perfectly secure? It was recently expanded from regular ROT-13 so it doesn't only encrypt letters, so it should be good enough for any application.
In the long run, we're all dead.
It's going to take a lot of time for a 1024-bit key, and it seems to me such an attack should be easily noticed, and even then the timing dependency should make this attack impossible to pull off in the real world unless you're sitting right next to the target box.
Why is this a 5?
The article provides FAR superior timing masking ideas.
Of course, it would be asking alot to read the article first
Just use the damn crap, and pretty soon someone somewhere will send you multiple proofs of the insecurity of your system...
GW Bush is trolling /.?
Being further from the server will add noise, but they already compensate for noise by averaging 7 samples (5 would have been sufficient for local use). Over a remote network, you take more samples. (perhaps quite a few)
It currently takes 2 hours to crack a server.
If you have a week or so of time on your hands, a realtively unused server (not mail.bigisp.com but admin.bigisp.com), and the asministrator doesn't notice the traffic spike, quite a few sites could be vulnerable.
Remember, people get upset when crypto can be cracked in terms of *years* and *dollars*. This can crack things in HOURS on a fast pc.
vag
znva(vag netp, pune* neti[])
{
pbafg pune* cge;
pune ohs[OHS_FVMR];
juvyr (!srbs(fgqva))
{
vag yra = sernq(ohs, 1, fvmrbs(ohs), fgqva);
sbe (cge = ohs; cge < ohs + yra; ++cge) {
*cge = EBG13(*cge);
}
sjevgr(ohs, 1, yra, fgqbhg);
}
erghea 0;
}
Timing attacks are completely unrelated -- they are a result of code running predictably enough that the timing of a response leaks information. They are not a general security breach -- this is an isolated case where a large number of requests to a modSSL server could leak the server's private key -- but nothing else.
TANSTAAFI: There Ain't No Such Thing As A Free iPod.
David Brumley and Dan Boneh writes "Timing attacks are usually used to attack civilians buildings such as WTC. We show that timing attacks apply to several towers. Specifically, we devise a timing attack against USA. Our experiments show that we can collapse WTC from a pathetic weapon such as two planes with only 4 terrorists inside. Our results demonstrate that timing attacks against big towers are practical. Subsequently, infidels should implement defenses against timing attacks. Our paper can be found at Al Quada's Applied Crypto Group."
Since it came out in 2000, have modern browsers fixed the cache cookie problem? (Besides refusing cookies?)
If we were ants living on a Rubik's cube, differential geometry would be a little more confusing.
The exploit behind this is actually not that complicated, if you know RSA. In RSA, you have these formulas:
C=M^e mod n (encryption/signature verification)
M=C^d mod n (decryption/signing)
When OpenSSL wants to sign a message C, it needs to produce the signature M using the "M=C^d mod n" formula above. Calculating this is simple in idea: calculate C to the d'th power modulo n. However, d is a very big number; on average, it is n/2. There is no way you can calculate C^d mod n by multiplying C with itself many times.
The answer to this is to use a "repeated squaring" algorithm. Let's say that d=17, and you want to calculate C^d. Multiplying C 17 times works, but is very slow. It is possible to calculate C^17 using the following formula:
C^17 = C * C^16
C^17 = C * (((C^2)^2)^2)^2
Now, there are only 5 multiplies: 4 squares and one multiply with C. There is a pattern to when you square and when you multiply. The number 17 is 10001 in binary. The binary digits tell you when to square and when to multiply.
You start with the number 1, and go through the bits in 10001 from left to right. For each bit, either 0 or 1, you square. But if a bit is a 1, you also multiply. This means that the first step (a 1 bit), you square, then multiply by C. Since you started out with 1, you get C here. For the next 3 bits, all 0's, you square, getting C^8 as your result. The last bit is a 1. You square, getting C^16, then multiply by C again, since it's a 1 bit. This gets you C^17.
The problem here is that "1" bits require a different amount of work than "0" bits. When you have a "1" bit, you have to perform an additional multiply than for a "0" bit. If you can somehow time each multiplication/square step, you can determine whether the bit of "d" was a 0 or 1. If you can do this 2048 times, you can calculate all the bits of the private key, which is "d". That is what this attack does, minus all the complicated details.
This RSA hole can only possibly be exploited when the attacker has physical access to the device (as in a smart card attack), or the owner of the private key automatically signs/decrypts messages sent from a client (as in OpenSSL). Manual encryption systems, such as those used for email, can't be exploited this way realistically.
Myria ^-^ *hugs*
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
Busy sites will have variable server load for the attacker to cope with. It's more than just network latency you have to factor out.
:)
I wonder to what degree not knowing the precise parameters of the SSL server would complicate things. If, for instance, you don't know whether the server is a SPARC, Intel or some form or dedicated hardware. Each combination of software and hardware would have wildly different behavior relative to the very precise measurements required.
Also, by it's nature, this attack probably can't be used to implement a general purpose worm. So to be safe you'll need a lot of hosts in different locales at your disposal. If you spend too much time cracking remote hosts from a single site you will get found.
Finally, once you have a private key, you also need access to the traffic between the compromised server and whomever is trusting it. Without this it's not much good. Once you have managed to reliably tap that traffic, what then would you do with it? It's not a cash machine that starts pumping out money on command. Passively sniff collecting credit card numbers to sell off? Rouge employees do that all the time anyhow. Implement a man-in-the-middle somehow?
A concerted effort against a specific target could result in some successful theft of something. As we all know, however, there are many ways to attack a system when one has focus.
As vulnerabilities go, I don't think it rates very high. I'll bet 99% of the SSL servers and other encryption endpoints in the world will be made secure against this in the course of regular upgrades before an actual attack results in any real consequence.
But, then again, IANACE.
Maw! Fire up the karma burner!
I believe Paul Kocher first proposed (this is PDF) this attack way, way back in 1995, and as I recall, he even applied it to networked systems. RSA Labs' BSAFE, since version 3.0 has included a "blinding factor" in its RSA implementation that renders this attack ineffective. Reading the original RSA Labs bulletin (also PDF) on this attack shows a very simple fix, and I'm surprised that this hasn't made its way into OpenSSL! Ron Rivest proposed this back in early 1996. What's up?
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
tr A-Za-z N-ZA-Mn-za-m
You assume that:
1) Harvard thinks it's a bad thing to have pretentious, exclusionary alums.
2) That this attitude isn't inculcated in those who attend Harvard.
I've attended an Ivy (Brown, not Harvard) and the reality is they get off on the "we're better than everyone else" bit. It's about money and power -- something abundant in much of the student and alumni populace at Ivies.
This is not to say everyone at Harvard is like that (or any other top-notch school...) I've got friends from Harvard who aren't. But a lot of Harvard alums are. Same goes for any prestigious institution.
The paper mentions that things like palladium may also have this kind of problem (unless they implement timing protections of some sort), which leads me to believe the 2048-bit X-Box key could also be attacked this way, and probably much faster since you might be able to attack it right on the box without going over a network.
But I could be wrong.
Phil
You'd need to know something about how the latency varies. It's not constant. It's got a probability distribution over some range. (it's bounded below, and probably above too...)
Problem is, if that probability distribution is random, or "near" random, you're going to have a bitch of a time extracting enough info to perform an attack of this sort. This is why you need to be close; it's not because there's low latency (that helps) but because the latency has low variation, which means you can assume a value for it and subtract that out. With a random distribution, your "signal" will be lost in the noise.
It's another example of an attack being not quite as practical as advertised to the public. There's a real threat here, but it's not the "ultimate 'sploit".
you know how people use DES 3 times and called it 3DES? Why not use ROT-13+ 3 times and call it 3ROT-13?
ROT-n is a closed associative binary operation. That is, two composed ROT-i and ROT-j make a ROT-k. This is not true of DES, which is why DES E(i) D(j) E(i) provides 112 bits of effective key length.
Will I retire or break 10K?
Just Great... We need a ROT-13 enabled gcc so we can ROT-26 our code.
Funny, cuz I read:
Da Boner
As in, the boner is one smart cookie... and he tilts his head at 30 degree angle to left.
And I say, damn he needs to get some air then. Let 'em boys out!
THIS THING CAN TURN ON A DIME, MACROSSZERO STYLE ALSO FUCK BETA, ~NYORON
Thanks! My fantasy world is consistent again.
Congratulations, you've found a reference to a completely different attack.
This is a relatively well known type of attack. You ask a private key holder to decrypt a bunch of things and ask it how long it took. To defend against these types of attacks, the private key holder can either a) decrypt only a few things for you (which is a bit anti-social if you're an SSL engine.) or b) lie to you about how long it took to decrypt the things you sent.
The second option is effectively what happens when blinding is turned on.
nt
Everybody's suggestion seems to be to add a random delay to responses.
Why ?
Why not make the response time fixed ? Like in the biggest possible response time. If every query was responded in x ms, NO info would be leaking to the attacker. Or am I missing something ?
Alternatively, add your random padding to the constant, not to the time required to do the calculation. That has the advantage of giving DISinformation to the attacker. And there is a certain charm to that, don't you think?
[100% ISO 646 Compliant]
SVM, ERGO MONSTRO.
fixed or random delays work find - as long as you don't leak info about the key. this is mentioned in the paper.
the attack is a nice proof-of-concept, but almost totally impractical. notice that their "lan" was a completely private switch, with just the attack and target machines on it. if your lan is anything like mine, there's huge variance that will defeat the attack. not to mention that any other activity on the target machine will make the attack harder, or any kind of traffic shaping (they were doing 140 probes per second). not to mention simply turning on blinding.
it's great to see this vuln demonstrated in the lab, but really no need to worry about it.
All you fools who use OpenSSL, this thing cannot touch my 1337 telnet servers.
Behold my 31337 ROT-26 encryption method:
David Brumley and Dan Boneh writes "Timing attacks are usually used to attack civilians buildings such as WTC. We show that timing attacks apply to several towers. Specifically, we devise a timing attack against USA. Our experiments show that we can collapse WTC from a pathetic weapon such as two planes with only 4 terrorists inside. Our results demonstrate that timing attacks against big towers are practical. Subsequently, infidels should implement defenses against timing attacks. Our paper can be found at Al Quada's Applied Crypto Group."
Do you or your partner snore? - Visit www.snoring.com.au
All the OpenSSL developers need to do is check between each calculation, and wait until a slashdot article is moderated at "insightful"....NOT :-D
("funny", now, would operate like a geiger counter somewhere in the western region of the former U.S.S.R...and would probably overload the servers of the world; there would quite simply be no delays in any SSL engine on the planet.)
Not that I'm trying to add to the noise, mind you...
Redundancy is good; triple redundancy is twice as good! - Me.
Not breakable for a billion years? Assuming that a typical modern computer could check at least 1000 keys per second, and that Moore's law continues and computing power keeps doubling every 18 months, then it would "only" take 3057 years until a typical computer was capable of checking all possible 2048 bit keys in 1 second. Sure, that's a long time, but hardly a billion years :).
All they have to do is to take more samples to smooth out the random noise you get in practice. In the test environment they managed to crack the key in 2 hours. If they take 100 times as many samples, the attack takes 8 days 8 hours. Some of the bits they get may still be erroneous, but even if there are a dozen bits they got wrong, they can then fix them through brute force during the rest of the 8th day, and then break into the machine on the 9th day. All they need now is a machine where the sysadmins don't look at the logs too often...
Again, this shows how important it is to use separate key pairs for different jobs.
Imagine you use the same private key for both vulnerable SSL servers, and for offline protocols, such as PGP or S/MIME. Whoever successfully attacks your interactive SSL server would be capable of reading encrypted mail sent to you in the past.
I thought this was funny; no more slashdot humor for you!
For Each foot In mouth
MsgBox "Oh Shiiiiiit!"
Next foot
Nevertheless, it would be better to rewrite the concealed operation so that its running time didn't reveal sensitive information. Having to use delaying tactics imposes a significant response-time penalty, which can be a problem where low latency is desired. But it's nice to know that these concealment techniques are available when it's not possible to change the concealed operation (e.g., when the operation is part of a closed-source library).
Easy, automatic testing for Perl.
Yes. You simply have to setup some hardware to monitor the amount of time the encryption hardware spends verifying the discs. Then, you try to reverse engineer the particular algorithms they use in the hardware. This isn't as bad as it seems: there's only a finite number of known ways to accomplish something like RSA (or ElGamal, or AES (but I don't think the Xbox uses AES)). This paper might serve as a guide, but you'd likely have to perform simmilar analysis to what the paper's authors did.
Once you did it though, I expect that you could have the key in a day or two. Once again, we are taught that the weakness isn't in the math, it's in the implementation.
Yes, I'm still a junky. Are you still a bitch?
The recent SSL timing attacks I've seen have had their fixes be of the sort "Make the failure scenario take the same amount of time as the success scenario", which essentially causes certain paths to waste compute cycles purposely and unnecessarily. By gathering the max possible invocation time, opeenssl could just grab the time at invocation, then call usleep up till its max. This offers distinct overall advantages over the lengtening in that it causes the implementation to use processing resources much more efficiently (the scheduler will run other jobs while openssl sleeps), and also gives coders the freedom to implement the application in an optimal manner and still reap the benefits. Besides, users can't really tell the difference between 30ms and 70ms anyhow :)
.. that the logs on the target machines neither exist nor ever audited. And as with any probing method, the vulnerbility can very simply be fighted by rating incoming connections. Let the OpenSSL do its job efficiently, and guard against logistics of the vulnerability instead.
3.243F6A8885A308D313
In general, since X-boxes do not have the private key, the private key cannot be found given unrestricted access to X-boxes unless RSA is broken.
Sure it can, but not with a timing attack of course. Just nit picking.
Public key is essentially a pair of e and (p*q), where e - some number, p and q - primes. And the private key is an inverse of e by modulo (p-1)*(q-1). Thus factoring public key gives you private one.
3.243F6A8885A308D313
Forgot to read the context of the thread as usual :)
3.243F6A8885A308D313