ECDSA Key Extraction from Mobile Devices via ... - Semantic Scholar

ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels ∗ Daniel Genkin

Lev Pachmanov

Itamar Pipman

Technion and Tel Aviv University [email protected]

Tel Aviv University [email protected]


Eran Tromer

Yuval Yarom


The University of Adelaide and NICTA [email protected]

March 1, 2016

Abstract We show that elliptic-curve cryptography implementations on mobile devices are vulnerable to electromagnetic and power side-channel attacks. We demonstrate full extraction of ECDSA secret signing keys from OpenSSL and CoreBitcoin running on iOS devices, and partial key leakage from OpenSSL running on Android and from iOS’s CommonCrypto. These non-intrusive attacks use a simple magnetic probe placed in proximity to the device, or a power probe on the phone’s USB cable. They use a bandwidth of merely a few hundred kHz, and can be performed cheaply using an audio card and an improvised magnetic probe.

1

Introduction

1.1

Overview

Side channel analysis, exploiting unintentional and abstraction-defying information leakage from physical computation devices, has been used to break numerous cryptographic implementations (see [MOP07, And08, KJJR11] and the references therein). While traditional side channel research has mainly focused on small embedded devices such as smartcards, RFID tags, FPGAs and microcontrollers, recent works also study of vulnerability of complex PC-class computers (laptop, desktop and server) to physical key-extraction attacks [ZP14, GST14, GPT14, GPPT15, GPPT16]. In this paper we study vulnerability to side-channel key extraction in another class of complex devices: mobile devices (smartphones and tablet computers). This prospect is already supported by some recent results. Using invasive access to the device, it is possible to acquire electromagnetic and power measurements with very high fidelity in terms of bandwidth, noise and spatial locality. Such invasive access has been used for key extraction attacks on intentionally-naive RSA implementations [NSN+ 14, GS15]. A non-invasive attack was shown by Kenworthy and Rohatgi [KR12, CRI12] on BouncyCastle’s RSA implementation running on a smartphone. All of these attacks used expensive lab-grade equipment, such as oscilloscopes, for their measurements. ∗

The authors thank Noam Nissan for programming and lab support during the course of this research.

1

This paper focuses, instead, on the Elliptic Curve Digital Signature Algorithm (ECDSA) [NIS13], a very popular signature scheme that is especially pertinent and critical in mobile devices due to its use in mobile payment apps such as Bitcoin wallets and Apple Pay. Attacking ECDSA raises new challenges: • ECDSA signatures are computed faster than RSA, and thus the attacker gets less physical information at a given sampling rate. Increasing the sampling rate increases costs and runs into frequency-limited physical effects. • More fundamentally, ECDSA signatures are randomized. When attacking determinsitic operations, such as RSA decryption, attackers can rely on triggering numerous identical decryptions and then aggregating their recorded traces in order to improve signal-to-noise ratio and cope with transient events such as interrupts. But with ECDSA, one has to make deductions from individual traces that are noisy and frequently interrupted. We raise the following questions: 1. How vulnerable are implementations of ECDSA, running on mobile phones, to physical side channel attacks? 2. Are these vulnerabilities common across different implementations and across different phone models? 3. What physical channels can be used for the attacks? 4. How expensive are such attacks, both in terms of complexity and in terms of financial outlay? Can they be conducted with concealed, portable equipment? Do they require high-grade lab equipment or can they be implemented using cheap, over-the-shelf equipment? A concurrent and independent work of Belgarric et al. [BFMRT16] provides a valuable insight on some of these questions, demonstrating full key extraction from BouncyCastle’s ECDSA implementation on a phone. That attack used an electromagnetic probe placed invasively inside the open case of a phone. It relied on triggering measurement via the USB interface, and (even though essentially relying on low-frequency signals) used an expensive oscilloscope. This leaves unexplored much of the space posed by the aforementioned questions.

1.2

Our Results

In this paper we demonstrate the first side channel attack on Elliptic Curve Cryptography (ECC) running on a smartphone which simultaneously achieves the following properties: 1. Real-World Implementations. We attacked the ECDSA implementation of OpenSSL running on iOS devices (iPhone and iPad) as well as Android devices. In particular, we attacked the CoreBitcoin library, based on OpenSSL, which is used by popular Bitcoin wallets on iOS devices. We also attacked the built-in ECDSA implementation of iOS’s CommonCrypto library. 2. Non-Invasive. The demonstrated attacks are non invasive and can be conducted by merely placing a magnetic probe in the proximity of the device, or using a power tap on its USB charging cable. The attack does not require any software to be installed on the device, and does not require opening the device’s case (see Figures 1 and 9). 3. Cheap EM and power analysis. Our attack utilizes physical emanations (electromagnetic or power) at frequencies below 200 kHz, which is well below the GHz-scale processor clock speed. Consequentially, our attack can acquire secret-key information using cheap, compact and readily available equipment, such as sound cards and improvised probes. 2

(a) Top view. The target is (top right) is measured by the improvised probe (taped on the underside of a glass table). The signal is captured by a Tracker Pre sound card connected to a laptop (under the table).

(b) Improvised probe (view from under the glass table).

Figure 1: Mounting a cheap EM attack on an iPhone 4 using an improvised EM probe. In some cases (e.g., CoreBitcoin on iPhone devices), we demonstrated full key extraction. It was impractical to do so for all combinations of target software, target hardware and acquisition hardware, but for numerous such combinations we found clear leakage of key material suggesting feasibility of full key extraction, as discussed in Sections 3 and 4. We achieve the above using new techniques for enhancing the measured side-channel signal in the presence of noise generated by the device’s internal components. While typical techniques for overcoming measurement noise involve averaging the signal obtained from several secret-key operations, these techniques are not applicable for ECDSA since the nonce is generated afresh for every signature. Instead, we present techniques which are capable of enhancing the signal present in a single trace without relying on additional information from other traces, which might be of independent interest.

1.3

Targeted Software and Hardware

Hardware. We target mobile devices such as tablets and phones. We have measured numerous devices of various models and manufactures. Many devices exhibit key-dependent leakage (see Figure 3). In the sequel, unless stated otherwise, the experiments were performed on Apple iPhone 3GS which exhibited a particularly clear signal. Software. In this work, we target popular ECDSA implementations running on various mobile devices. More specifically, we target the following implementations: 1. OpenSSL. The ECDSA implementation of OpenSSL (version 1.0.1m), a ubiquitous cryptographic library, running on iOS and Android devices.1 The underlying Elliptic Curve (EC) scalar multiplication algorithm is wNAF with w = 3. 1

We used OpenSSL compiled with its default options. In particular, the “enable-ec nistp 64 gcc 128” option, which enables a constant-time implementation for some curves [K¨ as12], is disabled by default and works only on 64-bit x86 (32-bit processors are unsupported, and the built-in tests fail on 64-bit ARM).

3

