Get your hands off my laptop: physical side-channel key-extraction attacks on PCs

Abstract

We demonstrate physical side-channel attacks on a popular software implementation of RSA and ElGamal, running on laptop computers. Our attacks use novel side channels, based on the observation that the “ground” electric potential, in many computers, fluctuates in a computation-dependent way. An attacker can measure this signal by touching exposed metal on the computer’s chassis with a plain wire, or even with a bare hand. The signal can also be measured on the ground shield at the remote end of Ethernet, USB and display cables. Through suitable cryptanalysis and signal processing, we have extracted 4096-bit RSA keys and 3072-bit ElGamal keys from laptops, via each of these channels, as well as via power analysis and electromagnetic probing. Despite the GHz-scale clock rate of the laptops and numerous noise sources, the full attacks require a few seconds of measurements using Medium Frequency (MF) signals (around 2 MHz), or one hour using Low Frequency (LF) signals (up to 40  kHz).

1 Introduction

1.1 Background

Side-channel attacks that exploit unintentional and abstraction-defying information leakage from physical computing devices have proven effective in breaking the security of numerous cryptographic implementations [4, 23, 26]. However, most research attention has been focused on small devices: smartcards, RFID tags, FPGAs, microcontrollers, and simple embedded devices. The “PC” class of devices (commodity laptop/desktop/server computers) has been studied from the perspective of side channels measured by resident software (see [20] and subsequent works) and from peripherals (e.g., [25]).

PCs, however, have received little academic attention with regard to physical emanations from cryptographic computations, presumably due to three main barriers. First, PCs have highly complicated system architecture and CPU micro architecture, with many noise sources and asynchronous events. Fine low-level events are thus difficult to model and measure. Second, most physical side-channel cryptanalysis approaches require the leakage signal to be acquired at rates well beyond the device’s clock rate; for multi-GHz CPUs, the requisite equipment is expensive, and the signals are difficult to probe. Finally, attack scenarios differ: the aforementioned small devices are often deployed into potentially malicious hands, where they could be subjected to lengthy or invasive attacks; but for PCs, the typical scenario (short of theft) is where a physical attacker gains physical proximity for a restricted amount of time, and must operate surreptitiously.

Recently, a key extraction attack on PCs was demonstrated using the acoustic side channel, addressing all three barriers: using a chosen-ciphertext attack, the sound emanations of interest are made very robust, brought down to very low frequencies (tens or hundreds of kHz), and extended to long durations (hundreds of milliseconds), making it possible to record the leakage surreptitiously and non-invasively, by a cellphone microphone or from many meters away [18].

We thus study the question: what other physical, non-invasive, cryptanalytic side-channel attacks can be effectively conducted on full-blown PC computers?

1.2 Our results

In this paper,¹ we describe key extraction of 4096-bit RSA and 3072-bit ElGamal keys from laptop computers of various models. The attacked software implementation is GnuPG [2], a popular open source implementation of the OpenPGP standard [8]. The attacks exploit several side channels, enumerated below (along with examples of attack scenarios):

• 1. Chassis potential We identify a new side channel: fluctuations of the electric potential on the chassis of laptop computers, in reference to the mains earth ground. This potential can be measured by a simple wire, non-invasively touching a conductive part of the laptop, and connected to a suitable amplifier and digitizer. (This, essentially, creates a ground loop through the laptop and measures its voltage.) The chassis potential, thus measured, is affected by ongoing computation, and our attacks exploit this for extracting RSA and ElGamal keys, within a few seconds.

  Scenarios: The probe wire can be fixed in advance in a location where the target laptop will be placed (e.g., a cluttered desk), or put in contact with the laptop by a passerby.

• 2. Far end of cable The chassis potential can also be observed from afar, through any cable with a conductive shield that is attached to an I/O port on the laptop. For example, we demonstrated key recovery through a 10-meter long Ethernet cable, by tapping the cable shield at the remote Ethernet switch (see Fig. 13). Similar observations apply to USB, VGA, HDMI, etc. Since only the shield potential is used, the attack is oblivious to the data passing through the cable, and works even if the port is disabled.

  Scenarios: While many users are careful about connecting suspicious devices (such as USB sticks) to the physical ports of their machines, they will routinely connect VGA display cables to their laptops. Likewise, users often connect Ethernet cables to their laptop computers when an adequate firewall is configured or when the environment appears trustworthy. However, a simple voltage measurement device, perhaps located in the cabinet or server room to which the cable leads, could be capturing the leakage. This is hard to check, since Ethernet wiring and projectors’ VGA cables are often hidden out of sight and cannot easily be tracked.

• 3. Human touch Surprisingly, the requisite signal can be measured, with sufficient fidelity, even through a human body. An attacker merely needs to touch the target computer with his bare hand, while his body potential is measured.

  Scenarios: The attacker positions himself in physical proximity to the target laptop and, under some ruse, touches it with his bare hand or a conducting pen (see Fig. 14). Surreptitiously, the attacker carries the requisite equipment for measuring his body potential relative to some nearby grounded object. In the non-adaptive attack (see below), a few seconds’ contact will suffice; in the adaptive attack, 1 key bit can be extracted approximately every 4 seconds of contact. Note that the above attacks all rely on fluctuations in the PC’s ground (relative to the mains earth ground). This makes mitigation difficult: the usual method for preventing voltage fluctuations, using bypass capacitors to shunt stray AC currents into the device ground, does not apply to the device ground itself. We also revisit two traditional physical side channels, and demonstrate their applicability to software running on PCs:

• 4. Electromagnetic (EM) We performed key extraction by measuring the induced EM emanations, using a near-field probe placed near the laptop.

  Scenarios: Electromagnetic probes are easily hidden in nearby objects. A glove, containing a concealed probe loop and hovering over the target laptop, would unveil its key within seconds.

• 5. Power. Likewise, we extracted keys by measuring the current draw on the laptop’s power supply. Our attack works even though PCs use complex switching power supplies, which partially decouple the power source from the CPU load,² and moreover employ large capacitors, chokes, and shields for electromagnetic compatibility (EMC) compliance—all of which attenuate and disrupt the signals sought in traditional power analysis.

  Scenarios: A public charging station can be easily augmented with a current meter, logger, and transmitter. Even a regular power supply “brick” can be similarly augmented, and such laptop power supplies are often shared, offered to guests, or left unattended.

Our attacks require very low bandwidth, well below the laptop CPU’s GHz-scale clock rate. We use two cryptanalytic approaches, based on known techniques and adapted to the target software:

Fast, non-adaptive Medium Frequency attack For both RSA and ElGamal key extraction, we can exploit signals circa 2 MHz (medium frequency band), using the “$n-1$” non-adaptive chosen-ciphertext simple-power-analysis attack of Yen et al. [39]. Key extraction then requires a few seconds of measurements.

