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."
Well, according to the article:
"Many crypto libraries completely ignore the timing attack and have no defenses implemented to
prevent it. For example, libgcrypt [6] (used in GNUTLS and GPG) and Cryptlib [7] do not defend
against timing attacks."
So I would say yes it is (If you consider GPG the same has PGP that is)
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. :(
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 ...
No. According to the article, "Timing attacks enable an attacker to extract secrets maintained in a security system by observing the time it takes the system to respond to various queries." Once you choose to encrypt and send a message with GPG/PGP, it is done, and that is that. Aide from the conversation your computer makes with the SMTP server, there is no further communication between hosts, so there is no way somebody could try to measure the time it takes to generate an encrypted reply to something.
;-)
Therefore, as long as your computer isn't comprimised, you're fine. However, if your computer is comprimised, well, you've got bigger things to worry about than somebody trying to time how long it takes to encrypt a message.
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 should clarify though that it would only be possible if someone was on your system WHILE you were encrypting something or decrypting something that was encrypted with your key. It isn't /possible/ to execute this attack AFTER something is encrypted, only during the encrypting process.
Someone tell me if I'm wrong...I might be, but I don't think I am...
It's called RSA Blinding which pads the computation by some random timings. Implementations vary but typical performance overhead is 2-10%.
Someone you trust is one of us.
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.
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
Theoretically possible. But they'd have to get you to encrypt arbitrary chosen-plaintext, and a lot of it, to check the timings. It's probably easier just to root the box and steal your password with a keyboard sniffer.
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?
Actually, if you look at the Cryptonomicon.Net article about this attack, you can see that, in fact, blinding has been added to the OpenSSL code. The issue is whether or not it is turned on by developers.
It takes 2 hours in the real world. If you log connections, you'll see it there. But do you watch your logs that closely? One funny defense to try is to run OpenSSL w/ logging to a full disk. The full disk breaks the timing attack as the OS valiantly and unsuccessfully tries to find free blocks to record the SSL error message.
I saw Boneh give a talk on this a few days ago. One machine, over a LAN, can do it in two hours. Sure, that can be noticed if you know to look for lots of aborted SSL sessions, but if you don't have this on an IDS or something like that, someone can Nimda your secretary's box and still get your private key before your sysadmin gets back from the weekly staff meeting.
WARNING: there is a trojan on your
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.
No, they'd have to get you to decrypt chosen ciphertext (but they don't need the result of the decryption, just the timing). PGP uses public-key cryptography, so anyone can encrypt chosen plaintext.
Having a fixed "response time" would be appropriate. But it seems simpler to add a random delay before replying than it is it determine the elapsed time and then compensate with a difference delay.
In other words:
x = time to process
random delay:
response time = x + Rand(y)
fixed delay:
response time = x + (FixedTime - x)
The other problem with a Biggest Possible Fixed Time is performance. Encryption already causes overhead; maximizing overhead on remote network connections is not generally viewed as a Good Thing (TM). Plus you have to figure out what the Biggest Possible delay is, and that just sounds like homework (yuch!).
The idea is that bad code will do something like:
if (bit[i] != key[i]) return FALSE;
By timing this accurately, you'll know what (approximately) bit failed. Once fixed, and everyone agrees the fix is trivial, your code will look something like:
if (bit[i] != key[i]) bad_bit = 1;
else good_bit = 1;
[...]
if (bad_bit) return FALSE;
As you can see the computer has to do exactly the same work for a good or a bad bit. Thus the timing should be identical.
It's VERY VERY hard to mask these timing issues by "random" delays. Worst case, the attacker guesses your random numbers. Best case, the attacker will have to run his attack a couple more times to get the same results through the noise.
Cryptographers have known about this for years. In fact, this (kind of) attack was posted on slashdot no more than a week ago.
Roger.
Microsoft's private key isn't on the X-box, but rather their public key is. This is because the public key is what the box needs to verify that a game is signed by Microsoft. It certainly does not need the private key. Hence, there is no private key on the box to extract.
X-box security is actually extremely different from Palladium. For Palladium, it is inherently necessary to have a private key (that is, a private key inaccessible to the end user) with every computer, so that computers can authenticate the trusted kernel (aka Nexus) that they are running to third parties. If they use an RSA implementation vulnerable to a timing-based attack, a local user could easily perform such an attack, extract the key, and forge any desired authentication.