A remark on a success rate model for side-channel attack analysis

In [1], a general statistical model for side-channel attack analysis is proposed. Based on this model, one can calculate a success rate of an attack by numerical simulation. This success rate is the most common evaluation metric for measuring the performance of a particular attack scenario. In [5], it is stated:

“Closed-form expressions of success rate are desirable because they provide an explicit functional dependence on relevant parameters such as number of measurements and signal-to-noise ratio which help to understand the effectiveness of a given attack and how one can mitigate its threat by countermeasures. However, such closed-form expressions involve high-dimensional complex statistical functions that are hard to estimate”. In the following, we will derive an analytic formula for the success rate. Simulation experiments confirm that this analytic formula is a good approximation for the success rate for a wide class of leakage functions.

We further restrict ourselves to the simplest setting:As in [1], we now apply the maximum likelihood attack: We compute the conditional probability density function of the observations \(b_w\) under each hypothesis k. We choose as the correct key that k which maximizes the probability density function. An easy calculation shows that we have to compare the valuesThis can further be reduced to the valuessince \(\sum _{w=0}^{N-1} h(w\oplus k)^2\) does not depend on k. The success rate as defined in [1] is the probability thatwhere \(X_k\) is the random variableThis success rate can certainly be computed by numerical simulation of the \(T_w\).

Let A be the N\(\times \)N-matrix with entries \(h(w\oplus k)\). The rows of A areLet T be the random vector (as column) of length N with entries \(T_w\). Let \(d = A \cdot a_{k_c}^t\) with entries \(d_k\). We define the set R of all vectors of length N with entries \(y_k\) that fulfillAn easy calculation shows that the success rate can be written asA is a symmetric matrix, and therefore there exists an orthonormal basis of eigenvectors \(v_0,\ldots , v_{N-1}\) with corresponding eigenvalues \(\lambda _0,\ldots ,\lambda _{N-1}\) of A. T can be written in the basis of eigenvectors in the formwhere the \(X_i\) are independent random variables with standard normal distribution. The distribution of \(A \cdot T\) is the image of the standard normal distribution under A. Each vector in the distribution of T is stretched in the direction of the eigenvectors of A with the corresponding eigenvalue as factor.We easily computeFor values like \(n=6\) or \(n=8\), \(N=2^n\) is a relatively large number, so that the typical vector in the distribution of \(A \cdot T\) has square of norm \(N^2 \delta ^2\). As a heuristic approximation for the success rate, we just replace the distribution of \(A\cdot T\) by the normal distribution stretched by the constant factor \(2^{n/2} \delta \):In addition, we omit the influence of d and getwhere \(\tilde{R}\) is the set of all vectors \(t_k\) that fulfillThe last probability can be in fact computed as a two-dimensional integralThis expression only depends on \(\delta \), so that it can easily be listed for different \(\delta \) by numerical methods. Figure 1 plots this approximated success rate as computed by MAPLE software for \(n=8\).

Remarks:

The properties of the matrix A are used in the context of dyadic codes; see [2]. In [3], the matrix A is called dyadic matrix. Due to the structure of A, we can compute the eigenvectors of A explicitly: There are N \(\hbox {GF}(2)\)-linear functions LFor every L, \(v_L=[(-1)^{L(w)}]_w\) is a vector of length N. For every k, we haveTherefore, \(v_L\) is an eigenvector with eigenvalue \( \sum _y h(y) (-1)\)\(^{L(y)} \). The rank of A is the number of nonzero eigenvalues.

Let S be the S-Box of the AES and G a fixed \(\hbox {GF}(2)\)-linear function. We assume that the leakage function h only depends on \(G \circ S\), i.e., after normalizationThe eigenvalues of A are nowWith other words: The set of eigenvalues is exactly the Walsh spectrum of the Boolean function \(G\circ S\) multiplied by \(\delta \). Each eigenvalue is a measure how good \(G\circ S\) can be approximated by a linear function L. S is the composition of the inversion over \(F=\hbox {GF}(256)\) and an affine function. The Walsh spectrum of any function of the form \(G\circ S\) is well known: It can be expressed by the so-called Kloosterman sums; see [4].where tr(y) denotes the trace of y over F. Any \(\hbox {GF}(2)\)-linear function \(L: F \longrightarrow \hbox {GF}(2)\) can be written as \(L(y)=tr(l y)\) for exactly one \(l \in F\). Therefore, we find \(c \in F\) such thatorNote that for \(c\ne 0\)The distribution of the Kloosterman sums can be described by values of certain class numbers (see [4, Prop. 9.1]), which can be interpreted in terms of the Walsh spectrum.