2. CommonCrypto. The built-in ECDSA implementation of iOS which is part of Apple’s CommonCrypto framework (as included in iOS versions 7.1.2 through 8.3). The underlying EC multiplication algorithm is wNAF with w = 1. 3. CoreBitcoin. We target the deterministic ECDSA as implemented (following RFC6979 [Por13]) in CoreBitcoin [Cor], a popular cryptographic library for iOS used by many many Bitcoin clients [Yel, Bitb, Bitc, Myc, ARC]. The underlying EC multiplication algorithm is OpenSSL’s. Our attacks require side-channel measurements while the victim performs multiple ECDSA signing operations. Signing multiple messages under the same key is common when the key is fixed by a public key infrastructure or a PGP “web of trust”. It is also necessary for Bitcoin micropayment channels [Mic, Smi15], which allow making lightweight out-of-blockchain automated payments for an ongoing service, and each payment requires an ECDSA signature. Disclosure and Status. Practicing responsible disclosure, we have worked with the vendors of all targeted software to convey our findings and coordinate response, prior to public disclosure. See Appendix A for the current status of targeted software, including newer versions.

1.4

Related Work

Physical Attacks on ECC on Small Devices. For small devices (smartcards, RFID tags, FPGAs and microcontrollers), side-channel attacks have been extensively demonstrated on numerous cryptographic implementations, using various channels, and in particular electromagnetic emanations starting with [AARR02, GMO01, QS01]. See [And08, KJJR11, MOP07] and the references therein. In particular, physical key-extraction attacks were shown on many ECC implementations on small devices, staring with Coron [Cor99]; see the surveys [FGM+ 10, FV12] and the references therein. However these techniques either utilize subtle physical effects which are only visible at bandwidths comparable to the device’s clock rate, attack naive implementations (such as the double-and-sometimes-add algorithm), or utilize a chosen ciphertext in order to deduce additional information about the algorithm’s secret internal state. Unfortunately, all of the above approaches have significant drawbacks in the case of a nonnaive implementation of ECDSA running on a high-speed smartphone. Non-invasively recording clock-rate signals from a smartphone running a multi GHz-scale CPU is difficult, often requiring expensive, cumbersome, and delicate lab equipment. Chosen-input attacks are usually inapplicable to signature schemes, since the inputs are processed through a cryptographic hash function. Key-Extraction Side-Channel Attacks on Phones. High bandwidth electromagnetic attacks (sampling at clock-rate speeds) on symmetric ciphers were demonstrated by Aboulkassimi et al. [AAF+ 11] on Java-based feature-phones. Attacks at clock-rate frequencies on public key cryptography were also recently demonstrated by Goller and Sigl [GS15] on Android smartphones running a naive square-and-sometimes-multiply RSA, with the phone’s shielding plate often removed. Lower-frequency attacks on smartphones executing naive implementations of squareand-sometimes-multiply RSA as well as double-and-sometimes-add ECC were also demonstrated by [NSN+ 14] with the phone battery cover opened, battery removed and the probe positioned directly over the leaky component. A non-invasive low-frequency attack was demonstrated by Kenworthy and Rohatgi [KR12] against naive square-and-sometimes-multiply RSA. These attacks were also later extended to RSA windowed exponentiation as used in BouncyCastle [CRI12]. Finally, measuring at clock-rate frequencies, the work of Kenworthy and Rohatgi [KR12] also presented an attack on a naive double-and-sometimes-add ECC. In a concurrent and independent work, Belgarric et al. [BFMRT16] presented an invasive lowfrequency attack on the ECDSA implementation of Android’s BouncyCastle library, running on 4

a smartphone, using a magnetic probe placed inside the (opened) phone. It used a bandwidth of 50 kHz, measured by an oscilloscope. Triggering of the acquisition equipment was done via the phone’s USB port, using software installed on the phone, which sends a trigger signal via USB and then immediately invokes the BouncyCastle signing function. The acquisition and analysis of the signal were done by manual observation of the double and add operations in the (hundreds of) traces. Software side-channel attacks, utilizing cache contentions, were demonstrated on ARM devices, showing partial extraction of an AES key [LGSM15]. These require attacker’s code to run on the device. Physical Key Extraction Attacks on ARM Development Boards. In recent works, DPAstyle attacks were demonstrated on ARM-type devices. Balasch et al. [BGRV15] demonstrated a clock-rate attack on AES running on a BeagleBone Black ARM development board. A similar attack on the same device at much lower frequencies was demonstrated by Galea et al. [GMPT15]. However, while these results demonstrate the possibility of attacking symmetric key encryption running on complex devices, both attacks were highly invasive with the probe physically glued to the leaky component. The task of demonstrating a non-invasive attack on symmetric key encryption running on a real smartphone remains open. Key-Extraction Side-Channel Attacks on PCs. Physical key-extraction side-channels were exploited for extracting keys from RSA, ElGamal and ECDH implementations, using the acoustic, chassis-potential and electromagnetic channels [GST14, GPT14, GPPT15, GPPT16]. Software key extraction attacks were demonstrated using timing differences [BB05, BT11], and cache contention [Ber05, Per05, OST06] and applied to ECDSA [BH09, BvdPSY14, Van de PolSY15, ABF+ 15].

2 2.1

Cryptanalysis Preliminaries

ECDSA. We start by describing the Elliptic-Curve Digital Signature Algorithm scheme (ECDSA). Given a generator G of an elliptic curve group of order n, key generation consists of selecting a random integer 1 ≤ d ≤ n − 1 and computing Q = [d]G. (Here and onward, we use additive group notation, and [d]G denotes scalar-by-point multiplication.) The (secret) signing key is d and the (public) verification key is Q. Signing of a message m is done as follows: hash m under a designated hash function and convert the first dlog2 ne bits of the digest into an integer z; generate a random nonce 1 ≤ k ≤ n−1; compute the curve point (x, y) = [k]G using a scalar-by-point multiplication; compute r = x mod n and s = k −1 (z + r · d) mod n; output the signature (r, s). (In case r = 0 or s = 0, repeat the signature operation using a fresh random k.) Verifying a signature (r, s) on m is done by computing z as above, computing w = s−1 mod n, u1 = zw mod n, u2 = rw mod n, (x, y) = [u1 ]G + [u2 ]Q and then checking that x ≡ r (mod n). Low s-value ECDSA. ECDSA signatures are malleable in the sense that given a message m and a signature pair (r, s), it is possible to generate an additional valid signature for m (r0 , s0 ) 6= (r, s) by setting r0 = r and s0 = −s mod n. This property is problematic for Bitcoin clients which use the hashing of (r, s) in order to identify matching signatures [Wui14, ADMM15]. A common solution to the above problem used by many Bitcoin clients is to require that s ≤ n/2. That is, in the case that the signing process (described above) generates a pair (r, s) where s > n/2 for some message m, the signature routine outputs (r, −s mod n) as the signature of m [Wui14]. 5

