$\mu(m_i)$ modulo $N$ is very small. Then, the attack can be applied to the integers $t_i$ instead of $\mu(m_i)$.

More precisely, suppose that one can find a constant $a$ and messages $m_i$ such that for all $i$:

$$t_i = a \cdot \mu(m_i) \mod N$$

is small. Then we can hope to find many smooth $t_i$'s, and the attack can proceed as before. There is no problem in handling of the extra factor $a$ in the multiplicative relations: one only needs to add a corresponding column in the matrix of exponents considered in §9.3.1 to keep track of it.

In their attack Coron et al. used $a = 2^8$. Then, to construct messages $m$ such that $a \cdot \mu(m) \mod N$ is small can be done as follows. From the definition of ISO/IEC 9796-2, we have:

$$\begin{aligned} \mu(m) &= \mathbf{6A}_{16} \quad \parallel \mathbf{m}[1] \quad \parallel \mathbf{H}(m) \quad \parallel \mathbf{BC}_{16} \\ &= \mathbf{6A}_{16} \cdot 2^{k-8} + \mathbf{m}[1] \cdot 2^{k_h+8} + \mathbf{H}(m) \cdot 2^8 + \mathbf{BC}_{16} \end{aligned}$$

Euclidean division by $N$ provides $b$ and $0 \le r < N < 2^k$ such that:

$$(\mathbf{6A}_{16} + 1) \cdot 2^k = b \cdot N + r$$

Denoting $N' = b \cdot N$ one can write:

