First-Order Leakage Squeezing Countermeasure

Get Complete Project Material File(s) Now! »

Higher-Order Side Channel Analysis

We call higher-order side channel attack [CJRR99,Mes00b,WW04, JPS05, PSDQ05, OMHT06, SP06] (abridged HO-SCA), any attack that combines all shares [GBPV10] or a judicious combination [PRB09] of them in order to turn a successful key recovery. Later, the attacker computes the dependency between the combined leakage and the leakage model for every key guess k using a distinguisher. When the correlation (respectively the mutual information) is used as a distinguisher, the attack is called higher-order differential power analysis (HO-DPA/ HO-CPA) (respectively higher-order MIA (HO-MIA)).
Several combining functions are used in HO-SCA. The choice of the combination depends on the implementation (e.g. software or hardware implementation). In fact, the SCA attacker of a dth-orde masking scheme gets direct observations of the (d + 1)-tuple L in the software case since the variables are evaluated sequentially. So, the leakage L is a multivariate signal and such an attack is called multivariate attack. Then, the adversary can thus choose adequate combining functions using several measurements [PR07]. Mainly two combining functions have been previously studied:
• In [CJRR99], Chari suggests performing the product of the shares.
• In [Mes00b], Messerges combines the shares using the absolute difference. In [PRB09], Prouff et al. analyzed both the product and the absolute difference combining functions and they show that the product combining is the best published function to perform a second-order DPA when devices leak the Hamming weight of the processed data.
In hardware implementations, ASIC or FPGA, the variables are evaluated in parallel. So, the only combination function available to the attacker is the arithmetic sum of individual leakages of the shares. This is done physically because of the parallelism in hardware devices execution. Hence, the leakage L corresponds to a univariate signal and such an attack is called univariate attack.

Vulnerability of Masking in Practice

Masking can be defeated if the attacker knows how to combine the leakages corresponding to the masked data Z ⊕ M and its mask M. This is known as secondorder power analysis (abridged 2O-DPA) and was originally suggested by Messerges in [Mes00b]. Investigating 2O-DPA is of major importance for practitioners as it remains a good alternative that is powerful enough to break real-life DPA-protected security products. In the sequel, we overview univariate second-order attacks since we are interested in the hardware setting.
In [WW04], Jason Waddle and David Wagner proposed a second-order attack that consists in computing the difference of means of the square of the power consumption traces in order to obtain key-dependent measurements, instead of the difference of means of the traces as in DPA. Peeters et al. present in [PSDQ05] another attack against a masked FPGA countermeasure based on the maximum likelihood distinguisher.

Probability Density Function Estimation

In order to compute the mutual information, one has to estimate the probability density functions for which several solutions exist. For instance, the probability density function can be estimated non-parametrically, by using histograms or kernel density estimation, or parametrically by using the Expectation Maximization (EM) algorithm. In the context of SCA attacks, the authors of the original MIA attack [GBTP08] used the histogram method for density estimation. In [PR09], Emmanuel Prouff and Matthieu Rivain emphasize the use of parametric PDF estimation tools since they are more relevant to side channel key recovery attacks. The main disadvantages of using advanced estimation tools are the memory requirements and the higher computation load. Hereafter, we detail these widely used PDF estimation tools.

Table of contents :

