Microarchitectural Side-Channel Attacks

Cryptanalysis is the science which evaluates the security of a cryptosystem and detects its weaknesses and flaws. Initially confined to the black-box model, where only the input and output data were considered, cryptanalysis is now broadened to the security evaluation of the physical implementation of a cryptosystem. The implementation attacks which compose physical cryptanalysis are divided into fault attacks, exploiting the effect of disruption of the normal functioning of the device, and side-channel attacks, exploiting the dependency between the instructions and data (including key bits) processed by a device and its physical characteristics (e.g. execution time, power consumption, electromagnetic (EM) radiations). In the scope of this thesis, we particularly focus on the latter attacks. “Every computation leaks information” and lowering the physical leakages of an implementation is indeed a complex task both from cryptographic and engineering viewpoints, especially when performance and cost enter the equation. The development of adequate countermeasures necessitates a thorough knowledge of the various vulnerabilities that the microcontroller induces. Although generic side-channel attacks such as Differential Power Analysis (DPA) can generally retrieve the key with weak assumptions on a cryptographic implementation, we show in this thesis that the focus on specific components and properties from the architecture of the target device may allow an adversary to yield better success in a key recovery and sometimes to thwart DPA countermeasures. First, we elaborate on attacks which deduce the cache activity of a device from single side-channel traces and algebraically exploit this information to recover the key. We propose different attacks against embedded software implementations of the Advanced Encryption Standard (AES) in the chosen- and known-plaintext scenarios and make them tolerant to environments where high noise or a partially preloaded cache would normally introduce errors in the key recovery. Second, we discuss the failure of standard DPA against the modular addition and propose a practical and generic approach to circumvent it. Third, we show that microarchitectural leakages and fault inductions can be exploited in a constructive way when induced by hardware Trojans implemented on general-purpose microprocessors. Such Trojans can either provide an adversary with a backdoor access to the trojanized device executing an arbitrary cryptographic software or serve to protect the Intellectual Property (IP) of the chip designer through digital watermarking. The last part concerns divide and conquer side-channel attacks such as DPA. Testing different combinations of key chunk candidates turns out to be very complex when the individual chunk recoveries are bounded in measurement complexity or performed in noisy environments. We address the so-called key enumeration problem with an efficient sorting method.La cryptanalyse a pour but d’évaluer la sécurité d’un cryptosystème et de déceler ses failles. D’abord cantonnée au modèle dit en boîte noire, où sont seulement considérées les données en entrée et en sortie de l’algorithme, la cryptanalyse prend maintenant également en compte l’implémentation physique d’un cryptosystème. Les attaques d’implémentation qui constituent la cryptanalyse physique sont composées d’une part des attaques par faute (exploitant les effets d’une perturbation du fonctionnement de l’appareil) et d’autre part des attaques par canal auxiliaire (exploitant les dépendances entre les instructions et données (dont la clé) traitées par l’appareil et ses caractéristiques physiques (telles que le temps d’exécution, la consommation électrique ou les émanations électromagnétiques). Dans le cadre de cette thèse, nous nous intéressons particulièrement à ces dernières. “Chaque calcul laisse fuir de l’information” et atténuer les fuites d’une implémentation est en effet une tâche complexe tant d’un point de vue algorithmique que technique, en particulier quand performance et coût entrent en considération. La conception de contre-mesures adéquates nécessite une profonde connaissance des diverses failles qu’un microcontrôleur peut induire. Bien que les attaques génériques par canal auxiliaire permettent généralement de retrouver la clé avec peu de connaissances sur l’implémentation cryptographique visée, nous montrons dans cette thèse que certains composants de l’architecture de l’appareil peuvent parfois permettre à un adversaire de retrouver plus efficacement la clé et de contourner des contre-mesures génériques. En premier lieu, nous traitons des attaques qui déterminent l’activité du cache d’un microprocesseur à partir de simples courbes de mesures et qui exploitent cette information pour retrouver la clé. Nous proposons différentes attaques à message choisi et à message connu sur des implémentations logicielles embarquées d’AES et les adaptons à la présence de bruit dans les mesures ou au préchargement partiel du cache. Ensuite nous abordons l’échec des attaques standard par analyse différentielle de la consommation sur les additions modulaires et proposons une approche générique et pratique pour y remédier. D’un angle de vue différent, nous montrons que les fuites microarchitecturales ainsi que les fautes peuvent être exploitées de façon constructive quand elles sont induites par des chevaux de Troie physiques implémentés sur des microprocesseurs. Ces chevaux de Troie peuvent fournir à un adversaire une porte dérobée vers les clés secrètes de l’appareil ou bien protéger la propriété intellectuelle du concepteur de la puce par un tatouage numérique. La dernière partie concerne les attaques par canal auxiliaire diviser pour régner. Trouver la bonne combinaison à partir de différents candidats pour chaque morceau de clé peut s’avérer difficile voire impossible, en particulier quand le nombre de mesures est limité ou quand les mesures comportent beaucoup de bruit. Nous proposons une méthode efficace d’énumération des clés en solution à ce problème