$$\begin{aligned} N' &= \mathbf{6A}_{16} \cdot 2^k + (2^k - r) \\ &= \mathbf{6A}_{16} \quad \parallel \mathbf{N'}[1] \parallel \mathbf{N'}[0] \end{aligned}$$

where $N'$ is $k + 7$ bits long and $N'[1]$ is $k - k_h - 16$ bits long.

Consider the linear combination:

$$\begin{aligned} t &= b \cdot N - a \cdot \mu(m) \\ &= N' - 2^8 \cdot \mu(m) \end{aligned}$$

By setting $m[1] = N'[1]$ we get:

$$\begin{aligned} t &= \mathbf{6A}_{16} \quad \parallel \mathbf{N'}[1] \quad \parallel \mathbf{N'}[0] \\ &= - \mathbf{6A}_{16} \quad \parallel \mathbf{m}[1] \quad \parallel \mathbf{H}(m) \parallel \mathbf{BC}_{00}_{16} \\ &= - \mathbf{6A}_{16} \quad \parallel \mathbf{N'}[1] \quad \parallel \mathbf{N'}[0] \\ &= - \mathbf{6A}_{16} \quad \parallel \mathbf{N'}[1] \quad \parallel \mathbf{H}(m) \parallel \mathbf{BC}_{00}_{16} \\ &= \mathbf{N'}[0] - (\mathbf{H}(m) \parallel \mathbf{BC}_{00}_{16}) < 2^{k_h+16} \end{aligned}$$

For $k_h = 160$, the integer $t$ is therefore at most 176-bits long.

The forger can thus modify $m[2]$ (and therefore $H(m)$), until he gets a set of messages whose $t$-values are $B$-smooth and express one such $\mu(m_\tau)$ as a multiplicative combination of the others. As per the analysis in [CNS99], attacking the instances $k_h = 128$ and $k_h = 160$ requires $2^{54}$ and $2^{61}$ operations respectively.

Note that the sign of the $t_i$'s must be accounted for. This is simple because $(-1)^d \mod N$ is public. Hence, when an odd number of $t_i$'s is used a minus sign is inserted into $\delta$.
## 9.4 Building Blocks of the New Attack

We improve the above complexities by using four new ideas: we speed up the process of finding smooth integers by using Bernstein's batch smoothness detection algorithm [Ber04a] instead of trial division; we also use the large prime variant [BP96]; moreover, we modify Coron et al.'s attack by selecting better messages and by optimizing exhaustive search to balance complexities. In this section we present these new building blocks.

### 9.4.1 Bernstein's smoothness detection algorithm

Bernstein [Ber04a] describes the following algorithm for finding smooth integers.

**Algorithm:** Given prime numbers $p_1, \dots, p_\ell$ in increasing order and positive integers $t_1, \dots, t_n$, output the $p_\ell$-smooth part of each $t_k$:

1. Compute $z \leftarrow p_1 \times \dots \times p_\ell$ using a product tree.

2. Compute $z_1 \leftarrow z \bmod t_1, \dots, z_n \leftarrow z \bmod t_n$ using a remainder tree.

3. For each $k \in \{1, \dots, n\}$: Compute $y_k \leftarrow (z_k)^{2^e} \bmod t_k$ by repeated squaring, where $e$ is the smallest non-negative integer such that $2^{2^e} \ge t_k$.

4. For each $k \in \{1, \dots, n\}$: output $\gcd(t_k, y_k)$.

We refer the reader to [Ber08] for a description of the product and remainder trees.

**Theorem 9.1 (Bernstein).** *The algorithm computes the $p_\ell$-smooth part of each integer $t_k$ in $O(b \log^2 b \log \log b)$ time, where $b$ is the number of input bits.*

In other words, given a list of $n_t$ integers $t_i < 2^a$ and the list of the first $\ell$ primes, the algorithm will detect the $B$-smooth $t_i$'s, where $B = p_\ell$, in time:

$$O(b \cdot \log^2 b \cdot \log \log b)$$

where $b = n_t \cdot a + \ell \cdot \log_2 \ell$ is the total number of input bits.

When $n_t$ is very large, it becomes more efficient to run the algorithm $k$ times, on batches of $n'_t = n_t/k$ integers. We explain in Appendix 9.A how to select the optimal $n'_t$, and derive the corresponding running time.

Bernstein recommends a number of speed-up ideas of which we used a few. In our experiments we used the *scaled remainder tree* [Ber04b], which replaces most division steps in the remainder tree by multiplications. This algorithm is fastest when FFT multiplications are done modulo numbers of the form $2^\alpha - 1$: we used this *Mersenne FFT multiplication* as well, as implemented in Gaudry, Kruppa and Zimmermann's GMP patch [GKZ07]. Other optimizations included computing the product $z$ only once, and treating the prime 2 separately.

Bernstein's algorithm was actually the main speed up in our attack. It proved $\simeq 1000$ faster than the trial division used in [CNS99].
## 9.4.2 The large prime variant

An integer is semi-smooth with respect to $y$ and $z$ if its greatest prime factor is $\le y$ and all other factors are $\le z$. Bach and Peralta [BP96] define the function $\sigma(u, v)$, which plays for semi-smoothness the role played by Dickman's $\rho$ function for smoothness [Dic30]: $\sigma(u, v)$ is the asymptotic probability that an integer $n$ is semi-smooth with respect to $n^{1/v}$ and $n^{1/u}$.

After an integer $t_i$ has had all its factors smaller than $B$ stripped-off, if the remaining factor $\omega$ is lesser than $B^2$ then $\omega$ must be prime. This is very easy to detect using Bernstein's algorithm. As Bernstein computes the B-smooth part $z_i$ of each $t_i$, it only remains to check whether $t_i/z_i$ is small enough. In most cases it isn't even necessary to perform the actual division since comparing the sizes of $t_i$ and $z_i$ suffices to rule out most non-semi-smooth numbers.

Hence, one can use a second bound $B_2$ such that $B < B_2 < B^2$ and keep the $t_i$'s whose remaining factor $\omega$ is $\le B_2$, hoping to find a second $t_i$ with the same remaining factor $\omega$ to divide $\omega$ out. We refer the reader to Appendix 9.B for a detailed analysis of the large prime variant in our context.

## 9.4.3 Constructing smaller $a \cdot \mu(m) - b \cdot N$ candidates

In this paragraph we show how to construct smaller $t_i = a \cdot \mu(m_i) - b \cdot N$ values for ISO/IEC 9796-2. Smaller $t_i$-values increase smoothness probability and hence speed up the forgery process. We write:

$$ \mu(x, h) = 6A_{16} \cdot 2^{k-8} + x \cdot 2^{k_h+8} + h \cdot 2^8 + BC_{16} $$

where $x = m[1]$ and $h = H(m)$, with $0 < x < 2^{k-k_h-16}$.

We first determine $a, b > 0$ such that the following two conditions hold:

$$ 0 < b \cdot N - a \cdot \mu(0, 0) < a \cdot 2^{k-8} \qquad (9.3) $$

$$ b \cdot N - a \cdot \mu(0, 0) = 0 \quad \mod 2^8 \qquad (9.4) $$

and $a$ is of minimal size. Then by Euclidean division we compute $x$ and $r$ such that:

$$ b \cdot N - a \cdot \mu(0, 0) = (a \cdot 2^{k_h+8}) \cdot x + r $$

where $0 \le r < a \cdot 2^{k_h+8}$ and using (9.3) we have $0 \le x < 2^{k-k_h-16}$ as required. This gives:

$$ b \cdot N - a \cdot \mu(x, 0) = b \cdot N - a \cdot \mu(0, 0) - a \cdot x \cdot 2^{k_h+8} = r $$

Moreover as per (9.4) we must have $r = 0 \mod 2^8$; denoting $r' = r/2^8$ we obtain:

$$ b \cdot N - a \cdot \mu(x, h) = r - a \cdot h \cdot 2^8 = 2^8 \cdot (r' - a \cdot h) $$

where $0 \le r' < a \cdot 2^{k_h}$. We then look for smooth values of $r' - a \cdot h$, whose size is at most $k_h$ plus the size of $a$.
<table><caption>Table 9.1: {$a, b$} values for several RSA challenge moduli.</caption><thead><tr><th>Challenge</th><th>RSA-704</th><th>RSA-768</th><th>RSA-896</th><th>RSA-1024</th><th>RSA-1536</th><th>RSA-2048</th></tr></thead><tbody><tr><td>a</td><td>481</td><td>251</td><td>775</td><td>311</td><td>581</td><td>625</td></tr><tr><td>b</td><td>228</td><td>132</td><td>412</td><td>172</td><td>316</td><td>332</td></tr></tbody></table>

If $a$ and $b$ are both 8-bit integers, this gives 16 bits of freedom to satisfy both conditions (9.3) and (9.4); heuristically each of the two conditions is satisfied with probability $\approx 2^{-8}$; therefore, we can expect to find an {$a, b$} pair with $a$ and $b$ not much larger than 8 bits. For example, for the RSA-2048 challenge, we found {$a, b$} to be {625, 332}; therefore, for RSA-2048 and $k_h = 160$, the integer to be smooth is 170-bits long (instead of 176-bits in Coron et al.'s original attack). This decreases the complexity of the attack further. The optimal {$a, b$} values for other RSA challenge moduli are given in Table 9.1.

## 9.5 Attacking ISO/IEC 9796-2

We combined all the building-blocks listed in the previous section to compute an actual forgery for ISO/IEC 9796-2, with the RSA-2048 challenge modulus. The implementation replaced Coron et al.'s trial division by Bernstein's algorithm, replaced Coron et al.'s $a \cdot \mu(m) - b \cdot N$ values by the shorter $t_i$'s introduced in §9.4.3 and took advantage of the large prime variant. Additional speed-up was obtained by exhaustive searching for particular digest values. Code was written in C++ and run on 19 Linux-based machines on the Amazon EC2 cloud. The final linear algebra step was performed on a single desktop PC.

### 9.5.1 The Amazon cloud

Amazon.com, Inc. offers virtualized computer instances for rent on a pay by the hour basis, which we found convenient to run our computations. Various models are available, of which the best-suited for CPU-intensive tasks, at the time when we carried out the attack, featured 8 Intel Xeon 64-bit cores clocked at 2.4 GHz supporting the Core2 instruction set and offering 7 GB RAM and 1.5 TB disk space. Renting such a capacity cost US$0.80 per hour (plus tax). One could run up to 20 such instances in parallel, and possibly more subject to approval by Amazon (20 were enough for our purpose so we didn't apply for more).

When an instance on the grid is launched, it starts up from a disk image containing a customizable UNIX operating system. In the experiment, we ran a first instance using the basic Fedora installation provided by default, installed necessary tools and libraries, compiled our own programs and made a disk image containing our code, to launch subsequent instances with. When an instance terminates, its disk space is freed, making it necessary to save results to some permanent storage means. We simply rsync'ed
results to a machine of ours. Note that Amazon also charges for network bandwidth but
data transmission costs were negligible in our case.

All in all, we used about 1,100 instance running hours (including setup and tweaks)
during a little more than two days. While we found the service to be rather reliable, one
instance failed halfway through the computation, and its intermediate results were lost.

**9.5.2 The experiment: Outline, details and results**

The attack can be broken down into the following elementary steps, which we shall review
in turn:

1. Determining the constants $a, b, x, \mu(x, 0)$ for the RSA-2048 challenge modulus $N$.

2. Computing the product of the first $\ell$ primes, for a suitable choice of $\ell$.

3. Computing the integers $t_i = bN - a\mu(m_i)$, and hence the SHA-1 digests, for sufficiently many messages $m_i$.

4. Finding the smooth and semi-smooth integers amongst the $t_i$'s.

5. Factoring the smooth integers, as well as the colliding pairs of semi-smooth integers, obtaining the sparse, singular matrix of exponents, with $\ell$ rows and more than $\ell$ columns.

6. Reducing this matrix modulo $e = 2$, with possible changes in the first row (corresponding to the prime 2) depending on the Jacobi symbols $(2|t_i)$ and $(2|a)$.

7. Finding nontrivial vectors in the kernel of this reduced matrix and inferring a forgery.

Steps 2-4 were executed on the Amazon EC2 grid, whereas all other steps were run
on one offline PC. Steps 3-4, and to a much lesser extent Step 7, were the only steps
that claimed a significant amount of CPU time.

*Determining the constants.* The cost of the attack doesn’t depend on the choice of *N*. Since *N* has to be congruent to 5 mod 8 for Rabin-Williams signatures, we used the RSA-2048 challenge. The resulting constants were computed in SAGE [S+10b]. We found the smallest {a, b} pair to be {625, 332}. The integers $t_i = bN - a\mu(x, h_i)$ are thus at most 170-bits long.

*Product of the first primes.* The optimal choice of $\ell$ for 170 bits is about $2^{21}$. Since the Amazon instances are memory-constrained (less than 1 GB of RAM per core), we preferred to use $\ell = 2^{20}$. This choice had the additional advantage of making the final linear algebra step faster, which is convenient since this step was run on a single offline PC. Computing the product of primes itself was done once and for all in a matter of seconds using MPIR [H+09].
**Hashing.** Since the smoothness detection part works on batches of $t_i$'s (in our cases, we chose batches of $2^{19}$ integers), we had to compute digests of messages $m_i$ in batches as well. The messages themselves are 2048-bit long, i.e. as long as $N$, and we chose them in a fixed format facilitating the distributed computation: a constant 246-byte prefix followed by a 10-byte seed. The first two bytes identify a family of messages examined on a single core of one Amazon instance, and the remaining eight bytes are explored by increments of 1 starting from 0.

Messages were hashed using the SHA-1 implementation from OpenSSL. For each message, we only need to compute one SHA-1 block, since the first three 64-byte blocks are fixed. This computation is relatively fast compared to Bernstein's algorithm, so we have a bit of leeway for exhaustive search. We can compute a large number of digests, keeping the ones likely to give rise to a smooth $t_i$. We did this by selecting digests for which the resulting $t_i$ would have many zeros as leading and trailing bits.

More precisely, we looked for a particular bit pattern at the beginning and at the end of each digest $h_i$, such that finding $n$ matching bits results in $n$ null bits at the beginning and at the end of $t_i$. The probability of finding $n$ matching bits when we add the number of matches at the beginning and at the end is $(1 + n/2) \cdot 2^{-n}$, so we expect to compute $2^n/(1 + n/2)$ digests per selected message. We found $n = 8$ to be optimal: on average, we need about 50 digests to find a match, and the resulting $t_i$ is at most $170 - 8 = 162$ bit long once powers of 2 are factored out.

Note that faster (e.g. hardware-enhanced) ways to obtain digests might significantly reduce the running time of the attack. We considered for example an FPGA-based solution called COPACOBANA [P+09], which could in principle perform a larger amount of exhaustive search, and speed up the attack dramatically. It turned out that our attack was fast enough, hence pursuing the hardware-assisted search idea further proved unnecessary, but a practical attack on EMV (see §9.7) could certainly benefit from hardware acceleration.

At present, Amazon is also renting time on instances equipped with fast GPUs. As GPUs are notoriously well-suited for the evaluation of hash functions like SHA-1, it might be interesting to try and run the attack on such machines.

**Finding smooth and semi-smooth integers.** Once a batch of $2^{19}$ appropriate $t_i$'s is generated, we factor out powers of 2, and feed the resulting odd numbers into our C++ implementation of Bernstein's algorithm. This implementation uses the MPIR multiprecision arithmetic library [H+09], which we chose over vanilla GMP because of a number of speed improvements, including J.W. Martin's patch for the Core2 architecture. We further applied Gaudry, Kruppa and Zimmermann's FFT patch, mainly for their implementation of *Mersenne FFT multiplication*, which is useful in the scaled remainder tree [Ber04b].

We looked for B-smooth and for $(B, B_2)$-semi-smooth $t_i$'s, where $B = 16,290,047$ is the $2^{20}$-th prime, and $B_2 = 2^{27}$. Each batch took $\simeq 40$ seconds to generate and to process, and consumed about 500 MB of memory. We ran 8 such processes in parallel on each instance to take advantage of the 8 cores, and 19 instances simultaneously.
Finding the 1,050,667 columns (slightly in excess of the $l = 2^{20} = 1,048,576$ required) took a little over 2 days.

***Factoring and finding collisions.*** The output of the previous stage is a large set of text files containing the smooth and semi-smooth $t_i$'s together with the corresponding message numbers. Turning this data into a matrix suitable for the linear algebra stage mostly involved text manipulation in Perl to convert it to commands that could be piped into PARI/GP [Gro08]. The resulting 1,048,576 × 1,050,667 matrix had 14,215,602 non-zero entries (13.5 per column on average, or $10^{-5}$ sparsity; the columns derived from the large prime variant tend to have twice as many non-zero entries, of course).<fnref n="3" />

***Linear algebra.*** We found non-zero kernel elements of the final sparse matrix over GF(2) using Coppersmith's block Wiedemann algorithm [Cop94] implemented in WLSS2 [KL99, Lob95], with parameters $m = n = 4$ and $\kappa = 2$. The whole computation took 16 hours on one 2.7 GHz personal computer, with the first (and longest) part of the computation using 2 cores, and the final part using 4 cores.

The program discovered 124 kernel vectors with Hamming weights ranging from 337,458 to 339,641. Since columns obtained from pairs of semi-smooth numbers account for two signatures each, the number of signature queries required to produce the 124 corresponding forgeries is slightly larger, and ranges between 432,903 and 435,859.

Being written with the quadratic sieve in mind, the block Wiedemann algorithm in WLSS2 works over GF(2). There exist, however, other implementations for different finite fields.

The whole experiment is summarized in Figure 9.1.

***Fewer signature queries.*** In Appendix 9.E we address the question of reducing the number of signature queries in the attack.

## 9.6 Cost Estimates

The experiment described in the previous section can be used as a benchmark to estimate the cost of the attack as a function of the size of the $t_i$'s, denoted $a$; this will be useful for analyzing the security of the EMV specifications, where $a$ is bigger (204 bits instead of 170 bits).

We assume that the $t_i$'s are uniformly distributed $a$-bit integers and express costs as a function of $a$. It is then easy to estimate the number of hash computations and smoothness tests necessary for the attack, since we know, by the work of Bach and

<footnote n="3">³This matrix actually contained a number of rows with only one nonzero entry or less. Those rows and the corresponding columns can be safely removed, and the process can be repeated on the resulting matrix until a fix-point is reached (see Appendix 9.F for details). This reduction process is frequently the first operation carried out by linear algebra packages when searching for kernel vectors. When applied to our matrix, it produced a reduced matrix of dimension 750,031 × 839,908. We found it most convenient to leave any such reduction step to the linear algebra package itself.</footnote>
<figure><img src="image_18.png" /><figcaption>Figure 9.1: Summary of the practical attack on ISO/IEC 9796-2.</figcaption></figure>

<table><caption>Table 9.2: Bernstein & large prime variant. Estimated parameter trade-offs, running times and costs, for various $t_i$ sizes.</caption><thead><tr><th>a = log<sub>2</sub> t<sub>i</sub></th><th>log<sub>2</sub> l</th><th>Estimated TotalTime</th><th>log<sub>2</sub> &tau;</th><th>EC2 cost (US$)</th></tr></thead><tbody><tr><td>64</td><td>11</td><td>15 seconds</td><td>20</td><td>negligible</td></tr><tr><td>128</td><td>19</td><td>4 days</td><td>33</td><td>10</td></tr><tr><td>160</td><td>21</td><td>6 months</td><td>38</td><td>470</td></tr><tr><td>170</td><td>22</td><td>1.8 years</td><td>40</td><td>1,620</td></tr><tr><td>176</td><td>23</td><td>3.8 years</td><td>41</td><td>3,300</td></tr><tr><td>204</td><td>25</td><td>95 years</td><td>45</td><td>84,000</td></tr><tr><td>232</td><td>27</td><td>19 centuries</td><td>49</td><td>1,700,000</td></tr><tr><td>256</td><td>30</td><td>320 centuries</td><td>52</td><td>20,000,000</td></tr></tbody></table>

Peralta [BP96], the proportion of semismooth integers with respect to given bounds among all $a$-bit integers. The semismoothness bounds themselves are selected according to the results of Appendix 9.B.

Results are summarized in Table 9.2. Cost figures do not include the linear algebra step whose computational requirements are very low compared to the smoothness detection step. Another difference with our experiment is that here we do not assume any exhaustive search on the $t_i$'s; this is why the cost estimate for $a = 170$ in Table 9.2 is about twice
the actual cost of our experimental ISO/IEC 9796-2 forgery.

Running times are given for a single 2.4 GHz PC. Costs correspond to the Amazon EC2 cloud (as of February 2009) like in the previous section. Estimates show that the attack is feasible up to ≃ 200 bits, but becomes infeasible for larger values of a. We also estimate log₂ τ, where τ is the number of messages in the forgery.

## 9.7 Application to EMV Signatures

EMV is a collection of industry specifications for the inter-operation of payment cards, POS terminals and ATMs. The EMV specifications [EMV] rely on ISO/IEC 9796-2 signatures to certify public keys and to authenticate data. For instance, when an Issuer provides application data to a Card, this data must be signed using the Issuer's private key $S_I$. The corresponding public-key $P_I$ must be signed by a Certification Authority (CA) whose public key is denoted by $P_{CA}$. The signature algorithm is RSA with $e = 3$ or $e = 2^{16} + 1$. The bit length of all moduli is always a multiple of 8.

EMV uses special message formats; 7 different formats are used, depending on the message type. We first describe one of these formats: the *Static Data Authentication, Issuer Public Key Data* (SDA-IPKD), and adapt our attack to it. The other six formats are examined in Appendix 9.D.

### 9.7.1 EMV Static Data Authentication, Issuer Public Key Data (SDA-IPKD)

We refer the reader to §5.1, Table 2, page 41 in EMV [EMV]. SDA-IPKD is used by the CA to sign the issuer's public-key $P_I$. The message to be signed is as follows:

$$m = 02_{16} \| X \| Y \| N_I \| 03_{16}$$

where $X$ represents 6 bytes that can be controlled by the adversary and $Y$ represents 7 bytes that cannot be controlled. $N_I$ is the Issuer's modulus to be certified. More precisely, $X = \text{ID} \| \text{DATE}$ where ID is the issuer identifier (4 bytes) and DATE is the *Certificate Expiration Date* (2 bytes); we assume that both can be controlled by the adversary. $Y = \text{CSN} \| C$ where CSN is the 3-bytes *Certificate Serial Number* assigned by the CA and C is a constant. Finally, the modulus to be certified $N_I$ can also be controlled by the adversary.

Together with ISO/IEC 9796-2 encoding, this gives:

$$\mu(m) = 6A02_{16} \| X \| Y \| N_{1,1} \| H(m) \| BC_{16}$$

where $N_I = N_{1,1} \| N_{1,2} $ and the size of $N_{1,1}$ is $k - k_h - 128$ bits. $k$ denotes the modulus size and $k_h = 160$ as in ISO/IEC 9796-2.

### 9.7.2 Attacking SDA-IPKD

To attack SDA-IPKD write:

$$\mu(X, N_{1,1}, h) = 6A02_{16} \cdot 2^{k_1} + X \cdot 2^{k_2} + Y \cdot 2^{k_3} + N_{1,1} \cdot 2^{k_4} + h$$
where $Y$ is constant and $h = H(m) \| \mathbf{BC}_{16}$. We have:

$$ 
\left\{ 
\begin{array}{l}
k_1 = k - 16 \\
k_2 = k_1 - 48 = k - 64 \\
k_3 = k_2 - 56 = k - 120 \\
k_4 = k_h + 8 = 168.
\end{array}
\right. 
$$

Generate a random $k_a$-bit integer $a$, where $36 \le k_a \le 72$, and consider the equation:

$$ b \cdot N - a \cdot \mu(X, 0, 0) = b \cdot N - a \cdot X \cdot 2^{k_2} - a \cdot (6A02_{16} \cdot 2^{k_1} + Y \cdot 2^{k_3}). $$

If we can find integers $X$ and $b$ such that $0 \le X < 2^{48}$ and:

$$ 0 \le b \cdot N - a \cdot \mu(X, 0, 0) < a \cdot 2^{k_3} \qquad (9.5) $$

then as previously we can compute $N_{I,1}$ by Euclidean division:

$$ b \cdot N - a \cdot \mu(X, 0, 0) = (a \cdot 2^{k_4}) \cdot N_{I,1} + r \qquad (9.6) $$

where $0 \le N_{I,1} < 2^{k_3-k_4}$ as required, and the resulting $b \cdot N - a \cdot \mu(X, N_{I,1}, h)$ value will be small for all values of $h$.

In the above we assumed $Y$ to be a constant. Actually the first 3 bytes of $Y$ encode the CSN assigned by the CA, and may be different for each new certificate (see Appendix 9.C). However if the attacker can predict the CSN, then he can compute a different $a$ for every $Y$ and adapt the attack by factoring $a$ into a product of small primes.

Finding small $X$ and $b$ so as to minimize the value of

$$ |b \cdot N - a \cdot X \cdot 2^{k_2} - a \cdot (6A02_{16} \cdot 2^{k_1} + Y \cdot 2^{k_3})| $$

is a Closest Vector Problem in a bidimensional lattice—a problem that can be easily solved using the LLL algorithm [LLL82]. We first determine heuristically the minimal size that can be expected; we describe the LLL attack in Appendix 9.C.

Since $a \cdot 6A02_{16} \cdot 2^{k_1}$ is an $(k+k_a)$-bit integer, with $X \simeq 2^{48}$ and $b \simeq 2^{k_a}$, we can heuristically hope to find $X$ and $b$ such that:

$$ 0 \le b \cdot N - a \cdot \mu(X, 0, 0) < 2^{(k+k_a)-48-k_a} = 2^{k-48} \simeq a \cdot 2^{k-48-k_a} = a \cdot 2^{k_3+72-k_a} $$

which is $(72 - k_a)$-bit too long compared to condition (9.5). Therefore, by exhaustive search we will need to examine roughly $2^{72-k_a}$ different integers $a$ to find a pair $(b, X)$ that satisfies (9.5); since $a$ is $k_a$-bits long, this can be done only if $72 - k_a \le k_a$, which gives $k_a \ge 36$. For $k_a = 36$ we have to exhaust the $2^{36}$ possible values of $a$.

Once this is done we obtain from (9.6):

$$ t = b \cdot N - a \cdot \mu(X, N_{I,1}, h) = r - a \cdot h $$

with $0 \le r < a \cdot 2^{k_4}$. This implies that the final size of $t$ values is $168 + k_a$ bits. For $k_a = 36$ this gives 204 bits (instead of 170 bits for plain ISO/IEC 9796-2). The cost of the attack will thus be higher than for plain ISO/IEC 9796-2.
<table><caption>Table 9.3: EMV message formats. X denotes a data field controllable by the adversary. Y is not controllable. Data sizes for X, Y and t are expressed in bits.</caption><thead><tr><th>EMV mode</th><th>Format</th><th>|X|</th><th>|Y|</th><th>|t|</th><th>EC2 cost</th></tr></thead><tbody><tr><td>SDA-IPKD</td><td>02<sub>16</sub>||X||Y||N<sub>I</sub>||03<sub>16</sub></td><td>48</td><td>56</td><td>204</td><td>45,000</td></tr><tr><td>SDA-SAD</td><td>Y</td><td>-</td><td>k - 176</td><td>-</td><td>-</td></tr><tr><td>ODDA-IPKD</td><td>02<sub>16</sub>||X||Y||N<sub>I</sub>||03<sub>16</sub></td><td>48</td><td>56</td><td>204</td><td>45,000</td></tr><tr><td>ODDA-ICC-PKD</td><td>04<sub>16</sub>||X||Y||N<sub>ICC</sub>||03<sub>16</sub>||DATA</td><td>96</td><td>56</td><td>204</td><td>45,000</td></tr><tr><td>ODDA-DAD1</td><td>Y</td><td>-</td><td>k - 176</td><td>-</td><td>-</td></tr><tr><td>ODDA-DAD2</td><td>Y</td><td>-</td><td>k - 176</td><td>-</td><td>-</td></tr><tr><td>ICC-PIN</td><td>04<sub>16</sub>||X||Y||N<sub>ICC</sub>||03<sub>16</sub></td><td>96</td><td>56</td><td>204</td><td>45,000</td></tr></tbody></table>

In Appendix 9.C we exhibit concrete $(a, b, X)$ values for $k_a = 52$ and for the RSA-2048 challenge; this required $\approx 2^{23}$ trials (109 minutes on a single PC). We estimate that for $k_a = 36$ this computation will take roughly 13 years on a single PC, or equivalently US$11,000 using the EC2 cloud.

Table 9.2 shows that attacking 204-bit $t_i$'s would cost US$84,000. As for the ISO/IEC 9796-2 attack, we can decrease this cost by first doing exhaustive search on the bits of $H(m)$ to obtain a smaller $t$-value. We found that with 8 bits of exhaustive search cost drops to about US$45,000 (without the matrix step, but in our attack linear algebra takes a relatively small amount of time).

### 9.7.3 Summary

In Appendix 9.D we provide an analysis of the other formats in the EMV specifications, with corresponding attacks when such attacks exist. We summarize results in Table 9.3 where an $X$ represents a string that can be controlled by the adversary, while $Y$ cannot be controlled. The size of the final $t$-value to be smooth is given in bits. Note that cost estimates are cheaper than Table 9.2 because we first perform exhaustive search on 8 bits of $H(m) = SHA-1(m)$; however here we do take into account the cost of computing these SHA-1($m$) values.

Table 9.3 shows that only four of the EMV formats can be attacked, with the same cost as the SDA-IPKD format. The other formats seem out of reach because the non-controllable part $Y$ is too large.

## 9.8 Conclusion

This chapter exhibited a practically exploitable flaw in the ISO/IEC 9796-2 standard and a conceptual flaw in EMV signatures. In response to this attack, the ISO/IEC 9796-2 standard was amended [ISO9796-2:2010] to discourage the use of the ad-hoc signature padding in contexts where chosen-message attacks are an issue.
We can see this cryptanalysis as another indication that it might wise for the industry to move away from ad-hoc constructs from the 1980s and early 1990s, and embrace provable security as the cryptologic community and standardization bodies have done in the past decade.

## 9.A Optimizing Bernstein's Batch Size

We assume that for a single batch the algorithm runs in time:

$$ \text{BatchTime}(n'_{t}, a, \ell) = c \cdot b' \cdot \log^2 b' \cdot \log \log b' $$

where c is a constant and:

$$ b' = n'_{t} \cdot a + u \qquad (9.7) $$

is the bit-length of the batch, and $u = \ell \cdot \log_2 \ell$ is the $p_i$-list's size in bits. The total running time is then:

$$ \text{TotalTime}(n_t, a, \ell, n'_t) = \frac{n_t}{n'_t} \cdot c \cdot b' \cdot \log^2 b' \cdot \log \log b' $$

The running time of a single batch only depends on $b'$. Hence, as a first approximation one could select an $n'_t$ equating the sizes of the $t_i$-list and the $p_i$-list; this yields $n'_t \cdot a = u$. A more accurate analysis (see below) reveals that TotalTime is minimized for a slightly larger $n'_t$ value; more precisely for an $n'_t$ such that:

$$ n'_{t} \cdot a = \frac{u \log u}{2}. $$

Using (9.7) this gives $b' = (u \log u)/2$ and a total running time of:

$$ \text{TotalTime}(n_t, a, \ell) \approx c \cdot n_t \cdot a \cdot \log^2 b' \cdot \log \log b' $$

We now proceed with the analysis of the optimal $n'_t$. For the sake of clarity we temporarily denote $b'$ by $b$. Let $u = \ell \cdot \log_2 \ell$ and

$$ n'_{t} = \frac{u}{a} \cdot \alpha $$

for some parameter $\alpha$. We look for the optimal $\alpha$. We have $b = u \cdot (\alpha + 1)$ and:

$$ \text{TotalTime}(n_t, a, \ell, \alpha) = \frac{n_t \cdot a}{u \cdot \alpha} \cdot c \cdot b \cdot \log^2 b \cdot \log \log b. $$

We neglect the $\log \log b$ term and consider the function:

$$ f(u, \alpha) = \frac{b \cdot \log^2 b}{\alpha} \quad \text{where} \quad b = u \cdot (\alpha + 1). $$

Setting:

$$ \frac{\partial f(u, \alpha)}{\partial \alpha} = 0 $$
we get:

$$u \cdot (\log^2 b + 2 \log b) \cdot \alpha - b \log^2 b = 0 \quad \text{i.e.} \quad (\log b + 2) \cdot \alpha = (\alpha + 1) \log b$$

and then $2\alpha = \log b$, which gives:

$$2\alpha = \log u + \log(\alpha + 1).$$

Neglecting the $\log(\alpha + 1)$ term, we finally get $\alpha \approx \log u/2$ as the optimal value of $\alpha$. This translates into running time as:

$$\text{TotalTime}(n_t, a, \ell) \approx c \cdot n_t \cdot a \cdot \log^2 b \log \log b$$

where $b = (u \log u)/2$ and $u = \ell \cdot \log_2 \ell$.

## 9.B Large Prime Variant: Complexity Analysis

In this appendix we provide an accurate analysis of the large prime variant in the context of our attack.

Assume that we check our $t_i$-list for $(B, B_2)$-semi-smoothness (instead of B-smoothness) and detect $\eta$ semi-smooth numbers. Amongst those, we expect to find $\eta\lambda$ numbers that are actually B-smooth, for some $\lambda \in [0, 1]$ that can be expressed in terms of $\rho$ and $\sigma$ functions. If we further assume that the $\eta(1 - \lambda)$ remaining numbers, which are semi-smooth but non-smooth, have their largest prime factors uniformly distributed amongst the $h$ primes between $B$ and $B_2$, we expect to find about $\eta^2(1 - \lambda)^2/(2h)$ “collisions” between them, that is, about $\eta^2(1 - \lambda)^2/(2h)$ pairs of numbers with the same largest prime factor.

Note that:

$$h \approx \frac{B_2}{\log B_2} - B.$$

Let $\ell$ be the number of primes less than $B$. The smooth numbers in the list yield a total of $\eta\lambda$ exponent vectors over the first $\ell$ primes, and each of the collisions between the remaining semi-smooth numbers yields such an additional exponent vector. Since we need (slightly more than) $\ell$ vectors to forge a signature, we should examine enough $t_i$'s to find $\eta$ semi-smooth numbers, where $\eta$ satisfies:

$$\ell = \eta\lambda + \frac{\eta^2(1 - \lambda)^2}{2h}.$$

Solving for $\eta$, we get:

$$\eta = \frac{2\ell}{\lambda + \sqrt{2\ell \cdot (1 - \lambda)^2/h + \lambda^2}}.$$

The probability $\beta$ that a random $a$-bit integer is semi-smooth with respect to $B_2$ and $B \approx \ell \cdot \log \ell$ is:

$$\beta = \sigma \left( \frac{a \log 2}{\log(\ell \log \ell)}, \frac{a \log 2}{\log B_2} \right)$$
<table><caption>Table 9.4: Improvement factors from the large prime variant.</caption><tr><td>a</td><td>128</td><td>144</td><td>160</td><td>176</td><td>192</td></tr><tr><td>Optimal log<sub>2</sub>(ℓ)</td><td>19</td><td>20</td><td>21</td><td>23</td><td>24</td></tr><tr><td>Best ϑ</td><td>1.43</td><td>1.46</td><td>1.49</td><td>1.43</td><td>1.45</td></tr></table>

and if $\alpha$ denotes the probability that a random $a$-bit integer is $B$-smooth, we have:

$$ \lambda = \frac{\alpha}{\beta} = \frac{\rho\left(\frac{a \log 2}{\log(\ell \log \ell)}\right)}{\sigma\left(\frac{a \log 2}{\log(\ell \log \ell)}, \frac{a \log 2}{\log B_2}\right)}. $$

In this large prime variant, we only need to generate $n'_t = \eta/\beta$ numbers to find enough exponent vectors, as opposed to $n_t = \ell/\alpha$ previously. Therefore, the large prime variant improves upon simple smoothness by a factor of roughly:

$$ \vartheta = \frac{n_t}{n'_t} = \frac{\ell/\alpha}{\eta/\beta} = \frac{1}{\lambda} \cdot \frac{\ell}{\eta} = \frac{1}{2} \left[ 1 + \sqrt{1 + \frac{2\ell}{h} \left( \frac{1}{\lambda} - 1 \right)^2} \right] \ge 1. \quad (9.8) $$

$\vartheta$ is always greater than 1, and for the sizes we are interested in, say $100 \le a \le 200$, we find $\vartheta \approx 1.5$ for the best choice of $B$, and $B_2 \gtrsim 7B$.<fnref n="4" /> The reader is referred to Table 9.4 for precise figures.

# 9.C LLL Attack on EMV SDA-IPKD Encoding

## 9.C.1 The LLL attack

Given $a$, $N$ we must minimize the value of:

$$ \left| b \cdot N - a \cdot X \cdot 2^{k_2} - a \cdot (6A02_{16} \cdot 2^{k_1} + Y \cdot 2^{k_3}) \right|. $$

We show how this can be done using LLL. We write:

$$ \begin{aligned} u &= a \cdot 2^{k_2} \\ v &= a \cdot (6A02_{16} \cdot 2^{k_1} + Y \cdot 2^{k_3}) \end{aligned} $$

<footnote n="4">⁴According to formula (9.8), $\vartheta$ increases until $B_2$ reaches $\approx 7B$, and decreases slowly thereafter. This is actually *not* the case: finding a larger $t_i$ population to be semi-smooth can only produce *more* collisions. The decrease suggested by formula (9.8) stems from the assumption that the largest prime factors of the $t_i$'s are uniformly distributed amongst the $h$ primes between $B$ and $B_2$, which is only approximately true. The imprecision grows with $h$ (a larger $B_2$ doesn't spread the largest prime factors more thinly). Choosing a very large $B_2$ is not advisable, however, because it produces considerable extra output (searching for collisions becomes cumbersome) with negligible returns in terms of actual collisions. In the practical attack, we selected $\ell = 2^{20}$ and $B_2 = 2^{27} \approx 9B$.</footnote>
where $N \approx 2^k$, $X \approx 2^{48}$, $a \approx 2^{k_a}$, $u \approx 2^{k-64+k_a}$ and $v \approx 2^{k+k_a}$. Hence we must minimize the absolute value of:

$$t = b \cdot N - x \cdot u - v.$$

Consider the lattice of column vectors:

$$L = \begin{pmatrix} & 2^{k-48} \\ & 2^{k-96} \\ N & -u & -v \end{pmatrix}$$

As seen previously, heuristically, we can obtain $t \approx 2^{k-48}$; therefore the coefficients in $L$ are chosen so as to obtain a short vector of norm $\approx 2^{k-48}$. More precisely, we look for a short column vector $c \in L$ of the form:

$$c = \begin{pmatrix} 2^{k-48} \\ x \cdot 2^{k-96} \\ b \cdot N - u \cdot x - v \end{pmatrix}$$

**Theorem 9.2 (LLL).** Let $L$ be a lattice spanned by $(u_1, \dots, u_\omega)$. The LLL algorithm, given the vectors $(u_1, \dots, u_\omega)$, finds in polynomial time a vector $b_1$ such that:

$$\|b_1\| \le 2^{(\omega-1)/4} \det(L)^{1/\omega}.$$

Therefore, using LLL we can find a short vector of norm:

$$\|b_1\| \le 2 \cdot (\det L)^{1/3} \le 2 \cdot (2^{3k-144})^{1/3} \le 2^{k-47}.$$

Heuristically we hope that $b_1 = c$, which allows solving for the values of $b$ and $X$. The attack is heuristic but it works very well in practice, as shown in the next section.

### 9.C.2 Practical value for EMV SDA-IPKD

Consider again the SDA-IPKD EMV format; we write:

$$\mu(X, N_{1,1}, h) = 6A02_{16} \cdot 2^{k_1} + X \cdot 2^{k_2} + Y \cdot 2^{k_3} + N_{1,1} \cdot 2^{k_4} + h$$

where the constant $Y$ is taken to be:

$$Y = 010203 \ 0101 \ \mathbf{F8} \ 01_{16}.$$

The first 3 bytes correspond to the CSN assigned by the CA (we took `010203_{16}`), `0101_{16}` corresponds to the hash algorithm indicator and to the public-key algorithm indicator. `F8_{16}` = 248 is the issuer public-key length (in bytes) and `01_{16}` is the length of the public exponent ($e=3$).

Taking the RSA-2048 challenge for $N$, we have run the attack (Appendix 9.C.1) for $k_a = 52$ and found the following values after 8,303,995 $\approx 2^{23}$ iterations:

$$a = 4127135343129068 \quad b = 2192055331476458 \quad X = 66766242156276$$
which are such that $0 < X < 2^{48}$ and:

$$0 \le b \cdot N - a \cdot \mu(X, 0, 0) < a \cdot 2^{k_3} \qquad (9.9)$$

as required.

The computation took ≈ 109 minutes on a single 2 GHz PC. Therefore, for $k_a = 36$ we expect that $2^{36}$ trials to yield a triple $\{a, b, X\}$ satisfying condition (9.9) such that $|a| \le 2^{36}$, within a running time of ≈ $109 \cdot 2^{36-20} = 4.3 \cdot 10^8$ minutes = 13 years on a single PC, or equivalently for US$11,000 using the EC2 cloud.

## 9.D EMV Signature Encoding Formats

EMV specifies the following encoding formats, based on the ISO/IEC 9796-2 standard. The new attack applies to modes preceded by the sign ♦ and does not apply to modes preceded by a ◊.

1. ♦ *Static Data Authentication, Issuer Public Key Data.* EMV SDA-IPKD §5.1, Table 2, page 41.

The signing entity is the CA. The signed message is the Issuer's public-key $P_I$.

$$m = 02_{16} \| X \| Y \| N_I \| 03_{16}.$$

While being operationally debatable we assume that $X$ (the concatenation of the *Issuer's Identifier* (4 bytes) and the *Certificate Expiration Date* (2 bytes)) and $N_I$ (the Issuer's modulus to be certified) can be both controlled by the attacker. $Y$ (7 bytes) cannot be controlled by the adversary.

2. ◊ *Static Data Authentication, Static Application Data.* EMV SDA-SAD §5.1, Table 3, page 42.

The signing entity is the Issuer. The signed message is the Issuer's public-key $P_I$. As the first part of the message $m$ is fixed, the attack does not apply.

3. ♦ *Offline Dynamic Data Authentication, Issuer Public-Key Data.* EMV ODDA-IPKD §6.1, Table 10, page 57.

The signing entity is the CA. The signed message is the Issuer's public-key $P_I$. The message format is identical to SDA-IPKD.

4. ♦ *Offline Dynamic Data Authentication, ICC Public-Key Data.* EMV SDA-ICC-PKD §6.1, Table 11, page 58.

The signing entity is the Issuer. The signed message is the Card's public-key $P_I$.

$$m = 04_{16} \| X \| Y \| N_{ICC} \| 03_{16} \| \text{DATA}.$$

While being operationally debatable we assume that $X$ (12 bytes) and $N_{ICC}$ (the Card's modulus to be certified) can be both controlled by the attacker. $Y$ (7 bytes)
cannot be controlled by the adversary. Here DATA is static data to be authenticated, as specified in Section 10.3, Book 3, EMV specifications; DATA can only appear in the non-recoverable part of the message in the ISO/IEC 9796-2 standard.

5. ♦ Offline Dynamic Data Authentication, Dynamic Application Data. EMV ODDA-DAD1 §6.5, Table 15, page 67.

The signing entity is the Card. As the first part of the message m is fixed (BB₁₆ padding), the attack does not apply.

6. ♦ Offline Dynamic Data Authentication, Dynamic Application Data. EMV ODDA-DAD2 §6.6, Table 18, page 73.

The signing entity is the Card. As the first part of the message m is fixed<fnref n="5" />, the attack does not apply.

7. ♦ Personal Identification Number Encipherment, ICC PIN Encipherment Public Key Data. EMV ICC PIN §7.1, Table 23, page 83.

The signing entity is the Issuer.

$$m = 04_{16} \| X \| Y \| N_{\text{ICC}} \| 03_{16}.$$

While being operationally debatable we assume that X (12 bytes) and N<sub>ICC</sub> (the Card's modulus to be certified) can be both controlled by the attacker. Y (7 bytes) cannot be controlled by the adversary.

*Commercial impact.* It is very fortunate that ODDA-DAD1 and ODDA-DAD2 do not lend themselves to the new attack. Indeed, in the ODDA-DAD modes the signing device is the payment card, which is supposedly in the opponent's hands. In addition, the signing capacity of EMV cards is limited by a ratification counter restricting the number of signatures performed by the card during its lifetime.

## 9.E Fewer Queries

The number of signatures *actually used* by the forger is not τ but the number of nonzero βᵢ values in the formula:

$$\mu(m_{\tau}) = \left( \prod_{j=1}^{\ell} p_j^{\gamma_j} \right)^e \cdot \prod_{i=1}^{\tau-1} \mu(m_i)^{\beta_i}.$$

Assuming that (β₁, ..., βτ−₁) is a random vector of Zτ−₁e only τ(e − 1)/e of the signatures will be actually used to compute the forgery. The gain is significant when

<footnote n="5">⁵Here m = 0501₁₆||Y||X where Y is a 32 + 1 = 33 bytes string that cannot be controlled by the adversary (32 leftmost bytes of ICC Dynamic Data). X can be controlled by the adversary.</footnote>
$e$ is a very small exponent (e.g. 2 or 3). However, one can try to generate more than $\tau$ candidates but select the subset of signatures minimizing the number of nonzero $\beta_i$ values. Such a sparse $\beta$-vector may allow to reduce the number of queries and defeat ratification counters meant to restrict the number of authorized signature queries.

In essence, we are looking at a random [$\ell, k$] code: a kernel vector has $\ell$ components which, for $e = 2$, can be regarded as a set of independent unbiased Bernoulli variables. The probability that such a vector has weight less than $w = \sum_{i=1}^{\tau-1} \beta_i$ is thus:

$$ \sum_{j=1}^{w} \binom{\ell}{j} 2^{-\ell} \approx \frac{1}{2} \left( 1 + \operatorname{erf} \left( \frac{w - \ell/2}{\sqrt{\ell/2}} \right) \right). $$

We have $2^k$ such vectors in the kernel, hence the probability that at least one of them has a Hamming weight smaller than $w$ is surely bounded from above by:

$$ 2^k \times \frac{1}{2} \left( 1 + \operatorname{erf} \left( \frac{w - \ell/2}{\sqrt{\ell/2}} \right) \right) = 2^{k-1} \left( 1 + \operatorname{erf} \left( \frac{w - \ell/2}{\sqrt{\ell/2}} \right) \right). $$

Let $c$ denote the density bias of $w$, i.e. $w = (1/2 - c)\ell$. The previous bound becomes:

$$ \begin{aligned} p(c) &= 2^{k-1} \left(1 + \operatorname{erf}\left(-c\sqrt{2\ell}\right)\right) = 2^{k-1} \left(1 - \operatorname{erf}\left(c\sqrt{2\ell}\right)\right) \\ &= 2^{k-1} \operatorname{erfc}\left(c\sqrt{2\ell}\right) \underset{\ell \to +\infty}{\sim} \frac{2^{k-1} \exp\left(-2\ell c^2\right)}{c\sqrt{2\pi\ell}}. \end{aligned} $$

For $\ell = 2^{20}$, even if we take $k$ as large as $2^{10}$ (the largest subspace dimension considered tractable, even in much smaller ambient spaces), we get $p(1/50) \approx 10^{-58}$, so the probability that there exists a kernel vector of weight $w < 500,000$ is negligible. In addition, even if such a vector existed, techniques for actually computing it, e.g. [BLP08], seem to lag far behind the dimensions we deal with.

It follows that a better strategy to diminish $w$ is to simply decrease $\ell$. The expected payoff might not be that bad: If the attacker is limited to, say, $2^{16}$ signatures, then he can pick $\ell = 2^{17}$, and for 196-bit numbers (204 bits minus 8 bits given by exhaustive search), the attack becomes about 15 times slower than the optimal choice, $\ell = 2^{24}$ (note as well that more exhaustive search becomes possible in that case). That's slow, but perhaps not excruciatingly so.

## 9.F Expected Number of Queries

A further question that arises when studying the problem of minimizing the number of signature queries in the attack is that of evaluating the expected Hamming weight of the nullspace vectors returned by the linear algebra step, with or without the large prime variant. The problem is nontrivial and still open. For simplicity we only consider the GF(2) case ($e = 2$) the following, but the problem is not fundamentally different for other exponents.
<figure><img src="image_19.png" /><figcaption>Figure 9.2: Distribution of row weights for a smooth matrix of size 2<sup>16</sup>. Linear scale (left) and log-log scale (right).</figcaption></figure>

Some primes can never appear as components of nullspace vectors. That is the case, in particular, when the corresponding row of the matrix contains only one nonzero element (i.e. if the prime divides only one of our smooth or semismooth numbers to an odd power): indeed, the column containing that nonzero element is clearly linearly independent from all other columns. Hence, we may as well remove that row and column from the matrix, and do so for every similar pair of rows and columns.

Additional rows of weight 1 may turn up after those removals, so we need to repeat the process recursively. A fix-point is reached (i.e. the algorithm stops) when there is no singleton row left in the reduced matrix.

Let $\ell_0$ denote the total number of rows in this reduced matrix. It seems reasonable to conjecture that (in the case of a square matrix at least) the expected weight of nullspace vectors is of the order of $\ell_0/2$. In other words, the primes that can appear as components of nullspace vectors are likely to do so randomly. The question then reduces to evaluating $\ell_0$.

All this prompts us to estimate how many rows in the original matrix contain exactly one nonzero entry, or more generally exactly $n$ nonzero entries for small $n$. We expected this variable to follow a Poisson distribution, or perhaps a sum of Poisson distributions, but experiments appear to challenge this expectation: the empirical distribution does not have exponential decay but a fat tail, as evidenced by the plots in Figures 9.2 and 9.3. Finding a simple description of this distribution seems like a rather difficult open problem in itself.
<figure><img src="image_20.png" /><figcaption>Figure 9.3: Distribution of row weights (log-log scale) for a smooth matrix of size $2^{16}$ and the first four iterations of the reduction step applied to it. Lighter curves correspond to further iterations.</figcaption></figure>
<figure><img src="image_21.png" /></figure>
# Fault Attacks on EMV Signatures

## 10.1 Introduction

In this chapter, we continue our investigation of the vulnerabilities of the ISO/IEC 9796-2 and EMV signature standards from a different angle. Whereas in Chapter 9 we were interested in constructing signature forgeries in the “black-box” chosen-ciphertext attack model, we now turn to fault attacks: in this threat model, the adversary can tamper with a physical signing device and try to introduce errors during signature generation, by hardware attacks such as voltage spikes in the power source or laser beams targeted at memory chips.

Fault attacks were introduced by Boneh, DeMillo and Lipton [BDL01] in 1997. They showed that RSA signatures, in particular, and especially when used with the Chinese Remainder Theorem as is almost always the case in practice, were quite vulnerable to this type of attack. In fact, a single faulty signature produced by an unprotected device is enough to reveal the private signing key. Since then, fault attacks on RSA signatures and countermeasures against them have been an active research topic.

Boneh et al.'s attack, however, is not directly applicable to ISO/IEC 9796-2 and EMV signatures, because some of the information used to compute the signature is unknown to the adversary (either because it is randomly chosen at the time of signature generation, or because it is not transmitted along with the signature but recovered when verifying the—correct!—signature).

At CHES 2009, Coron, Joux, Kizhvatov, Naccache and Paillier [CJK+09] showed how the attack could still be adapted if the unknown message parts were small enough, by retrieving the small unknown bit strings as small roots of a multivariate polynomial, using variants of the lattice-based technique introduced by Coppersmith [Cop97]. The size restriction on unknown message parts with their technique was quite severe, however, making their attack difficult to apply in practice.

In this chapter, we present a different strategy for recovering the unknown message parts when several faulty signatures are available, also based on lattice reduction but in a simpler way, and that can handle much longer unknown bit strings very efficiently.
We show for example how ten faulty signatures in a specific EMV signature format are enough to retrieve the private signing key with our new attack, while the same format was well beyond the reach of the previous attack. This work was presented at CT-RSA 2010 [CNT10].

### 10.1.1 Fault attacks on RSA-CRT

As mentioned above, one of the first and best-known examples of a fault attack in cryptography is the one described by Boneh, DeMillo and Lipton [BDL97, BDL01, JLQ99] on RSA-CRT signatures. Let us first recall it succinctly.

To sign a message $m$ with RSA, a signer computes $\sigma = \mu(m)^d \bmod N$, where $N$ is the public modulus, $d$ is the private exponent and $\mu$ is a certain encoding function. Since this computation is time-consuming, it is very common to use the Chinese Remainder Theorem (CRT) to obtain a roughly 4-fold speed-up, by first evaluating:

$$ \sigma_p = \mu(m)^d \bmod p^{p-1} \quad (\text{mod } p) \quad \text{and} \quad \sigma_q = \mu(m)^d \bmod q^{q-1} \quad (\text{mod } q) $$

and then deducing $\sigma$ from $\sigma_p$ and $\sigma_q$ with the CRT.

This method is vulnerable to fault attacks: if an attacker can inject a fault during the computation of $\sigma_q$, the whole computation will produce a faulty signature $\sigma'$ satisfying

$$ \sigma' \equiv \mu(m)^d \pmod{p} \quad \text{and} \quad \sigma' \not\equiv \mu(m)^d \pmod{q} $$

which allows the attacker to factor $N$ by computing

$$ \gcd((\sigma')^e - \mu(m) \bmod N, N) = p. $$

Clearly, Boneh et al.'s fault attack applies to any deterministic RSA encoding $\mu$, such as the Full Domain Hash [BR96], where $\mu$ is a full-length hash function, or certain add-hoc signature paddings such as PKCS#1 v1.5 [PKCS#1 v1.5]. The attack is also applicable to probabilistic signature schemes where the random nonce used to generate the signature is sent along with the signature, like PFDH [Cor02].

However, if the nonce is only recovered when verifying the signature, or if some part of the message is unknown, the attack does not apply directly. For example, with a probabilistic encoding of the form $\mu(m) = m \parallel r$ where a random nonce $r$ is simply concatenated with the message $m$, the nonce $r$ is only recovered when verifying a correct signature. Given a faulty signature $\sigma'$, the attacker cannot retrieve $r$ nor infer $(m \parallel r)$ which would be necessary to compute $\gcd((\sigma')^e - \mu(m) \bmod N, N) = p$. It is not advisable to use this particular toy encoding (for example, one can clearly forge signatures if $r$ is allowed to be as large as $N^{1-1/e}$), but more serious probabilistic encodings in which the randomness is recovered as part of signature verification, such as PSS [BR96], are similarly immune to Boneh et al.'s attack.

### 10.1.2 The attack of Coron et al.

At CHES 2009, Coron, Joux, Kizhvatov, Naccache and Paillier [CJK+09] showed how, for certain padding schemes, the case of unknown nonces or partially unknown messages
can be tackled nonetheless if the unknown part is not too large. The attack uses a technique by Herrmann and May [HM08] for finding small roots of linear equations modulo an unknown factor $p$ of a public modulus $N$. This technique is in turn based on Coppersmith's lattice-based method for finding small roots of polynomials [Cop97].

The main application considered by Coron et al. was RSA signatures using the ISO/IEC 9796-2 standard padding scheme [ISO9796-2:2002], where the message is partially unknown, a common situation in smart card applications, especially EMV smart cards [EMV]. The ISO/IEC 9796-2 encoding function is of the form:

$$ \mu(m) = 6A_{16} \| m[1] \| H(m) \| BC_{16} $$

where $m = m[1] \| m[2]$ is split in two parts, and $H$ is a hash function, typically SHA-1. Only $m[2]$ is transmitted together with the signature $\sigma = \mu(m)^d \mod N$. To recover the whole message and verify the signature, the recipient first computes $\mu(m) = \sigma^e \mod N$, from which he deduces $m[1]$, and then checks that the hash value $H(m)$ is correct.

In the cases considered in [CJK+09], the message prefix $m[1]$ is partially known to a fault attacker (because messages are formatted in a particular way, as is common in applications) but some variable part is unknown, and the hash value $H(m)$ is unknown as well as a result. Yet, if the unknown part of $m[1]$ is not too large (up to about 160 bits for a 2048-bit modulus), then, like in Boneh et al.'s attack, the private key can be recovered with a single fault.

In addition, the same paper presents an extension of this attack to the case when multiple faults are available, which makes it theoretically possible to deal with larger unknown message parts. However, this variant involves lattice reduction in dimensions exponential in the number of faults (using heuristic, multivariate versions of Coppersmith's method), and becomes quickly impractical.

### 10.1.3 Our contribution

In this chapter, we present another multiple fault attack in the same setting eschewing Coppersmith-like techniques entirely. It is based on orthogonal lattices, as used in earlier cryptanalytic results such as [NS97, NS98]. The lattice sizes involved are moderate and make the attack quite practical for relatively large unknown message parts.

We implement a simulation of the attack and show it to scale gracefully with the number of available faulty signatures. Unknown message parts very close to the theoretical maximum of half of the modulus length can be recovered in seconds.

We also show that the attack applies to a number of EMV signature formats. For a particular EMV use case well beyond the reach of the attack in [CJK+09], 10 faulty signatures are sufficient with our technique to recover the private key in a fraction of a second.

### 10.1.4 Outline

In preparation for the orthogonal lattice techniques used in this and the next chapter, we start by collecting a few results about integer lattices and lattice reduction (§10.2).
We then recall the definition of the ISO/IEC 9796-2 padding function and describe the structure of CRT faults on ISO/IEC 9796-2 signatures (§10.3). Based on this structure, we explain the idea of Coron et al.’s Coppersmith-based attack as well as its limitations (§10.4). Then, we describe our new multiple-fault attack (§10.5) and provide some simulation results to assess its practicality and compare it to the previous attack (§10.6). We show that our new attack does apply to EMV signatures (§10.7) and finally suggest some possible countermeasures (§10.8).

## 10.2 Preliminaries on Lattices

We start with some preliminary definitions and results about lattices. A similar presentation with a larger scope and more details can be found in [Ngu09, §6].

### 10.2.1 Notation and background

We will consider $\mathbb{R}^n$ endowed with its usual structure as an Euclidean vector space. Bold letters will denote vectors, usually in row notation. If $\mathbf{x} = (x_1, \dots, x_n)$ and $\mathbf{y} = (y_1, \dots, y_n)$ are two vectors, their Euclidean inner product is denoted by

$$ \langle \mathbf{x}, \mathbf{y} \rangle = \sum_{i=1}^{n} x_i y_i . $$

The corresponding Euclidean norm is denoted by

$$ \| \mathbf{x} \| = \sqrt{\langle \mathbf{x}, \mathbf{x} \rangle} = \sqrt{x_1^2 + \cdots + x_n^2} . $$

For any subset $S$ of $\mathbb{R}^n$, we define the linear span of $S$, denoted by $\text{span}(S)$, as the minimal vector subspace of $\mathbb{R}^n$ containing $S$.

The Gram determinant of $\mathbf{b}_1, \dots, \mathbf{b}_m \in \mathbb{R}^n$, denoted by $\Delta(\mathbf{b}_1, \dots, \mathbf{b}_m)$, is by definition the determinant of the Gram matrix $(\langle \mathbf{b}_i, \mathbf{b}_j \rangle)_{1 \le i,j \le m}$. This real number $\Delta(\mathbf{b}_1, \dots, \mathbf{b}_m)$ is always $\ge 0$, and it turns out to be zero if and only if the $\mathbf{b}_i$'s are linearly dependent. The Gram determinant is invariant by any permutation of the $m$ vectors, and by any integral linear transformation of determinant $\pm 1$ such as adding to one of the vectors a linear combination of the others. The Gram determinant has a very useful geometric interpretation: when the $\mathbf{b}_i$'s are linearly independent, $\sqrt{\Delta(\mathbf{b}_1, \dots, \mathbf{b}_m)}$ is the $m$-dimensional volume of the parallelepiped spanned by the $\mathbf{b}_i$'s.

### 10.2.2 Lattices and lattice bases

For our purposes, a *lattice* will be any subgroup $L$ of $(\mathbb{Z}^n, +)$ for some $n$ (such a subgroup is sometimes called an *integral lattice*, to distinguish it from more general definitions of a lattice). Examples include $\mathbb{Z}^n$ itself, the zero lattice $\{0\}$, and the set $a\mathbb{Z} + b\mathbb{Z}$ of linear combinations of any two integers $a, b \in \mathbb{Z}$ (which is simply $\text{gcd}(a, b)\mathbb{Z}$). For another example, consider $n$ integers $a_1, \dots, a_n$, together with a modulus $M$. Then the set of
all $(x_1, \dots, x_n) \in \mathbb{Z}^n$ such that $\sum_{i=1}^n a_i x_i \equiv 0 \pmod{M}$ is a lattice, as it is clearly a subgroup of $\mathbb{Z}^n$.

Let $\mathbf{b}_1, \dots, \mathbf{b}_m$ be arbitrary vectors in $\mathbb{Z}^n$. Denote by $L(\mathbf{b}_1, \dots, \mathbf{b}_m)$ the set of all integral linear combinations of the $\mathbf{b}_i$'s:

$$L(\mathbf{b}_1, \dots, \mathbf{b}_m) = \left\{ \sum_{i=1}^{m} n_i \mathbf{b}_i : n_1, \dots, n_m \in \mathbb{Z} \right\}.$$

This set is a subgroup of $\mathbb{Z}^n$, and hence a lattice $L$, called the lattice generated or spanned by the $\mathbf{b}_i$'s. When the $\mathbf{b}_i$'s are linearly independent, we say that $(\mathbf{b}_1, \dots, \mathbf{b}_m)$ is a basis of the lattice $L$, in which case each lattice vector decomposes itself uniquely as an integral linear combination of the $\mathbf{b}_i$'s.

Bases and sets of generators are useful to represent lattices, and to perform computations. One will typically represent a lattice by some lattice basis, which can itself be represented by a matrix with integer coefficients. If $(\mathbf{b}_1, \dots, \mathbf{b}_m)$ is a basis of $L$, with $\mathbf{b}_i = (b_{i,1}, \dots, b_{i,n})$, we will represent the lattice $L = L(\mathbf{b}_1, \dots, \mathbf{b}_m)$ by the following matrix:

$$\begin{pmatrix} b_{1,1} & \cdots & b_{1,n} \\ \vdots & & \vdots \\ b_{m,1} & \cdots & b_{m,n} \end{pmatrix}$$

whose rows are the coordinates of the $\mathbf{b}_i$'s.

We define the dimension or rank of a lattice $L$, denoted by $\dim(L)$, as the dimension $d$ of the vector space span($L$). The dimension is the maximal number of linearly independent lattice vectors. Any lattice basis of $L$ must have exactly $d$ elements. It is clear that there exist $d$ linearly independent lattice vectors, but such vectors do not necessarily form a basis, contrary to what happens in the case of vectors spaces. However, it is in fact always possible to find a basis of $L$: in other words, lattices of dimension $d$ in $\mathbb{Z}^n$ are exactly all subsets of $\mathbb{Z}^n$ of the form

$$L = L(\mathbf{b}_1, \dots, \mathbf{b}_d)$$

for some linearly independent vectors $\mathbf{b}_1, \dots, \mathbf{b}_d \in \mathbb{Z}^n$.

### 10.2.3 Lattice volume

Let $(\mathbf{b}_1, \dots, \mathbf{b}_d)$ and $(\mathbf{c}_1, \dots, \mathbf{c}_d)$ be two bases of a lattice $L$ in $\mathbb{R}^n$. An elementary result states that there exists a $d \times d$ integral matrix $U = (u_{i,j})_{1 \le i,j \le d} \in M_d(\mathbb{Z})$ of determinant $\pm 1$ such that $\mathbf{c}_i = \sum_{j=1}^d u_{i,j} \mathbf{b}_j$ for all $1 \le i \le d$. It follows that the Gram determinants of those two bases are equal:

$$\Delta(\mathbf{b}_1, \dots, \mathbf{b}_d) = \Delta(\mathbf{c}_1, \dots, \mathbf{c}_d) > 0.$$

The volume of the lattice $L$ is then defined as:

$$\mathrm{vol}(L) = \Delta(\mathbf{b}_1, \dots, \mathbf{b}_d)^{1/2}$$
which is independent of the choice of the lattice basis $(\mathbf{b}_1, \dots, \mathbf{b}_d)$. It corresponds to the $d$-dimensional volume of the parallelepiped spanned by any basis. In the important case of full-dimensional lattices where $\dim(L) = n = \dim(\mathbb{R}^n)$, the volume is also equal to the absolute value of the determinant of any lattice basis.

If an explicit basis is known, computing the lattice volume amounts to computing a determinant. However, in some cases, we may not know any explicit lattice basis; in such a case, the following elementary result may be useful for computing the volume nonetheless. If $L_1$ and $L_2$ are two lattices in $\mathbb{Z}^n$ of the same dimension such that $L_1 \subset L_2$, then $L_2/L_1$ is a finite group of order denoted by $[L_2 : L_1]$ which satisfies

$$ \mathrm{vol}(L_1) = [L_2 : L_1] \cdot \mathrm{vol}(L_2). $$

For example, consider $n$ integers $a_1, \dots, a_n$, together with a modulus $M$. We have seen in §10.2.2 that the set $L$ of all $(x_1, \dots, x_n) \in \mathbb{Z}^n$ such that $\sum_{i=1}^n a_i x_i \equiv 0 \pmod M$ is a lattice in $\mathbb{Z}^n$, but it is not obvious how to explicitly write down a basis of $L$. However, note that $L \subset \mathbb{Z}^n$ and that the dimension of $L$ is $n$ because $L$ contains $MZ^n$. It follows that $\mathrm{vol}(L) = [\mathbb{Z}^n : L]$. Furthermore, the definition of $L$ says that it is the kernel of the group homomorphism $\mathbb{Z}^n \to \mathbb{Z}/MZ$ sending $(x_1, \dots, x_n)$ to $\sum_{i=1}^n a_i x_i$. The image of this morphism is the subgroup generated by $\mathrm{gcd}(M, a_1, a_2, \dots, a_n)$, and hence:

$$ \mathrm{vol}(L) = [\mathbb{Z}^n : L] = \frac{M}{\mathrm{gcd}(M, a_1, a_2, \dots, a_n)}. $$

### 10.2.4 Lattice reduction

As previously noted, any lattice has a basis. In fact, any lattice of dimension 2 or more has infinitely many bases. However, some of these bases are “better” than others, in the sense that they give more compact descriptions of the lattice and make it easier to answer various questions about the lattice.

In the case of Euclidean vector spaces, it is usually convenient to work with orthogonal bases. Lattices, on the other hand, do not always admit orthogonal bases. Nevertheless, it can be shown that one can always find so-called *reduced bases*, consisting of “relatively short” vectors that are “not too far” from being orthogonal.

Giving precise definitions for such notions as “short vectors” and “reduced bases”, showing that such vectors or such bases exist, and describing methods to find them, is the purpose of the theory of lattice reduction.

*Minkowski's successive minima.* In order to explain what a reduced basis is, we need to define what is meant by short lattice vectors. Let $L$ be a lattice of dimension $\ge 1$ in $\mathbb{R}^n$. Since any closed hyperball centered at zero contains finitely many vectors of $L$, there exists a non-zero vector in $L$ of minimal length. The Euclidean norm of that shortest non-zero vector is called the *first minimum* of $L$, and is denoted by $\lambda_1(L) > 0$. Any vector $v$ in $L$ of norm $\lambda_1(L)$ is called a shortest vector of $L$. It is never unique, since $-v$ is also a shortest vector.
For that reason, one must be careful when defining the second-to-shortest vector of a lattice. Minkowski [Min96] defined the other minima as follows. For all $1 \le i \le \dim(L)$, the $i$-th minimum $\lambda_i(L)$ is defined as the minimum of $\max_{1 \le j \le i} ||v_j||$ over all families of $i$ linearly independent lattice vectors $v_1, \dots, v_i \in L$. Clearly, the minima are increasing: $\lambda_1(L) \le \lambda_2(L) \le \dots \le \lambda_d(L)$. And it is not difficult to see that there always exist linearly independent lattice vectors $v_1, \dots, v_d$ reaching simultaneously the minima, that is $||v_i|| = \lambda_i(L)$ for all $i$.

As a side note, perhaps surprisingly, it is not the case in general that such vectors form a basis of $L$. In fact, one can find lattices (of dimension $\ge 5$) in which there is no basis at all formed by vectors of length equal to the successive minima.

**Random lattices.** It is possible to give a relatively precise description of how Minkowski's minima behave “generically”, namely for so-called random lattices. The precise definition of a random lattice is somewhat technical but the idea is that there is a natural way to pick a lattice “uniformly at random” (see e.g. [Ajt02] for details).

It is proved in [Ajt06] that a random lattice of rank $n$ satisfies asymptotically, with overwhelming probability:

$$ \forall 1 \le i \le n, \quad \lambda_i(L) \approx \sqrt{\frac{n}{2\pi e}} \mathrm{vol}(L)^{1/n}. \qquad (10.1) $$

This means that all minima are close to each other and to the radius of an $n$-dimensional ball of volume vol($L$).

Furthermore, [Ajt06] also shows that asymptotically, in a random $n$-rank lattice $L$, there exists with overwhelming probability a lattice basis ($b_1, \dots, b_n$) such that:

$$ \forall 1 \le i \le n, \quad ||b_i|| \approx \sqrt{\frac{n}{2\pi e}} \mathrm{vol}(L)^{1/n}. \qquad (10.2) $$

Such a basis consists of very short vectors, since their norms are close to the successive minima. Thus, random lattices typically have nice bases.

In applications, lattices are often not picked at random in the previous sense but constructed in a particular way. Such non-random lattices can sometimes behave quite differently from random lattices: for example, the first minimum can be arbitrarily small compared to vol($L)^{1/n}$ for lattices constructed in an ad hoc way. However, it is often a reasonable heuristic to infer the “typical” behavior of lattices in a given problem from the case of random lattices, and assume that the previous properties hold most often nonetheless.

**Reduction notions and LLL.** We just mentioned that random lattices always have nice bases: what about general lattices? The goal of lattice reduction is to prove the existence of nice lattice bases in every lattice, and to describe procedures to find such bases. These nice bases are called reduced.

There are multiple definitions of a reduced basis: usually, one first defines a notion of reduction, then shows that there exist bases which are reduced in this sense, and
finally proves that bases which are reduced in this sense have interesting properties, mathematical (how short are the vectors of a reduced basis?) and computational (how easy is it to compute the basis?).

One classical notion of reduction, which will be enough for our purposes, is the Lenstra-Lenstra-Lovász reduction [LLL82] (LLL for short). It isn't very strong (in the sense that vectors of an LLL-reduced basis aren't necessarily very short) but it is computationally inexpensive: we can compute LLL-reduced basis of lattices of relatively large dimension quickly.

We will not need a precise definition of LLL reduction, but the following few properties will come in handy. All lattices admit LLL-reduced bases, and any LLL-reduced basis $(b_1, \dots, b_d)$ of a lattice $L$ satisfies:

$$1. \quad \|b_1\| \le 2^{(d-1)/4}(\mathrm{vol} L)^{1/d}.$$

$$2. \quad \text{For all } 1 \le i \le d, \quad \|b_i\| \le 2^{(d-1)/2}\lambda_i(L).$$

$$3. \quad \|b_1\| \times \dots \times \|b_d\| \le 2^{d(d-1)/4} \mathrm{vol} L.$$

The vectors of an LLL-reduced basis are thus at most exponentially far from the minima.

# 10.3 Modeling Faults on ISO/IEC 9796-2 Signatures

## 10.3.1 The ISO/IEC 9796-2 signature scheme

As discussed in Chapter 9, ISO/IEC 9796-2 is an encoding standard allowing partial message recovery [ISO9796-2, ISO9796-2:2002], and used in many embedded applications, including EMV smart cards [EMV]. The encoding can be used with hash functions $H$ of various digest sizes $k_h$. When $k_h$, the message size and the size of $N$ (denoted $k$) are all multiples of 8, the ISO/IEC 9796-2 encoding of a message $m = m[1] \| m[2]$ is

$$\mu(m) = 6A_{16} \| m[1] \| H(m) \| BC_{16}$$

where $m[1]$ consists of the $k-k_h-16$ leftmost bits of $m$ and $m[2]$ represents the remaining bits of $m$. In [ISO9796-2:2002] it is required that $k_h \ge 160$.

The ISO/IEC 9796-2 encoding itself is deterministic, but it is often used with messages containing parts which are either secret or picked at random upon signature generation. This is particularly the case in EMV smart cards. The message to be signed can be put in the following general form: $m = m[1] \| m[2]$ with

$$m[1] = \alpha \| r \| \alpha' \quad \text{and} \quad m[2] = \text{DATA}$$

where $r$ is an unknown bit string (e.g. a random nonce), $\alpha$ and $\alpha'$ are bit strings known to the attacker, and DATA is a possibly unknown bit string. Thus, the ISO/IEC 9796-2-encoded message is

$$\mu(m) = 6A_{16} \| \alpha \| r \| \alpha' \| H(\alpha \| r \| \alpha' \| \text{DATA}) \| BC_{16}$$
where both $r$ and the hash value are unknown. In typical use cases, the hash value is a 160-bit long SHA-1 digest, and $N$ is an RSA modulus of around 1024 bits. The unknown string $r$ can be of various sizes depending on the nature of the signed message; the shorter $r$ is, the easier the attack becomes.

More generally, we will consider encoded messages of the form:

$$ \mu(m) = A + B \cdot x_0 + C \cdot y_0 $$

where $B$ and $C$ are public constants (in the ISO/IEC 9796-2 case, suitable powers of 2), $A$ is a number representing the known part of the encoding, and $x_0$ and $y_0$ are the unknown parts (equal to $r$ and $H(m)$ respectively). The signature is then computed as $\sigma = \mu(m)^d \bmod N$ as usual, using the CRT.

### 10.3.2 Attack model

A fault is injected in the exponentiation modulo $q$ part of the RSA-CRT signature generation, resulting in a faulty signature $\sigma$ satisfying

$$ \sigma^e \equiv A + B \cdot x_0 + C \cdot y_0 \pmod{p} \quad \text{and} \quad \sigma^e \not\equiv A + B \cdot x_0 + C \cdot y_0 \pmod{q}. $$

Dividing by $B$ and subtracting the left-hand side, the faulty signature yields a relation of the form

$$ a + x_0 + c \cdot y_0 \equiv 0 \pmod{p} \quad \text{and} \quad a + x_0 + c \cdot y_0 \not\equiv 0 \pmod{q} $$

where $a = B^{-1}(A - \sigma^e) \bmod N$ is a value known to the attacker, and $c = B^{-1} \cdot C \bmod N$ is a public constant.

In other words, the fault attack provides the attacker with an integer $a$ such that for a certain unknown pair $(x_0, y_0)$ of bounded size, the following holds:

$$ a + x_0 + c \cdot y_0 \equiv 0 \pmod{p} \quad \text{and} \quad a + x_0 + c \cdot y_0 \not\equiv 0 \pmod{q}. $$

We will write the bounds on $x_0$ and $y_0$ as $0 \le x_0 < N^\gamma$ and $0 \le y_0 < N^\delta$. The total fraction of unknown bits in the encoded message is thus $\gamma + \delta$.

Intuitively, in both Coron et al.'s attack and our new attack, the adversary takes advantage of the affine relation in $x_0$ and $y_0 \bmod p$ to recover the unknown part with lattice techniques, and use it to factor $N$.

In practice, the fault can be injected using e.g. voltage spikes during the computation modulo $q$ (see [CJK$^{+}$09, §4]).

The resulting value modulo $q$ (of the faulty signature, or equivalently of $a + x + cy$) is usually modeled as a random element in $\mathbb{Z}_q$: this is the random fault model.

## 10.4 The Small Root Attack

We now describe the previous attack by Coron et al. [CJK$^{+}$09] in the single-fault case, and show how it extends to multiple faults (albeit with poor efficiency).
### 10.4.1 Single-fault attack

After a single fault, the attacker obtains a bivariate linear polynomial $f(x, y) = a+x+c \cdot y$ such that $f(x_0, y_0) \equiv 0 \pmod{p}$ and $f(x_0, y_0) \not\equiv 0 \pmod{q}$ for some unknown pair $(x_0, y_0)$ satisfying known bounds. They can then apply the following Coppersmith-like result by Herrmann and May.

**Theorem 10.1 (Herrmann-May [HM08]).** Let $N$ be a sufficiently large composite integer with a divisor $p \ge N^\beta$. Let $f \in \mathbb{Z}[x, y]$ be a bivariate linear polynomial. Assume that $f(x_0, y_0) = 0 \pmod{p}$ for some $(x_0, y_0)$ such that $|x_0| \le N^\gamma$ and $|y_0| \le N^\delta$. Then for any $\varepsilon > 0$, under the condition

$$ \gamma + \delta \le 3\beta - 2 + 2(1 - \beta)^{3/2} - \varepsilon \qquad (10.3) $$

one can find linearly independent polynomials $h_1, h_2 \in \mathbb{Z}[x, y]$ such that $h_1(x_0, y_0) = h_2(x_0, y_0) = 0$ over $\mathbb{Z}$, in time polynomial in $\log N$ and $\varepsilon^{-1}$.

In our case, $N$ is a (presumably balanced) RSA modulus, so $\beta = 1/2$ and condition (10.3) becomes:

$$ \gamma + \delta < \frac{\sqrt{2} - 1}{2} \approx 0.207. \qquad (10.4) $$

Under that condition, we obtain two linearly independent polynomials $h_1, h_2 \in \mathbb{Z}[x, y]$ such that $(x_0, y_0)$ is a root of both.

Suppose further that $h_1, h_2$ are in fact algebraically independent. It is then easy to compute the finite list of their common roots, e.g. by taking the resultant with respect to $y$ and solving for $x$, and thus to find $(x_0, y_0)$. Once $(x_0, y_0)$ is computed, one can proceed as in Boneh et al.'s attack to factor $N$:

$$ \gcd(f(x_0, y_0) \pmod{N}, N) = p. $$

The algebraic independence assumption makes the attack heuristic, but the experimental validation carried out in [CJK+09] suggests that it works well for $\gamma + \delta$ not too large. For example, with a 2048-bit modulus and 160-bit hash function, a 158-bit long nonce $r$ is recovered in less than a minute with a single fault. The total fraction of unknown message bits is then $\gamma + \delta = (158 + 160)/2048 \approx 0.155$.

However, condition (10.4) is quite restrictive, especially when $N$ is small. Indeed, for a 1024-bit modulus with 160-bit hash function, the theoretical maximum nonce size that can be recovered is 58 bits, and the algorithm is only manageable in practice for much smaller sizes. As a result, the attack performs worse than exhaustive search for $r$ for this modulus size.

### 10.4.2 Extension to several faults

To tackle larger unknown message parts, Coron et al. suggest [CJK+09, §2.4] taking advantage of $\ell > 1$ faulty signatures obtained with the same signing key. This gives a
family of $\ell$ linear polynomials $f_i(x, y) = a_i + x + c \cdot y$ each of which has a small root $(x_i, y_i)$ modulo $p$.

Using independent variables for all of these polynomials and multiplying powers of them together, they get a large number of polynomials in $2\ell$ variables, each of which has the small root $(x_1, y_1, \dots, x_\ell, y_\ell)$ modulo $p$. If the small root is small enough, it is then possible to construct a lattice from those multivariate polynomials such that lattice reduction yields $2\ell$ linearly independent polynomials with the same small root $(x_1, y_1, \dots, x_\ell, y_\ell)$ over the integers. If those polynomials happen to be algebraically independent, this reveals the unknown message parts $x_i, y_i$ and we can factor $N$ as before.

The algebraic independence condition in this case is a real hurdle, but more importantly, the dimension of the lattice constructed in that way quickly becomes very large. Theoretically, given a sufficiently large number of faults, the extended attack could tackle cases where $\gamma + \delta$ is asymptotically close to $1/2$. However, since the lattice dimension grows exponentially with the number $\ell$ of faulty signatures, achieving $\gamma + \delta$ values significantly higher than the single-fault maximum of 0.207 is quite impractical. Table 10.2 illustrates how intractable the problem gets as $\gamma + \delta$ approaches 1/2. As a result, this approach doesn't extend the scope of the single-fault attack by a large margin.

## 10.5 Our New Multiple-Fault Attack

We now describe our new multiple-fault attack, which uses lattices in a very different way. We are now given $\ell$ faulty signatures, and in particular a vector $\mathbf{a} = (a_1, \dots, a_\ell)$ of integers such that, for two short unknown vectors $\mathbf{x} = (x_1, \dots, x_\ell)$, $\mathbf{y} = (y_1, \dots, y_\ell)$, we have:

$$ \mathbf{a} + \mathbf{x} + c \cdot \mathbf{y} \equiv \mathbf{0} \pmod{p}. \qquad (10.5) $$

The attack then proceeds in three steps.

**Linearization.** The first step is to eliminate $\mathbf{a}$ in (10.5) to obtain a linear, rather than affine, relation. To do so, we try to find vectors $\mathbf{u}_j$ orthogonal to $\mathbf{a}$ modulo $N$, and take the inner products of (10.5) with the $\mathbf{u}_j$'s.

The set $L_a = \{\mathbf{u} \in \mathbb{Z}^\ell \mid \langle \mathbf{a}, \mathbf{u} \rangle \equiv 0 \pmod{N}\}$ of vectors $\mathbf{u}$ orthogonal to $\mathbf{a}$ modulo $N$ is a lattice in $\mathbb{Z}^\ell$ of rank $\ell$ and volume $N$, as seen in §10.2.3. It is possible to find a reduced basis of it by standard orthogonal lattice techniques [NS97] as follows. Denote by $L_a^{(0)}$ the lattice in $\mathbb{Z}^{\ell+1}$ generated by the rows of the matrix

$$ \begin{pmatrix} \kappa N & 0 & \cdots & 0 \\ \kappa a_1 & 1 & & 0 \\ \vdots & & \ddots & \vdots \\ \kappa a_\ell & 0 & & 1 \end{pmatrix} \qquad (10.6) $$

where $\kappa$ is a large scaling constant. Now for any vector $\mathbf{u}^{(0)} = (u_0, u_1, \dots, u_\ell)$ in this lattice, one has $u_0 = \kappa(a_1 u_1 + \cdots + a_\ell u_\ell + mN)$ for some integer $m$. In particular, if
$|u_0| < \kappa$, then $u_0 = 0$, and $\mathbf{u} = (u_1, \dots, u_\ell)$ must satisfy $\langle \mathbf{a}, \mathbf{u} \rangle \equiv 0 \pmod{N}$. Thus, any vector $\mathbf{u}^{(0)}$ in $L_a^{(0)}$ whose norm is less than $\kappa$ gives rise to a vector $\mathbf{u} \in L_a$. Conversely, if $\mathbf{u}$ is a point in $L_a$, then $\mathbf{u}^{(0)} = (0, u_1, \dots, u_\ell)$ is in $L_a^{(0)}$.

Since it admits $N\mathbb{Z}^\ell$ as a sublattice, the lattice $L_a$ in $\mathbb{Z}^\ell$ contains a linearly independent family consisting of $\ell$ vectors of length at most $N$. Taking the corresponding vectors in $L_a^{(0)}$, this implies that $\lambda_j(L_a^{(0)}) \le N$ for $1 \le j \le \ell$.

Consider then an LLL-reduced basis $(\mathbf{u}_1^{(0)}, \dots, \mathbf{u}_{\ell+1}^{(0)})$ of $L_a^{(0)}$. Recall from §10.2.4 that a property of LLL reduction is that for $1 \le j \le \ell$,

$$ \|\mathbf{u}_j^{(0)}\| \le 2^{\ell/2} \lambda_j(L_a^{(0)}) \le 2^{\ell/2} N. $$

Hence, if one chooses $\kappa$ large enough, all vectors $\mathbf{u}_j^{(0)}$, $1 \le j \le \ell$, are of norm less than $\kappa$ and give rise to independent vectors $\mathbf{u}_j$ that are orthogonal to $\mathbf{a}$ modulo $N$ (it is in fact an LLL-reduced basis of the lattice of such orthogonal vectors). In particular, taking the inner product of (10.5) with $\mathbf{u}_j$, we get, for $1 \le j \le \ell$,

$$ \langle \mathbf{x}, \mathbf{u}_j \rangle + c \langle \mathbf{y}, \mathbf{u}_j \rangle \equiv 0 \pmod{p}. \quad (10.7) $$

Moreover, we can give a heuristic estimate the size of the vectors $\mathbf{u}_j$. Assuming that $L_a$ behaves like a random lattice, the length of these vectors should be around $\sqrt{\ell/2\pi e} \cdot N^{1/\ell}$ since vol($L_a$) = $N$. Neglecting the small multiplicative factor, we can heuristically expect that $\|\mathbf{u}_j\| \lesssim N^{1/\ell}$.

**Orthogonalization.** For all $j$, let $\alpha_j = \langle \mathbf{x}, \mathbf{u}_j \rangle$ and $\beta_j = \langle \mathbf{y}, \mathbf{u}_j \rangle$. We expect to have, for all $j$ except the last few, $|\alpha_j| \lesssim N^{\gamma+1/\ell}$ and $|\beta_j| \lesssim N^{\delta+1/\ell}$. Now recall from (10.7) that

$$ \alpha_j + c \cdot \beta_j \equiv 0 \pmod{p}. $$

If $(\alpha_j, \beta_j) \ne (0, 0)$, this amounts to writing $-c$ as the modular ratio $\alpha_j/\beta_j \pmod{p}$. But this is only possible in general if the sum of sizes of $\alpha_j$ and $\beta_j$ is at least the size of $p$. In other words, if $N^{\gamma+1/\ell} \cdot N^{\delta+1/\ell} \ll p$, that is

$$ \gamma + \delta + \frac{2}{\ell} \le \frac{1}{2} \quad (10.8) $$

we should have $\alpha_j = \beta_j = 0$ for all $j$ except perhaps the last few. This means that $\mathbf{u}_j$ is orthogonal to $\mathbf{x}$ and $\mathbf{y}$ in $\mathbb{Z}^\ell$.

Assume that this does in fact hold for $1 \le j \le \ell - 2$, and consider the lattice of vectors in $\mathbb{Z}^\ell$ orthogonal to $\mathbf{u}_j$ for $1 \le j \le \ell - 2$. This is a bidimensional lattice containing $\mathbf{x}$ and $\mathbf{y}$, and we can find a basis $(\mathbf{x}', \mathbf{y}')$ of it with LLL. This is done by computing the LLL-reduction of the following lattice in $\mathbb{Z}^{\ell-2+\ell}$ generated by the rows of

$$ \begin{pmatrix} \kappa' u_{1,1} & \cdots & \kappa' u_{\ell-2,1} & 1 & 0 \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \kappa' u_{1,\ell} & \cdots & \kappa' u_{\ell-2,\ell} & 0 & 1 \end{pmatrix} $$

where $\kappa'$ is a suitably large constant [NS97].
**Factoring.** Finally, using LLL again as in the linearization step, we can construct a short vector $v$ orthogonal to both $x'$ and $y'$ modulo $N$. Then $v$ is also orthogonal mod $N$ to all $\mathbb{Z}$-linear combinations of $x'$ and $y'$, in particular $x$ and $y$. Therefore, taking the inner product of (10.5) with $v$, we get

$$ \langle a, v \rangle \equiv 0 \pmod{p} $$

and we can thus factor $N$ as required:

$$ \gcd(\langle a, v \rangle, N) = p. $$

**Summary.** If condition (10.8) is satisfied, the following algorithm should heuristically find a nontrivial factor of $N$:

1. Find an LLL-reduced basis $(u_1, \dots, u_\ell)$ of the lattice of vectors in $\mathbb{Z}^\ell$ orthogonal to $a$ modulo $N$.

2. Find a basis $(x', y')$ of the lattice of vectors in $\mathbb{Z}^\ell$ orthogonal to $u_j$, $1 \le j \le \ell - 2$.

3. Find a short vector $v$ orthogonal to $x'$ and $y'$ modulo $N$ (for example the first vector of an LLL-reduced basis of the lattice formed by such orthogonal vectors).

4. Return $\gcd(\langle a, v \rangle, N)$.

The attack is heuristic because it might be the case that $u_j$ isn't actually orthogonal to $x$ and $y$ in $\mathbb{Z}^\ell$ for all $j \le \ell - 2$.

Experimentally, however, success rates are very high when condition (10.8) is verified, as we show in the next section.

## 10.6 Simulation Results

We simulate our new fault attack as follows: we first generate a correct $\sigma_p = \mu(m)^d$ mod $p$ and a random $\sigma_q \in \mathbb{Z}_q$ and then compute the faulty signature $\sigma$ using the Chinese Remainder Theorem. This mimics the process described in [CJK$^+$09] where concrete faults are injected into devices generating ISO/IEC 9796-2 signatures. We then feed the resulting faulty signatures into the algorithm described above and check whether it successfully factors the signing key.

We first collect results on the success rate of the attack $\gamma + \delta = 0.33$. Condition (10.8) predicts that the number of faulty signatures should satisfy $\ell \gtrsim 12$, and we do in fact find a success rate of 100% for $\ell = 13$ or 14, both for balanced and unbalanced $(\gamma, \delta)$ configurations, as shown in Table 10.1.

We then assess the practicality and efficiency of our attack for various unknown message part lengths $\gamma + \delta$, and compare it to the attack by Coron et al. [CJK$^+$09]. The results are presented in Table 10.2, which provides, for several values of $\gamma + \delta$, the following information: the number of faulty signatures $\ell_{new}$ used in our simulation, the
<table><caption>Table 10.1: Attack simulation results using SAGE. Random 1024-bit moduli. Single 2.5 GHz Intel CPU core.</caption><thead><tr><th>Number of faults <i>l</i></th><th>12</th><th>13</th><th>14</th></tr></thead><tbody><tr><td>Success rate with <i>γ</i> = <i>δ</i> = <sup>1</sup>&frasl;<sub>6</sub></td><td>13%</td><td>100%</td><td>100%</td></tr><tr><td>Success rate with <i>γ</i> = <sup>1</sup>&frasl;<sub>4</sub>, <i>δ</i> = <sup>1</sup>&frasl;<sub>12</sub></td><td>0%</td><td>100%</td><td>100%</td></tr><tr><td>Average CPU time (seconds)</td><td>0.19</td><td>0.14</td><td>0.17</td></tr></tbody></table>

<table><caption>Table 10.2: Comparison of the new attack with [CJK$^{+}$09] for a random 1024-bit modulus.</caption><thead><tr><th>γ + δ</th><th>l<sub>new</sub></th><th>ω<sub>new</sub></th><th>CPU time (new)</th><th>l<sub>old</sub></th><th>ω<sub>old</sub></th><th>CPU time (old)</th></tr></thead><tbody><tr><td>0.204</td><td>7</td><td>8</td><td>0.03 s</td><td>3</td><td>84</td><td>49 s</td></tr><tr><td>0.214</td><td>8</td><td>9</td><td>0.04 s</td><td>2</td><td>126</td><td>22 min</td></tr><tr><td>0.230</td><td>8</td><td>9</td><td>0.04 s</td><td>2</td><td>462</td><td>—</td></tr><tr><td>0.280</td><td>10</td><td>11</td><td>0.07 s</td><td>6</td><td>6188</td><td>—</td></tr><tr><td>0.330</td><td>14</td><td>15</td><td>0.17 s</td><td>8</td><td>2<sup>21</sup></td><td>—</td></tr><tr><td>0.400</td><td>25</td><td>26</td><td>1.44 s</td><td>—</td><td>—</td><td>—</td></tr><tr><td>0.450</td><td>70</td><td>71</td><td>36.94 s</td><td>—</td><td>—</td><td>—</td></tr></tbody></table>

corresponding lattice dimension $\omega_{new}$, and the running time of the new attack, as well as the corresponding values $\ell_{old}$, $\omega_{old}$ and estimated running time for the multi-fault attack of [CJK$^{+}$09] (the stated $\gamma + \delta$ being out of reach of the single-fault variant).

As we can see from the table, the attack by Coron et al. has the advantage of requiring fewer faulty signatures to attack the same $\gamma + \delta$ value. However, lattice dimensions are much smaller in our case, making the attack considerably faster, and indeed practical for values very close to the theoretical maximum of 1/2, which are completely out of reach of the previous attack.

# 10.7 Application to EMV Signatures

## 10.7.1 The EMV specification

EMV is a collection of industry specifications for the inter-operation of payment cards, POS terminals and ATMs. The EMV specification [EMV] uses ISO/IEC 9796-2 signatures to certify public-keys and to authenticate data. For instance, to authenticate itself, the payment card must issue a signature on data provided by the terminal. The signature algorithm is RSA with ISO/IEC 9796-2 using $e = 3$ or $e = 2^{16} + 1$. The bit length of all moduli is always a multiple of 8. EMV uses special message formats; 7 different formats are used, depending on the message type.

In the following, for clarity's sake, we analyze one of these formats only: the *Offline Dynamic Data Authentication, Dynamic Application Data* format, described in Book 2,
Section 6.5, Table 15, page 67 of the EMV specifications [EMV]. The signing entity is the Card. The message $m$ to be signed has the format $m = m[1]||m[2]$ with:

$$m[1] = 0501_{16} || L_{DD} || ICCDD || BB \cdots BB_{16} \\ m[2] = DATA$$

where $L_{DD}$ is a byte identifying the length (in bytes) of the ICC Dynamic Data string ICCDD, and DATA is some data provided by the terminal. In general, the ICC Dynamic Data string has the following form:

$$ICCDD = L_{ICCDN} || ICCDN || ADD$$

where $L_{ICCDN}$ is one byte identifying the length (in bytes) of the time-variant ICC Dynamic Number ICCDN, and ADD consists of $L_{DD} - L_{ICCDN} - 1$ bytes of Additional Dynamic Data to be signed. It is specified that one must have $2 \le L_{ICCDN} \le 8$.

As mentioned in the EMV specifications, the ICC Dynamic Number can be an unpredictable number or a counter incremented for every new signature. In a typical use case (as described, for example, as part of EMV Test 2CC.086.1 Case 07 [EMV TC]), ICCDN is a random 8-byte string generated by the card, and ADD is a variable 8-byte string, encoded according to [ISO8825-1]. In this case, we have:

$$m[1] = 0501_{16} || 11_{16} || 08_{16} || ICCDN || ADD || BB \cdots BB_{16}$$

which can be rewritten as:

$$m[1] = X || r || BB \cdots BB_{16}$$

where $X$ is a known value and $r$ is a variable byte string of bit-size $k_r = 128$. This gives:

$$\mu(m) = 6A_{16} || X || r || BB \cdots BB_{16} || H(m) || BC_{16} \quad (10.9)$$

where $H(m)$ is a 160-bit digest of the encoded message $m$. Note that the no-fault forgery attack from Chapter 9 does not apply because here $m[1]$ cannot be controlled by the adversary.

## 10.7.2 Fault attack

The EMV format for $\mu(m)$ given in (10.9) is the same as the one recalled in §10.3.1 and considered in our new attack. In the particular use case described above, the string $X$ is known but $r$ and $H(m)$ are unknown to the attacker. Therefore the total number of unknown bits is:

$$k_r + k_h = 128 + 160 = 288.$$

Hence, for a 1024-bit modulus $N$, we get:

$$\gamma + \delta = \frac{288}{1024} \approx 0.28$$

which is well beyond the range of practical applicability of [CJK+09], as shown in Table 10.2. However, as apparent from the same table, our new attack will factor $N$ in a fraction of a second using about ten faulty signatures.
10.8 Proposed Countermeasures

Since faulty signatures are invalid, a possible countermeasure is to check the signature
after generation. Since signature verification is significantly cheaper than signature
generation in cases of interest (because of a low public exponent), this is a reasonable
option, and preferable to incurring the 4-fold performance penalty of not using the
Chinese Remainder Theorem at all. More generally, other usual countermeasures against
RSA-CRT fault attacks, as proposed e.g. by Shamir [Sha99, JPY01] or Giraud [Gir06],
apply to this setting. See however [KQ07] for an indication that such strategies may
prove ineffective in more elaborate attack models.

Furthermore, it should be noted that ad hoc signature paddings have no proof
of security even against standard attacks. The ISO/IEC 9796-2 padding scheme, in
particular, has a number of known vulnerabilities [CNS99, CNTW09]. It may be advisable
to use a probabilistic RSA signature scheme like PSS [BR96] instead, which is actually
secure in the random fault model considered here, as proved by Coron and Mandal
[CM09].
# Modulus Fault Attacks Against
RSA-CRT Signatures

## 11.1 Introduction

This chapter, like the previous one, is devoted to the description of a new fault attack on RSA signatures using the Chinese Remainder Theorem, and the mathematical tools involved are again the orthogonal lattice techniques of Nguyen and Stern.

However, while most of the work on RSA-CRT fault attacks and countermeasures since the seminal 1997 paper of Boneh, DeMillo and Lipton has concentrated on the perturbation of one of the two half exponentiations in signature generation, in this work we consider the injection of faults in the *public modulus* before CRT interpolation. This is a very different type of fault which does not seem to have been considered before, and which defeats fault countermeasures that concentrate on protecting the exponentiations.

This new attack proves very effective in practice: depending on the fault model, between 5 to 45 faults suffice to recover the RSA factorization within a few seconds. Our simplest attack requires that the adversary knows the faulty moduli, but the most sophisticated variant works even if the moduli are unknown, under reasonable fault models. All our attacks have been fully validated experimentally with fault-injection laser techniques.

This work is to be presented at CHES 2011 [BNNT11a] and will appear in the *Journal of Cryptographic Engineering* [BNNT11b].

### 11.1.1 Fault attacks on RSA-CRT signatures

To sign a message $m$ with RSA [RSA78], the signer first applies an encoding function $\mu$ to $m$, and then computes the signature $\sigma = \mu(m)^d \bmod N$. To verify the signature $\sigma$, the receiver checks that $\sigma^e = \mu(m) \bmod N$. The Chinese Remainder Theorem (CRT) is often used to speed up signature generation by a factor of about 4. This is done by
computing:

$$ \sigma_p = \mu(m)^{d \mod p-1} \mod p \quad \text{and} \quad \sigma_q = \mu(m)^{d \mod q-1} \mod q $$

and deriving $\sigma$ from $(\sigma_p, \sigma_q)$ using the CRT. As we discussed in Chapter 10, Boneh, DeMillo and Lipton [BDL97, BDL01] observed in 1997 that RSA-CRT implementations are vulnerable to fault attacks. Assuming that the attacker can induce a fault when $\sigma_q$ is computed while keeping the computation of $\sigma_p$ correct, one gets:

$$ \sigma_p = \mu(m)^{d \mod p-1} \mod p \quad \text{and} \quad \sigma_q \neq \mu(m)^{d \mod q-1} \mod q $$

hence:

$$ \sigma^e = \mu(m) \mod p \quad \text{and} \quad \sigma^e \neq \mu(m) \mod q $$

which allows the attacker to factor $N$ by computing $\gcd(\sigma^e - \mu(m) \mod N, N) = p$. This attack applies to any deterministic padding function $\mu$, such as Full Domain Hash [BR96], or probabilistic signatures where the randomizer used to generate the signature is sent along with the signature, such as PFDH [Cor02]. Only probabilistic signature schemes such that the randomness remains unknown to the attacker may be safe, though some particular cases have been attacked as well, as we saw in the previous chapter.

In 2005, Seifert [Sei05] introduced a new type of RSA fault attacks, by inducing faults on the RSA public modulus. The initial attack [Sei05] only allowed to bypass RSA verification, but key-recovery attacks were later discovered by Brier et al. [BCMCC06], and improved or extended in [Mui06, BCG08, BCDG09, BCDG10]. These key-recovery attacks only apply to RSA without CRT, and they require many more faults than the attack of Boneh et al.—at least on the order of 1000 faulty signatures.

### 11.1.2 Our contribution

We present new alternative key-recovery attacks on RSA-CRT signatures: instead of targeting one of the RSA-CRT sub-exponentiations, we inject faults into the public modulus like in Seifert’s attack. As a result, typical countermeasures against the attack of Boneh et al. do not apply to these new attacks.

Our attacks are based on the orthogonal lattice techniques introduced by Nguyen and Stern [NS97] in 1997. They are very effective in practice: they disclose the RSA factorization within a few seconds using only between 5 to 45 faulty signatures. The exact running time and number of faulty signatures depend on the fault model.

For instance, in our simplest attack, the running time is a fraction of a second using only 5 faulty signatures, but the attacker is assumed to know the faulted moduli for the 5 different messages. However, our attack can be extended to the case where the attacker no longer knows the faulted moduli, using at most 45 faulty signatures, under the following two fault models: either the faulted moduli only differ from the public modulus on a single byte of unknown position and unknown value, or the faulted moduli may differ from the public modulus by many bytes, but the differences are restricted to the least significant bits, up to half of the modulus size.

All our attacks have been fully validated with physical experiments with laser shots on a RISC microcontroller.
### 11.1.3 Related work

Many countermeasures have been proposed to protect against the attack of Boneh et al. and its numerous generalizations, but they often focus on the exponentiation process. The previously mentioned fault attacks [BCMCC06, Mui06, BCG08, BCDG09, BCDG10] on RSA using faulty moduli only apply to standard RSA without CRT, and they use non-lattice techniques. Our attack seems to be the first attack on RSA-CRT with faulted moduli.

It should be pointed out, however, that a number of protected RSA-CRT implementations also protect the CRT recombination. This is for example the case of [ABF+02, CJ05, Gir06, BNP07, Vig08, Riv09].

More generally, as we observe in §11.5, using the technique known as Garner's formula for CRT recombination does thwart the attack introduced in this chapter. Since this formula is often used in practice, typical implementations conforming to RSA standards like PKCS#1 [PKCS#1 v2.1] and IEEE P1363 [IEEE P1363] should in principle be immune to this attack.

### 11.1.4 Outline

In §11.2, we describe the basic attack where the faulty moduli are assumed to be known to the attacker. In §11.3, we extend the attack to realistic fault models in which the faulty moduli are no longer known to the attacker. In §11.4, we describe physical experiments with laser shots on a RISC microcontroller to validate the attack. Finally, in §11.5, we suggest possible countermeasures against this attack.

## 11.2 The New Attack

### 11.2.1 Overview

Consider again the generation of RSA-CRT signatures. To obtain the signature $\sigma$ of a message $m$ padded as $\mu(m)$, the signer computes the mod-$p$ and mod-$q$ parts:

$$ \sigma_p = \mu(m)^d \mod p \quad \text{and} \quad \sigma_q = \mu(m)^d \mod q $$

and returns the signature:

$$ \sigma = \sigma_p \cdot \alpha + \sigma_q \cdot \beta \mod N \quad (11.1) $$

where $\alpha, \beta$ are the pre-computed Chinese Remainder coefficients $\alpha = q \cdot (q^{-1} \mod p)$ and $\beta = p \cdot (p^{-1} \mod q)$.

Assume that an adversary can obtain the correct signature $\sigma$, and also a signature $\sigma'$ of the same padded message $\mu(m)$ after corrupting the modulus $N$ before the CRT step (11.1). In other words, the attacker gets $\sigma$ as before but also $\sigma'$ defined as:

$$ \sigma' = \sigma_p \cdot \alpha + \sigma_q \cdot \beta \mod N' \quad \text{for some } N' \neq N. $$
Suppose further, for the moment, that the adversary is able to recover the faulty modulus $N'$: we will see in §11.3 how this not-so-realistic hypothesis can be lifted in a more practical setting. Then, by applying the Chinese Remainder Theorem to $\sigma$ and $\sigma'$, the adversary can compute

$$v = \sigma_p \cdot \alpha + \sigma_q \cdot \beta \quad \mod N \cdot N'$$

But if we denote the bit length of $N$ by $n$, then $N \cdot N'$ is a 2n-bit integer, whereas $\alpha, \beta$ are of length $n$ and $\sigma_p, \sigma_q$ of length $n/2$, so $v$ is really a linear combination of $\alpha$ and $\beta$ in $\mathbb{Z}$:

$$v = \sigma_p \cdot \alpha + \sigma_q \cdot \beta.$$

That alone does not suffice to factor $N$, but several such pairs $(\sigma, \sigma')$ provide multiple linear combinations of the (unknown) integers $\alpha, \beta$ with relatively small coefficients. Then lattice reduction techniques allow us to recover the coefficients $\sigma_p$ and $\sigma_q$, and hence obtain the factorization of $N$ by GCDs. The following sections describe this process in detail.

### 11.2.2 Applying orthogonal lattice techniques

We refer to §10.2 or [Ngu09, NS01] for basic definitions and results on lattices. The cryptanalytic tool we use here is the orthogonal lattice technique introduced by Nguyen and Stern [NS97] and already used in §10.5. If $L$ is a lattice in $\mathbb{Z}^n$, we let $L^\perp$ be the lattice formed by all vectors in $\mathbb{Z}^n$ which are orthogonal to all vectors of $L$.

Suppose an attacker obtains $\ell$ pairs $(\sigma, \sigma')$ as above. He can compute as before a vector $v = (v_1, \dots, v_\ell)$ of $3n/2$-bit integers satisfying an equation of the form:

$$v = \alpha x + \beta y \qquad (11.2)$$

where $x, y$ are unknown vectors with $n/2$-bit components and $\alpha, \beta$ are the (unknown) CRT coefficients relative to $p$ and $q$. Lattice reduction can exploit such a hidden linear relationship as follows.

Using the results from [NS97, NS98], it is possible to compute a reduced basis $\{b_1, \dots, b_{\ell-1}\}$ of the lattice $v^\perp \subset \mathbb{Z}^\ell$ of vectors orthogonal to $v$ in $\mathbb{Z}^\ell$. In particular we get:

$$\alpha \langle b_j, x \rangle + \beta \langle b_j, y \rangle = 0 \quad \text{for } j = 1, 2, \dots, \ell-1.$$

Now, observe that the smallest nonzero solution $(u, v) \in \mathbb{Z}^2$ of the equation $\alpha \cdot u + \beta \cdot v = 0$ is $\pm(\beta, -\alpha)/g$, where $g = \gcd(\alpha, \beta)$ is heuristically expected to be very small, which implies that $|u|, |v| \ge \Omega(N)$ where the $\Omega(N)$ constant is very small. For each $j = 1, 2, \dots, \ell-1$, there are thus two possibilities:

* Case 1: $\langle b_j, x \rangle = \langle b_j, y \rangle = 0$, in which case $b_j$ belongs to the lattice $L = \{x, y\}^\perp$ of vectors in $\mathbb{Z}^\ell$ orthogonal to both $x$ and $y$;

* Case 2: $\langle b_j, x \rangle$ and $\langle b_j, y \rangle$ have absolute value $\ge \Omega(N)$ with a very small $\Omega(N)$ constant. Since $x, y$ both have norm at most $\sqrt{\ell N}$, this implies $\|b_j\| \ge \Omega(\sqrt{N/\ell})$ by Cauchy-Schwarz.
Since the lattice $L = \{\mathbf{x}, \mathbf{y}\}^{\perp}$ is of rank $\ell - 2$, Case 1 cannot hold for all $\ell - 1$ linearly independent vectors $\mathbf{b}_j$, so that the longest one $\mathbf{b}_{\ell-1}$ should be in Case 2, and hence $\|\mathbf{b}_{\ell-1}\| \ge \Omega(\sqrt{N/\ell})$. On the other hand, the other vectors form a lattice of rank $\ell - 2$ and volume:

$$V = \mathrm{vol}(\mathbb{Z}\mathbf{b}_1 \oplus \cdots \oplus \mathbb{Z}\mathbf{b}_{\ell-2}) \approx \frac{\mathrm{vol}(\mathbf{v}^{\perp})}{\|\mathbf{b}_{\ell-1}\|} = \frac{\|\mathbf{v}\|}{\|\mathbf{b}_{\ell-1}\|} \le \frac{\sqrt{\ell} \cdot N^{3/2}}{\Omega(\sqrt{N/\ell})} = O(\ell N)$$

which can heuristically be expected to behave like a random lattice. In particular, we should have:

$$\|\mathbf{b}_j\| = O(\sqrt{\ell-2} \cdot V^{1/(\ell-2)}) = O(\ell^{1/2+1/(\ell-2)} \cdot N^{1/(\ell-2)}) \quad \text{for } j = 1, 2, \dots, \ell-2.$$

This length is much smaller than $\sqrt{N/\ell}$ as soon as $\ell \ge 5$. Assuming that this is case, $\mathbf{b}_j$ should thus be in Case 1 for $j = 1, 2, \dots, \ell - 2$. This means that those vectors generate a sublattice $L' = \mathbb{Z}\mathbf{b}_1 \oplus \cdots \oplus \mathbb{Z}\mathbf{b}_{\ell-2}$ of full rank in $L = \{\mathbf{x}, \mathbf{y}\}^{\perp}$.

Taking orthogonal lattices, we get $(L')^{\perp} \supset L^{\perp} = \mathbb{Z}\mathbf{x} \oplus \mathbb{Z}\mathbf{y}$. Therefore, $\mathbf{x}$ and $\mathbf{y}$ belong to the orthogonal lattice $(L')^{\perp}$ of $L'$. Let $\{\mathbf{x}', \mathbf{y}'\}$ be a reduced basis of that lattice. We can enumerate all the lattice vectors in $(L')^{\perp}$ of length at most $\sqrt{\ell N}$ as linear combinations of $\mathbf{x}'$ and $\mathbf{y}'$. The Gaussian heuristic suggests that there should be roughly:

$$\frac{\pi(\sqrt{\ell N})^2}{\mathrm{vol}((L')^{\perp})} = \frac{\pi \ell N}{V} = O(1)$$

such vectors, so this is certainly feasible. For all those vectors $\mathbf{z}$, we can compute $\mathrm{gcd}(\mathbf{v} - \mathbf{z}, N)$. We will thus quickly find $\mathrm{gcd}(\mathbf{v} - \mathbf{x}, N)$ among them, since $\mathbf{x}$ is a vector of length $\le \sqrt{\ell N}$ in $(L')^{\perp}$. But by definition of $\mathbf{v}$ we have:

$$\mathbf{v} = \mathbf{x} \mod p \quad \text{and} \quad \mathbf{v} = \mathbf{y} \mod q$$

so $\mathrm{gcd}(\mathbf{v} - \mathbf{x}, N) = p$, which reveals the factorization of $N$.

### 11.2.3 Attack summary

Assume that, for $\ell \ge 5$ padded messages $\mu(m_i)$, we know a correct signature $\sigma_i$ and a signature $\sigma'_i$ computed with a faulty modulus $N'_i$. Then, we can heuristically recover the factorization of $N$ as follows.

1. For each $i$, compute the integer $v_i = \mathrm{CRT}_{N,N'_i}(\sigma_i, \sigma'_i)$. They form a vector $\mathbf{v} = (v_1, \dots, v_\ell) \in \mathbb{Z}^\ell$.

2. Compute an LLL-reduced [LLL82] basis $\{\mathbf{b}_1, \dots, \mathbf{b}_{\ell-1}\}$ of the lattice $\mathbf{v}^{\perp} \subset \mathbb{Z}^\ell$ of vectors in $\mathbb{Z}^\ell$ orthogonal to $\mathbf{v}$. This is done by applying LLL to the lattice in $\mathbb{Z}^{1+\ell}$ generated by the rows of the following matrix:

$$\begin{pmatrix}
\kappa v_1 & 1 & 0 \\
\vdots & \ddots & \vdots \\
\kappa v_\ell & 0 & 1
\end{pmatrix}$$
<table><caption>Table 11.1: Attack success probability as a function of the number of faulty signatures and the size of N. Each parameter set was tested with random faults on 500 random moduli of the given size.</caption><thead><tr><th>Number of faulty signatures <i>l</i></th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><td>1024-bit moduli</td><td>48%</td><td>100%</td><td>100%</td></tr><tr><td>1536-bit moduli</td><td>45%</td><td>100%</td><td>100%</td></tr><tr><td>2048-bit moduli</td><td>46%</td><td>100%</td><td>100%</td></tr></tbody></table>

where $κ$ is a suitably large constant, and removing the first component of each resulting vector [NS97].

3. The first $l-2$ vectors $b_1, \dots, b_{l-2}$ generate a lattice $L' \subset \mathbb{Z}^l$ of rank $l-2$. Compute an LLL-reduced basis $\{x', y'\}$ of the orthogonal lattice $(L')^\perp$ to that lattice. Again, this is done by applying LLL to the lattice in $\mathbb{Z}^{l+2+l}$ generated by the rows of

$$ \begin{pmatrix} \kappa' b_{1,1} & \cdots & \kappa' b_{l-2,1} & 1 & 0 \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \kappa' b_{1,l} & \cdots & \kappa' b_{l-2,l} & 0 & 1 \end{pmatrix} $$

and keeping the last $l$ components of each resulting vector.

4. Enumerate the vectors $z = ax' + by' \in (L')^\perp$ of length at most $\sqrt{lN}$, and for each such vector $z$, compute $\gcd(v - z, N)$ using all components, and return any nontrivial factor of N.

### 11.2.4 Simulation results

Since the attack is heuristic, it is important to evaluate its experimental performances. To do so, we have implemented a simulation of the attack in SAGE [S+10b]: for a given modulus $N$, we compute the vector $v$ corresponding to a series of $l$ signatures on random messages and apply the lattice attack, attempting to recover a factor of $N$.

Table 11.1 shows the measured success probabilities for various values of $l$ and modulus sizes. It confirms the heuristic prediction that 5 faulty signatures should always suffice to factor $N$. It turns out that even 4 signatures are enough in almost half the cases.

Experimental running times are given in Table 11.2. The whole attack takes a few dozen milliseconds on a standard PC. The number of vectors to test as part of the final exhaustive search step is about 20 in practice, which is done very quickly.

## 11.3 Extending the Attack to Unknown Faulty Moduli

As mentioned in §11.2.1, in its basic form, the attack requires the recovery of the faulty moduli $N'_i$ in addition to the corresponding faulty signatures $\sigma'_i$. This is not a very
<table><caption>Table 11.2: Efficiency of the attack with $ℓ = 5$ faulty signatures and various modulus sizes. Each parameter set was tested with random faults on 500 random moduli of the given size. Timings for a SAGE implementation, on a single 2.4 GHz Core2 CPU core.</caption><thead><tr><th>Modulus size</th><th>1024</th><th>1536</th><th>2048</th></tr></thead><tbody><tr><td>Average search space πℓN/V</td><td>24</td><td>23</td><td>24</td></tr><tr><td>Average total CPU time</td><td>16 ms</td><td>26 ms</td><td>34 ms</td></tr></tbody></table>

realistic assumption, since a typical implementation does not output the public modulus along with each signature.

To work around this limitation, we would like to reconstruct the vector $v$ of integer values needed to run the attack from signatures alone, without the knowledge of the faulty moduli—possibly at the cost of requiring a few more faulty signatures.

This can actually be achieved in various ways depending on the precise form of the faults inflicted to the modulus. We propose solutions for the following two realistic fault models:

1. The faulty moduli $N'_i$ differ from $N$ on a single (unknown) byte. This is known to be possible using power glitches or laser shots with small aperture.

2. The differences between the faulty moduli $N'_i$ and $N$ are located on the least significant half: the errors on the least significant bits can be up to half of the modulus size. It is easy to obtain such faults with a laser or a cold boot attack.

### 11.3.1 Single byte faults

In this model, the attacker is able to obtain a certain number $ℓ' \ge 5$ of pairs $(\sigma_i, \sigma'_i)$ where $\sigma_i = \alpha x_i + \beta y_i \mod N$ is a valid signature and $\sigma'_i = \alpha x_i + \beta y_i \mod N'_i$ is the same signature computed with a faulty modulus. The faulty moduli $N'_i$ are not known, but they only differ from $N$ on a single byte whose position and value is unknown.

This type of fault can for example occur when attacking the transfer of the modulus to memory on a smart card with an 8-bit processor, or when using a laser attack with a sufficiently focused beam.

For a 1024-bit modulus $N$, for example, there are $128 \times 255 \approx 2^{15}$ possible faulty moduli. It can thus seem like a reasonable approach to try and run the attack with all possible faults. However, since this should be done with 5 signatures, this results in a search space of size $\approx (2^{15})^5 = 2^{75}$ which is prohibitive.

This kind of exhaustive search can be made practical, though, if we take into account the fact that the CRT value $v_i = \text{CRT}_{N,N'_i}(\sigma_i, \sigma'_i)$ satisfies:

$$v_i = \alpha x_i + \beta y_i \le N \cdot (p+q) = N^{3/2} \left( \sqrt{\frac{p}{q}} + \sqrt{\frac{q}{p}} \right) < (2N)^{3/2}$$
<table><caption>Table 11.3: Exhaustive search space size for the vector **v** of CRT values, and average attack running time, depending on the number of pairs ($\sigma_i, \sigma'_i$) available to the attacker. Measured for a family of random single byte faults on a 1024-bit modulus. Timings are given for the SAGE implementation as above.</caption><thead><tr><th>Number of pairs <i>l'</i></th><th>5</th><th>7</th><th>10</th><th>15</th><th>20</th><th>25</th></tr></thead><tbody><tr><th>Search space size (bits)</th><td>11.6</td><td>9.8</td><td>7.2</td><td>6.2</td><td>4.2</td><td>2.6</td></tr><tr><th>Total attack time (seconds)</th><td>49</td><td>14</td><td>2.4</td><td>1.2</td><td>0.29</td><td>0.10</td></tr></tbody></table>

since $p/q \in (1/2, 2)$. Now, for a given value of $\sigma'_i$, there are only very few possible target moduli $N_i^*$ differing from $N$ on a single byte such that $v_i^* = \text{CRT}_{N,N_i^*}(\sigma_i, \sigma'_i) < (2N)^{3/2}$: often only one or two, and almost never more than 20. We only need to run the attack with those target $v_i^*$'s until we find a factor.

Experimentally, for a 1024-bit modulus, the average base 2 logarithm of the number of possible $v_i^*$'s is about 2.5, so if an attacker has 5 pairs ($\sigma_i, \sigma'_i$) in this model, they can expect to try all vectors **v** in a search space of around 12.5 bits, i.e. run the attack a few thousand times, for a total running time of under 2 minutes. This is already quite practical.

If more pairs are available, the attacker can keep the 5 pairs for which the number of possible $v_i^*$'s is the smallest. This reduces the search space accordingly. In Table 11.3, we show how the exhaustive search space size and the average running time evolve with the number of signatures in a typical example.

### 11.3.2 Faults on many least significant bits

In this model, the attacker is able to obtain $\ell = 5$ signature families of the form $(\sigma_i, \sigma'_{i,1}, \dots, \sigma'_{i,k})$, where the $\sigma_i$'s are correct signatures:

$$ \sigma_i = \alpha x_i + \beta y_i \mod N $$

and the $\sigma'_{i,j}$'s are faulty signatures of the form:

$$ \sigma'_{i,j} = \alpha x_i + \beta y_i \mod N'_{i,j} \quad 1 \le i \le \ell, \ 1 \le j \le k. $$

In other words, for each one of the $\ell$ different messages, the attacker learns the reduction of the CRT value $v_i = \alpha x_i + \beta y_i$ modulo $N$, as well as modulo $k$ different unknown faulty moduli $N'_{i,j}$. Additionally, it is assumed that all $N'_{i,j}$ differ from $N$ only on the least significant bits, but the number of distinct bits can be as large as half of the modulus size: we assume that $|N - N'_{i,j}| < N^\delta$ for a certain constant $\delta < 1/2$.

This is a reasonable fault model for a laser attack: it suffices to target a laser beam on the least significant bits of $N$ to produce this type of faults.

To run the attack successfully, the attacker needs to recover the CRT values $v_i$. This can be done with high probability when the number of available faults $k$ for a given message is large enough. The simplest approach is based on a GCD computation.
<table><caption>Table 11.4: Success probabilities of the GCD method for CRT value recovery, depending on the number of available faults on a given message. Tested with random 1024-bit moduli. In the simulation, errors $\varepsilon_j$ are modeled as uniformly random signed integers of the given size, and 10,000 of them were generated for each parameter set.</caption><thead><tr><th>k (faults per message)</th><th>3</th><th>5</th><th>7</th><th>9</th></tr></thead><tbody><tr><td>1/ζ(k)</td><td>.832</td><td>.964</td><td>.992</td><td>.998</td></tr><tr><td>100-bit errors</td><td>83.2%</td><td>96.8%</td><td>99.0%</td><td>99.8%</td></tr><tr><td>200-bit errors</td><td>83.4%</td><td>96.2%</td><td>99.2%</td><td>99.8%</td></tr><tr><td>400-bit errors</td><td>82.7%</td><td>96.6%</td><td>99.1%</td><td>99.8%</td></tr><tr><td>Average CPU time</td><td>.73 ms</td><td>.75 ms</td><td>.79 ms</td><td>.85 ms</td></tr></tbody></table>

Indeed, fix an index $i \in \{1, \dots, \ell\}$, and write $N'_{i,j} = N + \varepsilon_j$, $v_i = u$, $\sigma_i = u_0$ and $\sigma'_{i,j} = u_j$. The attacker knows the $u_j$'s and wants to recover $u$.

Now, observe that there are integers $t_j$ such that $u$ satisfies $u = u_0 + t_0 \cdot N$ and $u = u_j + t_j \cdot (N + \varepsilon_j)$. In particular, for $j = 1, \dots, k$ we can write:

$$ (t_j - t_0) \cdot N + (u_j - u_0) + t_j \cdot \varepsilon_j = 0. \qquad (11.3) $$

This implies that $u_j - u_0 \equiv t_j \cdot \varepsilon_j \pmod N$. However, we have $t_j \cdot \varepsilon_j < N^{1/2+\delta} \ll N$, so that the congruence is really an equality in $\mathbb{Z}$. In view of (11.3), this implies that all $t_j$'s are in fact equal, and hence:

$$ t_0 \cdot \varepsilon_j = u_0 - u_j \quad 1 \le j \le k. $$

If the errors $\varepsilon_j$ on the modulus are co-prime, which we expect to happen with probability $\approx 1/\zeta(k)$, we can then deduce $t_0$ as the GCD of all values $u_0 - u_j$, and this gives:

$$ u = u_0 + t_0 \cdot N = u_0 + N \cdot \gcd(u_0 - u_1, \dots, u_0 - u_k). $$

As seen in Table 11.4, the success probability is in practice very close to $1/\zeta(k)$ regardless of the size of errors.

It is probably possible to further improve the success probability by trying to remove small factors from the computed GCD $g = \gcd(u_0 - u_1, \dots, u_0 - u_k)$ to find $t_0$ when $g > \sqrt{N}$, but we find that the number of required faults is already reasonable without this computational refinement.

Indeed, recall that $\ell = 5$ CRT values are required to run the attack. If $k$ faults are obtained for each of the $\ell$ messages, the probability that these $\ell$ CRT values can be successfully recovered with this GCD approach is $\zeta(k)^{-\ell}$. This is greater than 95% for $k = 7$, and 99% for $k = 9$.

We can also mention an alternate, lattice-based approach to recovering the CRT value $u$. The relation between the different quantities above can be written in vector form as:

$$ u_0 \mathbf{1} = \mathbf{u} + t_0 \mathbf{e} $$
where $\mathbf{1} = (1, \dots, 1)$, $\mathbf{u} = (u_1, \dots, u_k)$ and $\mathbf{e} = (\varepsilon_1, \dots, \varepsilon_k)$.

Then, since $u_0 \approx N$ is much larger than $\|t_0\mathbf{e}\| \approx N^{1/2+\delta}$, short vectors orthogonal to $\mathbf{u}$ will be orthogonal to both $\mathbf{1}$ and $\mathbf{e}$. More precisely, we can heuristically expect that when $k$ is large enough ($k \gtrsim 2/(1-2\delta)$), the first $k-2$ vectors of a reduced basis of $\mathbf{u}^{\perp}$ will be orthogonal to $\mathbf{1}$ and $\mathbf{e}$.

Taking orthogonal lattices again, we can thus obtain a reduced basis $\{\mathbf{x}, \mathbf{y}\}$ of a two-dimensional lattice containing $\mathbf{1}$ and $\mathbf{e}$ (and of course $\mathbf{u}$). Since $\mathbf{1}$ is really short, we always find that $\mathbf{x} = \mathbf{1}$ in practice. Then, it happens quite often that $\mathbf{y}$ can be written as $\lambda\mathbf{1} \pm \mathbf{e}$, in which case $t_0$ is readily recovered as the absolute value of the second coordinate of $\mathbf{u}$ in the basis $\{\mathbf{x}, \mathbf{y}\}$.

However, this fails when $\mathbb{Z}\mathbf{1} \oplus \mathbb{Z}\mathbf{e}$ is a proper sublattice of $\mathbb{Z}\mathbf{x} \oplus \mathbb{Z}\mathbf{y} = \mathbb{Z}^k \cap (\mathbb{Q}\mathbf{1} \oplus \mathbb{Q}\mathbf{e})$, namely, when there is some integer $d > 1$ such that all errors $\varepsilon_j$ are congruent mod $d$. Thus, we expect the success probability of this alternate approach to be $1/\zeta(k-1)$, which is slightly less than with the GCD approach.

## 11.4 Practical Experiments

Practical experiments for validating the new attack were done on an 8-bit 0.35µm RISC microcontroller with no countermeasures. As the microprocessor had no arithmetic coprocessor the values $\sigma_p$ and $\sigma_q$ were pre-computed by an external program upon each fault-injection experience and fed into the attacked device. The target combined $\sigma_p$ and $\sigma_q$ using multiplications and additions (using Formula 11.1) as well as the final modular reduction.

The location and spread of the faults were controlled by careful beam-size and shot-instant tuning. The reader is referred to Appendix app:laser for a description of the physical setting (common to the experiments reported in [MDT$^{+}$10]).

We conducted several practical experiments corresponding to three different scenarios, roughly corresponding to the fault models considered in §11.2.1, §11.3.1 and §11.3.2 respectively. Let us describe these experiments in order.

### 11.4.1 First scenario: Known modulus

In this case, we considered 5 messages for a random 1024-bit RSA modulus $N$. For each message $m_i$, we obtained a correct signature $\sigma_i$, as well as a faulty-modulus signature $\sigma'_i$ where the faulty modulus $N'_i$ was also read back from the microcontroller.

Therefore, we were exactly in the setting described in §11.2.1, and could apply the algorithm from §11.2.3 directly: apply the Chinese Remainder Theorem to construct the vector $\mathbf{v}$ of CRT values and run the lattice-based attack to recover a factor of $N$.

The implementation of the attack used the same SAGE code as the simulation from §11.2.4. In our experimental case, the ball of radius $\sqrt{N\ell}$ contained only about 10 vectors of the double orthogonal lattice, and the whole attack revealed a factor of $N$ in less than 20 milliseconds.
## 11.4.2 Second scenario: Unknown single byte faults

In this case, we tried to replicate a setting similar to the one considered in §11.3.1. We considered 20 messages and a random 1024-bit RSA modulus $N$. For each message $m_i$, we obtained a correct signature $\sigma_i$, as well as faulty-modulus signatures $\sigma'_i$ with undisclosed faulty modulus $N'_i$ generated by targeting a single byte of $N$ with the laser.

We had to eliminate some signatures, however, because in some cases, errors on the modulus turned out to exceed 8 bits.<fnref n="1" /> After discarding those, we had 12 pairs $(\sigma_i, \sigma'_i)$ left to carry out the approach described in §11.3.1.

The first step in this approach is to find, for each $i$, all values $v_i^*$ of the form $CRT_{N,N_i^*}(\sigma_i, \sigma'_i)$ ($N_i^*$ differing from $N$ only on one byte) that are small enough to be correct candidate CRT values. Unlike the setting of §11.3.1, we could not assume that bit-differences were aligned on byte boundaries: we had to test a whole $1016 \times 255$ candidate moduli<fnref n="2" /> $N_i^*$ for each $i$. Therefore, this search step was a bit costly, taking a total of 11 minutes and 13 seconds. Additionally, due to the higher number of candidate moduli, the number of candidate CRT values $v_i^*$ was also somewhat larger than in §11.3.1, namely:

$$7, 17, 3, 9, 15, 5, 14, 44, 44, 17, 10, 55$$

for our 12 pairs respectively. Keeping only the 5 indices with the smallest number of candidates, we obtained $3 \times 5 \times 7 \times 9 \times 10 = 9450$ possible CRT value vectors $v^*$.

We then ran the lattice-based attack on each of these vectors in order until a factor of $N$ was found. The factor was found at iteration number 2120, after a total computation time of 43 seconds.

## 11.4.3 Third scenario: Least significant bytes faults

In this case, we considered 10 messages for a random 1024-bit $N$. For each message $m_i$, we obtained a correct signature $\sigma_i$, as well as 10 faulty-modulus signature $\sigma'_{i,j}$ with undisclosed faulty modulus $N'_{i,j}$. The laser beam targeted the lower order bytes of $N$ but with a large aperture, generating multiple faults stretching over as much as 448 modulus bits.

In practice, we only used the data $(\sigma_i, \sigma'_{i,1}, \dots, \sigma'_{i,10})$ for the first 5 messages, discarding the rest. Then, we reconstructed the CRT values $v_i$ using the GCD technique of §11.3.2:

$$v_i = \sigma_i + N \cdot \gcd(\sigma_i - \sigma'_{i,1}, \dots, \sigma_i - \sigma'_{i,10}) \quad 1 \le i \le 5$$

and applied the lattice-based attack on the resulting vector $v$. This revealed a factor of $N$ in 16 milliseconds.

<footnote n="1">¹Note that in a real-world attack, it might not be possible to detect such overly spread out faults: hence, this particular technique should be used preferably when faults are known to affect only single bytes (e.g. in a glitch attack), whereas the technique from the next section is better suited to laser attacks as aperture control is much less of an issue.</footnote>

<footnote n="2">²There are duplicates among those, corresponding to perturbations of 7 consecutive bits or less, but we did not attempt to avoid testing them several times, as this can only improve the search by a small constant factor while introducing significant complexity in the code.</footnote>
We also tried the same attack using a fewer number of the $\sigma'_{i,j}$'s, and found that it still worked when taking only 4 of those values in the computation of $v_i$:

$$v_i = \sigma_i + N \cdot \gcd(\sigma_i - \sigma'_{i,1}, \dots, \sigma_i - \sigma'_{i,4}) \quad 1 \le i \le 5$$

but failed if we took 3 instead. Considering that $1/\zeta(3)^5 \approx .40$ and $1/\zeta(4)^5 \approx .67$, this is quite in line with expectations.

## 11.5 Countermeasures and Further Research

Probabilistic and stateful signature schemes are usually secure against this attack, since they make it difficult to obtain two signatures on the same padded message. However, all deterministic schemes are typically vulnerable, including those in which the attacker doesn't have full access to the signed message, provided that the target device can be forced to compute the same signature twice.

A natural countermeasure is to use a CRT interpolation formula that does not require $N$, such as Garner's formula, computed as follows:

$$ \begin{array}{l} t \leftarrow \sigma_p - \sigma_q \\ \text{if } t < 0 \text{ then } t \leftarrow t + p \\ \sigma \leftarrow \sigma_q + (t \cdot \gamma \bmod p) \cdot q \\ \text{return}(\sigma) \end{array} $$

where we assume that $p > q$, and $\gamma$ is the usual CRT coefficient $q^{-1} \bmod p$. Note that the evaluation of $\sigma$ does not require a modular reduction because

$$\sigma = \sigma_q + (t \cdot \gamma \bmod p) \cdot q \le q - 1 + (p - 1)q < N.$$

Besides the obvious countermeasures consisting in checking signatures before release, it would be interesting to devise specific countermeasures for protecting Formula (11.1) (or Garner's formula) taking into account the possible corruption of all data involved.

## 11.A Laser Fault Injection

Laser (Light Amplification by Stimulated Emission of Radiation) is a stimulated-emission electromagnetic radiation in the visible or the invisible domain. Laser light is monochromatic, unidirectional, coherent and artificial (i.e. laser does not spontaneously exist in nature). Laser light can be generated as a beam of very small diameter (a few $\mu$m). The beam can pass through various material obstacles before impacting a target during a very short duration.

Laser impacts on electronic circuits are known to alter functioning. Current chip manufacturing technologies are in the nanometers range. This, and the laser's brief and precise reaction time, makes laser a particularly suitable fault injection means.
<figure><img src="image_22.png" /><figcaption>Figure 11.1: Architecture of a typical SRAM cell.</figcaption></figure>

## 11.A.1 Photoelectric effects of laser on silicon

SRAM (Static Random Access Memory) laser exposure is known to cause bit-flips [SA02], [DBP+02], [BECN+06], [Can09], a phenomenon called *Single Event Upset* (SEU). By tuning the beam's energy level below a destructive threshold, the target will not suffer any permanent damage.

A conventional one-bit SRAM cell (Figure 11.1) is made of two cross-coupled inverters. Every cell has two additional transistors controlling the cell's content access during write and read. As every inverter is made of two transistors, an SRAM cell contains six MOS.

In each cell, the states of four transistors encode the stored value. By design, the cell admits only two stable states: a “0” or a “1”. In each stable state, two transistors are at an ON state and two others are OFF.

If a laser beam hits the drain/bulk reversed-biased PN junctions of a blocked transistor, the beam's energy may create pairs of electrons as the beam passes through the silicon. The charge carriers induced in the collection volume of the drain-substrate junction of the blocked transistor are collected and create a transient current that inverts logically the inverter's output voltage. This voltage inversion is in turn applied to the second inverter that switches to its opposite state: all in all, a bit flip happens [DBP+02], [BECN+06].

From the opponent's perspective, an additional advantage of laser fault injection is *reproducibility*. Identical faults can be repeated by carefully tuning the laser's parameters and the target's operating conditions.

## 11.A.2 Different parameters in a fault attack by laser

In a laser attack, the opponent usually controls the beam's diameter, wavelength, amount of emitted energy, impact coordinates (attacked circuit part) and the exposure's duration. Sometimes, the opponent may also control the synchronicity of the impact with a given clock cycle of the target, the target's clock frequency, $V_{cc}$ and temperature. Finally, laser attacks may indifferently target the chip's front side or back side.

However, the chip's front and back sides have different characteristics when exposed to a laser beam.

Front side attacks are particularly suited to green wavelength (~532nm). The visibility of chips components makes positioning very easy in comparison to backside attacks. But because of the metallic interconnects' reflective effect, it is difficult to target a component with enough accuracy. In addition, progress in manufacturing technology
gies results in both a proliferation of metal interconnects and much smaller chips. All in all, it becomes increasingly difficult to hit a target area.

**Backside attacks** are more successful at the infrared wavelength (~1064nm) as the laser needs to deeply enter the silicon. Positioning is more difficult for lack of visibility. Nonetheless, backside attacks allow to circumvent the reflective problem of metallic surfaces.

### 11.A.3 Practical CRT fault injection

After chip decapsulation and a mapping of the chip's components, we selected a large target area, given our knowledge of the implementation. Using automated search on the chip's front-side, we modified the impact's coordinates, the beam parameters and timing until a reproducible fault area was obtained.

The target is an 8-bit 0.35 µm 16 MHz RISC microcontroller with an integrated 4KB SRAM and no countermeasures. The device runs SOSSE (Simple Operating System for Smartcard Education [B+03]) to which we added some commands, most notably for feeding-in the data {$N, p, q, \sigma_p, \sigma_q, p^{-1} \mod q, q^{-1} \mod p$}. Upon reception all these parameters are stored in SRAM. The laser, shown in Figures 11.6 and 11.7, is equipped with a YAG laser emitter in three different wavelengths: green, infrared and ultraviolet.

The spot's diameter can be set between 0 and 2500µm. As the beam passes through a lens, it gets reduced by the lens' zoom factor and loses a big part of its energy. Our experiments were conducted with a 20× Mitutoyo lens, a green<fnref n="3" /> beam of Ø4µm and ≃ 15pJ per shot<fnref n="4" />. The circuit is installed on a programmable Prior Scientific X-Y positioning table<fnref n="5" />. The X-Y table, card reader, laser and an FPGA trigger board, were connected via RS-232 to a control PC. The FPGA trigger board receives an activation signal from the reader and sends a trigger signal to the laser after a delay defined by the control PC.

Experiments were conducted in ambient temperature and at $V_{cc}$ = 5V. These parameters are within the device's normal operating conditions $2.7V \le V_{cc} \le 5.5V$.

The chip was decapsulated by chemical etching using a Nisene JetEtch automated acid decapsulator. The decapsulator can be programmed for the chemical opening of different chip types using different ratios of nitric acid (HNO₃) and sulfuric acid (H₂SO₄), at a desired temperature and during a specified time. For opening our chip, we used only nitric acid at 80°C for 40 seconds. The etched chip (Figure 11.2) successfully passed functional tests before and during fault injection.

As it is very difficult to target the chip's ALU (Arithmetic Logic Unit) during a very specific calculation step, we decided to hit the SRAM to corrupt data rather than modify calculations.

<footnote n="3">³532nm wavelength.</footnote>

<footnote n="4">⁴At the laser source emitter, before passing through the lens.</footnote>

<footnote n="5">⁵Motorized stepper stage for upright microscopes with 0,1 µm steps.</footnote>
<figure><img src="image_23.png" /><figcaption>Figure 11.2: Decapsulated chip (SRAM is on the left middle and bottom side).</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Figure 11.3: Decapsulated chip (closeup on SRAM).</figcaption></figure>

Finding the SRAM area containing each data element and properly tuning the laser's parameters is very time consuming. The number of faults in the read back data, their position and their contents indicate which element has been hit.

Figure 11.5 compares a 1µm laser spot and SRAM cells in different technology sizes. As technology advances, transistor density per µm grows. With several transistors are packed into 1µm areas, single-bit fault injection will require much more precise equipment and are likely to become unfeasible using cheap lasers.

Figure 11.4 shows how we explored the target SRAM space. The method consisted in searching *N*'s precise storage area, shooting into it and reading data back. Figure 11.4 is just a schematic model of the real SRAM (Figure 11.3) to describe our technique and does not correspond to real address allocation. We could successfully inject multiple byte faults into selected parts of *N* and iterate the process for different moduli and signatures. This sufficed to implement our scenario.
<figure><img src="image_25.png" /><figcaption>Figure 11.4: Exploration process.</figcaption></figure>
<table><caption>Figure 11.5: 1µm laser spot (dotted circle) vs. technology sizes [Pou07].</caption><thead><tr><th></th><th>Transistor</th><th>SRAM Cell</th></tr></thead><tbody><tr><td>350nm</td><td></td><td></td></tr><tr><td>130nm</td><td></td><td></td></tr><tr><td>90nm</td><td></td><td></td></tr><tr><td>65nm</td><td></td><td></td></tr></tbody></table>

<figure><img src="image_26.png" /><figcaption>Figure 11.6: Laser and target (general overview).</figcaption></figure>

<figure><img src="image_27.png" /><figcaption>Figure 11.7: Laser and target (closeup).</figcaption></figure>
<figure><img src="image_28.png" /></figure>
# On the Broadcast and Validity-Checking Security of PKCS#1 v1.5 Encryption

## 12.1 Introduction

Returning to black-box model attacks on ad-hoc RSA paddings, this chapter describes new attacks on PKCS#1 v1.5 encryption, a deprecated but still widely used RSA encryption standard.

The first attack predicts, using a single query to a validity checking oracle, which of two chosen plaintexts corresponds to a challenge ciphertext (in other words, it breaks semantic security under validity-checking attacks). The rather simple idea is that a validity-checking oracle makes it possible to check when the least significant bits of the plaintext are zero, an observation that essentially goes back to Bleichenbacher's famous 1998 attack on SSL.

The second attack is a so-called broadcast attack, allowing the opponent to reveal an identical plaintext sent to different recipients, which is nontrivial because different random nonces are used for different encryptions (i.e. plaintexts coincide only partially). It relies on multivariate generalizations Coppersmith's technique for finding small roots of polynomials over $Z_N$.

This work was presented at ACNS 2010 [BCN+10].

### 12.1.1 The PKCS#1 v1.5 standard

PKCS stands for *Public-Key Cryptography Standards*, and refers to a large body of specifications covering RSA encryption, Diffie-Hellman key agreement, password-based encryption, syntax (extended-certificates, cryptographic messages, private-key information and certification requests) and selected attributes. PKCS was initially developed by RSA Laboratories in collaboration with academia and multiple industry players, and has been
regularly updated since. Today, PKCS has become part of several standards and of a
wide range of security products including S/MIME (the standard for encrypted e-mails).

Within the PKCS collection, PKCS#1 v1.5 [PKCS#1 v1.5] describes a particular
padding scheme for RSA encryption, in which the secret data (usually a random symmetric
key for a block cipher) is prepended with random bytes before applying the RSA function.

At CRYPTO 1998, Bleichenbacher [Ble98] presented an adaptive chosen-ciphertext
attack against PKCS#1 v1.5 capable of recovering arbitrary plaintexts from about half
a million ciphertexts. Although active adversarial models are generally regarded as
theoretical concerns, Bleichenbacher's attack makes use of an oracle that only detects
conformance with respect to the padding format, a real-life assumption that resulted in
a practical threat. PKCS#1 v1.5 was subsequently updated (release 2.0 [PKCS#1 v2.0])
and patches were issued to users wishing to continue using the old version of the standard.
Over a decade later and despite its vulnerabilities, PKCS#1 v1.5 remains widely used
in applications. Provably secure algorithms such as RSA-OAEP [BR94, FOPS04] and
RSA-KEM [CS03, ISO18033-2, ANSI X9.44] are recommended replacements, but their
deployment remains limited.

Another more recent work by Coron, Joye, Naccache and Paillier on the security of PKCS#1 v1.5 [CJNP00] presented a somewhat atypical attack allowing the opponent to retrieve plaintexts ending by enough zero bits.

12.1.2 Our results

In this chapter, we look again at the security of PKCS#1 v1.5 in various adversarial
models, and mainly describes two new weaknesses in PKCS#1 v1.5:

* The possibility to predict, using a single validity-checking query and with high probability, which of two chosen plaintexts corresponds to a challenge ciphertext. In other words, we show that PKCS#1 v1.5 encryption in not 1-IND-VCA-secure. The proof is quite elementary.

* A broadcast attack allowing to decrypt an identical message sent to several recipients. The attack is based on multivariate extensions of Coppersmith's technique for finding small roots of polynomials modulo an integer with unknown factorization.

We also obtain some additional results, including a (rather weak) positive security
result on the one-wayness of PKCS#1 v1.5, and a proof that PKCS#1 v1.5 encryption
is malleable.

12.2 Preliminaries

12.2.1 Public-key encryption

A public-key encryption scheme $\mathcal{P} = (\text{KeyGen}, \text{Encrypt}, \text{Decrypt})$ is a collection of three efficient algorithms (the first two can be probabilistic):
KeyGen(1^k): produces a pair (pk, sk) of matching public and private keys depending on the security parameter k (which implicitly define a message space M).

Encrypt(pk, m ∈ M): produces a ciphertext c = Encrypt(pk, m).

Decrypt(sk, c): produces a plaintext m = Decrypt(sk, c) or ⊥.

For all m ∈ M and for properly generated {pk, sk}, the following correctness condition must hold:

$$ \text{Decrypt}(sk, \text{Encrypt}(pk, m)) = m. $$

### 12.2.2 Security definitions

Security is traditionally defined by combining an adversarial goal and an attack model. We refer to classical texts on provable security, such as [Poi05], for precise statements of security definitions. Intuitively, a public-key encryption scheme $\mathcal{P}$ is:

*   **Unbreakable (UBK):** if no efficient adversary $\mathcal{A}$ can compute sk given pk with significant probability;

*   **One-Way (OW):** if no efficient adversary $\mathcal{A}$ can recover m ∈ M given pk and c = Encrypt(pk, m) with significant probability;

*   **Indistinguishable (IND):** if no efficient adversary $\mathcal{A}$, given pk and a ciphertext computed from one of two messages of his choice, can guess with significant probability which of the two messages was encrypted (this is also referred to as “semantic security”, as it implies no information on the plaintext can be recovered from a ciphertext by an efficient adversary);

*   **Non-Malleable (NM):** if no adversary $\mathcal{A}$ can produce, given pk and a ciphertext c = Encrypt(pk, m) corresponding to a message m chosen according to a distribution of his choice (with positive entropy), a new ciphertext c' ≠ c corresponding to a plaintext m' meaningfully related to m (in the sense that $\mathcal{R}(m, m') = 1$ with good probability, for some binary relation $\mathcal{R}$ initially chosen by $\mathcal{A}$ as well).

Security notions for encryption schemes are obtained by combining an adversarial goal with an attack model, which is essentially the definition of an oracle that $\mathcal{A}$ is given access to. In this chapter, we consider the following attack models:

*   **Chosen-Plaintext Attack (CPA):** $\mathcal{A}$ is given nothing more than pk.

*   **Validating-Checking Attack (VCA):** $\mathcal{A}$ is given access to a validity-checking oracle, indicating if a given ciphertext c is a valid or not (i.e. returning the bit $\text{Decrypt}(sk, c) \stackrel{?}{=} \perp$). Note that this is different from the notion of Plaintext-Checking Attack (PCA) [Poi05].

*   **Chosen-Ciphertext Attack (CCA):** $\mathcal{A}$ has access to a decryption oracle.
<figure><img src="image_29.png" /><figcaption>Figure 12.1: Public-key encryption security hierarchy.</figcaption></figure>

We denote security notions positively: e.g. OW-VCA[$\mathcal{P}$] is the problem of contradicting the one-wayness of scheme $\mathcal{P}$ under validity-checking attack. This convention permits the easy description of hierarchies between security notions using reductions, as illustrated in Figure 12.1. When oracle access is permitted (i.e. either for VCA or CCA), we denote by $\ell$-GOAL-ATTACK[$\mathcal{P}$] the problem of contradicting GOAL $\in \{\text{UBK}, \text{OW}, \text{IND}, \text{NM}\}$ in less than $\ell$ oracle queries under an ATTACK $\in \{\text{VCA}, \text{CCA}\}$.

### 12.2.3 RSA security

**Single-user RSA security.** RSA encryption as originally described by Rivest, Shamir and Adleman [RSA78] (also known as “textbook RSA encryption”) is UBK-CPA-secure assuming the hardness of factoring. Contradicting the OW-CPA security of textbook RSA is known as the *RSA problem* and is believed to be intractable. In fact, no better attack is known on the RSA problem than on factoring.

The validity of a textbook RSA ciphertext can be checked publicly, so in the case of textbook RSA, VCA and CPA are equivalent adversarial models. In particular, the scheme is OW-VCA-secure under the hardness of the RSA problem as well.

Since textbook RSA encryption is deterministic, on the other hand, it cannot be semantically secure: given the encryption $c$ of either $m_0$ or $m_1$, the adversary simply computes $c_0 = m_0^e \bmod N$ and checks whether $c_0 = c$.

Many variants of this basic scheme have been proposed in order to achieve better security properties (especially semantic security) through the use of randomized padding schemes. PKCS#1 v1.5 is an early example of such a randomized padding, and this chapter is devoted to studying its security under the various security notions mentioned above.

**Multi-user RSA security.** The previous definitions do not capture security in a multicast context. In the early 1990s, attacks against low-exponent RSA highlighted the danger of multi-user security threats left uncaptured by single-user models. In independent works, Baudron, Pointcheval and Stern [BPS00] and Bellare, Boldyreva and Micali [BBM00]
proved that for strong security notions (namely IND or NM), schemes with reductionist security in the multi-user setting are exactly those permitting security proofs in the single-user setting. However, encryption one-wayness (OW) in a multi-user setting is not guaranteed by single-user one-wayness.

For textbook RSA encryption, if a common public exponent $e$ is used, then $e$ encryptions of a given message $m$ under different public keys $N_1, \dots, N_e$ lead to an easy plaintext recovery (indeed, applying the Chinese Remainder Theorem reveals $m^e \bmod N_1 N_2 \cdots N_e$, but this value is just $m^e$ in $\mathbb{Z}$): see [Bon99, §4.2]. Again, several countermeasures have been proposed (e.g. padding the message with random bits) but with an unclear security guarantees. The second part of this chapter explores broadcast attacks on PKCS#1 v1.5.

## 12.3 PKCS#1 v1.5 Encryption

### 12.3.1 The PKCS#1 v1.5 encoding function

PKCS#1 v1.5 describes a particular padding scheme for RSA encryption. Consider an RSA modulus $N$, and let $k$ denote its byte-length (i.e. $2^{8(k-1)} < N < 2^{8k}$). Let $m$ be an $|m|$-byte message with $|m| < k - 11$. A PKCS#1 v1.5 padding $\mu(m)$ of $m$ is obtained as follows. A random nonce $r$ consisting in $k - 3 - |m| \ge 8$ nonzero bytes is first generated uniformly at random. Then, $\mu(m) = \mu(m, r)$ is the integer converted from the octet-string:

$$ \mu(m, r) = 0002_{16} \parallel r \parallel 00_{16} \parallel m. \qquad (12.1) $$

The leading 00 byte guarantees that the encryption block is an integer smaller than $N$.

The encryption of a message $m$ of $|m| < k - 11$ bytes is then computed as:

$$ c = \mu(m, r)^e \bmod N $$

where $r$ is the random nonce chosen as above.

To decrypt $c \in \mathbb{Z}_N^*$, compute $c^d \bmod N$, convert the result to a $k$-byte octet-string and parse it according to equation (12.1). If the string cannot be parsed correctly or if $r$ is shorter than 8 octets, the decryption algorithm Decrypt outputs $\perp$; otherwise, Decrypt outputs the plaintext $m$.

### 12.3.2 Previous attacks on PKCS#1 v1.5

In 1998, Bleichenbacher [Ble98] published an attack on PKCS#1 v1.5 capable of recovering arbitrary plaintexts from a large number $\ell$ of ciphertexts validation queries. This attack established that PKCS#1 v1.5 is not $\ell$-GOAL-ATTACK for a large$^1 \ell$, GOAL $\in \{\text{OW, IND, NM}\}$ and ATTACK $\in \{\text{VCA, CCA}\}$ (see Appendix 12.2.2 for definitions of these security notions).

In 2000, Coron, Naccache, Joye and Paillier [CJNP00] introduced two new CPAs on PKCS#1 v1.5. The first attack can be considered as a IND-CPA when $e$ is small (for

<footnote>$^{1}$3 · $10^5 < \ell < 2 \cdot 10^6$ for $512 < \log_2 N < 1024$.</footnote>
<figure><img src="image_30.png" /><figcaption>Figure 12.2: PKCS#1 v1.5 security.</figcaption></figure>

plaintext ending by sufficiently many zeros). The second attack applies to arbitrary $e$, provided that $|m|$ is large and most message bits are zeros. Thus PKCS#1 v1.5 is not GOAL-CPA for a small $e$ or a large $|m|$, for $GOAL \in \{IND, NM\}$.

The previous crytanalytic results are summarized in Figure 12.2. In the rest of the chapter, we will study the remaining security notions and prove that PKCS#1 v1.5 is:

* OW-CPA assuming the intractability of the RSA problem (§12.4);

* not OW-CCA for $\ell = 2$ (§12.4);

* not NM-CPA (§12.5.1);

* not IND-VCA for $\ell = 1$ (§12.5.2);

* not OW-CPA in a multi-user setting (§12.6).

## 12.4 On the OW-CPA-Security of PKCS#1 v1.5

In this paragraph, we prove the following result:

**Proposition 12.1.** The OW-CPA security of PKCS#1 v1.5 is equivalent to the RSA problem.

In [CJNP02, Lemma 2], Coron, Joye, Naccache and Paillier proved that for suitable parameters, the existence of an algorithm that on input $y \in \mathbb{Z}_N^*$ outputs the $k_1$ least significant bits of $y^d \bmod N$ is equivalent to the existence of an RSA inverter. Following their approach, we prove the following lemma.

**Lemma 12.1.** Let $\mathcal{A}$ be a OW-CPA-adversary against PKCS#1 v1.5 with success probability $\epsilon$ within time $\tau$, with uniformly distributed messages of (maximum) length
k − 11. There exists an algorithm $\mathcal{A}'$ that solves the RSA problem with success probability $\varepsilon'$ within time $\tau'$, where:

$$
\begin{cases}
\varepsilon' \ge \eta^2 \cdot \varepsilon^2 - 2^{-k}\varepsilon \\
\tau' \le 2 \cdot \tau + \text{poly}(k)
\end{cases}
$$

where $\eta$ is a constant independent of $k$ and $\eta \ge 5 \cdot 10^{-8}$.

Proof. Let $\mathcal{A}$ be a OW-CPA-adversary against PKCS#1 v1.5 with success probability $\varepsilon$ within time $\tau$. We construct an algorithm $\mathcal{A}'$ that on input $y \in \mathbb{Z}_N^*$ outputs $y^d$ with success probability $\varepsilon'$ within time $\tau'$:

1. $\mathcal{A}'$ picks $\alpha \in \mathbb{Z}_N^*$ uniformly at random;

2. $\mathcal{A}'$ sets $y_0 = y$ and $y_1 = y \cdot \alpha^e$

3. Let us denote, for $i \in \{0, 1\}$:

$$
y_i^d = \omega_i \cdot 2^\beta + m_i
$$

with $\beta = 8(k - 11)$. $y_i$ is a valid PKCS#1 v1.5 ciphertext if $\omega_i = 0002 \parallel r_i \parallel 00$ where $r_i$ is a 8-(nonzero)-octet string. This happens with probability $\eta \ge (255/256)^8 \cdot 2^{-24}$. If this happens, then with probability $\varepsilon$, $\mathcal{A}$ will return $m_i$ on input $y_i$ (for $i \in \{0, 1\}$).

4. Therefore with probability at least $(\eta\varepsilon)^2$, we obtain:

$$
\alpha(\omega_0 \cdot 2^\beta + m_0) = \omega_1 2^\beta + m_1 \mod N.
$$

Letting $c_1 = 2^{-\beta}(\alpha m_0 - m_1) \bmod N$, we get the equation in $(\omega_0, \omega_1)$:

$$
\omega_1 - \alpha \cdot \omega_0 = c_1 \bmod N. \tag{12.2}
$$

From [CJNP02, Lemma 3], there exists an algorithm that given this system will output a solution $(\omega_0, \omega_1)$ (should such a solution exist) with probability at least $1 - 2^{-k}$ on the choice of $\alpha$. $\square$

Using the same technique, this can be extended to messages of different length, with
a possibly higher constant loss in the reduction.

As a byproduct of the previous proof one immediately gets that:

**Proposition 12.2.** *PKCS#1 v1.5 is not 2-OW-CCA.*

Proof. Thanks to the homomorphic properties of RSA, an adversary can mask the challenge ciphertext $c$ as $c' = cr^e$ for some random $r$ and with two decryption oracle queries, compute the $e$-th root $x'$ of $c'$ as in the previous proof. Then $x = x'/r$ is the $e$-th root of $c$ from which, the adversary retrieves readily the plaintext. $\square$
## 12.5 PKCS#1 v1.5 Malleability and Indistinguishability

We now show in this section that PKCS#1 v1.5 is neither NM-CPA-secure nor IND-VCA-secure. The general idea is the following. Let $m$ be some message to be encrypted, and $\mu(m)$ a corresponding PKCS#1 v1.5 padded encryption block. If $m$ has $Z > 2$ trailing zero bits, then $\mu(m)$ is divisible by $2^Z$, and $\mu(m) - \mu(m)/2^Z \mod N$ has a good probability of still being a valid encryption block. This is not usually the case when the $Z$ least significant bits of $m$ are not all zero.

Let $c = \mu(m)^e \mod N$ be a ciphertext of some message $m$. If $m$ has $Z > 2$ trailing zeros, $c' = c \cdot (1 - 2^{-Z})^e \mod N$ will often be a valid ciphertext of some other message $m'$ which can be related to $m$: this contradicts non-malleability under chosen plaintext attack. Moreover, if one is granted a single query to a validity oracle, it is possible to distinguish ciphertexts of plaintexts with trailing zeros and ciphertexts from plaintexts whose least significant bits are not all zero: this contradicts indistinguishability under validity checking attack. Note that if $i$ queries are allowed, the distinguishing success odds can quickly approach 1 by iterating the test with $c'_i = c \cdot (i - 2^{-Z})^e \mod N$ for $i = 1, 2, \dots$.

We develop this idea in further details below.

### 12.5.1 On the NM-CPA-security of PKCS#1 v1.5

Let $k$ be the byte-size of $N$, $Z = 4k$, and $M$ a positive integer such that $M + Z + 1$ is a multiple of 8 and $(M + Z + 1)/8 < k - 11$. We consider messages of the following form:

$$m = \underbrace{\bar{m}}_{M \text{ bits}} \|1_2\| \underbrace{0 \cdots 0_2}_{Z \text{ zero bits}}.$$

Let $\mathcal{M}$ denote the uniform distribution over messages of this form. Furthermore, we define a relation $\mathcal{R}$ over messages of length $l = M + Z + 1$ as follows: for any $l$-bit two messages $m_1, m_2$ (not necessarily of the previous form), $\mathcal{R}(m_1, m_2)$ holds if and only if the $M$ most significant bits of $m_1$ and $m_2$ coincide. In particular, for any given message $m_2$, there is exactly one $m_1 \in \mathcal{M}$ such that $\mathcal{R}(m_1, m_2)$.

Now, consider $m \leftarrow \mathcal{M}$. We can write $\mu(m) \cdot (1 - 2^{-Z})$ as:

$$\begin{array}{c} 0002_{16} \| r \| 00_{16} \| \bar{m} \| 1_2 \quad 0 \cdots 0_2 \\ - \quad 0002_{16} \| r \| 00_{16} \| \bar{m} \| 1_2 \\ = \quad 0002_{16} \| r \| 00_{16} \| \bar{m} \| 0_2 \quad \text{some digits} \cdots \text{some digits} \end{array}$$

Hence, $\mu(m) \cdot (1 - 2^{-Z}) = \mu(m')$ for some message $m' \neq m$ such that $\mathcal{R}(m, m')$.

Consider, the NM-CPA adversary $\mathcal{A}$ which outputs sampling algorithm $\mathcal{M}$ in the setup stage, and transforms a challenge ciphertext $c$ into $c' = c \cdot (1 - 2^{-Z})^e \mod N$. $\mathcal{A}$'s advantage is:

$$\mathrm{Adv}_{\mathcal{A}}^{\mathrm{NM-CPA}} = \Pr[\mathcal{R}(m, m')] - \Pr[m_0 \stackrel{\$}{\leftarrow} \mathcal{M}; \mathcal{R}(m_0, m')] = 1 - 2^{-M} \ge 1/2$$

which is non-negligible. Therefore, PKCS#1 v1.5 encryption is not NM-CPA-secure.
Note that the advantage of $\mathcal{A}$ is, in fact, very close to 1. For a 1024-bit modulus and a 128-bit random nonce, we have $M = 383$, making it exceedingly unlikely that $\mathcal{A}$ will ever fail.

### 12.5.2 On the IND-VCA-security of PKCS#1 v1.5

We now show how to contradict ciphertext indistinguishability under validity checking attack using a single oracle query. There are two natural types of validity-checking oracles: one which determines whether a given query is a valid ciphertext associated to a plaintext of any length, and the other which also checks message length. We can always contradict IND-VCA-security in the non-length-checking case (which is the one considered in Bleichenbacher's attack [Ble98]) with a single oracle query. Furthermore, if the byte-length of the randomizer is constant, as permitted by the PKCS#1 v1.5 standard, it is also possible to break IND-VCA-security with a single query to a length-checking oracle. Both attacks stem from the following result.

**Proposition 12.3.** Let $c = \mu(m)^e \bmod N$ be the ciphertext associated to some byte-string message $m$, $\omega$ the byte-length of the random nonce and $c' = c \cdot (1 - 2^{-4})^e \bmod N$.

1. If the least significant nibble<fnref n="2" /> of $m$ is not $0_{16}$, then $c'$ is never a valid ciphertext.

2. If $m$ is a message consisting of a string of $00_{16}$ bytes, then $c'$ is a valid ciphertext with probability at least 0.47. $c'$ is a valid ciphertext corresponding to a message of the same length as $m$ with probability at least:

$$ \frac{64}{1445} \left( \frac{239}{255} \right)^{\omega-1}. $$

*Proof.* Starting with the first assertion, consider a message $m$ such that $c'$ is a valid ciphertext. This implies that $\mu(m) - \mu(m) \cdot 2^{-4} \bmod N$ is a valid encoding string that, in particular, begins with the same $0002_{16}$ pattern as $\mu(m)$.

If, for an integer $x$, we denote by $\bar{x}$ the only integer in $(-N/2, N/2)$ such that $x \equiv \bar{x} \bmod N$, it follows that:

$$ |\mu(m) \cdot 2^{-4} \bmod N| < 2^{8k-16}. $$

Consider the set $S$ of residue classes $x \bmod N$ such that $|\bar{x}| < 2^{8k-16}$. Clearly, $\#S = 2^{8k-15} - 1$. On the other hand, let $T^+$ be the set consisting of $k$-byte strings of the form $000_{16} \parallel u \parallel 0_{16}$, and $T$ be the union of $T^+$ and $-T^+$ (where opposites are taken mod $N$). We also have $\#T = 2^{8k-15} - 1$ and $T$ maps into $S$ under multiplication by $2^{-4} \bmod N$. Since multiplication by $2^{-4}$ is a permutation of $\mathbb{Z}_N$, we infer that $(y \cdot 2^{-4} \bmod N) \in S$ if and only if $y \in T$.

In particular, if $c'$ is a valid ciphertext, we get $\mu(m) \in T$. By inspection of its top bits, we see that $\mu(m)$ cannot be in $-T^+$, so it has to be in $T^+$. Its least-significant nibble must thus be $0_{16}$ as required.

<footnote n="2">²Recall that a nibble is a sequence of four bits, or equivalently a hexadecimal digit.</footnote>
Turning now to the second assertion, let $m$ be the zero-message of some fixed byte-length. Write the encryption block $\mu(m)$ as follows:

$$ \mu(m) = 0002_{16} \parallel r_{2\omega-1} \parallel r_{2\omega-2} \parallel \cdots \parallel r_1 \parallel r_0 \parallel 00_{16} \parallel 00\cdots00_{16} $$

where $r_0, \dots, r_{2\omega-1}$ are the nibbles of the random nonce. Recall that the randomizer bytes $r_{2j} \parallel r_{2j+1}$ are chosen uniformly and independently at random in the range $01_{16}, \dots, \text{FF}_{16}$.

Assuming that $r_{2\omega-1}$ is at least 4 (which happens with probability $(256-4 \times 16)/255 = 64/85$, and which we will henceforth assume), we can write $(1-2^{-4})\mu(m)$ as:

$$ \begin{array}{r@{\ }l} & 0002_{16} \parallel r_{2\omega-1} \parallel r_{2\omega-2} \parallel \cdots \parallel r_1 \parallel r_0 \parallel 00_{16} \parallel 00\cdots00_{16} \\ - & 0000_{16} \parallel 2_{16} \parallel r_{2\omega-1} \parallel \cdots \parallel r_2 \parallel r_1 \parallel r_0 \parallel 0_{16} \parallel 00\cdots00_{16} \\ = & 0002_{16} \parallel r'_{2\omega-1} \parallel r'_{2\omega-2} \parallel \cdots \parallel r'_1 \parallel r'_0 \parallel s \parallel 00\cdots00_{16} \end{array} $$

where $r'_j \equiv r_j - r_{j+1} - \kappa_j \mod 16$ for some carry bit $\kappa_j$.

Then, $\mu' = (1-2^{-4})\mu(m)$ is a valid encoding block if and only if the first 8 randomizer bytes, namely $r'_{2\omega+1-2j} \parallel r'_{2\omega-2j}$, $j = 1, \dots, 8$, are all nonzero. $\mu'$ is a valid encoding block for a message of the same length as $m$ (or for short, “strongly valid”) if and only if $s = 0$ and all the padding bytes $r'_{2j+1} \parallel r'_{2j}$, $j = 0, \dots, \omega-1$, are nonzero. We will find an explicit lower bound for the probability of these events.

Note first that a sufficient condition for $r'_{2j+1} \parallel r'_{2j}$ to be nonzero is that $r'_{2j+1} \neq 0$. This nibble is zero if and only if $r_{2j+2} \equiv r_{2j+1} - \kappa_{2j+1} \pmod{255}$. Now $r_{2j+2}$ is picked independently of $r_{2j+1}$, since they belong to different bytes; it is also independent of $\kappa_{2j+1}$, which only depends on lower order bytes. Consequently:

$$ \begin{align*} \Pr[r'_{2j+1} = 0] &= \sum_{\rho=0}^{15} \Pr[r_{2j+2} = \rho] \cdot \Pr[r_{2j+1} - \kappa_{2j+1} \equiv \rho \pmod{16}] \\ &\le \max_{\rho} \Pr[r_{2j+2} = \rho] = \frac{16}{255} \end{align*} $$

and this bound still holds conditionally to any assignment of the lower order nibbles $r'_{2i+1}$, $i < j$. Therefore:

$$ \begin{align*} \Pr[\mu' \text{ is valid}] &\ge \Pr[r_{2\omega-1} \ge 4 \land r'_{2\omega-3} \ne 0 \land r'_{2\omega-5} \ne 0 \land \cdots \land r'_{2\omega-15} \ne 0] \\ &\ge \frac{64}{85} \cdot \left(1 - \frac{16}{255}\right)^7 \ge 0.47. \end{align*} $$

Furthermore:

$$ \begin{align*} \Pr[\mu' \text{ is strongly valid}] &\ge \Pr[r_{2\omega-1} \ge 4 \land r'_{2\omega-3} \ne 0 \land \cdots \land r'_1 \ne 0 \land r_0 = 0] \\ &\ge \frac{64}{85} \cdot \left(1 - \frac{16}{255}\right)^{\omega-1} \cdot \frac{15}{255} = \frac{64}{1445} \cdot \left(\frac{239}{255}\right)^{\omega-1}. \end{align*} $$

The corresponding validity assertions for $c'$ follow immediately. $\square$
Consider the IND-VCA adversary $\mathcal{A}$ defined as follows. In the setup stage, $\mathcal{A}$ outputs two messages $m_0, m_1$ of equal length, with $m_1$ not zero-terminated (e.g. $00\cdots0001_{16}$) and $m_0$ consisting of $00_{16}$ bytes only. Then, upon receiving a challenge ciphertext $c = \mu(m_b)^e \bmod N$, $\mathcal{A}$ makes a single oracle query and outputs $b' = 0$ or $1$ according to whether $c' = c \cdot (1 - 2^{-4}) \bmod N$ is a valid ciphertext or not. Its advantage is then:

$$ \begin{aligned} \mathrm{Adv}_{\mathcal{A}^{\mathrm{IND-VCA}}} &= \Pr[b' = 0 | b = 0] - \Pr[b' = 1 | b = 0] = \Pr[b' = 0 | b = 0] - 0 \\ &\ge \begin{cases} 0.47 & \text{if the oracle doesn't check message length} \\ \frac{64}{1445} \cdot \left(\frac{239}{255}\right)^{\omega-1} & \text{otherwise} \end{cases} \end{aligned} $$

which is non-negligible. In the length-checking case, it is over 2.8% (resp. 1.6%) for 64-bit (resp. 128-bit) nonces.

In the non-length-checking case, we can obtain an even better advantage using $c' = c \cdot (1 - 2^{-8}) \bmod N$ (shifting by 8 bits instead of 4). The proof works similarly provided that $N$ satisfies $N > 2^{8k-7}$, which is not required by the PKCS#1 v1.5 standard but is usually verified in practice. This yields an advantage of at least:

$$ \frac{252}{255} \cdot \left( \frac{254}{255} \right)^7 > 0.96. $$

## 12.6 Broadcast Attack on PKCS#1 v1.5

We now examine the security of PKCS#1 v1.5 in a multiple users context.

In such a scenario, i.e. when broadcast encryption is performed, the sender wishes to transmit the same message $m$ to $\ell$ parties $P_1, \dots, P_\ell$. As each party has its own key $pk_i = (e, N_i)$ (with a common public exponent $e$), the sender encrypts $m$ using all the $pk_i$'s and sends the resulting ciphertexts $c_1, \dots, c_\ell$ to the corresponding recipients. It has long been known that textbook RSA encryption should not be used in such a context, since an attacker can easily recover the plaintext using the Chinese Remainder Theorem as long as $\ell \ge e$. Therefore, $m$ has to be padded before applying the RSA function, and the padding has to be different for each recipient.

In 1988, Håstad [Hås88] showed that using different deterministic linear paddings $\mu_i(m)$ for all parties is not enough to guarantee security. Indeed, when $e$ is small, $e$ ciphertexts are again sufficient to efficiently recover $m$ provided that the encoding functions $\mu_i$ are known to the attacker. To achieve this result, Håstad expressed the attack in terms of finding small roots of a univariate modular polynomial, which he accomplishes using Coppersmith's techniques [Cop97].

Håstad's attack does not apply to PKCS#1 v1.5, since the padding used for a given recipient is random, and is thus unknown to an attacker. The following sections will overcome this difficulty. Our main result is as follows.

**Proposition 12.4.** Let $c_1, \dots, c_\ell$ be $\ell$ PKCS#1 v1.5 ciphertexts of the same message $m$, of byte length $|m|$. Each $c_i$ is encrypted for a recipient having $pk_i = (e, N_i)$. All $N_i$ are
k-byte long. Then there exists a heuristic algorithm which, given $c_1, \dots, c_\ell$, outputs $m$, provided that the following condition is satisfied:

$$ \ell > \frac{e|m|}{k - e(k - |m| - 3)} > 0. $$

Its complexity is polynomial in $e, |m|$ and $k$ but exponential in the number $\ell$ of recipients.

We describe this algorithm in the coming sections. The core idea is to reduce the problem to finding small modular roots of a multivariate polynomial equation, which can be achieved using a standard generalization of Coppersmith's techniques. As usual, this generalization relies on an assumption of algebraic independence between polynomials, which makes the algorithm heuristic.

### 12.6.1 The multivariate polynomial of broadcast PKCS#1 v1.5

Recall from §12.3.1 that to encrypt message $m$ for recipient $P_i$, a PKCS#1 v1.5 sender first generates an $|r_i|$-byte randomizer $r_i$, and then computes the encoding function:

$$ \mu(m, r_i) = 0002_{16} \parallel r_i \parallel 00_{16} \parallel m. $$

Numerically, this gives:

$$ \mu(m, r_i) = m + 2^{8|m|+8}r_i + 2^{8|m|+8|r_i|+9}. $$

The ciphertext $c_i$ is then computed as $c_i = \mu(m, r_i)^e \bmod N_i$.

Consider then an adversary $\mathcal{A}$ who obtains $c_1, \dots, c_\ell$. Since the $N_i$ are of the same size, the random nonces $r_i$ have a common byte length $|r|$. Therefore, the ciphertexts collected by $\mathcal{A}$ can be written as:

$$ c_1 = (m + Ar_1 + B)^e \bmod N_1, \dots, c_\ell = (m + Ar_\ell + B)^e \bmod N_\ell $$

where $A = 2^{8|m|+8}$ and $B = 2^{8|m|+8|r|+9}$. Obviously, the $N_i$ are pairwise co-prime (otherwise, the factorization of some of the $N_i$ could easily be recovered). Thus, the Chinese Remainder Theorem ensures that the previous equations can be rewritten as a single congruence mod $N = N_1 \cdots N_\ell$:

$$ u_1c_1 + \cdots + u_\ell c_\ell = u_1(m + Ar_1 + B)^e + \cdots + u_\ell(m + Ar_\ell + B)^e \bmod N $$

where the constants $u_1, \dots, u_\ell$ are given by the extended Euclidean algorithm. It follows that the tuple $(m, r_1, \dots, r_\ell)$ is a root of the multivariate modular polynomial:

$$ f(x, y_1, \dots, y_\ell) = u_1(x + Ay_1 + B)^e + \dots + u_\ell(x + Ay_\ell + B)^e - C \bmod N \quad (12.3) $$

where $C = u_1c_1 + \cdots + u_\ell c_\ell$. This root is small in the sense that all of its components are bounded by quantities that are small compared to $N$: $m$ is smaller than $2^{8|m|}$ and each $r_i$ is bounded by $2^{8|r|}$. Under suitable conditions on $|m|$ and $|r|$ which will be detailed
below, it will thus become feasible to recover this root, and hence $m$, in polynomial time using Coppersmith's techniques.

In particular, we show in §12.6.3 that the lattice construction of Jochemsz and May [JM06] yields a heuristic polynomial time algorithm for recovering the small root of $f$ under the following condition:

$$ \ell|r| + |m| < \frac{t(\nu)}{s(\nu)} \cdot \ell k $$

where $\nu$ is a parameter which determines the complexity of the attack, and $s(\nu)$, $t(\nu)$ are defined as:

$$ s(\nu) = \sum_{i=0}^{e\nu} i \binom{e\nu - i + \ell}{\ell} = \binom{\ell + e\nu - 1}{\ell} \frac{(\ell + e\nu)(1 + \ell + e\nu)}{2 + 3\ell + \ell^2} $$

and

$$ t(\nu) = \sum_{i=1}^{\nu} \binom{e\nu - ie + \ell + 1}{\ell + 1}. $$

We also prove in the same section that $t(\nu)/s(\nu) \to 1/e$ as $\nu$ tends to $+\infty$, so that the best achievable bound on $|m|$ and $|r|$ for which the attack applies is:

$$ \ell|r| + |m| < \frac{\ell k}{e}. $$

Since $|r| = k - |m| - 3$ in PKCS#1 v1.5 we obtain the bound announced in Proposition 12.4. As usual when using Coppersmith's techniques, the complexity of the attack is polynomial in the dimension of the constructed lattice and in the size of the entries.

Given the heuristic nature of multivariate Coppersmith-like techniques, we also implement the attack and report practical experiment results in §12.6.4.

### 12.6.2 Finding small modular roots of a multivariate polynomial

The problem of solving modular polynomial equations is believed to be difficult in the general case. Nevertheless, when we restrict the problem to finding small roots only, the problem becomes easier to solve. Indeed, in 1996, Coppersmith [Cop96] introduced a technique, based on lattice reduction, allowing to recover the root of a univariate modular polynomial provided that this root is small enough. This construction was reformulated in simpler terms by Howgrave-Graham [HG97] and its extensions to more variables found numerous cryptanalytic applications.

**Coppersmith's technique.** Starting from a polynomial $f$ modulo a known composite integer $N$, the idea behind Coppersmith's method is to construct a set of polynomials $h_1, \dots, h_n$ sharing the same sought root over the integers. If the number of these generated polynomials is sufficiently large (greater than the number of variables) and under the assumption that all resultant computations lead to non-zero results, then the root can easily be recovered. Note that this assumption makes the method heuristic.
A sufficient condition ensuring that the polynomials $h_1, \dots, h_n$ share a common root in $\mathbb{Z}$ was formulated by Howgrave-Graham.

**Lemma 12.2 (Howgrave-Graham [HG97]).** Let $h \in \mathbb{Z}[x_1, \dots, x_n]$ be an integer polynomial that consists of at most $\omega$ monomials. Suppose that

1. $h(x_{01}, \dots, x_{0n}) \equiv 0 \mod N$ for some $|x_{01}| < X_1, \dots, |x_{0n}| < X_n$.

2. $\|h(x_1 X_1, \dots, x_n X_n)\| < \frac{N}{\sqrt{\omega}}$.

Then $h(x_{01}, \dots, x_{0n}) = 0$ holds over the integers.

The problem can thus be reduced to finding polynomials $h_1, \dots, h_n$ of small norm having the same modular root as $f$. This can be achieved by representing polynomials as coefficient vectors (using a suitable ordering on monomials) and using lattice reduction techniques such as LLL [LLL82] to search for small vectors in a lattice spanned by polynomials which are known to have the sought modular root.

If $L$ is a lattice of polynomials consisting of at most $\omega$ monomials and all having the same modular root as $f$, then the condition

$$2^{\frac{\omega(\omega-1)}{4(\omega+1-n)}} \det(L)^{\frac{1}{(\omega+1-n)}} < \frac{N}{\sqrt{\omega}} \quad (12.4)$$

ensures first $n$ polynomials obtained by applying LLL to the lattice $L$ match Howgrave-Graham's bound. In the analysis, we let terms that do not depend on $N$ contribute to an error term $\epsilon$, and simply use the determinant condition $\det(L) \le N^{w+1-n}$.

**Lattice construction.** A variety of methods for constructing the lattice $L$ have been proposed in the literature. In what follows, we choose to rely on the technique introduced by Jochemsz and May in [JM06].

Recall that we have a polynomial $f$ with an unknown root $x_0 = (x_{01}, \dots, x_{0n})$ modulo some composite integer $N$ whose factorization is unknown. This root is small in the sense that each of its components is bounded: $|x_{0i}| < X_i$ for $i \in \{1, \dots, n\}$. We denote by $\lambda$ the leading monomial of the polynomial $f$ and by $M(f)$ the set of monomials appearing in $f$. Of course, $\lambda$ can be assumed to be monic as otherwise one simply has to multiply $f$ by the modular inverse of its initial coefficient.

Given $\epsilon > 0$, we fix an integer $\nu = \nu(\epsilon)$ and without loss of generality we assume that $M(f^j) \subseteq M(f^\nu)$ for $j \in \{1, \dots, \nu-1\}$. If $k$ is an integer between 0 and $\nu+1$, we define the set $M_k$ as $M(f^\nu) \cap \lambda^k M(f^{\nu-k})$ (in particular $M_0 = M(f^\nu)$ and $M_{\nu+1} = \emptyset$). Next, we define the following shift polynomials:

$$g_{i_1 \dots i_n}(x_1, \dots, x_n) = \frac{x_1^{i_1} \dots x_n^{i_n}}{\lambda^k} f^k N^{\nu-k}$$

for $k \in \{0, \dots, \nu\}$ and $x_1^{i_1} \dots x_n^{i_n} \in M_k \setminus M_{k+1}$. By definition, all polynomials $g$ have the root $(x_{01}, \dots, x_{0n})$ modulo $N^\nu$. We can now define $L$ as the lattice generated by the
coefficient vectors of all polynomials $g_{i_1...i_n}(x_1X_1, ..., x_nX_n)$. If the monomial ordering has been chosen correctly, the matrix corresponding to that lattice is lower triangular and the determinant becomes easy to compute. Indeed, the diagonal elements are those corresponding to the monomial $\lambda^k$ in $f^k$ for each row. Therefore, the diagonal terms of the matrix are $X_1^{i_1}...X_n^{i_n}N^{\nu-k}$ for $k \in \{0, ..., \nu\}$ and $x_1^{i_1}...x_n^{i_n} \in M_k \setminus M_{k+1}$. By doing a simple computation and neglecting low order terms, one can finally reduce the condition (12.4) to the following new one:

$$ \prod_{j=1}^{n} X_j^{s_j} < N^{s_N} \quad \text{for} \quad \left\{ \begin{array}{l} s_j = \sum_{x_1^{i_1}...x_n^{i_n} \in M_0} i_j \quad (1 \le j \le n) \\ s_N = \sum_{k=1}^{\nu} |M_k|. \end{array} \right. \qquad (12.5) $$

This formula expresses an asymptotic condition on the bounds $X_1, ..., X_n$ allowing to recover the root in polynomial time.

*Remark 12.1.* The method outlined above is what Jochemsz and May called the “basic strategy”; they also proposed an “extended strategy” in which we can use extra shifts of a certain variable and replace $M_k$ for instance by $M_k = \bigcup_{j=1}^{t} x_1^j (M(f^{\nu}) \cap \lambda^k M(f^{\nu-k}))$ for some well-chosen parameter $t$.

### 12.6.3 The Jochemsz-May lattice in broadcast PKCS#1 v1.5

Let us examine what the lattice $L$ looks like in the particular setting of broadcast PKCS#1 v1.5 encryption.

Recall from §12.6.1 that recovering $m$ from $c_1, ..., c_\ell$ reduces to finding the root $(x_0, y_{0,1}, ..., y_{0,\ell}) = (m, r_1, ..., r_\ell)$ of the following modular polynomial:

$$ f(x, y_1, ..., y_\ell) = u_1(x + Ay_1 + B)^e + \dots + u_\ell(x + Ay_\ell + B)^e - C \quad \text{mod } N. $$

We know that this root satisfies the bounds $|x_0| < X$ and $|y_{0i}| < Y$ for all $i \in \{1, ..., \ell\}$ with $X = 2^{8|m|}$ and $Y = 2^{8|r|}$. We examine how the Jochemsz-May bounds described in the previous section translate into bounds on $|m|$ and $|r|$ allowing the message to be recovered in polynomial time.

**Form of the sets $M_k$.** The analysis' first step consists in describing the sets $M_k$. Note first that the set of monomials $M(f)$ is included in $\{x^a y_1^{b_1} \cdots y_\ell^{b_\ell} \mid a+b_1+\cdots+b_\ell \le e\}$. In other words, the geometrical shape of the polynomial $f$ is included in a “pyramid” of dimension $\ell+1$ of monomials with total degree less than $e$. We choose the deglex monomial order, according to which the leading monomial of $f$ is $x^e$. The sets $M_k$ can then be described as follows:

$$ M_0 = \{x^a y_1^{b_1} \cdots y_\ell^{b_\ell} \mid a+b_1+\cdots+b_\ell \le e\} $$

$$ M_1 = \{x^a y_1^{b_1} \cdots y_\ell^{b_\ell} \mid a+b_1+\cdots+b_\ell \le e\} $$

...

$M_\nu = \{x^a y_1^{b_1} \cdots y_\ell^{b_\ell} \mid a+b_1+\cdots+b_\ell \le e\}$

$$ M_\nu = \{x^a y_1^{b_1} \cdots y_\ell^{b_\ell} \mid a+b_1+\cdots+b_\ell \le e\} $$

which makes it easy to count the number of monomials in each of them.
**Condition on the bounds.** Given the above description, we can evaluate the quantities $s_j$ and $s_N$ of equation (12.5) as follows. First, by symmetry, $s_i, s_{j_1}, \dots, s_{j_\ell}$ are all equal to:

$$s(\nu) = \sum_{i=0}^{\nu} \frac{i(e\nu - i + 1)(e\nu - i + 2) \cdots (e\nu - i + \ell)}{\ell!}.$$

Furthermore, we have:

$$s_N = t(\nu) = \sum_{i=1}^{\nu} \frac{(e\nu - ie + 1)(e\nu - ie + 2) \cdots (e\nu - ie + \ell + 1)}{(\ell + 1)!}.$$

Condition (12.5) can then be rewritten as $X^{s(\nu)}Y^{\ell s(\nu)} < N^{t(\nu)}$, and since $N$ is of byte size $\ell k$, this gives:

$$\ell|r| + |m| < \frac{t(\nu)}{s(\nu)} \cdot \ell k.$$

**Asymptotic bound.** The functions $s(\nu)$ and $t(\nu)$ are polynomials in $\nu$. Hence, it suffices to evaluate their leading coefficients to obtain an asymptotic estimate as $\nu \to +\infty$. Note further that $s(\nu)$ and $t(\nu)$ are easily expressed in terms of the antidifference operator, which takes a polynomial $P(X)$ to the polynomial $\sigma(P)(X)$ defined by $\sigma(P)(j) = \sum_{i=1}^j P(i)$ for $j \in \mathbb{N}$. Indeed:

$$s(\nu) = \sum_{i=0}^{\nu} (e\nu - i)P(i) = e\nu \cdot \sigma(P)(e\nu) - \sigma(XP)(e\nu) + e\nu$$

with $P(X) = \frac{(X+1)\cdots(X+\ell)}{\ell!}$;

$$t(\nu) = \sum_{i=1}^{\nu} Q(i) = \sigma(Q)(\nu)$$

with $Q(X) = \frac{(eX - e + 1)\cdots(eX - e + \ell + 1)}{(\ell + 1)!}.$

Now it is easily seen that if the leading coefficient of $P$ is $c_d X^d$, the leading coefficient of $\sigma(P)$ is $c_d X^{d+1}/(d+1)$. It follows that, as $\nu \to +\infty$, we have:

$$s(\nu) \sim e\nu \cdot \frac{(e\nu)^{\ell+1}}{\ell!(\ell+1)} - \frac{(e\nu)^{\ell+2}}{\ell!(\ell+2)} = \frac{(e\nu)^{\ell+2}}{(\ell+2)!} \quad \text{and} \quad t(\nu) \sim \frac{e^{\ell+1}\nu^{\ell+2}}{(\ell+2)!}.$$

In particular, $t(\nu)/s(\nu) \to 1/e$ when $\nu \to +\infty$. Thus, the best asymptotic bound on $|m|$ and $|r|$ for which the attack is theoretically possible is:

$$\ell|r| + |m| < \frac{\ell k}{e}.$$
### 12.6.4 Experimental results on the broadcast attack

Given the heuristic nature of Coppersmith's techniques in the multivariate case, it is important to assess the practicality of our attack. In particular, one can ask how many ciphertexts an attacker really needs to recover $m$. In the particular instance $\{\log_2 N = 1024, e = 3\}$, the number of required ciphertexts is, in principle, really low.

**Corollary 12.1.** If a PKCS#1 v1.5 user encrypts the same message $m$ with 64-bit random nonces to multiple recipients using 1024-bit moduli and $e = 3$, then there exists a heuristic polynomial time algorithm that recovers $m$ from $\ell = 4$ ciphertexts.

*Proof.* This is a direct consequence of Proposition 12.4, given that, for 1024-bit moduli and 64-bit nonces, message size is equal to 936 bits. $\square$

These parameters, corresponding to optimal message size and encryption speed for 1024-bit moduli, are rather realistic and commonly implemented (although it is much more common to encrypt short messages such as AES symmetric keys than messages of maximal size). However, we will see that the dimension of the lattice that should be reduced to recover $m$ with these parameters can hardly be called practical.

**Partial information.** Consider an attacker who does not collect all the $\ell$ required ciphertexts. In that specific case, even if $m$ can not be fully recovered, the attacker can nevertheless obtain partial information on $m$. In particular, in a scenario where $m$ would not be of full size and would have been previously padded with zero bits, the attack can still be performed.

**Practical implementations.** To check the applicability of the attack, we investigated three configurations: An attacker having access to two, three and four ciphertexts. Before implementing the attack in each scenario, we first evaluated the dimension of the corresponding lattices (for reasonably small values of the parameter $\nu$) and then expressed the number of bits on $m$ that should be recovered in practice. The results obtained for 1024-bit moduli and $e = 3$ are shown in Table 12.1.

As we can see, the number of bits of $m$ that we are able to recover increases with $\nu$, and approaches 936 bits for $(\ell, \nu) = (4, 10)$. Unfortunately, the dimensions of the constructed lattices are often quite impractical. In many cases, matrix size turns out to exceed 1000, making lattice reduction unfeasible in practice. As a result, and because we had limited processor time at our disposal, we only ran practical experiments in the small cases, namely $\ell = 2$ and $\nu = 2, 3$.

Experiments have been performed on a 7-processor Intel Xeon clocked at 1.86 GHz. Each test was done in the same way: construction of the appropriate lattice, LLL-reduction and then extraction of short vectors. Although theoretically one only needs a number of short vectors equal to the number of variables, in practice we decided to take as many vectors as possible to increase the success odds of the attack. Most of the CPU time was claimed by the LLL-reduction step (approximately 3 hours for $(\ell, \nu) = (2, 3)$). With
<table><caption>Table 12.1: Dimension of the lattice L and number of recoverable bits for different values of $(\ell, \nu)$.</caption><thead><tr><th rowspan="2">ν</th><th colspan="2">ℓ = 2</th><th colspan="2">ℓ = 3</th><th colspan="2">ℓ = 4</th></tr><tr><th>dim(L)</th><th>|m|</th><th>dim(L)</th><th>|m|</th><th>dim(L)</th><th>|m|</th></tr></thead><tbody><tr><td>2</td><td>84</td><td>213</td><td>210</td><td>246</td><td>462</td><td>249</td></tr><tr><td>3</td><td>220</td><td>306</td><td>715</td><td>395</td><td>2002</td><td>451</td></tr><tr><td>4</td><td>455</td><td>359</td><td>1820</td><td>483</td><td>6188</td><td>578</td></tr><tr><td>5</td><td>816</td><td>394</td><td>3876</td><td>542</td><td>15504</td><td>664</td></tr><tr><td>6</td><td>1330</td><td>418</td><td>7315</td><td>584</td><td>33649</td><td>726</td></tr><tr><td>7</td><td>2024</td><td>435</td><td>12650</td><td>615</td><td>65780</td><td>773</td></tr><tr><td>10</td><td>5456</td><td>469</td><td>46376</td><td>675</td><td>324632</td><td>863</td></tr></tbody></table>

1024-bit moduli and 64-bit random nonces, we managed to recover a 115-bit message (padded with zeros).

**Toy example.** To better illustrate the process, we present here a toy example for 150-bit moduli and a 5-bit message $m$. After constructing the polynomial $f$ had and generating the lattice (of dimension 84 in this case), we performed the LLL-reduction. Here the first 50 vectors corresponded to polynomials having the desired root over the integers. We then took all these polynomials and computed a Gröbner basis of the ideal they generated. The results were the following:

$$N_i = 150 \text{ bits, } m = 5 \text{ bits, } r = 6 \text{ bits, } e = 3, \nu = 2$$
$$f(x, y, z) \text{ with modular root } (24, 58, 34).$$

$$ \left\{ \begin{aligned} p_1 &= z^4 + 512z^3 + 98304z^2 + 86093442y - 94710946z - 1908346880 \\ p_2 &= yz^2 - \frac{89}{81}z^3 + 256yz - \frac{7936}{27}z^2 + 16384y - \frac{573440}{27}z - \frac{33783328}{81} \\ p_3 &= y^2 - \frac{62}{27}yz + \frac{961}{729}z^2 - \frac{1024}{27}y + \frac{31744}{729}z + \frac{262144}{729} \\ p_4 &= x - 55297y + 63489z + 1048576. \end{aligned} \right. $$

The Gröbner basis computation does not allow us to directly recover the message $m$, since the corresponding subvariety is not of dimension zero, as was usually the case in most experiments. In fact, we commonly faced problems of algebraic dependence between the resulting polynomials (hence our choice to take a large number of polynomials, rather than the first few, to compute the Gröbner basis). Nevertheless, it was usually possible to recover the message, as the polynomials in the Gröbner basis had a very simple form. In this particular case, for instance, $p_4$ is affine and $p_3$ can be written as $(ay + bz + c)^2$, making it easy to recover the common root.

## 12.7 Conclusion

Figure 12.3 summarizes our current knowledge of the security of PKCS#1 v1.5.
<figure><img src="image_31.png" /><figcaption>Figure 12.3: Updated security status of PKCS#1 v1.5.</figcaption></figure>
<figure><img src="image_32.png" /></figure>
# Cryptanalysis of the RSA Subgroup Assumption

## 13.1 Introduction

This chapter is devoted to a different type of attack: a “better” exponential algorithm for factoring an RSA modulus of a special form.

At TCC 2005, Groth [Gro05] underlined the usefulness of working in small RSA subgroups of hidden order. In assessing the security of the relevant hard problems, however, the best attack considered for a subgroup of size $2^{2\ell}$ had a complexity of $O(2^{\ell})$. Accordingly, $\ell = 100$ bits was suggested as a concrete parameter.

In this chapter, we exhibit an attack with a complexity of roughly $2^{\ell/2}$ operations, suggesting that Groth’s original choice of parameters was overly aggressive. We also discuss the practicality of this new attack and various implementation issues. This work was presented at PKC 2011 [CJM+11].

### 13.1.1 Groth’s small RSA subgroups

In 2005, Groth [Gro05] proposed a collection of cryptographic primitives based on small RSA subgroups of $\mathbb{Z}_N^*$ of hidden orders. The motivation behind these constructions is improved efficiency and tighter security reductions.

The RSA moduli $N$ used by Groth are of the form:

$$N = p \cdot q = (2p'r + 1) \cdot (2q's + 1)$$

where $p, p', q, q'$ are prime integers and $r, s$ are random integers. Then there exists a unique subgroup $\mathbb{G}$ of $\mathbb{Z}_N^*$ of order $p'q'$. Letting $g$ be a random generator of $\mathbb{G}$, the pair $(N, g)$ is made public whereas everything else including the group order $p'q'$ is kept secret.

The best attack considered in [Gro05] has complexity $O(p')$. Therefore, when proposing concrete parameters, the author suggests to take the bit-lengths $\ell_{p'}$ and $\ell_{q'}$ of the primes $p'$ and $q'$ as $\ell_{p'} = \ell_{q'} = 100$.
### 13.1.2 Our results

We do not consider any specific scheme from [Gro05] in this chapter. Instead, we describe an attack that recovers the secret factors of $N$ from the public data $(N, g)$ in $\tilde{O}(\sqrt{p'})$, and hence breaks all the proposed schemes with the same complexity. This results in a $2^{50}$ attack making the choice $\ell_{p'} = \ell_{q'} = 100$ potentially insecure. We analyze the practicality of our attack with an implementation, for which we provide the source code in the Appendix.

*Remark 13.1.* In [Gro05], Groth also considers RSA subgroups where $r$ and $s$ are smooth integers (i.e. all prime factors of $r$ and $s$ are smaller than some bound $B$). For this specific variant an attack in complexity $O(\sqrt{p'})$ is given in [Gro05], and consequently larger parameters ($\ell_{p'} = \ell_{q'} = 160$) are suggested. In this chapter we do not consider this variant but directly focus on the general case.

*Remark 13.2.* Other works have proposed schemes based on small subgroups of $Z_{N}^{*}$. The attack introduced in this chapter applies to some, but not all of them. In particular, the scheme proposed by Damgård et al. in [DGK07] uses a subgroup of prime order $v$ of $Z_{N}^{*}$, where $v$ is a factor of both $p-1$ and $q-1$ (of around 160 bits). Since the group has the same order modulo $p$ and $q$, the attack presented herein does not apply to this scheme. On the other hand, it does, in principle, apply to the subgroup variant of the Paillier cryptosystem [PP99]. The parameter choice from the original paper was more conservative than that of Groth, however (320-bit subgroup), making it out of reach of our new attack.

## 13.2 The New Attack

Using the notations above, we factor $N$ in time $\tilde{O}(\sqrt{p'})$ and memory $O(\sqrt{p'})$ as follows. Recall that the RSA modulus $N = pq$ is such that:

$$N = p \cdot q = (2p'r + 1) \cdot (2q's + 1)$$

where $p'$ and $q'$ are prime; besides, $g$ is a generator of the subgroup $G$ of order $p'q'$. From $g^{p'q'} = 1 \mod N$ we get:

$$g^{p'} = 1 \mod p. \qquad (13.1)$$

Let $\ell$ denote the bit length of $p'$, which we assume is even without loss of generality, and write $\Delta = 2^{\ell/2}$. We then have

$$p' = a + \Delta \cdot b$$

with $0 \le a, b < 2^{\ell/2}$. From (13.1), we get:

$$g^a = (g^\Delta)^{-b} \mod p.$$

If the prime factor $p$ was known, one could carry out a baby-step giant-step attack by generating the following two lists:

$$L_p = \{g^i \mod p : 0 < i < 2^{\ell/2}\}$$

$$L'_{p} = \{(g^{\Delta})^{-j} \mod p : 0 \le j < 2^{\ell/2}\}$$
and finding a collision between $L_p$ and $L'_p$, which would reveal $a, b$ and thus $p'$ in total time and space $O(2^{\ell/2})$.

Obviously $p$ is unknown, so instead of computing $L_p$ and $L'_p$, we generate the two following lists modulo $N$:

$$L = \{x_i = g^i \mod N : 0 < i < 2^{\ell/2}\}$$
$$L' = \{y_j = (g^\Delta)^{-j} \mod N : 0 \le j < 2^{\ell/2}\}$$

One could then compute $\gcd(x_i - y_j, N)$ for all $x_i \in L$ and all $y_j \in L'$. Since we have

$$x_a - y_b = 0 \mod p$$

this would reveal the factors of $N$ for $i = a$ and $j = b$. However, the complexity of this naive approach is quadratic in $\Delta$, and will thus require $2^\ell$ computations, not $2^{\ell/2}$. Hence we proceed as follows instead:

1. Generate the polynomial:

$$f(x) = \prod_{x_i \in L} (x - x_i) \mod N$$

2. For all $y_j \in L'$, evaluate $f$ at $y_j$ and compute $\gcd(f(y_j), N)$.

Since we have

$$f(y_b) = \prod_{x_i \in L} (y_b - x_i) = (y_b - x_a) \cdot R = 0 \mod p$$

computing $\gcd(f(y_j), N)$ reveals the factors of $N$ for $j = b$.

The attack is summarized in Algorithm 13.1. In the next section we show that it can be carried out in time quasi-linear in the cardinalities of $L$ and $L'$.

## 13.3 Attack Complexity

This attack involves the computation and evaluation of a polynomial of the form:

$$f(x) = \prod_{i=1}^{d-1} (x - x_i) \mod N$$

with $d = 2^{\ell/2}$. It is a classical fact [Ber08] that the coefficients of such a polynomial can be computed using a product tree, with a total number of operations in $\mathbb{Z}_N$ which is quasilinear in $d$ (namely $O(M(d) \log d)$, where $M(d)$ is the complexity of the multiplication of two polynomials of degree $d$). Similarly, with a remainder tree, this polynomial can be evaluated at all points $y_j$, $0 \le j < d$ in $O(M(d) \log d)$ operations.

In our case, however, both $(x_i)$ and $(y_j)$ are geometric progressions, hence even more efficient algorithms exist: the Newton basis conversion algorithms of Bostan and Schost [BS05] make it possible to compute $f$ using $O(d)$ pre-computations and a single
**Algorithm 13.1 Attack overview.**

1: Let $\Delta \leftarrow 2^{\ell/2}$.

2: **for** $i = 0$ to $\Delta - 1$ **do**

3: &nbsp;&nbsp;&nbsp;&nbsp; $x_i \leftarrow g^i \bmod N$

4: &nbsp;&nbsp;&nbsp;&nbsp; $y_i \leftarrow (g^\Delta)^{-i} \bmod N$

5: **end for**

6: Generate the polynomial

$$f(x) \leftarrow \prod_{i=1}^{\Delta-1} (x - x_i) \bmod N$$

7: **for** $i = 0$ to $\Delta - 1$ **do**

8: &nbsp;&nbsp;&nbsp;&nbsp; Evaluate $f(y_i) \in \mathbb{Z}_N$

9: &nbsp;&nbsp;&nbsp;&nbsp; Attempt to factor $N$ by computing $\gcd(f(y_i), N)$.

10: **end for**

middle product [HQZ04] of polynomials of degree $d$, and to evaluate $f(y_j)$ for all $j$ using $O(d)$ pre-computations, a product of polynomials of degree $d$ and a middle product of polynomials of degree $d$. See the next section for details. This results in an overall complexity of $3M(d) + O(d)$ for the complete attack, with a small constant in the big-O. Space requirements are also $O(d)$, to store a few polynomials of degree $d$.

Thus, for typical parameter sizes, the attack is essentially linear in $\sqrt{p}$ both in time and space.

## 13.4 Algorithmic Details

As discussed above, we can break down the attack in two steps: first compute the coefficients of the polynomial $f(x) = \prod_{i=1}^{d-1}(x - x_i) \bmod N$, and then evaluate $f \bmod N$ at each of the points $y_j$. Since both $(x_i)$ and $(y_j)$ are geometric progressions, both of these steps reduce to a variant of the discrete Fourier transform, called the “chirp transform” (or its inverse) [RSR69, Blu70]. In our implementation, we carry out these computations using the particularly efficient algorithms of Bostan and Schost [BS05], as described in [Bos03, §5.5]. More precisely, Bostan gives pseudocode, reproduced as Algorithms 13.3 and 13.4 in Appendix 13.A, to compute polynomial interpolation and polynomial evaluation at a geometric progression.

In our case, a number of further simplifications are possible in the interpolation stage. Indeed, $f(x_i) = 0$ for $1 \le i \le d-1$ and $f(1) = \prod_{i=1}^{d-1}(1 - x_i)$, so with the notations of Algorithm 13.3, $v_0 = (-1)^{n-1}s_{n-1}$ and $v_i = 0$ for $i > 0$. This means in particular that the polynomial multiplication of Algorithm 13.3, Step 9 reduces to a simple scalar multiplication, and that the computations of Steps 10–12 can be carried out in the main loop. We can also have a slightly more conservative memory management, with only 4 polynomials of degree $n-1$ kept in memory for both the interpolation and the
<table><caption>Table 13.1: Experimental attack running times for 1024-bit moduli.</caption><thead><tr><th>ℓ = ⌈log<sub>2</sub> p'⌋</th><th>running time</th></tr></thead><tbody><tr><td>26 bits</td><td>1.9 seconds</td></tr><tr><td>28 bits</td><td>4.0 seconds</td></tr><tr><td>30 bits</td><td>8.1 seconds</td></tr><tr><td>32 bits</td><td>16.5 seconds</td></tr><tr><td>34 bits</td><td>33.5 seconds</td></tr><tr><td>36 bits</td><td>68.9 seconds</td></tr></tbody></table>

<table><caption>Table 13.2: Estimated attack running times for 1024-bit moduli.</caption><thead><tr><th>ℓ = ⌈log<sub>2</sub> p'⌋</th><th>running time</th><th>estimated number of clock cycles</th></tr></thead><tbody><tr><td>60 bits</td><td>3 days</td><td>2<sup>50</sup></td></tr><tr><td>80 bits</td><td>9 years</td><td>2<sup>60</sup></td></tr><tr><td>100 bits</td><td>9000 years</td><td>2<sup>70</sup></td></tr></tbody></table>

evaluation step. Finally, the multiplications by $s_i$ in Algorithm 13.4, Step 14 can be skipped altogether as we search for a factor of $N$ with GCD computations, since the $s_i$'s are prime to $N$ by construction. We obtain the detailed procedure described in Algorithm 13.2.

The attack can again be broken down in three stages: interpolation in Steps 2–18, evaluation in Steps 19–36 and factor search in Steps 37–40. Complexity is dominated by the three quasi-linear multiplication steps: the middle products of Steps 15 and 32, and the polynomial multiplication of Step 36.

## 13.5 Implementation

We provide the source code of our attack in Appendix 13.B. The implementation of polynomial interpolation and evaluation using Newton basis conversions largely follows the pseudocode from [Bos03] (Figure 5.1 and 5.2), implemented in C using the FLINT library [HH+10].

In Table 13.1, we provide the observed running time of our attack on an Intel Core2 Duo E8500 3.12 GHz, for 1024-bit RSA moduli. The program was linked to the following libraries: FLINT 1.6 (prerelease), MPIR 2.1.3 and MPFR 3.0, and ran on a single CPU core.

From Table 13.1 we see that, as expected, running times are essentially linear in $\sqrt{p'}$. Direct extrapolation yields the estimates given in Table 13.2.

Thus, even the parameter $ℓ = 100$ suggested in Groth's paper [Gro05] would require a large but not unachievable amount of computation, even by academic standards. As a
<caption>**Algorithm 13.2 Detailed attack.**</caption>

1: **function** ATTACK(g, n, N)
2:     p ← 1; q ← 1; s ← 1; u ← 1; z ← 1; w ← 1
3:     Initialize U, Z, S, W as zero polynomials of degree n − 1
4:     U₀ ← u; Z₀ ← z; W₀ ← w
5:     **for** i = 1 to n − 1 **do**
6:         p ← p · g mod N
7:         q ← q · p mod N
8:         s ← s · (p − 1) mod N
9:         u ← u · p/(1 − p) mod N
10:        z ← (−1)sup/u/q mod N
11:       w ← q/(s · u) mod N
12:      Uᵢ ← u; Zᵢ ← z; Wᵢ ← w
13:      **end for**
14:      Z ← (−1)ⁿ⁻¹sₙ₋₁ · Z mod N
15:      W ← mulᵗ(n − 1, U, W)
16:      **for** i = 0 to n − 1 **do**
17:         Wᵢ ← Wᵢ · Zᵢ mod N
18:      **end for**
19:      g ← 1/(p · g) mod N ▷ g ← g⁻△
20:      p ← 1; q ← 1; s ← 1; u ← 1; z ← 1; w ← 1
21:      U ← 0; Z ← 0
22:      U₀ ← u; Z₀ ← z; S₀ ← s
23:      **for** i = 1 to n − 1 **do**
24:         p ← p · g mod N
25:         q ← q · p mod N
26:         s ← s/(p − 1) mod N
27:         u ← u · p/(1 − p) mod N
28:         z ← (−1)sup/u/q mod N
29:        Sᵢ ← s; Uᵢ ← u; Zᵢ ← z
30:       Wᵢ ← Wᵢ/z mod N
31:      **end for**
32:      W ← mulᵗ(n − 1, Z, W)
33:      **for** i = 0 to n − 1 **do**
34:         Wᵢ ← (−1)sup/Wᵢ · Uᵢ mod N
35:      **end for**
36:      W ← W · S
37:      **for** i = 0 to n − 1 **do**
38:         **if** gcd(Wᵢ, N) ≠ 1 **then return** gcd(Wᵢ, N) ▷ Factor found!
39:         **end if**
40:      **end for**
41: **end function**
comparison, the recent factorization of RSA 768 [KAF+10] required about 2000 CPU-years.

However, it is not obvious how the algorithm can be efficiently parallelized to distribute the computation. A naive parallelization strategy is to reduce the number of $x_i$'s and increase the number of $y_i$'s by some factor $2^k$, but this only reduces time and memory by a factor of about $2^k$ while requiring $2^{2k}$ parallel nodes. It would be desirable to be able to distribute the full size computation—both the FFT steps (multiplication and middle product) and the pre-computations—but this appears to be nontrivial.

Most importantly, it is difficult to deal with larger parameters because the attack is heavily memory-bound: the $O(\sqrt{p'})$ memory requirement is a serious hurdle. In experiments, we encountered memory problems as early as $\ell \approx 38$ for a 1024-bit modulus, and even with much more careful memory management and the use of mass storage rather than RAM, it seems unlikely that parameters larger than $\ell \approx 60$ can be attacked unless storage can be efficiently distributed as well.

## 13.6 Conclusion

We have described an attack against the RSA subgroup of hidden order described in [Gro05] that works in time $\tilde{O}(\sqrt{p'})$ while the best attack considered in [Gro05] had complexity $O(p')$. We have implemented our attack and assessed its practicality. As expected, our attack exhibits a time complexity quasi-linear in $\sqrt{p'}$. In terms of CPU time alone, the parameters suggested in [Gro05] appear to be within reach for a resourceful attacker. However, due to heavy memory requirements and parallelization problems, these parameters may remain unchallenged.

An interesting open question is to decrease the memory requirement: an algorithm similar to Pollard rho or Pollard lambda with constant memory would be the most convenient type of attack on this problem if it exists. If not, a method for distributing the computation and storage efficiently would be the simplest way to make the attack practical for larger parameters.
13.A Bostan's Algorithms

**Algorithm 13.3 Polynomial interpolation:** compute the polynomial $F$ of degree $< n$
such that $F(p_i) = v_i$, where $p_i = q^i$, $0 \le i \le n-1$.

1: **function** INTERPGEOM($p_0, \dots, p_{n-1}; v_0, \dots, v_{n-1}$)
2:   $q_0 \leftarrow 1$; $s_0 \leftarrow 1$; $u_0 \leftarrow 1$; $z_0 \leftarrow 1$; $w_0 \leftarrow v_0$
3:   **for** $i = 1$ to $n-1$ **do**
4:     $q_i \leftarrow q_{i-1} \cdot p_i$
5:     $s_i \leftarrow s_{i-1} \cdot (p_i - 1)$
6:     $u_i \leftarrow u_{i-1} \cdot p_i / (1-p_i)$
7:     $z_i \leftarrow (-1)^i u_i / q_i$
8:   **end for**
9:   $H \leftarrow (\sum_{i=0}^{n-1} v_i / s_i x^i) \cdot (\sum_{i=0}^{n-1} (-x)^i q_i / s_i)$
10:  **for** $i = 1$ to $n-1$ **do**
11:    $w_i \leftarrow (-1)^i \text{Coeff}(H, i) / u_i$
12:  **end for**
13:  $G \leftarrow \text{mul}^t(n-1, \sum_{i=0}^{n-1} u_i x^i, \sum_{i=0}^{n-1} w_i x^i)$
14:  **return** $\sum_{i=0}^{n-1} z_i \text{Coeff}(G, i) x^i$
15: **end function**

**Algorithm 13.4 Polynomial evaluation:** evaluate the polynomial $F$ at all points $p_i = q^i$, $0 \le i \le n-1$.

1: **function** EVALGEOM($p_0, \dots, p_{n-1}$; $F$)
2:   $q_0 \leftarrow 1$; $s_0 \leftarrow 1$; $u_0 \leftarrow 1$; $z_0 \leftarrow 1$; $g_0 \leftarrow 1$
3:   **for** $i = 1$ to $n-1$ **do**
4:     $q_i \leftarrow q_{i-1} \cdot p_i$
5:     $s_i \leftarrow s_{i-1} \cdot (p_i - 1)$
6:     $u_i \leftarrow u_{i-1} \cdot p_i / (1-p_i)$
7:     $z_i \leftarrow (-1)^i u_i / q_i$
8:   **end for**
9:   $G \leftarrow \text{mul}^t(n-1, \sum_{i=0}^{n-1} z_i x^i, \sum_{i=0}^{n-1} g_i x^i)$
10:  **for** $i = 1$ to $n-1$ **do**
11:    $g_i \leftarrow (-1)^i u_i \text{Coeff}(G, i)$
12:  **end for**
13:  $W \leftarrow (\sum_{i=0}^{n-1} g_i x^i) \cdot (\sum_{i=0}^{n-1} s_i^{-1} x^i)$
14:  **return** $s_0 \text{Coeff}(W, 0), \dots, s_{n-1} \text{Coeff}(W, n-1)$
15: **end function**
```c
        c0 = clock();
        attack(g, m, 1L<<d);
        c1 = clock();

        printf("Elapsed time: %.3f seconds.\n",
               ((float)(c1-c0))/CLOCKS_PER_SEC);
    }
```
<figure><img src="image_33.png" /></figure>