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 will be 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).

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:

• Software Defined Radio (SDR) attack. We constructed a simple shielded loop antenna (15 cm in diameter) using a coaxial cable. We then recorded the signal produced by the probe using an SDR receiver. The electromagnetic field, thus measured, is affected by ongoing computation, and our attacks exploit this to extract RSA and ElGamal keys, within a few seconds.
  
  
• Untethered SDR attack. Setting out to simplify and shrink the analog and analog-to-digital portion of the measurement setup, we constructed the Portable Instrument for Trace Acquisition (Pita), which is built of readily-available electronics and food items (see instructions here). Pita can be operated in two modes. In online mode, it connects wirelessly to a nearby observation station via WiFi, and provides real-time streaming of the digitized signal. The live stream helps optimize probe placement and allows adaptive recalibration of the carrier frequency and SDR gain adjustments. In autonomous mode, Pita is configured to continuously measure the electromagnetic field around a designated carrier frequency, and records the digitized signal into an internal microSD card for later retrieval, by physical access or via WiFi. In both cases, signal analysis is done offline, on a workstation.
  
• Consumer radio attack. Despite its low price and compact size, assembly of the Pita device still requires the purchase of an SDR device. As discussed, the leakage signal is modulated around a carrier circa 1.7 MHz, located in the range of the commercial AM radio frequency band. We managed to use a plain consumer-grade radio receiver to acquire the desired signal, replacing the magnetic probe and SDR receiver. We then recorded the signal by connecting it to the microphone input of an HTC EVO 4G smartphone.
  

  

---

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:

• In almost all machines, it is possible to tell, with sub-millisecond precision, whether the computer is idle or performing operations.
• On many machines, it is moreover possible to distinguish different patterns of CPU operations and different programs.
• Using GnuPG as our study case, we can, on some machines:
  • distinguish between the spectral signatures of different RSA secret keys (signing or decryption), and
  • fully extract decryption keys, by measuring the laptop's electromagnetic emanations during decryption of a chosen ciphertext.

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.

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?

• Software Defined Radio (SDR) attack. The main component in the first setup is a FUNcube Dongle Pro+ SDR receiver. Numerous cheap alternatives exist, including ``rtl-sdr'' USB receivers based on the Realtek RTL2832U chip (originally intended for DVB-T television receivers) with a suitable tuner and upconverter; the Soft66RTL2 dongle is one such example.
• Untethered SDR attack. The Pita device uses an unshielded loop antenna made of plain copper wire, wound into 3 turns of diameter 13 cm, with a tuning capacitor chosen to maximize sensitivity at 1.7 MHz (which is where the key-dependent leakage signal is present). These are connected to the aforementioned FUNcube Dongle Pro+ SDR receiver. We control the SDR receiver using a small embedded computer, the Rikomagic MK802 IV. This is an inexpensive Android TV dongle based on the Rockchip RK3188 ARM SoC. It supports USB host mode, WiFi and flash storage. We replaced the operating system with Debian Linux, in order to run our software, which operates the SDR receiver via USB and communicates via WiFi. Power is provided by 4 NiMH AA batteries, which suffice for several hours of operation.
  

• Consumer radio attack. We have tried many consumer-grade radio receivers and smartphones with various results. Best results were achieved using a "Road Master" brand consumer radio connected to the microphone jack of an HTC EVO 4G smartphone, sampling at 48 kHz, through an adapter cable. The dedicated line-in inputs of PCs and sound cards do not require such an adapter, and yield similar results.

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.

 

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.

• 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.

Q6: What's new since your previous papers?

• Cheap experimental setup. The previous papers required either a long attack time (about an hour) when using inexpensive equipment, or a fast attack (a few seconds) but using an expensive setup. In this paper we achieve the best of both, presenting an experimental setup which extracts keys quickly while remaining simple and cheap to construct.
• New cryptographic technique addressing modern implementations. In the previous papers we attacked the naive square-and-multiply exponentiation algorithm and the square-and-always-multiply variant (which reduces side-channel leakage). However, most modern implementations utilize faster exponentiation algorithms: sliding-window, or for better side-channel resistance, m-ary exponentiation. In this paper we demonstrate a low-bandwidth attack on the latter two algorithms, extracting their secret keys.

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. 
   
   

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

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

We thank Werner Koch, lead developer of GnuPG, for the prompt response to our disclosure and the productive collaboration in adding suitable countermeasures. Erik Olson's Baudline signal analysis software was used for some of the analysis.

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 the Leona M. & Harry B. Helmsley Charitable Trust; by the Israeli Ministry of Science and Technology; by the Israeli Centers of Research Excellence I-CORE Program (center 4/11); and by NATO's Public Diplomacy Division in the Framework of "Science for Peace".
https://www.tau.ac.il/~tromer/radioexp/

---