Unified and optimized linear collision attacks and their application in a non-profiled setting: extended version

Side-channel collision attacks are one of the most investigated techniques allowing the combination of mathematical and physical cryptanalysis. In this paper, we discuss their relevance in the security evaluation of leaking devices with two main contributions. On one hand, we suggest that the exploitation of linear collisions in block ciphers can be naturally re-written as a Low Density Parity Check Code decoding problem. By combining this re-writing with a Bayesian extension of the collision detection techniques, we improve the efficiency and error tolerance of previously introduced attacks. On the other hand, we provide various experiments in order to discuss the practicality of such attacks compared to standard differential power analysis (DPA). Our results exhibit that collision attacks are less efficient in classical implementation contexts, e.g. 8-bit microcontrollers leaking according to a linear power consumption model. We also observe that the detection of collisions in software devices may be difficult in the case of optimized implementations, because of less regular assembly codes. Interestingly, the soft decoding approach is particularly useful in these more challenging scenarios. Finally, we show that there exist (theoretical) contexts in which collision attacks succeed in exploiting leakages, whereas all other non-profiled side-channel attacks fail.

1. Actually this corresponds to the square root of the Euclidean distance but the root does not alter the ordering hence there is no reason to consider it.

2. Since the Bayesian extension does not modify the ordering of the scores, using it only makes sense when applying the LDPC decoding algorithm.

3. Increasing the basis with non-linear elements would not allow solving this issue as long as only non-profiled attacks are considered. It would lead to more precise leakage models both for the correct key candidates and the wrong ones, by over-fitting.

Authors and Affiliations

1. UCL Crypto Group, Université catholique de Louvain, Place du Levant 3, 1348, Louvain-la-Neuve, Belgium

   Benoît Gérard & François-Xavier Standaert

2. DGA-MI, Bruz, France

   Benoît Gérard

Corresponding author

Correspondence to Benoît Gérard.

Part of this work has been done as a postdoctoral researcher supported by Walloon region MIPSs project. Associate researcher of the Belgian Fund for Scientific Research (FNRS-F.R.S.). This work has been funded in part by the ERC project 280141 (acronym CRASH).

Appendix A: Proof of Lemma 2

We want to express the mean and the variance of a mixture of two distributions as a function of the means and variances of these distributions. Let us recall that \(\mathcal D \) is a mixture of two distributions \(\mathcal D _\mathrm{c}\) and \(\mathcal D _\mathrm{nc}\) with respective weights \(2^{-8}\) and \(1-2^{-8}\). We denote by \(\mu \) and \(\sigma ^2\) the expected value and variance of \(\mathcal D \), by \((\mu _\mathrm{c},\sigma ^2_\mathrm{c})\) the expected value and variance of \(\mathcal D _\mathrm{c}\), and by \((\mu _\mathrm{nc},\sigma ^2_\mathrm{nc})\) the expected value and variance of \(\mathcal D _\mathrm{nc}\). Let \(X_\mathrm{c}\) and \(X_\mathrm{nc}\) be respectively drawn according to \(\mathcal D _\mathrm{c}\) and \(\mathcal D _\mathrm{nc}\) and \(X\) be the mixture \(2^{-8} X_\mathrm{c} + (1-2^{-8})X_\mathrm{nc}\). Then, due to the linearity of the operator, \(\mathbb{E }\left(X\right)=\mathbb{E }\left(2^{-8} X_\mathrm{c} + (1-2^{-8})X_\mathrm{nc}\right)=2^{-8}\mu _\mathrm{c}+(1-2^{-8})\mu _\mathrm{nc}\). Thus, it follows that \(\mu _\mathrm{nc}= \frac{\mu -2^{-8}\mu _\mathrm{c}}{1-2^{-8}}\). Concerning the variance, a slightly more difficult calculus leads to the claimed result. First, we use the relationship \(\mathbb V \left(X\right) = \mathbb{E }\left(X^2\right) - \mathbb{E }\left(X\right)^2\) and we develop its first term in:

Since \(X_\mathrm{c}\) and \(X_\mathrm{nc}\) are independent variables, we have:

We then notice that \(\mathbb{E }\left(X_\mathrm{c}^2\right) = \sigma ^2_\mathrm{c}+\mu _\mathrm{c}^2\) (the same holds for \(\mathbb{E }\left(X_\mathrm{nc}^2\right)\)). Hence:

Now returning to \(\mathbb V \left(X\right) = \mathbb{E }\left(X^2\right) - \mathbb{E }\left(X\right)^2\), we finally observe that many terms in \(\mu \) vanish to yield \(\mathbb V \left(X\right) = 2^{-16}\sigma ^2_\mathrm{c}+(1-2^{-8})^2\sigma ^2_\mathrm{nc}\).

Appendix B: Additional details about the target implementations

Our experiments are based on two different implementations of the AES: a reference one that has been designed such that S-boxes’ look-ups have similar leakage functions, and the furious implementation. Codes corresponding to one look-up are presented in Table 1 and commented below.