Attack Overview. Our attack deduces partial information about the nonce k used during the scalar-by-point multiplication [k]G in the signing operation. The signing key d is recovered by combining the information obtained during multiple signature operations. Notation. In the sequel, for an integer a, we denote by |a| is absolute value, by bacn the result of reducing a modulo n into the range [0, · · · , n − 1] and by |a|n the result of reducing a modulo n into the range [−n/2, · · · , n/2). Closest Vector Problem (CVP). An input of a CVP consists of a matrix (lattice basis) B and a vector u. The output is an integer vector x such that the `2 -norm of the vector xB − u is minimal, i.e., the lattice vector xB is the closest to u. While the CVP problem is believed hard in geneal and the best algorithms are exponential in the dimension of B (in the worst case), many heuristic CVP solvers exists [Ngu11]. In this work, we utilize the fplll solver [ABC+ ] running on a PC (3.4 GHz, 6 cores, 64 GB of RAM).

2.2

Scalar-by-Point Multiplication

The main operation performed during a ECDSA signing is the elliptic curve scalar-by-point multiplication. The w-ary non-adjacent form (wNAF) method (Algorithm 1) is one of the commonlyused algorithms for implementing scalar-by-point multiplication. wNAF is used for multiplication in curves over prime size fields, including many of the NIST P-curves and the Bitcoin curve secp256k1, in several cryptographic libraries, such as OpenSSL, CoreBitcoin, Apple’s CommonCrypto and BouncyCastle. The algorithm is so named for representing the scalar k using the wNAF representation which we now discuss. The non adjacent form [Rei60] is a generalization of the binary representation of integers, allowing for three possible digits, -1, 0, and 1, referred to as NAF digits, and requiring that every pair of non-zero digits is separated by at least one zero digit. For example, the 4-digit NAF representation of 7 is (1,0,0, −1) compared to its binary representation (0,1,1,1). The main advantage of using a NAF representation is that it reduces the expected number of non-zero digits from about 1/2 for the binary representation to about 1/3. Since every non zero digit in the representation of k leads to a point addition operation, representing k in NAF form reduces the number of point addition operations performed during the scalar-by-point multiplication operation. The wNAF representation generalizes this by allowing odd digits from {−2w + 1, · · · ,2w − 1} as well as zero digits.

2.3

Attack Algorithm

Let DA-sequence denote the sequence of double and add operations performed in lines 9 and 11 of Algorithm 1. Notice that by observing the DA-sequence performed by Algorithm 1 it is possible to deduce all the locations of the non-zero valued wNAF digits of the nonce k. However, since the DA-sequence only discloses the positions of the non-zero digits but not their values, recovering the DA-sequence alone is not enough for achieving key extraction. Nguyen and Shparlinski [NS03] describe a theoretical attack for combining partial information on the bits of multiple nonces in order to recover the secret key d. Benger et al. [BvdPSY14] later apply the attack to the DA-sequences of OpenSSL’s implementation of ECDSA, as leaked through a cache channel on a PC. In this section we extend these techniques for handling low s-value ECDSA commonly used by Bitcoin clients. Attacking Low s-value ECDSA. Let d be an ECDSA signing key and G be a generator of an elliptic curve of order n. Assume we have a dataset of m ECDSA signatures where for each signature i we are given the hashed message zi and the signature (ri , si ), where si is the low s-value,

6

Algorithm 1 wNAF scalar-by-point multiplication operation (simplified). Input: A positive scalar k and an elliptic-curve point P, where kg−1 · · · k0 is the wNAF repreP i w w sentation of k, that is k = g−1 i=0 2 · ki , ki ∈ {−2 + 1, · · · ,2 − 1}, ki is odd or zero, and kg−1 6= 0. Output: [k]P. 1: procedure point mul(k, P) 2: Q1 ← P 3: Q−1 ← [−1]P 4: for i ← 1 to 2w−1 − 1 do 5: Q2i+1 ← Q2i−1 + [2]P 6: Q−2i−1 ← [−1]Q2i+1 7: A ← Qkh−1 8: for i ← g − 2 to 0 do 9: A ← [2]A 10: if ki 6= 0 then 11: A ← A + Qki return A 13: end procedure

12:

i.e. s ≤ n/2. First, we notice that for all i it holds that zi + d · ri ≡ si ki

(mod n)

zi + d · ri ≡ −si ki

or

(mod n).

(1)

Notice that, without knowing ki , we do not know which of the above cases holds. (This depends on whether k −1 (z + r · d) mod n is larger than n/2 or not.) Next assume that for each i we learn (for example through side channel leakage) that the li least significant wNAF digits of ki are zero. We first note that this also implies that the li least significant bits of ki are zeros or, equivalently, that ki = 2li · bi for some bi ≤ n/2li . Expanding and rearranging Equation 1 we obtain that for all i it holds that −li + d · r · s−1 · 2−li ≡ b zi · s−1 i i i i ·2

−li + d · r · s−1 · 2−li ≡ −b zi · s−1 i i i i ·2

(mod n). (2) −li c , u = bz · s−1 · 2−li c and ν = |dt − u | . From Equation 2 we Next, define ti = bri · s−1 · 2 n i i n i i i n i i have that either νi ≡ bi (mod n) or that νi ≡ −bi (mod n). Finally, since bi ≤ n/2li ≤ n/2 and |νi | ≤ n/2, we obtain: |νi | = bi ≤ n/2li . (3) (mod n)

or

Notice that |νi | is smaller by a factor of 2li −1 than a random element in Zn . Utilizing this fact, following the approach of [NS03, BvdPSY14], we now convert our dataset into a closest vector lattice problem. CVP Attack. Consider the lattice L(B) over the m + 1-dimensional real space generated by the rows of the following matrix  l  21 ·n   ..   . B= . l m   2 ·n l l 2 1 · t1 · · · 2 1 · tm 1 7

Next, define a vector u = (2l1 · u1 , · · · , 2lm · um ,0). Notice that both the matrix B and the vector u can be computed from the public information zi , si and the leakage li for 1 ≤ i ≤ m. We now claim that the solution to the closest vector problem defined by L(B) and u reveals the secret key d. Indeed, Equation 3 implies the existence of integers (λ1 , · · · , λm ) such that for the vectors x = (λ1 , · · · , λm , d) and √ y = (2l1 · ν1 , · · · ,2lm · νm , d) we have xB − u =Py. Next, notice that the `2 -norm of y is about n · d + 1 whereas the determinant of L(B) is 2m+ li · nm . Thus, we obtain that the lattice vector xB is heuristically closest to the vector u. Therefore, by solving the CVP problem on inputs (B, u) we obtain the vector x the last entry of which reveals the secret key d.

3 3.1

Signal Analysis Experimental Setup

