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
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.
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
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?
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?
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!
mouth < foot
A SQL varient of this is far more effective:
insert into mouth values ('foot')
Maw! Fire up the karma burner!
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.
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.
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.
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
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.
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?
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 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.
Heh, everyone hold on, it's been a few years since the crypto class in college:
RSA is based on modular arithmetic. This is nasty stuff: it's not unbreakable, but so difficult to reverse that it's not practical to do so. Basically, when my client sends a request to start a SSL session to a server, I send a number g. The server and client use that number to create a shared key that they use to encrypt their messages.
Here's the fun part: the server can only unlock the shared messages using its private key. When I send it an encrypted message, it takes the server a certain amount of time to try and unlock it. If the number g I used to encrypt the message is close to the number that is the server's private key, it takes noticably less time for the server to respond with "good message" or "bad message". So by sending millions of queries, I can narrow in on the private key just by timing how long it takes the server to answer me.
Note it doesn't help me read messages, only to get the private key. Of course, once I have that key, I can read anything the server receives - like credit card numbers, email addresses, etc.
I've probably confused a few details - someone with more recent experience here feel free to correct 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 :).
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.