ECDH Key-Extraction via Low-Bandwidth Electromagnetic Attacks on PCs

Daniel Genkin Lev Pachmanov Itamar Pipman Eran Tromer
Technion and Tel Aviv University Tel Aviv University Tel Aviv University Tel Aviv University
This web page contains an overview of, and Q&A about our recent results that were presented at the RSA Conference Cryptographers' Track (CT-RSA) 2016 on March 3rd.

This research was conducted at the Laboratory for Experimental Information Security (LEISec).

In March 2016 we published a follow-up paper, "ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels", about extracting ECDSA secret keys from mobile phones.

Paper

Summary

We show that the secret decryption keys can be extracted from PCs running the the ECDH encryption algorithm, using the electromagnetic emanations generated during the decryption process. By measuring the target's electromagnetic emanations, the attack extracts the secret decryption key within seconds, from a target located in an adjacent room across a wall.

ECDH (Elliptic Curve Diffie Hellman) is a standard public-key encryption algorithm used in OpenPGP, as specified in RFC 6637 and NIST SP800-56A. We attacked the ECDH implementation of GnuPG's libgcrypt 1.6.3 (the latest version at the time the paper was written). The attack asks for decryption of a single carefully-chosen ciphertext, iterated a few dozen times, and then uses  time-frequency signal analysis techniques in order to extract from the electromagnetic leakage emitted by the target laptop during execution of ECDH decryptions.

Electromagnetic measurement
Attacker's setup for capturing EM emanations. Left to right: power supply, antenna on a stand, amplifiers, software defined radio (white box), analysis computer.
Electromagnetic measurement
Target laptop performing ECDH decryption using its secret key , on the other side of the wall.


Q&A

Q1: How vulnerable are GnuPG and other applications that use libgcrypt now?

We have disclosed our attack to GnuPG developers under CVE-2015-7511 and worked with the developers to implement countermeasures. GnuPG's Libgcrypt 1.6.5, containing these countermeasures and resistant to the key-extraction attack described here, was released concurrently with the public posting of these results.

Specifically, Libgcrypt 1.6.5 completely changed their implementation of the elliptic-point curve multiplication, to the "double-and-always-add" algorithm. This is slower than the prior implementation, but more resistant to side-channel attack since the sequence of high-level arithmetic operations does not the depend on the secret key.

Application-level status is as follows:

Q2: What does the measured signal look like?


We measure the electromagnetic signal with suitable analog and digital filter, and then apply FM demodulation. The resulting signal looks like this:


Processed signal
A segment of the electromagnetic signal obtained during a single decryption (after FM demodulation and filtering).

In order to obtain a clearer trace and remove the interrupts, we aggregate several dozen recorded decryption traces. The resulting aggregate trace looks like this:

Aggregate signal
A segment of the electromagnetic signal, after aggregating multiple measurements.
The information required for successful key extraction is the sequence arithmetic operations done on the elliptic curve: doubling (marked as D above) and additions (marked as 1 or -1).  These operations can be gleaned above, but we can detect them much more reliably by analyzing the frequency components of the aggregated trace:

Detecting additions
Distinguishing between elliptic-point doubling and additions. Top: a segment aggregated trace. Middle: the spectrogram of the aggregated segment, where blue denotes frequencies with low-energy and red denotes frequencies with high energy. The bottom figure gives the final result of the processing, clearly showing the locations of the addition operations.

From the identified elliptic-curve operations, the secret key can be completely reconstructed.

Q3: You attacked ECDH. What about other cryptographic schemes?

Other cryptographic schemes, running on PC-class computers, are also vulnerable to non-invasive physical side-channel key-extraction attacks. In prior works we attacked:
ECDH is faster than RSA and ElGamal, so it was harder to attack it using low-bandwidth measurements.

Ongoing works evaluates the security of additional cryptographic schemes.

Q4: What if I can't get physically close enough to the target computer?

For RSA and ElGamal (though not yet for ECDH), similar attacks have been demonstrated from large distances:

Q5: Is there a realistic way to perform a chosen-ciphertext attack on GnuPG?

GnuPG is often invoked to decrypt externally-controlled inputs, fed into it by numerous frontends, via emails, files, chat and web pages. The list of GnuPG frontends contains dozens of such applications, each of them can be potentially used in order to make the target decrypt the chosen ciphertexts required by our attack. As a concrete example, Enigmail (a popular plugin to the Thunderbird e-mail client) automatically decrypts incoming e-mail (for notification purposes) using GnuPG. An attacker can e-mail suitably-crafted messages to the victims (using the OpenPGP and PGP/MIME protocols), wait until they reach the target computer, and observe the target's EM emanations during their decryption (as shown above), thereby closing the attack loop. We have empirically verified that such an injection method does not have any noticeable effect on the leakage signal produced by GnuPG running on the target laptop. GnuPG's Outlook plugin, GpgOL also did not seem to alter the target's leakage signal.

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

The attack, in its current form, uses lab equipment that costs about $3000 and, as shown in the photo, is somewhat unwieldy.

However, experience shows that once the physical phenomena are understood in the lab, the attack setup can be miniaturized and simplified. This is especially true for low-banwidth attacks, such as ours, which measures frequencies that are three orders of magnitudes lower than the clock rate of the target computer. For example, in a we showed a compact for electromagnetic attacks on RSA and ElGamal encryption, called PITA: ostensibly Portable Instrument for Trace Acquisition, but aptly named after its portable form factor which fits inside typical pita bread. The PITA is improvised out of commodity parts and costs about $300. Other physical side channel attacks, such as acoustic attacks, can even be performed by a plain smartphone.

Thus, it is likely that the new attack on ECDH can also be performed clandestinely and at at even lower cost. Most adversaries would not go through the trouble of using such techniques, given the sorry state of security vulnerabilities at the software level (after all, a thief will not bother climbing through a window if the front door is left unlocked). Thus, our work is most pertinent to systems that are carefully protected against software attacks, but — as we show — may be wide open to inexpensive physical attacks.

Acknowledgments

We thank Werner Koch, Yutaka Niibe, developers of GnuPG, for the prompt response to our disclosure and the productive collaboration in adding suitable countermeasures.

This work was sponsored by the Check Point Institute for Information Security; by the European Union's Tenth Framework Programme (FP10/2010-2016) under grant agreement 259426 ERC-CaC; by a Google Faculty Research Award; by the Israeli Ministry of Science and Technology; by the Israeli Centers of Research Excellence I-CORE Program (center 4/11); by the Leona M. & Harry B. Helmsley Charitable Trust; and by NATO's Public Diplomacy Division in the Framework of "Science for Peace".