To measure the EM leakage from the smartphone, we used a Langer LF-R 400 near field probe (a 25mm loop probe, 100 kHz–50 MHz). We amplified the signal measured by the probe using a (customized) Mini-Circuits ZPUL-30P amplifier, providing 40 dB of gain. The output of the amplifier was then low-pass filtered at 5 MHz. For digitizing the analog signal, we used one of two instruments. For the best robustness during initial characterization, as described below in this subsection, we used a National Instruments PCI6115 data acquisition device, sampling at 10 Msample/sec with 12 bits of ADC resolution. For key extraction, described in Section 3.2, we used an Ettus N200 software defined radio device, with its LFRX daughterboard, sampling at 1 Msample/sec. Note that in terms of bandwidth, the above is an overkill for our attacks, which exploit signals up to 200 kHz. Thus, similarly to [GPPT15], we can replace the probe and data acquisition device with much cheaper equipment, such as a sound card; this is discussed in Section 4. Scalar-Dependent Leakage. Confirming the existence of scalar-dependent leakage from the scalar-by-point multiplication function of OpenSSL, Figure 2 shows a spectrogram of the electromagnetic leakage obtained during four distinct signature operations, using the same point P and four different values of the scalar k. Notice that all of the four scalars can be easily distinguished by their spectral signature alone. Such nonce-dependent leakage was observed on many target phones, of various models and manufactures (see Figure 3). This hints at the relationship between the time behavior of the observed leakage signal and the secret bits of the scalar k (analogous to what was observed in [GPT14, GPPT15, GPPT16] on laptop computers).

3.2

Attacking OpenSSL ECDSA

Signal Acquisition. We recorded the leakage of 5000 OpenSSL ECDSA signatures executed on an iPhone 3GS. For all of the recorded signatures, we used the secp256k1 curve with the same randomly-generated secret key. We measured the iPhone’s electromagnetic emanations during the signing operations using the setup described in Section 3.1 (with the Ettus N200 sampling at 1 Msample/sec). We then stored the recorded traces, as well as the signed message produced by the ECDSA signing, for offline signal processing and cryptanalysis. Examining Raw Traces. After digitizing, we applied a Finite Impulse Response (FIR) lowpass filter to suppress noise outside the 0–125 kHz band. The resulting signal can be seen in Figure 5 (top). Evidently, even after suppressing high frequency noise, one still cannot easily determine the locations of point addition and point doubling operations. In addition, the signal is periodically corrupted by strong disturbances caused by the operating system timer interrupts.

8

Figure 2: EM measurement (0.5 sec, 0–225 kHz) of four scalar-by-point multiplication operations using the NIST P-521 curve executed on an iPhone 3GS smartphone. The scalar was set to be either a random 521-digit number or a the 521-digit number obtained by repeating the pattern written to the right. In all cases, the same curve point was used to perform the multiplication. Previous works ([GPT14, GPPT15, GPPT16]) have mitigated the problem of low SNR and signal distortion by repeating each measurement several times and combining the results into a single clear aggregate trace. However, this is inapplicable to ECDSA: each signing operation uses a different nonce k, so the corresponding scalar-by-point multiplications [k]G results in different DA-sequences that cannot be directly combined. Locating Signing Operations. In order to successfully execute our attack, we need to find the exact points in time where each signing operation ends. Unlike the concurrent work of [BFMRT16] which assumes that these exact time points are leaked via the USB port, we assume the attacker has no leakage of such information and tackle the problem during our signal processing steps. For this purpose we utilize a distinct trace pattern occurring at the very end of each signing. This pattern is a natural product of the executed code (it is not an artificial trigger), but is very similar across different signing operations, for given software and hardware. After performing signal denoising (described next) we apply correlation-based detection to identify all instances where this distinct pattern occurs. we thus obtain the end points for most signing operations. We ignored some traces that ended in distorted patterns that did not correlate well. Denoising Signal Traces. As mentioned above, an average-based denoising approach is not applicable to ECDSA since each signing operation uses a different nonce k. Instead, to increase the SNR of our traces, we add a preprocessing step (following the FIR filter) that performs Singular Spectrum Analysis (SSA). SSA can be used for blind source separation and denoising of single traces [GZ13]. In the context of side channels, SSA was used in [PS15] to increase the success probability of various DPA-style attacks targeting embedded devices. The aim of the SSA procedure N is to decompose a given time series ai i=1 into several distinct components, each with its own physical properties. The algorithm can be described in three stages (See [GZ13] for further details). Step 1: Embedding. First, a window length 2 < L < N/2 is chosen and used to construct a trajectory N matrix of the input time series ai i=1 . The trajectory matrix is comprised of K “lagged” copies . of the series and is defined as follows (where Ai are column vectors and K = N − L + 1):   a1 a2 ... aK a3 . . . aK+1    a2  A = A1 A2 . . . AK =  . .. ..  . . . .  . . . .  aL aL+1 . . .

aN

Notice A is also a Hankle matrix since all entries on its anti-diagonal are identical, i.e. for all 2 6 i + j 6 N + 1 and 1 6 n 6 N we get Aij = an if i + j = n + 1. 9

(a) Apple iPad Mini 2 (0 − 400 kHz, 0.2 msec).

(b) Apple iPad 3rd Generation (0− 200 kHz, 0.3 msec).

(c) Apple iPhone (0 − 175 kHz, 0.3 msec).

(d) Apple iPhone (0 − 200 kHz, 0.2 msec).

(e) Apple iPod Touch 4th Generation (0 − 200 kHz, 0.2 msec).

(f) Sony Ericsson Xperia (250 − 500 kHz, 0.8 msec).

5s

4s

X10

Figure 3: EM measurement of four scalar-by-point multiplication operations using the NIST P521 curve executed on various mobile devices. In each subfigure, the first multiplication used a random 521-digit scalar while the remaining three used the same repetitive 521-digit numbers used in Figure 2 (in the same order). Similarly to Figure 2, the same curve point was used to perform the multiplication. Step 2: Singular Value Decomposition. After obtaining the trajectory matrix, it is decomposed using a Singular Value Decomposition (SVD). An SVD of a matrix A is a well known decomposition and is defined by (for an L by K matrix with L < K):    √  V1T λ1 0 0 ··· 0  T   .   V2  T . .. A = USV = U1 U2 . . . UL  ..   ..  , 0 · · · 0  .  √ 0 0 λL · · · 0 VKT where λi are the eigenvalues of AAT in descending order and Ui are their corresponding eigenvecT tors. The vectors Vi for 1 6 i 6 d are given by Vi = A√λUi , where d is the lowest eigenvalue such i that λd > 0. The SVD of a matrix thus allows us to represent it as a sum of matrices: A = USVT =

d p d p X X λi Ui Vi T = λi Xi . i=1

i=1

The matrices Xi√are called projection matrices, and their contribution to the original matrix A are proportional to λi (which are also called the singular values of A).

10

Figure 4: Our lab-grade setup for capturing EM emanations attacking a Sony-Ericsson Xperia x10 phone. Left to right: analysis laptop, power supply, ZPUL 30P amplifier (gray box), Ettus (white box), and Xperia x10 phone being attacked using the Langer LF-R 400 probe (blue). Step 3: Reconstruction. Each matrix Xi can now be transformed back into a length N time series i N xn n=1 by averaging over the entries in its anti-diagonal. This process is also called diagonal averaging or Hankelazation [Has07]. Overall we obtain a decomposition of the original time series N an n=1 into a sum of d series: d X N i N an n=1 = xn n=1 . i=1