Slow, adaptive VLF/LF attack For RSA key extraction, we can exploit signals of about 15–40 kHz (very low frequency/low frequency bands), using the adaptive chosen-ciphertext attack of [18]. Full 4096-bit RSA key extraction then takes approximately 1 h, but is very robust to low signal-to-noise ratio.

Our results require careful choice and tuning of the signal acquisition equipment, to attain usable signal-to-noise ratio in the presence of abundant noise, delicate grounding, and impedance-matching considerations. We report these choices in detail and describe the requisite signal processing. We also analyze the code of GnuPG’s mathematical library, showing why the specific chosen ciphertext creates exploitable, key-dependent leakage in this implementation.³

1.3 Vulnerable software and hardware

Hardware We have tested various laptop computers, of different models, by various vendors. The signal quality varied dramatically, as did the relative quality between channels, the carrier frequencies of interest, the best placement of the probes or human hand, and the optimal grounding connection. Thus, manual calibration and experimentation were required. Generally, instruction-dependent leakage occurs on most laptops; key extraction is possible on many laptops, but the requisite signal-to-noise is not always present. Heavily used laptops appear to exhibit stronger information-bearing signals.

GnuPG For this case study, we focused on GnuPG version 1.4.15, running on Windows XP and compiled with the MinGW GCC version $4.6.2$. This version of GnuPG was the most recent when our research was publicly announced. Following the practice of responsible disclosure, we worked with the authors of GnuPG to suggest several countermeasures and verify their effectiveness against our attacks (including those described in [18]; see discussion therein as well as CVE-2013-4576 [28]). GnuPG 1.4.16, released concurrently with the public announcement of our results, contains these countermeasures.⁴

Chosen ciphertext injection Our key extraction attacks require chosen ciphertexts (either adaptive or non-adaptive, depending on the attack). As observed in [18], one way to remotely inject such ciphertexts into GnuPG is to send them as a PGP/MIME-encoded e-mail [13], to be automatically decrypted by the Enigmail [14] plugin for the Mozilla Thunderbird e-mail client. In the case of the non-adaptive attack, the attacker can provide the chosen ciphertext files to the victim (by any means or guise), and merely needs to conduct the measurement, for a few seconds, when those files are decrypted.

1.4 Related work

Power analysis attacks were introduced by Kocher et al. [22], and applied to both symmetric and asymmetric ciphers, implemented on hardware such as smartcards, microcontrollers and FPGAs (see [4, 23, 26] and the references therein).

Clark et al. [9] observed that is it possible to use power analysis to identify, with high probability, the web pages loaded by a web browser on the target machine, by tapping the AC electrical outlet to which the target is connected.

Oren and Shamir [30] observed that the power line voltage on USB ports exhibits a distinct signature when OpenSSL RSA decryption executes, even when the port is disabled; this property is shared by our “far end of cable” channel. Schmidt et al. [34] observed leakage through voltage variations on the I/O pins of embedded devices.

Basic multiplication instructions were shown to have operand-specific leakage, in simulation [36] and embedded devices [11] (though this was not demonstrated or exploited on PCs).

The electromagnetic side channel has been studied and exploited for smartcards and FPGAs (e.g., [3, 16, 33]), including for RSA. More recently, Zajic and Prvulovic [40] observed electromagnetic leakage from laptop and desktop computers (but did not show cryptographic applications). Timing attacks have been shown on software implementations of DSS, RSA, and ECDSA [6, 7, 24, 37]. Cache attacks [5, 31, 32] were applied to GnuPG’s RSA implementation [38].

1.5 Paper outline

The remainder of this paper is organized as follows. Section 2 establishes the presence of computation-dependent side-channel leakage via fluctuations of computers’ chassis potential. Section 3 presents and analyzes the fast, non-adaptive MF attack. Section 4 recalls the slow, adaptive VLF/LF attack. Section 5 reports experimental key-extraction results, using both attacks, applied to the five aforementioned channels. Section 6 concludes and discusses countermeasures.

2 Computation-dependent chassis-potential leakage

The electric potential on a laptop computer’s chassis (metal panels, shields and ports) is ideally equal to that of the mains earth ground potential, but in reality it fluctuates greatly. Even when the laptop is grounded (via its power supply connector or via shielded cables such as Ethernet, USB, VGA or audio), there is non-negligible impedance between the grounding point(s) and other points in the chassis. Voltage, often 10 mV RMS or more,⁵ develops across this impedance, in part due to currents and electromagnetic fields inside the computer. Since the latter depend on the ongoing computation, a natural question is whether information about the ongoing computation can be learned by measuring the chassis potential.

In this section, we observe elementary correlations between the chassis potential (observed in various ways) and the operations performed by the target machine. These operations include individual CPU operations, as well as various public key operations such as decryption and signing. We show that it is possible for an attacker to obtain information about the operations executed by the target machine, as well as some information about the secret keys. Later (Sect. 5), we discuss the hardware setup in detail, describe additional leakage channels, and show that each of these channels can be used for key-extraction attacks on GnuPG’s implementation of RSA and ElGamal.

2.1 Code-dependent leakage

We first demonstrate leakage of information about which instructions are executed by the CPU of the target computer. As in [18], we let the target computer run a simple program that executes (partially unrolled) loops containing one of the following $\mathsf{x86}$ instructions: $\mathsf{HLT}$ (CPU sleep), $\mathsf{MUL}$ (integer multiplication), $\mathsf{FMUL}$ (floating-point multiplication), memory access (forcing L1 and L2 cache misses, so they reach DRAM), and $\mathsf{REP \ NOP}$ (short-term idle). Figure 1 shows a recording of one target computer’s chassis potential, while this program is running; different types of operations can be easily distinguished.

Fig. 1

Frequency spectrogram of the chassis potential, while running different CPU operations using a Lenovo 3000 N200 laptop. The horizontal axis is frequency (2–2.3 MHz), the vertical axis is time (10 s), and intensity is proportional to the instantaneous energy in that frequency band

Leakage on other machine models is demonstrated in Fig. 2. Moreover, similar effects can be observed by measuring EM emanations or by touching the laptop’s chassis and measuring the attacker’s body potential (see Fig. 3).

Fig. 2

Chassis measurements of various target computers performing $\mathsf{MUL}$, $\mathsf{HLT}$ and $\mathsf{MEM}$ in this order. Note that the three operations can be distinguished on all machines. a Dell Latitude E6400, b Gateway W340UA, c Lenovo ThinkPad T61, d HP HDX 18

Fig. 3

