Guide to Side-Channel Analysis of Embedded Systems: An Efficient Algorithmic Approach

Description

It has been more than 20 years since the seminal publications on side-channel attacks. They aim at extracting secrets from embedded systems while they execute cryptographic algorithms, and they consist of two steps, measurement and analysis. This book tackles the analysis part, especially under situations where the targeted device is protected by random masking. The authors explain advances in the field and provide the reader with mathematical formalizations. They present all known analyses within the same notation framework, which allows the reader to rapidly understand and learn contrasting approaches. It will be useful as a graduate level introduction, also for self-study by researchers and professionals, and the examples are taken from real-world datasets. Contents 1 General Introduction blackPart I Classical Side-Channel Attacks-1pt 2 Foundations of Side-Channel Attacks 2.1 Notations 2.2 General Framework for Side-Channel Attacks 2.3 Leakage Models 2.3.1 Hamming Weight Leakage Model 2.3.2 Hamming Distance Leakage Model 2.3.3 The Unevenly Weighted Sum of the Bits (UWSB) Leakage Model 2.3.4 Polynomial Leakage Model 2.3.5 Leakage Model in Profiled SCA 2.4 SCA Security Metrics 2.4.1 Success Rate (SR) 2.4.2 Guessing Entropy (GE) 2.4.3 Signal-to-Noise Ratio (SNR) 2.4.4 Normalized Inter-Class Variance (NICV) 2.4.5 Information Theory Metric 2.4.6 Metrics in Machine Learning 2.4.7 Relation Between the Security Metrics 2.5 Pre-processing of the Leakage Traces for SCA 2.5.1 Traces Synchronization 2.5.2 Noise Filtering 2.5.3 Points-of-Interest (PoI) Selection 2.5.4 Dimensionality Reduction 3 Side-Channel Distinguishers 3.1 SCA Distinguishers Classification 3.2 First-Order Distinguishers 3.2.1 Simple Power Analysis (SPA) 3.2.2 Differential Power Analysis (DPA) 3.2.3 Correlation Power Analysis (CPA) 3.2.4 Rank-Based CPAs 3.2.5 Covariance-Based Distinguisher 3.2.6 Collision Side-Channel Attacks 3.2.7 Mutual Information Analysis (MIA) 3.2.8 Kolmogorov-Smirnov Distance (KS)-Based Distinguisher 3.2.9 Chi-Squared Test (Chi-2-Test)-Based Distinguisher 3.2.10 Template Attack (TA) 3.2.11 Linear Regression-Based Side-Channel Attacks (LRA) 3.2.12 Machine Learning-Based Distinguishers 3.3 Higher Order Distinguishers 3.3.1 Higher Order Distinguishers Overs Combination 3.3.2 Higher Order Distinguishers Without a Prerequisite Combination 3.4 Comparison of Distinguishers 4 SCA Countermeasures 4.1 Hiding 4.1.1 Hiding on the Time Dimension 4.1.2 Hiding on the Amplitude Dimension 4.2 Masking Countermeasure 4.2.1 Boolean Masking (BM) 4.2.2 Multiplicative Masking (MM) 4.2.3 Affine Masking (AfM) 4.2.4 Arithmetic Masking (ArM) 4.2.5 Polynomials-Based Masking (PM) 4.2.6 Leakage Squeezing Masking (LSM) 4.2.7 Rotating S-Boxes Masking (RSM) 4.2.8 Inner Product Masking (IPM) 4.2.9 Direct Sum Masking (DSM) 4.2.10 Comparison Between Masking Schemes 4.3 Combination of Countermeasures blackPart II Spectral Approach in Side-Channel Attacks-1pt 5 Spectral Approach to Speed up the Processing 5.1 Walsh-Hadamard Transformation to Speed Up Convolution Computation 5.2 Convolution Product 5.3 Extension of the Spectral Approach to the Higher Order 5.4 Conclusion 6 Generalized Spectral Approach to Speed up the Correlation Power Analysis 6.1 Introduction 6.1.1 Outline 6.2 CPA's Preliminaries 6.2.1 Target of the Attack 6.3 Carrying Out the CPA, with Arbitrary Set of Messages, According to the Spectral Approach 6.3.1 Incremental CPA Computation 6.4 Extension of the Improvements to the Protected Implementations by Masking 6.5 Experiments 6.6 Conclusion blackPart III Coalescence-based Side-Channel Attacks-1pt 7 Coalescence Principle 7.1 Difference Between SCAs with and Without Coalescence 7.2 Optimization of the Stochastic Collision Attack Thanks to the Coalescence 7.2.1 Preliminaries 7.2.2 New Concept of Stochastic Collision Distinguisher 7.2.3 Main Result 7.3 Conclusion 8 Linear Regression Analysis with Coalescence Principle 8.1 Introduction 8.1.1 State-of-the-Art's Review 8.1.2 Contributions 8.1.3 Outline 8.2 Mathematical Modelization 8.2.1 Description of Stochastic Attacks 8.3 LRA Study and Improvements of Its Implementation 8.3.1 LRA with Assumption of Equal Images Under different Subkeys (EIS) 8.3.2 Spectral Approach Computation to Speed up LRA (with EIS) 8.3.3 Further Improvement 8.3.4 Incremental Implementation of LRA 8.4 Extension of the Improvements to the Protected Implementations by Masking 8.4.1 Normalized Product Combination Against Arithmetic Masking 8.5 Experiments 8.5.1 LRA with and Without Spectral Approach 8.5.2 SCAs with and Without Coalescence 8.5.3 LRA Against Higher Order Masking 8.6 Conclusion and Perspectives 9 Template Attack with Coalescence Principle 9.1 Introduction 9.1.1 Context: The Side-Channel Threat 9.1.2 Problem: Making the Most of High Dimensionality 9.1.3 State-of-the-Art 9.1.4 Contributions 9.1.5 Outline 9.2 Mathematical Modelization of the Problem and Notations 9.2.1 Side-Channel Problem 9.2.2 Additional Notations 9.3 Formalization of Template Attacks 9.3.1 Template Attack (Without Coalescence) 9.3.2 Template Attack (With Coalescence) 9.3.3 State-of-the-Art Dimensionality Reduction for TA 9.4 Efficiently Computing Templates with Coalescence 9.4.1 Simplification by the Law of Large Number (LLN) 9.4.2 Profiling and Attack Algorithms 9.4.3 Improved Profiling and Attack Algorithms 9.4.4 Extension of Our Approach to Masked Implementations 9.4.5 Computational Performance Analysis 9.5 Experiments 9.5.1 Traces Used for the Case Study 9.5.2 Template Attacks with Windows of Increasing Size 9.5.3 Comparison with PCA 9.5.4 Template Attack after Dimensionality Reduction (over First Eigen-Components) 9.5.5 Study of Our Approach with Simulated Traces 9.6 Conclusion 10 Spectral Approach to Process the High-Order Template Attack Against any Masking Scheme 10.1 Introduction 10.1.1 Related Works 10.1.2 Contributions 10.1.3 Outline 10.2 Preliminaries 10.2.1 Linear Algebra and Linear Codes 10.3 Higher Order Template Attack 10.3.1 High-Order Boolean Masking 10.3.2 Attack on High-Order Boolean Masking 10.3.3 Computing the Template Profile Functions p(Xq(w)|.) 10.3.4 Equivalent Multivariate Signal-to-Noise Ratio (SNR) 10.4 Type of Fourier Transform per Masking Scheme 10.4.1 Type of Fourier Transform for Inner Product Masking (IPM) Scheme 10.4.2 Type of Fourier Transform for Direct Sum Masking (DSM) Scheme 10.4.3 Multi-share DSM (MS-DSM) 10.4.4 Type of Fourier Transform for the Polynomial DSM (PDSM) Scheme 10.4.5 Type of Fourier Transform for the Rotating S-boxes Masking (RSM) Scheme 10.4.6 Type of Fourier Transform for the Leakage Squeezing Masking (LSM) Scheme 10.5 Experiments 10.5.1 Results of High-Order Attacks on Boolean Masking 10.5.2 Results of MS-DSM applied to PRESENT 10.5.3 Further Improvement in Performance 10.6 Conclusion and Perspectives 10.6.1 Conclusion 10.6.2 Perspectives 10.7 Appendix: Multi-Share DSM Scheme 10.7.1 Incorrect Multi-Share DSM Scheme 10.7.2 Correct Multi-Share DSM Scheme