We observed that the most leaking operation in the S-box computation was the mov operation, that stores the input of the S-box in the ZL register. Hence, in the reference implementation, we first copy intermediate values in a register SR, that is the same for all 16 S-boxes computations. Then, SR is updated and the output is copied back to the initial state register. On the contrary, we can see that in the furious implementation, the ZL register is directly updated from the state register (here ST22), and the answer directly goes back to the state register. In addition, the furious implementation combines the S-box layer with the ShiftRows operation. It explains why the output is stored in ST21 and not ST22. The optimizations in the furious implementation are the main reason of the poor results of the attacks performed. As a simple illustration, we plotted the templates of the leakage points used in the attacks for different S-boxes in Fig. 4 (for the reference implementation) and Fig. 5 (for the furious one).

Leakage functions for the reference implementation

Full size image

Leakage functions for the furious implementation

Full size image

Appendix C: Discussion on parameters for list decoding

In this section we discuss two parameters for the list decoding procedure presented in Sect. 4.4 namely the application of belief propagation and the information set choice.

Using belief propagation in the procedure Choosing an information set and using it to enumerate codewords seems to be not optimal since we actually do not benefit from information contained in other positions (redundancy). Note that this is not obvious when different information sets are used and when the overall probability of a codeword is computed using the 120 positions. However, in the case we consider a single information set is used and codewords are enumerated according to a partial probability computed from the 15 chosen positions.

To take profit of redundancy in this situation, the application of the belief propagation step should be used to propagate information according to the linear constraints of the code. The question is then how many iterations should we perform?

We performed experiments for 0 (no application), 1 and 2 iterations and obtained results in favor of the application of the belief propagation. We do not provide results obtained for correlation coefficient since in both standard and Bayesian cases applying twice the propagation step led to better results. This is not so clear for Euclidean distance as can be seen in Figs. 6 and 7.

Median ranks using Euclidean distance metric with different number of belief propagation steps

Full size image

Indeed, we see that for the Bayesian extension of the Euclidean distance, performing belief propagation alters results as soon as the number of traces are available reaches some point (between 100 and 250 traces depending on the number of iterations considered).

Median ranks using Bayesian Euclidean distance metric with different number of belief propagation steps

Full size image

Such degradation of performances may be due to the fact that in the context of Furious implementation the base hypothesis from which we built the Bayesian extension is not fulfilled anymore. The extension for correlation coefficient seems to be not (or at least less) impacted. This difference may comes from the nature of hypotheses: for Euclidean distance an hypothesis is made for the behavior of (infrequent and informative) colliding events while for correlation coefficient the hypothesis refers to (less informative) non-colliding events.

Choice of the information set The second important point in the procedure is the choice of the information set. Ideally we would like to chose the least faulty positions.

One may assume that when a position is faulty (due to the lack of information) the corresponding distribution looks “more uniform” than a position where the correct value has a good rank. This heuristic can be partially confirmed as positions depending on the two particular S-boxes have a larger entropy than others.

This remark implies that to overcome the problem encountered when attacking the Furious implementation, one could try to detect such error prone S-boxes, remove them from the analysis and use the single output decoding algorithm.

Since a list-decoding algorithm also aims at trading data for computation time, the former remark does not mean that such algorithm is useless. Hence we investigated the use of entropy to choose the information set.

We previously saw that applying belief propagation improved attacks we ran. Thus, the question is should we consider entropy posterior or prior to this step? Intuitively, applying the belief propagation should correct errors or confirm good positions thanks to redundancy. Thus, it is expected that positions having small entropy after the belief propagation steps are less faulty than the ones before.

This is confirmed by experiments where the choice of information set with prior entropies shows median larger ranks with a typical (and significant) factor of \(2^5\).

Appendix D: About time complexity

Metrics used in Sect. 5 for analyzing experiments only consider the success rate of the attacks as a function of their data complexity. We consider the time complexity of the proposed collision attack in this section. When attacking \(n_\mathrm{s}\) S-boxes processing \(n_\mathrm{b}\)-bit words, these complexities for our different procedures are:

When using the pre-processing technique that has a cost \(\Theta \left(n_\mathrm{s}n_tm\right)\), the complexity of the procedure ComputeStatistics is decreased to \(O\left(n_\mathrm{s}^2 2^{2n_\mathrm{b}}m\right)\). Hence, it turns out that, in realistic contexts, collision attacks can be performed in a negligible time compared to the on-line acquisition and the final key search phases (a similar comment applies to stochastic attacks). Furthermore, by carefully profiling the number of cycles needed to perform the different steps of the attacks, we observed that the slight time overhead induced by the use of a Bayesian extension and/or an LDPC decoding algorithm is positively balanced by the reduction of the data complexity, hence leading to globally more efficient attacks.

We stress that no precise timing is given here because the core of the attacks performed took less than a single second on a traditional PC. Hence we consider that such information is not relevant regarding the time spent to read traces from the drive or to perform enumeration/rank estimation.

Reprints and permissions