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

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.

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

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

Q2: Why does this happen?

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?

 

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?

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?

Q9: How vulnerable are other algorithms and cryptographic implementations?

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?

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?

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

Acknowledgments