Confused yet Successful:

Abstract

Many side-channel distinguishers (such as DPA/DoM, CPA, Euclidean Distance, KSA, MIA, etc.) have been devised and studied to extract keys from cryptographic devices. Each has pros and cons and find applications in various contexts. These distinguishers have been described theoretically in order to determine which distinguisher is best for a given context, enabling an unambiguous characterization in terms of success rate or number of traces required to extract the secret key.

In this paper, we show that in the case of monobit leakages, the theoretical expression of all distinguishers depend only on two parameters: the confusion coefficient and the signal-to-noise ratio. We provide closed-form expressions and leverage them to compare the distinguishers in terms of convergence speed for distinguishing between key candidates. This study contrasts with previous works where only the asymptotic behavior was determined—when the number of traces tends to infinity, or when the signal-to-noise ratio tends to zero.

1 Introduction

Today’s ciphering algorithms such as AES are considered resistant to cryptanalysis. This means that the best possible way to extract a 128-bit key is about as complex as an exhaustive search over the $2^{128}$ possibilities. With our current computational power, this is not achievable within a reasonable amount of time.

However, it is possible to use plaintexts, ciphertexts, along with additional side information in order to recover the secret key of a device. Indeed, the secret key may leak via side-channels, such as the time to compute the algorithm, the power consumption of the device during the computation of the algorithm, or the electro-magnetic radiations of the chip.

In order to secure chips from side-channel attacks, designers have to understand how these work and what could be the future security breaches in the cryptographic algorithm as well as in the hardware implementation. A preliminary step is to identify how the secret keys leak and deduce leakage models. Then, mathematical functions—called distinguishers—take the leakage as argument and return an estimation of the secret key. Such distinguishers come in many flavours¹ and have different figures of merit in different contexts. A given context not only involves the cryptographic algorithm and the device through the leakage model, but also the side-channel acquisition setup through the measurement characterized by its signal-to-noise ratio (SNR). This is illustrated in Fig. 1 borrowed from Heuser et al. [12] (with our annotations ).

Fig. 1.

Illustration of the two parts of the side-channel analysis context (). (Color figure online)

In practice one may encounter monobit leakages. This means that the output of the leakage model can only take two values. In this case, as we shall see, the mathematical computations turn to be simpler and information theoretic tools can be used to precisely describe the link between the leakage model and the real-world leaking traces. From another perspective, considering monobit leakages can also be seen as an “abstraction” trick meant to intentionally ignore the complex effect of the way the device leaks, thereby keeping only the contribution from the cryptographic algorithm in the leakage model.

A related question is how the choice of the substitution box in the cryptographic algorithm may “help” the attacker. The standard AES substitution box was designed to be very secure against linear and differential cryptanalysis [6]. On the contrary, under side-channel analysis, the substitution box may be helpful for the attacker, especially for monobit leakages as shown below.

Related Work. Distinguishers were often studied empirically, yet such an approach does not allow for generalizations to other contexts and measurement campaigns. A theoretical approach consists in analyzing the formal expressions of the distinguishers as mathematical functions. Fei et al. [8] have shown that distinguishers such as DoM and CPA can be expressed in terms of a confusion coefficient. They gave the impetus to extend this formal analysis to other types of distinguishers. In 2014, Heuser et al. [11] relate KSA to the confusion coefficient, and also noticed that the confusion coefficient can be related to the resistance of a substitution box against differential cryptanalysis.

Whitnall and Oswald [21] have proposed the relative distinguishing margin metric to compare distinguishers. However, it has been shown [18] that this metric may not be relevant in all contexts. Another way to compare distinguishers is to contrast how their success rate (SR) in key recovery depends on the number q of side-channel traces. Works such as [8, 14] provide mathematically models for the SR. But the comparison between different distinguishers has never been actually carried out based on such frameworks. Instead, we shall leverage on the so-called success exponent (SE) [10] which allows to compare the SR of various distinguishers based on only one exponent parameter.

Our Contributions. In this paper, we consolidate the knowledge about side-channel attacks exploiting monobit leakages. We provide a rigorous proof that any distinguisher acting on monobit leakages depends only on two parameters: the confusion coefficient and the noise variance. Some distinguishers, namely DoM, CPA and KSA, have already been expressed as a function of those two parameters [8, 11]. In this article, we derive this expression for MIA and we obtain a simple analytic function when the non zero values of the confusion coefficient are near , which is the case of leakages occurring at cryptographically strong substitution boxes [4].

We derive the success exponent of these distinguishers in terms of the confusion coefficient and the standard deviation of the noise. Success exponents allow to characterize the efficiency (in terms of number of traces) of distinguishers to recover the key. Our closed-form expressions of the success exponent enable the comparison of distinguishers based only on these two parameters. The flow chart of Fig. 2 situates our contributions in relation to the current state of the art.

Organization. The remainder of this paper is organized as follows. In Sect. 2, we recall the main definitions. In Sect. 3, we consider all distinguishers in one mathematical framework and we show that they are only functions of two parameters. In Sect. 4, we compare the distinguishers in terms of the success exponent. Section 5 concludes. Appendices provide proofs for technical lemmas.

Fig. 2.

The state of the art in relation to our contributions (in yellow boxes—see also Tables 1 and 2 below). (Color figure online)

Notations. Throughout this paper, we use calligraphic letters to denote sets and lower-case letters for elements in this set (e.g. $x\in \mathcal {X}$). Capital letters denote random variables. For example, X is a random variable taking values in $\mathcal {X}$ and $x\in \mathcal {X}$ is a realization of X. The probability that X is x is noted $\mathbb {P}(X=x)$ or simply $\mathbb {P}(x)$ when there is no ambiguity. The expectation of a random variable is noted $\mathbb {E}[X]$ and its variance $\mathrm {Var}(X)$. The differential entropy h(X) of a random variable X following distribution p(x) is defined as

