A Systematic Approach to the Side-Channel Analysis of ECC Implementations with Worst-Case Horizontal Attacks
The wide number and variety of side-channel attacks against scalar multiplication algorithms makes their security evaluations complex, in particular in case of time constraints making exhaustive analyses impossible. In this paper, we present a systematic
- PDF / 2,381,467 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 161 Views
ICTEAM/ELEN/Crypto Group, Universit´e catholique de Louvain, Louvain-la-Neuve, Belgium [email protected] 2 Brightsight BV, Delft, The Netherlands
Abstract. The wide number and variety of side-channel attacks against scalar multiplication algorithms makes their security evaluations complex, in particular in case of time constraints making exhaustive analyses impossible. In this paper, we present a systematic way to evaluate the security of such implementations against horizontal attacks. As horizontal attacks allow extracting most of the information in the leakage traces of scalar multiplications, they are suitable to avoid risks of overestimated security levels. For this purpose, we additionally propose to use linear regression in order to accurately characterize the leakage function and therefore approach worst-case security evaluations. We then show how to apply our tools in the contexts of ECDSA and ECDH implementations, and validate them against two targets: a Cortex-M4 and a Cortex-A8 micro-controllers.
1
Introduction
State of the art. The secure implementation of Elliptic Curve Cryptography (ECC) is an important ingredient in modern information systems. In this paper, we are concerned with side-channel attacks against scalar multiplication implementations which have been the focus of continuous interest over the last 20 years. This literature informally divides these attacks in two main categories: attacks using a Divide and Conquer (DC) approach and attacks using an Extend and Prune (EP) approach – which we next survey. Attacks that belong to the first category aim at recovering the scalar bits independently and are therefore simple to analyze. They associate a probability or a score to each scalar bit. The scalar is trivially recovered if all the correct bits have the highest probability. If it is not the case, computational power can be used to mitigate the lack of side-channel information thanks to key enumeration [30,35,38]. If the key is beyond computational reach (e.g. beyond 260 ), rank estimation (which requires the knowledge of the key and is therefore only accessible to evaluators, not to concrete adversaries) allows estimating the computational security level of a leaking implementation [6,20,30,39]. c International Association for Cryptologic Research 2017 W. Fischer and N. Homma (Eds.): CHES 2017, LNCS 10529, pp. 534–554, 2017. DOI: 10.1007/978-3-319-66787-4 26
A Systematic Approach to the Side-Channel Analysis
535
k0 k1 k0
Pr [k2 = 1|k0 = 1, k1 = 1]
Pr [k1 = 1|k0 = 1] Pr [k2 = 0|k0 = 1, k1 = 1]
Pr [k0 = 1] Pr [k2 = 1|k0 = 1, k1 = 0] Pr [k1 = 0|k0 = 1] Pr [k2 = 0|k0 = 1, k1 = 0] Pr [k2 = 1|k0 = 0, k1 = 1] Pr [k1 = 1|k0 = 0] Pr [k2 = 0|k0 = 0, k1 = 1] Pr [k0 = 0] Pr [k2 = 1|k0 = 0, k1 = 0] Pr [k1 = 0|k0 = 0] Pr [k2 = 0|k0 = 0, k1 = 0]
Fig. 1. Conditional probability tree for a 3 bits scalar k = (k0 , k1 , k2 ).
Attacks using an EP approach recover the scalar bits in a recursive manner. Recovering the i-th bit requires to first recover all the previous ones. For a nbit scala
Data Loading...
