Truncation of Optimal Distinguisher against shuffled Masking Table

Get Complete Project Material File(s) Now! »

Samples Selection and Dimensionality Reduction

As presented in Sec. 1.3.2 the number of exploitable leakage samples may be small compared to the length of the measurements. As the Templates Attacks are naturally multivariate they can be applied directly on the whole traces but this leads to excessive computational loads and memory consumption (31). To reduce the number of points on which the attacks will be proceed a variety of methods exits. Such methods can be divided into two main categories: the sample selection methods and the dimensionality reduction methods.
Those two kinds of method are conceptually closed as they lead to smaller traces. The sample selection methods aim at finding in the traces the most relevant samples and select them. Sample selection methods lead as a consequence to a data selection. The dimensionality reduction methods aim at recombining the different samples in order to increase the possible exploitable information contained in one point. The dimensionality reduction methods lead therefor to a data transformation. As a consequence the major difference occurs when monovariate distinguisher are applied on the reduced traces. Indeed in the cases of monovariate distinguishers as the ones presented in SubSect. 1.3.3.3 there is no need of sample selection as the distinguishers are applied independently on each time sample. Then the results of the attacks with sample selection will be similar to the results of attacks without sample selection. While, dimensionality reduction may be an interesting tool as it combines information spread over different leakage samples in an exploitable one and as a consequence better results can be expected.

Sample Selection

Different metrics for sample selection have presented in the field of SCA. They allow to classify the samples in order to identify the most relevant ones. The attacker selecting an arbitrary number of samples maximizing the sample selection metric. In their original article on Template Attacks Chari et al. (31) used the difference of mean in order to recover the sample points which are linked to the key.

Protection for Asymmetric Cryptography

The Asymmetric Cryptography algorithms can be vulnerable to SPA indeed the classical algorithms used for the modular exponentiation used in RSA or the scalar multiplication for ECC use conditional branches depending on the exponent or the scalar. As an example the classical scalar multiplication algorithm performs a double and an add when the scalar bit is one or just a double when the scalar bit is zero. Therefor by simply looked at the sequence of operations it is possible to recover the entire key within one trace. It exists in the literature many different scalar multiplications/modular exponentiations. To avoid SPA a first countermeasure makes the scalar multiplication regular meaning that the same operations are performed independently from the value of the current bit. Different algorithms have been proposed to attend this goal such as the Double and Add Always or the Montgomery Ladder algorithm. Nevertheless this kind of countermeasure does not protect against differential attacks. An example of differential attacks has been proposed in (38). Similarly to the protected implementations of symmetric cryptographic algorithms, different randomization countermeasures have been developed, they will differ on the randomized values but their behaviors are similar. Indeed for each execution of the cryptographic algorithm one value or more is randomized which makes this particular variable not attackable by differential means. Different types of variable can be targeted and as a consequence different variables can be randomized.

Comparison with PCA and LDA

When the attacker does not precisely know the model given by Eqn. (2.1), the optimal dimensionality reduction cannot be applied directly. In this section, we analyse theoretically two well-known engineering solutions to reduce the dimensionality: PCA and LDA. Both techniques are based on eigen decompositions.

Table of contents :

