Project topics and materials
Get Complete Project Material File(s) Now! »
Categories of the Attacks
The different attacks in embedded systems are generally classified into three main categories: Side-Channel, Fault and Combined Attacks. For each attack of the next chapter, we specify in which category it belongs to.
Side-Channel or Passive Attacks are those where the attacker observes the behaviour of the chip during a process without disturbing it. Since the behaviour depends on the manipulated data, the observations may reveal secret information such as the secret scalar. So far, the different passive attacks are:
• Timing Attacks. They exploit the interdependence between values of the inputs and the time needed to execute the cryptographic algorithm. The first reported side-channel attack of Kocher [Koc96] is in fact a timing attack.
• Simple Side-Channel Analysis (SSCA). The attacker observes the different patterns of the power consumption or the electromagnetic traces. Each step of the attack requires a single trace to conclude on some information of the secret.
• Template Attacks. They proceed in two phases [CRR02]. The first phase consists in building the templates. The attacker needs a fully controllable device in which she can choose private and public data, and acquire traces of the power consumption by varying the input data: this database makes up the templates. The second phase is the acquisition of the targeted device with the same known public data used for the templates. The trace is then compared with the templates to conclude which secret data are the more probably manipulated.
• Vertical Side-Channel Analysis. Several ecsms are run with different input data. Each time, the power consumption or the electromagnetic radiation is acquired. A statistical analysis is performed on the different traces to deduce the manipulated values, and hence the secret scalar.
• Horizontal Side-Channel Analysis. A single trace is analysed to conclude on some information of the secret. The attacker uses statistical tools on segments of the trace. Since a single trace is available, the length of the random variables is really limited. Therefore, Horizontal SCA is more difficult to mount in practice compared with Vertical SCA in which the attacker has a potential access to unlimited traces. Nonetheless, recently, these attacks have been intensively studied because they are in fact very powerful since a single trace can reveal the whole secret data. These attacks make it possible to target some cryptographic protocols naturally immune to vertical SCA such as ecdsa. They also can bypass some very powerful countermeasures.
Test Platform
Side-Channel attacks are generally experimentally validated. We implemented elliptic curves operations in the Side-channel Attack Standard Evaluation Board SASEBO-GII [SASEBO]. The hardware arithmetic module was implemented using algorithms described in Chapter 2 with a word size of 64 bits. All measures and experimental results given in the next chapter are performed with this test platform.
Quantifying the Cost of the Countermeasures
Each countermeasure has a non negligible time or memory cost on ecc applications. Indeed, a countermeasure can extend the ecsm by several iterations, it can increase the number of operations of an elliptic curve formula, or it can cost only a few modular multiplications. For the extra field operations, extra elliptic curve operations, or extra iterations of the ecsm, we use the notation of Sections 2.6, 3.2 and 4.3 respectively. A Random Number Generation (rng), a Random Permutation Generation (rpg) or a Cyclic Redundancy Check (crc) might be needed for the countermeasure. We notify it. The memory required to store the extra values also matters. For each countermeasure, we give the cost with the following notation:
• ecsml,n: execution time of an ecsm with a l-bit scalar and a n-bit modulus.
• ecaddn, ecdbln, c-ecaddn: execution time of an elliptic curve addition, doubling and conjugate addition with a modulus of size .
• addn, sqrn,muln, divn: execution time of an addition/subtraction, a square, a multiplication and a division respectively, with n-bit integers.
• maddn,msqrn,mmuln,minvn: execution time of a modular addition/subtraction, a modular square, a modular multiplication and a modular inversion respectively, with n-bit integers,
• rngn: execution time of the generation of a random n-bit integer,
• rpgm: execution time of the generation of a random permutation of m elements,
• crcn: execution time of a cyclic redundancy check of a n-bit integer,
• memn: memory block to store a n-bit integer.
Table of contents :
List of Acronyms
Introduction
I Elliptic Curve Cryptography
1 General Definition
1.1 Elliptic Curves in Affine Coordinates
1.2 Group Structure
1.3 Short Weierstraß Equation
1.4 Elliptic Curves in Projective Coordinates
2 Finite Field Arithmetic
2.1 Field Element Representation
2.2 Main Module
2.3 Modular Addition and Subtraction
2.4 Modular Multiplication
2.5 Modular Inversion
2.6 Cost of Arithmetic Operations
3 Elliptic Curve Arithmetic
3.1 Elliptic Curve Formulæ
3.1.1 Classical Formulæ
3.1.2 Co-Z Formulæ
3.2 Cost Summary
4 Elliptic Curve Scalar Multiplication
4.1 Unregular ECSMs
4.2 Regular ECSMs
4.3 Cost Summary
5 Cryptographic Protocol
5.1 Elliptic Curve Digital Signature Algorithm
5.2 Elliptic Curve Diffie Hellman
5.3 Elliptic Curve ElGamal
6 ECC Security
II Physical Attacks and Countermeasures on ECC
7 Characterisation
7.1 Categories of the Attacks
7.2 Attack Context
7.3 Test Platform
7.4 Quantifying the Cost of the Countermeasures
8 Attacks and Countermeasures
8.1 Classical Timing Attack
8.1.1 Constant Time of Field Operations
8.2 Simple Side-Channel Analysis
8.2.1 Regular ECSM
8.2.1.1 C Safe-Error
8.2.2 Unified Formulæ
8.2.2.1 SSCA on Unified Formulæ
8.2.2.2 Horizontal SVA on Unified Formulæ
8.2.3 Side-Channel Atomicity
8.2.3.1 SVA on the Atomicity Countermeasure
8.2.3.2 Horizontal SVA on the Atomicity Countermeasure
8.3 Correlation Side-Channel Analysis
8.3.1 Group Scalar Randomization
8.3.1.1 Carry Leakage Attack
8.3.2 Additive Splitting
8.3.2.1 Carry Leakage Attack
8.3.2.2 Combined Attacks against Additive Splitting
8.3.3 Multiplicative Splitting
8.3.4 Euclidean Splitting
8.3.5 Point Blinding
8.3.6 Random Projective Coordinates
8.3.7 Random Curve Isomorphism
8.4 M Safe-Error
8.5 Invalid Point Attack
8.5.1 Output Point Validity
8.6 Classical Differential Fault Attack
8.6.1 Output Point Validity
8.7 Big Mac Attack
8.7.1 Multiplication with Random Permutation
8.8 Horizontal Correlation Side-Channel Analysis
8.8.1 Multiplication with Random Permutation
8.9 Address-bit DSCA
8.9.1 Random Register Address
8.10 Doubling Attack
8.11 Refined Side-Channel Analysis
8.11.1 Isomorphism Shifting
8.12 Zero Side-Channel Analysis
8.13 Classical Same Values Side-Channel Analysis
8.14 Horizontal SVA
8.15 Particular Point Timing Attack
8.16 Invalid Curve Attack
8.16.1 Curve Integrity Check
8.17 Sign Change Fault Attack
8.18 Coherence Check
8.19 Zero Word and SSCA
8.20 Template Attack
8.21 Twist Curve Attack
8.22 Invalid Point Attack and SSCA
8.22.1 Input Point Validity after a Randomization
8.23 Fault Attack on Coordinates Conversion
9 Differential Fault Attacks on ECDSA
9.1 Principle of the Method
9.2 Attacking ECDSA with the Classical Differential Fault Attack
9.3 Attacking ECDSA with the Sign Change Fault Attack
9.4 Attacking ECDSA with the Fault on the Coordinates Conversion
9.5 Synthesis
10 Summary of the Context of the Attacks
10.1 Key Recovery
10.2 Elliptic Curve Specificity
10.3 Implementation Access
10.4 Implementation Specificity
10.5 Number of Executions Needed
10.6 Input Access
10.7 Output Access
10.8 Fault Model
11 Synthesis
Conclusion and Perspectives
Bibliography
