# Amélioration d’attaques par canaux auxiliaires sur la cryptographie asymétrique

Alice in cryptoland

I will tell you a typical day for Alice. To go to work, Alice takes public transport using her electronic pass. Upon arriving at work, she opens her office’s door with her identification badge. After saying hello to her colleagues, she moves to her office and identifies/authenticates herself on her computer session to have access to her company’s network and reads her emails encrypted in order to guarantee their confidentiality. At noon, she sends a message to Bob, so that he can join her to eat. She takes her meal tray and pays at the cash desk with her canteen badge. At the end of her working day, she goes to the pool using her hobbies’ card containing 20 hours of swimming. After, she picks up her medications using her vital card at the pharmacy. Then she takes bread at the bakery using the contact-less payment of her credit card. Arriving at home, she decides to buy the train tickets for the next weekend online using an e-card generated on her bank’s website. Then she settles on the sofa to watch a movie on demand on her connected TV while eating her meal. At the end of the day, Alice thinks where and when cryptography is present in my day?

The answer is all these daily actions, described previously. In most daily actions, Alice uses embedding devices with cryptography, when Alice uses a card such as electronic pass, identification badge, etc. All these cards permit to identify and authenticate Alice. Each transactions/actions may be made with these card save and have got a signature to avoid the repudiation by Alice. When Alice receives e-mails and sends a message to Bob, the message was encrypted and decrypted to insure the confidentiality and integrity of the message. In general case, the video was encrypted for the movie on pay-tv using broadcast encryption. Alice thinks that cryptography takes an important place in her daily.

In a world where information is increasingly paperless, computer security has taken an important place in everyday life. Cryptography’s aims cause the strongest guarantees on information security. For its security, the cryptosystems claim to be “sure” when they are demonstrated by mathematical proofs. The oldest cryptography names secret key cryptography or symmetric cryptography. It allows encrypting and decrypting a message using a common key shared between each participant. Its main advantage is that the computation is very efficient, but requires the exchange of a common secret. Since three quarters of the 20th century, the other way is asymmetric cryptography. It allows a secure exchange without sharing common secret, but calculations require more memory and computing time. Asymmetric cryptography addresses different needs such as key exchange and digital signature. RSA, Diffie-Hellman, and ElGamal have been used for decades, and elliptic curve  cryptography (ECC) algorithms such as ECDSA [ANS99] are more and more deployed. ECC pairing-based cryptography has recently been accelerated in practice and is thus becoming practical [NNS10]. For example, the construction of “pairing friendly” elliptic curves is an active subject [GV12]. Homomorphic encryption schemes are getting more practical and are progressively considered viable solutions for some real-world applications requiring strong privacy. All these algorithms use large numbers and take place in mathematical structures such as finite rings and fields, which enables powerful mathematical properties but also facilitates attacks.

My doctoral studies focus only on the asymmetric cryptography such as RSA scheme and cryptography based on elliptic curve. The classical algorithms security level is oblivious to the implementation on the cryptosystem on a physical device such as computer, smart-phone, smart-card, etc. In fact, a concrete device possesses physical properties: it consumes power current; it produces electromagnetic and photonic emanation. Moreover, the execution duration of the computation can vary on the concrete device. Each physical parameter cited previously no exhaustively allows a kind of attack, who implies a new evaluation of the security of these cryptosystems. These attacks are a part of cryptanalysis and are named Side Channel Analysis (SCA). These attacks deduced information from the power consumption, the electromagnetic and photonic emanation, etc. A clever attacker can retrieve secret information by analyzing the involuntary leak. To be more precise, there are two ways to extract information from side channel: either observed a leakage during an execution, named passive attack or disturbed using a fault injection during an execution, named active attack. Passive attacks are an observation of some side channels during a cryptographic computation and do not modify its execution. Active attacks disturb voluntarily the execution of the cryptographic computation. The first proof of concept of these attacks is a 20-year old. Since there are an explosion in the number of attacks published, the discovery of new side channel or application of this side channel analyze. Each applied attack depends of the choice of implementation and/or countermeasures used on the device. The main consequence is the security evaluation of cryptosystems on a device becomes increasingly complicated.

CLiCours.com :  Altérations biomécaniques d'individus avec une CAl lors d'un atterrissage d'un saut unipodal

This thesis is about the security evaluation of cryptographic algorithm implemented on embedded device, particularly, the security of asymmetric cryptography against side channel attacks. The main side channels used are execution time, power consumption and electromagnetic emanation. The power consumption and the electromagnetic emanation require probe and oscilloscope in order to be measured. The measurements are named acquisitions. The execution time of asymmetric algorithm is larger than a symmetric algorithm; it increases the memory for each acquisition. The quality of an acquisition depends on the sampling rate on the oscilloscope, the position probing and the quality of the probe. The three parameters should be optimized to improve the quality of the signal information. The increasing of sampling rate of the oscilloscope increases also the memory size of acquisitions. The increasing of the number of acquisition can improve the analysis by reducing the noise of the signal and increasing the signal information. The number of acquisitions must be reduced to limit the global time of the side channel attack. Indeed, a large number of huge size acquisitions increases the measurement time, the pre processing time like alignment, filtering, etc. and the analysis time, as well as the computational power. In the industrial context, the evaluation of embedded device takes into account time and specialized equipment required for the attacks .

 Table des matières 1 Introduction 1.1 Alice in cryptoland 1.2 Context 1.3 Contributions 1.4 Outline 2 Asymmetric cryptography and its implementation 2.1 Introduction 2.2 Mathematics over RSA scheme 2.2.1 RSA keys 2.2.2 RSA encryption 2.2.3 RSA implementation 2.3 Mathematics over elliptic curve 2.3.1 Definition of elliptic curve domain 2.3.2 Elliptic curve scalar multiplication 2.3.3 Group law: Addition and doubling operations 2.4 Modular Multiplications Implementation 2.4.1 Multiplication over large numbers 2.4.2 Euclidean division 2.4.3 Montgomery reduction 2.4.4 Barrett Reduction 2.4.5 Special moduli reduction 2.5 Conclusion 3 Side Channel Attacks on asymmetric cryptography 3.1 Introduction 3.2 Simple Side Channel Analysis 3.2.1 Attack 3.2.2 Extra-information on simple side channel techniques 3.2.3 Countermeasures 3.3 Differential Side Channel Analyses 3.3.1 Non supervised attacks 3.3.2 Template attacks 3.3.3 Countermeasures in RSA 3.3.4 Countermeasures in ECC 3.4 Horizontal Analysis 3.4.1 Horizontal attacks 3.4.2 Collision on Doubling operation 3.4.3 Timing execution attacks 3.5 Extra-Reductions Analysis 3.5.1 ERA 1: attacks on RSA without protections 3.5.2 ERA 2: attacks on RSA with blinding exponent 3.5.3 ERA 3: attacks on RSA with message blinding 3.6 Fault attacks 3.6.1 Attacks 3.6.2 Countermeasures 3.7 Conclusion Conclusion

Télécharger le document complet