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

TitleStealing Keys from PCs using a Radio: Cheap Electromagnetic Attacks on Windowed Exponentiation
File Size2.0 MB
Total Pages28
Table of Contents
                            Abstract
Contents
1 Introduction
	1.1 Overview
	1.2 Our Contribution
	1.3 Vulnerable Software and Hardware
	1.4 Related Work
	1.5 Preliminaries
2 Cryptanalysis
	2.1 GnuPG's Sliding-Window Exponentiation Routine
	2.2 ElGamal Attack Algorithm
	2.3 RSA Attack Algorithm
	2.4 Leakage from GnuPG's Multiplication Routine
3 Experimental Results
	3.1 SDR Experimental Setup
	3.2 Signal Analysis
	3.3 ElGamal Key Extraction
	3.4 RSA Key Extraction
	3.5 Long-Range Attack
	3.6 Untethered SDR Attack
	3.7 Consumer-Radio Attack
4 Discussion
Acknowledgments
References
                        
Document Text Contents
Page 1

Stealing Keys from PCs using a Radio:

Cheap Electromagnetic Attacks on Windowed Exponentiation

(extended version)

Daniel Genkin

Technion and Tel Aviv University

[email protected]

Lev Pachmanov

Tel Aviv University

[email protected]

Itamar Pipman

Tel Aviv University

[email protected]

Eran Tromer

Tel Aviv University

[email protected]

Posted February 27, 2015
Updated March 2, 2015

Abstract

We present new side-channel attacks on RSA and ElGamal implementations that use the
popular sliding-window or fixed-window (m-ary) modular exponentiation algorithms. The at-
tacks can extract decryption keys using a very low measurement bandwidth (a frequency band
of less than 100 kHz around carrier under 2 MHz) even when attacking multi-GHz CPUs.

We demonstrate the attacks’ feasibility by extracting keys from GnuPG, in a few seconds,
using a nonintrusive measurement of electromagnetic emanations from laptop computers. The
measurement equipment is cheap and compact, uses readily-available components (a Software
Defined Radio USB dongle or a consumer-grade radio receiver), and can operate untethered
while concealed, e.g., inside pita bread.

The attacks use a few non-adaptive chosen ciphertexts, crafted so that whenever the decryp-
tion routine encounters particular bit patterns in the secret key, intermediate values occur with
a special structure that causes observable fluctuations in the electromagnetic field. Through
suitable signal processing and cryptanalysis, the bit patterns and eventually the whole secret
key are recovered.

1

Page 2

Contents

1 Introduction 3
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Vulnerable Software and Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Cryptanalysis 7
2.1 GnuPG’s Sliding-Window Exponentiation Routine . . . . . . . . . . . . . . . . . . . 7
2.2 ElGamal Attack Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 RSA Attack Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Leakage from GnuPG’s Multiplication Routine . . . . . . . . . . . . . . . . . . . . . 12

3 Experimental Results 14
3.1 SDR Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Signal Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 ElGamal Key Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4 RSA Key Extraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.5 Long-Range Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.6 Untethered SDR Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.7 Consumer-Radio Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Discussion 25

Acknowledgments 26

References 26

2

Page 14

3 Experimental Results

This section presents experimental key extraction using the above cryptanalytic attack, via the elec-
tromagnetic side channel, using inexpensive Software Defined Radio (SDR) receivers and consumer
radios.

3.1 SDR Experimental Setup

Our first experimental setup uses Software Defined Radio to study EM emanations from laptop
computers at frequencies of 1.5–2 MHz, as detailed below (see also Figure 3).

Probe. As a magnetic probe, we constructed a simple shielded loop antenna using a coaxial
cable, wound into 3 turns of 15 cm diameter, and with suitable conductor soldering and center
shield gap [Smi99]. (For the compact untethered setup of Section 3.6 we used a different antenna,
described there.)