$$\begin{aligned} h(X) = -\int _{\mathbb {R}} p(x)\log _2 p(x) \,\mathrm {d}x. \end{aligned}$$

(1)

The mutual information between two random variables X and Y is defined as

$$\begin{aligned} I(X;Y) = h(X)-h(X|Y) = \mathbb {E}\biggl [\log _2 \frac{\mathbb {P}(X,Y)}{\mathbb {P}(X)\mathbb {P}(Y)} \biggr ]. \end{aligned}$$

(2)

2 Modelization and Definitions

2.1 The Leakage Model

In order to compare the different distinguishers for monobit leakages, we need a leakage model upon which our computations will be based. A plaintext t meets the secret key $k^*$ through a leakage function $f(t,k^*)$. The resulting variable $y(k^*)$ is called the sensitive variable. The dependence in the plaintext t will be omitted to make equations easier to read when there is no ambiguity.

The attacker measures a noisy version of $y(k^*)$ called trace and denoted by x. When the key is unknown, the attacker computes a sensitive variable with a key hypothesis k, that is, $y(k)= f(t,k)$. Thus our model takes the form

(3)

where n is an independent measurement noise.

As we consider monobit leakages, we suppose that y(k) can take only two values. In practice, t (resp. k) are subsets of the full plaintext (resp. key). Typically, in the case of AES where attacks can be conducted using a divide-and-conquer approach on a per substitution box basis, t and k are 8-bit works (i.e., bytes).

The above leakage model can also be written using random variables. Let T the random variable for the plaintext, Y(k) for the sensitive variable, X for the measurement, and N for the Gaussian noise. We have:

(4)

In a view to simplify further mathematical computations, we suppose that the leakage random variable is reduced, that is, centered ($\mathbb {E}[Y(k)]=0$ for all k) and of unit variance ($\mathbb {E}[Y(k)^2]=1$ for all k). The noise is also assumed Gaussian of zero mean and its standard deviation is noted $\sigma >0$. Moreover, we assume that for any key hypothesis the sensitive variable is balanced, that is, $\mathbb {P}(y(k))=\frac{1}{2}$. Since Y(k) is a binary random variable, we necessarily have that $Y(k)\in \{\pm 1\}$ in our model, and consequently the signal-to-noise ratio equals $\textsf {SNR}=1/\sigma ^2$.

Last, we suppose that the attacker has at his disposal a number of q traces $x_1,\ldots ,x_q$ obtained from leaking sensitive variables $y_1(k^*), \ldots , y_q(k^*)$ under additive noise $n_1, \ldots ,n_q$.

2.2 The Confusion Coefficient

In the side-channel context, the confusion coefficient was defined by Fei et al. as the probability that two sensitive variables arising from two different key hypotheses are different [8, Section 3.1]. Mathematically, the confusion coefficient is written as

$$\begin{aligned} \kappa (k,k^*) = \mathbb {P}(Y(k) \ne Y(k^*)). \end{aligned}$$

(5)

As the secret key $k^*$ is constant and understood from the context, we can write $\kappa (k,k^*) = \kappa (k)$. Notice that in practical situations, the EIS (Equal Images under different Subkeys [20, Def. 2]) assumption holds, therefore $\kappa$ is actually a function of the key bitwise XOR difference $k\oplus k^*$.

Figure 3 illustrates the confusion coefficient for a monobit leakage $Y(k) = \mathsf {SubBytes}(T\oplus k) \bmod 2$, where SubBytes is the AES substitution box (application $\mathbb {F}_2^8\rightarrow \mathbb {F}_2^8$) and $\oplus$ is the bitwise exclusive or. We notice that except for $k = k^*$ (here taken $= 178= \mathtt {0xb2}$), the confusion coefficient for the AES SubBytes is close to . This results from the fact the AES SubBytes has been designed to be resistant against differential cryptanalysis. Specifically, Heuser et al. [11, Proposition 6] noticed that a “good” substitution box leads to confusion coefficients near .

Fig. 3.

Confusion coefficient for the AES SubBytes Least Significant Bit (LSB)

The original definition of the confusion coefficient [8] considers only monobit leakages. An extension for any type of leakage was proposed in [10] where $\kappa (k)$ is defined by

$$\begin{aligned} \kappa (k) = \mathbb {E}\biggl [ \Bigl (\frac{Y(k^*) - Y(k)}{2} \Bigr )^2 \biggr ]. \end{aligned}$$

(6)

Equation (5) can be easily recovered from this more general expression by noting that when Y(k) and $Y(k^*)\in \{\pm 1\}$, $\bigl (\frac{Y(k^*) - Y(k)}{2} \bigr )^2$ is 0 or 1 according to whether $Y(k) = Y(k^*)$ or $Y(k) \ne Y(k^*)$.

2.3 Distinguishers

Distinguishers aim at recovering the secret key $k^*$ from the traces and the model. For every key k, the attacker computes the associated distinguisher. The key hypothesis that gives the highest value of the distinguisher is the estimated key. The attack is successful if the estimated key is equal to the secret key.

For every key hypothesis k, a distinguisher is noted $\widehat{\mathcal {D}}(k)$ and the estimated key is $\widehat{k} = \arg \max _k \widehat{\mathcal {D}}(k)$. Five classical distinguishers are:

• Difference of Means (DoM) [8], also known as the Differential Power Analysis (DPA) [13] where the attacker computes

  $$\begin{aligned} \widehat{\mathcal {D}}(k) = \frac{\sum _{i|y_i(k)=+1}x_i}{\sum _{i|y_i(k)=+1}} - \frac{\sum _{i|y_i(k)=-1}x_i}{\sum _{i|y_i(k)=-1}}. \end{aligned}$$

  (7)

