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.
- Daniel Genkin, Lev Pachmanov, Itamar Pipman, Eran Tromer, ECDH key-extraction via low-bandwidth electromagnetic attacks on PCs, proc. RSA Conference Cryptographers' Track (CT-RSA) 2016, LNCS 9610, 219-235, Springer, 2016
- Latest version: [PDF]
- Archived on [eprint]
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.
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:
- On Linux:
- GnuPG 2.1.x typically use the system's libgcrypt library installation, so updating libgcrypt to 1.6.5 or newer is sufficient.
- GnuPG 1.x and 2.0.x does not support elliptic-curve cryptography.
- On Windows:
- Gpg4Win does not support elliptic-curve cryptography.
- Cygwin packages only the vulnerable libgcrypt 1.6.4, and does not package a GnuPG version that supports elliptic-curve cryptography (as of Feburary 16, 2016)
- On Mac:
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:
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:
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:
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:
- 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).
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:
- 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.
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.