A denoised time series can now be reconstructed by choosing a suitable subset of m ≤ d series from d within the set xin i=1 . SSA Parameter Choice. The quality of the decomposition and denoising is highly dependent on the window size L and the choice of subset m. Empirically, we have found that good results are obtained when L is chosen to be shorter than both the double and the add operations. At a sampling rate of 1M samples per second, the length of double and add operations was 50 and 250 samples, respectively. We thus chose L to be 10 samples long. The reconstruction subset m was also chosen empirically. We found that a good result is achieved when one uses the components corresponding to the third, fourth and fifth highest singular values for reconstruction (regarding the rest of the components as noise). It is worth noting that SSA is often used in the literature to expose hidden periodic trends in noisy signals. In these cases it is recommended [KP11, GZ13] to choose L to be relatively large (larger than the longest suspected hidden period). However, in our case the DA sequence has no intrinsic periodicity, and larger L values seemed to be less suited for denoising. Figure 5 depicts a signal trace after undergoing the SSA procedure. The double and add sequence can now be clearly seen. Note that the SSA procedure did not get rid of the interrupt induced disturbances, but since we only require a small number of double operations taken from the end of the trace, this is usually not an issue. On the rare occasions where an interrupt was 11

Figure 5: A recorded trace after filtering out high frequency noise (top), and the same trace after additionally applying SSA (bottom). Note the timer interrupt disturbing the measurement signal. detected at the very end of the trace, the corresponding recording was simply discarded. Locating Addition Operations In Time. Examining the denoised trace, we can now attempt to extract the DA-sequence. For this purpose we turn to the time-frequency domain. The middle of Figure 6 depicts the spectrogram of a denoised trace, where the frequency band containing most of the energy of addition operations becomes especially clear (see Figure 6 (middle)). Summing over the spectrogram’s energy we receive a trace marking the locations of addition operations in time . In order to increase the detection accuracy, we enhance this trace by multiplying it with its own derivative with respect to time. This way we are able to enhance high amplitude peaks that also rise sharply, and attenuate other peaks. Further smoothing produces the signal depicted in Figure 6 (bottom), where the peaks marking the locations of add operations can be detected with high fidelity. Extracting the Partial DA-Sequence. Having found a way to detect addition operations with sufficient fidelity, we can now attempt to locate the position of the very last addition operation in the signal. We do so by first finding the point in each trace where the signing operation ends. This point can be reliably found in many traces since the signal pattern that immediately follows the signing operation is consistently similar across many traces. We can use this pattern as a template to reliably locate it in other traces using correlation, discarding traces that do not correlate well with the chosen template. By measuring the distance between the estimated template location in each trace and the very last addition operation detected in the signature (found using the methods described in the previous subsection), we can determine the number of double operations that occurred at the very end of each signing operation, thus acquiring the DA information necessary for key extraction. Signal Analysis Performance. Applying our attack to a randomly-generated ECDSA secp256k1 OpenSSL key, we measured the EM emanations during 5000 signatures on an Apple iPhone 3GS smartphone, each signature lasting 0.1 sec. Applying our signal processing to the 5000 traces we 12

Figure 6: (top) A denoised trace with add operations marked. (middle) Zoomed-in view of the spectrogram of the trace. The energy of add operations is clearly visible. (bottom) Energy as a function of time of the visible part of the spectrogram (after enhancement and smoothing). Peaks approximate the location of add operations. collected, we were able to detect the end time of the signing operation in 1278 traces. Out of these, 114 traces were identified as having their DA-sequence terminate with at least three elliptic curve double operations; 3 of these were false positives (as discovered in retrospect; the attack code did not use this information). Lattice Reduction and Key Extraction. Using the above 114 traces, we randomly selected 85 traces2 and applied the lattice attack of [BvdPSY14] using the fplll [ABC+ ] implementation of the BKZ algorithm with block size β = 30. Unfortunately, in case one of the 3 erroneous traces are selected for the lattice, the BKZ algorithm fails to recover the signing key, causing the attack to fail. Therefore, we repeated the procedure of randomly selecting 85 traces and applying the lattice attack 30 times. Across the 30 attempts, the secret key was successfully recovered in 2. The signal processing and lattice reductions took two hours on a desktop PC (3.4 GHz, 6 cores, 65 GB RAM), leading to complete extraction of the ECDSA signing key.

3.3

Attacking Other ECSDA Implementations

Attacking OpenSSL on Android Devices. Key-dependent leakage, similar to Figure 2, was also observed on various Android phones. See Figure 3. We thus conjecture that similar attacks can be mounted on these devices as well. Demonstrating the feasibility of such a result on an Android device, Figure 7 shows the extraction of a sequence of elliptic curve double and add operations 2

The number of traces was set empirically for maximizing the success probability in the next step.

13

Figure 7: Sequence of double and add operations extracted during a secp256k1 scalar by point multiplication operation executed on an Sony-Ericsson Xperia X10 smartphone. In this experiment we replaced the wNAF representation of k with the 256-digit string obtained by repeating the pattern 10100. from a Sony-Ericsson Xperia X10 smartphone. The signal in the figure is the result of digital FM demodulation and filtering. Attacking CoreBitcoin. Demonstrating the possibility of Bitcoin theft via side-channel from iOS devices, we have mounted a successful key extraction attack on CoreBitcoin’s low s-value ECDSA implementation running on iOS. We recorded the leakage of 5000 ECDSA secp256k1 signatures executed on an Apple iPhone 3GS smartphone. Out of these 5000 traces, 1940 were discarded due to measurement noise. Out of the remaining 3060 traces, 110 were identified as having their DA sequence terminate in at least four elliptic curve double operations with one of these being a false positive (again, discovered in retrospect). Next, we randomly chose 85 out of the 110 available traces and applied the lattice attack described in Section 2.3. Repeating the attack 20 times (each time choosing a random subset containing 85 traces) resulted in a successful key extraction in 4 out of the 20 attempts. Attacking Apple’s CommonCrypto ECDSA Implementation. The ECDSA implementation of Apple’s CommonCrypto library performs the elliptic curve scalar-by-point multiplication operation using Algorithm 1 with w = 1. Figure 8 shows scalar-dependent leakage, similar to Figure 2, obtained by measuring an iPhone 3GS when invoking the elliptic curve multiplication operation as implemented in Apple’s CommonCrypto library.

4

Cheap Attacks

While the results of Section 3 clearly demonstrate the possibility of key extraction via the electromagnetic channel using expensive lab equipment, the low bandwidth nature of our attacks allows for key extraction using a much cheaper experimental setup via both the electromagnetic channel and the power channel. EM Probe. For the electromagnetic channel we improvised a probe by scavenging a coil from a Qi wireless charging receiver module ($1 on eBay). See Figure 1. Power Probe. To monitor the phone’s current draw, we built a simple USB pass-through adapter, with a 0.33Ω resistance in series with the ground line. We then connected the phone to a portable 14