Receiver. We recorded the signal produced by the probe using a FUNcube Dongle Pro+ [Fun]
SDR receiver. The FUNcube Pro+ is an inexpensive (GBP 125) USB dongle that contains a
software-adjustable mixer and a 192 Ksample/sec ADC, accessed via USB as a soundcard audio
interface. We used the GNU Radio software [Gnu] to interface with this receiver. Numerous
cheaper 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 [RTL] (USD 50) is one such example.

Probe Placement. The placement of the EM probe relative to the laptop greatly influences
the measured signal and noise. We wished to measure EM emanations close to the CPU’s voltage
regular, located on the laptop’s motherboard, yet without mechanical intrusion. In most modern
laptops, the voltage regulator is located in the rear left corner, and indeed placing the probe close
to this corner usually yields the best signal. With our loop antennas, the best location is parallel
to the laptop’s keyboard for close distances (up to approximately 20 cm), and perpendicular to the
keyboard for larger distances; see Figures 3, 9 and 11 for examples.

Exponent-Dependent Leakage. To confirm the existence of leakage that depends on the (secret)
exponent, we first show how different exponents cause different leakage. Figure 4 demonstrates
ElGamal decryption operations using different secret exponents, easily distinguishable by their
electromagnetic leakage. Similar results were obtained for RSA.

3.2 Signal Analysis

Demodulation. As can be seen in Figure 4, when using periodic exponents the leakage signal
takes the form of a central peak surrounded by distinguishable side lobes. This is a strong indication
that the secret bit exponents are modulated by the carrier. As in [GPT14], the carrier signal turned
out to be frequency modulated, though in our case the baseband signal does not directly represent
the key bits.

Different targets produce such FM-modulated signals at different, and often multiple, frequen-
cies. In each experiment, we chose one such carrier and applied a band-pass filter around it: first
via coarse analog RC and LC filters (some built into the SDR receiver), and then via a high-order
digital band-pass filter. We then demodulated the filtered signal using a discrete Hilbert transform
and applied a low-pass filter, yieldinga demodulated trace as shown in Figure 5(a).

14

Page 15

Figure 3: A shielded loop antenna (handheld) connected to the the attacker’s computer through
an SDR receiver (right), attacking a Lenovo 3000 N200 target (left).

Signal Distortions. In principle, only a single demodulated trace is needed per chosen ciphertext,
if measurment is sufficiently robust. However, the signals obtained with our setup (especially those
recorded from afar) have insufficient signal-to-noise ratio for reliable information extraction.

Moreover, there are various distortions afflicting the signal, making straightforward key extrac-
tion difficult. The signals are corrupted every 15 msec, by the 64 Hz timer interrupt on the target
laptop. Each interrupt event corrupts the trace for a duration of several exponent bits, and may
also create a time shift relative to other traces (see Figures 5(b) and 6(a)). In addition, many traces
exhibit a gradual drift, increasing the time duration between two adjacent peaks (relative to other
traces), making signal alignment even more problematic (see Figure 6(b)).

The attack of [GPT14], targeting square-and-always-multiply exponentiation, overcame inter-
rupts and time drift using the fact that every given stage in the decryption appears in non-corrupted
form in most of the traces. They broke the signal down into several time segments and aligned
them using correlation, thereby resolving shift issues. Noise was suppressed by averaging the
aligned segments across all signals. Since, in their case, the baseband signal reflected a sequence of
random-looking key bits, correlation proved sufficient aligning trace segments.

However, such correlation-based alignment and averaging is inadequate for sliding-window ex-
ponentiation. Here, the demodulated traces are mostly periodic, consisting of a train of similar
peaks that change only when the corresponding table index is used for multiplication. Correlat-
ing nearly-periodic signals produces an ambiguity as to the actual shift compensation required for
proper alignment; it is also not very robust to noise.

The problem is exacerbated by the low bandwidth of the attack: had we (expensively) performed
clockrate-scale measurments, consecutive peaks would likely have been distinguishable due to fine-
grained data dependency, making alignment via segment correlation viable.

