New Attacks on OpenSSL’s Elliptic Curve Crypto

Joël Alwen, Cryptography at Wickr
May 10, 2019 A new family of attacks targeting OpenSSL’s elliptic curve crypto (ECC) implementations has been released to the public. Vulnerable schemes include ECDH, ECDSA and ECIES on a variety of very common curve families. Given the widespread use of such schemes, including by Wickr, it is worth taking a more in-depth look at the attacks to understand what they achieve and what (if anything) you may need to do to defend yourself against them.

Spoiler alert: it turns that Wickr is not vulnerable due to how it uses ECC in OpenSSL. (In fact, even if Wickr were vulnerable, it’s far from clear that the cost of countermeasures would be worth it given the types of devices Wickr is used with in practice.)

The Attacks

The attacks were discovered and recently published by Akira Takahashi of Århus University, Denmark and Mehdi Tibouchi of NTT Secure Platform Laboratories, Japan. Their detailed writeup can be found here. In this post, we will go over the basic technique at a high level to help form an understanding of the impact these attack techniques can and cannot have.

First, a quick reminder about how ECC works. Recall that ECC schemes (e.g. ECDH) operate over a group of points on some underlying elliptic curve. That is, they represent certain data (e.g. ciphertexts, signatures and/or key material) as points in such a group. So, to actually use such an ECC scheme we must first specify exactly which elliptic curve, which set of points on that curve, and which designated “based point” in that set we want to use. Henceforth, we’ll refer to this extra information as the curve parameters.

The new attacks make use of OpenSSL’s optional ability, when reading ECC key material from a file (e.g. a .pem file) to also load curve parameters along with a key itself. This was added to OpenSSL to support non-standard EC groups.

The attack also makes use of a powerful technique known as fault injection. Basically, these aim to trigger specific errors in the execution of a target process. For attacks on OpenSSL, the goal is to cause a particular instruction in OpenSSL’s code to be skipped. Generally, this can be achieved through a variety of techniques that vary in effectiveness, cost, and complexity. For example, such errors can be triggered by varying the target device’s voltage, temperature or clock speed at the right moment in time or by exposing the device to certain types of radiation such as lasers, x-rays, ion beams or even white light. As a proof of concept of the new attacks against OpenSSL 1.1.1, Takahashi and Tibouchi triggered the desired errors in a RaspberryPi using voltage-based fault injection. To make the attack work at a price point of 250 USD, they ended up exploiting some artificial vulnerabilities in the target setup. However, they point out that a more expensive attack setup can be used to the same end against a more realistic target.

The details of how the different ECC schemes attack vary somewhat. But roughly speaking, they all adhere to the following paradigm:

  1. Fault injection is used to skip a single instruction on the target device while it is loading the curve parameters for the keyfile. This results in one of two integers in the equation defining the elliptic curve to be erroneously set to 0.
  2. Because the curve parameters are already loaded incorrectly, the remaining validity checks in OpenSSL (e.g. designed to detect faulty key material) won’t detect any problem. In fact, this property is central to what makes these attacks so interesting. Until now, tricking OpenSSL to operate on degenerate curve parameters (or curve points) required much more expensive and difficult to mount fault injections. Lowering this bar results in a host of mathematical attacks on the underlying ECC to become more feasible/cheaper in practice.
  3. The remainder of the ECC algorithm is evaluated faithfully by the target device and the (normally not sensitive) results are returned to the attacker. For example, when attacking ECDSA, the signature is returned to the attacker. When attacking ECDH, the attacker receives a ciphertext encrypting a (presumably secret) message using the shared key produced during the ECDH execution.
  4. After performing these steps several times to gather a sufficient amount of information, the attacker uses some (quite sophisticated) algorithms to reconstruct secrets belonging to the target device. For example, when attacking ECDSA, a single faulty signature is enough to recover the target’s signing key! When attacking ECDH, several faulty runs (all with the same ECDH keys) are needed to recover the shared ECDH key and thus also the encrypted message(s).

Who is Vulnerable?

The results of these attacks are quite devastating and defending yourself against them can, depending on your circumstances, be quite expensive. To decide if you actually need to take some form of mitigating action, you should be asking yourself at least two questions:

  • Am I vulnerable to the attacks?
  • If I am vulnerable, does it make sense to spend the resources on closing the vulnerability?