Figure 8: EM measurement (0.2 sec, 0–250 kHz) of four scalar-by-point multiplication operations using the NIST P-521 curve executed on an iPhone 3GS smartphone running Apple’s CommonCrypto library. As in Figure 2, the scalar was set to be either a random 521-digit number or a the 521-digit number obtained by repeating the pattern written to the right. In all cases, the same curve point was used to perform the multiplication. USB battery pack through the pass-through adapter, and measured the voltage over the resistor; see Figure 9. Digitizer. We connected the improvised EM and power probes into the microphone input of a Creative Tracker Pre sound card ($50, eBay). This card acts both as an amplifier (60dB gain) and as a digitizer (192 Ksample/sec). Attack Scenario. Small loops of wire acting as EM probes can be easily concealed inside various objects (such as tabletops, phone cases (especially those containing an extra battery), or even food items [GPPT15]). See Figure 1. Monitoring the phone’s power consumption can be easily done by augmenting an aftermarket charger, external battery or battery case with the requisite equipment. In this context, phone cases which contain an additional battery (and therefore are connected to the phone’s charging port) are especially dangerous since these can be augmented to monitor both channels simultaneously, thus obtaining a potentially cleaner signal. Scalar-Dependent Leakage. We measured the EM leakage of an iPhone 4 using our improvised EM probe connected to the Tracker Pre sound card and concealed beneath a glass tabletop (see Figure 10). Similarly to Figure 3, Figure 10 (right) presents a spectrogram of five distinct signature operations, using the same point P and five different values of the scalar k. Notice that even though the equipment used to generate Figure 10 is much simpler (and cheaper) than the lab-grade equipment used in Figure 3, the five different scalars can be easily distinguished from their spectral signature. Similar results were obtained using the power probe as well (see Figure 10 (left)). Extracting the DA-Sequence. After observing the scalar dependent leakage using our improvised probes and the Tracker Pre sound card, we proceeded to extract the DA-sequence which is required for our attack. Applying our signal processing techniques on an iPhone 3GS running OpenSSL secp256k1 signature operations, Figure 11 depicts the results of extracting the DAsequence using EM leakage from a single signature. Notice that the individual double and add operations can clearly be seen. Repeating this process for about 5000 signatures should result in a complete key recovery.

5

Countermeasures and Future Work

Our attack exploits the differences between point addition and point doubling to recover the DAsequence. Two approaches can be used to protect an implementation from side-channels. The 15

Figure 9: Mounting cheap power analysis attack on an iPhone 4 through its charging port. This setup includes a portable battery (bottom, left), a power monitoring probe (bottom, middle) and an iPhone 4 (bottom, right). The power probe is then connected to the Tracker Pre sound card (top, middle) and the attacker’s laptop (top, left). value of the nonce can be decoupled from the DA-sequence using blinding. Alternatively, the implementation can be modified to always use the same DA-sequence, irrespective of the value of the nonce. Nonce Splitting. Clavier and Joye [CJ01] suggest expressing the nonce k as k = k1 + k2 , where k1 is random and then compute [k1 ]G + [k2 ]G using a multi-exponentiation algorithm [Möl01a]. However, that this approach leaks the least significant bits of k1 and k2 , as well as long, overlapping sequences of repeating bits in k1 and k2 . Splitting the nonce more, i.e., expressing k = k1 +k2 +k3 + · · · , such that all the terms but one are chosen at random, can reduce the probability of overlaps. However, this approach still leaks the least significant bit of k and as [AFG+ 14] show, leaks of one bit can be exploitable. Nonce Blinding. Coron [Cor99] suggests blinding the nonce by choosing a random c and calculating [k]G + [cn]G where n is the group order. Ciet and Joye [CJ03] note that for groups of order close to a power of two, this method still leaks information about the high order bits of k, and Van de Pol et al. [Van P de PolSY15] show how to exploit suchPleaks. Combining the two approaches, i.e., calculating [ki ]G for random ki ’s and c such that ki = k + cn, protects from both types of leaks. Constant-time implementations. Constant-time implementations remove side-channel leaks by ensuring a fixed execution path that does not depend on secret data, to prevent timing attacks [BB05]. Additionally, a constant memory access pattern is desired to avoid cache-based attacks [Ber05, Per05, OST06], as well as cache-induced differences in timing and electromagnetic behavior. For, EC scalar-by-point multiplication, the scalar can be represented in a regular way such that the DA-sequence does not depend on the nonce [JT09, Möl01b]; Moller [Möl01b] notes 16

Figure 10: Power (left) and EM (right) measurement (0.2 sec, 0–96 kHz) of five scalar-by-point multiplication operations using the NIST P-521 curve executed on an iPhone 4 smartphone running OpenSSL. As in Figure 2, the scalar was set to be either a random 521-digit number or a the 521digit number obtained by repeating the pattern written to the right. In all cases, the same curve point was used to perform the multiplication.

Figure 11: Extracted DA-sequence obtained from iPhone 3GS during an OpenSSL secp256k1 signature operation. The leakage was measured using the Tracker Pre sound card and the improvised EM probe. The double and add operations can clearly be seen. that these encodings may leak information when a point is added to itself, yet with a random scalar, as is the case in ECDSA, the probability of this leak is negligible. A constant-time implementation for some elliptic curves, on some 64-bit platforms, is included in OpenSSL [Käs12]. For Bitcoin’s secp256k1 curve, the libsecp256k1 [Wui] implementation offers a constant-time, constant-memoryaccess implementation of ECDSA signing. Future Work. While this work clearly demonstrates the vulnerability of multiple implementations of ECDSA signatures running on mobile devices to cheap low-bandwidth key extraction attacks, much works remains to be done. The vulnerability of other ECDSA implementations, as well as general cryptographic code running on mobile devices has received much research attention. Improving the signal quality, thereby increasing the attack range and reducing the number of required signatures is an intriguing open problem. To that end, we note that the more advanced lattice techniques of [Van de PolSY15, ABF+ 15] are of potential use in order to reduce the number of signatures. However, our signal is too corrupted (due to interrupts) making these techniques inapplicable without significant improvements in signal processing techniques.

17

Acknowledgments This work was supported by the Blavatnik Interdisciplinary Cyber Research Center; by the Check Point Institute for Information Security; by a Google Faculty Research Award; by the Israeli Centers of Research Excellence I-CORE program (center 4/11); by the Leona M. & Harry B. Helmsley Charitable Trust; and by NATO’s Public Diplomacy Division in the Framework of ”Science for Peace”. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.

A

Current Status of Targeted Software

