Symbolic binary-level code analysis for security. Application to the detection of microarchitectural timing attacks in cryptographic code

Les logiciels informatiques manipulent fréquemment des données secrètes, garantissant généralement leur confidentialité à l’aide de programmes cryptographiques. Dans ce contexte, il est crucial de s’assurer que ces programmes cryptographiques ne peuvent être exploités par un attaquant pour en extraire les données secrètes. Malheureusement, même si les algorithmes cryptographiques sont basés sur des fondations mathématiques solides, leur exécution dans le monde physique produit des effets secondaires pouvant être exploités par un attaquant. En particulier, un attaquant peut exploiter le temps d’exécution d’un programme pour inférer des informations sur ses entrées secrètes, ou pour extraire des données secrètes encodées dans la microarchitecture grâce aux attaques microarchitecturales. Plus récemment, les attaques Spectre ont montré qu’il est aussi possible d’exploiter les optimisations des processeurs — en particulier les mécanismes de spéculation — pour extraire des données secrètes.Dans cette thèse, nous développons des outils d’analyse automatique de programme permettant de vérifier la confidentialité des données secrètes dans les logiciels cryptographiques. En particulier, nous ciblons trois propriétés cruciales pour les programmes cryptographiques : (1) secret-erasure, qui s’assure que les données secrètes sont effacées de la mémoire à la fin d’un programme, (2) constant-time, qui protège des attaques microarchitecturales, (3) speculative constant-time, qui protège contre les attaques Spectre. Ces propriétés ont en commun deux caractéristiques qui les rendent difficiles à analyser. Premièrement, il s’agit de propriétés de paires d’exécution (c’est-à-dire de 2-hypersûreté), ce qui les rend incompatibles avec les outils de vérification habituels (conçus pour la sûreté). Deuxièmement, elles ne sont généralement pas préservées par les compilateurs.Dans cette thèse, notre objectif est de concevoir des outils d’analyse symbolique automatiques, modélisant des paires d’exécution, fonctionnant au niveau du code binaire, incluant les mécanismes de spéculation des processeurs, et passant à l’échelle sur des logiciels cryptographiques existants. Nos analyses sont basées sur l’exécution symbolique relationnelle — une adaptation de l’exécution symbolique à la 2-hypersûreté — que nous complétons avec des optimisations permettant de : (1) la rendre efficace au niveau binaire, et (2) de modéliser de manière efficace la sémantique spéculative des programmes. Nous proposons deux outils open source : Binsec/Rel, un outil pour la recherche de bugs et la vérification bornée de constant-time et secret-erasure ; et Binsec/Haunted, un outil pour détecter des vulnérabilités aux attaques Spectre. Notre évaluation expérimentale montre que nos optimisations permettent une amélioration drastique des performances en comparaison aux approches antérieures : elles diminuent le temps d’analyse, trouvent plus de bugs, et permettent la vérification de primitives cryptographiques jusqu’alors hors de portée des approches antérieures.Nous analysons, grâce à nos outils, un large éventail de primitives cryptographiques et de fonctions utilitaires de bibliothèques open source (telles que Libsodium, OpenSSL, BearSSL and HACL*) pour constant-time (338 binaires), secret-erasure (680 binaires), et Spectre (45 binaires). Au cours de ces travaux, nous découvrons quelques bugs nouveaux, ainsi que des faiblesses dans certaines protections logicielles.Programs commonly perform computations involving secret data, relying on cryptographic code to guarantee their confidentiality. In this context, it is crucial to ensure that cryptographic code cannot be exploited by an attacker to leak secret data. Unfortunately, even if cryptogtaphic algorithms are based upon secure mathematical foundations, their execution in the physical world can produce side-effects that can be exploited to recover secrets. In particular, an attacker can exploit the execution time of a program to leak secret data, or use timing to recover secrets encoded in the microarchitecture using microarchitectural timing attacks. More recently, Spectre attacks showed that it is also possible to exploit processor optimizations—in particular speculation mechanisms—to leak secret data.In this thesis, we develop automated program analyses for checking confidentiality of secret data in cryptographic code. In particular, we target three crucial properties of cryptographic implementations: (1) secret-erasure, which ensures that secret data are erased from memory at the end of the program; (2) constant-time, which protects against timing microarchitectural attacks; (3) speculative constant-time, which protects against Spectre attacks. These properties have two characteristics in common that make them challenging to analyze. First, they are properties of pairs of traces (namely 2-hypersafety), which makes them incompatible with the standard verification framework (designed for safety properties). Second, they are not always preserved by compilers.Our goal in this thesis is to design automatic symbolic analyses for pairs of traces, operating at binary-level, including processor speculations, and that scale on real-world cryptographic code. Our analyses are built on top of relational symbolic execution—the adaptation of symbolic execution to 2-hypersafety—that we complement with dedicated optimizations: (1) for efficient relational symbolic execution at binary-level, (2) for modeling efficiently the speculative semantics of programs. We implement our analyses into two open-source tools: Binsec/Rel, a tool for bug-finding and bounded-verification of constant-time and secret-erasure; and Binsec/Haunted, a tool for detecting vulnerabilities to Spectre attacks. Our experimental evaluation shows that our optimizations drastically improve performance over prior approaches, allowing for faster analysis, finding more bugs, and enabling bounded-verification on real-world cryptographic primitives whereas prior approaches times-out.Using our tools, we analyze a wide range of cryptographic primitives and utility functions from open-source libraries (including Libsodium, OpenSSL, BearSSL and HACL*) for constant-time (338 binaries), secret-erasure (680 binaries), and Spectre (45 binaries). Along the way, we discover a few new bugs, as well as weaknesses in standard protections schemes