Frequency spectrogram (1.1 s, 2–2.3 MHz) of a recording of different CPU operations obtained while measuring the attacker’s body potential while touching an exposed part of the chassis of a Lenovo 3000 N200 laptop

2.2 GnuPG key distinguishability

The leakage via chassis potential and electromagnetic emanations is also applicable to cryptographic code. In this section, we show a very simple (yet already troubling) form of leaked information: determining which of several randomly generated secret keys was used by the target machine, for a signing or decryption operation. For brevity, in the remainder of this section we discuss chassis potential measurements; similar effects are also present when using the EM side channel. Our evaluation follows the methodology of [18].

Distinguishing RSA secret keys Figure 4 depicts the spectrogram of four GnuPG RSA signing operations, using different 4096-bit random keys, on a fixed message. Each signing operation is preceded by a short CPU sleep (for visual separation).

Fig. 4

Chassis measurement (1.7 s, 1.9–2.6 MHz) of four GnuPG RSA signatures executed on a Lenovo 3000 N200. The transitions between $p$ and $q$ are marked with yellow arrows (color figure online)

The different signing keys can be clearly distinguished by their subtly different spectral signatures (which may itself be of practical interest). Another telling detail is visible: halfway through each signing operation, a transition appears at several frequency bands (marked with yellow arrows). This transition corresponds to the transition between exponentiation modulo the secret $p$ to exponentiation modulo the secret $q$, in the RSA decryption implementation of GnuPG, which is based on the Chinese Remainder Theorem. We can thus spectrally observe internal, secret-dependent information within the signing operation.

ElGamal key distinguishability Another popular public key encryption scheme is ElGamal encryption [12]. Recall that in ElGamal encryption, the key generation algorithm consists of generating a large prime $p$, a generator $\alpha$ of $\mathbb {Z}^*_p$, and a secret exponent $a \in \mathbb {Z}^*_p$. The public key is $\mathsf{pk }=(p,\alpha ,\alpha ^a)$ and the secret key is $\mathsf{sk }= a$. Encryption of a message $m$ outputs a pair $(\gamma ,\delta )$, where $\gamma = \alpha ^k \hbox { mod }p$ and $\delta = m \cdot \left( \alpha ^a\right) ^k \hbox { mod }p$ for random $k$. Decryption of $(\gamma ,\delta )$ outputs $\gamma ^{-a} \cdot \delta \hbox { mod }p$. Figure 5 presents a recording of four ElGamal decryptions, using a fixed message $m$ and randomly generated keys with $3072$-bit primes $p$. As in the RSA case, the four decryptions are clearly visible, and the four different keys can be easily distinguished.

Fig. 5

Chassis measurement (0.20 s, 0–20 kHz) of four ElGamal decryptions using the same message and randomly generated $3072$-bit keys, on a Lenovo ThinkPad T61

3 Non-adaptive attack

We proceed to describe our cryptanalytic attack techniques (whose applicability will be shown in Sect. 5). The first technique is a non-adaptive chosen ciphertext attack using very few traces, following the simple power analysis of RSA (see [15, 19, 22, 27, 29, 39], the surveys [4, 23, 26], and the references therein). We begin by reviewing the high-level modular exponentiation algorithm in GnuPG (Sect. 3.1), describe our attack (Sect. 3.2) exploiting this algorithm, and then analyze its success by recalling the inner squaring routines used by GnuPG (Sect. 3.3) and their behavior under the attack (Sect. 3.4).

3.1 GnuPG’s modular exponentiation routine

To perform arithmetic on the large integers occurring in RSA and ElGamal, GnuPG uses an internal mathematical library called MPI (based on GMP [1]). MPI stores large integers as arrays of limbs, i.e., 32-bit words (on the x86 architecture used in our tests).

We now review the modular exponentiation routine of GnuPG (as introduced in GnuPG v1.4.14), which is used for both RSA and ElGamal. GnuPG uses a variant of the square-and-multiply modular exponentiation algorithm, processing the bits of the exponent from the most significant bit to the least significant one. To mitigate a cache side-channel attack of [38], GnuPG now always performs the multiplication operation in every loop iteration regardless of the exponent’s bits (but only uses the result as needed). The pseudocode is given in Algorithm 1. The operation returns the number of limbs in the $t$-bit number $x$, namely $\lceil t/32 \rceil$. This top-level exponentiation routine suffices for the high-level description of our attack. For details about GnuPG’s underlying squaring routines, necessary for understanding the attack’s success, see Sects. 3.3 and 3.4.

3.2 The attack algorithm

Since GnuPG 1.4.15 attempts to avoid correlation between the bits of the exponent and high-level operations (such as multiplication), we use a chosen ciphertext attack to create correlations between these bits and intermediate values computed inside the low-level operations inside GnuPG’s modular exponentiation routine. Moreover, the chosen ciphertext will have an amplification effect, whereby numerous recursive calls will be similarly affected, resulting in a distinct leakage signal over a long time period. This is the key for successfully conducting a MHz-scale attack on a GHz-scale computation.

The technique of Yen et al. [39] is particularly suitable. In the case of both RSA-CRT and ElGamal, it chooses a ciphertext $c$ such that $a \equiv -1 \pmod p$ during the execution modular_exponentiation (Algorithm 1) above. Within GnuPG, this ciphertext creates a correlation between the bits of the secret exponent $b$ and the number of zero limbs of $m$, as described next. As we analyzed in Sects. 3.3 and 3.4, the number of zero limbs inside $m$ drastically affects the control flow inside the GnuPG basic squaring routine,thus creating discernible differences in the physical leakage.

Note that, for $a \equiv -1 \pmod p$, the value of $m$ during the execution of modular_exponentiation is always either $1$ or $-1$ modulo $p$. Thus, the value of $m$ in line 7 does not depend on the bits of $b$, and is always $1$ modulo $p$ (since $-1^2 \equiv 1^2 \equiv 1 \pmod p$). Consequently, the following correlation holds between the value of $m$ at the start of the $i$th iteration of the loop in line 5 and $b_{i-1}$.

• $b_{i-1} = 0$. In this case, the branch on line 8 was not taken; thus, the value of $m$ at the start of the $i$th iteration of the loop in line 5 is also $m=1 \hbox { mod }p=1$. Next, since GnuPG’s internal representation does not truncate leading zeros, it holds that the value $m$ sent to the squaring routine during the $i$-th iteration contains many zero limbs.

• $b_{i-1} = 1$. In this case, the branch on line 8 was taken, so the value of $m$ at the start of the $i$th iteration of the loop in line 5 is $m=-1 \hbox { mod }p=p-1$. Since $p$ is a random large prime, the value $m$ sent to the squaring routine during the $i$th iteration contains very few zero limbs.