Abstract
Remerciements
Résumé de la thèse en français
List of Figures
List of Tables
Acronyms
Thesis Context
Part I Preliminaries
1 General Background
1.1 Introduction to Cryptography
1.2 Symmetric Cryptography
1.2.1 Stream Ciphers
1.2.2 Block Ciphers
1.2.3 Standard Block Ciphers
1.3 Asymmetric Cryptography
1.4 Cryptographic Devices and Physical Attacks
1.4.1 Cryptographic Devices
1.4.2 Physical Attacks
1.5 Conclusions
2 Introduction to Side Channel Analysis
2.1 SCA: General Background
2.1.1 Timing Attacks
2.1.2 Power Attacks
2.1.3 Electromagnetic Attacks
2.2 Side Channel Analysis Models
2.2.1 Attack Model
2.2.2 Leakage Models
2.3 Classical Side Channel Distinguishers
2.3.1 Correlation
2.3.2 Mutual Information
2.3.3 Kolmogorov-Smirnov
2.3.4 Likelihood
2.4 Side Channel Metrics
2.4.1 Leakage Metrics
2.4.2 Attack Metrics
2.5 Side Channel Countermeasures
2.5.1 Noise Generators
2.5.2 Shuffling
2.5.3 Hiding
2.5.4 Masking
2.6 Higher-Order Side Channel Analysis
2.7 Conclusions
Part II Higher-Order Side Channel Attacks
3 Variance-based Power Analysis
3.1 Vulnerability of Masking in Practice
3.2 Evaluation of the VPA Attack
3.2.1 Peeters’s Attack
3.2.2 Proposed VPA Attack
3.2.3 Experimental Results
3.3 Link between VPA and Second-Order CPA
3.4 Conclusions
4 Entropy-based Power Analysis
4.1 Probability Density Function Estimation
4.2 Practical MIA Attack
4.2.1 MIA Attack on Unprotected DES
4.2.2 MIA Attack on Masked DES
4.3 Evaluation of the EPA Attack
4.3.1 Proposed EPA Attack
4.3.2 Experimental Results
4.3.3 EPA Vs VPA Vs MIA
4.4 Conclusions
5 Inter-class Information Analysis
5.1 Inter-class Distinguishers
5.1.1 On Comparing Conditional Probability Distributions
5.1.2 Conditional-to-Unconditional
5.1.3 Conditional-to-Conditional
5.1.4 More than One Definition
5.1.5 Non-Equivalence of MIA and IIA
5.2 Side Channel Analysis Scenario
5.3 Soundness Proofs for MIA and IIA
5.3.1 Soundness Proof for Mutual Information Analysis
5.3.2 Soundness Proof for Inter-class Information Analysis
5.4 Mutual Vs Inter-class Information
5.4.1 Inter-class Information for a Gaussian Mixture
5.4.2 Why IIA is more Discriminating than MIA?
5.4.3 Simulation Results
5.5 Inter-class Approach and the Kolmogorov-Smirnov Test
5.5.1 Existing Frameworks
5.5.2 Increasing the Fairness of the Estimations
5.5.3 Bounding the Success Rate
5.5.4 Simulation Results
5.6 Conclusions
Part III Characterization of Masking Schemes
6 Introduction to Higher-Order Masking Countermeasures
6.1 State-of-the-Art: Higher-Order Masking
6.1.1 Notation and Basics of Statistics
6.1.2 Efficiency of Higher-Order Attacks
6.1.3 Information-Theoretic Characterization of Masking
6.2 HO-CPA Attacks and HO-CPA Immunity
6.2.1 HO-CPA Immunity
6.2.2 Link between Mutual Information and HO-CPA Immunity
6.3 First-Order Boolean Masking Schemes in the Literature
6.3.1 The Re-Computation Method
6.3.2 The Global Look-up Table Method
6.3.3 The S-box Secure Calculation Method
6.4 Conclusions
7 Security Evaluation of Masking Countermeasures
7.1 On Comparing Side Channel Attacks
7.2 Leakage Estimation with Information Theory
7.2.1 Leakage Metric Computation
7.2.2 Discussion
7.3 Security Estimation with Attacks
7.3.1 Success Rate Results
7.3.2 Security Analysis of Masking
7.3.3 Analytical Derivation of the Security Level for CPA Attacks
7.3.4 Discussion
7.4 Conclusions
Part IV New proposed Masking Countermeasures
8 First-Order Leakage-Free Masking Countermeasure
8.1 The GLUT Masking Method
8.1.1 Detailed Description of the GLUT Method
8.1.2 Security Analysis of the GLUT Method
8.1.3 Towards a New Masking Function
8.2 Study in the Idealized Model
8.2.1 Proposed Masking Function
8.2.2 Security Evaluation
8.2.3 Application to the Software Implementation Case
8.3 Study in the Imperfect Model
8.3.1 Description
8.3.2 Simulation Parameters
8.3.3 Simulation Results
8.4 Conclusions
9 Register Leakage Masking Using Gray Counter
9.1 Core Principle, Existing Works and Novelties
9.2 A New masking Function
9.2.1 Introduction of the New Proposal
9.2.2 Analysis of the New Proposal in the Idealized Model
9.2.3 Study in the Imperfect Model
9.3 Hardware Implementation of the Countermeasure
9.3.1 New Masking Architecture
9.3.2 Complexity and Throughput Results
9.3.3 Attack Experiments
9.4 Conclusions
10 First-Order Leakage Squeezing Countermeasure
10.1 Studied Implementation and its Leakage
10.2 Optimal Function in dth-Order CPA
10.2.1 Definition of the Optimal Function
10.2.2 Study with Sequential Leakage
10.2.3 Condition for the Resistance Against Second-Order CPA
10.2.4 Condition for the Resistance Against dth-Order CPA
10.3 Existence of Bijections
10.3.1 Three Conditions on Optimal Bijections
10.3.2 Optimal Linear Bijections
10.3.3 Optimal Non-Linear Bijections
10.3.4 Cost Optimality of the Leakage Squeezing
10.4 Security and Leakage Evaluations
10.4.1 Security Evaluation
10.4.2 Verification of the Leakage of the Identified Bijections
10.4.3 Results in Imperfect Models
10.5 FPGA Implementation of the Countermeasure
10.5.1 The GLUT Hardware Implementation
10.5.2 The USM Hardware Implementation
10.5.3 Complexity and Throughput Results
10.5.4 Evaluation of the Proposed Implementations
10.6 Conclusions
11 Leakage Squeezing of Order Two
11.1 Reminder on First-Order Leakage Squeezing
11.1.1 Leakage Squeezing in the Hamming Distance Model
11.1.2 Leakage Squeezing in the Hamming Weight Model
11.2 Second-Order Leakage Squeezing
11.2.1 Goal
11.2.2 Motivation
11.3 Formalization of Second-Order Leakage Squeezing
11.3.1 Gaining at Least one Order with Two Masks instead of One
11.3.2 Problem Formulation in Terms of Boolean Theory
11.4 Solutions when using Linear Bijections
11.4.1 Example for the found Linear Functions of F82
11.4.2 Example for the found Linear Functions of F42
11.5 Security Evaluation
11.6 Conclusions
Part V Conclusions and Perspectives
12 Conclusions and Perspectives
12.1 Summary
12.2 Perspectives
List of Publications
Bibliography