• Correlation Power Analysis (CPA) [3] where the attacker computes the absolute value of the Pearson coefficient

  $$\begin{aligned} \widehat{\mathcal {D}}(k) =\biggl | \frac{\frac{1}{q}\sum _{i=1}^q x_i y_i(k) - \frac{1}{q}\sum _{i=1}^q x_i \cdot \frac{1}{q}\sum _{i=1}^q y_i(k)}{\sqrt{\mathrm {Var}(X)\mathrm {Var}(Y_i(k))}} \biggr |. \end{aligned}$$

  (8)

  Notice that $\mathrm {Var}(Y_i(k))$ do not depend on the index i, since repeated measurements are i.i.d.

• Euclidean distance, which corresponds to the Maximum Likelihood (ML) attack under the Gaussian noise hypothesis, where the attacker actually computes the negative Euclidean distance between the model and the trace

  $$\begin{aligned} \widehat{\mathcal {D}}(k) = -\frac{1}{q} \sum _{i=1}^q (x_i - y_i(k))^2. \end{aligned}$$

  (9)

  Maximizing the value of the distinguisher amounts to minimizing the Euclidean distance. According to [12], as the noise is Gaussian and additive, the Euclidean distance is the optimal distinguishing rule (ML rule) that maximizes the success probability.

• Kolmogorov-Smirnov Analysis (KSA) [22] where the traces are used to build an estimation of the cumulative density function $\widehat{F}(x)$, and the distinguisher is

  $$\begin{aligned} \widehat{\mathcal {D}}(k) = -\mathbb {E}_{Y(k)} \bigl [ \Vert \widehat{F}(x|Y(k)) - \widehat{F}(x) \Vert _{\infty } \bigr ] \end{aligned}$$

  (10)

  where the infinite norm is defined as $\Vert \widehat{F}(x) \Vert _{\infty } = \sup _x |\widehat{F}(x) |$. Maximizing the value of the distinguisher amounts to minimizing the expected infinite norm.

• Mutual Information Analysis (MIA) [9] where the attacker computes the mutual information between the traces and each model. The traces are used to build an estimation of the joint distribution of X and Y(k), denoted by $\widehat{p}(X,Y(k))$, and with this estimation, we calculate the mutual information

  $$\begin{aligned} \widehat{\mathcal {D}}(k) = \sum _{x,y(k)}\widehat{p}(x,y(k))\log _2\frac{\widehat{p}(x,y(k))}{\widehat{p}(x)\cdot \widehat{p}(y(k))}. \end{aligned}$$

  (11)

Given the available data, the attacker computes the distinguisher as a function of $x_1,\ldots ,x_q$ and $y_1(k),\ldots ,y_q(k)$. To emphasize the dependence on the data, we may write $\widehat{\mathcal {D}}(k)=\widehat{\mathcal {D}}(X_1,\ldots ,X_q,Y_1(k),\ldots ,Y_q(k))$. As these traces are realizations of random variables, we may also consider $\widehat{\mathcal {D}}(k)$ as a random variable which is a function of $X_1,\ldots ,X_q$ and $Y_1(k),\ldots ,Y_q(k)$, with expectation $\mathbb {E}[\widehat{\mathcal {D}}(k)]$ and a variance $\mathrm {Var}(\widehat{\mathcal {D}}(k))$.

When the number of queries q tends to infinity, we assume that the distinguisher converges in the mean-squared sense:

Definition 1

(Theoretical Distinguisher [10]). The theoretical value of the distinguisher is defined as the limit in the mean square sense when $q\rightarrow \infty$ of the distinguisher. The notation for the theoretical distinguisher is $\mathcal {D}(k)$, which is therefore implicitly defined as:

$$\begin{aligned} \mathbb {E}[ (\widehat{\mathcal {D}}(k) - \mathcal {D}(k))^2] \longrightarrow 0\text { as } q\rightarrow \infty . \end{aligned}$$

(12)

Put differently, $\widehat{\mathcal {D}}(k)$ can be seen as an estimator of $\mathcal {D}(k)$. It is easily seen that as $q\rightarrow +\infty$ the distinguishers presented previously have the following theoretical distinguishers:

• For DoM, the theoretical distinguisher is

  $$\begin{aligned} \mathcal {D}(k) = \mathbb {E}[XY(k)]. \end{aligned}$$

  (13)

• For CPA, the theoretical distinguisher is

  $$\begin{aligned} \mathcal {D}(k) = \frac{\bigl | \mathbb {E}[XY(k)] - \mathbb {E}[X]\mathbb {E}[Y(k)] \bigr |}{1+\sigma ^2}. \end{aligned}$$

  (14)

• For Euclidean distance (ML) distinguisher, we have:

  $$\begin{aligned} \mathcal {D}(k) = -\mathbb {E}\bigl [(X-Y(k))^2 \bigr ]. \end{aligned}$$

  (15)

• For KSA, we have:

  $$\begin{aligned} \mathcal {D}(k) = \mathbb {E}_{Y(k)} \bigl [ \Vert F(x|Y(k)) - F(x) \Vert _{\infty } \bigr ]. \end{aligned}$$

  (16)

• For MIA, it is the mutual information

  $$\begin{aligned} \mathcal {D}(k)=I(X;Y(k)). \end{aligned}$$

  (17)

3 Theoretical Expressions for Distinguishers

In this section, we show that all distinguishers for monobit leakages are functions of only two parameters: the confusion coefficient $\kappa (k)$ and the $\textsf {SNR}=1/\sigma ^2$. This is confirmed by the closed-form expressions for classical distinguishers. In particular we derive the one corresponding to MIA.

3.1 A Communication Channel Between Y(k) and $Y(k^*)$

