Lattice Attacks Against Elliptic-Curve Signatures with Blinded Scalar Multiplication

Abstract

Elliptic curve cryptography is today the prevailing approach to get efficient public-key cryptosystems and digital signatures. Most of elliptic curve signature schemes use a nonce in the computation of each signature and the knowledge of this nonce is sufficient to fully recover the secret key of the scheme. Even a few bits of the nonce over several signatures allow a complete break of the scheme by lattice-based attacks. Several works have investigated how to efficiently apply such attacks when partial information on the nonce can be recovered through side-channel attacks. However, these attacks usually target unprotected implementation and/or make ideal assumptions on the recovered information, and it is not clear how they would perform in a scenario where common countermeasures are included and where only noisy information leaks via side channels. In this paper, we close this gap by applying such attack techniques against elliptic-curve signature implementations based on a blinded scalar multiplication. Specifically, we extend the famous Howgrave-Graham and Smart lattice attack when the nonces are blinded by the addition of a random multiple of the elliptic-curve group order or by a random Euclidean splitting. We then assume that noisy information on the blinded nonce can be obtained through a template attack targeting the underlying scalar multiplication and we show how to characterize the obtained likelihood scores under a realistic leakage assumption. To deal with this scenario, we introduce a filtering method which given a set of signatures and associated likelihood scores maximizes the success probability of the lattice attack. Our approach is backed up with attack simulation results for several signal-to-noise ratio of the exploited leakage.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In 1985, Koblitz [Kob87] and Miller [Mil86] independently proposed to use the algebraic structure of elliptic curves in public-key cryptography. Elliptic curve cryptography requires smaller keys and it achieves faster computation and memory, energy and bandwidth savings. It is therefore well suited for embedded devices. There exists several digital signature schemes based on the discrete logarithm problem in the group of points of an elliptic curve (e.g. [ElG84, Sch91, Nat00]). These schemes use a nonce k for each signed message and compute $[k]\varvec{P}$ for some public point $\varvec{P}$ on the elliptic curve. It is well known that the knowledge of partial information on the nonces used for the generation of several signatures may lead to a total break of the scheme [HS01, Ble00].

Side-channel attacks are a major threat against implementations of cryptographic algorithms [Koc96, KJJ99]. These attacks consists in analyzing the physical leakage of a cryptographic hardware device, such as its power consumption or its electromagnetic emanations. Elliptic curves implementations have been subject to various side-channel attacks. In order to prevent the leakage of partial information on the nonce k from the run of the algorithm that computes scalar multiplication $[k]\varvec{P}$, many countermeasures have been proposed. To thwart simple side-channel analysis, it is customary to ensure a constant (or secret-independent) operation flow (see for instance [Cor99, JY03, IMT02]). To prevent more complex attacks it is necessary to use a probabilistic algorithm to encode the sensitive values such that the cryptographic operations only occur on randomized data. In [Cor99], Coron proposed notably to randomize the scalar k and the projective coordinates of the point $\varvec{P}$. These countermeasures are nowadays widely used and it is not very realistic to assume that a specific set of bits from the nonces could be recovered in clear by a side-channel attacker.

Related works. Two famous attacks have been designed against elliptic-curve signature schemes that exploit partial information on the nonces of several signatures: the Bleichenbacher’s attack [Ble00] and the Howgrave-Graham and Smart’s attack [HS01]. Nguyen and Shparlinski [NS02, NS03] proposed a proven variant of Howgrave-Graham and Smart’s attack when a single block of consecutive bits is unknown to the adversary. Very few results on the security of elliptic-curve signatures with noisy partial information on the nonces are known. In [LPS04], Leadbitter, Page and Smart considered adversaries that can determine some relation amongst the bits of the secret nonces rather than their specific values (but this relation is known with certainty). This work was recently extended by Faugère et al. in [FGR13]. In [BV15], Bauer and Vergnaud designed an attack where the adversary learns partial information on the nonces but not with perfect certainty (but their attack does not apply to ECDSA or Schnorr signatures).

In [CRR03], Chari et al. introduced the so-called template attacks which aim at exploiting all the available side-channel information when the adversary can only obtain a limited number of leakage traces (which is the case in our discrete logarithm setting since a nonce is used only once). Template attacks require that the adversary is able to perform a profiling of the side-channel leakage (e.g. based on a copy of the target device under her control). Template attacks against ECDSA were proposed in [MO09, HMHW09, HM09, MHMP13] but none of them considered a blinded implementation of the scalar multiplication.

Our contributions. We consider practical attack scenario, where the target implementation is protected with usual countermeasures and where the adversary recovers some noisy information from a signature computation. We consider an elliptic curve signature based on a regular scalar multiplication algorithm which is protected using classic randomization techniques, such as the masking of projective coordinates and the scalar blinding [Cor99, CJ03]. Our contributions are three-fold.

Firstly, we adapt the lattice-based attack proposed by Howgrave-Graham and Smart [HS01] to the setting where the adversary gets partial information on blinded nonces of the form $k + r \cdot q$ where r is a small random integer (typically of 32 bits) and q is the elliptic curve group order [Cor99]. We show that the attack works essentially in the same way than the original one but the number of known bits per nonce must be increased by the bit-length of the random r and the number of unknown blocks of consecutive bits.

Afterwards, we consider a scenario where some noisy information is leaked on the bits of the blinded nonces. Under a realistic leakage assumption, the widely admitted multivariate Gaussian assumption, we show how to model the information recovered by a template attacker. Specifically, we characterize the distribution of the obtained likelihood scores with respect to a multivariate signal-to-noise ratio parameter. We then introduce a filtering method which, given a set of signatures and associated likelihood scores, select the blinded nonce bits to construct the lattice a way to maximize the success probability of the attack. The method relies on a criteria derived from the analysis of the Howgrave-Graham and Smart’s attack and techniques from dynamic programming.

Finally, we consider a second implementation setting in which the scalar multiplication is protected by the random Euclidean splitting method [CJ03]. In this setting, the nonces k are split as $k = \lceil k/r \rceil \cdot r + (k \bmod r)$ for a (small) random r and the adversary gets partial information on r, $\lceil k/r \rceil$ and $(k \bmod r)$. We show how this partial information can be use to directly get likelihood scores on the nonce bits and we adapt our filtering method to this scenario. For both blinding schemes, we provide some experimental results for our attack based on several values for the multivariate SNR parameter. Our experiments are simulation-based but one could equally use practically-obtained score vectors from a template attack against an actual implementation. The obtained results would be the same for similar multivariate signal-to-noise ratios.

2 Implementation and Leakage Model

2.1 ECDSA Signature Scheme

