Project topics and materials
Get Complete Project Material File(s) Now! »
Formal Security Proofs and Studies
During my thesis, my main concern has been: how to unify and understand the link betwee the dierent metrics used to evaluate the sensitive information leakage of cryptographic chips? Indeed, various dierent metrics have been proposed by various authors in respond to specic issues. For example, we can cite:
The Mutual Information (MI) between measurements and the sensitive variables;
The Perceived Information computed with the estimated distribution of the leakage, based on template attacks;
The Success Rate or the Guessing Entropy of an attack exploiting a leakage.
A Generic Bound for Any Leakage With Only SNR
For example, the notion of MI is a widely spread concept in Side-Channel Analysis [30], and everyone agrees that the larger the MI, the better the attack, or from the defender’s side, the weaker the chip. However, the link between MI and the success rate of an attack, has never been established formally yet for generic attacks. Some links have already been made [29, 53] but they have been made for particular types of attacks, especially to show how the masking order impacts the MI [67] and are therefore true in a specic context. Moreover, I have noticed that no paper really deals with a tight prediction of the security of a chip. My question was: how can a designer predict the success rate of an attack with a very restricted number of assumptions. Indeed, a designer does not know how a device will be attacked. New methods may appear several years after the conception of the chip. This is why I have started looking for a framework that can unify any type of attack under simple concepts and notations. This is the beginning of my re ection: if we use some information theoretic metrics, then the answer must be in this eld.
In order to better formalize a side-channel attack, I based myself on the framework given by Francois-Xavier Standaert in [82]. This framework presents a simple albeit comprehensive look on what a side-channel attack is. In 2014, Annelie Heuser has published an article [39] where she demonstrates that the optimal distinguisher for an attack is the Maximum Likelihood decoder. To obtain this result, she establishes a rst formal link between side-channel analysis and information theory. The leakage model is there seen as a communication channel with a message to recover (i.e. the secret key). The method to derive the optimal distinguisher has been to express the expression for the key decoding rule which maximizes the success rate.
As MI is an information theoretic metric, it becomes here natural to study its impact with information theoretic models and theorems. I have therefore worked on this aspect. The main diculty for me has been to deal with the philosophical dierences between information theory and side-channel. Indeed, the purpose of each is clearly dierent:
The goal of an information theorist is to send a message with the highest possible rate and with an arbitrary small error rate. To do so, the communication engineer can use correcting codes and choose how the message is encoded.
In side-channel analysis, the message is the secret key. But the attacker do not have access to it (which is obvious). This means that the input distributions are imposed by the model and that there is not coding possibility to improve the success rate.
Adapting Theoretical Tools for Practical Issues
Another task of my thesis was to adapt some of the theoretical tools for practical issues. I based my studies on an ARM processor edited by ST Microelectronics: the STM32 Discovery Board [59].
On this architecture, we compute timing attacks on the AES algorithm. Here, in this practical example, the leakage model is not easy to nd and to deal with. A template attack is therefore needed to learn the model. However a learning phase may encounter some problems such as:
A bias between the learned model and the real leakage;
A poor learning phase.
Table of contents :
List of Figures
List of Tables
I Introduction and Contributions
1 Introduction
1.1 On the Importance of Cyber Security
1.2 The Rise of Cryptography
1.2.1 A Bit of History
1.2.2 Cryptography Today
1.2.3 AES
1.3 Side-Channel Analysis
1.3.1 Vulnerabilities
1.3.2 Attack
1.4 A Look on Information Theory
1.4.1 Background
1.4.2 Link With Side-Channel Analysis
1.5 Organization of the Manuscript
1.6 Notations
2 Contributions
2.1 Formal Security Proofs and Studies
2.1.1 A Generic Bound for Any Leakage With Only SNR
2.1.2 Extension to Template Attacks
2.1.3 MIA is Universal ML
2.1.4 A Unied Vision of Monobit Leakages
2.2 Adapting Theoretical Tools for Practical Issues
2.2.1 Avoid the Empty Bin Issue
2.2.2 Extract a Model for a Timing Attack
II A Mathematical Bound on Success Rate
3 A Mathematical Bound of the Success Rate with Mutual Information
3.1 Side-Channel Seen as a Communication Channel
3.2 Theoretical Bounds on Mutual Information
3.2.1 Main Result
3.2.2 A Fundamental Lower Bound on Mutual Information I(X;Y j T)
3.2.3 First Upper Bound on I(X;Y j T): Proof of Inequality (3.4)
3.2.4 Second Upper Bound on I(X;Y j T) – Proof of Inequality (3.5)
3.3 Application to Additive White Gaussian Noise
3.3.1 Shannon’s Channel Capacity
3.3.2 Evaluation of the Kullback-Leibler Divergence
3.4 Link with Guessing Entropy
4 Application
4.1 Numerical Approximations for Mutual Information
4.1.1 Numerical Estimation of I(X;Y j T)
4.1.2 Graphical Comparison
4.1.3 A Parametric Estimation of I(X;Y j T)
4.2 Application to Two Leakage Models
4.2.1 Example for Monobit Leakage
4.2.2 Example for Hamming Weight Leakage
4.2.3 Comparison with Duc’s Bound
4.3 Practical Applications
4.3.1 The SNR estimation
4.3.2 A Real World Case: the DPA Contest
4.4 Conclusion
III A Mathematical Study of Distinguishers
5 When Monobit Leakages are Dened with the Confusion Coecient
5.1 Introduction
5.2 Modelization and Denitions
5.2.1 The Leakage Model
5.2.2 The Confusion Coecient
5.2.3 Distinguishers
5.3 Theoretical Expressions for Distinguishers
5.3.1 A Communication Channel Between Y (k) and Y (k)
5.3.2 A General Result
5.3.3 Classical Distinguishers as Functions of (k) and 2
5.4 Comparing Distinguishers with the Success Exponent
5.4.1 Mathematical Expression of SE
5.4.2 Comparison of Distinguishers Based on their Success Exponent
5.5 Conclusion
6 When MIA is a Maximum Likelihood and better than CPA
6.1 Introduction
6.2 Optimality of Mutual Information Analysis
6.2.1 Notations and Assumptions
6.2.2 Mathematical Derivation
6.2.3 MIA Faster Than ML Distinguisher
6.3 Non-Gaussian Noise Challenge
6.3.1 Pedagogical Case-study
6.3.2 Application to Bitslice PRESENT
6.4 Partially Unknown Model Challenge
6.5 Fast Computations
6.5.1 Fast computation of CPA
6.5.2 Fast computation of MIA
6.5.3 Standard computation algorithm for MIA
6.6 Conclusion
IV Practical Issues With Timing Attacks
7 Methods to Solve the Empty-Bin Issue
7.1 Mathematical Derivation
7.1.1 Notations and Assumptions
7.1.2 About Empty Bins
7.2 Distinguishers which Tolerate Empty Bins
7.2.1 Building Distributions or Models
7.2.2 Robust distinguishers
7.3 Simulated Results
7.3.1 Presentation of the Simulated Model
7.3.2 Attack Results
8 Obtain a Leakage Model with Timing Attacks
8.1 Results on Real Devices
8.1.1 The ARM processor
8.1.2 Weaknesses – Non Constant AES Time
8.1.3 Characterizing the leakages for Data Cache On
8.1.4 Attack Results
8.1.5 Nature of Empty Bins
8.1.6 Study on the Mean-Square Error
8.2 Success Rate in Presence of External Noise
8.2.1 Eect of Measurement Noise
8.2.2 Comparison with Existing Methods in the Presence of Noise
8.3 Conclusion and Perspectives
V Conclusion and Perpectives
9 Conclusion
9.1 Conclusion
9.2 Further Perspectives
VI Appendix.
A Appendix on the Shannon Bound
A.1 Proof of Lemma 4.1
A.2 Proof of (3.5)
A.3 Proof of Corollary 3.1
A.4 Alternative Proof of (3.5) and Further Comments
A.5 A Discussion about Masking
A.6 About Mismatched Decoding
A.6.1 The Channel Coding Theorem with Divergence
A.6.2 Discussion About Merhav’s Paper
B Appendix about the Monobit Leakages
B.1 Proof of Lemma 5.3
B.2 Proof of Lemma 5.4
B.3 Proof of Lemma 5.5
B.4 Proof of Lemma 5.6
C The OpenSSL source code
C.1 The OpenSSL AES Encryption Code
Bibliography