Fortunately, mounting these attacks requires the target to allow the non-standard OpenSSL feature of loading curve parameters from user supplied key files. In practice, this isn’t always supported because OpenSSL already provides hardcoded curve parameters for a large collection of common cases. Such parameters can be referenced directly by applications via the abstraction of “named curves”. So, if your application only uses a named curve (i.e. it doesn’t allow user supplied curve parameters), then it isn’t vulnerable in the first place and you have nothing to worry about.

For example, all Wickr applications make exclusive use of the named curve secp521r for all ECC purposes. In particular, no Wickr applications permit the user defined curve parameters meaning that no Wickr application is vulnerable to these attacks.

Say You Are Vulnerable, Should You Take Action?

Counter measures for these attacks include switching away from vulnerable versions of OpenSSL, hardening your device against fault injection or disabling features in your product that make you vulnerable in the first place. Each of these approaches comes with their own costs and unwanted side effects: added developer resources, QA, external code reviews, re- certification, hardware design/construction costs, reduced functionality, etc. Moreover, as an end user, you may not even be able to make such changes to the product leaving you with no better defense than to simply stop using the vulnerable system.

The good news: in many practical use cases, it’s just not worth it to pay the price of a defense. The bad news: that’s because in those cases there are probably cheaper, more reliable and easier ways to attack you with the same result.

To help you decide if you fall into one of those cases, we’ll take a moment to look at things from the attacker’s perspective. What do they need to mount the attack against different types of devices? Suppose those needs are met, is it likely that there are easier ways to achieve the same ends? If the answer is “yes,” there seems to be little point in defending yourself from these attacks. (Rather, focus your efforts on those easier attack methods!)

Software Fault Injection: Crucially, to run the new attacks on OpenSSL an adversary must be able to perform a fault injection resulting in skipping a very specific instruction. Now, fault injections come in many flavors and result in many types of faults. If the attacker has a method on your device to trigger the particular fault used in the new attacks using a software-based method, then you can be almost sure that there will be cheaper and more reliable methods for them to gain root access to the device. Moreover, once they have root there are likely easier, more reliable, and cheaper methods to access its sensitive data. So, there seems to be little point in defending against the attacks in such cases.

PCs & Laptops: Realistically, for the vast majority of target devices and vulnerable implementations triggering the type of fault required for the new attacks can only be triggered when given prolonged physical access to the target device while using very specialized (and often expensive) attack hardware.

But the truth is, once an adversary gets prolonged physical access to your laptop or PC, there will almost always be cheaper and easier ways for them to access all of its sensitive data. This is especially true if they have the level of resources and sophistication necessary to mount such fault injections. So, for these types of devices it will rarely make practical sense to pay the price to defend against these attacks.

Phones & Tablets: For phones and tablets, the situation may at first seem to be somewhat less clear cut. Modern mobile OSes and hardware actually allow users to lock down their devices much more tightly than is common for PCs and laptops. This would seem to make the new attacks more relevant and worth defending against. However, even with all of those security features enabled and correctly configured, we still keep seeing reliable and easy to use “unlocking” exploits which restore full access to such devices and its data (e.g. those used increasingly often by law enforcement). In fact, even when the adversary does not have access to such an unlocking exploit, they still face the very real hurdle of needing to be able to actually run the vulnerable application, load the keyfile and cause the desired fault at a very precise moment. The required precision is all the more stringent for the adversary in light of the complexity of modern mobile OSes and the comparatively high clock speeds of the device’s CPUs. Worse, it’s not unlikely that failed attempts at fault injection will inadvertently end up crashing the OS, resulting in a reboot. Yet, if the adversary can unlock the device then we’re back to there being better ways to attack the device. Realistically, for the attack to make sense, the adversary will need a way to repeatedly run the target application under very stringent timing constraints despite the device being locked. For this to be both possible and the best attack available seems like a tall order in almost any practical scenario. For phones and tablets it will rarely make sense to pay too high a price for defending against the new attacks.

IoT: Where the new attacks really shine though are against devices that have otherwise been properly hardened against physical attacks, where prolonged physical access by an adversary is a real possibility, and where access to the OS of the device is not available. For this reason, Takahashi and Tibouchi motivate the attacks as being primarily relevant to IoT devices. In fact, even devices where security wasn’t a prominent design goal may inadvertently end up limiting the adversary’s options simply by presenting a very restricted interface to the user. In these types of cases, the new attacks may end up being the best method to extract secrets from the devices and so it starts to make sense to implement countermeasures despite their costs.