Stealing Keys from PCs using a Radio:
Cheap Electromagnetic Attacks on Windowed Exponentiation

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 published in a technical paper (PDF, 2.1MB), archived as IACR ePrint 2015/170. It was presented at the Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2015 in September 2015.

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

In February 2016 we published a follow-up paper, "ECDH Key-Extraction via Low-Bandwidth Electromagnetic Attacks on PCs", about electromagnetic attacks on ECDH encryption.
In March 2016 we published another follow-up paper, "ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels", about extracting ECDSA secret keys from mobile phones.

Overview

We demonstrate the extraction of secret decryption keys from laptop computers, by nonintrusively measuring electromagnetic emanations for a few seconds from a distance of 50 cm. The attack can be executed using cheap and readily-available equipment: a consumer-grade radio receiver or a Software Defined Radio USB dongle. The setup is compact and can operate untethered; it can be easily concealed, e.g., inside pita bread. Common laptops, and popular implementations of RSA and ElGamal encryptions, are vulnerable to this attack, including those that implement the decryption using modern exponentiation algorithms such as sliding-window, or even its side-channel resistant variant, fixed-window (m-ary) exponentiation.

We successfully extracted keys from laptops of various models running GnuPG (popular open source encryption software, implementing the OpenPGP standard), within a few seconds. The attack sends a few carefully-crafted ciphertexts, and when these are decrypted by the target computer, they trigger the occurrence of specially-structured values inside the decryption software. These special values cause observable fluctuations in the electromagnetic field surrounding the laptop, in a way that depends on the pattern of key bits (specifically, the key-bits window in the exponentiation routine). The secret key can be deduced from these fluctuations, through signal processing and cryptanalysis.

The attack can be mounted using various experimental setups:

Q&A

Q1: What information is leaked by the electromagnetic emanations from computers?

This depends on the specific computer hardware. We have tested numerous laptop computers, and found the following:
A good way to visualize the signal is as a spectrogram, which plots the measured power as a function of time and frequency. For example, in the following spectrogram (recorded using the first setup pictured above), time runs vertically (spanning 2.1 seconds) and frequency runs horizontally (spanning 1.6-1.75 MHz).  During this time, the CPU performs loops of different operations (multiplications, additions, memory accesses, etc.). One can easily discern when the CPU is performing each operation, due to the different spectral signatures.
various CPU operations

Q2: Why does this happen?

Different CPU operations have different power requirements. As different computations are performed during the decryption process, different electrical loads are placed on the voltage regulator that provides the processor with power. The regulator reacts to these varying loads, inadvertently producing electromagnetic radiation that propagates away from the laptop and can be picked up by a nearby observer. This radiation contains information regarding the CPU operations used in the decryption, which we use in our attack.

Q3: How can I construct such a setup?

Q4: What is the range of the attack?

In order to extend the attack range, we added a 50dB gain stage using a pair of inexpensive low-noise amplifiers (Mini-Circuits ZFL-500LN+ and ZFL-1000LN+ in series, 175$ total). We also added a low-pass filter before the amplifiers. With this enhanced setup, the attack can be mounted from 50 cm away. Using better antennas, amplifiers and digitizers, the range can be extended even further.
 long-range attack

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

There are still attacks that can be mounted from large distances.

Q6: What's new since your previous papers?

Q7: How can low-frequency (kHz) leakage provide useful information about a much faster (GHz) computation?

We use two main techniques.
  1. Leakage self-amplification. Individual CPU operations are too fast for our measurement equipment to pick up, but long operations (e.g., modular exponentiation in RSA and ElGamal) can create a characteristic (and detectable) spectral signature over many milliseconds. Using a suitably chosen ciphertext, we are able to use the algorithm's own code to amplify its own key leakage, creating very drastic changes, detectable even by low-bandwidth means.
  2. Data-dependent leakage. While most implementations (such as GnuPG) attempt to decouple the secret key from the sequence of performed operations, the operands to these operations are key-dependent and often not fully randomized. The attacker can thus attempt to craft special inputs (e.g., ciphertexts to be decrypted) to the cryptographic algorithm that "poison" the intermediate values inside the algorithm, producing a distinct leakage pattern when used as operands during the algorithm's execution. Measuring leakage during such a poisoned execution can reveal in which operations the operands occurred, and thus leak secret-key information.

    For example, the figure presents the leakage signal (after suitable processing) of an ElGamal decryption. The signal appears to be mostly regular in shape, and each peak corresponds to a multiplication performed by GnuPG's exponentiation routine. However, an occasional "dip" (low peak) can be seen. These dips correspond to a multiplication by a poisoned value performed within the exponentiation routine. 
    signal example