To understand the link between any sensitive variable Y(k) and the leaking sensitive variable $Y(k^*)$, consider the following information-theoretic communication channel between these two variables described in Fig. 4. This communication channel is simply a theoretical construction that helps explain the link between Y(k) and $Y(k^*)$, which are both binary and equiprobable random variables taking their values in $\{\pm 1\}$. The parameters p and $p'$ are the transition probabilities defined as $p = \mathbb {P}(Y(k^*)=+1 | Y(k) = -1)$ and $p'=\mathbb {P}(Y(k^*) = -1 | Y(k) = +1)$.

Lemma 1

The communication channel defined in Fig. 4 is a binary symmetric channel (BSC) with transition probability equal to the confusion coefficient $\kappa (k)$.

Fig. 4.

Abstract communication channel between Y(k) and $Y(k^*)$

Proof

To prove that the channel is symmetric, we show that both transition probabilities coincide: $p=p'$. In fact, from Fig. 4, $\tfrac{1}{2} = \mathbb {P}(Y(k^*)=1) = p\mathbb {P}(Y(k) = -1) + (1-p')\mathbb {P}(Y(k) = 1) = \tfrac{1}{2}(p+1-p')$ hence $p=p'$. Now the confusion coefficient $\kappa (k) = \mathbb {P}(Y(k) \ne Y(k^*))$ can be expanded as

$$\begin{aligned} \kappa (k)&= \tfrac{1}{2}\bigl ( \mathbb {P}(Y(k) \ne Y(k^*) | Y(k) = 1) + \mathbb {P}(Y(k) \ne Y(k^*) | Y(k) = -1) \bigr ) \end{aligned}$$

(18)

$$\begin{aligned}&= \tfrac{1}{2}\bigl ( \mathbb {P}(Y(k^*) =-1 | Y(k) = 1) + \mathbb {P}(Y(k^*) = 1 | Y(k) = -1) \bigr ) \end{aligned}$$

(19)

$$\begin{aligned}&= \tfrac{1}{2}\bigl ( p + p' \bigr ) = p = p' . \end{aligned}$$

(20)

This proves that the BSC has transition probability equal to $\kappa (k)$.    $\square$

According to a well-known information theoretic result [5, p. 187], the Shannon’s capacity in bits per bit of this channel is

$$\begin{aligned} \mathcal {C} = 1 - H_2(\kappa (k)), \end{aligned}$$

(21)

where $H_2(x)$ is the binary entropy function defined by

$$\begin{aligned} H_2(x) = x\log _2 \Bigl (\frac{1}{x} \Bigr ) + (1-x)\log _2 \Bigl (\frac{1}{1-x} \Bigr ). \end{aligned}$$

(22)

This is represented in Fig. 5 as a function of $\kappa (k)$. Interestingly, the value corresponds to null capacity while the capacity is evidently 1 bit per bit for $\kappa (k^*)=0$, since in this case the above communication channel reduces to the identity.

3.2 A General Result

We can now explain why all distinguishers for monobit leakages depend only on the two parameters $\kappa (k)$ and $\mathsf {SNR}=\sigma ^{-2}$.

Fig. 5.

Representation of the channel capacity according to $\kappa (k)$

Theorem 1

Any theoretical distinguisher $\mathcal {D}(k)$ for a binary leakage y can be expressed as a function of $\kappa (k)$ and $\sigma$.

Proof

Any theoretical distinguisher is defined in terms of the joint probability distribution of X and Y(k), noted p(x, y(k)). Now for any $x\in \mathbb {R}$ and $y(k) =\pm 1$,

$$\begin{aligned} p(x,y(k))&= \mathbb {P}(y(k))\;p(x \mid y(k)) \end{aligned}$$

(23)

$$\begin{aligned}&= \frac{1}{2}p(y(k^*) + n \mid y(k)) \end{aligned}$$

(24)

$$\begin{aligned}&= \frac{1}{2}\sum _{y(k^*)}p(y(k^*) + n \mid y(k),y(k^*))\;\mathbb {P}(y(k^*)\mid y(k)) \end{aligned}$$

(25)

where $\mathbb {P}(y(k^*)\mid y(k))$ is the transition probability of the channel defined in Fig. 4. There are two possibilities. Either $y(k) = y(k^*)$, and in this case $\mathbb {P}(y(k^*)|y(k)) = 1 - \kappa (k)$, or $y(k) \ne y(k^*)$ and in this case $\mathbb {P}(y(k^*) | y(k)) = \kappa (k)$. The sum over $y(k^*)$ has two terms and both cases are represented. Moreover, the Gaussian noise is independent from every other random variable. Therefore, we have two possibilities for the joint probability:

$$\begin{aligned} p(x,y(k)) = {\left\{ \begin{array}{ll} \frac{1}{2} \Bigl ( \phi ( \frac{1+n}{\sigma })\kappa (k) + \phi (\frac{-1+n}{\sigma })(1-\kappa (k)) \Bigr ) \\ \frac{1}{2} \Bigl ( \phi (\frac{-1+n}{\sigma })\kappa (k) + \phi ( \frac{1+n}{\sigma })(1-\kappa (k)) \Bigr ) \end{array}\right. } \end{aligned}$$

(26)

where $\phi (x)$ is the probability density function of a standard normal random variable. As the noise is centered and Gaussian, the only parameter that characterizes $\phi$ is its standard deviation $\sigma$. Therefore, a joint distribution of a monobit leakage is fully characterized by $\sigma$ and $\kappa (k)$.    $\square$

This proves that the knowledge of the confusion coefficient and the noise power are essential to predict the performances of the side-channel attacks for monobit leakages.

3.3 Classical Distinguishers as Functions of $\kappa (k)$ and $\sigma ^2$

To highlight the result of Sect. 3.2, we compute the classical distinguishers according to the confusion coefficient and the noise power. As we mentioned in the introduction, some of them have already been expressed according to these variables: we recall these results in Table 1 with references to the articles where the expression of the distinguisher in terms of $\kappa (k)$ is proven.

Table 1. Summary of classical distinguishers. Among all the classical theoretical distinguishers, we notice that the expression of the theoretical value of DoM with $\kappa (k)$ does not depend on $\sigma$.

The new results are given by the following lemmas.

Lemma 2

For monobit leakages, the Euclidean distance distinguisher can be expressed as:

(27)

Proof

We have $\mathcal {D}(k) = -\mathbb {E}\bigl [ (X - Y(k))^2 \bigr ]=-\mathbb {E}\bigl [ (Y(k^*) - Y(k)+N)^2 \bigr ]=-\mathbb {E}\bigl [ (Y(k^*) - Y(k))^2 \bigr ]-\sigma ^2$ since the noise is independent from $Y(k^*) - Y(k)$. Then by (6), where we have stressed the dependence in $\nicefrac 12 - \kappa (k)$ as in Table 1.    $\square$

Lemma 3

For monobit leakages, when for $k\ne k^*$, the MIA distinguisher can be expressed at first order as:

(28)

where

$$\begin{aligned} g(\sigma ) = \frac{1}{2} \mathbb {E}\Bigl [ \tanh ^2 \Bigl (\frac{Z}{\sigma }+\frac{1}{\sigma ^2} \Bigr ) + \tanh ^2 \Bigl ( \frac{Z}{\sigma } - \frac{1}{\sigma ^2} \Bigr ) \Bigr ] \end{aligned}$$

(29)

and $Z\sim \mathcal {N}(0,1)$. The function g satisfies

$$\begin{aligned} \lim _{\sigma \rightarrow 0} g(\sigma ) = 1 \qquad \text {and}\qquad \lim _{\sigma \rightarrow \infty } \sigma ^2\times g(\sigma ) = 1. \end{aligned}$$

(30)

Proof

See Appendix A.    $\square$

Figure 6 plots the shape of $g(\sigma )$ which tends to 1 when $\sigma \rightarrow 0$ and is equivalent to $\frac{1}{\sigma ^2}$ when $\sigma \rightarrow \infty$.

When $k=k^*$ the MIA distinguisher also has a simple expression since it reduces to the known expression of the channel capacity for channels with binary input and additive Gaussian noise [2, p. 274]:

$$\begin{aligned} \mathcal {D}(k^*) = \frac{1}{\sigma ^2} - \int _{\mathbb {R}}\frac{e^{-\frac{1}{2}y^2}}{2\pi }\log _2\cosh (\frac{1}{\sigma ^2}-\frac{y}{\sigma ^2})\mathrm {d}y. \end{aligned}$$

(31)

Fig. 6.

Representation of $g(\sigma )$

Remark 1

With respect to their theoretical distinguishers, DoM is in bijection with the Euclidean distance, and CPA is in bijection with KSA. Indeed, the Euclidean distance is and $\sigma$ is independent from the choice of the key. Therefore, there is a bijection between and which is the theoretical value of DoM. Regarding CPA and KSA, both distinguishers are functions of .

We also notice that MIA is in bijection with CPA (and therefore KSA). Indeed, according to the value of MIA with $\kappa (k)$, the distinguisher is a function of which is in bijection with . This means that for monobit leakages, any attack that works with one of these distinguishers will also work with another, and vice versa.

4 Comparing Distinguishers with the Success Exponent

In the previous section, we have computed the theoretical values of the classical distinguishers in terms of $\kappa (k)$ and $\sigma$. Now, we wish to compare their success rate. As we mentioned Sect. 2.3, the attacker computes the estimated distinguisher $\widehat{\mathcal {D}}(k)$ to recover the secret key. This is the main reason why all distinguishers do not perform equally in key recovery; indeed, they do not converge at the same speed towards their theoretical value.

In order to compare them, we have computed their success exponent, a metric proposed by Guilley et al. in [10] that evaluates how fast the success rate of a distinguisher converges to 100%. With a Gaussian assumption, they prove that the success rate can be modeled as

$$\begin{aligned} \mathsf {SR} = 1 - \exp (-q\times \mathsf {SE}) , \end{aligned}$$

(32)

where q is the number of traces and $\textsf {SE}\in \mathbb {R}^+$ is the so-called success exponent. Therefore, the greater the success exponent is, the faster the convergence of the success rate.

Table 2. Success exponents for the classical distinguishers. The numerical values of SE are obtained for AES SubBytes least significant bit leakage model and noise of standard deviation $\sigma =4$. Notice that in the monobit case, Euclidean distance and DoM have strictly the same success rate because $-(X-Y(k))^2 = -X^2 + 2XY(k) -1$, and $X^2$ is independent of the choice of the key.

We present the theoretical values of the success exponent for the different distinguishers in Table 2. As a direct consequence of Theorem 1, all of these success exponents are function of $\kappa (k)$ and $\sigma$. Therefore, if the attacker only knows the type of substitution box that is used and the SNR of the leakage, he can predict how fast he recovers the secret key.

Lemma 4

(Success exponent of CPA). The success exponent of CPA² is:

(33)

Proof

See Appendix B.    $\square$

Lemma 5

(Success exponent of KSA). Assuming that the distributions are estimated with the kernel method using Heaviside step function, the success exponent of KSA is

(34)

Proof

See Appendix C.    $\square$

Lemma 6

(Success exponent of MIA). When $\sigma \gg 1$, the success exponent for an MIA computed with histograms is

$$\begin{aligned} \mathsf {SE} = \frac{4\log _2(e)^2}{\sigma ^4}\min _{k\ne k^*} \kappa (k)^2(1-\kappa (k))^2. \end{aligned}$$

(35)

Fig. 7.

Success rate for classical distinguishers ($\sigma = 4$)

Proof

See Appendix D.    $\square$

In order to validate our theoretical results, we have simulated attacks within the monobit model presented in Sect. 2. The success rates of these attacks are presented in Fig. 7. In this figure, we notice that, as expected, the Euclidean distance (ML) is the best distinguisher, closely followed by CPA. Both have similar same success rate. The small difference is due to the use the the absolute values in the distinguishing function of CPA (see discussion in Remark 9 of [12]). The KSA is requiring a bit less than the double of traces, compared to Euclidean distance, DoM and CPA. The MIA performs really bad compared to the other distinguishers. Error bars represent the inaccuracy while estimating the SR (here, we ran 100 simulations).

These simulations are therefore in complete coherence with the theoretical results of Table 2. Indeed, the order of the distinguishers is the same w.r.t. the success rate and w.r.t. the success exponent. In addition, according to the definition of the success exponent $\mathsf {SE}$ in (32), the number of traces q to reach a given success rate (e.g., $\mathsf {SR}=80\%$) is proportional to the inverse of $\mathsf {SE}$. This quantitative law is satisfied in the simulation of Fig. 7.

5 Conclusion

In this paper, we have mathematically proven that only two parameters, the confusion coefficient and the SNR, determine the side-channel distinguishing efficiency for monobit leakages. Both of them are easy to compute because the confusion coefficient can be calculated with the knowledge of the operating substitution box and the SNR can be measured offline.

Our work is useful to predict how fast a distinguisher will succeed to recover the secret key. Long and painful simulations can be advantageously replaced by the computation of the success exponent using closed-form expressions.

This paper also consolidates the state of the art about the classical distinguishers, especially for MIA and KSA. We have derived the success exponent for these two distinguishers as a function of the confusion coefficient and the standard deviation of the noise.

Appendices

A Proof of Lemma 3

The MIA distinguisher is expressed as

$$\begin{aligned} \mathcal {D}(k) =I(Y(k^*)+N;Y(k))= h( Y(k^*) + N ) - h(Y(k^*) + N \mid Y(k)). \end{aligned}$$

(36)

From Sect. 3.1, $Y(k^*)$ knowing Y(k) is a binary random variable with probability $\kappa (k)$. As N is Gaussian independent from Y(k), the pdf of $Y(k^*) + N$ knowing Y(k) is a Gaussian mixture that can take two forms:

$$\begin{aligned} p_{\kappa (k)}(x)= {\left\{ \begin{array}{ll} \frac{1}{\sqrt{2\pi }\sigma }[ \kappa (k) e^{-\frac{(x-1)^2}{2\sigma ^2}} + (1-\kappa (k)) e^{-\frac{(x+1)^2}{2\sigma ^2}} ] \\ \frac{1}{\sqrt{2\pi }\sigma }[ \kappa (k) e^{-\frac{(x+1)^2}{2\sigma ^2}} + (1-\kappa (k)) e^{-\frac{(x-1)^2}{2\sigma ^2}} ] \end{array}\right. }, \end{aligned}$$

(37)

By symmetry, their entropy $h(Y(k^*) + N \mid Y(k))$ will be the same and we can take any of these pdfs. Letting $\phi$ be the standard normal density, we can write

$$\begin{aligned} p_{\kappa (k)}(x)&= p_{1/2}(x) - 2(1/2 - \kappa (k)) \phi (x) e^{-\frac{1}{\sigma ^2}}\sinh (\frac{x}{\sigma ^2}) \end{aligned}$$

(38)

$$\begin{aligned}&= p_{1/2}(x)(1 - 2(1/2 - \kappa (k))\tanh (\frac{x}{2\sigma ^2}). \end{aligned}$$

(39)

where

$$\begin{aligned} p_{1/2}(x) = \frac{1}{2\sqrt{2\pi }\sigma }[ e^{-\frac{(x-1)^2}{2\sigma ^2}} + e^{-\frac{(x+1)^2}{2\sigma ^2}} ] = \frac{1}{\sigma }e^{-\frac{1}{2\sigma ^2}}\phi (\frac{x}{\sigma })\cosh (\frac{x}{\sigma ^2}). \end{aligned}$$

(40)

For notational convenience define $\epsilon = 2(1/2 - \kappa (k))$, $p=p_{1/2}(x)$, and $t=\tanh (x)$. Then

$$\begin{aligned} I(X;Y(k))&=h( Y(k^*) + N ) - h(Y(k^*) + N \mid Y(k))\end{aligned}$$

(41)

$$\begin{aligned}&= -\int p\log _2 p + \int (p(1 - \epsilon t)) \log _2(p(1 - \epsilon t)) \end{aligned}$$

(42)

$$\begin{aligned}&= -\int \epsilon p t \log _2 p + \int p \log _2(1 - \epsilon t) - \int p\epsilon t \log _2(1-\epsilon t). \end{aligned}$$

(43)

The first term vanishes since p is even and t odd. We apply a Taylor expansion:

$$\begin{aligned} I(X;Y(k)) = \int p[-\epsilon t - \frac{\epsilon ^2 t^2}{2} - \frac{\epsilon ^3 t^3}{3} + O(\epsilon ^4) ] - \int \epsilon p t [-\epsilon t - \frac{\epsilon ^2 t^2}{2} - \frac{\epsilon ^3 t^3}{3} + O(\epsilon ^4) ]. \end{aligned}$$

(44)

The odd terms of the expansion are null as t is odd and p even. We therefore obtain:

$$\begin{aligned} I(X;Y(k)) = \int p[ - \frac{\epsilon ^2 t^2}{2} + O(\epsilon ^4) ] - \int [-\epsilon ^2 pt^2 + O(\epsilon ^4) ] = \int \frac{\epsilon ^2 p t^2}{2} + O(\epsilon ^4). \end{aligned}$$

(45)

Thus, finally,

$$\begin{aligned} \mathcal {D}(k) = 2\log _2(e)(1/2 - \kappa (k))^2g(\sigma ), \end{aligned}$$

(46)

where

$$\begin{aligned} g(\sigma ) =\frac{1}{\sigma } e^{-\frac{1}{2\sigma ^2}}\int _{\mathbb {R}} \phi (\frac{x}{\sigma })\cosh (\frac{x}{\sigma ^2})\tanh ^2(\frac{x}{\sigma ^2})\mathrm {d}x. \end{aligned}$$

(47)

There are several ways to express $g(\sigma )$. For example, we have:

$$\begin{aligned} g(\sigma ) = e^{-\frac{1}{2\sigma ^2}}\int _{\mathbb {R}} \phi (x)\cosh (\frac{x}{\sigma })\tanh ^2(\frac{x}{\sigma })\mathrm {d}x. \end{aligned}$$

(48)

This expression can be reduced to:

$$\begin{aligned} g(\sigma ) = \frac{1}{2}\mathbb {E}_X \left[ \tanh ^2(\frac{X}{\sigma }+ \frac{1}{\sigma ^2}) + \tanh ^2(\frac{X}{\sigma }- \frac{1}{\sigma ^2}) \right] , \end{aligned}$$

(49)

where $X\sim \mathcal {N}(0,1)$. By the dominated convergence theorem ($\tanh ^2(\frac{X}{\sigma }+ \frac{1}{\sigma ^2})$ is always smaller than 1) when $\sigma \rightarrow 0$, we obtain $g(0)=1$ and when $\sigma \rightarrow \infty$ we obtain the equivalent $\frac{1}{\sigma ^2}$.

B Proof of Lemma 4

The success exponent is defined by

$$\begin{aligned} \mathsf {SE} = \frac{\mathbb {E}[\widehat{\mathcal {D}}(k^*) - \widehat{\mathcal {D}}(k)]^2}{2\mathrm {Var}(\widehat{\mathcal {D}}(k^*) - \widehat{\mathcal {D}}(k))}. \end{aligned}$$

(50)

where in our case

$$\begin{aligned} \widehat{\mathcal {D}}(k) = \frac{1}{q\sqrt{1+\sigma ^2}} \Bigl |\sum _{i=1}^q X_i Y_i(k) \Bigr |. \end{aligned}$$

(51)

First for large q we can consider that $\mathbb {E}[|\sum _i X_iY_i(k)|] = |\mathbb {E}[\sum _i X_iY_i(k)]|$.

(52)

hence

(53)

Secondly we have

$$\begin{aligned} \mathrm {Var}(\widehat{\mathcal {D}}(k^*) - \widehat{\mathcal {D}}(k)) = \frac{1}{q^2(1+\sigma ^2)}\mathrm {Var}\Bigl ( \Bigl |\sum _{i=1}^q X_i Y_i(k^*) \Bigr | - \Bigl |\sum _{i=1}^q X_i Y_i(k) \Bigr | \Bigr ). \end{aligned}$$

(54)

To remove the absolute values, we distinguish two cases whether the sum is positive or negative. We consider that q is large enough to have strictly positive or negative values.

$$\begin{aligned} \mathrm {Var}(\widehat{\mathcal {D}}(k^*) - \widehat{\mathcal {D}}(k))&= \frac{1}{q^2(1+\sigma ^2)}\mathrm {Var}\Bigl ( \sum _{i=1}^q X_i Y_i(k^*) \mp \sum _{i=1}^q X_i Y_i(k) \Bigr ) \end{aligned}$$

(55)

$$\begin{aligned}&= \frac{1}{q^2(1+\sigma ^2)}\mathrm {Var}\Bigl ( \sum _{i=1}^q X_i \bigl (Y_i(k^*) \mp Y_i(k) \bigr ) \Bigr ) \end{aligned}$$

(56)

$$\begin{aligned}&= \frac{1}{q(1+\sigma ^2)}\mathrm {Var}\bigl ( X \bigl (Y(k^*) \mp Y(k) \bigr ) \bigr ) \end{aligned}$$

(57)

$$\begin{aligned}&= \frac{1}{q(1+\sigma ^2)}\mathrm {Var}\bigl ( (Y(k^*) + N) \bigl (Y(k^*) \mp Y(k) \bigr ) \bigr ) \end{aligned}$$

(58)

$$\begin{aligned}&= \frac{1}{q(1+\sigma ^2)}\mathrm {Var}\bigl ( \mp Y(k^*)Y(k) +N(Y(k^*) \mp Y(k)) \bigr ). \end{aligned}$$

(59)

The variance term is the difference of the two following quantities

(60)

(61)

Combining all the above expressions we obtain (33).

C Proof of Lemma 5

To prove the success rate of KSA, we first need an estimator for the cumulative density function. We take as kernel a function $\varPhi$ as simple as possible i.e. the Heaviside function $\varPhi (x)=0$ if $x<0$ and $\varPhi (x)=1$ if $x\ge 0$.

With this function and for $x\in \mathbb {R}$, we can estimate $F(x|Y(k) = 1) - F(x)$ by the following estimator:

$$\begin{aligned} \tilde{F}(x |Y(k) = 1) - \tilde{F}(x) = \frac{\sum _{i|Y_i(k)=1}\varPhi (x-X_i)}{\sum _{i|Y_i(k)=1}1} - \frac{\sum _i \varPhi (x-X_i)}{q}. \end{aligned}$$

(62)

We suppose that q is large enough to consider that $\sum _{i|Y_i(k)=1}1 = \frac{q}{2}$ (by the law of large numbers). Therefore we have:

$$\begin{aligned} \tilde{F}(x |Y(k) = 1) - \tilde{F}(x) = \frac{\sum _{i|Y_i(k)=1}\varPhi (x-X_i)}{q} - 2\frac{\sum _i \varPhi (x-X_i)}{q}. \end{aligned}$$

(63)

We notice that $\sum _{i|Y_i(k)=1}\varPhi (x-X_i) = \frac{1}{2}\sum _i (Y_i(k)+1)\varPhi (x-X_i)$. Therefore

$$\begin{aligned} \tilde{F}(x |Y(k) = 1) - \tilde{F}(x) = \frac{1}{q}\sum _{i=1}^q Y_i(k)\varPhi (x-X_i). \end{aligned}$$

(64)

This estimator is a sum of i.i.d. random variables. We can therefore apply the central limit theorem.

$$\begin{aligned} \mathbb {E}[ \tilde{F}(x |Y(k) = 1) - \tilde{F}(x) ]&= \mathbb {E}[Y(k)\varPhi (x-X_i)] \end{aligned}$$

(65)

$$\begin{aligned}&= \mathbb {E}[Y(k)\varPhi (x- Y(k^*) - N)] \end{aligned}$$

(66)

$$\begin{aligned}&= \frac{1}{2} ( \kappa (k) - 0.5) \Bigl ( \mathrm {erf}\Bigl (\frac{1-x}{\sigma \sqrt{2}}) + \mathrm {erf}\Bigl (\frac{1+x}{\sigma \sqrt{2}} \Bigr ) \Bigr ). \end{aligned}$$

(67)

The maximum of the absolute value is for $x=0$ and we obtain:

$$\begin{aligned} \Vert \mathbb {E}[ \tilde{F}(x |Y(k) = 1) - \tilde{F}(x) ] \Vert _{\infty } = |0.5 - \kappa (k)|\mathrm {erf}\Bigl ( \frac{1}{\sigma \sqrt{2}} \Bigr ). \end{aligned}$$

(68)

We notice that $\Vert \mathbb {E}[ \tilde{F}(x |Y(k) = 1) - \tilde{F}(x) ] \Vert _{\infty } = \Vert \mathbb {E}[ \tilde{F}(x |Y(k) = -1) - \tilde{F}(x) ] \Vert _{\infty }$. To calculate the variance, we consider that $x=0$ as it is the value that maximizes the expectation of the distinguisher.

$$\begin{aligned} \mathrm {Var}(\widehat{\mathcal {D}}(k^*) - \widehat{\mathcal {D}}(k)) = \mathrm {Var}\Bigl ( \frac{1}{q} \Bigl ( \sum _{i=1}^q \varPhi (x-X_i)(Y_i(k^*)-Y_i(k)) \Bigr ) \Bigr ) \end{aligned}$$

(69)

The computation of this variance gives:

$$\begin{aligned} \mathrm {Var}(\widehat{\mathcal {D}}(k^*) - \widehat{\mathcal {D}}(k)) = 2(0.5 - |0.5 - \kappa (k)|) - \mathrm {erf}\Bigl (\frac{1}{\sigma \sqrt{2}} \Bigr )^2 (0.5 - |0.5 - \kappa (k)|)^2. \end{aligned}$$

(70)

Overall, the success exponent is:

(71)

D Proof of Lemma 6

For MIA, we refer to [10, Section 5.3] for the theoretical justifications. In order to obtain a simple closed-form expression of the success exponent, we suppose that $\sigma \gg 1$ and that the probability density functions are all Gaussian. This means that X|Y(k) is a Gaussian random variable of standard deviation $\sqrt{4\kappa (k)(1-\kappa (k)) + \sigma ^2}$. Moreover, we will keep only the first order approximation in $\mathsf {SNR}=\sigma ^{-2}$ of the SE.

$$\begin{aligned} h(X|Y(k)) - h(X|Y(k^*)&= \frac{1}{2}\log _2(2\pi e \cdot (4\kappa (k)(1-\kappa (k)) + \sigma ^2) - \frac{1}{2}\log _2(2 \pi e \cdot \sigma ^2) \end{aligned}$$

(72)

$$\begin{aligned}&= \frac{1}{2}\log _2 \frac{4\kappa (k)(1-\kappa (k)) + \sigma ^2}{\sigma ^2} \end{aligned}$$

(73)

$$\begin{aligned}&\approx \frac{\log _2(e)4\kappa (k)(1-\kappa (k))}{2\sigma ^2} \end{aligned}$$

(74)

The Fisher information of a Gaussian random variable of standard deviation $\zeta$ is equal to $\frac{1}{\zeta ^2}$. Therefore the Fisher information of X knowing $Y=y(k)$ is:

$$\begin{aligned} F(X|Y(k) = y(k)) = \frac{1}{4\kappa (k)(1-\kappa (k)) + \sigma ^2}. \end{aligned}$$

(75)

As this value does not depend on the value of Y(k), we have:

$$\begin{aligned} F(X|Y(k))&= \frac{1}{4\kappa (k)(1-\kappa (k)) + \sigma ^2} \end{aligned}$$

(76)

$$\begin{aligned} J(X|Y(k)) - J(X|Y(k^*))&= \frac{1}{4\kappa (k)(1-\kappa (k)) + \sigma ^2} - \frac{1}{\sigma ^2}\end{aligned}$$

(77)

$$\begin{aligned}&\approx -\frac{\kappa (k)(1-\kappa (k))}{\sigma ^4}. \end{aligned}$$

(78)

Last, we have to calculate $\mathrm {Var}(-\log _2 p(X|Y(k) = y(k)))$. Let $\zeta ^2 = \sigma ^2 + 4\kappa (k)(1-\kappa (k))$ and C the normalization constant. We have:

(79)

(80)

(81)

(82)

Overall, the success exponent defined in [10, Proposition 6] can be simplified in the case of monobit leakage as:

$$\begin{aligned} \mathsf {SE} \approx \min _{k\ne k^*} 4\frac{\log _2(e)^2\kappa (k)^2(1-\kappa (k))^2}{\sigma ^4}. \end{aligned}$$

(83)