We now proceed to describe the specific ciphertext choices required for our attack for both the RSA and ElGamal case.

Ciphertext choice for RSA-CRT Recall that in the case of RSA decryption, GnuPG first computes $c^{d\,\mathrm{mod}\,(p-1)} \hbox { mod }p$ and $c^{d\,\mathrm{mod}\,(q-1)} \hbox { mod }q$, and then combines these via the Chinese Remainder Theorem. By choosing $c=n-1$ where $n=pq$ is the public RSA modulus, the modular reduction in line 3 is always triggered, causing the value of $a$ in line 5 to be $p-1$ (i.e., $-1$ modulo $p$ as desired).

Ciphertext choice for ElGamal For ElGamal encryption, the prime modulus $p$ is part of the public key, so we directly choose the ciphertext to be $p-1$.

3.3 GnuPG’s squaring routine

GnuPG’s large-integer squaring routine combines two squaring algorithms: a basic quadratic-complexity squaring routine, and a variant based on a recursive Karatsuba multiplication algorithm [21]. The chosen combination of algorithms is based on the size of the operands, measured in whole limbs. We will first discuss the basic squaring algorithm and its key-dependent behavior, and then show how this behavior is preserved by the Karatsuba squaring.

GnuPG’s basic squaring routine The core side-channel weakness we exploit in GnuPG’s code lies inside the basic squaring routine. The basic squaring routine used by GnuPG is a simple, quadratic-complexity “grade school” squaring, with optimizations for multiplication by limbs equal to 0 or 1, depicted in Algorithm 2.

Note how sqr_basecase handles zero limbs of $a$. In particular, when a zero limb of $a$ is encountered, none of the operations mul_by_single_limb, add_with_offset and mul_and_add_with_offset are performed and the loop in line 9 continues to the next limb of $a$. Our attack exploits this, by causing the number of such zero limbs to depend on the current bit of the secret exponent, thus affecting the control flow in lines 3 and 11, and thereby the side-channel emanations.

GnuPG’s Karatsuba squaring routine The basic squaring routine described above is invoked via two code paths: directly by the modular exponentiation routine (Sect. 3.1) when the operand is small, and also as the base-case by the Karatsuba squaring routine. The latter is a variant of the Karatsuba multiplication algorithm [21], relying on the identity:

