ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

This research was conducted at Tel Aviv University's Laboratory for Experimental Information Security (LEISec), in collaboration with The University of Adelaide.

Paper

• Latest version: [PDF]
• Daniel Genkin, Lev Pachmanov, Itamar Pipman, Eran Tromer, Yuval Yarom, ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels, IACR Cryptology ePrint Archive, https://eprint.iacr.org/2016/230
• Daniel Genkin, Lev Pachmanov, Itamar Pipman, Eran Tromer, Yuval Yarom, ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels, ACM Conference on Computer and Communications Security (CCS) 2016, to appear

Summary

We show that modern cryptographic software on mobile phones, implementing the ECDSA digital signature algorithm, may inadvertently expose its secret keys through physical side channels: electromagnetic radiation and power consumption which fluctuate in a way that depends on secret information during the cryptographic computation. An attacker can non-invasively measure these physical effects using a $2 magnetic probe held in proximity to the device, or an improvised USB adapter connected to the phone's USB cable, and a USB sound card. Using such measurements, we were able to fully extract secret signing keys from OpenSSL and CoreBitcoin running on iOS devices. We also showed partial key leakage from OpenSSL running on Android and from iOS's CommonCrypto.

The attacked cryptographic algorithm is ECDSA (Elliptic Curve Digital Signature Algorithm), a standard digital signature algorithm used in many applications such as Bitcoin wallets and Apple Pay. Thus, such applications, especially those that rely on vulnerable versions of OpenSSL, CoreBitcoin or iOS, may expose their users to low-cost physical attacks leading to theft of signing credentials and subsequent unauthorized transactions or false authentication.

Our methodology includes physical signal acquisition from mobile devices (phones and tablet), signal processing for signal extraction and enhancement using Singular Spectrum Analysis, and a lattice-based algorithm for recovering the secret signing key by aggregating partial information learned from many randomized signing operations.

Here is an example of an electromagnetic attack setup (underneath the glass tabletop), that can be used to attack a mobile phone placed on the table.

---

Q&A

Q1: What is the status of the vulnerable libraries?

Practicing responsible disclosure, we have worked with the vendors of all targeted software to convey our findings and coordinate response, prior to public disclosure.

Application-level status is as follows:

• OpenSSL:
• OpenSSL 1.0.x is vulnerable: we performed key extraction on this implementation.
  Exception: OpenSSL uses an alternative implementation for some elliptic curves, when compiled for x86-64 with the non-default enable-ec_nistp_64_gcc_128 option. We have no evidence that the alternative implementation is vulnerable.
  The OpenSSL's developers notified us that "hardware side-channel attacks are not in OpenSSL's threat model", so no updates are planned to OpenSSL 1.0.x to mitigate our attacks.
• OpenSSL 1.1.x is vulnerable, since it uses the vulnerable wNAF implementation as OpenSSL 1.0.x.
  Exceptions: the aforementioned x86-64 code. Moreover, on ARM, and specifically for the NIST P-256 curve (but not secp256k1), new constant-time code is used and we have no evidence that it is vulnerable.
• iOS CommonCrypto:
• iOS 7.1.2-8.3 appears vulnerable: its ECDSA implementation, in CommonCrypto, exhibits scalar-dependent leakage and thus appears vulnerable.
• iOS 9.x does not appear vulnerable: its implementation uses side-channel mitigation techniques and we have no evidence that it is vulnerable.
• CoreBitcoin: CoreBitcoin is vulnerable: we performed key extraction on this implementation. The developers expressed their intention to switch to the libsecp256k1 library in the future.
• Bitcoin Core: the latest Bitcoin Core does not appear vulnerable. It transitioned to using the libsecp256k1 library in v0.10.0 (released in February 2015; see fda3fed18a and dffb8f81b8) and we have no evidence that libsecp256k1 is vulnerable.
• BouncyCastle: Android's version of BouncyCastle is vulnerable, as discovered by a concurrent and independent work, Side-Channel Analysis of Weierstrass and Koblitz Curve ECDSA on Android Smartphones.

Q2: What does the measured electromagnetic signal look like?

