Timing attacks have been a problem for designers of cryptosystems–as well as for people implementing those systems–for a long time. They’ve plagued just about every popular system, and although practical attacks have been demonstrated many times, the problem and what can be done to defend against it are well understood. As a result, researchers have for the most part focused their efforts on other side-channel attacks on cryptosystems of late. However, a new paper by a pair of researchers at a Finnish university shows that timing attacks still can be used to completely compromise some cryptosystems.
The researchers, Billy Bob Brumley and Nicola Tuveri of Aalto University School of Science, focused their efforts on OpenSSL’s implementation of the elliptic curve digital signature algorithm (ECDSA), and they were able to develop an attack that allowed them to steal the private key of an OpenSSL server.
“This paper describes a timing attack vulnerability in OpenSSL’s ladder implementation for curves over binary fields. We use this vulnerability to steal the private key of a TLS server where the server authenticates with ECDSA signatures. Using the timing of the exchanged messages, the messages themselves, and the signatures, we mount a lattice attack that recovers the private key,” they say in the paper, “Remote Timing Attacks Are Still Practical*”.
I spoke with Brumley via email about the attack, the defense and whether enterprises should be concerned about its ramifications.
Threatpost: How difficult would it be to implement the attack you describe against a real-world cryptosystem?
Brumley: I know of at least one study showing that TLS sessions authenticated with elliptic curve cryptography outnumber those authenticated with any other method (RSA, DSA, …).
In our attack, we used OpenSSL’s generic TLS server s_server as the attack target. In many respects, it represents a large class of applications built upon OpenSSL. A developer might use it as the starting point when developing an application that requires TLS. So we feel that this attack target in fact encompasses a wide range of real-world cryptosystems.
Threatpost: Are there any practical mitigations for the attack, aside from the defense you describe in the paper?
Brumley: Use a different certificate and/or disable elliptic curve support in OpenSSL. (Of course I’d recommend first the source code patch provided in the paper–it’s a free countermeasure.)
Threatpost: How worried should defenders be about this attack?
Brumley: The most remote scenario we consider in the paper is the client and server on two separate machines on the same LAN. This work is substantially different from that of Brumley and Boneh’s timing attack on RSA; there, the attacker can compensate for variances in network noise by repeating measurements. This is because the RSA private exponent is not changing. In our attack, the one-time ECDSA keys are *always* distinct. So if there is sufficient noise on the network, the timings might not prove useful. Can it work across a LAN? Yes, we tried it. Can it work across the Internet? Feasible, but I don’t know; try it yourself. Can you steal the private key of the Mars Rover? Probably not. On the other hand, ask a room full of cryptographers: ‘Raise your hand if you want the security of your private key to rely only on variations in network latency.’ Then watch the tumbleweeds roll by.
Furthermore, the definition of a remote attack is vastly different from what it was ten years ago. Now cloud computing, VPS, etc. are widespread. With these technologies, it’s feasible that an attacker can run its code on the same physical machine as the attack target, eliminating network noise altogether. So the line between a remote and local attack is quickly vanishing.
As it stands, the attack is only relevant when using elliptic curves over binary fields. If I’m running a server with a certificate containing a public key on such a curve, without a doubt I’d consider this a serious threat. Users should also understand that OpenSSL is a general-purpose library. I cannot speak for every protocol implemented using OpenSSL. It’s feasible that the curve parameters are negotiated in a protocol, so although on the surface it might not look like you’re using such a curve, perhaps an attacker can force the server to use one of these curves. A good example of a protocol built using OpenSSL is OpenSSH. I’m not claiming OpenSSH is vulnerable to our attack, but you get the idea; the list goes on and on.
Perhaps the scariest part is that the piece of code introducing the vulnerability has been in the library since roughly 2005. This shows that identifying timing attack vulnerabilities is a daunting task. This isn’t the first timing attack vulnerability discovered in OpenSSL, and I can guarantee it won’t be the last. This is not me criticizing OpenSSL. I’d argue that implementing completely constant-time cryptographic software, in such a versatile, portable, feature and support-packed library like OpenSSL is a futile task. In my opinion, the library is the most important piece of open source cryptographic software that exists. My hope is that identifying vulnerabilities like this and implementing attacks based on them leads to more secure software and that end-users will have more confidence in the product.