Aligning the Signals. As a first attempt to align the signals and correct distortions, we applied
the “Elastic Alignment” [vWWB11] algorithm to the demodulated traces; however, for our signals
the results were very unreliable. For more robust key extraction, we used a more problem-specific
algorithm.

Initial Synchronization. We started by aligning all traces belonging to identical decryption
operations using a short segment in the very beginning of each trace, before the start of the
modular exponentiation operation. This segment is identical in all traces, making it suitable as
a trigger for the alignment. All traces were aligned via correlation relative to a reference trace,

15

Page 27

[CJ01] Christophe Clavier and Marc Joye. Universal exponentiation algorithm. In CHES,
pages 300–308. Springer, 2001.

[CJRR99] Suresh Chari, Charanjit S. Jutla, Josyula R. Rao, and Pankaj Rohatgi. Towards
sound approaches to counteract power-analysis attacks. In CRYPTO, pages 398–412.
Springer, 1999.

[CMR+13] Shane S. Clark, Hossen A. Mustafa, Benjamin Ransford, Jacob Sorber, Kevin Fu, and
Wenyuan Xu. Current events: Identifying webpages by tapping the electrical outlet.
In ESORICS, pages 700–717, 2013.

[Cop97] Don Coppersmith. Small solutions to polynomial equations, and low exponent RSA
vulnerabilities. J. Cryptology, 10(4):233–260, 1997.

[CRI12] SPA/SEMA vulnerabilities of popular rsa-crt sliding window implementations, 2012.
CHES rump session. URL: https://www.cosic.esat.kuleuven.be/ches2012/ches_
rump/rs5.pdf .

[ElG85] Taher ElGamal. A public key cryptosystem and a signature scheme based on discrete
logarithms. IEEE Transactions on Information Theory, 31(4):469–472, 1985.

[Eni] The Enigmail Project. Enigmail: A simple interface for OpenPGP email security. URL:
https://www.enigmail.net .

[ETLR01] M. Elkins, D. Del Torto, R. Levien, and T. Roessler. MIME security with OpenPGP.
RFC 3156, 2001. URL: http://www.ietf.org/rfc/rfc3156.txt .

[FKM+06] Pierre-Alain Fouque, Sébastien Kunz-Jacques, Gwenaëlle Martinet, Frédéric Muller,
and Frédéric Valette. Power attack on small RSA public exponent. In CHES, pages
339–353, 2006.

[Fun] FUNcube Dongle. URL: http://www.funcubedongle.com .

[GMO01] Karine Gandolfi, Christophe Mourtel, and Francis Olivier. Electromagnetic analysis:
concrete results. In CHES, pages 251–261, 2001.

[Gmp] GNU multiple precision arithmetic library. URL: http://gmplib.org/ .

[Gnu] GNU Radio. URL: http://gnuradio.org .

[Gou05] L. Goubin. Method for protecting an electronic system with modular exponentiation-
based cryptography against attacks by physical analysis, 2005. US Patent 6,973,190.

[Gpga] GNU Privacy Guard. URL: https://www.gnupg.org .

[Gpgb] GnuPG Frontends. URL: https://www.gnupg.org/related_software/frontends.
html .

[GPT14] Daniel Genkin, Itamar Pipman, and Eran Tromer. Get your hands off my laptop:
Physical side-channel key-extraction attacks on pcs. In CHES, pages 242–260, 2014.

[GST13] Daniel Genkin, Adi Shamir, and Eran Tromer. RSA key extraction via low-bandwidth
acoustic cryptanalysis (extended version). IACR Cryptology ePrint Archive, 2013:857,
2013. Extended version of [GST14].

[GST14] Daniel Genkin, Adi Shamir, and Eran Tromer. RSA key extraction via low-bandwidth
acoustic cryptanalysis. In CRYPTO, pages 444–461 (vol. 1), 2014. See [GST13] for
extended version.

[HIM+13] Johann Heyszl, Andreas Ibing, Stefan Mangard, Fabrizio De Santis, and Georg Sigl.
Clustering algorithms for non-profiled single-execution attacks on exponentiations. In
Smart Card Research and Advanced Applications - CARDIS 2013, pages 79–93, 2013.

