Remote RSA Timing Attacks Practical 230
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."
Personal crypto? (Score:5, Interesting)
Re:Personal crypto? (Score:4, Funny)
Re:Personal crypto? (Score:2, Informative)
"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)
Re:Personal crypto? (Score:5, Informative)
Someone tell me if I'm wrong...I might be, but I don't think I am...
Re:Personal crypto? (Score:2, Funny)
Someone tell me if I'm wrong...I might be, but I don't think I am...
You shouldn't worry. Oh yea, and can you send that last email again please? I had to reboot and missed it.......
Re:Personal crypto? (Score:3, Funny)
Damn Windows-using crackers....
Re:Personal crypto? (Score:3, Informative)
Re:Personal crypto? (Score:3, Informative)
Re:Personal crypto? (Score:5, Informative)
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.
Re:Personal crypto? (Score:2)
Oh Shiiiiiiit! (Score:4, Funny)
$mouth . $foot
A billion years? (Score:2, Interesting)
Re:I'm sorry (Score:2, Funny)
Re:I'm sorry (Score:5, Funny)
insert into mouth values ('foot')
What a shame. (Score:2, Offtopic)
How could OpenSSL be vulnerable to security attack (Score:4, Funny)
Re:How could OpenSSL be vulnerable to security att (Score:3, Funny)
Re:How could OpenSSL be vulnerable to security att (Score:2)
Dan Boneh (Score:3, Funny)
Re:Dan Boneh (Score:4, Interesting)
Even reading all the course books intently, I got a great deal of helpful information from the lectures.
Re:Dan Boneh (Score:2)
Umm... (Score:5, Funny)
Not cracking crypto (Score:3, Insightful)
is this easy to implement? (Score:4, Interesting)
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?
Re:is this easy to implement? (Score:5, Informative)
Uniform response time. (Score:3, Redundant)
Set a t
Re:Uniform response time. (Score:2)
Re:is this easy to implement? (Score:5, Informative)
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.
Not so! Best case is better. (Score:2)
This is true only if the random delays are added to the running time of the operation you want to conceal. A simple, alternative method that reveals no information about the operation's running time is to decide upon the total (typically random) running time before performing the operation. Then, after t
Re:is this easy to implement? (Score:2)
Re:is this easy to implement? (Score:2)
On an CISC machine you should possibly even modify the assembly:
; test the bit.
jne elsepart
mov 1, badbit
jmp next
elsepart:
mov 1, goodbit
next:
by adding a
jmp next
into the "else" part to make the timing identical. It is exactly these
In a nutshell... (Score:5, Informative)
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. :(
Practical? (Score:2, Interesting)
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.
Re:Practical? (Score:2, Informative)
Re:Practical? (Score:3, Informative)
Re:In a nutshell... (Score:4, Insightful)
Your elitism has been commented on thoroughly, so I'll skip to the meat.
It takes 1.5 million queries to break an SSL key using this technique if you have an account on the same machine. That's for a local attack.
They go on to give evidence that a remote attack is possible, but don't actually give parameters that would indicate the complexity of the attack. 1.5 million queries is already kind of pushing it though, and I would imagine taking the attack to the remote setting, even with a small round trip, will explode the complexity significantly. So the attack may not be feasible at all.
Furthermore, adding random variance to latency data doesn't theoretically help much. Get enough samples, and that noise drops out. It raises the number of queries, yes, but doesn't stop the latency from forming a statistically usable distribution.
-Lux
Re:In a nutshell... (Score:2)
Re:In a nutshell... (Score:2, Funny)
Harvard should teach a course on how to shut up about Harvard
Re:In a nutshell... (Score:2)
Essentially what you're trying to do is mask the difference in the timings, unless you're using a theoretically interesting technique.
Lea
Xbox (Score:5, Interesting)
Just a thought.
Re:Xbox (Score:2)
Re:Xbox (Score:2)
-Lucas
After reading the article.... (Score:5, Informative)
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.
Re:After reading the article.... (Score:2)
Basically, if your connection to the attacked machine is shorter, the noise you'll receive is less.
Considering that there are thousands of compromised machines on the internet, there'll probably be a machine closeby that is vulnerable to some known exploit. That machine can then be used by the cracker as a proxy that does the timings. It may also do the attack automated, and at the end just relay the resulting key somewhere.
Remember that most machines are in
Followup or what? (Score:5, Informative)
This sounds a lot like the weakness discovered last month by the LASEC folks in Switzerland ...
Re:Followup or what? (Score:5, Informative)
The new attack just looks at how long the RSA decryption takes for carefully chosen values, and determines from that what the RSA secret exponent is, which means the RSA secret key. So this leaks the server's secret key and the server operator loses all of his cryptographic security. It's a much worse break.
However the timing precision needed for the new attack is much tighter thatn for the pad-vs-mac one, so at this point it can only be mounted across a LAN or on a shared-user system.
Where's the DMCA lawsuit (Score:5, Funny)
Re:Where's the DMCA lawsuit (Score:2)
1) We want it fixed, not hidden (no security through obscurity)
2) That which does not root our boxen makes them stronger
3) Can't afford the legal fees and lawyers
4) Too busy with pr0n
Pick whichever floats your boat
Palladium (Score:2)
Is this different from the recent OpenSSL warning? (Score:2)
Running
Package openssl-0.9.6g has a weak-encryption vulnerability, see http://www.openssl.org/news/secadv_20030219.txt
Define Remote.... (Score:5, Informative)
"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...
From far away? Probably not... (Score:4, Informative)
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".
Re:From far away? Probably not... (Score:3, Insightful)
Hmmmm... Not as unlikely as that - lots of people host on virtual-machines (e.g. Verio) or with managed hosting companies (e.g. Rackspace, which is why I'm nervous ;) ). That means that latency is very low, and fairly consistent.
Just a thought.
Re:From far away? Probably not... (Score:3, Insightful)
Then you could (somewhat) compensate for latency with each iteration.
Not necessarily elegant or foolproof, but I think possible... I wonder how much varience/latency (noise) you can reasonably account for before the exploit breaks down (or becomes too time-consuming to be worthwhile...)?
Re:Define Remote.... (Score:2)
No, but does that make this any less valid? A determined cracker will find a way. Maybe he has to comprimise an internal box first, to then be able to crack the SSL key -- does that make this any less risky?
It seems to me, to avoid timing attacks, that the server (SSL or whatever) should be careful to ensure that the response timing is similar whether it is an error condition or success condition -- in other words, give no cl
Is the xbox vulnerable to this? (Score:2, Interesting)
Re:Is the xbox vulnerable to this? (Score:2)
Re:Is the xbox vulnerable to this? (Score:2)
Chill please, It's not that bad (Score:4, Interesting)
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.
Actualyl it IS that bad (Score:5, Interesting)
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.
Re:Actually it IS that bad (Score:2)
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 pro
Re:Chill please, It's not that bad (Score:2)
If you want to be sure (and deal with multi-timeslice operations and kernels that give the process control in a more timely fashion), use setitimer. It's not a hard problem to correct, but people didn't previously think that it was actually a prob
Re:Chill please, It's not that bad (Score:2)
No, you don't always want to have that delay (random or otherwise), or it can be accounted for -- better is to have a desired total time for the operation (random or otherwise) and usleep(desired_total_time-time_taken), and much better than that is just to perform all the possible steps in any case (merely discarding thos
ROT-13+ (Score:4, Funny)
Re:ROT-13+ (Score:3, Funny)
Re:ROT-13+ (Score:2)
Re:ROT-13+ (Score:2)
ROT-13 CUBED sounds more L337. I was gonna do a super script 3, but
Why triple-DES is better than triple-ROT-13 (Score:2, Informative)
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.
Re:ROT-13+ (Score:2)
(Putting on my best Scooby voice) That would be called Rot-Row-13...
Easily remedied (Score:4, Insightful)
Too bad this can't be used against Xbox (Score:2, Informative)
An explanation of this attack (Score:5, Informative)
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*
Re:An explanation of this attack (Score:3, Interesting)
So, does that mean a feasible solution to prevent this sort of
Re:An explanation of this attack (Score:2, Informative)
Myria ^-^ *hugs*
Re:An explanation of this attack (Score:2, Interesting)
Please read the paper. The key to this attack is the selection of different multiplication algorithms depending on the lengths of the words being multiplied. Then, depending on the algorithm, the timing attack is based on whether the ciphertext is larger, smaller, or a multiple of the secret RSA moduli. Your explanation is a little too oversimplified.
Why hasn't the simple fix reached OpenSSL? (Score:5, Interesting)
I believe Paul Kocher first proposed [cryptography.com] (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 [rsasecurity.com] (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?
Re:Why hasn't the simple fix reached OpenSSL? (Score:3, Informative)
Re:Why hasn't the simple fix reached OpenSSL? (Score:3)
Interesting. But why in the name of all that is holy, did the OpenSSL developers choose to use an insecure-by-default system that requires every developer of an OpenSSL server application to turn on the blinding algorithm explicitly? That will mean patching every application! Apparently, some distributions that bundle OpenSSL don't include the blinding code either, without having it compiled in, which points to the distinct possibility that OpenSSL has this option turned off by default for some reason. The
Use this attack against X-Box (Score:5, Interesting)
But I could be wrong.
Phil
Re:Use this attack against X-Box (Score:2)
Re:Use this attack against X-Box (Score:4, Informative)
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.
Re:Use this attack against X-Box (Score:2)
(If OK takes longer than Not ok)
Or is the checking of a signed message an complete different method?
Re:Use this attack against X-Box (Score:3, Insightful)
Think about what you're saying for a second. If it is possible, using any sort of method whatsoever, to extract an RSA private key from a device that has only a public key, RSA is completely broken in general. In this particular example, I just build an X-box, substituting my adversary's public key for Microsoft's public key, perform whatever hocus pocus you're suggesting, and get my adversary's private key.
The fact is that the timing attack given in the article involves timing decryption, an activity wh
Re:Use this attack against X-Box (Score:2)
Write a game for the X-Box. Drop it in the mail to have it signed by microsoft, and start your stop watch. Write down how long it takes to get back. Repeat 1.5 million times.
The might get a bit suspicious when you send in games like Rouge Ninja Fighters 1432143, though.
Why random delay and not fix delay ? (Score:3, Insightful)
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 ?
re: Why random delay and not fix delay? (Score:2, Insightful)
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 d
Re:Why random delay and not fix delay ? (Score:2, Informative)
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
Re:Why random delay and not fix delay ? (Score:2)
Non-deterministic, workable, timing delay (Score:2, Insightful)
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...
Separate key pairs for different jobs ... (Score:2, Insightful)
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.
Idiot... (Score:4, Informative)
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.
Re:Idiot... (Score:2)
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.
So, the timing is so perfect because the code produces such predictable results, it leaks information? Maybe if they put s
Re:Idiot... (Score:2)
I smell Patent!!
Re:Idiot... (Score:2)
Re:Idiot... (Score:2)
Why is a lack of length checks so common in legacy code? Because it's human nature not to spend additional time on things that are not critical. Prior to exposure to hackers, the majority of potential buffer overflows were harmless. Most would never occur under normal conditions.
Now predictable timing in encryption code can be exploited by hackers, so in a way it's just as much a bug as a potential buffer overrun. The trend is
For all of you NOT rot-13 readers decoded (Score:2)
Re:ROT-26 is TWICE as secure as ROT-13 (Score:2)
That's a different, but interesting, problem. (Score:2, Insightful)
Since it came out in 2000, have modern browsers fixed the cache cookie problem? (Besides refusing cookies?)
Re:Invulnerable? (Score:2)
Re:Crypto for Idiots (Score:5, Informative)
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.