The ECDSA signature scheme [Nat00] relies on an elliptic curve E defined over some finite field $\mathbb {K}$ where $E(\mathbb {K})$, the group of $\mathbb {K}$-rational points of E, has (almost) prime order q. The public parameters of the scheme include a description of $E(\mathbb {K})$, a base point $\varvec{P}\in E(\mathbb {K})$ that is a generator of the group (or of the large prime-order subgroup), and a cryptographic hash function $\mathrm {H} : \{0,1\}^* \mapsto [\![0,2^{\ell -1}]\!]$, where $\ell := \lceil \log _2 q \rceil$. The secret key x is randomly sampled over $[\![0,q-1]\!] = [0,q) \cap \mathbb {Z}$ and the corresponding public key is set as the point $\varvec{Q}= [x] \varvec{P}$, that is the scalar multiplication of $\varvec{P}$ by x.

A signature $\sigma = (t,s)$ of a message $m \in \{0,1\}^*$ is then computed from the secret key x as $t = \text {xcoord}([k]\varvec{P})$ and $s = k^{-1} (h + t \cdot x) \bmod q$, where k is a random nonce sampled over $[\![1,q-1]\!]$ and $h = \mathrm {H}(m)$. One can then verify the signature from the public key $\varvec{Q}$ by computing $u = s^{-1} \, h \bmod q$ and $v = s^{-1} \, t \bmod q$, and checking whether $\text {xcoord}([u]\varvec{P}+ [v]\varvec{Q}) = t$. A legitimate signature indeed satisfies $[u]\varvec{P}+ [v]\varvec{Q}= [s^{-1} (h + t \cdot x) \cdot h \bmod q] \varvec{P}= [k] \varvec{P}$.

2.2 Target Implementation

The attacks presented in this paper target an ECC-signature implementation that relies on a regular scalar multiplication algorithm, which is assumed to be binary in the sense that each loop iteration handles a single bit of the scalar. A prominent example of such a binary regular algorithm is the Montgomery ladder [Mon87] which is widely used for its security and efficiency features [JY03, IMT02, GJM+11].

The target implementation is also assumed to include common countermeasures against side-channel attacks such as as the classic scalar blinding [Cor99] and the Euclidean blinding [CJ03]:

2.3 Leakage Model

The computation performed during one iteration of any regular binary scalar multiplication is deterministic with respect to the current scalar-bit b and the two points $\varvec{P}_0$ and $\varvec{P}_1$ in input of the iteration. The side-channel leakage produced in such an iteration can hence be modeled as a noisy function $\psi (b,\varvec{P}_0,\varvec{P}_1)$. In the following we shall assume that for randomized points $(\varvec{P}_0,\varvec{P}_1)$, the leakage $\psi (b,\varvec{P}_0,\varvec{P}_1)$ can be modeled by a multivariate Gaussian distribution:

$$\begin{aligned} \psi (b,\varvec{P}_0,\varvec{P}_1) \sim \mathcal {N}(m_b, \varSigma ), \end{aligned}$$

(1)

where $m_0$ and $m_1$ are T-dimensional mean leakage vectors and where $\varSigma$ is a $T \times T$ covariance matrix. In what follows, we shall simply denote this leakage $\psi (b)$. The overall leakage of the scalar multiplication $[a]\varvec{P}$ is hence modeled as $\big (\psi (a_{\ell _a-1}), \ldots , \psi (a_{1}), \psi (a_{0})\big )$ where we further assume the mutual independence between the $\psi (a_{i})$ (where the length $\ell _a$ of a depends on the randomization scheme).

2.4 Profiling Attack

We consider a profiling attacker that owns templates for the leakage of a scalar multiplication iteration w.r.t. the input bit. Based on these templates, the attacker can mount a maximum likelihood attack to recover each bit of the scalar with a given probability. More precisely, the considered attacker can

• measure the side-channel leakage of a scalar multiplication $[a]\varvec{P}$,

• divide the measured traces into sub-traces $\psi (a_{i})$,

• compare the measured leakage with templates for $\psi (0)$ and $\psi (1)$, and determine the probability that $a_i=0$ or $a_i=1$ given an observation $\psi (a_{i})$.

In particular, we consider the ideal case where the attacker knows the exact distribution of $\psi (0)$ and $\psi (1)$, namely he knows the leakage parameters $m_0$, $m_1$ and $\varSigma$. Although this might be viewed as a strong assumption, efficient techniques exist to derive precise leakage templates in practice, especially in our context where the key-space is of size 2 ($b\in \{0,1\}$). Even if model-error might lower the probability of correctly recovering a target bit in practice, it would not invalidate the principle of our attacks.

Considering the above leakage model, the probability that the bit $a_i$ equals $b\in \{0,1\}$ given a leakage sample $\psi (a_i) = x_i$ satisfies

$$\begin{aligned} p_b(x_i) := \Pr (a_i = b \mid \psi (a_i) = x_i) \propto \exp \big ( - \frac{1}{2} (x_i - m_b)^{\mathsf {t}} \cdot \varSigma ^{-1} \cdot (x_i - m_b) \big ) , \end{aligned}$$

(2)

where $\propto$ means is equal up to a constant factor, such that $p_0(x_i) + p_1(x_i) = 1$. Let us define the multivariate signal-to-noise ratio (SNR) $\theta$ as

$$\begin{aligned} \theta = \varLambda \cdot (m_0 - m_1) , \end{aligned}$$

(3)

where $\varLambda$ is the Cholesky decomposition matrix of $\varSigma ^{-1}$, that is the upper triangular matrix satisfying $\varLambda ^{\mathsf {t}} \cdot \varLambda =\varSigma ^{-1}$. This decomposition always exists provided that $\varSigma$ is full-rank (i.e. no coordinate variable of the multivariate Gaussian is the exact linear combination of the others) which can be assumed without loss of generality. We have the following result:

Proposition 1

For every $x_i \in \mathbb {R}^{\mathsf {t}}$