This appendix reviews the vulnerability status of the targeted software, at the time of writing. OpenSSL 1.0.x branch. We have conducted most of our experiments on OpenSSL version 1.0.1m which was the latest version at the time of conducting this research. For ARM processors, all curves over prime fields in the current versions of OpenSSL (1.0.1r and 1.0.2f) use the same underlying elliptic curve implementation and should be vulnerable to attacks as well. While we did not attempt key extraction, scalar dependent leakage (similar to Figure 2) was empirically observed from these OpenSSL versions as well. Upon contacting OpenSSL we were notified that “hardware side-channel attacks are not in OpenSSL’s threat model”, so no updates are planned to OpenSSL 1.0.x to mitigate our attacks. Note that OpenSSL 1.0.2 will be supported until the year 2020, OpenSSL 1.1.x branch. OpenSSL 1.1.0 pre-release 3 includes an ARM-specific constant-time implementations of the NIST P-256 curve, which is unlikely to be vulnerable to similar attacks. All other curves over prime fields, including the secp256k1 curve, still use the vulnerable wNAF implementation. iOS 7.1.2–8.3 CommonCrypto. The ECDSA implementation in the CommonCrypto framework of iOS 7.1.2 appears vulnerable, since it exhibits scalar-dependent leakage (see Section 3.3). Reverse-engineering the code in iOS 8.3 reveals that it uses the same vulnerable implementation (wNAF with w = 1). iOS 9.x CommonCrypto. Starting with iOS 9, CommonCrypto uses a new EC implementation, including side-channel mitigation techniques such as operand-independent control flow and Montgomery-ladder multiplication.3 Our current attacks are not applicable to this new EC implementation, and we have no evidence that it is vulnerable. CoreBitcoin. CoreBitcoin [Cor] (not to be confused with Bitcoin core, below) is currently vulnerable, as discussed in Section 3.3. In response. the CoreBitcoin developers expressed their intention to switch to using the libsecp256k1 library [Wui] in the future. This library offers a constant-time, constant-memory-access implementation of ECDSA signing, and we have no evidence that it is vulnerable. Bitcoin Core. The Bitcoin core code [Bita] (not to be confused with the CoreBitcoin, above) has already transitioned to using the libsecp256k1 library [Wui] for ECDSA signing, starting from version v0.10.0 (released in February 2015).4 This library offers a constant-time, constant-memoryaccess implementation of ECDSA signing, and we have no evidence that it is vulnerable. 3 The relevant code is in the corecrypto library version 337 [App]. The Apple Product Security confirmed that this is, essentially, the implementation in all iOS 9.x versions, as well as OS X 10.11, and that 77% of the iOS installations are iOS 9.x, as of February 2016. 4 Bitcoin Git commit fda3fed18a added support for libsecp256k1 ECDSA signing, and commit dffb8f81b8 removed support for OpenSSL ECDSA signing.

18

References [AAF+ 11]

D. Aboulkassimi, M. Agoyan, L. Freund, J. Fournier, B. Robisson, and A. Tria. Electromagnetic analysis (EMA) of software AES on Java mobile phones. In Workshop on Information Forensics and Security (WIFS) 2011, pages 1–6. IEEE Computer Society, 2011.

[AARR02]

Dakshi Agrawal, Bruce Archambeault, Josyula R. Rao, and Pankaj Rohatgi. The EM side-channel(s). In Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2002, pages 29–45. Springer, 2002.

[ABC+ ]

M. Albrecht, S. Bai, D. Cadé, X. Pujol, and D. Stehlé. fplll-4.0, a floating-point LLL implementation. URL: http://perso.ens-lyon.fr/damien.stehle.

[ABF+ 15]

Thomas Allan, Billy Bob Brumley, Katrina E. Falkner, Joop van de Pol, and Yuval Yarom. Amplifying side channels through performance degradation. Cryptology ePrint Archive, Report 2015/1141, 2015. http://eprint.iacr.org/2015/ 1141.

[ADMM15]

Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, and Lukasz Mazurek. On the malleability of Bitcoin transactions. In Financial Cryptography and Data Security - FC 2015, pages 1–18, 2015.

[AFG+ 14]

Diego F. Aranha, Pierre-Alain Fouque, Benoˆıt Gérard, Jean-Gabriel Kammerer, Mehdi Tibouchi, and Jean-Christophe Zapalowicz. GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias. In ASIACRYPT 2014, Part I, pages 262–281. Springer, 2014.

[And08]

Ross J. Anderson. Security Engineering — A Guide to Building Dependable Distributed Systems (2nd ed.). Wiley, 2008.

[App]

Apple Inc. Cryptographic libraries. URL: https://developer.apple.com/ cryptography/.

[ARC]

Arcbit. URL: http://arcbit.io/.

[BB05]

David Brumley and Dan Boneh. Remote timing attacks are practical. Computer Networks, 48(5):701–716, 2005.

[Ber05]

Daniel J. Bernstein. Cache-timing attacks on AES. http://cr.yp.to/papers. html#cachetiming, 2005.

[BFMRT16]

Pierre Belgarric, Pierre-Alain Fouque, Gilles Macario-Rat, and Mehdi Tibouchi. Side-channel analysis of Weierstrass and Koblitz curve ECDSA on Android smartphones. In RSA Conference Cryptographers’ Track (CT-RSA) 2016. Springer, 2016. To Appear.

[BGRV15]

Josep Balasch, Benedikt Gierlichs, Oscar Reparaz, and Ingrid Verbauwhede. DPA, bitslicing and masking at 1 GHz. In Cryptographic Hardware and Embedded Systems (CHES) 2015, pages 599–619. Springer, 2015.

[BH09]

Billy Bob Brumley and Risto M. Hakala. Cache-timing template attacks. In ASIACRYPT 2009, volume 5912 of Lecture Notes in Computer Science, pages 667–684. Springer, 2009.

[Bita]

Bitcoin Core. URL: https://bitcoin.org/en/bitcoin-core/.

[Bitb]

BitStore. URL: http://bitstoreapp.com/. 19

[Bitc]

BitWallet. URL: https://bitwallet.cc/.

[BT11]

Billy Bob Brumley and Nicola Tuveri. Remote timing attacks are still practical. In ESORICS 2011, pages 355–371. Springer, 2011.

[BvdPSY14]

Naomi Benger, Joop van de Pol, Nigel P. Smart, and Yuval Yarom. ”Ooh aah... just a little bit” : A small amount of side channel can go a long way. In Cryptographic Hardware and Embedded Systems (CHES) 2014, pages 75–92, 2014.

[CJ01]

Christophe Clavier and Marc Joye. Universal exponentiation algorithm. In Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2001, pages 300–308. Springer, 2001.

[CJ03]

Mathieu Ciet and Marc Joye. (virtually) free randomization techniques for elliptic curve cryptography. In International Conference Information and Communications Security (ICICS) 2003, pages 348–359. Springer, 2003.

[Cor]

CoreBitcoin Library. URL: https://github.com/oleganza/CoreBitcoin.

[Cor99]

Jean-Sébastien Coron. Resistance against differential power analysis for elliptic curve cryptosystems. In Cryptographic Hardware and Embedded Systems (CHES) 2002, pages 292–302, 1999.

[CRI12]

SPA/SEMA vulnerabilities of popular RSA-CRT sliding window implementations, 2012. presented at Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2012 rump session. URL: https://www.cosic.esat. kuleuven.be/ches2012/ches_rump/rs5.pdf.

[FGM+ 10]

Junfeng Fan, Xu Guo, Elke De Mulder, Patrick Schaumont, Bart Preneel, and Ingrid Verbauwhede. State-of-the-art of secure ECC implementations: A survey on known side-channel attacks and countermeasures. In Proceedings of the 2010 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST) 2010, pages 76–87, 2010.

[FV12]