Q8: How vulnerable is GnuPG now?

We have disclosed our attack to GnuPG developers under CVE-2014-3591, suggested suitable countermeasures, and worked with the developers to test them. GnuPG 1.4.19 and Libgcrypt 1.6.3 (which underlies GnuPG 2.x), containing these countermeasures and resistant to the key-extraction attack described here, were released concurrently with the first public posting of these results.

Q9: How vulnerable are other algorithms and cryptographic implementations?

This is an open research question. Our attack requires careful cryptographic analysis of the implementation, which so far has been conducted only for the GnuPG 1.x implementation of RSA and ElGamal. Implementations using ciphertext blinding (a common side-channel countermeasure) appear less vulnerable.

Q10: 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.

Q11: What countermeasures are available?

Physical mitigation techniques of electromagnetic radiation include Faraday cages. However, inexpensive protection of consumer-grade PCs appears difficult. Alternatively, the cryptographic software can be changed, and algorithmic techniques employed to render the emanations less useful to the attacker. These techniques ensure that the rough-scale behavior of the algorithm is independent of the inputs it receives; they usually carry some performance penalty, but are often used in any case to thwart other side-channel attacks. This is what we helped implement in GnuPG (see Q8).

Q12: Why software countermeasures? Isn't it the hardware's responsibility to avoid physical leakage?

It is tempting to enforce proper layering and decree that preventing physical leakage is the responsibility of the physical hardware. Unfortunately, such low-level leakage prevention is often impractical due to the very bad cost vs. security tradeoff: (1) any leakage remnants can often be amplified by suitable manipulation at the higher levels, as we indeed do in our chosen-ciphertext attack; (2) low-level mechanisms try to protect all computation, even though most of it is insensitive or does not induce easily-exploitable leakage; and (3) leakage is often an inevitable side effect of essential performance-enhancing mechanisms (e.g., consider cache attacks).

Application-layer, algorithm-specific mitigation, in contrast, prevents the (inevitably) leaked signal from bearing any useful information. It is often cheap and effective, and most cryptographic software (including GnuPG and libgcrypt) already includes various sorts of mitigation, both through explicit code and through choice of algorithms. In fact, the side-channel resistance of software implementations is nowadays a major concern in the choice of cryptographic primitives, and was an explicit evaluation criterion in NIST's AES and SHA-3 competitions.

Q13: What does the RSA leakage look like?

Here is an example of a spectrogram (which plots the measured power as a function of time and frequency) for a recording of GnuPG decrypting the same ciphertext using different randomly generated RSA keys:

spectrogram of multiple GnuPG RSA decryptions

In this spectrogram, the horizontal axis (frequency) spans ranges from 1.72 MHz to 1.78 MHz, and the vertical axis (time) spans 1.2 seconds. Each yellow arrow points to the middle of a GnuPG RSA decryption. It is easy to see where each decryption starts and ends. Notice the change in the middle of each decryption operation, spanning several frequency bands. This is because, internally, each GnuPG RSA decryption first exponentiates modulo the secret prime p and then modulo the secret prime q, and we can actually see the difference between these stages. Moreover, each of these pairs looks different because each decryption uses a different key. So in this example, by simply observing electromagnetic emanations during decryption operations, using the setup from this figure, we can distinguish between different secret keys.

Q14: What is the difference between your attack and the recent cache attack by Yarom et al.?

Cache side channel (timing cross-talk between processes or virtual machines) apply to scenarios where the attacker can execute code on the same physical machine as the targeted process (e.g., in shared computers, such as Infrastructure as a Service cloud computing).

Our attack exploits physical information leakage from computation devices, and does not require the attacker to execute his own code on the intended target.

Acknowledgments