[HMA+08] Naofumi Homma, Atsushi Miyamoto, Takafumi Aoki, Akashi Satoh, and Adi Shamir.
Collision-based power analysis of modular exponentiation using chosen-message pairs.
In CHES, pages 15–29, 2008.

27

Page 28

[KJJR11] Paul Kocher, Joshua Jaffe, Benjamin Jun, and Pankaj Rohatgi. Introduction to differ-
ential power analysis. Journal of Cryptographic Engineering, 1(1):5–27, 2011.

[KO62] A. Karatsuba and Y. Ofman. Multiplication of many-digital numbers by automatic
computers. Proceedings of the USSR Academy of Sciences, 145:293–294, 1962.

[Koc96] Paul C. Kocher. Timing attacks on implementations of diffie-hellman, RSA, DSS, and
other systems. In CRYPTO, pages 104–113, 1996.

[Mic] Making your own smartphone cable. URL: http://en.wiki.backyardbrains.com/
index.php?title=Making_your_own_Smartphone_Cable.

[Min] Minimalist GNU for Windows. URL: http://www.mingw.org.

[MIT14] MITRE. Common vulnerabilities and exposures list, entry CVE-2014-3591, 2014. URL:
http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-3591.

[MOP07] Stefan Mangard, Elisabeth Oswald, and Thomas Popp. Power Analysis Attacks —
Revealing the Secrets of Smart Cards. Springer, 2007.

[MVO96] Alfred J. Menezes, Scott A. Vanstone, and Paul C. Van Oorschot. Handbook of Applied
Cryptography. CRC Press, Inc., Boca Raton, FL, USA, 1st edition, 1996.

[OS06] Yossi Oren and Adi Shamir. How not to protect PCs from power
analysis, 2006. CRYPTO rump session. URL: http://iss.oy.ne.ro/
HowNotToProtectPCsFromPowerAnalysis.

[OST06] Dag Arne Osvik, Adi Shamir, and Eran Tromer. Cache attacks and countermeasures:
The case of AES. In CT-RSA, pages 1–20, 2006.

[Per05] Colin Percival. Cache missing for fun and profit. Presented at BSDCan, 2005. URL:
http://www.daemonology.net/hyperthreading-considered-harmful.

[QS01] Jean-Jacques Quisquater and David Samyde. Electromagnetic analysis (EMA): Mea-
sures and counter-measures for smart cards. In E-smart’01, pages 200–210, 2001.

[RSA78] Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digi-
tal signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–
126, 1978.

[RTL] Soft66RTL. URL: http://zao.jp/radio/soft66rtl.

[Smi99] D.C. Smith. Signal and noise measurement techniques using magnetic field probes.
In IEEE International Symposium on Electromagnetic Compatibility, volume 1, pages
559–563, 1999.

[vWWB11] Jasper G. J. van Woudenberg, Marc F. Witteman, and Bram Bakker. Improving
differential power analysis by elastic alignment. In Aggelos Kiayias, editor, CT-RSA,
pages 104–119. Springer, 2011.

[Wal01] Colin D. Walter. Sliding windows succumbs to Big Mac attack. In CHES, pages
286–299, 2001.

[YF14] Yuval Yarom and Katrina Falkner. FLUSH+RELOAD: A high resolution, low noise,
L3 cache side-channel attack. In USENIX Security Symposium, pages 719–732, 2014.

[YLG+ 15] Yuval Yarom, Fangfei Liu, Qian Ge, Gernot Heiser, and Ruby B. Lee. Last-level cache
side-channel attacks are practical. In IEEE Symposium on Security and Privacy (S&P),
2015.

[ZP14] A. Zajic and M. Prvulovic. Experimental demonstration of electromagnetic information
leakage from modern processor-memory systems. IEEE Transactions on Electromag-
netic Compatibility, 56(4):885–893, 2014.

28

Similer Documents