Junfeng Fan and Ingrid Verbauwhede. An updated survey on secure ECC implementations: Attacks, countermeasures and cost. In Cryptography and Security: From Theory to Applications - Essays Dedicated to Jean-Jacques Quisquater on the Occasion of His 65th Birthday, pages 265–282, 2012.

[GMO01]

Karine Gandolfi, Christophe Mourtel, and Francis Olivier. Electromagnetic analysis: concrete results. In Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2001, pages 251–261. Springer, 2001.

[GMPT15]

Jake Longo Galea, Elke De Mulder, Dan Page, and Michael Tunstall. Soc it to EM: electromagnetic side-channel attacks on a complex system-on-chip. In Cryptographic Hardware and Embedded Systems (CHES) 2015, pages 620–640. Springer, 2015.

[GPPT15]

Daniel Genkin, Lev Pachmanov, Itamar Pipman, and Eran Tromer. Stealing keys from PCs using a radio: Cheap electromagnetic attacks on windowed exponentiation. In Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2015, pages 207–228, 2015. Extended version: Cryptology ePrint Archive, Report 2015/170.

[GPPT16]

Daniel Genkin, Lev Pachmanov, Itamar Pipman, and Eran Tromer. ECDH key-extraction via low-bandwidth electromagnetic attacks on PCs. In RSA Conference Cryptographers’ Track (CT-RSA) 2016, pages 219–235, 2016. 20

[GPT14]

Daniel Genkin, Itamar Pipman, and Eran Tromer. Get your hands off my laptop: Physical side-channel key-extraction attacks on PCs. In Workshop on Cryptographic Hardware and Embedded Systems (CHES) 2014, pages 242–260. Springer, 2014. Extended version: Cryptology ePrint Archive, Report 2014/626.

[GS15]

Gabriel Goller and Georg Sigl. Side channel attacks on smartphones and embedded devices using standard radio equipment. In International Workshop on Constructive Side-Channel Analysis and Secure Design (COSADE) 2015, pages 255–270. Springer, 2015.

[GST14]

Daniel Genkin, Adi Shamir, and Eran Tromer. RSA key extraction via lowbandwidth acoustic cryptanalysis. In CRYPTO 2014, pages 444–461 (vol. 1). Springer, 2014. Extended version: Cryptology ePrint Archive, Report 2013/857.

[GZ13]

Nina Golyandina and Anatoly Zhigljavsky. Singular Spectrum Analysis for Time Series. Springer, 2013.

[Has07]

Hossein Hassani. Singular spectrum analysis: Methodology and comparison. J. of Data Science, (5):239–257, 2007.

[JT09]

Marc Joye and Michael Tunstall. Exponent recoding and regular exponentiation algorithms. In AFRICACRYPT 2009, pages 334–349. Springer, 2009.

[Käs12]

Emilia K¨ asper. Fast elliptic curve cryptography in OpenSSL. In Financial Cryptography and Data Security (FC) 2011, pages 27–39. Springer, 2012.

[KJJR11]

Paul Kocher, Joshua Jaffe, Benjamin Jun, and Pankaj Rohatgi. Introduction to differential power analysis. Journal of Cryptographic Engineering, 1(1):5–27, 2011.

[KP11]

Md Atikur Rahman Khan and D.S. Poskitt. Window Length Selection and Signal-Noise Separation and Reconstruction in Singular Spectrum Analysis. Monash Econometrics and Business Statistics Working Papers 23/11, Monash University, Department of Econometrics and Business Statistics, 2011. URL: https://ideas.repec.org/p/msh/ebswps/2011-23.html.

[KR12]

Gary Kenworthy and Pankaj Rohatgi. Mobile device security: The case for side channel resistance. In Mobile Security Technologies (MoST) 2012, 2012.

[LGSM15]

Moritz Lipp, Daniel Gruss, Raphael Spreitzer, and Stefan Mangard. ARMageddon: Last-level cache attacks on mobile devices. CoRR, abs/1511.04897, 2015. http://arxiv.org/abs/1511.04897.

[Mic]

Working with micropayment channels. URL: https://bitcoinj.github.io/ working-with-micropayments.

[Möl01a]

Bodo M¨ oller. Algorithms for multi-exponentiation. In Selected Areas in Cryptography (SAC) 2001, pages 165–180. Springer, 2001.

[Möl01b]

Bodo M¨ oller. Securing elliptic curve point multiplication against side-channel attacks. In Information Security Conference (ISC) 2001, pages 324–334. Springer, 2001.

[MOP07]

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

[Myc]

Mycelium wallet. URL: https://mycelium.com/mycelium-wallet.html.

21

[Ngu11]

Phong Q. Nguyen. Lattice reduction algorithms: Theory and practice. In Eurocrypt 2011, pages 2–6, Tallinn, Estonia, May 2011.

[NIS13]

nist. Digital Signature Standard (DSS), 2013.

[NS03]

Phong Q. Nguyen and Igor Shparlinski. The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Des. Codes Cryptography, 30(2):201–217, 2003.

[NSN+ 14]

Yuto Nakano, Youssef Souissi, Robert Nguyen, Laurent Sauvage, Jean-Luc Danger, Sylvain Guilley, Shinsaku Kiyomoto, and Yutaka Miyake. A pre-processing composition for secret key recovery on Android smartphone. In Information Security Theory and Practice (WISTP) 2014, pages 76–91. Springer, 2014.

[OST06]

Dag Arne Osvik, Adi Shamir, and Eran Tromer. Cache attacks and countermeasures: The case of AES. In RSA Conference Cryptographers’ Track (CT-RSA) 2006, pages 1–20. Springer, 2006.

[Per05]

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

[van de PolSY15] Joop van de Pol, Nigel P. Smart, and Yuval Yarom. Just a little bit more. In RSA Conference Cryptographers’ Track (CT-RSA) 2015, pages 3–21, 2015. [Por13]

T. Pornin. Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algorithm (ECDSA). RFC 6979, 2013.

[PS15]

Santos Merino Del Pozo and Fran¸cois-Xavier Standaert. Blind source separation from single measurements using singular spectrum analysis. In Cryptographic Hardware and Embedded Systems (CHES) 2015, pages 42–59. Springer, 2015.

[QS01]

Jean-Jacques Quisquater and David Samyde. Electromagnetic analysis (EMA): Measures and counter-measures for smart cards. In E-smart 2001, pages 200–210, 2001.

[Rei60]

George W. Reitwiesner. Binary arithmetic. Advances in Computers, 1:231–308, 1960.

[Smi15]

Chris Smith. What are micropayments and how does Bitcoin enable them?, 2015. URL: https://coincenter.org/2015/06/ what-are-micropayments-and-how-does-bitcoin-enable-them/.

[Wui]

Pieter Wuille. libsecp256k1. URL: https://github.com/bitcoin/secp256k1.

[Wui14]

Pieter Wuille. Dealing with malleability, 2014. URL: https://github.com/ bitcoin/bips/blob/master/bip-0062.mediawiki.

[Yel]

Yellet. URL: https://www.yallet.com/.

[ZP14]

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

22