The electromagnetic signal is measured using a magnetic probe, and digitized by a sound card, a software-defined radio, or a lab-grade sampling card. After some digital filtering, the raw signal looks like this: In order to obtain a clearer trace, we applied singular spectrum analysis (SSA). The resulting trace trace looks like this:
The information required for successful key extraction is the sequence of double and add operations done on the elliptic curve (marked D and A respectively). These operations can be gleaned above, but we can detect them much more reliably by analyzing the frequency components of the trace:
After observing the elliptic-curve double and add operations during a few thousand signatures, the secret signing key can be completely reconstructed.

Q3: You attacked ECDSA on phones. What about other cryptographic schemes? How about PCs?

Other cryptographic schemes, running on laptop computers, are also vulnerable to non-invasive physical side-channel key-extraction attacks. In prior works we attacked:

• RSA implementations using sliding-window and fixed-window exponentiation (shown at CHES'15), as well as square-and-always-multiply exponentiation (at CHES'14 and at CRYPTO'14).
• ElGamal implementations using sliding-window and fixed-window exponentiation (at CHES'15), as well as square-and-always-multiply exponentiation (at CHES'14).
• ECDH encryption implementations using double-and-sometimes-add with NAF represenation (at CT-RSA 2016).

Ongoing works evaluates the security of additional cryptographic schemes.

Q4: Why did you attack ECDSA? Is it any different from the prior works on RSA, ElGamal and ECDH?

We focused on extracting secrets keys of the ECDSA (Elliptic Curve Digital Signature Algorithm), for two reasons:

• In terms of practical importance, ECDSA is a standard digital signature algorithm (FIPS PUB 186-4) that is much faster than traditional RSA signatures at the same security level, making it a very popular choice in new software and protocols running on mobile phones (e.g., Bitcoin and Apple Pay).
• From a research perspective, ECDSA raises new and interesting challenges, placing a very high bar on the requisite signal processing and cryptanalytic tools. First, ECDSA signatures are fast, so the attacker gets little physical information (compared to, say, RSA). Second and more fundamentally, ECDSA signatures are randomized. When attacking non-randomized operations, such as RSA/ElGamal/ECDH decryption, attackers can rely on triggering numerous identical decryptions and then aggregating their recorded traces in order to improve signal-to-noise ratio and cope with transient events such as interrupts. But with ECDSA, the attacker is forced to make deductions from individual traces that are noisy and frequently interrupted.

Q5: What if I can't get physically close enough to the target device?

For RSA and ElGamal, similar attacks have been demonstrated from large distances, including across walls:

• Laptop-chassis potential, measured from the far end of virtually any shielded cable connected to the laptop (such as Ethernet, USB, HDMI and VGA cables), can be used for key-extraction, as we demonstrated in a paper presented at CHES'14.
• Acoustic emanations (sound), measured via a microphone, can also be used to extract keys from a range of several meters, as we showed in a paper presented at CRYPTO'14.
• Electromagnetic leakage, measured though the wall, can be used for key extraction from laptops, as we showed in a paper at CT-RSA'16.
• Power analysis, which monitors the phone's power consumption, can be used to extract the signing keys as well.  In principle, any charger, battery or even charging station can be augmented with the required equipment in order to extract the key.

Q6: How realistic is the attack? What is its cost in practice?

We showed that the signal can be measured and analyzed using cheap and readily-available equipment: a USB sound card hooked to a laptop, some wires, and a $2 probe (that can also be made out of plain wires).

Small loops of wire acting as EM probes can be easily concealed inside various objects that come in proximity with mobile devices, such as tabletops and phone cases. The phone's power consumption can be easily monitored by augmenting an aftermarket charger, external battery or battery case with the requisite equipment. Phone cases which contain an additional battery (and therefore are connected to the phone's charging port) can even be augmented to monitor both channels simultaneously.

The attack requires measuring a few thousand ECDSA signatures. How this may be done depends on the particular application being attacked. For example, in Bitcoin micropayment channels, which allow making lightweight out-of-blockchain automated payments for an ongoing service, each payment requires an ECDSA signature.

Q7: Most of your pictures are of iPhones. What about Android phones?

OpenSSL's ECDSA running on Android phones is also vulnerable to our attacks. For example, here is a Sony Xperia 10s being measured, with our lab-grade measurement equipment: A concurrent and independent work, Side-Channel Analysis of Weierstrass and Koblitz Curve ECDSA on Android Smartphones, also studied the vulnerability of Android's BouncyCastle's ECDSA implementation, and found it vulnerable to (intrusive) electromagnetic key extraction attacks.

---

Acknowledgments

---