On the optimality and practicability of mutual information analysis in some scenarios

The best possible side-channel attack maximizes the success rate and would correspond to a maximum likelihood (ML) distinguisher if the leakage probabilities were totally known or accurately estimated in a profiling phase. When profiling is unavailable, however, it is not clear whether Mutual Information Analysis (MIA), Correlation Power Analysis (CPA), or Linear Regression Analysis (LRA) would be the most successful in a given scenario. In this paper, we show that MIA coincides with the maximum likelihood expression when leakage probabilities are replaced by online estimated probabilities. Moreover, we show that the calculation of MIA is lighter that the computation of the maximum likelihood. We then exhibit two case-studies where MIA outperforms CPA. One case is when the leakage model is known but the noise is not Gaussian. The second case is when the leakage model is partially unknown and the noise is Gaussian. In the latter scenario MIA is more efficient than LRA of any order.

1. Obviously, this hypothesis only holds provided the device manufacturer does not reuse the same cryptographic engine in an open platform, such as a JavaCard, where the user is able to use the cryptographic API at its will.

2. We comply with the usual notations of [7] where offline quantities are indicated with a hat, whereas online quantities are indicated with a tilde. In this paper, there is no profiling phase hence no offline quantities.

3. We use bold letters to indicate vectors while scalars are presented using small italic letters.

4. In order to uniquely distinguish the correct key, some conditions on the expressions of y are required. Specifically, let us denote by y _k the function t↦y _k (t) = y(k,t), and let \(\mathcal {B}\) the set of bijections on the leakage space \(\mathcal {X}\). We have:

   $$\begin{array}{@{}rcl@{}} \text{if }\forall k, \exists k^{\prime}\neq k, &\ \ \ & \exists \beta\in\mathcal{B} \text{ s.t. } y_{k^{\prime}} = \beta \circ y_{k}, \quad \text{then the distinguisher features a } \text{tie}, \end{array} $$

   (3)

   $$\begin{array}{@{}rcl@{}} \text{if }\forall k, \forall k^{\prime}\neq k, &\ \ \ & \exists \beta\in\mathcal{B} \text{ s.t. } y_{k^{\prime}} = \beta \circ y_{k}, \quad \text{then the distinguisher is } \text{not\ sound} . \end{array} $$

   (4)

   Indeed, in (3), there is no way for the distinguisher to tell k ^∗ from k ^′, and in (4), the distinguisher yields the same value for all the key guesses.

   We refer the interested reader to the work done in [24, Sec. 3]. We note that y _i = k ⊕ t _i does not lead to a sound distinguisher, as for all k ^′, x↦x ⊕ k ^′ is bijective, and maps y _k to \(y_{k\oplus k^{\prime }}\). On the contrary, there is no bijection β such that for all t, w _H (k ⊕ t) = β(w _H (k ⊕ k ^′⊕ t)). So the choice y _i = w _H (k ⊕ t _i ) is sound.

5. Some side-channels are discrete by nature, such as the timing measurements (measured in units of clock period). In addition, oscilloscopes or data acquisition appliances rely on ADCs (Analog to Digital Converters), which usually sample a continuous signal into a sequence of integers, most of the time represented on 8 bits (hence \(\mathcal {X}={\mathbb {F}_{2}^{8}}\)).

6. Universal, in the information theoretic sense of the word, means: computed from the available data without prior information.

7. In practice, logarithms require a high computational power, hence the number of calls to this function shall be minimized.

8. The least significant bit S ₀ of the PRESENT Sbox S is not suitable because one has \(\forall z{\in \mathbb F_{2}^{4}}\), S ₀(z) = S ₀(z ⊕0x9) = ¬S ₀(z ⊕0x1) = ¬S ₀(z ⊕0x8). As in (3) of footnote 4, ties occur: it is not possible to distinguish k ^∗, k ^∗⊕0x9, k ^∗⊕0x1, k ^∗⊕0x8 (the corresponding bijections are respectively x↦x and x↦1 − x). Therefore, we consider component 1 instead of 0, which does not satisfy such relationships.

Authors and Affiliations

1. Télécom ParisTech, LTCI, CNRS, Université Paris-Saclay, 75 013, Paris, France

   Éloi de Chérisey, Sylvain Guilley, Annelie Heuser & Olivier Rioul

2. Think Ahead Business Line, Secure-IC, 15 rue Claude Chappe, Bâtiment B, 35 510, Cesson-Sévigné, France

   Sylvain Guilley

Corresponding author

Correspondence to Éloi de Chérisey.

This article is part of the Topical Collection on Recent Trends in Cryptography

Guest Editors: Tor Helleseth and Bart Preneel

Reprints and permissions