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?
That summary is so buzzword-rich I feel compelled to purchase a product, if one were offered.
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.
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?
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.
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
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.