$$\begin{aligned} p_0(x_i) \propto \left\{ \begin{array}{ll} \exp {\big (- \frac{1}{2} y_i^{\mathsf {t}} y_i \big )} &{} \text {if } a_i = 0 \\ \exp {\big (- \frac{1}{2} (y_i^{\mathsf {t}} y_i + 2 \theta ^{\mathsf {t}} y_i + \theta ^{\mathsf {t}} \theta ) \big )} &{} \text {if } a_i = 1 \end{array}\right. \end{aligned}$$

(4)

where $y_i = \varLambda \cdot (x_i - m_{a_i})$. Moreover if $x_i$ follows a distribution $\mathcal {N}(m_{a_i}, \varSigma )$, then $y_i$ follows a distribution $\mathcal {N}(\mathbf 0 , I_T)$, where $I_T$ is the identity matrix of dimension T.

The above proposition shows that, for any T-dimensional leakage distribution, the outcome of the considered template attack only depends on the multivariate SNR $\theta$. That is why, in Sect. 6 we provide attack experiments for several values of $\theta$. In practice, one could evaluate the vulnerability of an implementation to our attack by constructing leakage templates for $\psi (0)$ and $\psi (1)$, deriving the corresponding multivariate SNR $\theta$, and simulating probability scores based on Proposition 1.

3 Lattice Attack with Partially-Known Blinded Nonces

In this section, we recall the lattice attack by Howgrave-Graham and Smart [HS01] against ECDSA with partially known nonces, and we extend it to the case where the attacker has partial information on the blinded nonces. The attacker is assumed to collect $n+1$ signatures $\sigma _0, \sigma _1, \ldots , \sigma _{n}$, for which he knows some bits of the blinded nonces $a_0, a_1, \ldots , a_n$. These blinded nonces are defined as $a_i = k_i + r_i \cdot q$, where $k_i$ is the original (non-blinded) nonce, and $r_i$ is the $\lambda$-bit random used in the blinding of $k_i$. Additionally, we denote by $t_i$ and $s_i$ the two parts of the ECDSA signature $\sigma _i=(t_i,s_i)$ and by $h_i$ the underlying hash value.

3.1 Attack Description

By definition, we have $s_i - a_i^{-1}(h_i + t_ix) \equiv 0 \bmod q$ for every signature $\sigma _i$. We can then eliminate the secret key x from the equations since we have

$$\begin{aligned} x \equiv \frac{a_i s_i-h_i}{t_i} \bmod q \quad \implies \quad \frac{a_0s_0-h_0}{t_0} \equiv \frac{a_i s_i-h_i}{t_i} \bmod q \end{aligned}$$

(5)

for every $i \in \{1,\dots ,n\}$. The above can then be rewritten as

$$\begin{aligned} a_i + A_i a_0 + B_i \equiv 0 \bmod q \end{aligned}$$

(6)

where $A_i = -\frac{s_0t_i}{s_it_0} \bmod q$ and $B_i = \frac{h_0t_i-h_it_0}{t_0s_i} \bmod q$.

The goal of the attack is to use the information we have on each $a_i$ to derive a system of equations which can be reduced to a lattice closest vector problem (CVP). Let us assume we can obtain several blocks of consecutive bits so that $a_i$ can be expressed as:

$$\begin{aligned} a_i = \sum _{j=1}^{N} x_{i,j}2^{\kappa _{i,j}} + x_{i}'\end{aligned}$$

(7)

where $x_i'$ is known, and $x_{i,1}, x_{i,2}, \ldots , x_{i,N}$ are the N unknown blocks. We will denote by $\mu _{i,j}$ the bit-length of each $x_{i,j}$ so that we have $0 \le x_{i,j} < 2^{\mu _{i,j}}$.

We can now rewrite (6) to obtain a system of linear equations in the $x_{i,j}$ as follows:

$$\begin{aligned} x_{i,1} + \sum _{j=2}^{N}\alpha _{i,j}x_{i,j}+\sum _{j=1}^{N}\beta _{i,j}x_{0,j}+\gamma _i = \eta _i q \end{aligned}$$

(8)

for some known coefficients $\alpha _{i,j}, \beta _{i,j}, \gamma _{i} \in [\![0,q-1]\!]$, and unknown integers $x_{i,j}$ and $\eta _i$. Let $C \in \mathcal {M}_{n,N(n+1)-n}(\mathbb {Z})$ be the matrix defined as

(9)

and let $\varvec{x}\in \mathbb {Z}^{N(n+1)-n}$ and $\varvec{\eta }\in \mathbb {Z}^{n}$ be the (column) vectors defined as

$$\begin{aligned}&\varvec{x} = (x_{1,2},\ldots ,x_{1,N} ~|~ x_{2,2},\ldots ,x_{2,N} ~|~ \ldots ~|~ x_{n,2},\ldots ,x_{n,N} ~|~ x_{0,1},\ldots ,x_{0,N})^{\mathsf {t}},&\\&\varvec{\eta } = (\eta _1,\eta _2,\ldots , \eta _n)^{\mathsf {t}} .&\end{aligned}$$

According to (7), we have

$$\begin{aligned} C \cdot \varvec{x} - q \cdot \varvec{\eta } = - (\gamma _1 + x_{1,1}, \gamma _2 + x_{2,1}, \ldots , \gamma _n + x_{n,1} )^{\mathsf {t}} \end{aligned}$$

(10)

We consider the lattice $\mathcal {L}$ spanned by the columns of the following matrix:

$$\begin{aligned} M = \begin{pmatrix} C &{} - q \cdot I_n \\ - I_{N(n+1)-n} &{} 0 \\ \end{pmatrix} \end{aligned}$$

(11)

where $I_n$ and $I_{N(n+1)-n}$ denote the identity matrices of dimension n and $N(n+1)-n$ respectively. In particular, the vector $\varvec{y}^{\mathsf {t}} = - (\varvec{x}^{\mathsf {t}} | \varvec{\eta }^{\mathsf {t}}) \in \mathbb {Z}^{N(n+1)}$ yields the following lattice vector:

$$\begin{aligned} M \cdot \varvec{y} = (\gamma _1 + x_{1,1}, \gamma _2 + x_{2,1}, \ldots , \gamma _n + x_{n,1} ~|~ \varvec{x}^{\mathsf {t}} )^{\mathsf {t}} \end{aligned}$$

(12)

which might be close to the non-lattice vector

$$\begin{aligned} \varvec{v} = (\gamma _1, \gamma _2, \ldots , \gamma _n, 0, 0, \ldots , 0)^{\mathsf {t}} \end{aligned}$$

(13)

It is indeed easy to check that the Euclidean distance $\Vert M \cdot \varvec{y} - \varvec{v}\Vert$ satisfies

$$\begin{aligned} \Vert M \cdot \varvec{y} - \varvec{v}\Vert ^2 = \sum _{0\le i\le n \atop 1\le j \le N} x_{i,j}^2 \le \sum _{0\le i\le n \atop 1\le j \le N} 2^{2 \mu _{i,j}} \end{aligned}$$

(14)

If the distance is small enough, and if the lattice dimension $(n+1) N$ is not too high, one can find $M \cdot \varvec{y}$ as the closest lattice vector to $\varvec{v}$ and hence get the solution to the system. From the latter solution, one can recover the randomized nonces $a_i$ (by (7)) which in turn yields the secret key x (by (5)).

Normalization. We consider unknown blocks $x_{i,j}$ that may be of different bit-lengths $\mu _{i,j}$. Therefore, we shall normalize the matrix M in order to have the same weight in all the coordinates of $M \cdot \varvec{y}$, which shall lead to a better heuristic on the resolution of the lattice problem. To do so, let us define $\rho _{i,j}\in \mathbb {Z}$ as

$$\begin{aligned} \rho _{i,j} = \frac{1}{2^{\mu _{i,j}}} . \end{aligned}$$

(15)

We then consider the lattice $\mathcal {L}'$ spanned by the rows of the matrix $M' = D \cdot M$, where D denotes the following diagonal matrix:

$$\begin{aligned} D = \mathcal {D}\big ((\rho _{i,1})_{i=1}^n ~\big |~ (\rho _{1,j})_{j=2}^N ~\big |~ (\rho _{n,j})_{j=2}^N ~\big |~ (\rho _{0,j})_{j=1}^N\big ) \end{aligned}$$

(16)

where $\mathcal {D}$ is the function mapping a vector to the corresponding diagonal matrix.¹ The non-lattice vector $\varvec{v}'$ is then defined as

$$\begin{aligned} \varvec{v}' = D \cdot \varvec{v} = (\rho _{1,1} \gamma _1, \rho _{2,1} \gamma _2 ,\dots , \rho _{n,1} \gamma _n, 0, 0, \ldots , 0)^{\mathsf {t}}\end{aligned}$$

and the target closest lattice vector is $M' \cdot \varvec{y}$. The distance between these two vectors then satisfies

$$\begin{aligned} \Vert M' \cdot \varvec{y} - \varvec{v}' \Vert = \Vert D \cdot (M \cdot \varvec{y} - \varvec{v}) \Vert = \Big ( \sum _{0\le i\le n \atop 1\le j \le N} (\rho _{i,j} x_{i,j})^2 \Big )^{\frac{1}{2}} \le \sqrt{(n+1)N} . \end{aligned}$$

(17)

3.2 Attack Parameters

We make the classic heuristic assumption that the CVP can be efficiently solved as long as the dimension is not too high and the distance is upper-bounded by

$$\begin{aligned} \Vert M' \cdot \varvec{y} - \varvec{v}' \Vert \le c_0 \sqrt{\dim (M')} \det (M')^{\frac{1}{\dim (M')}}, \end{aligned}$$

(18)

for some constant $c_0 = 1/\sqrt{2 \pi e} \simeq 0.24197$ (see for instance [FGR13]). In our attacks, we will actually use the polynomial-time LLL [LLL82] algorithm in order to recover the lattice vector $M' \cdot \varvec{y}$. This gives a slightly worse inequality in (18) and the CVP can be efficiently solved for smaller values $c_0$ that may actually depend on the dimension of the lattice.

Let us denote by $\mu _i = \sum _{j} \mu _{i,j}$ the number of unknown bits in $a_i$, and by $\mu = \sum _{i} \mu _{i}$ the total number of unknown bits. Let us also denote by $\delta _i = \ell + \lambda - \mu _i$ the number of known bits in $a_i$, and by $\delta = \sum _i \delta _i = (n+1)(\ell + \lambda ) - \mu$ the total number of known bits. The dimension of the matrix $M'$ is $(n+1)N$ and its determinant is $\det (M') = \det (M) \cdot \det (D) = q^n \cdot 2^{-\mu }$. By (17), the above inequality is satisfied whenever we have²

$$\begin{aligned} 1 \le c_0 (q^n \cdot 2^{-\mu })^{\frac{1}{N_b}} \Longleftrightarrow \mu + c_1 N_b \le n \cdot \log _2(q) < n \ell , \end{aligned}$$

(19)

where $N_b = (n+1) N$ denotes the total number of unknown blocks in the $n+1$ signatures, and where $c_1$ is a constant defined as $c_1 = - \log _2(c_0) > 0$. We can deduce a sufficient condition on the number of bits $\delta$ that must be known for the attack to succeed:

$$\begin{aligned} \delta \ge \ell + (n+1) \lambda + c_1 N_b \Longleftrightarrow \sum _{i=0}^n (\delta _i - \lambda - c_1 N) \ge \ell . \end{aligned}$$

(20)

This means that in order to mount a lattice attack against ECDSA protected with classic randomization of the nonce, one must recover at least $(\lambda + c_1 N)$ bits of each blinded nonce plus some extra bits, where the total amount of extra bits must reach $\ell$.

Varying number of Blocks. For the sake of clarity, we described the attack by assuming a constant number N of unknown blocks for all the signatures. Note that the attack works similarly with a varying number of blocks $N_0, N_1, \ldots , N_n$ and the above condition keep unchanged. To see this, simply consider the above description with $N = \max _i N_i$ and $\mu _{i,j} = 0$ for every $j > N_i$. Note however that for different block sizes, we have $N_b = \sum _{i=0}^n N_i$ instead of $N_b = (n+1)N$.

3.3 Experiments

The CVP can be solved using Babai’s rounding algorithm [Bab86], but in practice one shall prefer the embedding technique from [GGH97]. This technique reduces the CVP to the shortest vector problem (SVP), by defining the embedding lattice $\mathcal {L}_{\text {emb}}$ spanned by the columns of

$$\begin{aligned} \left( \begin{array}{ccc|c} &{} &{} &{} \\ &{} M' &{} &{} \varvec{v} \\ &{} &{} &{} \\ \hline 0 &{} \cdots &{} 0 &{} -K \end{array} \right) \end{aligned}$$

(21)

where K is a constant taken to be of the same order as the greatest coefficient of $M'$. Informally, if $M' \cdot \varvec{y} \in \mathcal {L}$ is close to $\varvec{v}$, then $\varvec{w} = \big ((M' \cdot \varvec{y} - \varvec{v})^{\mathsf {t}} ~|\, K\big )^{\mathsf {t}}$ is a short vector of the embedding lattice $\mathcal {L}_{\text {emb}}$. By applying LLL to $\mathcal {L}_{\text {emb}}$, one can therefore recover $\varvec{w}$ as the shortest vector in the reduced basis, from which $M' \cdot \varvec{y}$ is easily deduced.

In order to validate the constraint on the parameters (see (20)) and determine the actual value of $c_1$, we experienced the attack using the embedding technique with different set of parameters. Specifically, we used the ANSSI 256-bit elliptic curve ($\ell = 256$), different random sizes ($\lambda \in \{0,16,32,64\}$), different numbers of signatures ($(n+1) \in \{5, 10, 20\}$), as well as different numbers of blocks per signature ($N \in \{1,2,5,10\}$). In each experiments, the blocks were randomly distributed in the blinded nonces (by randomly sampling the starting index among possible ones). Additionally, we considered that the number of bits per block could vary according to a standard deviation parameter $\sigma$ as follows. The bit-length $\delta _{i,j}$ of each block is randomly sampled according to the distribution $\mathcal {N}(m,\sigma )$ with $m = \delta / N_b$, where we recall that $\delta = \sum _{i,j} \delta _{i,j}$ is the total number of known bits and $N_b = (n+1)N$ is the total number of unknown blocks. Samples are then rounded to the nearest integer with rejection for samples lower than 1 (minimum number of bits per block). Finally, samples are randomly incremented or decremented until they sum to the desired value $\delta$. In a nutshell, taking a standard deviation $\sigma = 0$ makes all the $\delta _{i,j}$’s equal to m. On the other hand, taking a standard deviation to $\sigma \approx m$ makes the $\delta _{i,j}$’s to vary over $[\![1,2m]\!]$ (with a few ones beyond 2m). For our experiments, we took $\sigma = 0.1 m$ (slight deviation), $\sigma = 0.5 m$ (medium deviation), and $\sigma = m$ (strong deviation).

In each setting, the number of known bits is set to $\delta = \ell + (n+1) \lambda + \tau$ for a varying margin $\tau$ that shall correspond to $c_1 N_b$. For each tested value of $\tau$, we record the success rate of the attack over 100 trials. Table 1 summarizes the obtained ratio $\tau _{95} / N_b$ where $\tau _{95}$ is the margin required to obtain a $95\%$ success rate. This ratio gives a good estimation of the practical value of $c_1$.

Table 1. Ratio $\tau _{95} / N_b$ for various set of parameters.

We observe that for the tested parameters, the experimental value of $c_1$ lies between 3 and 5 most of the time. We also observe that the size of the random ($\lambda$) and the deviation on the number of bits per known blocks have a small impact on the resulting $c_1$, whereas the number of signatures and the total number of blocks have a stronger impact.

4 Attacking Implementations with Classic Blinding

In this section we focus on attacking implementations of elliptic-curve signatures that leak side-channel information on the blinded nonce as described in Sect. 2. In this model, one performs a template attack on the randomized scalar multiplication and recovers a probability score $\Pr (a_{i,j}=0)$ for every bit $a_{i,j}$ of every blinded nonce $a_i$. The goal is then to select a set of bits among all the recovered noisy bits that has the required properties for solving the associated lattice system and that has the highest possible probability of success (i.e. all the selected bits must have been correctly guessed based on the probability scores).

For the lattice construction, we shall use the most probable value $\hat{a}_{i,j}$ of each bit $a_{i,j}$, that is

$$\begin{aligned} \hat{a}_{i,j} = \mathop {\text {argmax}}\limits _{b\in \{0,1\}}\, \Pr (a_{i,j}=b) , \end{aligned}$$

(22)

and we shall denote by $p_{i,j}$ the probability that the bit $a_{i,j}$ is correctly guessed, that is

$$\begin{aligned} p_{i,j} = \Pr (\hat{a}_{i,j} = a_{i,j}) = \max _{b\in \{0,1\}} \Pr (a_{i,j}=b) . \end{aligned}$$

(23)

Let I denote the set of indices corresponding to the selected signatures $\{\sigma _i\}_{i\in I}$ and let $J_i$ denote the set of indices corresponding to the selected guessed bits $\{\hat{a}_{i,j}\}_{i\in J_i}$ within a random nonce for every $i \in I$. Then we will use the bits $\{\hat{a}_{i,j} | i\in I, j\in J_i\}$ to construct the lattice. The CVP’s algorithm will only succeed in recovering the right solution if all these bits are correctly guessed, namely if $\hat{a}_{i,j} = a_{i,j}$ for every $i\in I$ and $j\in J_i$. The probability p that these success events happen satisfies

$$\begin{aligned} p = \prod _{i \in I} p_i \,\,\text {with}\,\, p_i = \prod _{j \in J_i} p_{i,j} , \end{aligned}$$

(24)

where $p_i$ is the probability that all the guessed bits within the random nonce $a_i$ are correct. Our goal is hence to define the sets I, and $J_i$ for every $i \in I$ such that the success probability is maximal and such that the prerequisites of the lattice attack are well met.

Let $N_i$ denote the number of unknown blocks in the blinded nonce $a_i$, i.e. the number of non-adjacent blocks of indices $j\notin J_i$. The dimension $\varDelta$ of the lattice satisfies $\varDelta = \sum _{i\in I} N_i$ (see Sect. 4). Let $\varDelta _{max}$ be the maximal dimension of a lattice for which the attack can be practical, i.e. the LLL-reduction can be done in a reasonable time.³ The selected bits must then satisfy

$$\begin{aligned} \sum _{i\in I}N_i \le \varDelta _{max}. \end{aligned}$$

(25)

Following Sect. 4, we denote by $\delta _i=|J_i|$ the number of recovered bits in the nonce $a_i$. We recall the necessary condition for the lattice reduction to work:

$$\begin{aligned} \sum _{i\in I} (\delta _i-\lambda -c_1N_i)\ge \ell . \end{aligned}$$

(26)

From the two above conditions, a requirement for the selected bits within a blinded nonce $a_i$ is to satisfy:

$$\begin{aligned} \frac{\delta _i-\lambda }{N_i} > \frac{\ell }{\varDelta _{max}} + c_1. \end{aligned}$$

(27)

Otherwise, the contribution in terms of known bits is too small with respect to the increase of the lattice dimension. In other words, if the above condition is not satisfied then the maximal dimension $\varDelta _{max}$ is reached before the number of necessary known bits.

The above condition on the pair $(\delta _i,N_i)$ is not sufficient in itself as it does not specify how to select the sets $J_i$ maximizing the success probability. Our goal is now to define a sound criterion on each signature that will allow us to select the best sets $J_i$ i.e. the set maximizing the success probability defined in (24). Maximizing this probability is equivalent to maximizing the $\log$-success probability $\log (p) = \sum _{i\in I}\log (p_i)$, and maximizing the latter sum while satisfying (26) can be done by selecting the sets $J_i$ with maximal ratio $\frac{\log p_i}{\delta _i-\lambda -c_1N_i}$. We hence look for the set of indices $J_i$ that maximizes the following value

$$\begin{aligned} \gamma _i = p_i^{\frac{1}{\delta _i-\lambda -c_1N_i}}. \end{aligned}$$

(28)

Let $f:N \mapsto \lceil \frac{\ell \cdot N}{\varDelta _{max}} \rceil + c_1 N +\lambda$ be the function that define the minimum number of known bits from a number of unknown blocks for condition (27) to hold. For each signature $\sigma _i$ and for each possible number of blocks $N\in \llbracket 1,N_{max}\rrbracket$ we define:

$$\begin{aligned} J_i(N) = \mathop {\text {argmax}}\limits _{J;|J|=f(N)\atop g(J)\le N}\Big (\prod _{j\in J_i}p_{i,j} \Big ), \end{aligned}$$

(29)

where the function g(J) gives the number of unknown blocks in the set J.

We then define

$$\begin{aligned} p_i(N) = \prod _{j\in J_i(N)}p_{i,j} \,\,\text {and}\,\, \gamma _i (N) = p_i(N)^{\frac{1}{f(N)-\lambda -c_1N}}. \end{aligned}$$

(30)

Eventually, we shall set

$$\begin{aligned} N_i = \mathop {\text {argmax}}\limits _{N \atop } \gamma _i(N) , \gamma _i = \gamma _i(N_i) , J_i = J_i(N_i), \,\,\text {and}\,\, \delta _i = f (N_i). \end{aligned}$$

Remark 1

At this point, a natural idea is to take I as the set of indices with the highest values $\gamma _i$. However, this strategy is not reliable in practice. Indeed, it can occur that a bad guess $\hat{a}_{i,j} \ne a_{i,j}$ comes with a strong probability $p_{i,j}$ (i.e. one gets a strong confidence in the wrong choice). Since each $\gamma _i$ aggregates many probabilities $p_{i,j}$, the occurrence of such an extreme event is only marginally correlated to the actual value of $\gamma _i$.

In view of the above remark, our approach in practice is to try several random combinations of signatures, namely to take I uniformly at random among the subsets of signatures (tightly) satisfying the constraint (26).

Evaluating Eq. (29). We now explain how to evaluate the function

$$\begin{aligned} N \mapsto \max _{J;|J|=f(N)\atop g(J)\le N}\Big (\prod _{j\in J_i}p_{i,j} \Big ) \end{aligned}$$

(31)

for some family of probabilities $p_{i,0}$, $p_{i,1}$,$\dots$, $p_{i,\ell + \lambda -1}$ (getting the argmax is then straightforward). For this purpose, we define $\mathsf {maxp}$ as the function mapping a triplet $(j,\delta ,N)$ to the above max but with the condition $J \subseteq [\![j,\ell +\lambda -1]\!]$, $|J| = \delta$, and $g(J) \le N$, so that the target function in (31) can be rewritten as:

$$\begin{aligned} N \mapsto \mathsf {maxp}(0,f(N),N) \end{aligned}$$

(32)

The $\mathsf {maxp}$ function can then be evaluated by the following recurrence relation:

$$\begin{aligned} \mathsf {maxp}(j,\delta ,N) = \max \big (\mathsf {block}(j,\delta ,N), \mathsf {next}(j,\delta ,N)\big ) \end{aligned}$$

(33)

where

$$\begin{aligned}&\mathsf {block}(j,\delta ,N) = \max _{w \in [\![1,\delta ]\!]}\Big (\prod _{k=j}^{j+w-1} p_{i,k} \Big )\,\mathsf {maxp}(j+w+1,\delta -w,N-1) ,\end{aligned}$$

(34)

$$\begin{aligned}&\mathsf {next}(j,\delta ,N) = \mathsf {maxp}(j+1,\delta ,N) . \end{aligned}$$

(35)

The term $\mathsf {block}(j,\delta ,N)$ in the above $\max$ represents the case where the next w bits are added to the set J, while the term $\mathsf {next}(j,\delta ,N)$ is for the case where the next bit is not taken in the set J.⁴ The tail of the recursion is fourfold:

$$\begin{aligned} \mathsf {maxp}(j, \delta , N) = {\left\{ \begin{array}{ll} 0 &{} \text {if}\, j+\delta> \ell + \lambda \\ \prod _{k=j}^{\ell +\lambda -1} p_{i,k} &{} \text {if}\, j+\delta = \ell + \lambda \\ 0 &{} \text {if}\, N = 0 \, \text {and}\, \delta > 0 \\ 1 &{} \text {if}\, \delta = 0 \end{array}\right. } \end{aligned}$$

(36)

Remark 2

In order to get a higher success probability, we can also use exhaustive search to guess certain bits in a signature. In fact, between two blocks of bits selected by the $\mathsf {block}$ function, we can find a small block of bits with poor probability score which will discard the chance of selecting a larger unique block. To tackle this issue and improve the probability of success, we can use exhaustive search to recover these bits with probability 1 (independently of the underlying $p_{i,j}$ values). This improvement of our method is described in Appendix A.

5 Attacking Implementations with Euclidean Blinding

In this section we focus on attacking implementations protected with Euclidean blinding [CJ03], i.e. for which the nonces are decomposed as $k_i= a_i\cdot r_i+b_i$ for $i \in \{1,\dots ,n\}$ where $r_i$ is picked uniformly at random over $\llbracket 1,2^{\lambda }-1\rrbracket$, $a_i= \lceil \frac{k_i}{r_i}\rceil$ and $b_i = k_i \mod r_i$ (see Sect. 3). We suppose that the attacker can recover the probability score for every bit of $a_{i}$, $r_{i}$ and $b_{i}$ for $i \in \{1,\dots ,n\}$ with the same template attack as in the previous section.

One approach to mount an attack is to use the information we have on each nonce to derive a system of equations which we may solve using a lattice attack. The equations are of degree 2 and the number of involved monomials increases quadratically with the number of unknown blocks. A natural idea is to use the famous Coppersmith method [Cop96b, Cop96a] which is a family of lattice-based techniques to find small integer roots of polynomial equations. The method generates more non-linear equations by multiplication of several non-linear equations before the linearization step in order to improve attacks. However, in this case the structure of the variables is complex and even using polynomials of small degree leads to a lattice of very large dimension.

Our approach is different and practical: from the recovered noisy bits, one can compute probability scores for the individual bits of the nonces $k_i$ themselves. If the probability that the individual bits in $a_{i}$, $r_{i}$ and $b_{i}$ for $i \in [\![1,n]\!]$ are all correctly guessed is equal to $1/2+\varepsilon$, for some $\varepsilon > 0$, it can be checked that the obtained probabilities $\Pr (\hat{k}_{i,j}=k_{i,j})$ that the j-th bit of the nonce $k_i$ is correctly guessed tends towards 1 / 2 quickly as j grows towards the middle bit $\ell /2$.

Fig. 1.

Estimated error probability of individual nonce bits

To show this fact, we ran the following experiments:

• for several bias $\varepsilon \in \{1/4,1/8,\dots ,1/24\}$, we picked uniformly at random 10,000 nonces $k_i$ and random $r_i$ (for $\lambda = 16$) and we computed the corresponding $a_i$ and $b_i$ such that $a_i\cdot r_i + b_i = k_i$;

• we computed noisy versions of $(\tilde{a}_i,\tilde{r}_i,\tilde{b}_i)$ of $(a_i,r_i,b_i)$ as if they were transmitted over a binary symmetric channel with crossover probability $\varepsilon$ and we computed $\tilde{k}_i = \tilde{a}_i\cdot \tilde{r}_i + \tilde{b}_i$;

• for each bias and each individual bit, we computed the proportion of $\tilde{k}_{i,j}$ that matches $k_{i,j}$.

The estimated error probability $\Pr (\tilde{k}_{i,j} \ne k_{i,j})$ is plotted in Fig. 1 for the first 64 bits (in log-scale for the x-axis). These experiments show that the probabilities $\Pr (\hat{k}_{i,j}=k_{i,j})$ tends towards 1 / 2 exponentially as j comes close to the middle bit $\ell /2$. For this reason, in the case of the Euclidean blinding, we will only focus on two particular blocks of $k_i$ for each signature: the block of $\delta _{i,1}$ least significant bits (lsb) and the block of $\delta _{i,2}$ most significant bits (msb), for some $\delta _{i,1},\delta _{i,2}$. In this model, the necessary condition for the lattice reduction to work (see (20)) becomes:

$$\begin{aligned} \sum _{i\in I}(\delta _i-c_1)\ge \ell \,\, \text {where } \delta _i = \delta _{i,1} + \delta _{i,2}, \end{aligned}$$

(37)

since $\lambda =0$ and $N_i=1$ (there is a single unknown block per nonce), implying:

$$\begin{aligned} \delta _{i} \ge \left\lceil \frac{\ell }{\varDelta _{max}}\right\rceil + c_1 \end{aligned}$$

(38)

as a sound condition on each signature. As seen in the previous sections, the CVP algorithm will only succeed in recovering the right solution if the two blocks of $k_i$ are correctly guessed for each signature. In order to select the blocks and their respective sizes $\delta _{i,1}$, $\delta _{i,2}$, we use an approach similar to the one proposed in Sect. 5.

Let $B_{i,1}$ and $B_{i,2}$ denote the blocks of $\delta _{i,1}$ lsb and $\delta _{i,2}$ msb of $k_i$. The guessed blocks are defined as:

$$\begin{aligned} \hat{B}_{i,j} = \mathop {\text {argmax}}\limits _{x\in \{0,1\}^{\delta _{i,j}}}\Pr (B_{i,j} = x) \end{aligned}$$

(39)

for $j\in \{1,2\}$. The block probabilities are then defined as

$$p_{i,j} = \Pr (B_{i,j}=\hat{B}_{i,j}) = \max _{x\atop }\Pr (B_{i,j}=x)$$

for $j\in \{1,2\}$ and the probability for one signature is $p_i= p_{i,1} \cdot p_{i,2}$. Then, we select $\delta _{i,1}$ and $\delta _{i,2}$ such that they maximize the value $\gamma _i = p_i^{\frac{1}{\delta _i-c_1}}$.

Clearly, $\gamma _i$ depends on the sizes $\delta _{i,1}$ and $\delta _{i,2}$ of the blocks $B_{i,1}$ and $B_{i,2}$. We shall denote $\gamma _i(\delta _{i,1},\delta _{i,2})$ to see $\gamma _i$ as a function of these sizes. We then set $\delta _{i,1}$ and $\delta _{i,2}$ as $(\delta _{i,1},\delta _{i,2}) = \text {argmax}_{(\delta _1,\delta _2)} \gamma _i(\delta _1,\delta _2)$ so that $\gamma _i = \max _{(\delta _1,\delta _2)}\gamma _i(\delta _1,\delta _2)$. Unlike for the classic blinding (see Remark 1), the number of selected bits $\delta _i$ per signature can be small (it just has to be greater than $c_1$). Therefore, it is more relevant to select the signatures according to the $\gamma _i$ value in the case of the Euclidean blinding. In order to still allow several selection trials, we suggest a hybrid approach: we first randomly pick half of the available signatures and then select a subset I among them such that the values $(\gamma _i)_{i \in I}$ are the highest, and such that the constraint (37) is well (tightly) satisfied.

Computation of block probabilities. We now explain how to evaluate (39), i.e. how to evaluate the probabilities $\Pr (B_{i,1}=x)$ and $\Pr (B_{i,2}=x)$. For the sake of simplicity, we drop the index i, namely we consider a nonce $k = a\cdot r +b$ for which we know some probability score $\Pr (a_j=1)$, $\Pr (r_j=1)$ and $\Pr (b_j=1)$ for the bits of a, r, and b. Moreover, for some integer v, we shall denote $v_{[j_0:j_1]} = \lfloor \frac{v}{2^{j_0}} \rfloor \bmod 2^{j_1-j_0}$, i.e. the integer value composed of the $j_0$-th bit to the $(j_1-1)$-th bit of v. It is easy to check that the block $B_{1}=k_{[0:\delta _1]}$ only depends on the $\delta _1$ lsb of a, r and b. We can then compute the probability $\Pr (B_1=x)$ as:

$$\begin{aligned} \Pr (B_1=x) = \sum _{x,y,z} \chi _1 (x,w,y,z) \prod _{j=0}^{\delta _{1}-1}\Pr (a_{j}=w_{j})\Pr (r_{j}=y_{j})\Pr (b_{j}=z_{j}) \end{aligned}$$

(40)

with $\chi _1 (x,w,y,z) = 1$ if $x=(w\cdot y+z)_{[0:\delta _1]}$ and $\chi (x,w,y,z) = 0$ otherwise.

For the case of the block $B_2 = k_{[\ell - \delta _2:\ell ]}$, we shall denote by $a_h$ and $r_h$ the $\delta$ msb of a and r respectively for some $\delta$ (i.e. $a_h = a_{[\ell -\lambda -\delta :\ell -\lambda ]}$ and $r_h = r_{[\lambda -\delta :\lambda ]}$). We then have

$$\begin{aligned} k_{[\ell - 2 \delta :\ell ]} = a_h r_h + c \quad \text {where} \,\,\, c = \left\lfloor \frac{a \cdot r + b - a_h r_h 2^{\ell - 2 \delta }}{2^{\ell - 2 \delta }}\right\rfloor . \end{aligned}$$

(41)

It can be checked that the carry c is lower than $2^{\delta +1}$. Then if we take $\delta$ sufficiently greater than $\delta _2$, we get $\tilde{B}_2 = B_2$ with high probability, where $\tilde{B}_2$ denotes the $\delta _2$ msb of $a_h r_h$ (i.e. $\tilde{B}_2 = (a_h r_h)_{[2\delta - \delta _2 : 2\delta ]}$). We then approximate

$$\begin{aligned} \Pr (B_2 = x) \approx \Pr (\tilde{B}_2 = x) = \sum _{x_0=0}^{2^{2\delta - \delta _1}} \Pr (a_h r_h = x_0 + 2^{2 \delta - \delta _1} x) , \end{aligned}$$

(42)

where the probability mass function of $a_h r_h$ satisfies

$$\begin{aligned} \Pr (a_h r_h = x) = \sum _{w,y} \chi _2(x,w,y) \prod _{j=0}^{\delta -1}\Pr (a_{\ell -\lambda -\delta +j}=w_{j})\Pr (r_{\lambda -\delta +j}=y_{j}) \end{aligned}$$

(43)

where $\chi _2(x,w,y) = 1$ if $x = w \cdot y$ and $\chi _2(x,w,y) = 0$ otherwise.

The above approximation is sound as long as we take $\delta$ sufficiently greater than $\delta _2$. Since we have $c \le 2^{\delta +1}$, it can be checked that the approximation error is upper bounded by $2^{\delta _1 +1 - \delta }$. We shall then take $\delta$ such that the latter approximation error does not impact the selection of the maximal probability $\Pr (B_2 = x)$.

6 Experimental Results

This section provides experimental results: we have implemented our attacks against ECDSA on the ANSSI 256-bit elliptic curve (i.e. $\ell = 256$) with the two considered blinding schemes for 3 different random sizes, specifically $\lambda \in \{16,32,64\}$. We considered a three-dimensional leakage model with unbalanced multivariate SNR $\theta = \alpha \cdot (0.5, 1, 2)$, where $\alpha \in \{1.5, 2.0\}$. For each setting, the used signatures and blinded nonces were randomly generated, and the corresponding likelihood scores were simulated from the multivariate SNR $\theta$ as shown in Proposition 1. We then applied our filtering methods to select the best blocks of bits from which we constructed the Howgrave-Graham and Smart lattice with the constant $c_1$ set to 4, and we checked whether the correct solution was well retrieved by the CVP algorithm. We experimented our attacks with $n_{sig}$ available signatures and $n_{tr}$ trials for the subset selection (and the underlying lattice reduction) for $(n_{sig},n_{tr}) \in \{(10,1), (20, 5), (20, 10), (100, 10), (100, 50), (100, 100)\}$.

Table 2. Success rate of our attacks.

The obtained success rates are reported in Table 2. The lattice reduction worked almost every time the selected bits were correctly guessed (we noticed only a few lattice failures in all the performed experiments). These results suggest that the classic blinding is more sensitive to our attack than the Euclidean blinding. However, one should note that the classic blinding is inefficient when the group order is sparse. We also observe that for the Euclidean blinding, the random size $\lambda$ has a small impact on the resulting success rate, which is not surprising since it can be checked from Sect. 5 that this parameter is not expected to play a significant role.

A Using Exhaustive Search

In order to increase the success probability of our attack, we can make use of exhaustive search to guess certain bits in a signature. Specifically, we can select m bits among all the signatures for which we shall try the $2^m$ possible values and apply the previously defined lattice attack. To select the guessed bits in a signature we follow the same approach as previously but with a new dimension for the parameters: the number of bits allowed to be exhaustively guessed. Specifically, we shall compute the optimal parameters $\gamma _i, J_i$ and $N_i$ for each possible $m_i\le m_{max}$, where $m_i$ is the number of bits exhaustively guessed in the i-th signature and $m_{max}$ is the maximal value for m. We hence get a new constraint to the selection of the signatures, that is:

$$\begin{aligned} \sum _{i=0}^{n}m_i \le m_{max} . \end{aligned}$$

(44)

Let us introduce the function $\pi _i$ defined for every $J \subseteq [\![0,\ell +\lambda -1]\!]$ and $m \in \mathbb {N}$ as:

$$\begin{aligned} \pi _i(J,m) = \max _{J'\subseteq J \atop |J'| = |J|-m}\prod _{j\in J'}p_{i,j} . \end{aligned}$$

(45)

Namely, $\pi _i(J,m)$ is the maximal product of $|J|-m$ probabilities among $(p_{i,j})_{j \in J}$. This gives the probability of correctly guessing the bits $(a_{i,j})_{j \in J}$ while m among them are exhaustively guessed. We then define

$$\begin{aligned} J_i(m,N) = \mathop {\text {argmax}}\limits _{J; |J|=f(N)\atop g(J)\le N} \pi _i(J,m) \end{aligned}$$

(46)

and

$$\begin{aligned} p_i(m,N) = \pi _i(J_i(m,N),m) , \gamma _i(m,N) = p_i(m,N)^{\frac{1}{f(N)-\lambda -c_1N}} , \end{aligned}$$

(47)

from which we set

$$\begin{aligned} \gamma _i(m) = \max _{N \atop } \gamma _i(m,N) , N_i(m) = \mathop {\text {argmax}}\limits _{N \atop } \gamma _i(m,N) ,\,\, \text {and} \,\, J_i(m) = J_i(m,N_i(m)). \end{aligned}$$

(48)

Eventually, we select I and $(J_i(m_i))_{i\in I}$ such that (44) and

$$\begin{aligned} \ell \le \sum _{i\in I} |J_i(m_i)|-\lambda -c_1N_i \end{aligned}$$

(49)

are both satisfied.

Evaluating Eq. (46). We now explain how to evaluate the function

$$\begin{aligned} (m,N) \mapsto \max _{J;|J|=f(N)\atop g(J)\le N}\pi _i(J,m) , \end{aligned}$$

(50)

from which getting the argmax is then straightforward. For such a purpose, we extend the $\mathsf {maxp}$ function of Sect. 4 to deal with the m parameter i.e. the number of bits that can be exhaustively guessed. Here, $\mathsf {maxp}$ maps a quadruple $(j,\delta ,N,m)$ to the above max with the condition $J \subseteq [\![j,\ell +\lambda -1]\!]$, $|J| = \delta$, and $g(J) \le N$, so that the target function in (50) can be rewritten as:

$$\begin{aligned} (m,N) \mapsto \mathsf {maxp}(0,f(N),N, m) \end{aligned}$$

(51)

The difference with the original method is that in a recursive call to the $\mathsf {maxp}$ function, one can spend v out of m bits to be exhaustively guessed. Specifically, the recurrence relation becomes:

$$\begin{aligned} \mathsf {maxp}(j,\delta ,N,m) = \max (\mathsf {block}(j,\delta ,N,m), \mathsf {next}(j,\delta ,N,m)) \end{aligned}$$

(52)

with

$$\begin{aligned} \mathsf {block}(j,\delta ,N,m)= & {} \max _{w \in [\![1,\delta ]\!] \atop v\in \llbracket 0,m\rrbracket } \pi _i(\llbracket j, j+w-1\rrbracket ,v) \\&\quad \times \mathsf {maxp}(j+w+1,\delta -w,N-1,m-v)\\ \mathsf {next}(j,\delta ,N,m)= & {} \mathsf {maxp}(j+1,\delta ,N,m) \end{aligned}$$

The recursion tail is pretty similar to the original case:

$$\begin{aligned} \mathsf {maxp}(j,\delta ,N,m) = {\left\{ \begin{array}{ll} 0 &{} \text {if}\, j + \delta> \ell + \lambda \\ \pi _i(\llbracket j, \ell + \lambda \rrbracket , m) &{} \text {if}\, j + \delta = \ell + \lambda - 1\\ 0 &{} \text {if}\, N=0 \, \text {and}\, \delta >0 \\ 1 &{} \text {if}\, \delta = 0 \end{array}\right. } \end{aligned}$$

(53)

Only the second case changes, where the m left bits of exhaustive search are spend for the final block.