In this example, h does not depend on the output of the substitution box, but on the Hamming weight of the input. After normalization, we can writeIn this case, A has exactly n eigenvectors with eigenvalues \(\ne 0\) and these are given by the n linear projectionsThe eigenvalues of these n eigenvectors are equal to \(\delta \frac{N}{\sqrt{n}}\). Since we have only a few eigenvalues \(\ne 0\), we cannot expect that the second approximating formula is a good approximation in this case.

However, we can derive an exact formula for the success rate: Since h is a linear function, we haveThe sums in brackets do not depend on k, so thatThe maximum likelihood attack is therefore successful exactly in the event thatWith other words: The success rate is the probability that the random variable \(Y_j\) fulfills\(Y_j\) is normally distributed with an expectation value \(\frac{\delta N }{\sqrt{n}}\) and variance N. Since the covariance between \(Y_j\) and \(Y_{\tilde{j}}\) is 0 for \(j \ne \tilde{j}\), the success rate is given by the formula

We computed the success rate for different n, h and \(\delta \) by numerical simulation of the \(T_w\). Table 1 compares the success rates for \(n=8\), and Table 2 the same for \(n=6\). In both tables, f is chosen as a random function \(\hbox {GF}(2)^n \longrightarrow \hbox {GF(2)}\), but uniformly distributed. P is chosen as a random permutation on \(\hbox {GF}(2)^n\). g is the function from paragraph 6. We repeated the simulation 1000 times with different f and P, so that a mean is given in both tables.

We note that the second approximating formula and the Hamming weight formula from paragraph 6 give different values for identical \(\delta \), but both formulas match the numerical values very well. In all experiments, the numerical values in each of the 1000 repetitions were very close to the mean given in the tables. For \(n=8\) (Table  1), the empirical standard deviation was less than 0.004. For \(n=6\) (Table  2), the empirical standard deviation was less than 0.02.

Similar to [5], we can apply the second approximating formula to the case of masking. For a concrete example, we adapt our leakage model in the following way:We setThe sum is taken over \(\frac{m}{N}\) realizations of independent random variable. For any fixed mask \(m_w\), we computeandIf \(\frac{m}{N}\) is not too small, we approximate \(c_\nu \) as realizations of N independent normally distributed random variables, each with expectationand varianceAgain if \(\frac{m}{N}\) is not too small, we approximate these sums by the expectation over the random variables \(M_w\). An easy calculation showsandSince \(\sum _{z}\mu (z)^2=n\cdot N\), we can apply the leakage model of paragraph 2 withGiven the measurements \(\tilde{b}'_w, \tilde{b}''_w\), we directly compare the valuesfor different k and decide for the k with the largest value. For large m, we can expect that the success rate of this ad hoc attack only depends on \(\delta ^2= \frac{n m}{N(2 n \sigma ^2+\sigma ^4)}\).

Table 3 gives the success rates of this attack computed by numerical simulation and \(n=8\). We compare these success rates with the values for the example from paragraph 6 (\(h=\delta g\)). Since the numerical simulations are rather slow, we repeated the simulation only for a few instances. However, in all instances the values matched very well.

Table 4 gives similar data, but for \(m=N^2\).

The leakage in \(\tilde{b}'_{w}\) depends on the input of an S-Box computation. We can certainly consider the case that the leakage depends on the output of an S-Box computation, i.e.,The computation is completely analog, but we expect that the second approximating formula applies. Tables 4 and  5 compare the numerical values for the success rate with the second approximating formula. Again, we computed only a few instances, but in all instances the values matched very well (Table 6)