List of Figures
List of Tables
1 Introduction
1.1 Introduction to the cryptography
1.1.1 Symmetric Cryptography
1.1.2 Asymmetric Cryptography
1.2 Physical Attacks
1.3 Side Channel Attacks
1.3.1 Notations
1.3.2 Leakages descriptions
1.3.3 Distinguisher
1.4 Samples Selection and Dimensionality Reduction
1.4.1 Sample Selection
1.4.2 Dimensionality Reduction
1.5 Protection methods
1.5.1 Data Masking Scheme
1.5.2 Protection for Asymmetric Cryptography
1.6 Attacks on the countermeasures
1.6.1 High Order Attacks
1.6.2 High Order Differential Attacks
1.6.3 Dimensionality parameters of the attacks
1.6.4 Horizontal Attack
1.7 Attacks evaluation
1.7.1 Empirical Evaluations
1.7.2 Theoretical comparison
1.8 Contributions of the Thesis
1.8.1 Contributions
1.8.2 Outlines
I Dimensionality Reduction a case study in presence of masking
2 Optimal Dimensionality Reduction with Profiling.
2.1 Introduction
2.2 Theoretical Solution in the Presence of Gaussian Noise
2.2.1 Notations
2.2.2 Optimal Attack
2.2.3 Optimal Dimensionality Reduction
2.2.4 Discussion
2.3 Examples
2.3.1 White Noise
2.3.2 Correlated Autoregressive Noise
2.4 Comparison with PCA and LDA
2.4.1 Principal Components Analysis (PCA)
2.4.2 Linear Discriminant Analysis (LDA)
2.4.3 Numerical Comparison Between Asymptotic PCA and LDA
2.5 Practical Validation
2.5.1 Precharacterization of the Model Parameters D and
2.5.2 Computation of SNRs on the AES Traces from DPA Contest v2 Last Round
2.6 Conclusions and Perspectives
3 Dimensionality Reduction a case study in presence of masking.
3.1 Introduction
3.2 Theoretical optimal preprocessing function
3.2.1 Case study
3.2.2 Principal component analysis
3.2.3 Preprocessing on modulated side channel traces
3.2.4 Covariance vector as a preprocessing method
3.2.5 Discussion
3.2.6 Time vs Frequency domains
3.3 Empirical results
3.3.1 Implementation of the masking scheme
3.3.2 Leakage analysis
3.3.3 Experimental protocol
3.3.4 Comparison of the two preprocessing methods and classical second-order CPA
3.3.5 How is the preprocessing linked to the noise?
3.4 On the fly preprocessing
3.4.1 Case study
3.4.2 Empirical results
3.5 Conclusions and Perspectives
II Multivariate Leakages of a Masking Scheme with Table Recomputation
4 Optimal Distinguisher against Masking Table
4.1 Algorithm of masking tables
4.2 Classical Attacks
4.3 High Order Optimal Distinguisher for Precomputation Masking Tables
4.3.1 Experimental Validation
4.4 Classical countermeasure
4.5 Conclusions and Perspectives
5 Multivariate High Order Attack against shuffled Masking Table
5.1 Introduction
5.1.1 Preliminary and notations
5.2 Totally random permutation and attack
5.2.1 Defeating the countermeasure
5.2.2 Multivariate attacks against table recomputation
5.2.3 Leakage analysis
5.2.4 Simulation results
5.2.5 Theoretical analysis of the SR
5.3 An example on a high-order countermeasure
5.3.1 Coron masking scheme attack and countermeasure
5.3.2 Attack on the countermeasure
5.3.3 Leakage analysis
5.3.4 Simulation results on Coron masking Scheme
5.4 A note on affine model
5.4.1 Properties of the affine model
5.4.2 Impact of the model on the confusion coefficient
5.4.3 Theoretical analysis
5.4.4 Simulation results
5.5 Practical validation
5.5.1 Experimental Setup
5.5.2 Experimental results
5.6 Countermeasure.
5.6.1 Countermeasure Principle
5.6.2 Implementations
5.6.3 Security Analysis
5.7 Conclusions and Perspectives
6 Truncation of Optimal Distinguisher against shuffled Masking Table
6.1 Introduction
6.2 Notations
6.2.1 Model
6.3 A Generic Log-Likelihood for Masked Implementations
6.3.1 Maximum Likelihood (ML) Attack
6.4 Case Study: Shuffled Table Recomputation
6.4.1 Parameters of the Randomization Countermeasure
6.4.2 Second-Order Attacks
6.4.3 Exploiting the Shuffled Table Recomputation Stage
6.5 Complexity
6.5.1 Complexity in the General Case
6.5.2 Complexity of our Case Study
6.6 Simulation Results
6.6.1 Exploiting only Leakage of the Mask and the Masked Share
6.6.2 Exploiting the Shuffled Table Recomputation
6.7 Conclusions and Perspectives
7 Conclusion
7.1 Conclusion
7.2 Perspectives.
7.2.1 Under Review.
7.2.2 Research Perspectives.
7.3 List of publications.
III Appendix.
A Appendix of Dimensionality Reduction
A.1 Proof of Theorem 3
A.2 Proof of Lemma
A.3 Proof of Proposition
B Appendix of Multivariate Attack.
B.1 Proof of Theorem
B.2 Proof of the propositions of Sect. 5.2.5
B.2.1 Proof of Prop.
B.2.2 Proof of Prop.
B.2.3 Proof of Prop.
B.3 Proof of Theorem 5.3.1
B.4 Affine model
B.4.1 Proof of Lemma
B.4.2 Proof of the Theorem 5.4.1
B.4.3 Proof of Corollary
C Appendix of Mixed Order.
C.1 Computation of the Moments
C.1.1 Computation of 1
C.1.2 Computation of 2
C.1.3 Computation of 3
C.2 Complexity Proofs
C.2.1 Proof of Lemma 7
C.2.2 Proof of Proposition
C.2.3 Proof of Proposition
C.2.4 Proof of Proposition
C.2.5 Time and complexity
C.3 Analysis of the DPAcontest.
Bibliography