$$\begin{aligned} a^2 = {\left\{ \begin{array}{ll} (2^{2n}+2^n) a_\mathsf{H}^2 -2^n(a_\mathsf{H}-a_\mathsf{L})^2 &{} \\ \quad + (2^n+1)a_\mathsf{L}^2 &{} \text{ if } a_\mathsf{H} > a_\mathsf{L}\\ (2^{2n}+2^n) a_\mathsf{H}^2 -2^n(a_\mathsf{L}-a_\mathsf{H})^2 &{} \\ \quad + (2^n+1)a_\mathsf{L}^2 &{} \text{ otherwise } \end{array}\right. } \end{aligned}$$

(1)

where $a_\mathsf{H},a_\mathsf{L}$ are the most and least significant halves of $a$, respectively.

3.4 Attack analysis

In this section, we analyze the effects of our attack on sqr_basecase (Algorithm 2). Recall that in Sect. 3.2, we created a correlation between the $i$th bit of the secret exponent $b_i$ and the number of zero limbs in the operand $m$ of the squaring routine during iteration $i+1$ of the main loop of the modular exponentiation routine. Concretely, for the case where $b_i=1$, we have that $m= -1 \hbox { mod }p = p-1$ is a random-looking number containing several thousand bits (2048 bits for the case of RSA and 3072 bits for the case of ElGamal). Conversely, for the case where $b_i=0$, we have that $m=1 \hbox { mod }p = 1$ and, since GnuPG does not truncate leading zeros, the representation of $m$ is a large number (2048 bits for the case of RSA and 3072 bits for ElGamal), all of whose limbs are 0 (except for the least significant).

The code of GnuPG passes $m$ directly to the Karatsuba squaring routine. Notice that for the case where $b_i=1$, since $m$ is a random-looking number, this property of $m$ will be preserved in all three recursive calls (computing the three squaring operations in Eq. 1). Similarly, for the case of $b_i=0$, we have that $m=1$, meaning $m_\mathsf{H} =0$ and $m_\mathsf{L}=1$. Thus, the second case of Eq. 1 will always be taken, again preserving the structure of $m$ as having mostly zero limbs, in all three recursive calls.

When reaching the recursion’s base case, we have the following dependence on $b_i$. If $b_i=0$, then the values of the operand of sqr_basecase during iteration $i+1$ of the main loop of modular_exponentiation (in all branches of the recursion) will have almost all of their limbs equal to zero. Conversely, if $b_i=1$, then the values of the operand of sqr_basecase during iteration $i+1$ of the main loop of modular_exponentiation in all branches of the recursion will be random-looking. Thus, by (indirectly) measuring the instructions executed by sqr_basecase, we shall deduce the number of zero limbs in its operand and deduce $b_i$.

Confirming this, Fig. 6 presents the number of zero limbs in the operand of sqr_basecase during each iteration of the main loop of the modular exponentiation routine using our chosen ciphertext and five randomly generated keys. The values of the first 50 bits of the exponent are clearly visible (many zero limbs during the $i$th iteration implies that the $i-1$th bit of the secret exponent is $0$).

Fig. 6

Number of zero limbs in the operand of sqr_basecase($a$) during an execution of the modular exponentiation routine, using our attack and randomly generated keys. Whenever the $i-1$th bit of the secret exponent is $0$, there are $189$ zero limbs during the squaring; otherwise, there are none

Next, recall the effect of zero limbs in the operand on the code of sqr_basecase. Note that the control flow in sqr_basecase depends on the number of non-zero limbs in its operand. The drastic change in the number of zero limbs in the operand of sqr_basecase is detectable by our side-channel measurements. Thus, we are able to leak the bits of the secret exponent by creating the correlation between its bits and the number of zero limbs in the operand of sqr_basecase, using our carefully chosen cipher text.

4 Adaptive attack

Our other cryptanalytic technique is an adaptive chosen-ciphertext side-channel attack, which extracts, bit by bit, the prime modulus used during the CRT-based RSA modular exponentiation routine. Our attack on GnuPG was introduced in [18] (following [7]) for the GnuPG acoustic side channel. For self-containment, we give an overview here. (This attack is not applicable to ElGamal, where the prime modulus $p$ is public.) The attack recovers the bits of $p=p_1 \ldots p_k$ iteratively, starting with the MSB $p_1$. Once we learn all of $p$, we know the factorization of $n$. Moreover, after recovering just the top half of the bits of $p$, it is possible to use Coppersmith’s attack [10] to recover the remaining bits.

Ciphertext choice for RSA In GnuPG, the MSB is always set, i.e., $p_{k}=1$. Assume that we have already recovered the topmost $i-1$ bits of $p$. To extract the next bit $p_i$, we check the two hypotheses about its value, by requesting decryption of an adaptively chosen ciphertext $g^{i,0}+n$, where $g^{i,0}=p_1\cdots p_{i-1}10\cdots 0$ ($k$ bits in total). Let $n=pq$ be the public RSA modulus. Consider the RSA decryption of $g^{i,0}+n$. Two cases are possible, depending on $p_i$.

• $p_i=1$. Then, $g^{i,0} < p.$ The ciphertext $g^{i,0}+n$ is passed as the variable $a$ to Algorithm 1. Since $n=pg$ is the product of two equal-sized primes, $g^{i,0}+n$ has a larger limb count than $p$. This triggers the modular reduction of $a$ in line 3 of Algorithm 1, which returns $g^{i,0}$, resulting in $a$ being a $k$-bit number having mostly zero limbs. Next, $a$ is passed to the multiplication routine in line 5.

• $p_i=0$. Then, $p < g^{i,0}$ and as in the previous case, $g^{i,0}+n$ is passed as the variable $a$ to Algorithm 1 triggering the modular reduction of $a$ in line 3. Since $g^{i,0}$ and $p$ share the same topmost $i-1$ bits, we have that $g^{i,0} < 2p$, and the reduction results in $a=g^{i,0} - q$, which is a $(k-i)$-bit random-looking number. This is then passed to the multiplication routine in line 5.

Code analysis We now present a high-level analysis of how our bit-by-bit chosen ciphertext attack affects the code of GnuPG. Using the above-described ciphertexts, the second operand of the multiplication routine during the entire execution of the main loop of the modular exponentiation routine will be either full-size and repetitive or shorter and random-looking (depending on the value of $p_i$).⁶

GnuPG’s uses two algorithms for large integer multiplication: the Karatsuba-based multiplication algorithm and the grade-school (quadratic-time) multiplication algorithm. GnuPG’s variant of Karatsuba recursive multiplication relies on the identity $ab = (2^{2n}+2^n) a_\mathsf{H} b_\mathsf{H} +2^n(a_\mathsf{H}-a_\mathsf{L})(b_\mathsf{L}-b_\mathsf{H}) + (2^n+1)a_\mathsf{L} b_\mathsf{L}$, where $a_\mathsf{H}, b_\mathsf{H}$ are the most significant halves of $a$ and $b$, respectively, and $a_\mathsf{L},b_\mathsf{L}$ are the least significant halves of $a$ and $b$, respectively. We thus see that GnuPG’s Karatsuba multiplication preserves the structure of $a$ as being either random looking or containing many zero limbs. That is, if $a$ is random looking, then $a_\mathsf{H} b_\mathsf{H}$, $(a_\mathsf{H}-a_\mathsf{L})(b_\mathsf{L}-b_\mathsf{H})$ and $a_\mathsf{L} b_\mathsf{L}$ are random-looking as well. Conversely, if $a$ contains mostly zero limbs, the values of $a_\mathsf{H} b_\mathsf{H}$, $(a_\mathsf{H}-a_\mathsf{L})(b_\mathsf{L}-b_\mathsf{H})$ and $a_\mathsf{L} b_\mathsf{L}$ also contain mostly zero limbs.

Next, when the recursion reaches its base case (when multiplying numbers of 15 limbs or less), GnuPG passes $a$ to the basic multiplication routine. GnuPG’s basic multiplication routine is implemented similarly to Algorithm 2. In particular, it includes optimizations for zero limbs similar to lines 3 and 11 of Algorithm 2. Thus, we are able to leak the bits of $p$, one bit at a time, by creating a correlation between the current bit of $p$ and the number of zero limbs in the second operand of GnuPG’s basic multiplication routine using our chosen ciphertexts.

Confirming this, Fig. 7 shows the number of zero limbs in the second operand of GnuPG’s basic multiplication routine during an execution of the modular exponentiation routine using our carefully chosen cipher texts and five randomly generated $4096$-bit keys. The values of the first $100$ bits of $p$ are clearly visible (many zero limbs imply that the respective bit is $1$).

Fig. 7

Number of zero limbs in the second operand of mul_basecase($a,b$) during an execution of the modular exponentiation routine with the secret prime $p$ using our attack and randomly generated keys. The correct bit values are indicated on the horizontal axis of each key

The above is a high-level description of the adaptive attack. To achieve full RSA key extraction, improvements are required for the basic attack algorithm. See [18] for details.

5 Empirical key-extraction results

In this section, we discuss our empirical results for the various side channels. For each channel, we review the empirical setup and describe successful key extraction experiments.

5.1 Chassis-potential attack

5.1.1 Setup

As discussed in Sect. 2, there are computation-dependent fluctuations of the electric potential on the chassis of laptop computers. We measured the electric potential of the laptop’s chassis by touching it with the simplest possible probe: a plain wire, 80 cm long. The wire is pressed against the chassis by hand, or (for longer attacks) using an alligator clip. The wire’s potential is then measured through an amplifier, filters, and a digitizer (whose choice, discussed below, depends on the attack). See Fig. 8.

Fig. 8

Chassis-potential attack. The chassis potential is measured via the red wire is connected to the laptop’s heatsink fins (color figure online)

Grounding The attack measures the voltage between the room’s mains earth ground potential and the target computer’s chassis potential. Put otherwise, we create a ground loop which includes both the laptop chassis and the amplifier, and then measure the voltage across the amplifier’s input impedance (and thus its complement: the voltage across the laptop chassis).

Thus, correct grounding is essential for maximizing the signal-to-noise ratio. The measurement is done in single-ended mode, in reference to the mains earth ground potential, using low-impedance ground connection to the amplifier and digitizer. The target laptop is grounded through one of its shielded I/O ports (we used a VGA cable to a grounded screen, or a USB cable to a grounded printer). If the target laptop’s grounding is removed, but the laptop is still connected to a 3-prong (grounded) AC-DC power supply, the signal-to-noise ratio typically degrades.⁷ With a 2-prong (ungrounded) power supply and no other ground connections, the signal-to-noise ratio is very low and our attacks do not work.

Chassis probe placement The chassis of modern laptops, while made mostly of metal (for EMI shielding), is typically covered with non-conductive plastic. However, many IO ports, such as USB, Ethernet, VGA, DisplayPort and HDMI, typically have metal shielding which is connected to the chassis or PCB ground, and thus can be probed by the attacker. Also, metal heatsink fins are often easily reachable through the exhaust fan grill. Heuristically, the best results are achieved when the chassis is probed close to the CPU and its associated voltage regulator circuitry (similarly to the source of acoustic emanations [18]) and far from the laptop’s earth ground connection.

Chassis potential or EM? To ascertain that we were indeed measuring chassis potential rather than stray electromagnetic fields, we broke the direct galvanic connection between the probe wire and the laptop’s chassis, by inserting a sheet of paper in-between. As expected, this resulted in severe signal attenuation.

5.1.2 Non-adaptive chassis-potential attack

MF measurement equipment The non-adaptive attack exploits signals in the Medium Frequency (MF) frequency band, on the order of 2 MHz. To measure these signals, we connected the probe wire to a 16 kHz high-pass filter, followed by a high-input-impedance low-noise amplifier (Femto HVA-200M-40-F, 40 dB gain). The amplified signal was then low-pass filtered at 5 MHz and digitized at 12 bits and 10 Msample/s (National Instruments PCI 6115).

Exponent-dependent leakage RSA and ElGamal decryptions both use modular exponentiation of the ciphertext to the power of a secret exponent. We now examine how different exponents affect the chassis leakage. Figure 9 demonstrates seven RSA signing operations using different secret exponents. The different exponents can be easily distinguished. Similar results are observed for ElGamal decryption, though the exponentiation is shorter and thus its frequency spectrum can be characterized less accurately.

Fig. 9

Chassis measurement (2.5 s, 1.9–2.6 MHz) of seven GnuPG RSA decryptions executed on a Lenovo 3000 N200 laptop. In the first 6 cases, exponents ($d_p$ and $d_q$) are both overridden to be the 2048-bit number obtained by repeating the pattern written to the right. In the last case, the exponent is unaltered. In all cases, the moduli $p$ and $q$ are the same and the ciphertext is set to $n-1$

Analyzing the signal The signals presented in Fig. 9 provide the first indication as to how the different exponents might be distinguished. For periodic exponents, the leakage signal spectrum takes the form of small, distinct side lobes centered around a dominant frequency peak. This indicates that the bits of the exponents manifest themselves as modulations on a central sinusoidal carrier wave. Further analysis reveals that the carrier is frequency modulated, meaning that its instantaneous frequency changes slightly in accordance with the current bit of the exponent. Thus, to recover these bits, we obtain the dominant instantaneous frequency as a function of time, by applying FM demodulation digitally. The signal is first filtered using a 30 kHz band-pass filter centered at the carrier frequency. Next, the signal is demodulated using a discrete Hilbert transform. Additional filtering is then performed on the demodulated signal, to suppress high-frequency noise and to compensate for a slow frequency drift of the carrier wave. Figure 10 shows an example of a fully demodulated leakage signal; the correlation with the secret key bits can clearly be seen.

Fig. 10

Frequency demodulation of a segment of the leakage signal obtained during a decryption operation using a randomly generated 4096-bit RSA key. Note the correlation between the signal and the secret key bits

Key extraction Theoretically, it should be possible to extract the entire secret key from a single demodulated trace, provided the measurement is robust and has a high signal-to-noise ratio. However, we observed a periodic interrupt (marked in Fig. 10), which disrupted the key extraction. The interrupt manifests as a large frequency fluctuation in the carrier every 15 ms (Fig. 11), corresponding to the 64 Hz timer interrupt frequency on the target laptop. These interrupts systematically occur at the same time during the decryption process (when decryption is deterministically synchronized to the OS scheduler), and thus disrupt similar bit offsets in repeated decryptions. Fortunately, the inherent jitter is sufficient so that, over a few measurements, every bit is (with high probability) undisturbed in some sample.

Fig. 11

Frequency demodulation of the leakage signal during a decryption operation using a randomly generated 4096-bit RSA key. The interrupts, occurring every 15 ms, are marked by green arrows (color figure online)

On the other hand, jitter creates a difficulty in aligning the multiple traces. We thus break each trace, post-modulation, into multiple time segments. The segments are then aligned via correlation, and averaged. Large amplitude fluctuations caused by interrupts are discarded during this process, and thus do not contribute to the averaging. This results in an interrupt-free aggregate trace, with very high SNR. The bits are then extracted using a peak detection algorithm. Each peak in the averaged signal represents a logical “1” in the key, while the logical zeroes are determined by the distance between peaks.

Non-adaptive RSA key extraction Applying our non-adaptive attack on a randomly generated $4096$-bit RSA key while measuring the chassis potential of a Lenovo 3000 N200 laptop during 6 decryption operations, each lasting 0.35 s, we have directly extracted $2044$ out of $2048$ bits of $d_p$ thereby extracting the key.⁸ The laptop was powered by a 3-prong AC-DC power supply (Lenovo, 90W, model 42T4428), without additional connections.

Non-adaptive ElGamal key extraction Attacking the exponentiation in ElGamal decryption, and applying similar cryptanalytic and signal analysis, we extracted all but 2 of the bits of the secret exponent from a randomly generated 3072-bit ElGamal key by measuring the chassis potential of a Lenovo 3000 N200 laptop during 9 decryption operations, each lasting 0.1 s.

5.1.3 Adaptive chassis-potential attack

We now discuss results obtained using the adaptive attack described in Sect. 4. While this attack requires more decryption operations to recover the key, it utilizes lower frequency signals and requires much lower signal-to-noise ratio compared to the non-adaptive attack.

VLF/LF measurement equipment The adaptive attack can exploit very low bandwidth signals, in the VLF and LF frequency bands: in the order of 15–40 kHz (depending on the laptop model). To measure these signals, we used a more compact, higher dynamic range, measurement chain. The probe was directly connected to a high-input-impedance low-noise amplifier (customized Brüel&Kjær 5935, usually set to 40 dB gain). The amplified signal was high-pass filtered at 10 kHz, and digitized at 16 bits and 200 Ksample/s (National Instruments MyDAQ). Grounding and probe placement considerations are the same as for the non-adaptive attack.

Analyzing the leakage signal Recall that GnuPG’s RSA code performs modular exponentiation modulo $p$ followed by a modular exponentiation modulo $q$. Figure 12a shows a typical recording of RSA decryption when the value of the attacked bit of $q$ is $0$, and Fig. 12b shows a recording of RSA decryption when the value of the attacked bit of $q$ is $1$.⁹ Several effects are shown in the figures. As in Fig. 4, the transition between $p$ and $q$ is clearly visible in Fig. 12a, b. Note, then, that the signatures of the modular exponentiation using the prime $q$ (the second exponentiation) are quite different in Fig. 12a vs. b. This can be seen more clearly in Fig. 12c, which summarizes the aforementioned spectral signatures by taking the median, over time, for each. This clear difference is used to extract the bits of $q$, as explained in Sect. 4.

Fig. 12

Chassis measurement of RSA decryption for various values of the attacked bit executed on a Lenovo ThinkPad T60. a Attacked bit is $q_i = 0$, b attacked bit is $q_i = 1$, c frequency spectra of the second modular exponentiation

Adaptive RSA key extraction By connecting the VLF/LF measurement setup to a Lenovo ThinkPad T60, powered by the 3-prong AC-DC power supply without additional connections,¹⁰ we directly extracted the 1024 most significant bits of the secret prime $q$ of a randomly generated 4096-bit RSA key in approximately 1 hour. By Coppersmith’s technique, this results in full key extraction. (Alternately, it is possible to continue the attack and recover all the bits of $q$ directly.)

5.2 “Far end of cable” attack

The electric potential on a laptop’s chassis and external ports can be measured from far away. When a cable is plugged into one of the laptop’s many IO ports (such as USB, Ethernet, VGA, DisplayPort and HDMI), the port’s shield typically contacts to the plug’s shield, which in turn is connected to a conductive cable shield running the length of the cable. Thus, one can measure the chassis potential from the far side of cables connected to the aforementioned ports. Ethernet cables, for examples, often span long distances, across and between building floors. An attacker who gains access to the far side of the cable (see Fig. 13a), or taps the shield along the way, can measure the approximate chassis potential.

Fig. 13

“Far end of cable” attacks. a Measuring shield potential at the far side of an Ethernet cable (probed at the Ethernet switch). b Adaptive “far end of cable” attack using a mobile phone. The chassis potential of the laptop is measured from the far side of an Ethernet cable (blue, 10 m long). An alligator clip connected to a plain wire (green) taps the shield of the Ethernet cable where it connects to an Ethernet switch. The signal passes through a passive filter (orange) and then, via a coax cable (white), into the microphone/earphone jack of the phone (Samsung Galaxy S II), where it is amplified and digitized. The phone itself is grounded to mains earth via its USB port. It is possible to perform the adaptive attack using this setup (color figure online)

Crucially, the attacker’s only point of contact is the far side of the cable shield. The attack does not utilize the data transmitted over the cable, and is oblivious to whether the port is even enabled.

We conducted the attacks by connecting the target laptop, through a 10-m long-shielded CAT5e Ethernet cable, to a Gigabit Ethernet switch (EDIMAX ES-3308P). We attached a plain wire to the cable shield via a clip, on the switch side (see Fig. 13a). Its potential was measured and analyzed as follows.

Non-adaptive RSA key extraction Using the MF measurement setup (see Sect. 5.1.2), we measured the chassis potential of a Lenovo 3000 N200 laptop through the shield of the Ethernet cable. The laptop was powered by the 3-prong AC-DC power supply, and was also connected via a shielded VGA cable to a grounded monitor (Dell 2412M). We directly extracted $2042$ out of $2048$ bits of $d_p$, by observing the shield’s potential during $5$ decryption operations (each lasting 0.35 s). Thus, by searching for the remaining 6 bits of $d_p$, the complete key is extracted.

Similar results were obtained by monitoring the far side of a (dangling) USB cable.

Non-adaptive ElGamal key extraction Applying our non-adaptive attack to ElGamal decryption, we extracted all but 3 of the bits of the secret exponent, from a randomly generated 3072-bit ElGamal key, by observing the shield’s potential during 4 decryption operations (each lasting 0.1 s).

Adaptive RSA key extraction For this experiment, we attacked a Lenovo ThinkPad T60 laptop, through an Ethernet cable, whose shield potential was measured using the VLF/LF measurement equipment (see Sect. 5.1.3). The laptop was powered by the 3-prong AC-DC power supply, without additional connections. In this setting, we extracted the 1024 most significant bits of the secret prime $q$ (and thus, by Coppersmith’s technique, full key extraction) in 1 h. Again, similar results were obtained by monitoring the far side of a (dangling) USB cable. Finally, on some machines, this attack only requires 15 kHz of analog bandwidth to extract the key making it possible to execute using almost any commodity sound recording equipment such as a mobile phone (see Fig. 13b).

5.3 “Human touch” attack

On many laptops, the chassis potential can be sensed indirectly through a human body. An attacker can sense the chassis potential by merely touching a conductive part of the laptop chassis with his hand. ¹¹ This affects the electric potential of the attacker’s body (assuming suitable insulation, e.g., nonconductive floor or shoes). Surreptitiously, the attacker can measure the electric potential induced on his own body, using a concealed probe, in reference to some nearby conductive grounded surface in the room. Even this circuitous measurement, through an ill-characterized, high-impedance path, can suffice for key extraction.

Non-adaptive RSA key extraction Using the MF measurement setup (see Sect. 5.1.2), we measured the chassis potential of a Lenovo 3000 N200 laptop through the body of a volunteer (one of the authors). The volunteer held a paperclip or a metal pen in his hand, and briefly touched it to the laptop’s heatsink fins, which are easily reachable through the exhaust vent.¹² Concurrently, the volunteer’s body potential was measured using the MF measurement equipment (see Sect. 5.1.2), via a probe wire attached to a conductive wristband on his other wrist (see Fig. 14a). The laptop was powered by the 3-prong AC-DC power supply, with no further connection.

Fig. 14

“Human touch” attacks. a Non-adaptive “human touch” attack through a metal pen touching the heatsink fins. The wristband is connected to the probe wire. b Adaptive “human touch” attack by bare hand. The wristband is connected to the probe wire

Applying our non-adaptive attack and the signal analysis techniques from Sect. 5.1.2 on a randomly generated 4096-bit RSA key, we directly extracted 2042 out of 2048 bits of $d_p$ by observing the volunteer’s body potential (while holding the paperclip against the laptop’s heatsink) during 6 decryption operations, each lasting 0.35 s. Thus, by searching for the remaining 6 bits of $d_p$, the complete key is extracted.

Non-adaptive ElGamal key extraction Applying our non-adaptive attack and the signal analysis techniques from Sect. 5.1.2 on a randomly generated 3072-bit ElGamal key, we were able to extract all but 3 of the bits of the secret exponent by observing the volunteer’s body potential (while holding the paperclip against the laptop’s heatsink) during 16 decryptions, each lasting 0.1 s.

Adaptive RSA key extraction The adaptive attack, being more robust (due to relying on lower-frequency, longer-duration signals), succeeded with unaided finger touch. A patient volunteer touched the chassis (specifically, VGA connector shield) of a Lenovo ThinkPad T61 with his fingers. The volunteer’s body potential was measured using the VLF/LF measurement equipment (see Sect. 5.1.3), through the aforementioned wristband, and the laptop was connected as above. On some ThinkPad models, this attack can even be mounted by simply touching the, partially conductive, LCD cover (see Fig. 14b).

In this setting, we directly extracted the topmost 1024 bits of the prime $q$ of a randomly generated 4096-bit RSA key within one hour. Using Coppersmith’s theorem this information is enough in order to completely extract the entire key.

5.4 Electromagnetic (EM) attack

We studied EM emanations from laptop computers, in the MF band (approximately 2 MHz). We used a near-field magnetic probe (Rohde&Schwarz 7405901, 6 cm diameter, $50\,\Omega$ impedance). The signal was low-pass filtered at 5 MHz and amplified using an impedance-matched low-noise amplifier (a customized Mini-Circuits ZPUL-30P). The resulting signal was digitized at 12 bits and 10 Msample/s (National Instruments PCI 6115).

EM probe placement The placement of the EM probe relative to the laptop greatly influences the measured signal and noise. We wish to measure EM emanations close to the CPU’s voltage regular, located on the laptop’s motherboard, yet without mechanical intrusion. Luckily, most of the components covering the motherboard, such as the keyboard and its bezel cover, are almost transparent to EM signals. Concretely, hovering over the rear-left corner often yields the best signal.

Non-adaptive RSA key extraction Applying our non-adaptive attack to a randomly generated 4096-bit RSA key, we directly extracted 2046 out of 2048 bits of $d_p$, by measuring the EM emanations from a Lenovo 3000 N200 laptop during 5 decryption operations, each lasting about 0.35 s.

Non-adaptive ElGamal key extraction Using the same experimental setup and applying our non-adaptive attack to a randomly generated 3072-bit ElGamal key, we were able to extract all but 3 of the bits of the secret exponent by measuring the EM emanations from a Lenovo 3000 N200 laptop during 16 decryption operations, each lasting about 0.1 sec.

5.5 Power analysis attack

We revisited the classic power analysis channel, and analyzed the current draw fluctuations on the power supply of the target laptop in the VLF/LF frequency bands. Specifically, we placed a $0.5\Omega$ resistor in series with the laptop’s power supply, on the low (“ground”) supply rail. For a typical laptop load of 2–5 A at 16–20 V, the voltage on the resistor was around 2 V.

Adaptive RSA key extraction We measured the voltage on the resistor using a National Instruments MyDAQ device through a 150 kHz low-pass filter. We directly extracted the topmost 1024 bits of the prime $q$ of a randomly generated 4096-bit RSA key, from a Lenovo ThinkPad T61, in one hour.

6 Conclusion

While physical side-channel attacks have proven very effective at breaking cryptosystems, most research attention has focused on small and relatively simple devices. This paper demonstrated that PC systems too are vulnerable, despite their complexity, noise, and challenging electrical characteristics. Moreover, PCs can be attacked by mere touch or from afar by almost any wired connection.

Following our observations, several software countermeasures were proposed and incorporated into GnuPG $1.4.16$ and libgcrypt $1.6$.

Ciphertext normalization Our adaptive attack requires a careful selection of ciphertexts that are slightly larger than $p$ (but have the same limb count as $p$) to undergo reduction modulo $p$. However, for such ciphertexts, the modular exponentiation routine used by GnuPG will not normally reduce the ciphertext modulo $p$. We force this modular reduction to occur by padding the ciphertext with the public RSA moduli $n$ or by padding additional zeros. Thus, one immediate countermeasure to our adaptive attack is, before decrypting a ciphertext $c$, to compute $c'= c \hbox { mod }n$ and then strip $c$ of any leading zeros. This prevents the modular reduction in Line 3 of Algorithm 1, essential to the adaptive attack, from ever being executed.

Ciphertext randomization A common countermeasure against chosen-ciphertext attacks is ciphertext randomization [24]. For the case of RSA, such blinding is done as follows. Given a ciphertext $c$, instead of directly raising $c$ to the $d$th power, one generates a random value $r$, raises $c \cdot r^e$ to the $d$th power, and multiplies the result by $r^{-1}$. Since $r^{ed} \cdot r^{-1}\equiv 1 \pmod {n}$, the result is correct; yet the value sent to the modular exponentiation routine is randomized, which foils chosen-ciphertext attacks.

While the above countermeasures indeed foil the attacks presented in this paper, the key distinguishing attack is unaffected and still present in the latest versions of GnuPG; mitigating it in software, without a large overhead, remains an open problem.

Eliminating data-dependent branches While physical side-channel leakage is affected by many properties of the executed code and processed data, changes in control flow tend to be particularly prominent: same program, taking different branches, will often induce very different physical emanations. Thus, a common heuristic for mitigating leakage is to avoid data-dependent, and in particular key-dependent, control flow in the cryptographic code. This is often called “constant-time” implementation (a misnomer, because effects such as cache contention can create key-dependent timing differences even if the control flow is fixed [5, 31] and, moreover, because key-dependent branches should be avoided even if they happen to take the same number of cycles). The most easily observed differences are in high-level control flow (as exploited, e.g., in [7, 22]). Accordingly, GnuPG 1.4.15 modular exponentiation routine indeed avoids key-dependent branches at the higher level of the code (mitigating the attack of [38]). However, there are still branches affected by key-dependent intermediate values, in the inner levels of the code—as exploited by our attack. Some other cryptographic implementations attempt to avoid key-dependent branches at all levels of the cryptographic code, at some cost in performance. Examples include recent OpenSSL with RSA_FLAG_NO_CONSTTIME disabled (in C), and Google’s End-to-End implementation (in JavaScript). Achieving perfectly constant time is a difficult and a delicate task, depending on the cryptographic algorithm and intimate knowledge of the timing (and more generally, side-channel) characteristics of the target platform.

Physical mitigation Physical mitigation techniques include Faraday cages (against EM attacks), insulating enclosures (against chassis and touch attacks), and photoelectric decoupling or fiberoptic connections (against “far end of cable” attacks). However, inexpensive protection of consumer-grade PCs appears difficult, especially for the chassis channel. Indeed, substantial engineering attention and expense are already dedicated to the mitigation of conducted emanations, for the purpose of electromagnetic compatibility (EMC) compliance, yet the channel evidently persists; moreover, the common method for filtering conducted emanations on power supply lines is to use bypass capacitors to shunt stray AC currents into the ground, but this obviously does not apply to the ground line itself. Robust low-impedance grounding and shielding, with careful attention to current paths, should reduce voltages across the ground and chassis (at costs in engineering effort and portability). We conjecture that prudent design of switching power supplies and voltage regulators can reduce computation-dependent leakage without significantly hampering efficiency, and we raise this challenge as another open problem.