Alexander Schaub

Formal methods for the analysis of cache-timing leaks and key generation in cryptographic implementations

Keywords: 1, 2, 4 SGX Security Guard Extensions. 17, 18

Finally, I would like to thank my family for their support, and my soon-to-be wife Luce-Marie

M éthodes formelles pour l'analyse de fuites cache-timing et la g én ération de cl és dans les impl émentations cryptographiques

Introduction xxi

ACKNOWLEDGEMENTS.

First and foremost, I would like to thank my PhD advisors, Oliver Rioul and Sylvain Guilley, for their invaluable advice, patience and enthousiasm during my PhD study. Our fruitful collaboration started back in 2013, saw the publication of numerous papers, and allowed me now to earn a PhD. I will always remain grateful for all the time and effort they spent to help me in my studies.

I would also like to thank the reviewers, Ingrid Verbauwhede and Avi Mendelsson, for accepting to review my manuscript, and all the jury members, David Naccache, Yuval Yarom, Joseph Boutros, Pierre Loidreau and Jean-Luc Danger, for attending my defense. I appreciated your thoughtful remarks and suggestions, and found the discussion we had very enriching. I would like to extend my gratitude to all the faculty members from COMELEC I had the pleasure to interact with during my time at Télécom Paris -especially Jean-Luc Danger, whose technical knowledge of PUFs and their designs has been invaluable for my work.

These three and half last years would have been much more dull without all the great colleagues with whom I shared my joys and doubts. Michael Timbert, Sébastien Carré, Thuy Ngo, and all the others: thank you very much for all the time we spent together, in front of a whiteboard or around a beer. Bien que les systèmes d'exploitation mettent en oeuvre une séparation de la mémoire en fonction des processus qui s'exécutent sous son contrôle, une telle séparation n'est pas implémentée pour le cache. Ainsi, tous les programmes s'exécutant sur le même coeur (pour les caches L1 et L2) voire le même processeur (pour le cache L3) partagent le même cache. Un programme malveillant peut alors manipuler l'état du cache pour déduire des informations sur l'état d'exécution d'un programme ciblé. Plus précisément, des informations concernant les adresses mémoire accédées par le programme cible peuvent être retrouvées. Il peut s'agit des indices utilisés pour accéder à des tableaux, mais aussi des directions des branchements. En effet, les instructions exécutées par un programme sont également mis dans le cache, et en fonction de la direction des branchements, seules les instructions d'une des deux branches (branche if ou branche else) sont exécutées, et donc chargées.

L'objectif principal de la thèse est de détecter et prévenir ce genre de fuites. A cet égard, j'ai développé un outil qui effectue une analyse de dépendance sur des programmes écrits en C afin de déterminer quelles variables contiennent des valeurs dépendant d'un secret, et lève une alerte lorsqu'une telle variable risque de fuiter (branchement ou accès à une adresse mémoire dépendant de sa valeur). Le fonctionnement de cet outil est le suivant.

Tout d'abord, les données sensibles doivent être identifiées et annotées. Il s'agit principalement des clés privées d'implémentations cryptographiques et de l'aléa secret utilisé par certains algorithmes. Ensuite, l'outil détermine l'ensemble des variables qui dépendent de ces données sensibles. Pour cela, un graphe bipartite est construit, reliant les variables définies dans le programme en C à analyser, à un certain nombre de valeurs. La première valeur est la valeur spéciale secret, qui indique que la variable contient des données sensibles. Ce n'est pas la seule valeur à considérer, cependant. Premièrement, xv pour des raisons de performance, il est préférable d'analyser chaque fonction séparément. Or, lors de l'analyse d'une fonction, on ne peut pas encore déterminer si les arguments avec lesquels elle sera appelée dépendent de données sensibles ou non. Ainsi, les valeurs initiales (abstraites) des arguments de fonctions sont également considérés comme des valeurs dans cette analyse. Cela permet de composer l'analyse de fonctions en substituant les valeurs initiales par les valeurs des variables lorsque celle-ci est appelée. Finalement, il faut aussi déterminer quelles variables peuvent être référencées par les pointeurs définis dans le programme en C. Pour cela, les adresses mémoires de toutes les variables sont également des valeurs considérées dans le graphe de dépendance. Bien sûr, la valeur exacte des adresses est inconnue puisque le programme analysé n'est jamais exécuté. À la place, une valeur abstraite est employée pour désigner l'adresse de chaque variable. Ce graphe de dépendance est ensuite mis à jour lors de l'analyse du code source fourni.

En parallèle, les fuites sont enregistrées: il s'agit des valeurs entrant dans le calcul des adresses mémoires accédées (comme les indices de tableaux) ainsi que les valeurs utilisées pour calculer le résultat d'un branchement conditionnel. Le programme analysé est considéré comme sûr lorsque la valeur spéciale sensible ne fuite pas.

Cet outil est ensuite utilisé pour analyser la plupart des candidats du processus de standardisation de cryptographique post-quantique initié par le NIST. Comme les ordinateurs quantiques seraient capables de casser les algorithmes à clé publique actuellement déployés (comme RSA et ECDSA), il est nécessaire de trouver des primitives cryptographiques alternatives. Puisque ces nouveaux algorithmes sont relativement récents, leurs implémentations ont été moins scrutés jusqu'à présent. Parmi les 21 soumissions qui ont pu être traités, environ un tiers contenaient de potentielles fuites exploitables par des attaques "cache-timing".

La deuxième moitié de la thèse est consacrée aux "physically unclonable functions", ou PUFs. Ce sont des circuits dont on peut extraire des identifiants imprédictibles mais stables. De petites variations incontrôlables dans les propriétés des semi-conducteurs sont amplifiés pour produire un comportement imprédictible. Cela permet, par exemple, de générer des clés cryptographiques. Des garanties théoriques pour deux caractéristiques fondamentales des PUFs sont présentées dans cette thèse, applicables à une large famille de PUFs: la stabilité de l'identifiant, perturbée par des bruits de mesure, et l'entropie disponible, dérivée du modèle mathématique du PUF.

Le principe de fonctionnement des PUFs est le suivant: afin de générer un bit d'identifiant, un challenge est envoyé au PUF. Ce challenge correspond à une suite de n bits, où n dépend des caractéristiques du PUF. Dans l'idéal, la réponse que constitue ce bit d'identifiant est stable (toujours identique pour un même PUF et challenge) mais imprédictible (on ne peut pas le "deviner" avec moins de 50% de chances de se tromper, même en connaissant les réponses à d'autres challenges pour un même PUF ou ceux à n'importe quel challenge pour un PUF différent).

Le défaut de stabilité provient essentiellement des bruits de mesure. En effet, les PUFs que j'ai considérés dans cette thèse sont basés sur des boucles d'inverseurs, permettant de construire des oscillateurs dont la fréquence varie légèrement d'une instance à l'autre. La réponse du PUF est ensuite obtenue en calculant la différence entre deux fréquences d'oscillations dans le PUF. Cela peut provenir de deux oscillateurs distincts dans le circuit, comme pour le RO-sum PUF [START_REF] Yu | Recombination of physical unclonable functions[END_REF] ou le Ring Oscillator PUF [START_REF] Hajimiri | Jitter and phase noise in ring oscillators[END_REF], ou de deux configurations [START_REF] Cherif | An easy-to-design PUF based on a single oscillator: The loop PUF[END_REF]. En modélisant la fréquence d'oscillation et le bruit de mesure par des lois normale, modélisation vérifiée par des mesures et des simulations, ont peut obtenir des expressions explicites du taux d'erreur binaire (ou BER pour Bit Error Rate). Si la fréquence des oscillations suit une loi normale centrée de variance Σ 2 et le bruit gaussien additif une loi normale centrée de variance σ 2 , alors, en définissant le ratio signal sur bruit (ou SNR pour Signal to Noise Ratio) par Σ 2 σ 2 , on peut montrer que le taux d'erreur moyen du PUF est égal à

BER = 1 π arctan( 1 √ SN R ).
Même pour des valeurs élevées du SNR, cette valeur reste relativement importante (voir Figure 2), de l'ordre de quelques pour cents même pour des valeurs du SNR au-dessus de 4000.

Ce taux d'erreur élevé provient principalement des quelques challenges aux réponses instables. En effet, comme la différence de fréquences, utilisée pour calculer le bit de réponse, suit une loi normale, une proportion non négligeable de ces différences ont une valeur autour de 0, résultant en un taux d'erreur très important pour ces réponses, autour de 50%. Une première méthode pour améliorer la fiabilité du PUF consiste alors à filtrer les challenges qui résulteraient en une différence de fréquence inférieure, en valeur absolue, à un seuil égal à un multiple de σ, par exemple W σ. On peut alors montrer que le taux d'erreur moyen des challenges restants après le filtrage est égal à Ce filtrage, cependant, diminue l'entropie utile du PUF: comme certains challenges sont mis de côté, la taille des identifiants générés est plus petite. En moyenne, on montre que, en supposant que le PUF sans filtrage fournit n bits de réponse indépendants, l'entropie restante après filtrage est égale à

BER f ilt = 2 erfc( W √ 2 √ SNR ) T (W, 1 √ SNR ) + 1 4 erf( W √ 2 √ SNR )(erf( W √ 2 ) -
H = n • erfc( W √ 2SNR
).

En combinant ces deux formules, on peut caractériser entièrement le compromis fiabilité-entropie défini par le filtrage par seuil (voir Figure 3). En général, le SNR est fixé pour un modèle de PUF donné. La caractérisation permet alors de prévoir comment dimensionner le PUF pour obtenir une fiabilité et une entropie donnée.

Une deuxième méthode pour améliorer la fiabilité de ces PUFs consiste à changer de métrique pour obtenir un bit de réponse: au lieu de prendre le signe de la différence de fréquences, on peut définir deux seuils et considérer que la réponse du PUF est de 0 si la différence de fréquence est comprise entre ces deux seuils, et de 1 sinon. En choisissant bien ces seuils, qui dépendent de la variance des fréquences σ 2 , l'entropie par réponse reste de 1 bit. En choisissant judicieusement deux paires de deux seuils, et en appliquant la paire de seuils en fonction de la différence de fréquences de façon à minimiser le taux d'erreur, on peut améliorer la fiabilité du PUF sans diminuer son entropie (voir Figure 4). Les désavantages de cette méthode sont la complexité supplémentaire introduite par les comparaisons aux seuils, et surtout la nécessité de Mean BER Use of two-metric method Raw BER (no helper data)

Figure 4: Taux d'erreur binaire en utilisant deux paires de seuils différences de fréquence. En effet, une mauvaise estimation de cette grandeur biaiserait la réponse des PUFs. Enfin, la dernière partie de la thèse concerne l'estimation de l'entropie des PUFs. Dans la précédente partie, nous avons supposé que toutes les réponses des PUFs étaient indépendantes. Or, pour une large famille de PUFs, comprenant les Arbiter PUF [START_REF] Suh | Physical unclonable functions for device authentication and secret key generation[END_REF], les RO-sum PUFs [START_REF] Yu | Recombination of physical unclonable functions[END_REF] et les Loop PUFs [START_REF] Cherif | An easy-to-design PUF based on a single oscillator: The loop PUF[END_REF], il n'est pas possible d'extraire plus de n réponses indépendantes pour un PUF de taille n, alors qu'il existe 2 n challenges possibles. En autorisant l'utilisation de challenges pour lesquels les réponses sont liées, l'entropie que l'on peut extraire d'un tel PUF est alors augmentée. Cependant, calculer cette entropie n'est pas évidente. En effet, chaque réponse à un challenge pouvant prendre deux valeurs différentes, il pourrait existe au total jusqu'à 2 2 n PUFs différents. Cependant, tous ces PUFs ne sont pas tous réalisables. En effet, la réponse d'un PUF à un challenge donné suit, pour les PUFs considérés, la formule suivante:

b = sign( n i=1 c i x i ) = sign(c • x)
où c i représente la i-ème bit du challenge (-1 ou +1) et x i représente une différence de fréquences "élémentaire", distribuée selon une loi normale. Dans ma thèse, je rapproche cette formulation des fonctions booléennes à seuil (ou BTF pour Boolean Threshold Function). Ceci permet de démontrer, d'une part, que l'entropie de ces PUFs, même en considérant tous les 2 n challenges possibles, ne peux dépasser n 2 . D'autre part, en utilisant les propriétés de symétrie établies pour les BTFs, j'ai pu développer un algorithme Cependant, les PUFs utilisés habituellement ont des tailles bien plus élevés, de l'ordre de n ≈ 100 ou plus. La simulation de l'entropie n'est alors plus possible. Cependant, les résultats obtenus semblent indiquer que l'entropie de Shannon suit approximativement la max-entropy, asymptotiquement équivalente à n 2 . Si cette tendance est confirmée, cela montrerait que l'on peut théoriquement extraire bien plus de n bits d'entropie d'un PUF de taille n. Pour appliquer ces résultats en pratique, il faudrait également déterminer quels sont les challenges optimaux à choisir. En effet, pour un PUF de taille par exemple n = 32, il n'est pas envisageable de produire un identifiant en utilisant tous les 2 32 ≈ 4 • 10 9 challenges possibles. La question est alors de savoir si c'est possible de choisir, par exemple, k 1 • 32 2 challenges pour obtenir une entropie de k 2 • 32 2 bits, avec k 1 et k 2 des constantes qui restent à déterminer.

Introduction

Buying products on the Internet, chatting online with friends and family, or working remotely from anywhere on earth: these activities are part of our everyday life. They would not be possible without modern cryptography. It prevents our credit card information from being stolen, our private conversations to be shared with strangers, and industrial secrets from being revealed.

Such accidents still happen, because getting the security of any system right is a challenging problem. The news is filled with reports of data breaches, credentials thieves and stolen credit card numbers. However, the underlying cryptography is almost never at fault. For instance, 20 years after is has been standardized, the best-known attacks against the popular Advanced Encryption Standard (AES) reduce its theoretical security by a mere two bits. While the key sizes for RSA have had to be increased in order to account for algorithmic advances and increases in computing power, large key sizes (2048 bits and above) are still considered out of reach for even the most powerful attackers. As of today, the confidence in the currently deployed cryptographic algorithms remains high.

But the same cannot be said for the implementations of these cryptographic algorithms. The first practical side-channel attacks against a specific implementation of AES were published in 2005 and improved ever since. A weak method of generating private RSA keys, revealed in 2017 under the name ROCA vulnerability, compromised the security of millions of smartcards and other sensitive devices. Cache-timing side-channels have been used to break all kinds of cryptographic algorithms: RSA, ECDSA, AES, BLISS, . . . . Therefore, securing the concrete implementation of cryptographic algorithms constitutes today a major challenge. While there are proofs of security for numerous cryptographic algorithms, less effort has been put into at least verifying that the implementations are also safe.

A significant number of causes can compromise the security of an implementation: timing leaks, data leaks through the cache, numerous "classical" programming errors, bad handling of edge cases and invalid values, . . . Whether a given cause leads to a cryptographic break depends on numerous external factors: the hardware on which the program runs, the presence or absence of an operating system, the type of operating system, the general mitigations that have been implemented, and more.

Furthermore, the emergence of quantum computers poses a new threat to traditional cryptographic algorithms. Public-key cryptography needs to be redesigned in order to resist against attacks using these new machines when they will become available. Algorithms that can resist against quantum computers are known as post-quantum cryptography algorithms, and designing such algorithms is currently an active field of research. Implementing these xxi xxii INTRODUCTION algorithms securely is another challenge. Indeed, the implementations are very recent and have therefore been analyzed much less than the implementations of traditional cryptographic algorithms. The risk of remaining implementation errors or side-channel leaks is quite high.

Verifying that an implementation cannot be compromised therefore amounts to a daunting task, given the variety of existing implementations and the compounding complexity of the causes and contexts that need to be taken into account. While it is possible to verify that an implementation is safe on a specific context-processor model and version, operating system version and configuration-the effort becomes almost infeasible when multiplied by the number of different contexts that can be encountered in the real world.

A more feasible approach consists in first abstracting the whole complexity of the context in order to create a simpler model, and then show interesting properties on this model. The drawback incurred by this approach is a loss of precision in the analysis. However, the results obtained by such an analysis are much more broadly applicable-on every system that fits the description of that model.

A similar approach can be applied to another crucial component of implementation security: the generation of keys. It ultimately requires a physical source of randomness, but assessing the entropy of that source with high confidence is not trivial. Statistical test suites can help to find some biases but offer no theoretical guarantees for the quality of the random generator. However, one can abstract the architecture of the generator in order to obtain a model which these guarantees can be derived from.

In this thesis, we will apply this line of reasoning to two independent problems in security, one in software security, the other in hardware security. The first half of this thesis will explore the automatic detection of cache-timing attacks. It will feature a tool written during my thesis that performs abstract execution of programs written in the C programming language in order to detect potential cache-timing leaks, as well as extensive case reports highlighting its performance on real-world code and in particular on the implementations of post-quantum cryptography algorithms.

The second half of this thesis deals with physically unclonable functions, or PUFs. These are hardware security primitives that ideally exhibit unpredictable physical properties (propagation delays, bias in memory cells, . . . ) that can be exploited to obtain a consistent identifier (a bitstring) from a given PUF. Two fundamental characteristics of a PUF are therefore the measure of unpredictability of the properties and the consistency of its response. These two characteristics are the subjects of two chapters in the second half of this thesis. The distribution of both the PUF characteristics and the measurement noise are modeled for a certain class of PUFs, which allows us to compute their entropy-a measure of the unpredictability-and the bit error rate (BER) of the identifier generated using different methods-a measure of the response consistency. For the first time, this provides theoretical guaranties on the PUF behavior, allowing for more efficient designs and higher confidence in the security of the PUFs. This manuscript is divided into six chapters, of which the first three cover cache-timing side-channel attacks and the next three cover PUFs.

Chapter 1 consists of an introduction to cache-timing side-channel attacks. These attacks threaten the security of cryptographic implementations executed on any processor xxiii that possesses a cache. Because the cache is often shared between programs executing on the same processor, sometimes even on different processor cores, they constitute a shared state between an attacker and its victim process. If the state of the cache depends on sensitive information handled by the victim process, such as cryptographic keys or sensitive randomness, then the attack can break the security of that implementation by strategically probing the cache. This is the case when the victim process branches on a sensible value, or accesses memory at an address that depends on a sensitive value (such as an array access at a sensitive offset). Several ways of probing the cache have been published during the last few years, and this chapter summarizes a few of them. They differ in both scope (vulnerable cache type, applicable processor families) and performance (period between two probing events, false positives and negatives).

Chapter 2 presents a methodology for automatically detecting potential cache-timing leakages in programs written in the C programming language. It consists in a static analysis in two parts, which are performed in parallel. The first is a dependency analysis, which determines which variables might contain sensitive values. It has to take into account pointer aliasing, dependency tracking through function calls, and indirect dependency flow. The second part consist in recording which variables govern the program control flow and which ones are used to compute addresses for memory accesses. If such a variable depends on a sensitive value, a leakage is reported. This methodology is implemented in the tool STAnalyzer which is available from https://gitlab.telecom-paris.fr/sen/ stanalysis.

Chapter 3 summarizes the results obtained with this tool on several real-world examples: known cache-timing vulnerabilities on the NSS and wpa_supplicant libraries, as well as most candidates of the first and second-round candidates for the NIST post-quantum cryptography standardization process. All known vulnerabilities were caught by this tool, although a larger number of unrelated warnings were also triggered by the NSS library. Some may be false positives, while others are potential vulnerabilities that cannot be ruled out by static analysis. A large number of the first round post-quantum candidates found to have potential vulnerabilities, while the updated implementations of the second round candidates were generally more robust to cache-timing attacks. The tool proved to be useful on these real-world examples, uncovering real issues without being overwhelmed by false positives.

Chapter 4 introduces PUFs, and explains what they are used for and how they can be build. Several kinds of PUFs are presented, with a special emphasis on so-called delay PUFs. These exploit delay differences in oscillating circuits, so that each manufactured circuit exhibits a different oscillation frequency. Numerous PUF designs are based on this basic building block: arbiter PUF, ring-oscillator (RO) PUF, RO-Sum PUF, loop-PUF among others. These designs are described in more detail in this chapter.

Chapter 5 presents results about the reliability of PUFs, especially delay PUFs. Because of inherent fluctuations of the oscillating frequency, different PUF measurements might lead to different identifiers, which defeats the purpose of a PUF. The authentication of the PUF might fail, and if the error rate is too high, it might never succeed at all. Different methods to improve the PUF reliability are presented in this chapter. For instance, one can filter out "unreliable" elements from the PUF response. After proposing a model for

INTRODUCTION

the PUF noise and delay distribution, we present a closed-form formula to determine the new error rates after filtering. This provides a more efficient way to predict the reliability of a PUF and therefore choose the right design parameters for a given application. Another method that consists in changing the way delay measurements are performed in order to obtain the PUF identifier is also presented, and we compute the reliability for this method. The theoretical results are then compared with measurements from real PUF circuits.

Chapter 6 presents results about the entropy of delay PUFs. The abstract description of these PUFs reveals a link between them and a class of boolean functions called boolean threshold functions (BTF). Using theoretical results from the study of BTFs, we derive an efficient algorithm that allows us to estimate the entropy of the PUF distribution up to PUFs of size 10. These results suggest a quadratic increase in entropy with the PUF size. While we show that the entropy is indeed bounded by a quadratic function of the PUF size, the asymptotic behavior for the Shannon entropy remains an open question.

Chapter 1

State of the Art in Cache-Timing Attacks

Know yourself and know your enemy, and you will never be defeated.

Sun Tzu, The Art of War.

Modern CPUs utilize numerous optimizations in order to increase their performance. The instructions that need to be executed and the data that these instructions are working with need to be loaded from memory. Usually, these reside in the main memory or RAM. However, accessing the RAM is slow, taking about 100 to 150 cycles before the first bytes can be read [2]. In order to overcome this bottleneck, CPUs include several layers of much faster cache, with access times as low as 4 cycles [2]. Programs that make use of them can see a significant improvement in performance. However, the lack of isolation between the cache lines accessed by different processes (see Section 1.1.2) can lead to security risks, as described in the next sections.

The security threat created by the caches is exacerbated by other performance optimizations. Speculative execution is a mechanism by which the CPU executes instructions before it can be determined whether they should be executed or not. For instance, instructions that try to access data for which the process has no access rights should cause the process to be aborted. Because checking for the access rights takes time, and access rights violations are fairly rare in most programs, it makes sense, from a performance point of view, to continue executing instructions while simultaneously checking for the access rights. In case of a violation, the executed instructions are then rolled back before the process is stopped. Speculative execution can also happen when the CPU executes a branching operation, which is used to implement conditional statements and loops. Because determining which branch should be executed (the if or the else branch, loop continuation or loop exit) might also be slow in some situations, the CPU can choose to execute the instructions in one branch, and roll back the state if it chose the wrong 2 CHAPTER 1. STATE OF THE ART IN CACHE-TIMING ATTACKS branch. However, the cache state is often not rolled back, and it might reveal sensitive informations. This is the main cause of the Spectre and Meltdown attacks, major security vulnerabilities that affected a wide variety of computer systems around the world [START_REF] Kocher | Spectre attacks: Exploiting speculative execution[END_REF][START_REF] Lipp | Meltdown: Reading kernel memory from user space[END_REF], which exploit speculative execution respectively after a branch misprediction and an access right violation.

The remainder of this chapter is organized as follows. First, I will explain the cache architecture of modern CPUs and the security implications of their organization. I will then present different methods that allow an attacker to infer information about the cache state, before presenting a brief overview of published attacks that use these methods.

General Computer Architecture Background

Virtual Memory

The OS has to deal with two memory spaces: physical and virtual memory.

Physical memory represents the memory available to the operating system, and depends on the hardware it runs on. It corresponds to the amount of RAM available to the processor (plus, optionally, some reserved hard disk space which is not relevant to the discussion).

Processes running on the OS, however, do not have directly access to the physical memory. Instead, memory accesses are done via virtual memory, and the translation between physical and virtual memory is performed by the OS. There are two main reasons for this design. Firstly, it reduces the complexity of the memory allocation for processes, as they would otherwise need to know what memory is used by all other processes. Second, it allows for isolating the memory between processes, so that one rogue process cannot read or modify sensitive data of another process.

The operating system presents to each process a virtual address space of size 2 64 bits, which might or might not be addressable in its entirety1 . When a process accesses a valid virtual address for the first time, the operating system will provision some physical memory, and record the mapping between the virtual address, the identifier of that process, and the address of the provisioned physical memory. Since provisioning and recording the mapping causes a delay, it is not done at the individual byte level. Rather, a whole page is provisioned at once. Their size is usually 4 KiB but depending on the system configuration, may be bigger. The mapping between virtual and physical addresses is encoded in so-called page tables, and cached in the Translation Lookaside Buffer (TLB).

Cache Architecture

A cache is a reserved set of fast memory, used to improve the performance of a CPU. Contrary to the RAM, programs cannot directly access the content of a cache. Instead, every time the CPU needs to fetch data from RAM, it first checks whether it is already present in one cache. If so, the program experiences a lower latency for accessing the data -this is called a cache hit. If not, the latency is higher, but the data is saved into one 1.1. GENERAL COMPUTER ARCHITECTURE BACKGROUND 3 or more caches in order to speed up subsequent memory accesses, and this constitutes a cache miss.

Albeit some details of the cache implementation are hidden by the CPU manufacturers, the general behavior is well documented and of particular importance for programmers wishing to optimize their implementation, as well as those, as we will see, that care about their security. Modern processors make use of three distinct levels of cache, named L1, L2 and L3. The L1 cache is the fastest, but also smallest, of the three levels. Every processor core possesses two L1 caches, one for caching data (L1D cache), the other for caching instructions (L1I cache). Their size is in general around 32KiB each, and the latency can be as low as 4 cycles [5, §2.1.3]. This cache being private to each physical processor core, processes executing on distinct cores do not have access to each other's L1 cache. However, two processes executing on different virtual cores, but on the same physical core on hyper-threaded processors, do share the L1 cache.

Cache Hierarchy

L3 (unified, inclusive) L1d L1i L2 (unified) Core #0 / #1 L1d L1i L2 (unified) Core #2 / #3 L1d L1i L2 (unified) Core #4 / #5 L1d L1i L2 (unified) Core #6 / #7
The L2 cache is slightly larger than the L1 cache, at around 256KiB. It has also a higher access time of 12 cycles [5, §2.1.3], and is private to each physical processor core. Only one cache for both data and instructions is present on modern processors.

Finally, the L3 cache (or LLC, for Last Level Cache) is shared among all processor cores. Its size varies depending on the CPU model, but it is generally comprised between 8MiB and several dozen MiB [6] for modern consumer-oriented CPUs. Also, the L3 cache is inclusive, that is, any data stored in the L1 or L2 cache of any core must be also present in the L3 cache.

CHAPTER 1. STATE OF THE ART IN CACHE-TIMING ATTACKS

Both the L2 and L3 caches are unified, meaning they can hold indifferently instruction or data.

Cache Organization

Caches are organized into so-called cache lines (sometimes called cache blocks). The cache line is the smallest unit of memory that is replaced in the cache, and their size is usually 64 bytes. Whenever data is loaded from the RAM into the cache, or from one cache to a smaller cache, the data corresponding to a whole cache line is transferred. Similarly, when a cache line is evicted from the cache, due to a special assembly instruction (clflush) or to make room for new data, the whole cache line is removed at once. This mechanism serves to reduce the number of transfers between the main memory and the caches.

Cache lines themselves are organized into cache sets. The 64 bytes starting at a given 64-byte aligned (physical or virtual) address can only be saved to a limited number of cache lines. These cache lines form the cache set of that address. For a given cache, the number of those cache lines is fixed and the same for every address, but it might vary between the different caches of the same processor. If there are n possible cache lines for a given address, the cache is said to have a n-way associativity (see Figure 1.2). If this set is determined from the physical address of the concerned memory region, then it is called physically indexed, and virtually indexed otherwise. Under certain conditions, data can be loaded into the cache even though no data from the cache line has been accessed. This is known as data prefetching [5, §2.3.5.4]. For instance, if the memory is accessed sequentially, two cache lines might be loaded into the cache on every cache miss -the line corresponding to the accessed data, as well as the next 64 bytes of memory (or the previous ones, if the memory is accessed sequentially but in reverse order).

Security Implications of the Cache

The cache constitutes a shared resource between processes. By default, no isolation is enforced between cache memory belonging to different processes. This opens up the possibility of side-channel attacks exploiting the cache.

If an attacker is able to determine the state of the cache after or during the execution of a program (see Section 1.3 for details), and if the state of the cache depends on some sensitive values handled by the program, then the attacker is able to gain knowledge about 1.2. SECURITY IMPLICATIONS OF THE CACHE 5 these sensitive values. We speak of leakages if the cache state depends on sensitive values. Leakages arise for mainly two reasons.

Secret-dependent Memory Access

One reason for leakages to happen are secret-depend memory accesses. These occur if a program accesses memory at an address that depends on secret data, either via pointer arithmetic, or by accessing an array at a secret-dependent index. For instance, one round of the popular AES [START_REF] Daemen | AES proposal: Rijndael[END_REF] encryption algorithm consists in a bytewise substitution, which is most efficiently implemented using a lookup table, and the index of the lookup operation depends on the secret key.

Secret-dependent memory accesses can lead to two kinds of vulnerabilities caused by the cache. First, the total execution time of the victim process might vary depending on sensitive data. For instance, this behavior has been demonstrated by Bernstein on a (now outdated) AES implementation found in OpenSSL [START_REF] Bernstein | Cache-timing attacks on AES[END_REF] and lead to a full key recovery attack. It is due to the fact that the number of cache misses during the execution of an AES encryption varies depending on the key and plaintext. Therefore, although the number of instructions executed during AES encryption remains constant, the encryption time varies.

The second kind of vulnerability can only be exploited by an attacker running unprivileged code on the same processor as the victim. If the victim and attacker processes share the same cache, then the cache-access pattern of the victim can influence the behavior of the attacker process, and vice-versa.

For instance, the attacker process could identify a memory address that might be used by the victim, depending on certain properties of sensitive data. They then identify an other memory address that maps to the same cache line as the memory of the victim process2 (Figure 1.3). When the victim process indeed accesses that specific address, it occurs a cache-miss and evicts the cache line owned by the attacker process (Figure 1.4). This has two effects: first, the attacker process will observe that loading the memory will now take longer, as the requested data is not in the cache anymore and has to be fetched from slower main memory (Figure 1.4). Second, the victim process incurs a cache miss that it would not have incurred without the attacker process. Therefore, the execution time of the victim might depend on which address is repetitively accessed by the attacker. If they are able to correlate this behavior with sensitive data manipulated by the victim, then they might be able to recover it.

Secret-dependent Branching

The second reason for leakages to occur are secret-depending branching operations. These are caused by programs executing certain instructions conditionally on some sensitive data. For instance, a loop can be executed a variable number of times, or the condition of an if-else branch could depend on that sensitive data. In some cases, this can cause the execution time of a program to vary depending on sensitive information, and such behavior

RAM

Cache

Victim Attacker has been exploited in numerous attacks, to construct decryption oracles for TLS [START_REF] Al Fardan | Lucky thirteen: Breaking the TLS and DTLS record protocols[END_REF][START_REF] Albrecht | Lucky microseconds: A timing attack on Amazon's s2n implementation of TLS[END_REF] or

SECURITY IMPLICATIONS OF THE CACHE

to attack various cryptographic primitives [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF][START_REF] Brumley | Remote timing attacks are practical[END_REF]. Cache-timing attacks are even more powerful, and can reveal information about sensitive data even when the two branches of an if-else branch execute the same functions [START_REF] Yarom | Recovering OpenSSL ECDSA nonces using the FLUSH+RELOAD cache side-channel attack[END_REF]. This is due to the fact that any instruction executed by a program is saved into the cache, so that when the instruction is executed again, it does not need to be loaded from main memory. However, this implies that the cache state depends on the instructions that have been executed. For instance, two branches can call the same functions, but the instructions preparing the function arguments and executing the function calls are considered different for caching purposes. Therefore, an attacker that can determine the cache state of the victim might be able to determine which branch was taken.

Exploiting Cache-Timing Leakages

In many cases, a successful cache-timing attack can allow the attacker to fully recover the victim key. How this is done, however, depends on the algorithm executed by the victim and the sensitive information leaked to the attacker.

Leakage of the key

On some implementations, the state of the cache directly depends on the key. This is for instance the case for unprotected RSA implementations. In RSA, the decryption step consists in a modular exponentiation with the secret key. The most straightforward implementation consist in implementing this operation via modular fast exponentiation, also called "square-and-multiply". Algorithm 1.2.1 RSA "square-and-multiply" Input: n: public key, d: private exponent, c: ciphertext Output:

c d mod n x ← 1 for i = log 2 (d) down to 0 do x ← x * x mod n if d & (1 i) = 0 then x ← c * x mod n end if end for return x
The total execution time depends on the secret exponent d, but it only depends on the number of bits set to 1. In contrast, a cache-timing attack with high enough resolution would be able to determine for each round of the loop whether the extra modular multiplication by c is executed or not. However, the timing variations were actually enough to retrieve the secret key in older reference implementations of RSA [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF].

Because of these vulnerabilities, "square-and-multiply" has not been used to implement RSA decryption in a long time, and other fast exponentiation algorithms such as Montgomery multiplication [START_REF] Montgomery | Modular multiplication without trial division[END_REF] are preferred. These resisted simple timing attacks but were ultimately broken using modern cache-timing attacks [START_REF] Acıiçmez | A vulnerability in RSA implementations due to instruction cache analysis and its demonstration on OpenSSL[END_REF][START_REF] Chen | Improvement of trace-driven I-cache timing attack on the RSA algorithm[END_REF].

CHAPTER 1. STATE OF THE ART IN CACHE-TIMING ATTACKS

Leakage of the nonce In some cryptographic implementations, protecting the random nonce generated during the signature is of paramount importance. This is mainly the case for ECDSA signatures [START_REF] Johnson | The elliptic curve digital signature algorithm (ECDSA)[END_REF] using non-deterministic nonces. Nonce misuse was used in order to break digital signatures on the Sony PlayStation 3 [START_REF]Console hacking 2010 -PS3 epic fail[END_REF] or to steal Bitcoins from insecure Android wallets [START_REF] Michaelis | Randomly failed! The state of randomness in current Java implementations[END_REF]. Similarly, recovering even partial or approximate information about the nonce allows to recover the secret key [START_REF] Yarom | Recovering OpenSSL ECDSA nonces using the FLUSH+RELOAD cache side-channel attack[END_REF][START_REF] Benger | Ooh aah... just a little bit": A small amount of side channel can go a long way[END_REF][START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF]. In [START_REF] Yarom | Recovering OpenSSL ECDSA nonces using the FLUSH+RELOAD cache side-channel attack[END_REF], a cache-timing attack is performed on an ECDSA implementation using Montgomery ladder for point multiplication. The pseudocode for this procedure is given in Algorithm 1.2.2. The algorithm works in a similar fashion as traditional fast multiplication, but does not exhibit timing variations as a point addition and a point doubling is executing for every bit of the input parameter k, regardless of the value of that bit. However, the code still branches on the value of the bits of k. When the instructions on the two branches map to distinct cache lines, as is the case in the OpenSSL implementation attacked by Yarom et al., then a cache-timing attack can reveal the value of k. Once most bits of the nonce are known, the private key can be recovered.

Algorithm 1.2.2 Elliptic curve point multiplication using Montgomery ladder

Input: k: nonce ∈ N, P: curve point Output: kP R 0 ← O Additive zero R 1 ← P for i = log 2 (k) down to 0 do if n & (1 i) = 0 then R 1 ← R 0 + R 1 R 0 ← 2R 0 else R 0 ← R 0 + R 1 R 1 ← 2R 1 end if end for return R 0
Leakage of the randomness More generally, the randomness used to perform cryptographic operations must be kept secret when it is not part of the output. When side-channel leaks reveal this private randomness, then the key might be recovered. Such a vulnerability was exploited in order to break implementations of the post-quantum signature scheme BLISS [START_REF] Ducas | Lattice signatures and bimodal Gaussians[END_REF] (as well as the variant BLISS-B [START_REF] Ducas | Accelerating BLISS: the geometry of ternary polynomials[END_REF]) using cache-timing attacks [START_REF] Bruinderink | Flush, Gauss, and reload -A cache attack on the BLISS lattice-based signature scheme[END_REF][START_REF] Pessl | To BLISS-B or not to be: Attacking strongSwan's implementation of post-quantum signatures[END_REF]. We will here quickly describe the attack against the strongSwan [START_REF]strongSwan VPN[END_REF] implementation of BLISS.

In BLISS, public and private keys are elements of the ring R 2q = Z 2q [x]/(x n + 1). Elements of this ring we will be denoted in bold for the remainder of this section. In particular, the public key is an element a ∈ R 2q while the secret key is a pair of sparse elements (s 1 , s 2 ) ∈ R 2 2q . Crucially, the signature contains an element of R 2q equal to

z 1 = y 1 + (-1) b s 1 • c mod 2q

SECURITY IMPLICATIONS OF THE CACHE

where y 1 is generated according to a n-dimensional discrete Gaussian distribution, b is chosen uniformly at random in {±1}, and c ∈ {0, 1} n ⊂ R 2q corresponds to a hash of the message and other values (and is also included in the signature). Now, because the elements of c are equal to 0 or 1, the ring multiplication s 1 • c actually correspond to a vector-matrix multiplication s 1 • C where C is a matrix with entries in {-1, 0, 1}. In particular, the i-th coordinate of s 1 • c is equal to the scalar product s, c i where c i is the i-th column of C.

The cache-timing attack now works as following. The generation of y 1 is done component-wise using a precomputed cumulative density table which contains the probabilities that an integer sampled from a discrete half-Gaussian is lower than k for values up to a fixed cutoff (the sign of the Gaussian is sampled separately). The strongSwan implementation of BLISS has the distinctive property that this table is not accessed when the sampled value is equal to 0, and this event can therefore easily be detected using a cache-timing attack. Now suppose that for a given i, we know thanks to the cache-timing attack that y 1,i = 0 and we also have that z 1,i = 0 by inspecting the signature. We then deduce that s 1 , c i = 0 mod 2q. Furthermore, due to the sparseness constraint in s 1 and the choice of q in the actual implementations, the absolute value of s 1 , c i is much smaller than q and therefore, this equality must hold in Z, not merely in Z 2q . Because c i can also be recovered from the signature, we have learned one vector of the nullspace of s 1 . Once enough such vectors have been collected, s 1 can be computed, either by solving a system of linear equations, or by applying the LLL algorithm [27] in order to cope with the measurement errors that might occur. Because s 2 can actually be recovered from s 1 , the key is then fully recovered.

Avoiding Cache-Timing Attacks

Several countermeasures have been proposed in order to thwart cache-timing attacks. Most of them target specific methods to read the cache state. For instance, disabling simultaneous multithreading (SMT) makes reading the L1 cache more difficult (see Section 1.3.1), and disabling memory sharing between processes can avoid attacks based on the clflush instruction (see Section 1.3.3). However, these countermeasures reduce the performance of the whole system, and do not prevent all attacks. Other suggestions include performing cache flushes after any process finishes, which would only work in conjunction with the aforementioned techniques and would further slow down the system, or degrade the performance of available timer functions, which has been tried and was circumvented [START_REF] Schwarz | Fantastic timers and where to find them: high-resolution microarchitectural attacks in JavaScript[END_REF].

Adding more randomness to the cryptographic operations is another possibility. One can either resort to masking, as is done to prevent physical side-channel attacks [START_REF] Eldib | Synthesis of masking countermeasures against side channel attacks[END_REF], or add random slowdowns in order to minimize timing differences. When using masking, one has to be careful to avoid higher-order attacks [START_REF] Joye | On second-order differential power analysis[END_REF] which could reveal the mask and render the countermeasure useless. Random slowdowns have to be implemented with care: the maximum slowdown and the granularity of the waiting periods need to be sufficiently high [START_REF] Albrecht | Lucky microseconds: A timing attack on Amazon's s2n implementation of TLS[END_REF]. Also, they mainly work against timing attacks, and it is not clear how they can prevent cache-timing attacks from succeeding.

An other direction consists in detecting cache-attacks rather than preventing them.

CHAPTER 1. STATE OF THE ART IN CACHE-TIMING ATTACKS

Most measurement methods induce a higher than usual number of cache misses, and these can be detected by using performance counters [START_REF] Alam | Performance counters to rescue: A machine learning based safeguard against micro-architectural side-channel-attacks[END_REF]. However, it is not clear what to do once a cache-timing attack is detected -if the system shuts down, then the false positive rate of such methods needs to be extremely low for them to be useful. Furthermore, new measurement methods that circumvent these detectors could be designed, rendering them useless.

Finally, the most promising solution is to implement cryptographic algorithms without secret-dependent branching and memory accesses. This solution provably protects from cache-timing leakages and can be implemented without any other hardware or software modifications. Verification tools that assess the absence of leakages can provide a muchneeded help for implementing constant-time algorithms. We designed and implemented such a tool. It is described in Chapter 2 and various results obtained thanks to the tool are provided in Chapter 3.

Measurement Methods

Cache-timing attacks exploit the dependency between the state of the cache and the value of sensitive data of a program, such as keys or security-relevant randomness. However, an attacker cannot directly access the state of the cache. In order to determine which memory addresses were accessed by the victim program, indirect methods have to be employed.

PRIME+PROBE

The first method that was described to perform cache-timing attacks is presumably PRIME+PROBE [START_REF] Osvik | Cache attacks and countermeasures: the case of AES[END_REF]. The first versions targeted the L1 cache, and therefore, the processes of the victim and the attacker need to run on the same physical core. This method is comprised of two phases:

• PRIME phase: the attacker accesses memory from its own memory space in order to completely fill the L1 cache with data under its control. They first need to determine how memory addresses are translated into cache sets (see Figure 1.2), and then accesses one memory address per cache set.

• PROBE phase: after the victim process has executed, the attacker records the access times for all the memory addresses accessed during the PRIME phase. If the access time is short, the data is still present in the cache. Therefore, the victim process has not accessed a memory address that maps to the same cache set. On the contrary, if the access time is slow, the data was evinced from the cache, and thus the victim process did access a memory address that maps to the same cache set. After all addresses have been accessed and the access time recorded, the attacker process waits for a while for the victim to execute before performing a new PROBE phase.

The order of operations is therefore: PRIME → wait → PROBE → wait → PROBE . . . Because the L1 data and instruction caches are separated on most Intel and AMD processors, an attacker targeting the L1 instruction cache must execute instructions at addresses that will map to all the addresses in the monitored cache sets, instead of just accessing the memory [START_REF] Acıiçmez | New results on instruction cache attacks[END_REF].

The main advantage of the PRIME+PROBE attack is that it does not need shared memory between the attacker and the victim process. Only the cache needs to be shared, which requires the two process to run on the same physical core. On the other hand, PRIME+PROBE is fairly slow compared with newer methods, and is also noisier. Indeed, the attacker cannot make the difference between two memory accesses (or instruction executions) of different virtual addresses that map to the same cache set. This method therefore does not achieve a granularity of one cache line. Also, background tasks unrelated to the victim process may also access the same cache sets as the victim, adding more noise to the measurements.

PRIME+PROBE on L3 cache

The PRIME+PROBE attack has also been extended to the L3 cache [START_REF] Liu | Last-level cache side-channel attacks are practical[END_REF][START_REF] Kayaalp | A high-resolution side-channel attack on last-level cache[END_REF][START_REF] Irazoqui | S$A: A shared cache attack that works across cores and defies VM sandboxing -and its application to AES[END_REF]. The main advantage is that this attack works across cores and even VMs [START_REF] Irazoqui | S$A: A shared cache attack that works across cores and defies VM sandboxing -and its application to AES[END_REF] with no simple mitigation. However, two complications arise when applying PRIME+PROBE to the L3 cache:

• The L3 cache is much larger than the L1, at a few MiB compared to about 32 KiB for the L1 caches. Therefore, priming and probing the whole L3 is much slower. This would reduce the time-resolution of this method by several orders of magnitude. Therefore, this attack requires a profiling phase, in which the attacker determines which cache sets are relevant for their attack.

• The L3 cache of modern Intel processors is partitioned into so-called slices. These slices span several cache sets, and the slice which will contain a given data will depend on its physical address. However, the function that maps physical addresses into slice indices is not public and depends on the processor family. However, this mapping can be reverse-engineered [START_REF] Irazoqui | Systematic reverse engineering of cache slice selection in Intel processors[END_REF][START_REF] Maurice | Reverse engineering Intel last-level cache complex addressing using performance counters[END_REF][START_REF] Kayaalp | A high-resolution side-channel attack on last-level cache[END_REF][START_REF] Andreou | Cache timing attacks on recent microarchitectures[END_REF], or the attack can be build in such a way to be independent of this mapping [START_REF] Liu | Last-level cache side-channel attacks are practical[END_REF].

PRIME+ABORT A variant of PRIME+PROBE is called PRIME+ABORT [START_REF] Disselkoen | Prime+Abort: A timerfree high-precision L3 cache attack using Intel TSX[END_REF].

It uses Intel's Transactional Synchronization Extension (TSX) to improve the timing resolution of the PRIME+PROBE side-channel, and targets either the L1 or the L3 cache. TSX allows a program to execute a series of instructions inside a transaction, such that either all instructions are executed, or none of them. Because any operation that writes to memory during a transaction might be reverted during an abort, the processor needs to buffer all write operations that occur during the transaction. These operations are actually buffered in the L1 data cache.

Therefore, an issue occurs if any cache line that is written during the transaction is evinced from the L1 cache. This causes the transaction to abort, and causes a callback to a user-defined function. The PRIME+ABORT measurement techniques exploits this design in order to improve on the PRIME+PROBE techniques. It works as follows for the L1 cache:

• PRIME: the attacker starts a transaction, and writes to addresses spanning a whole cache set of L1 memory. Then, they wait in a loop. This phase is similar to

CHAPTER 1. STATE OF THE ART IN CACHE-TIMING ATTACKS

the PRIME phase from PRIME+PROBE, except that it is done inside a TSX transaction, and the attacker writes to the memory addresses, instead of reading from them. Also, only one cache set will be monitored.

• ABORT: When the transaction aborts, the attacker knows that a cache line from the monitored cache set was evicted. The attacker records this event, and then executes the PRIME code again.

There are mainly two advantages for this method. The first one is that no profiling phase is necessary to determine thresholds for "slow" and "fast" memory accesses. Second, there is a performance improvement over PRIME+PROBE. Indeed, the overhead of the attack is lower, as there is no probing phase, and the callback on transaction abortion is very fast. As a consequence, PRIME+ABORT is less likely to miss memory accesses from the victim. Furthermore, according to their authors [START_REF] Disselkoen | Prime+Abort: A timerfree high-precision L3 cache attack using Intel TSX[END_REF], the number of false positives is also lower.

The L3 variant is similar, and shares the weaknesses with the PRIME+PROBE on the L3 cache. Notably, caches slices need to be determined before the attack can be launched. The other difference with the L1 variant is that a transactional abort happens also when data that was read during a transaction is evinced from the L3 cache, as opposed to only data that is written to the L1 cache. During the PROBE phase, the attacker therefore only needs to read data, in the same way as in the PRIME+PROBE technique.

EVICT+TIME

EVICT+TIME [START_REF] Osvik | Cache attacks and countermeasures: the case of AES[END_REF] infers the cache access pattern of a victim process by slowing it down selectively. The attack works as follows:

• Setup: the attacker executes the victim process, ensuring that the cache is filled with data used by that program.

• EVICT: using the same technique as PRIME+PROBE, the attacker pollutes a specific cache set, replacing data cached by the victim program with its own.

• TIME: the attacker runs the victim process again and measures the time it takes to complete. A fast execution time reveals that the evinced data would not have been accessed during the execution of the victim.

This attack works best on the L1 cache, because determining all addresses belonging to a given cache set is straightforward. While this attack is hard do detect and mitigate against, there are several shortcomings. Only the first access to the evinced data is slowed down (if it is accessed), so the attacker cannot distinguish between one or more accesses to the targeted cache set. Also, only one measurement is possible per execution of the victim process. More modern techniques, such as CacheBleed and MemJam (see Section 1.3.4) slow down the victim program proportionally to the number of memory accesses to the targeted addresses. Furthermore, they allow to target specific addresses even inside a cache line, instead of targeting all addresses belong to the cache set.

FLUSH+RELOAD

The FLUSH+RELOAD [START_REF] Yarom | FLUSH+RELOAD: A high resolution, low noise, L3 cache side-channel attack[END_REF] technique is a more modern measurement technique, that targets the L3 cache. The main advantage is that this method is able to monitor individual cache lines, as opposed to whole cache sets as in the different PRIME+PROBE variants. It is also faster, easier to implement, and subject to a low rate of false positives. Furthermore, several cache lines can be monitored at the same time. It works as follows:

• FLUSH: the attacker select a series of virtual addresses corresponding to data shared with the victim. This can be code shared with the victim, if they make use of dynamically-linked libraries, or read-only data if the OS uses page sharing. They then execute the clflush instruction on these addresses, causing them to be evinced from the L3 cache, and thus also from the L1 and L2 caches due to the inclusiveness of the L3 cache.

• RELOAD: After the victim process has executed for a while, the attacker accesses the addresses selected in the first phase. If the access is fast, then the victim has accessed data corresponding to the same address. Else, because the data had previously been evinced from all caches, the access is slow. Once all addresses have been accessed, the attacker executes the FLUSH phase again.

The order of operations is therefore as follows: FLUSH → wait → RELOAD → FLUSH → wait → RELOAD → FLUSH . . . Because this attack targets the L3 cache, it works in a cross-core setting: victim and attacker do not need to execute on the same physical core. The only weakness of this method is that victim and attacker need to share code. If page sharing is disabled by the OS, this can only happen when the victim uses dynamically-linked libraries.

FLUSH+FLUSH FLUSH+FLUSH [START_REF] Gruss | Flush+Flush: a fast and stealthy cache attack[END_REF] is a variant of the FLUSH+RELOAD attack. They mostly share the same weaknesses and advantages, with FLUSH+FLUSH having a slightly lower precision but also a lower latency. Furthermore, it causes far less cache misses than FLUSH+RELOAD, making an attack harder to detect.

In this attack, the RELOAD phase is replaced by a second, modified FLUSH phase:

• FLUSH 2 : After the victim process has executed for a while, the attacker times the clflush operation on the selected addresses. If the operation is fast, then nothing needed to be done: the data was not present in the cache, and the victim did not access it. If it was slower, then the data was present in the cache, because it was accessed by the victim process.

The order of operations is therefore as follows: FLUSH → wait → FLUSH 2 → wait → FLUSH 2 . . .

CacheBleed and MemJam

All previously listed measurement techniques have a resolution of either a cache line, or a cache set. CacheBleed [START_REF] Yarom | CacheBleed: a timing attack on OpenSSL constant-time RSA[END_REF] and MemJam [START_REF] Moghimi | Memjam: A false dependency attack against constant-time crypto implementations[END_REF] are two techniques that provide a resolution finer than a cache line -up to 4 bytes in the case of MemJam.

CHAPTER 1. STATE OF THE ART IN CACHE-TIMING ATTACKS

CacheBleed CacheBleed uses cache bank contention to slow down a victim program that accesses memory located at a specific offset of a cache line. In order to speed up cache access, older Intel architectures (up to Ivy Bridge) make use of so-called cache banks. Every cache line is divided into several cache banks, which can be accessed concurrently. Therefore, if one program accesses data at different offsets of a cache line, the data can be fetched from the cache simultaneously. However, concurrent accesses to the same cache bank causes one of the two accesses to stall, increasing the latency. The authors use this observation to break the RSA encryption routine from OpenSSL 1.0.2f, which accesses the same cache lines, but not cache banks, regardless of the secret key.

MemJam Newer Intel processors (Haswell architecture and newer) do not use cache banks anymore. However, the MemJam technique is able to achieve a similar functionality as CacheBleed using so-called false dependencies.

True dependencies arise on a write and a subsequent read on the same memory address. These two operations cannot be reordered, because the result of the read operation depends on that of the write operations. Therefore, there is a dependency between those operations -the read must be executed after the write -and those two operations cannot be executed simultaneously. Therefore, executing those two operations is slower than a write and a read to two different memory locations.

False dependencies can arise when two independent operations are wrongly considered as being dependent by the CPU. One such type of false dependencies is called 4K aliasing [5, §11.8], where a write and read to two distinct memory addresses that are a multiple 4096 bytes apart are falsely considered by the CPU as being dependent.

Because the translation between virtual and physical memory is done at the page level (see Section 1.1.1) which usually have a size of 4096 bytes, the 123 last bits of the physical and virtual memory addresses are identical. Therefore, addresses that differ in the last 12 bits cannot refer to the same physical address. However, if the last 12 bits are identical, aliasing is possible, and verifying whether the two virtual addresses refer to the same physical address requires to perform a virtual-to-physical-address translation first. Because of the additional delay introduced by the translation, the CPU considers that a read and a write operation to these addresses are dependent, and starts executing the first one instead of waiting for the result of the translation before deciding whether both can be executed simultaneously. The consequence is that a write and a read these two addresses, even if they do not represent the same data, are slower than operations to addresses that are not a multiple of 4096 apart.

MemJam exploits this additional latency by selectively slowing down a victim process, depending on the last bits of the addresses being accessed. It works by repetitively writing data to a given address, which slows down memory accesses to addresses being a multiple for the victim process. In order to be effective, the attacker and victim process must share the same physical core, and should thus execute on the two virtual cores of some physical hyper-threaded core.

The granularity of the attack is thus finer than a cache line, at 4 bytes instead of 64 bytes. Indeed, all memory accesses fetch a word-sized chunk of memory, totaling 4 bytes, thus memory accesses that are part of the same word-sized chunk cannot be distinguished. This method allows the authors to break various block ciphers from Intel's IPP cryptographic library [START_REF] Intel | Developer reference for Intel integrated performance primitives cryptography[END_REF], which accesses the same cache lines regardless of the encryption key. The attack compares the encryption times for a program using an unknown key with those of a program using a chosen key and plaintext, and retrieves the encryption key after 2 million recorded encryption durations.

BranchScope

In order to avoid the performance penalty caused by branch mispredictions, modern CPUs implement mechanisms to predict the branch to be taken based on previous executions of the branches. The rationale is that if one branch has been taken during the most recent executions, then that branch is very likely to be taken again during the next one. To implement this mechanism, for every branching instruction, the CPU records how often the branch was taken or not among the last few executions. Depending on this value, during the next execution, either the taken or the not-taken path will be speculatively taken, and upon success or failure, the counter will be updated. In practice, this counter is a 2-bit saturating counter, meaning that it can be in 4 different states: Strongly Non Taken (SN), Weakly Non Taken (WN), Weakly Taken (WT) and Strongly Taken (ST). When the branch is taken during some execution, the counter transitions from SN to WN, from WN to WT or from WT to ST. Conversely, if the branch is not taken, it transitions from ST to WT, from WT to WN or from WN to SN. Meanwhile, the branch predictor will always predict that during the next execution, the branch will be taken if the counter is in the ST state, and will not be taken if it is in the SN state. The decision for the two intermediary states depends on the architecture.

The counter is tied to the virtual address of the branching instruction. Therefore, two branches in two distinct processes may refer to the same counter if the code is loaded at the same virtual address. The BranchScope [START_REF] Evtyushkin | Branchscope: A new side-channel attack on directional branch predictor[END_REF] side-channel exploits this observation. It works as follows. First, the attacker saturates the counter by repetitively taking a branch loaded at the same virtual address than the target branch of the victim process. Then, it waits for the victim process to execute this branch once. Finally, the attacker executes the branch again, recording the execution time of these instructions. A slower execution time indicates a branch miss, which allows to infer the direction of the branch taken by the victim process.

Attack Improvement Methods

No measurement technique is able to perfectly capture all cache accesses. Cache line prefetching [5, §2.4.4.2] can cause false positives, long execution times of the attacker code can lead to false negatives, and system activity can cause either false positives or false negatives, depending on the measurement method. In order to improve their precision, several methods have been developed, targeting either the victim or the attacker process.

Performance Degradation Attacks

In addition to the methods enabling an attacker to determine the state of the processor cache, micro-architectural side-channel attacks generally make use of techniques known as performance degradation attacks. Determining the cache state takes at least several hundred cycles (FLUSH+FLUSH), but it might be much slower (PRIME+PROBE). If the victim process accesses the cache several times in a short time, some of these accesses might be missed by the attacker. The attacker can try to slow down the execution of the victim process, increasing the time between two cache accesses and reducing the number of missed ones. Two mechanisms to achieve such a slowdown have been proposed in order to mount micro-architectural side-channel attacks.

Attacking the scheduler One technique to slow down the victim process is to cause it to run for only a short time period before it is preempted by the OS [START_REF] Gullasch | Cache games -bringing access-based cache attacks on AES to practice[END_REF]. It specifically targets the Linux OS and the scheduler known as the Completely Fair Scheduler.

One crucial task performed by the OS is that of scheduling. In general, at a given point in time, more processes have been launched and need to run to completion than there are cores to execute them. In this situation, a given number of processes are running, ideally as many as there are CPU cores, while other are either blocked and are awaiting some external event (such as the release of some lock), or ready and could run if some processor core becomes available. The role of the scheduler is to decide when processes should execute on an available core, and when they should wait so that other processes can make progress towards completion.

To decide in which order the processes should be run, the CFS scheduler associates a virtual time τ to every process. When a process is executed, its virtual time increases. When the difference in virtual time between the running process and the process with the lowest virtual time attains a given threshold ∆τ max , the process is stopped and one of the processes with the lowest virtual time is scheduled instead. This ensures that unfairness, defined by the maximum difference in the amount of CPU time allocated to any two processes, is upper-bounded.

Blocked processes are special cases. Because they cannot be executed unless an external event happens, the difference in virtual time between the currently executing process, τ run , and any blocked process can exceed ∆τ max . However, as soon as a blocked process becomes ready to run, its virtual time is updated and set to τ run -∆τ max if its virtual time was lower than this value. Thus, a process that was blocked for a long time will be immediately scheduled to run when it is no longer blocked. This behavior can be abused if an attacker is able to schedule multiple threads to run on the same core as the victim process. Suppose that the attacker launches N 100 threads, numbered from 1 to N , which are all blocked for a long amount of time: each thread i + 1 waits on a signal that will eventually be send by the thread i, and the first thread busy-waits for a long period of time before launching the attack. While the attack is active, thread i:

• Measures the cache state as specified by the attack (for instance using FLUSH+RELOAD), and

• Sets a POSIX timer to send a signal to unblock thread i + 1 after a set number of cycles, and

• Returns into a blocked state.

The number of cycles for setting the timer is chosen in such a way that the victim process (ideally) executes a single memory access, before the next thread becomes unblocked. Because of its low virtual time, it then preempts the currently running victim thread. This ensures that the attacker will not miss any memory access.

While very powerful if correctly executed, this attack is rater complex to implement. First, it requires to precisely determine the time when the next thread is awoken. This time depends on the duration of the necessary context switch, which might be variable. Also, the attacker cannot ensure that the victim process will be scheduled next, as other processes might be simultaneously runnable on the same CPU. Finally, it is not entirely clear how CPUs with multiple cores should be handled.

Slowing down the execution

A second technique consists in making the victim's instructions take more time to execute. If the attacker and victim process share resources on the same processor core, then an intensive utilization of these resources by the attacker processes can slow down the execution of the victim process. Possible target resources could be the cache or the execution ports. Note that this observation can be used to design microarchitectural side-channel attacks: cache contention is used for the EVICT+TIME attack [START_REF] Osvik | Cache attacks and countermeasures: the case of AES[END_REF], while execution port contention forms the basis of the PORTSMASH attack [START_REF] Aldaya | Port contention for fun and profit[END_REF].

In order to improve the precision of microarchitectural side-channel attacks, cache contention has been shown to be fairly effective [START_REF] Allan | Amplifying side channels through performance degradation[END_REF]. This method consists in having a helper process repeatedly evincing cache line corresponding to code executed by the victim process. It works best if the victim spends time executing a small number of instructions in a loop with a large number of iterations. In this case, the helper process can evince the instructions making up the loop body on every iteration. This can slow down the execution time of that loop by a factor up to 40, which corresponds to the ratio between the latency of a memory access from main memory and that of an access from L1 cache [START_REF] Allan | Amplifying side channels through performance degradation[END_REF]. Because the victim process is slowed down, the attacker is less likely to miss memory accesses from the victim process.

The method is easier to implement (the helper process only consists in a loop of clflush instructions) and does not depend on the scheduler and OS used. It requires a preparation phase in order to determine which instructions from the victim process to flush, but these do not need to be adjusted during an attack. There are is mainly one major drawback: the factor by which the victim code is slowed down largely depends on the structure of this code. When no tight loop is present, the slow-down factor might be low and the precision of the attack might not be improved enough.

Methods Based on SGX

SGX is a technology created by Intel that allows programs to create secure enclaves. Code executed inside an enclave writes to encrypted memory zones, so that programs executed

CHAPTER 1. STATE OF THE ART IN CACHE-TIMING ATTACKS

outside the enclave, even the OS, cannot spy on programs executing inside the enclave. The adversarial model SGX consider thus also comprises processes running with higher privilege level, such as programs run as the system administrator or super-user. While SGX should prevent the OS from recovering sensitive information of programs running in a secure enclave, this protection can be breached in practice using cache-timing attacks. These attacks mainly use the measurement methods methods previously described, but their efficiency can be improved by using methods that are specific to victim code running on a SGX enclave.

CacheZoom [50]

The CacheZoom attack makes use of two techniques that improve the precision of the cache measurements. First, it uses a mechanism called "process isolation" to isolate a physical processor core from processes other than the victim and attacker process. This reduces the measurement noise caused by other processes accessing the cache while an attack is carried out. While this technique is not specific to SGX, it requires the attacker to run with administrator rights, which is possible in the threat model SGX targets. The second technique consists in setting a very short timer interrupt delay on the enclave running the victim process. This causes it to be interrupted often, ideally once between every two memory accesses, and allows the attack to measure the cache state without missing a victim memory access. Thus, this technique is somewhat similar to an attack on the scheduler, described in Section 1.4.1. CacheZoom is however easier to set up, while also requiring a more powerful attacker.

The main drawback of CacheZoom is that the victim process may detect the frequent interruptions, and thus abort its execution. Countermeasures based on this property have already been proposed [START_REF] Chen | Detecting privileged side-channel attacks in shielded execution with déjá vu[END_REF][START_REF] Shih | T-SGX: Eradicating controlledchannel attacks against enclave programs[END_REF].

Software Grand Exposure [53]

A second set of techniques, dubbed Software Grand Exposure [START_REF] Brasser | Software Grand Exposure: SGX cache attacks are practical[END_REF], exploits the additional attacker capabilities under the SGX threat model while minimizing the risk for the attacker to be detected. In addition to isolating the victim and attacker thread from other processes, as in [START_REF] Moghimi | Cachezoom: How SGX amplifies the power of cache attacks[END_REF], Software Grand Exposure proposes mainly two new techniques to improve the precision of cache measurements. First, it disables OS interrupts for both the attacker and victim processes, and increases the delay between timer interrupts. Thus, the victim and attacker processes are very likely to run uninterrupted while the attack takes place. The advantage is twofold: avoiding interruptions of the victim process reduces the noise caused by restarts of the enclave, and running uninterrupted reduces the number of missed cache accesses by the attacker process. The second method consists in using hardware counters, instead of timestamp counters, to detect whether a cache-hit or cache-miss took place. These allow the attacker to count the number of cache misses, which is more precise than using timing-based methods to determine if a cache miss took place. These counters, however, cannot be used by an unprivileged attacker.

Chapter 2 STAnalyzer: Static Analysis for Cache-Timing Vulnerability Detection in C Programs

But life is short and information endless: nobody has time to everything. In practice we are generally forced to choose between an unduly brief exposition and no exposition at all. Abbreviation is a necessary evil and the abbreviator's business is to make the best of a job which, although intrinsically bad, is still better than nothing. He must learn to simplify, but not to the point of falsification. He must learn to concentrate upon the essentials of a situation, but without ignoring too many of reality's qualifying side issues.

Aldous Huxley

Introduction

When implementing cryptographic algorithms in software, timing attacks represent a great risk to the security of the algorithm. For instance, the total execution time can depend on the key, which can be revealed by multiple measurements [START_REF] Brumley | Remote timing attacks are practical[END_REF]. More subtle attacks exploit the latency difference between the fast processor cache and the slower main memory (RAM). These attacks are collectively known as cache-timing side-channel attacks. They can determine, on a branching operation, which branch is being executed even if the branches are balanced and execute the same instructions [START_REF] Yarom | Recovering OpenSSL ECDSA nonces using the FLUSH+RELOAD cache side-channel attack[END_REF]. They can also reveal the address of memory accesses [START_REF] Bruinderink | Flush, Gauss, and reload -A cache attack on the BLISS lattice-based signature scheme[END_REF]. These attacks can be mitigated if some simple guidelines are followed: no memory access and no branching operation should depend on sensitive values. A code that follows these guidelines is said to be constant-time and immune to cache-timing attacks. In this chapter, we propose an algorithm that is able to determine 20 CHAPTER 2. STANALYZER whether a program written in the C programming language follows the constant-time guideline. This algorithm is implemented in our tool STAnalyzer.

Related Work

There are several ways to verify that a program follows the constant-time guidelines. It can be checked during program execution, this is called a dynamic analysis. One popular tool is ctgrind, an extension of the valgrind1 profiler tool. The program executable can be annotated, and the program can be executed in a virtualized environment, where memory accesses and branching operations are monitored. While this approach has the advantage of analyzing real program behavior, and thus minimizing false positives, it is in general not possible to explore all program paths. This might actually lead to false negatives, i.e. missed constant-time policy violations.

Another approach consists in analyzing the program code. One can either inspect directly the C source code [START_REF]TIS-CT[END_REF], the compiled assembler instructions [START_REF] Doychev | Cacheaudit: A tool for the static analysis of cache side channels[END_REF], or work with an intermediate representation of the program code [START_REF] Alpern | Detecting equality of variables in programs[END_REF][START_REF] Almeida | Verifying constant-time implementations[END_REF][START_REF] Blazy | Verifying constant-time implementations by abstract interpretation[END_REF]. Analyzing the assembler instructions has the advantage of taking into account compiler optimizations that might lead to either vulnerability removal or insertion, but has not been fully implemented for Intel x86 or x86-64 assembly, probably due to the complexity of the Intel assembly language [START_REF]Intel 64 and IA-32 architectures software developer's manual[END_REF]. A more common approach is to analyze intermediate representations, either in the LLVM intermediate language [START_REF] Lattner | LLVM: A compilation framework for lifelong program analysis & transformation[END_REF] or the Single Statement Assignment (SSA) form [START_REF] Alpern | Detecting equality of variables in programs[END_REF]. Both of these representations are emitted by the compiler after some optimization has been applied. Therefore, it accounts for some removals or insertions of timing leakages by the compiler, while being easier to analyze than a program written in low-level assembly. However, the link to the original source code is somewhat lost, and it is not necessarily easy from such an analysis to understand where the leaks originate from. Finally, working directly on the source code is also possible. However, the only existing tool [START_REF]TIS-CT[END_REF] does not allow to specify sensitive variables and requires a manual inspection of the leaking variables. We propose an alternative that allows for a fine-grained tracking of sensitive values. At the same time, we leverage the information in the C source code files to provide a meaningful explanation for any source of leakage.

Because the algorithm works directly on the source code, compiler transformations cannot be taken into account. While some leakages might be missed due to the compiler adding branches to the code, this does not seem to occur often in practice; more often, the compiler seems to actually remove some leakages. For example, the C code shown in Figure 2.1 uses a conditional branch, but the compiler replaces it with a conditional set instruction (setg), a constant-time operation. In the rest of this chapter, compiler-specific behavior is considered out-of-scope.

Background in Dependency Analysis

A program can be defined as a series of operations acting on the program state. For programs written in higher-level languages such as C, the state is defined by a set of variables. These variables can take different values, and the execution of a program consists in manipulating these values and assigning them to different variables. For the sake of our analysis, we will ignore other effects of program execution, notably I/O operations (screen printing, network and file operations, etc.).

Static analysis tools infer properties of the program execution from source code only, without actually executing it. Usually, the actual values manipulated by the program are not known. Instead, special abstract values are assigned to the variables, and the result of operations manipulating these values have to be defined. For instance, we can define two values, H and L, where H represents high security values, and L low security ones. The result from any binary operation • can then be defined as such: L • L = L and

H • L = L • H = H • H = H.
Information flow analysis consists in determining the values that might influence the variables in a program. For example, variables and values could be assigned security classes. This idea has been adapted by Rodrigues et al. [START_REF] Rodrigues | Sparse representation of implicit flows with applications to side-channel detection[END_REF] to create FlowTracker, a tool which performs information flow analysis in order to determine whether cache-timing leakages occur in a given program. Both these methods operate on the Static Single Assignment (SSA) format of a program. Rodrigues et al. consider two security classes, high and low, and their program determines whether any value of the high security class leaks due to branching instructions or memory access. As already noted by Denning and Denning [START_REF] Denning | Certification of programs for secure information flow[END_REF], in this model, function calls need to be treated with care. Indeed, they might create new dependencies between variables which should be accounted for. Also, since they might be called with arguments of high or low security class, it is not clear which leakages should be reported.

We propose a different idea: instead of tracking only two security classes, we define more abstract values: one for the initial value of any function arguments, for global variables and sensitive values. This makes it possible to track leakages and dependencies across multiple function calls, and allows to present more information about the flow of information inside a program.

The rest of the chapter is organized as follows.Section 2.2 provides the definitions and notations used in the remainder of this chapter. Section 2.3 provides a high-level description of the dependency analysis performed by our tool. Section 2.4 presents some of the results we obtained using it. Finally, Section 2.5 concludes.

CHAPTER 2. STANALYZER

Definitions and Notations

In this section, we will introduce the objects manipulated during the static leakage analysis. Table 2.1 explains the different notations styles used in the remainder of this paper. They serve to distinguish between actual C code, generic elements of the C language, and the objects abstracted from the C code which are used by the leakage analysis.

Concrete C code example expr

Abstract element of the C language var Symbolic object manipulated by the static analysis

Variables, Pointers and Values

In order to determine whether sensitive values might leak during the execution of a program, one needs to determine which variables of a C program might actually hold sensitive values. Performing a so-called dependency analysis solves this problem. This consists in determining, for any variable of a given program, what other variables might influence its value. In this section and the next, we will introduce the different notions that are required to describe how to perform this dependency analysis. It consists in defining a set of special symbolic values, and determining for any memory location, labeled by a variable, which values its content might depend on.

Definition 1 (Variable).

A variable is an identifier in a C program. It references a memory location. A variable will be denoted by its name, such as varname. In addition to all variables declared in the analyzed function, we also refer to the special \RET variable, which represents the return value of a function.

Definition 2 (Memory location).

A memory location is an independent region of memory that can store one or more values, as well as the addresses of other memory locations. A memory location will be denoted by the variable that references it, and we will use the same notation for both the variable and the memory location it refers to.

Definition 3 (Value).

A value is a specific symbol which will be tracked during the dependency analysis. The set of values depends on the function being analyzed. These values are:

• the special \SECRET value, which should not be leaked by the program execution and represents some sensitive value,

• all global variables, and

• the initial values of all function arguments (in order to compose the analysis of several functions). The initial value corresponding to the variable varname is denoted by varname 0 to distinguish it from the variable it originally refers to.

Listing 2.2: C code example

int foo(int a, int b) { int j = a; int i[2]; i[0] = b; i[1] = a; return i[0]+i[1]+j; }
As an example, consider the C code in Listing 2.2. The state of the memory locations, at the end of the function execution, can be represented as in Table 2.2.

Variable (memory location)

Values During our analysis, we consider that every variable declaration of any pointer simultaneously initializes a corresponding memory location of sufficient size. In a real program, this has to be done via a call to malloc or a similar function. Issues related to uninitialized memory are therefore out of scope of this analysis.

a a 0 b b 0 i a 0 , b 0 j a 0 \RET a 0 , b 0
Note that according to that definition, a pointer may point to more than one memory location. There are two reasons for this definition. The first is to accommodate arrays of pointers. Such a variable can contain pointers to several memory locations. Our analysis will not be able to determine which one will be accessed when the variable will be dereferenced, and we will have to assume that all of them will be accessed or modified.

The second reason is that, depending on the program execution, a pointer might point to one among several memory locations. Our static analysis must consider all of these possibilities. In order to simplify the analysis, we will again consider that all memory locations will be accessed or modified when the pointer is dereferenced.

An example of C code containing pointers is provided in Listing 2.3, and the state of all memory locations at the end of the function execution is given in Table

2.3. Listing 2.3: C code example with pointers int foo(int a, int b) { int j = a; int i[2]; i[0] = b; i[1] = a; int * * k = malloc(2 * sizeof(int * )); k[0] = i; k[1] = &j; return i[0]+i[1]+j; }
Note the fact that k is listed among the possible memory locations for the pointer &k is an artifact of our hypothesis that any pointer initializes sufficient memory -we suppose that &k points to some allocated memory location before any other operation is performed. This is not the case in this example, and there is no actual memory location bound to k.

Structures Structures are special types of C variables. A structure defines one or more fields, which will be bound to a single variable. We will consider the different fields as belonging to distinct memory locations. While it is possible to read or modify data of one field by accessing another field, through a buffer overflow for instance, the result of such an operation is arguably undefined behavior. Such techniques should not be used in cryptographic code.

Therefore, in order to handle structures, our analysis will simply consider different fields as corresponding to different variables, and track the dependencies of all the fields independently. One issue, however, arises with self-referential structures, i.e. structures that contain a pointer to a field of the same type as themselves. Such structures are

Variable (memory location)

Values Pointed memory locations

a a 0 - b b 0 - i a 0 , b 0 - &i - i j a 0 - &j - j k - - &k - i, j, k &&k - &k \RET a 0 , b 0 - Table 2

Dependency Graph

The dependency graph encodes the mapping between memory locations (variables), abstract values (see Definition 3) and referenced memory locations (see Definition 4).

Leakage Analysis

If the cache access pattern of a program changes depending on their input, then information about that input might be recovered by a spy process. Conversely, if the cache access pattern is constant, then no information might be retrieved by such methods. The cache access pattern depends on:

• the program control flow, because it changes the access pattern to the instruction cache, and

• the addresses of dereferenced pointers, because they change the access pattern to the data cache.

The cache access pattern need not be entirely constant for a program to be secure. Rather, it should not depend on sensitive values. For a signature algorithm for instance, the access pattern may depend on the data being signed, but not on the secret key that is used. Furthermore, some cryptographic algorithms rely on the output of an RNG, and an attacker able to recover enough information about that RNG might retrieve the secret key [START_REF] Bruinderink | Flush, Gauss, and reload -A cache attack on the BLISS lattice-based signature scheme[END_REF].

The objective of the leakage analysis is therefore to detect cache access patterns, which we will simply call leakages, that depend on sensitive values. However, because our analysis will be performed function by function, the leakage of other values need also to be tracked, namely the values of the function parameters, as well as global variables. These correspond exactly to the symbolic values tracked by the dependency analysis, as defined in Definition 3. Determining the leakages of these values is necessary in order to determine the leakages caused by function calls. Definition 9 (Leakages). The leakages of a function is the set of values that might change the control flow and the addresses of dereferenced pointers during the execution of the function. This includes the leakages caused by all the called functions.

Indirect Dependencies

Indirect dependencies are a particular type of implicit dependency [START_REF] Rodrigues | Sparse representation of implicit flows with applications to side-channel detection[END_REF]. Take for example the C code in Listing 2.4. The value returned by this function should depend on the value a 0 , but this cannot be inferred by considering only the assignments made to the variable b. Instead, one has to note that the control flow is controlled by the value of the variable a and can lead to an assignment to b. One way to resolve the indirect dependencies is to keep track of all the values that might influence the control flow leading to a given region of the control flow graph. Once that region has been analyzed, one should consider that all variables modified during the analysis of that region depend on the values that influence the control flow graph directly leading to that region. For the region 2, any variable modified during the execution of either BB2 or BB3 depends on the value of b at the beginning of BB4. Similarly, for region 1, any variable modified during the execution of either BB1, BB2, BB3 or BB4 depends on the value of a before the next basic block is executed.

Region #1 Region #2 BB1 if (b > 0) BB2 BB3 end-if BB4 end-if ... if (a > 0) ...
It is not immediately obvious why tracking indirect dependencies in order to perform leakage analysis is necessary. Indeed, keeping track of non-sensitive indirect dependencies is not useful, and when indirect dependencies are sensitive, the analyzed program cannot be constant-time. This would imply that the control flow depends on sensitive values, which contradicts the constant-time requirements. However, there are two reasons why it still might be be useful to consider indirect dependencies.

First, the aim of our program is to determine all constant-time violations. When indirect dependencies are not considered, then some variables might falsely be considered non-sensitive, and leakages caused by them are missed. Second, some branching operations are compiled into constant-time code by modern compilers, and thus do not necessarily result in a constant-time violation (see Figure 2.1). Our tool allows the user to flag branches as being safe, i.e. do not result in a constant-time violation. In this case, CHAPTER 2. STANALYZER indirect dependencies must be tracked in order to avoid underestimating dependencies and potentially missing leakages.

Description of the Algorithm

The program implementing the leakage analysis mainly follows the Visitor pattern [START_REF] Gamma | Design patterns: elements of reusable object-oriented software[END_REF]. It maintains a global state, comprised of the dependency graph and the set of currently leaking values, which is updated after evaluating every node of the AST representing the program to be analyzed. It also computes, for every node, which variables the expression represented by this node depends on.

To define the algorithm, it is thus sufficient to describe how the different tracked objects are updated when evaluating a given node, and how to determine which variables a given expression depends on. Notations that are introduced in this section are summarized below in Table 2 Variables that expr depends on when considering read operations expr W Variables that expr depends on when considering write operations

φ(G, L; inst) = (φ G (G, L; inst),φ L (G, L; inst))
Updated dependency graph (φ G (G, L; inst)) and leaking values (φ L (G, L; inst)) after the instruction inst has been analyzed.

The algorithm verifies that no sensitive values is used in a leaking operation. In a real-world setting, the cache architecture, size and eviction policy have to be taken into account in order to determine if a leakage is exploitable, as well as the implemented countermeasures. In contrast, our algorithm does not take these implementation-specific details into account. As a consequence, a program found to be constant-time will be secure regardless of the configuration of the cache (assuming no leakages were introduced by the compiler). On the other hand, not all leakages found by our tool might be exploitable on every cache configuration.

Abstract Syntax Tree (AST)

An AST is an abstract representation of the source code of a program. In such a graph, every node represents an element of the programming language, and the edges connect The corresponding (simplified) AST is represented in Figure 2.3. It can be noted that this is a direct translation of the source code -there is only "one" way to build an AST from a given source code, whereas there can be several ways to compile the source code into, for example, x86 machine code.

Dependency Graph Interpretation

The dependency graph encodes the dependencies between variables and values, and as such, can be queried to determine the set of memory addresses and values that a given variable depends on. However, for a variable varname, this set is not equal to G(varname). Indeed, suppose that the dependency graph can be represented as in Table 2.3 and that CHAPTER 2. STANALYZER the dependencies of k need to be determined. A wrong answer would be G(k), as this is the empty set. Instead, one should walk down the dependency graph, starting from the node &&k, to determine that in fact, the dependencies of k are equal to

G(i) ∪ G(j) ∪ G(j) ={a 0 , b 0 }.
The algorithm to determine the dependencies of a given variable is described in Algorithm 2.3.1. The result of this algorithm will be denoted by dep(G, varname). This notation is extended to a set of variables in the following way:

dep(G, S) = varname∈S dep(G,

Expression Evaluation

Given an expression of the C language, it is necessary for the analysis to determine which variables this expression refers to. A natural way to define them is explained in Table 2.5. The objective is twofold: for operations that read values from memory, the analysis needs to determine which memory locations are read from. Similarly, for operations that write to memory it needs to determine which memory locations are modified. For the same expression of the C language, these two sets are not necessarily identical.

Consider, for instance, a simple array access operation, arr[index], where arr is some array and index some integer. Our analysis has to consider that arr represents a single memory location and therefore, the values that this expression depends on are the same, regardless of the value of index. This does not mean, however, that the value of the expression does not depend of the value of index. For instance, arr could be a fixed array used to implement some permutation. Because its content is fixed, no value is recorded in the memory location corresponding to arr. However, the result of the operation does indeed depend on the values recorded at that of index.

On the other hand, if arr[index] is part of an assignment operation, such as arr[index] = y, then this operation should only update the values recorded at the memory location corresponding to arr, not that of index.

In order to distinguish between these two cases, we define the dereference operation on non-pointer variables as yielding a new variable with negative indirection level. They can be interpreted as the variables which values are used to compute an address inside a single memory location.

The negative indirection level will be indicated by a number of * symbols. Thus, a variable with indirection level -1 will be denoted by *varname, with -2 by **varname, etc.

Thus, for a given expression expr, expr might contain variables of negative indirection level. How they are interpreted depends on whether expr represents a memory location to write to, or to read from:

• If expr should be read from, then the result might depend on the values of the variables with negative indirection level. Therefore, in order to determine the read CHAPTER 2. STANALYZER set for expr, variables of negative indirection level have their indirection level set to 0. The resulting set is denoted by expr R .

• Conversely, when the memory location for a write operation should be computed, variables of negative indirection level should be removed. The resulting set is denoted by expr W .

Applying these rules to the previous example where the expression was arr[index], we get that arr[index] = {arr, *index}. Therefore, arr[index] R = {arr, index} and arr[index] W = {arr}.

Instruction Interpretation

The main algorithm visits each node of the AST and updates the dependency graph and set of leaking instructions according to the semantics defined in this section. Indirect dependencies are handled as explained in Section 2.2.4 and ignored in the description of the semantics for the sake of clarity. The pair comprised of the modified dependency graph and set of leakages, after analyzing the instruction inst, is denoted by φ(G, L; inst) where G and L are respectively the initial dependency graph and leakages. The dependency graph of this pair will be denoted by φ G (G, L; inst) and the set of leakages by φ L (G, L; inst).

Analyzing simple instructions

The modifications on the dependency graph G and leaking values L when analyzing simple instructions are summarized in Table 2. 6. φ G (resp φ L ) represents the function that computes the dependency graph (resp. the set of leaking values) given the previous state of G and L, and the instruction to analyze. Note that the set L is only comprised of values, not of memory addresses. As such, if E is a set comprised of both values and memory addresses, L ∪ E is understood as the union of L and the values of E.

Flagging sensitive variables

As noted in Table 2.6, sensitive variables are flagged using a special pragma directive. This directive creates a dependency between the targeted variable and a special value, \SECRET. For instance, the code from Figure 2.5 will result in the dependency graph represented in Table 2.8. The semantics for variable flagging are described in Table 2.7. Any leakage of the special \SECRET value is reported as a violation of the constant-time policy.

var = expr φ G var → dep(G, expr R ) G φ L L var op 2 = expr φ G G ∪ {var → dep(G, expr R )} φ L L inst 1 ; inst 2 φ G φ G (φ G (G, L; inst 1 ), L; inst 2 ) φ L φ L (φ G (G, L; inst 1 ), φ L (G, L; inst 1 ); inst 2 ) var[expr 1 ] = expr 2 φ G G ∪ { * (var + expr 1 ) W → dep(G, expr 2 R )} φ L L ∪ dep(G, expr 1 R ) ∪ dep(G, var) return expr φ G G ∪ {\RET → dep(G, expr R )} φ L L
a a 0 - j a 0 - i \SECRET - b b 0 - \RET a 0 , \SECRET -

Analyzing branching instructions

If-else branches When an if-else branch is encountered, the set of leaking values needs to be updated, and the two branches need to be analyzed. The latter part is however not trivial, as the static analysis program cannot determine which branch will be taken by the program flow during the execution. Instead, both branches need to be taken into account simultaneously. There are two natural methods to do so:

• Run the analysis sequentially on one branch and then on all the instructions following the branches. Then do the same with the second branch, and finally merge the analysis state.

• Run the analysis on one branch, then on the other, and merge the analysis state.

Then continue the analysis on the instructions following the branches.

The first method approximates more closely how a real program execution takes place. However, when applied on a code comprised of n adjacent if-else branches, 2 n code paths need to be considered. In the case of n adjacent if-else branches nested p levels deep, this number grows to (2 p ) n = 2 pn . Conversely, the second method might overestimate dependencies, because in a real program execution, only one of the two branches are executed, not both. While nested if-else branches are still expensive to analyze, n adjacent if-else branches can be analyzed in time 2n only.

It is not clear how the second method could induce false positives for detecting the leakage of sensitive values, and it is clearly computationally more efficient. That's why we choose the second option to be implemented in STAnalyzer. The corresponding semantics are provided in Table 2.9. Table 2.9: Dependency and leakage semantics for if-else branches

Instruction to analyze

Result

if (expr) { inst } φ G G ∪ φ G (G, L; inst) φ L L ∪ dep(G, expr R ) ∪ φ L (G, L; inst) if (expr) { inst 1 } else { inst 2 } φ G φ G (G, L; inst 1 ) ∪ φ G (G, L; inst 2 ) φ L L ∪ dep(G, expr R )∪ φ L (G, L; inst 1 ) ∪ φ L (G, L; inst 2 )
Switch-case statements Switch-case statements represent the second conditional branching statement available in C. Their analysis mostly resembles that of if-else branches, and we choose the same time-precision tradeoff. In detail, each case instruction block is analyzed separately, and the analysis state is then merged together before analyzing subsequent instructions.

However, switch-case statement bring additional complexity because of the fallthrough mechanism. If the control flow reaches the end of a case-block without encountering a breakstatement, then the next case-block is executed. This behavior needs to be accounted for, as ignoring it might lead to missed leakages -for instance, one case-block might set some variable to a sensitive value, and the next block leaks that variable. Furthermore, some case-blocks might always terminate with a break-statements, some might never execute them, and some other might terminate with a break-statements on some executions, and fallthrough on other. The last case is even more complicated, as a precise analysis would need to take into account that only a subset of the instructions of the case-block might be performed before the next block is executed. At the risk of introducing some false positives, we simplify the analysis of this third case and consider that all the instructions of a case-block are executed before a fallthrough is performed. The semantics of the switch-case statement however still depends on whether a break-statement will always, never or sometimes be encountered during the execution of a case-block.

Additionally, a switch-case statement may have a default label, which will define the instructions to execute if none of the case labels match. However, the default label is not mandatory. If it is omitted an no label matches the value of expr, then no case-block is executed.

In general, for a switch-case statement of the form

switch(expr) { case expr 1 : inst 1 • • • case expr i : inst i }
the semantics of that statement are defined by

φ G (G, L; inst) =    i φ i G (G, L) if a default label is present G ∪ i φ i G (G, L) if no default label is present φ L (G, L; inst) = L ∪ dep(G, expr R ) ∪ i φ i L (G, L)
where φ i G and φ i L are given in Table 2.10. Table 2.10: Dependency and leakage semantics for switch-case statements

Break encountered in inst i

Result

Always φ i G φ G (G, L; inst i ) φ i L dep(G, expr i R ) ∪ φ L (G, L; inst i ) Sometimes φ i G φ G (G, L; inst i )∪ φ i+1 G (φ G (G, L; inst i ), L) φ i L dep(G, expr i R ) ∪ φ L (G, L)∪ φ i+1 L (φ i G (G, L), L) Never φ i G φ i+1 G (φ G (G, L; inst i ), L) φ i L dep(G, expr i R ) ∪ φ L (G, L; inst i )∪ φ i+1 L (φ i G (G, L), L)

Analyzing loops

Analyzing requires computing a fixed point in the dependency and leakage analysis. Because our program does not perform any kind of value analysis, it cannot determine CHAPTER 2. STANALYZER how many times a loop will be executed. Therefore, the worst case situation, leading to the most dependencies and leakages, must be determined. Let's consider a while-loop of the type while (expr) { inst } and define the function ψ as

ψ(G, L; expr; inst) = (G ∪ φ G (G, L; inst), L ∪ φ L (G, L; inst) ∪ dep(G, expr R ))
The function ψ computes the updated dependencies and leakages after one execution of the loop. Let n ≥ 0, the dependencies and leakages after n loop executions are defined as

ψ n (G, L; expr; inst) = ψ(G , L ; expr; inst) where (G, L ) = ψ n-1 (G, L; expr; inst), ψ 0 (G, L; expr; inst) = (G, L).
Per its definition, the computed dependencies and leakages cannot decrease after applying ψ and are of course upper-bounded. This guarantees that ψ has a fixed point. Therefore, the resulting dependency graph and leakages after analyzing this instruction are equal to φ(G, L; while (expr) { inst }) = lim n→∞ ψ n (G, L; expr; inst).

Other Loops do-while loops are similar to while-loops, except that the instructions in the loop are executed at least once. Similarly, for-loops execute a provided init statement before first executing the loop instructions, and a step instruction after the loop body. Table 2.11 summarizes the dependency graph and leakage set pair after analyzing a given type of loop.

Function Calls

Function calls are more complex to handle. Indeed, a function call can modify any global variable and modify the values of the arguments it is called with (in case pointers are passed as arguments). The value returned by the function can also depend on global variables and any function arguments. Finally, any argument or global variable might be leaked. Because the values corresponding to function arguments and global variables are tracked, our algorithm is able to determine their behavior after finishing analyzing any function. When an already analyzed function is called, it is thus only necessary to perform a translation from the called function argument names to the callee expressions in order to determine the effect of the function call on G and L.

In the rest of this section, we consider an expression of the form f (expr 1 , expr 2 , . . . , expr n )

where f has been previously declared as

f (& l 1 arg 1 , & l 2 arg 2 , . . . , & ln arg n ).
Here, l i represents the indirection level of argument arg i .

Definition 10 (Variable translation). Let

I f = {(i, j) : i ∈ [|1; n|] ∧ j ∈ [|0; l i ]}.
For (i, j) ∈ I f , the translation function τ f is defined on memory addresses as

τ f (& j arg i ) = * l i -j expr i R
and on values as

τ f (arg 0 i ) = * l i expr i R .
The special \SECRET value and all global variables are translated as themselves.

The definition of τ f is naturally extended to a set of values and memory addresses related to the arguments of f as

τ f (S) = varname∈S τ f (varname).
φ L (G, L; f (. . .)) L ∪ dep(G, τ f (L f )) φ G (G, L; f (. . .)) (i,j>0)∈I f * j expr i W → dep(G, τ f (dep(G f , & l i -j arg i )) G f (. . .) τ f (dep(G f , \RET))
The semantics of function calls can then be defined with the help of τ f as in Table 2.12. In this table, f (. . .) is used as shorthand for f (expr 1 , expr 2 , . . . , expr n ). Furthermore, L f and G f represent respectively the the set of leaking values and the dependency graph computed after analyzing f . Variadic functions, that is, functions with a variable number of arguments, cannot be analyzed by our tool. However, we implemented a mechanism that allows the user to provide snippets of Python code to describe the behavior of variadic functions that might be encountered during analysis. Finally, function pointers can be handled, if it is clear from the analysis which function they point to. Since it is not easily possible to determine this for function pointers that are passed as function arguments, they are always considered as leaking all their arguments. This minimizes the risk of missing any source of leakage.

Output Presentation

The aim of our tool is to detect all possible sources of leakages and present them in a way that is easy to understand. To this purpose, two types of outputs are generated after each analysis. The first one is a textual file. For each detected leakage, it describes the function calls, dependencies between variables, and the instruction causing the leakage. The second is an overview of the function call graph leading to the leaking instructions.

In this example, the function mbedtls_blowfish_crypt_ecb was chosen as the entry point for our analysis. The variable ctx.P was flagged as sensitive, as it contains the Blowfish encryption key. The structure ctx is passed to the function blowfish_enc. The dependency analysis of that function determined that the variable Xl depends on the value of ctx.P. The function F is then called, with Xl corresponding to its x argument. Inside this function, b depends on the value of x, and this variable leaks on line 86. This corresponds to the first reported leak. The second one is very similar, but this time the leakage of the d, which also depends on the value of x, is reported.

Limitations

Our tool handles memory separation only between members of a structure, not between elements of an array. Consider for instance the code in Figure 2.8. The element at index 1 of the variable values is considered sensitive, however, only elements stored at indexes that are an even number leak on Line 8-11. Therefore, this code will not leak sensitive data, but because all elements of an array share the same dependencies during our analysis, a leakage will be reported by our tool, resulting in a false positive.

RESULTS

39

Results

Benchmarks

In order to compare the performance of our approach to existing tools, we ran an analysis of most algorithms mentioned in [START_REF] Almeida | Verifying constant-time implementations[END_REF]. The results are given in Table 2. [START_REF] Yarom | Recovering OpenSSL ECDSA nonces using the FLUSH+RELOAD cache side-channel attack[END_REF] Violations of the constant-time policy were found for the mbedtls implementations, and the constant-time property was verified for all other implementations. Because our tool lists all constant-time violations, it takes longer to analyze implementations that contain a lot of them. This is for instance the case for mbedtls_aes and mbedtls_des.

Applications on Other Cryptographic Algorithms

This tool was used in order to detect cache-timing vulnerabilities in the candidates for post-quantum cryptography standardization. A detailed description of this analysis is provided in Section 3.2 and Section 3.3 of the next chapter.

Conclusion

Folklore has it that you should never implement your own cryptographic algorithms. In addition to the traditional bugs that you could introduce into your software, there are several pitfalls one has to be aware of that are specific to cryptographic implementations, such as side-channel attacks. However, someone does need to implement these algorithms, and easy-to-use verification tools that can help to avoid those pitfalls can improve the confidence in your implementation. Thankfully, the rules for avoiding cache-timing leakages are relatively simple-never use sensitive data in a branch or for a memory access-and can be checked through static analysis. Of course, it is impossible to verify this property without introducing false positives. In designing our tool, we have tried to balance the tradeoff between computationally complexity, ease-of-use and false positives, while ensuring that no constant-time violation will be missed. The use cases on real-world code presented in the next chapter show that the tool is useful both to find constant-time violations and to verify their absence.

There a several directions for further improvements. First, additional sources of timing variations could be taken into account, such as divisions, rotations or multiplications taking a variable number of cycles to execute on some platforms [START_REF] Pornin | Why constant-time crypto?[END_REF]. Checking whether these arithmetic operations are performed with sensitive data can be easily done by our too, but this might lead to more reported leakages that are not necessarily exploitable.

In a similar fashion, there is currently no way to rank the severeness of the different constant-time violations that were detected. This could be useful to prioritize the correction of leakages, and could also help to filter out leakages that can be proven to be not exploitable. How to determine useful heuristics for the leakage severity remains an open research direction.

Chapter 3

Applications of the Static Analysis Techniques to Post-Quantum Cryptography and More

Bruce Schneier doesn't use a keylogger. He's standing right behind you. https://www.schneierfacts.com/ In this chapter, we present applications of our static analyzer tool. The goal is to show that it can be applied on real-world cryptographic code without producing too many false positives and without missing real leakages. Post-quantum algorithms provided an interesting target for this study. Several new algorithms or variants have been designed for the ongoing NIST post-quantum standardization process, and their implementations have not yet been vetted as much as the implementations of more traditional algorithms such as RSA or elliptic curve based cryptography. Furthermore, the implementations are mostly self-contained, facilitating the analysis compared to whole cryptographic libraries .

This chapter is organized as follows. First, in Section 3.1 ground truth is established by comparing the leakages reported by our tool on vulnerable programs to published sources of cache-timing leakages. Section 3.2 is a summary of the findings published in [START_REF] Facon | Detecting cachetiming vulnerabilities in post-quantum cryptography algorithms[END_REF] that analyzed the first-round candidates of the NIST post-quantum standardization process. Finally, a more detailed analysis of the second round candidates is provided in Section 3.3.

Collecting Ground Truth: Rediscovery of Known CVEs

In order to validate the approach of using static analysis techniques to discover cache-timing leakages, we ran the STAnalysis tool on known vulnerable code. The vulnerabilities were chosen from the Common Vulnerabilities and Exposures list https://cve.mitre.org/.

More precisely, we explored the entries containing the keywords "side-channel", ignoring the CVEs concerning non cache-timing side channels, implementations in languages other 44 CHAPTER 3. APPLICATIONS OF THE STATIC ANALYSIS TECHNIQUES than C, or vulnerabilities concerning codebases deemed too large for the validation (e.g. web browsers, the Linux kernel, etc.).

CVE-2019-9494 and CVE-2019-9495

These two vulnerabilities concern hostapd version 2.7, a program running on Wifi access points. The vulnerabilities are found in the code that derivates a secret key from the user-provided password. This code did not run in constant time, which could allow an attacker to speed up dictionary attacks against the access point's password.

For our analysis, we looked at the functions sae_derive_pwe_ecc, sae_derive_pwe_ ffc and compute_password_element. These functions implement the password derivation and are therefore natural entry points for our analysis. For the ground truth, we looked at the published patches1 and, by manual inspection, determined which branches and timing-dependent function calls were removed because they could cause timing differences.

True positives First, the patches replaced three calls to the GMP-function BN_mod_exp with calls to BN_mod_exp_consttime. Two such leaking calls were caught by our tool: those at lines 1298 and 1442 of the file crypto/crypto_openssl.c. The third one, at line 552 of the same file, was not found, because it was not called, either directly or indirectly, by the three functions we chose as entry points, and was therefore outside the code analyzed in this experiment.

Second, a call to the (potentially) variable-time os_memcp function is replaced by a call with the constant-time const_time_memcmp. This leaking function call was detected by our tool.

Third, a number of early returns in various functions were removed, in order to remove timing differences. These are found in crypto/crypto_openssl.c at lines 1446 and 1448, in eap_common/eap_pwd_common.c at lines 263 and 278, and finally in file common/sae.c at line 513 and 237. While performing these corrections, a boolean assignment was also changed in common/sae.c at line 260 to guarantee the absence of branching after compiling, as shown in Listing 3.1. All the early returns were detected by our tool, but not the boolean assignment. Such constructions could be reported, at the risk however of increasing the number of false positives. res = res == check ; // Changed t o // mask = const_time_eq ( r e s , check ) ; // r e s = c o n s t _ t i m e _ s e l e c t _ i n t ( mask , 1 , 0 ) ; Listing 3.1: Boolean Assignment in hostapd Finally, some loops that could run a variable number of times have been changes to a fixed number of iterations. These are found in common/sae.c at line 602 and 619, and were detected by our analysis tool.

False positives False positives were present in the analysis, and they can be classified into two main categories.

About half of the false positives are caused by the functions get_random_qr_qnr and get_rand_1_to_p_1. They implement randomness generation in a rejection sampling-like fashion. Although the code branches on randomly generated sensitive values, the sampled value is independent from the direction of the branches taken. Similar false positives are also caused by the function compute_password_element while sampling quadratic residues and non-residues.

The second half of the false positives is caused by checking for error conditions -such as failing to allocate memory, or very rare cases where generating random elements might fail. For example, a function that should return a boolean value depending on its (potentially sensitive) inputs, might also return -1 in order to signal a fatal error, which should happen very rarely in practice. Checking this error code would trigger a leakage warning from our tool, although no real leakage is present.

As a summary, about one third of the detected leakages are indeed security-relevant cache-timing leakages, one third are caused by rejection sampling, and one third by checks for error conditions. These false positives do fulfill the conditions of potentially vulnerable code, but are not exploitable. As such, they are an artifact of the general approach and not of the implementation of the static analysis. In order to avoid these kinds of false positives, one could resort to heuristics to filter them out, at the risk of missing real cache-timing leakages, or rely on annotations provided by the developers of the library.

CVE-2018-124049

This vulnerability affected Mozilla's NSS cryptographic library. Variable-timing code exposed the RSA decryption function to a Bleichenbacher-type attack [START_REF] Ronen | The 9 lives of Bleichenbacher's CAT: New cache attacks on TLS implementations[END_REF] that could be exploited using a cache-timing attack. Several other cryptographic libraries were affected by similar weaknesses, but in this section, we will only focus on the NSS library.

True positives Two functions contain vulnerable code that can be exploited to mount the attack. The first is mp_to_fixlen_octets which adds leading zeros to the representation of a large integer. This is not done in constant-time, and this function is applied to the decrypted plaintext. The second is RSA_DecryptBlock, which checks whether the decrypted plaintext has been padded correctly according to the PCKS #1 v1.5 standard. Different code is performed for conforming and non-conforming code, which allows an attacker access to different kind of oracles that can be used to decrypt RSA-encrypted ciphertexts.

The leakages in both functions were detected by our tool.

False negatives Numerous other potential leakages were reported by our tool -more than 5000 in total. Some are caused by leakages of randomly generated blinding values, which could potentially lead to multivariate attacks targeting the blinding and blinded values simultaneously. However, no such cache-timing attacks have yet been reported, and the feasibility of such an attack is unclear. Indeed, it is not possible to reduce the measurement noise related to the blinding values, as they change on each execution. Most of the other reported leakages concern functions of the big integer library used by NSS. For instance, the code often branches depending on the sign of the operands. This behavior may or may not lead to a cache-timing attack.

Finally, the error code returned by most functions is always checked. While this is good practice in general, it can also lead to numerous false positives. For example, a function could return a non-zero return code (indicating that an error has occurred) if the values supplied as arguments are outside a valid range. If this function is called with sensitive values that will always be in this valid range (by construction or because the range is verified beforehand), a potential leakage will be reported by our tool although none can happen in practice. However, one cannot simply ignore branching on all function error codes, as they could in other cases cause real leakages. More advanced tools can infer the range for the values of certain variables, such as [START_REF] Almeida | Verifying constant-time implementations[END_REF]. It has however not yet been demonstrated that this functionality is applicable to large integers handled by libraries such as NSS.

In this example, the vast majority of the potential leakages discovered by our tool were irrelevant to the reported vulnerability. While some of these leakages might be problematic, the vast majority seem to be false positives. Reducing their number would make our tool more useful for analyzing complex libraries. On the other hand, the false positives do not seem to stem from programming errors in our tool, but rather from the type of code found in NSS. As such, this library does not seem to be suitable for static analysis in general, at least not in order to verify the constant-time property of the code.

Analyzing First Round Post-Quantum Cryptography Candidates

The emergence of quantum computers in the medium term poses a particular threat to public key cryptography. Shor's algorithm [START_REF] Shor | Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[END_REF] promises an exponential speedup for operations such as integer factorization and discrete logarithm, once quantum computers with a sufficient number of quantum bits are available. This would undermine the security of most digital signature, public key encryption and key establishment algorithms deployed today. Private key primitives, such as symmetric encryption or hash functions, would also be affected by quantum computers, due to the Grover search algorithm [START_REF] Grover | A fast quantum mechanical algorithm for database search[END_REF]. However, the speedup provided by this quantum search algorithm is only quadratic and can therefore be offset by simpling doubling the key sizes.

It is thus crucial for public key algorithms resisting attacks by quantum computers to be designed, implemented, tested and ultimately standardized in the near future. These types of algorithms are collectively known as "post-quantum" algorithms, and aim at replacing RSA and elliptic curve-based primitives. They are thus based on other hard problems. The most promising candidates problems are:

1. LWE (Learning with Errors) [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF], which gives rise to the family of lattice-based proposals;

2. the decoding problem, used in the code-based family of proposals, initiated by the

McEliece cryptosystem [START_REF] Mceliece | A public-key cryptosystem based on algebraic coding theory[END_REF] and 3. multivariate polynomial systems solving [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[END_REF], which is the cornerstone of the multivariate cryptography family.

For signatures, systems inspired by the Merkle signature scheme [START_REF] Merkle | A certified digital signature[END_REF] are also proposed [START_REF] Buchmann | Merkle signatures with virtually unlimited signature capacity[END_REF] while other algorithms are based on more exotics constructions such as supersingular elliptic curve isogenies [START_REF] Jao | Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies[END_REF].

In 2016, the Nation Institute of Standards and Technology (NIST) started the standardization process for post-quantum cryptography algorithms. This process is expected to undergo three rounds, the first one which started in 2017 with the publication of the specifications of 69 algorithms, along with implementations for every algorithm. The main focus of the first round was to eliminate broken schemes, and the implementation security was not yet of paramount importance. Nevertheless, we analyzed most of the submitted candidates in order to determine which kind of side-channel leaks post-quantum algorithms might be subject to .

Analysis Methodology

The submissions to the NIST contest have mostly similar structures, owing to predefined templates for implementation. In particular, they all need to implement a main function which creates and verifies Known Answer Tests (KATs). This function thus performs either a signature and verification, or an encryption and decryption, with randomly generated key pairs. Executing this function therefore provides a relatively good code coverage. For the tagged variables, we simply choose to taint the randomness sources (which are also required to respect some specific format), as these sources are used to generate the secret keys as well as the randomness used during signature or encryption, which is probably sensitive in most cases. An issue is that the public key would also be considered sensitive. We mitigate this issue by automatically declaring safe any variable called pk. Of course, a more individual analysis would be necessary if one wants to guarantee the constant time property of a given implementation or, on the contrary, build a side-channel attack. However, this first analysis allows us to gain first insights about the existing and probable future difficulties of implementing constant time post-quantum schemes.

Result Overview

We present on Figure 3.1 the results for the 52 submissions we were able to perform static analysis on. Out of these 52 candidates, vulnerabilities were found in 42 of them (80.8%). 17 candidates have more than 100 vulnerabilities reported and 3 have more than 1000 vulnerabilities reported. Ten submissions (Frodo, Rainbow, Hila5, Saber, CRYSTALS-Kyber, LOTUS, NewHope, ntruprime, ThreeBears and Titanium) were found to be correctly protected. A few submissions were almost perfectly constant time, and replacing, for example, a small number of conditional branches with conditional move operations would render these implementations perfectly constant-time (EMBLEM, Lima, Giophantus, OKCN-AKCN in the MLWE variant). Also, false positives might have occurred, as it was not possible, given the number of submissions and reported vulnerabilities, to manually remove all false positives. The vast majority of the submissions, however, is not correctly protected against cache attacks, due to recurrent programming oversights in the portions of code handling sensitive data.

Analysis of Vulnerabilities

The detailed reports provided by the tool allowed us to classify the vulnerabilities into several categories, which seem to occur frequently among the submissions:

1. Gaussian sampling leaks: similar to the issues reported with BLISS [START_REF] Bruinderink | Flush, Gauss, and reload -A cache attack on the BLISS lattice-based signature scheme[END_REF], implementing a side-channel leakage free Gaussian sampler is not trivial to achieve. Some proposals, such as Frodo, manage to avoid this issue by slightly modifying the distribution being sampled and implementing this sampling in a constant-time fashion.

If the use of a discrete Gaussian sampler is required, constant time implementations [START_REF] Karmakar | Constanttime discrete gaussian sampling[END_REF] should be used.

2. Other sampling leaks: in general, when specific distributions need to be sampled, one has to take care to avoid conditional branches and array accesses that depend on the randomness source being used. There is no general solution to these type of leaks, as every submission implements samplers for potentially different kinds of distributions.

3. GMP library use: some submissions use GMP. This library does not seem to implement operations in constant time (at least, according to the C code implementing the version we used for analysis, which is the latest version, at the time of writing, of the mini-gmp variant), and thus functions defined by this library should not be used on sensitive data without further inspection of their assembly level implementation.

In any case, the portable mini-gmp implementation should probably not be used in implementations desiring to achieve the constant-time property.

4.

Operations in finite fields: several implementations need to handle operations in finite fields, notably multiplications. For small groups, this is often done via log/anti-log tables, which might open these implementations to cache-attacks. Other ways to implement these operations must be considered, such as bit-slicing [START_REF] Matsui | On the Power of Bitslice Implementation on Intel Core2 Processor[END_REF].

5.

Other: there were some potential leaks that we were not able to fit into one of the other categories. For instance, some submissions provide their own implementation of AES that use table accesses, or perform data-dependent branching for matrix operations such as Gaussian elimination. Custom implementations of AES will probably be replaced with calls to hardware-optimized instructions (such as AES-NI [START_REF] Gueron | Advanced encryption standard (AES) instructions set[END_REF]) on the platforms most commonly targeted by cache-timing attacks. As shown in Table 3.1, vulnerable code appears relatively often when implementing finite field operations and sampling specific distributions.

Code-based schemes are mainly affected by leakages due to finite field operations, as they need to perform multiplications in extensions of GF(2). Additions in these groups are less likely to cause side-channel leakages, as they can be implemented using constant time bit shifts and XOR-operations. However a naïve implementation might be vulnerable, as the conditional XOR, used during reduction, must also be executed in constant time, for example by using a conditional move (cmove) instruction.

On the other hand, vulnerabilities in randomness sampling are mainly encountered among lattice-based proposals. Perhaps surprisingly, vulnerabilities in Gaussian samplers are relatively rare. The publication of attacks against BLISS [START_REF] Bruinderink | Flush, Gauss, and reload -A cache attack on the BLISS lattice-based signature scheme[END_REF] might have forced some candidates to take special care in implementing the Gaussian sampler (DRS, qTesla, although the implementation is not entirely constant-time), while others avoided discrete Gaussian distributions altogether (CRYSTALS-Dilithium). However, other sampling routines were not sufficiently protected, for example Bernoulli sampling.

Analyzing Second Round Post-Quantum Cryptography Candidates

In January 2019, the NIST published a list of 17 candidates for public-key cryptography and key-establishment (which will be referred to as KEM algorithms) and 9 candidates for digital signatures that move to the second round of the post-quantum standardization process [START_REF] Of | Standards and Technology[END_REF]. Building on the insights gained during the analysis of first round candidates and improvements on our static analysis tool, we present here a more detailed analysis of 21 post-quantum cryptography algorithms. In this analysis, we strive to clearly present all potential causes of leakages found by our tool, as well as summarize the causes of false positives. This can help to design improved analysis tools that can avoid the false positives, and highlight where manual verification or code annotation is needed for verifying the constant-time property of the implementations.

Compared with the analysis of the first round candidates, we found less vulnerabilities. This is mainly due to two reasons: several submissions were updated with constant-time implementations, and the manual inspection removed reported false positives.

Unless stated otherwise, the analyzed implementations are those submitted to NIST at the beginning of the second round of the post-quantum standardization process. For some proposals, updated implementations that specifically address cache-timing leakages were made available (notably qTesla, Falcon and LAC), and those updated implementations were analyzed instead.

LUOV

LUOV (the Lifted Unbalanced Oil and Vinegar signature scheme) is a post-quantum, multivariate quadratic signature scheme. As such, both signature verification and generation need to perform additions and multiplications in different finite fields, of the form F 2 r -F 2 8 , F 2 16 , F 2 32 , F 2 64 and F 2 80 for the first version, F 2 7 , F 2 47 , F 2 61 and F 2 79 for an updated version that addresses weaknesses in the original parameters choices that were discovered during the standardization process [START_REF] Ding | New attacks on lifted unbalanced oil vinegar[END_REF].

Finite Field multiplication leakage

In the optimized as well as the reference implementations, finite field multiplications are not constant time. In the older version, multiplications in F 2 8 and F 2 16 are implemented via log and antilog tables, as shown in Listing 3.2. Multiplications in the larger groups are implemented using multiplications over F 2 16 , and are therefore also vulnerable.

In the newer version, multiplications in F 2 7 are also implemented using log and antilog tables, in a similar fashion as Listing 3.2. The larger groups implements carry-less multiplication, as shown in Listing 3.3, which uses table accesses and is potentially vulnerable to cache-timing attacks(see Line 11).

In addition to the reference and optimized implementations, an AVX2 optimized implementation is provided, but only for the variants of LUOV using the smallest group size: F 2 8 for the original version, and F 2 7 for the updated version. In this version, finite field multiplication is implemented using iterative multiplication with unconditional reduction. As shown in [START_REF] Danger | On the performance and security of multiplication in GF (2n)[END_REF], this routine could be sped up using Intel's clmul instructions and constant-time conditional reduction using cmov. In any case, finite field operations in the AVX2 implementation are constant-time. However, no constant-time implementation for the other parameter choices is provided.

Other Leaking Instructions After the solution to the multivariate quadratic system has been computed, the solution needs to be transformed, and this transformation is basically a multiplication by the secret linear map T. In the reference and optimized implementations, both in the original and updated version, the code performing this operation is shown in Listing 3.4. The code branches on the secret map T on Line 4, which might induce a timing vulnerability. The AVX2 optimized code performs the multiplication in a different way and is in fact constant time.

In a similar fashion, on the reference implementation, when building the augmented // Convert i n t o a s o l u t i o n f o r P( x ) = t a r g e t f o r ( i = 0

; i <= VINEGAR_VARS ; i++) { f o r ( j = 0 ; j < OIL_VARS ; j++) { i f ( getBit ( T [ i ] , j ) ) { solution [ i ] = subtract ( solution [ i ] , solution [ VINEGAR_VARS+1+j ] ) ; } } }
Listing 3.4: Multiplication by T matrix representing the multivariate system, another matrix multiplication is implemented in the same way and might potentially leak, as shown in Listing 3.5 (here, F2 depends on the secret map T). The optimized implementation does not contain this branching instruction. It uses strided matrix multiplication instead. However, this code in turn performs array accesses in order to perform the two following functions:

b = 8 i=0 b i • 2 i ∈ F 2 8 → 255 • 8 i=0 b i • 256 i b ∈ F 2 8 → 255 • 8 i=0 b • 256 i and is therefore not constant time. f o r ( i = 0 ; i <= VINEGAR_VARS ; i++) { f o r ( j = 0 ; j < OIL_VARS ; j++) { i f ( getBit ( F2 [ k ] [ i ] , j ) ) { A . array [ 1 6 * x+k ] [ j ] = add ( A . array [ 1 6 * x+k ] [ j ] , vinegar_variables [ i ] ) ; } } }
Listing 3.5: Multiplication by F2

Round5

Round5 is a post-quantum lattice-based KEM scheme. It has the particularity of using constant-time error correction, which prevents timing attacks that would be possible if variable-time decoders were used (e.g. BCH codes). Despite some warnings emitted by our analysis tool, the provided (optimized) implementation is actually constant-time. In the rest of this section, we will explain which warnings were emitted, as a way to explain how false positives can emerge.

Random permutation generation

The first warning concerns the generation of a random permutation. This is a countermeasure against backdoor attacks [81, §2.7.4].

ANALYZING 2 N D ROUND PQC CANDIDATES

53

However, because this random permutation is only applied to a public matrix in order to obtain an other public matrix, retrieving this permutation (or an equivalent one) is actually possible using public data only, and a side-channel attack would not help a potential attacker. This is therefore a false positive. For completeness, the code used to generate this permutation is provided in Listing 3.6.

f o r ( i = 0 ; i < params->k ; ++i ) { do { rnd = drbg_sampler16_2 ( params->tau2_len ) ; } w h i l e ( v [ rnd ] ) ; v [ rnd ] = 1 ; row_disp [ i ] = rnd ; }

Listing 3.6: Permutation generation

Ternary secret generation

The second warning also concerns a randomness generation routine: the generation of a sparse ternary random vector, in order to generate a random matrix. The code that generates that vector in the reference implementation is given in Listing 3.7. Note that the implementation uses rejection sampling (Line 4), which does not fit the exact definition of constant-time but does not, in fact, cause any issue. However, the creation of the ternary vector makes use of an array index at a sensitive location on Line 5, which constitutes the potential leakage.

f o r ( i = 0 ; i < h ; ++i ) { do { idx = drbg_sampler16 ( len ) ; } w h i l e ( vector [ idx ] != 0 ) ; vector [ idx ] = ( i & 1 ) ? -1 : 1 ; } Listing 3.7: Sparse ternary vector generation The optimized implementation, when choosing to use the appropriate constant-time matrix operations, is not concerned by this vulnerability, and is indeed constant-time.

qTesla

qTesla is a lattice-based post-quantum signature scheme. The signature generation requires to sample from a discrete Gaussian distribution, which is however claimed to be constanttime and thus not vulnerable to attacks such as those targeting BLISS [START_REF] Bruinderink | Flush, Gauss, and reload -A cache attack on the BLISS lattice-based signature scheme[END_REF][START_REF] Pessl | To BLISS-B or not to be: Attacking strongSwan's implementation of post-quantum signatures[END_REF] or older versions of Falcon [START_REF] Fouque | Falcon: Fast-fourier lattice-based compact signatures over NTRU[END_REF]. Both the reference and optimized implementations are claimed to be constant-time, and we will verify that this is the case in this section.

Uniform polynomial generation

In addition to the discrete Gaussian sampler, qTesla also implements a uniform sampler in function sample_y, in order to generate a polynomial CHAPTER 3. APPLICATIONS OF THE STATIC ANALYSIS TECHNIQUES of N independent coefficients, uniformly distributed in [-B, B]. The code that implements this sampler is given in Listing 3.8. This code performs branching on the potentially sensitive values y_t[0] to y_t [START_REF] Lipp | Meltdown: Reading kernel memory from user space[END_REF]. However, what is implemented here is actually rejection sampling, and thus the final coefficients of the polynomial y are independent of the branches taken during the execution of this code. Therefore, the uniform polynomial generation is constant-time. A very similar implementation is found in function poly_uniform, which is constant-time for the same reason.

// i n i t i a l i z a t i o n : i =0, buf c o n t a i n s random v a l u e s w h i l e ( i<PARAM_N ) { i f ( pos >= nblocks * nbytes * 4 ) { cSHAKE ( ( uint8_t * ) buf , SHAKE_RATE , dmsp++, seed , CRYPTO_RANDOMBYTES ) ; [START_REF] Kocher | Spectre attacks: Exploiting speculative execution[END_REF] pos += 4 * nbytes ; } Listing 3.8: Uniform polynomial generation Other rejection sampling The main signature code also uses rejection sampling, and branches on the return value of the functions test_correctness and test_rejection. This does not cause side-channel leakages. test_rejection is itself constant-time, while test_correctness leaks the position of the invalid coefficient -but per the comments, this does not reveal anything about their values.

pos = 0 ; } y_t [ 0 ] = ( * ( uint32_t * ) ( buf+pos ) ) & ((1<<( PARAM_B_BITS +1) ) -1) ; y_t [ 0 ] -= PARAM_B ; // . . . s i m i l a r f o r y_t [ 1 ] , y_t [ 2 ] , y_t [ 3 ] i f ( y_t [ 0 ] != (1<<PARAM_B_BITS ) ) y [ i++] = y_t [ 0 ] ; // . . . s i m i l a r f o r y_t [ 1 ] , y_t [ 2 ] , y_t
Leakage of public output Some functions leak data that depends on the secrets, but is revealed as part of the signature anyways. This is the case for encode_c, which leaks the public parameter c, as well as sparse_mul16, which leaks the positions and signs of the non-zero coefficients of c.

MQDSS

MQDSS (Multivariate Quadratic Digital Signature Scheme) is a post-quantum, multivariate quadratic signature scheme. It implements operations in F 2 31 in constant-time, for all implementation variants. The rest of the code can also be proven constant-time, with two small exceptions that require manual inspection: rejection sampling is used three times, and public data leaks once. This however does not prevent the analyzed reference and optimized implementations from being considered constant-time.

Rejection sampling Rejection sampling is used three times in order to generate random polynomials with coefficients in F 2 31 in functions gf31_nrand and gf31_nrand_schar.

The only difference is that gf31_nrand generates coefficients in [0; 30] while the coefficients generated by gf31_nrand_schar lie in [-15; 15]. The sampling code is provided in Listing 3.9. Finally, the main code in crypto_sign implements a similar rejection sampling which we do not reproduce here for brevity.

w h i l e ( i < len ) { shake256_squeezeblocks ( shakeblock , 1 , shakestate ) ; f o r ( j = 0 ; j < SHAKE256_RATE && i < len ; j++) { i f ( ( shakeblock [ j ] & 3 1 ) != 3 1 ) { out [ i ] = ( shakeblock [ j ] & 3

Leakage of public data

As the last step of the signature generation, as per [83, Fig. 7.2], the output of a hash function H 2 is used to determine which commitments c j i to write out as part of the signature. The selection code is provided in Listing 3.10 and leaks the output of that hash function, stored in the variable h1. 7.2]) depends on the secret key sk, it only depends on the hash of sk, which is not necessary sensitive. Furthermore, after inspecting the signature generation algorithm, it becomes clear that ch 2 can be computed from public output σ = (R, σ 0 , σ 1 , σ 2 ), as well as the message M and the public key pk, as

ch 2 = H 2 (H(pk||R||M ), σ 0 , H 1 (H(pk||R||M ), σ 0 ), σ 1 )
Therefore, the leakage of h1 constitutes a leakage of public data, which is in fact not sensitive. Thus, the provided MQDSS implementations are constant-time.

LEDAcrypt

LEDAcrypt is a post-quantum code-based KEM scheme. More specifically, it is based on LDPC (low density parity-check) codes in order to obtain compact key sizes. Our analysis applies to both the reference and optimized implementation provided by the LEDAcrypt implementors. Since we performed the analysis, a new version of the implementation has been made available in March 2020. The updated implementation has not yet been taken into account.

CHAPTER 3. APPLICATIONS OF THE STATIC ANALYSIS TECHNIQUES

Variable-time decoder

The proposed error-decoding algorithm are not constant time. This is the case for both the previously proposed Q-decoder [84, §1.5, Alg. 12] as well as the standard bit-flipping decoder referenced by the latest version of the documentation [85, §1.1.1, Alg. 1]. This can be already inferred from the description of the algorithms in the documentation. For [84, §1.5, Alg. 12], on Line 16, qrow[k] depends on the private matrix Qtr, on Line 17, similarity depends on qrow[k] and finally on Line 18, the algorithm branches on the value of similarity, which we just showed depends on sensitive values. This leak is also confirmed in the code.

For [85, §1.1.1, Alg. 1], Line 11 branches on the sensitive value syndrome, and Line 15 on unsatParityChecks[i], which depends on the sensitive value syndrome. Because the code has not been updated to the new specifications yet at the time of the writing, we could not verify that this leakage is also present in the code.

Variable-time finite field operations

LEDAcrypt implements various operations on elements in finite fields, notably for elements in extensions of finite fields with a sparse representation in the base field. Several of these operations are in fact variable time.

left_bit_shift_n and left_bit_DIGIT_shift_n are two primitives used for modular multiplication (function gf2x_mod_mul_dense_to_sparse). They shift the representation of an extension field element by n places, implementing the multiplication by X n . However, both leak the value n: left_bit_shift_n takes a shortcut for n = 0 (but otherwise performs the shift in constant time), while left_bit_DIGIT_shift_n simply iterates a number of times dependent on n. gf2x_mod performs the modulo operation in finite field. A security-relevant part of this function is provided as Listing 3.11. The leaks occurs on Line 4, where the bitrepresentation of the array aux is leaked. This array contains a copy of the input array representing the finite field element for which the modulo operation is to be performed. The function gf2x_mod also contains a second, similar block of code, that leaks the values of aux for analogous reasons. Therefore, gf2x_mod leaks its input parameter.

f o r ( i = 0 ; i < nin-NUM_DIGITS_GF2X_MODULUS ; i += 1 ) { f o r ( j = DIGIT_SIZE_b -1; j >= 0 ; j--) { mask = ( ( DIGIT ) 0x1 ) << j ; i f ( aux [ i ] & mask ) { aux [ i ] ^= mask ; posTrailingBit = ( DIGIT_SIZE_b-1-j ) + i * DIGIT_SIZE_b + P ; maskOffset = DIGIT_SIZE_b -1-(posTrailingBit%DIGIT_SIZE_b ) ; mask = ( DIGIT ) 0x1 << maskOffset ; aux [ posTrailingBit / DIGIT_SIZE_b ] ^= mask ; } } }

Listing 3.11: Finite field modulo (excerpt)

A and B in F 2 P for some P , given as the list of the positions of non-zero coefficients of their representative polynomial. Let us denote these positions with as {i A 1 , i A 2 , . . . i A n A } and an equivalent notation for B. The multiplication algorithm works as follows:

1. Compute all the sums i A j + i B k mod P , 2. Sort these values, and 3. Reduce this list by:

• Deleting the values that appear an even number of times • Keeping exactly one of the values that appear an odd number of times For any implementation, the first step is likely to leak n A and n B . The sorting algorithm should be implemented in constant-time in order to avoid leaking the result, and the last step is non-trivial to implement in constant time. The LEDAcrypt implementation performs neither step in constant-time. The code for the first step is given in Listing 3.12 and contains branches on the values of A and B. The sorting algorithm is a non constant-time quicksort. Finally, the third step is not protected, as shown by the code in Listing 3.13.

f o r ( i n t i = 0 ; i < sizeA ; i++){ f o r ( i n t j = 0 ; j < sizeB ; j++){ uint32_t prod = ( ( uint32_t ) A [ i ] ) + ( ( uint32_t ) B [ j ]
) ; prod = ( ( prod >= P ) ? prod -P : prod ) ; i f ( (

A [ i ] != INVALID_POS_VALUE ) && ( B [ j ] != INVALID_POS_VALUE ) ) { Res [ lastFilledPos ] = prod ; } e l s e { Res [ lastFilledPos ] = INVALID_POS_VALUE ; } lastFilledPos++; } }
Listing 3.12: Finite field multiplication (step 1)

w h i l e ( read_idx < sizeR && Res [ read_idx ] != INVALID_POS_VALUE ) { lastReadPos = Res [ read_idx ++]; duplicateCount =1; w h i l e ( ( Res [ read_idx ] == lastReadPos ) && ( Res [ read_idx ] != ← INVALID_POS_VALUE ) ) { read_idx++; duplicateCount++; } i f ( duplicateCount % 2 ) { Res [ write_idx++] = lastReadPos ; } }
Listing 3.13: Finite field modulo (step 3) gf2x_mod_add_sparse implements sparse addition in F 2 P . The function takes as input the list of indices of two elements in F 2 P , and output the list of indices of their sum.

As expected, this function involves quite a lot of comparing the input indices and is not constant-time. This function could be rewritten by using techniques derives from constant-time sorting algorithms.

Lastly, a less severe leakage appears in gf2x_transpose_in_place_sparse where A[0] might leak, and rand_circulant_sparse_block implements a kind of rejection sampling for generating random elements and matrices, which triggers a warning from our tool, but no leakage actually happens.

AES re-implementation LEDAcrypt ships with an AES implementation, used in the randomness generation code. It uses a T-table implementation which is not protected from cache-timing leaks. However, a real installation of LEDAcrypt would very likely use a system-specific and probably protected AES implementation, provided by OpenSSL or similar libraries.

Picnic

Picnic is a post-quantum signature scheme based on zero-knowledge proofs-of-knowledge (ZK-PoK), made non-interactive using standard transforms (Fiat-Shamir or the Unruh transform). The particular ZK-PoK exploited in picnic consists in simulating a multi-party computation (MPC) protocol T times, and selectively revealing some of the transcripts of the MPC as part of the signature. Two variants, picnic and picnic2 are proposed, the latter exploiting a more efficient ZK-PoK protocol. The principal advantage of this construction is that the security of the scheme only relies on standard symmetric primitives (cryptographic hash-functions and block ciphers). Thus, it is fairly unlikely that devastating attacks breaking novel assumptions will be discovered any time soon. As such, is can be seen as an alternative to stateless hash-based signature schemes, with which is shares the advantages (confidence in the security) and drawbacks (fairly long signature times and sizes compared with lattice-based solutions).

Two variants, picnic1 and picnic2, are implemented in the code submitted to NIST. Our analysis applies to both versions and shows that they are constant-time.

Leakage of the commitment hashes

The analysis revealed that the commitments to the MPC traces can leak during various operations. They are stored inside a Merkle tree, and search operations on the Merkle tree may leak the values of the commitments that are searched for. However, because the commitments are either part of the signature, or can be reconstructed from it, they should be considered as public output. Once the commitments are flagged as public output, almost all leakages disappear. For the picnic1 variant, the values of the challenges e t also leak during the proof-assembling phase (see [86, § 6.2; Step 5], the implementations branch on the values of e t ). However, since e = (e t ) t is actually part of the signature, this is obviously a leakage of public output.

For the picnic2 variant, the only remaining leakages are concerning verifications against corrupted public keys or fault injection attacks resulting in a failed MPC simulation (see [86, § 8.4]). However, this behavior can be directly observed by interacting with the program performing the signature, and no side-channel is required in order to determine 3.3. ANALYZING 2 N D ROUND PQC CANDIDATES 59 whether a failure took place. The only remaining risk would be a simultaneous fault and cache-timing attack: a fault attack could corrupt the secret key or other sensitive variables, and the side-channel attack could reveal the faulted commitments. However, even in this case, it is not clear how an attacker could exploit the knowledge of the commitments in order to gain knowledge about sensitive values. In any case, fault attacks are out-of-scope in this analysis, so the provided implementations are in fact constant-time.

Rejection sampling-like hashing The picnic1 variant uses a ternary hash function H3 that generates a sequence of elements in {0, 1, 2}. As shown in [86, § 6.4.5], the ternary hash function is build from a binary hash function by iterating over pairs of bits. The pair (1, 1) is discarded, while the other pairs are converted into ternary elements. This implies a branching operation on the pair of bits, which is potentially sensitive, as confirmed by the code implementing this conversion in the reference implementation given in Listing 3.14 (the code for the optimized implementation is different but also branches on the value of the bit pairs). However, this branch is actually benign: as in rejection sampling, the values returned by H3 cannot be inferred from the direction of the branching operations. Furthermore, the output of H3 is public, so this could also be considered as a leakage of public output.

NTSKEM

NTSKEM is a code-based post-quantum key-encapsulation scheme build on Goppa codes. It proved to be a challenge to analyze for three reasons:

• It makes heavy use of function pointers. While the initial version of our analysis tool had very limited capabilities for handling function pointers, these were expanded in an effort to try to handle the NTSKEM submissions. However, this ultimately proved unsuccessful, in part because the NTSKEM code makes use of function pointers to functions using themselves function pointers. This could be handled but requires a greater rewriting effort. Thankfully, only a handful of such functions are used by NTSKEM, exclusively for finite-field operations. These functions were manually inspected and easily found to be constant-time. They could then be excluded from the analysis.

• The implementations try to hide or abstract some implementation details via void *typed fields of structures related to the private key. These fields will themselves

CHAPTER 3. APPLICATIONS OF THE STATIC ANALYSIS TECHNIQUES

hold an other structure, also related to the private key. Some of these secondary fields, hidden behind the void * -field, are sensitive. However, because the information about the structure fields is lost, our analysis tool must consider all fields as being sensitive, which yields more false positives.

• The code makes use of generic data structures. More specifically, it makes use of a stack implementation which is used for the Fast Fourier Transform (FFT).

Polynomials are saved into that stack, and the coefficients of some of them are to be considered sensitive. However, the structure representing the coefficients also hold non-sensitive data, such as their degree. Again, after passing by the void * interface of the stack implementation, all fields of the polynomial structure are considered sensitive, which yields an unusually high amount of false positives.

A manual inspection found that most warnings emitted by our tool stem from false positives due to the reasons mentioned above. However, in addition to some leakages during key generation (which may be considered an issue or not), one potential leakage could be confirmed.

Permutation leakage

As part of the key-generation process, a permutation p is generated, which is part of the private key. The generation of the permutation itself is done via Fisher-Yates shuffle [START_REF] Fisher | Statistical tables: For biological, agricultural and medical research[END_REF] and is not constant-time. More importantly, the permutation is used during the error-recovery step of the decapsulation to index the e_prime_ptr array, as shown in the code of Listing 3.15 at Line 7, 12, and 18. This leakage is present in both the reference and the optimized implementations of NTSKEM.

LAC

LAC (LAttice-based Cryptosystems) is a ring-LWE based post-quantum public-key encryption and key-encapsulation scheme. The implementations submitted for the second round NIST post-quantum contest made use of a variable-time BCH decoding algorithm and was subsequently updated. Here, we therefore analyze the updated "LAC-v3a" variant which, as we will see, is still non constant-time.

Finite field operations

Multiplication in finite fields is implemented with table lookups, similar to other non-constant-time implementations. For instance, the code for finite field multiplication is given in Listing 3.16. This implementation avoids branching in order to check if both a and b are zero and uses a ternary check as well as masking. While it cannot be guaranteed that the compiled code does not contain any branching, we could verify their absence by inspecting the compiled code. However, this property needs to be checked again when using another compiler or compilation target. In any case, the problem of a secret-dependent table access remains (see Line 4). Similar leakages are also present in the functions gf_sqr and a_log. Finite-field polynomial multiplication is also affected by secret-dependent memory accesses. The secret corresponds to a sparse vector of +1 and -1 coefficients. In the sparse representation, only the positions of those non-zero coefficients are stored. The core multiplication code is given in Listing 3.17, where s_one (resp. s_minusone) represent the positions of the coefficients equal to +1 (resp. -1). The address of both v1_p and v2_p depends on these sensitive positions, and the array accesses at Line 5 resp. Line 6 thus constitute secret dependent memory accesses.

f o r ( i=0;i<NUM_ONE ; i++) { v1_p=v+DIM_N-s_one [ i ] ; v2_p=v+DIM_N-s_minusone [ i ] ; f o r ( j=0;j<vec_num ; j++) { sum1 [ j ] += v1_p [ j ] ; sum2 [ j ] -= v2_p [ j ] ; } }
Listing 3.17: LAC finite field polynomial multiplication BCH decoder array accesses and branching While the BCH decoder has been improved for LAC-v3a, the provided code is still potentially vulnerable against cachetiming attacks. The issues causing the vulnerabilities include:

• Use of primitives for finite fields that use table accesses (see above);

• "Solving" timing issues by duplicating code (see Listing 3.18), which does not protect from e.g. BranchScope [START_REF] Evtyushkin | Branchscope: A new side-channel attack on directional branch predictor[END_REF]. This is even more problematic as the compiled code for the second branch is, for some reason, located far away from the rest of the function code, making this section particularly vulnerable to cache-timing attacks in both the reference and optimized implementation;

• Use of the ternary operator for masking, for the same reasons as exposed above. Decapsulation failure check The verification whether the received ciphertext is correctly decapsulated is not done in constant time (see Listing 3.19). This probably leads to an attack against this implementation [START_REF] Guo | A key-recovery timing attack on postquantum primitives using the fujisaki-okamoto transformation and its application on frodokem[END_REF].

SIKE

SIKE (Supersingular Isogeny Key Encapsulation) is a post-quantum KEM scheme that relies on the hardness assumption of finding isogenies between supersingular elliptic curves. This is the only NIST-PQC candidate based on this novel assumption. Its main advantage are short public keys and ciphertexts. This was one of the more complicated submissions to analyze, for two reasons:

• SIKE relies on GMP [START_REF] Granlund | GMP: GNU multi precision library[END_REF], a library for handling large integers. More specifically, it relies on a subset implemented in a single 3400 lines-of-code file, mini-gmp.c, which has to be analyzed by our tool. This somewhat increases the duration of the analysis.

• The SIKE reference implementation makes liberal use of function pointers which are passed around in structures representing the algorithm parameters. Thus, the analysis tool had to be improved in to better handle function pointers, but the support of this functionality is still experimental.

While the analysis is probably not as accurate as for the other candidates, we could nevertheless make out two sources of potential leakages. These are only present in the reference implementation; the optimized implementation is, at the best of our knowledge, constant-time.

Point multiplication Point multiplication is implemented via the double-and-add method and provided in the function mont_double_and_add. The core of this function is presented in Listing 3.20. This code branches on the value of k, which represents the secret key.

f o r ( i = msb -1 ; i >= 0 ; i--) { xDBL ( curve , &kP , &kP ) ; i f ( fp_IsBitSet ( p , k , i ) ) { xADD ( curve , &kP , P , &kP ) ; } }

Listing 3.20: Point multiplication via double-and-add

Use of GMP Because GMP is a generic multiprecision arithmetic library, it supports operations with numbers, and specifically integers, of various sizes. Thus, the duration of most operations depends on the size (in bytes or words) of the numbers being handled, and their size depends on the value. Therefore, most GMP operations on sensitive inputs are reported as leaking by our tool. However, whether this leakage actually weakens the security of the implementation is not clear and would require further investigation on what information can actually be learned from cache-timing attacks targeting GMP.

Other Analyzed Candidates

FrodoKEM FrodoKEM requires an AES implementation. Three variants can be used: OpenSSL, AES-NI, or a provided standalone implementation. This last one is not constanttime; it is a straightforward implementation that leaks during S-BOX access. However, in practice, one of the other two options would be used, and they would be constant-time. The rest of the code is constant time, with one exception: checking for decapsulation failure is not done in constant-time, leading to an exploitable timing variation [START_REF] Guo | A key-recovery timing attack on postquantum primitives using the fujisaki-okamoto transformation and its application on frodokem[END_REF]. The code has since been patched.

ThreeBears

The provided implementation was verified to be constant time.

rainbow The small number of false positives reported by our tool were causes by difficulties handling union constructs. The provided implementation was nevertheless verified to be constant time.

McEliece Ignoring the code present only for debugging purposes, the provided implementation was verified to be constant time.

SaberKEM

The provided implementation was verified to be constant time.

Summary

Most round 2 candidates could be shown to be constant-time. Only LAC, LEDAcrypt and NTS-KEM do not have constant-time implementations. For LUOV, not all parameter sets have constant-time implementations, and these use the AVX2 instruction set. Therefore, on platforms with no AVX2 support, no constant-time implementation is currently available. Finally, the reference implementation of Round5 and SIKE are not constant-time, but the provided optimized implementations are in fact constant-time. A summary of those findings is provided in Table 3.2 for the KEM algorithms, and Table 3.3 for the signature schemes.

Perspectives

The NIST post-quantum standardization process will undergo a third round before the winners will be announced. New implementations will be provided, and analyzing the new implementations will be necessary in order to verify the absence of cache-timing leaks. Additionally, key generation could also be investigated. Depending on the usage that is made of the cryptographic algorithms, new keys might be frequently generated, and the cryptographic systems might be broken if an attacker gains knowledge about the keys. To our knowledge, no cache-timing attacks on key generation have yet been published. This could also be due to the fact that an attacker would have access to only one trace per key generation, making attacks much harder. However, even partial information about the key could lower the security provided by the schemes.

CHAPTER 3. APPLICATIONS OF THE STATIC ANALYSIS TECHNIQUES

Chapter 4 On the Stochastic Model of Physically Unclonable Functions

Scientists have calculated that the chances of something so patently absurd actually existing are millions to one. But magicians have calculated that million-to-one chances crop up nine times out of ten.

Terry Pratchett.

An Introduction to Physically Unclonable Functions (PUFs)

PUFs are electronic circuits whose behavior is unpredictable from one instantiation to another. However, ideally, the behavior of a given manufactured PUF device is deterministic and constant in time. These devices can be used as building blocks for hardware enabled security protocols [START_REF] Suh | Physical unclonable functions for device authentication and secret key generation[END_REF], requiring little computing power, and thus suitable for embedded devices. However, the security and reliability properties are not yet well understood, undermining the usability of protocols based on such hardware primitives. In the remainder of this thesis, we will motivate the use of a stochastic model to predict and improve the reliability and security of PUFs, with applications to the Loop-PUF [START_REF] Cherif | An easy-to-design PUF based on a single oscillator: The loop PUF[END_REF] and other PUFs sharing the same stochastic model (RO-sum PUF [START_REF] Yu | Recombination of physical unclonable functions[END_REF], Arbiter PUF [START_REF] Gassend | Delay-based circuit authentication and applications[END_REF], Ring-oscillator PUF [START_REF] Hajimiri | Jitter and phase noise in ring oscillators[END_REF]).

"Weak" and "Strong" PUFs

There are two black-box ways to model a PUF. The first way consist in considering a PUF as a device without input that produces an identifier when powered up. This is called a weak PUF. This identifier can then be used, for instance, to generate a cryptographic key, or be used to detect counterfeit devices.

CHAPTER 4. ON THE STOCHASTIC MODEL OF PUFS

The second way consists in considering a PUF as a device that takes an input, called challenge, and in response to that challenge produces an output bit. Such a PUF is called a strong PUF, and can be used, for instance, in challenge-response authentication protocols.

Of course, one can always consider a weak PUF that produces an identifier of n bits as a strong PUF with n possible challenges, and a strong PUF can become a weak PUF if the set of admissible challenges is fixed and part of the PUF specification. However, in general, a PUF is considered "weak" if the number of possible output bits is linear or sub-linear in the PUF "size", and "strong" if it is larger (for instance, exponential in the PUF "size"). As an example of how to design a PUF, let's consider a chain of an odd number of inverters (NOT gates), where the output of the last gate is taken as the input of the first gate. This is called a ring oscillator. After an impulse is applied as the input of the first inverter, the voltage at any given point in the circuit will oscillate. The exact oscillation frequency will depend on the physical characteristics of the inverters, and thus slightly vary from one chain to another. For a given circuit, however, this frequency should be relatively stable among several measurements. The frequency measurement can then be converted into response bits. One could, for instance, take the most significant digit of the measurement. However, it is not guaranteed that this number is uniformly distributed, and it might be subject to measurement noise and intrinsic jitter [START_REF] Hajimiri | Jitter and phase noise in ring oscillators[END_REF]. Another solution is to take two oscillators and compare their frequencies, yielding one output bit. This forms the basis of the so-called Ring Oscillator PUF.

Toy Example: The Ring Oscillator

Description of the Analyzed PUF Designs

In the next chapters, we will analyze the stochastic model applicable to several PUF designs exploiting the difference of delays in electronic circuits ("delay PUFs") Ring Oscillator PUF The Ring Oscillator PUF [START_REF] Suh | Physical unclonable functions for device authentication and secret key generation[END_REF] (RO PUF) consists of N ring oscillators with the same, odd number of inverters. It is considered a weak PUF, and there are mainly two ways to extract an identifier from a RO PUF: either comparing the frequencies of all ring oscillators, or comparing only the frequencies of N/2 ring oscillator pairs. In the first case, the output of the PUF consists in a permutation of N elements, and assuming the oscillator frequencies follow an i.i.d. law, produces log 2 (N !) N log(N )

AN INTRODUCTION TO PHYSICALLY UNCLONABLE FUNCTIONS (PUFS)71

bits of entropy. However, encoding the permutation into log 2 (N !) independent bits is not trivial. In the second case, the output are directly N/2 independent bits. The circuit description is summarized in Arbiter PUF The arbiter PUF [START_REF] Suh | Physical unclonable functions for device authentication and secret key generation[END_REF] consists of two series of delay paths, with n mux elements on each path, as depicted in Figure 4.3. Depending on the challenge bits c 1 , c 2 , . . . , c n , the signals either cross from one path to another if c i = -1, or stay at the same path if c i = 1. One bit of output is produced by determining whether the signal injected into the circuit arrives first on the last mux of the upper path or of the lower path.

Since there are 2 n different possible challenges, the arbiter PUF is considered a strong PUF. Compared to the RO PUF, it is however more complicated to implement, as all sections of the delay path between consecutive mux elements need to be perfectly balanced, as well as the cross links between the upper and lower path.

Arbiter PUF output: Let's denote by d i 1 (resp. d i -1 ) the delay incurred by the signal traversing the i-th upper (resp. lower) delay element. The arbiter PUF output for a given challenge c

= (c 1 , c 2 , . . . , c n ) is then equal to b(c) = sign n i=1 d i c i •c i+1 •...•cn - n i=1 d i -c i •c i+1 •...•cn = sign   n i=1   n j=i c j   (d i 1 -d i -1 )   .
Note that this slightly simplified model does not consider differences in delays caused by the connections between delay elements and muxes. However, as in [START_REF] Delvaux | Side channel modeling attacks on 65nm arbiter PUFs exploiting CMOS device noise[END_REF], these extra delay differences can be taken into account into a model that is also linear in n j=i c j i .

Faster ? The frequency measured for one oscillator of a pair is subtracted from the frequency of the other oscillator in the pair, multiplied by +1 or -1 depending on a challenge bit, and summed with the other frequency differences, as described in Figure 4.4. The output bit is then the sign of this sum. This design transforms 2n weak RO PUFs into one strong PUF. The output is linear in the delays, as in the arbiter PUF. Using ring oscillators allows to improve the reliability by improving the frequency measurement of the oscillator's frequency, whereas the arbiter PUF measurement cannot be improved. However, the RO-sum PUF design requires 2n ring oscillators, n subtractors and multipliers, as well as

(c 1 , c 2 , . . . , c n ) ∈ {±1} n d 1 1 +1 -1 d 1 -1 d 2 1 d 2 -1 d n 1 d n -1 -1 +1 -1 +1 +1 -1 +1 -1 -1 +1 c 1 c 2 c n Figure 4.3: Arbiter PUF - ×c 1 ×c 2 ×c n Σ (c 1 , c 2 , . . . , c n ) ∈ {±1} n - - d 1 1 d 1 -1 d 2 1 d 2 -1 d n 1 d n -1

STOCHASTIC MODELS FOR PUFS

73

a summation element, and is thus more costly to build than an arbiter PUF. RO-sum PUF output: Let's denote by d i 1 and d i -1 the delay of the two ring oscillators of the i-th pair. The RO-sum PUF output for a given challenge c

= (c 1 , c 2 , . . . , c n ) is then equal to b(c) = sign n i=1 c i • (d i 1 -d i -1
) .

Loop-PUF

The loop-PUF [START_REF] Cherif | An easy-to-design PUF based on a single oscillator: The loop PUF[END_REF], described in Figure 4.5, is a combination between the arbiter PUF and the RO-sum PUF. It consists of n pairs of delay elements, separated by n mux elements. Depending on the value of the i-th challenge bit, each mux will choose to output the signal delivered by one or the other delay element of the previous pair. This design is easier to implement than an arbiter PUF, since once a balanced pair of delay elements has been designed, they are fairly easy to replicate. Similarly to the RO-sum PUF, it is possible to amplify the differences in delay of the different delay elements by measuring several oscillation cycles, improving the reliability.

+1 -1 d 1 1 (c 1 , . . . , c n ) ∈ {±1} n ∼ c 1 c 2 c n d 1 -1 d 2 1 d 2 -1 d n 1 d n -1 +1 -1 +1 -1

Figure 4.5: Loop PUF

There are several ways in which one can obtain an output bit from a loop-PUF. We will use the method described in [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF] which consists in measuring the the delay for a codeword c = (c 1 , c 2 , . . . , c n ) ∈ {±1} n and its complimentary -c, and then taking the sign of the difference in delays.

Loop PUF output: Let's denote by

d i 1 (resp. d i -1
) the delay incurred by the signal traversing the i-th upper (resp. lower) delay element. The loop-PUF output for a given challenge

c = (c 1 , c 2 , . . . , c n ) is then equal to b(c) = sign n i=1 c i • (d i 1 -d i -1
) .

Stochastic Models for PUFs

Delay Distribution

For the stochastic model of these PUFs, we will suppose, as in [START_REF] Lim | Extracting secret keys from integrated circuits[END_REF], that all delays d j i follow a i.i.d. Gaussian distribution. This assumption is justified by the statistical analysis of the PUF circuit delays [START_REF] Cherif | An easy-to-design PUF based on a single oscillator: The loop PUF[END_REF][START_REF] Chang | Statistical timing analysis considering spatial correlations using a single PERT-like traversal[END_REF].

Chapter 5

On the Reliability of Physically Unclonable Functions

Insanity is doing the same thing over and over again and expecting different results.

Unknown.

This chapter is based on the two articles "An improved analysis of reliability and entropy for delay PUFs", published in 21st Euromicro Conference on Digital System Design (DSD) (2018) [START_REF] Schaub | An improved analysis of reliability and entropy for delay PUFs[END_REF], and "Two-Metric Helper Data for Highly Robust and Secure Delay PUFs", published in IEEE 8th International Workshop on Advances in Sensors and Interfaces (IWASI) (2019) [START_REF] Danger | Two-metric helper data for highly robust and secure delay PUFs[END_REF], with coauthors Sylvain Guilley, Olivier Rioul and Jean-Luc Danger.

An Improved Analysis of Reliability and Entropy for Delay PUFs

Designing a PUF involves a three-way tradeoff between entropy, reliability and complexity (e.g., circuit size). Firstly, entropy is increased by adding more elements such as RAM cells or oscillators, at the expense of an increased circuit size. Also, reliability is enhanced by error-correcting codes (ECC), but their redundancy generally decreases the entropy. For a given PUF design, it is not obvious how to precisely characterize the tradeoff between these three parameters (entropy, reliability and circuit complexity). For instance, fuzzy extraction [START_REF] Dodis | Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data[END_REF] using error-correcting codes is implemented in the PUFKY [START_REF] Maes | Pufky: A fully functional puf-based cryptographic key generator[END_REF] based on the ROPUF [START_REF] Bossuet | A puf based on a transient effect ring oscillator and insensitive to locking phenomenon[END_REF]. However, for this design, and fuzzy extraction in general, it is very hard to determine the bit error rate (BER) theoretically. Therefore, the actual parameter selection for the fuzzy extractor is not straightforward. Bit-filtering [START_REF] Škoric | Robust key extraction from physical uncloneable functions[END_REF] can also improve the reliability but since the number of output bits is reduced as a result of the filtering, this technique also decreases the entropy of the PUF. Thus, this technique, similar to fuzzy extraction, is subject to a tradeoff between reliability and entropy. The aim of this chapter is to build a framework to analyze this tradeoff for delay PUFs. Maes [START_REF] Maes | An accurate probabilistic reliability model for silicon PUFs[END_REF] proposed such a framework for the reliability of SRAM PUFs which was ad hoc 76 CHAPTER 5. ON THE RELIABILITY OF PUFS for a given PUF architecture and where the parameters' identification was performed on experimental data. Bhargava et al. [START_REF] Bhargava | An efficient reliable PUF-based cryptographic key generator in 65nm CMOS[END_REF] also perform filtering to improve the reliability of their PUF design, but provide no theoretical model to predict the reliability that might be obtained. In contrast, we aim at deriving a generic model using elementary assumptions, where the three-way tradeoff is not fully determined by real measurements, but given instead by closed-form expressions involving the signal-to-noise ratio (SNR). In this way, additional estimations of the SNR yield new predictions for the tradeoff.

Our framework is applied to three popular delay PUFs: the RO-PUF [START_REF] Suh | Physical unclonable functions for device authentication and secret key generation[END_REF], the RO sum PUF [START_REF] Yu | Recombination of physical unclonable functions[END_REF] and the Loop PUF [START_REF] Cherif | An easy-to-design PUF based on a single oscillator: The loop PUF[END_REF]. Two methods are chosen to improve the reliability: bit-filtering in a manner similar to the η-out-of-λ scheme of Škoric et al. [START_REF] Škoric | Robust key extraction from physical uncloneable functions[END_REF], and a novel "two-metrics" method. Our contributions are as follows:

• a generic tradeoff analysis framework for delay PUFs;

• closed-form expressions for the BER and entropy for these PUFs, with and without bit-filtering;

• an alternative method to improve reliability, based on two distinct metrics, as well as reliability estimations for this method;

• an analysis of the RO-PUF, the RO sum PUF and the Loop PUF, using this framework;

• real measurements of the delay PUFs on ASIC confirming our theoretical results.

The remainder of this chapter is organized as follows. Section 5.2 presents a theoretical model for the delay PUFs. Closed-form expressions for reliability and entropy under bitfiltering are derived in Section 5.3. The "two-metric" method is presented in Section 5.4. The analysis framework is applied to various delay PUFs in Section 5.5. Section 5.6 provides an experimental validation on silicon. Section 5.8 concludes.

Delay PUF Model

In this section, we provide a black-box analysis for a generic delay PUF. Throughout this chapter we use the following notations.

c m i i-th challenge bit C m m-th challenge C m = (c m i ) i d j C,t
total delay for challenge C (at measure t, for circuit j)

δ j C,t δ j C,t = d j C,t -d j ¬C,t δ j C δ j C = 1 T T t=1 δ j C,t ∆ C random variable modeling δ C Z additive Gaussian measurement noise
For simplification, sub-and superscripts (such as m, t, or j) may be dropped when this does not introduce any confusion.

We model an ideal (noiseless) delay PUF as a deterministic algorithm P I that takes a challenge C as input, and outputs a delay difference δ C :

P I : C → δ C .
This delay is then, in general, discretized in order to extract one (or more) bit(s). Thus, the final output is some function of the measured delay difference. For the sake of simplicity, we consider the sign function as the bit-output of the PUF:

b = sign(δ C ).
The delay difference δ C for a given challenge stems from a multitude of small delay variations caused by technology dispersion, and is thus seen as a realization of a random variable ∆ C . Similarly to Lim et al. [START_REF] Lim | Extracting secret keys from integrated circuits[END_REF], we model this random PUF variable as Gaussian ∆ C ∼ N (0, Σ 2 ) for some positive deviation Σ > 0.

Such a delay PUF model is ideal since in practice, measurement noise is always present. Following e.g., [START_REF] Lim | Extracting secret keys from integrated circuits[END_REF] we model this noise as additive and independent Gaussian. Our PUF model becomes a probabilistic algorithm:

P : C → δ C + Z b = sign(δ C + Z) (5.1)
where Z ∼ N (0, σ 2 ) for some σ > 0. Since P(C) is the sum of a "signal" ∆ C and noise Z, the signal-to-noise ratio (SNR) can be defined

SNR = E[∆ 2 C ] E[Z 2 ] = Σ 2 σ 2 . (5.2)
and the bit error rate is defined as

BER(δ C ) = P(sign(δ C + Z) = sign(δ C )). (5.3)
To simplify the reliability analysis, we make the additional assumption that all PUF responses δ C are mutually independent. In general this will only be satisfied approximately. As shown below for each specific PUF, the independence assumption will hold accurately for specific sets of challenges (at the order of n).

In the model proposed by Maes [START_REF] Maes | An accurate probabilistic reliability model for silicon PUFs[END_REF], δ C would correspond to the process variables and Z to the noise variable. However, the output bits from a delay PUF do not precisely correspond to a measurement of the process variables and further analysis is needed to apply the Maes model to delay PUFs. Furthermore, rather than estimating the BER from experimental data and then find the parameters using a top-down approach, we find it more convenient to derive the BER from measures of simple system parameters such as the SNR, in a bottom-up approach, as described in the next section. We feel that such a determination is better theoretically justified since it requires less ad hoc assumptions.

Delay PUF Reliability and Entropy

When considering n challenges to generate n response bits, there is a high probability that unreliable response bits are obtained. Katzenbeisser et al. [START_REF] Katzenbeisser | PUFs: Myth, Fact or Busted? A Security Evaluation of Physically Unclonable Functions (PUFs) Cast in Silicon[END_REF] showed that there is 2% to 15% unreliable bits, depending on the environment. Here we consider the proportion of faulty bits, or, equivalently, the average probability that a PUF bit flips, as a metric to characterize the PUF reliability. In contrast to an SRAM PUF, for which only the output bit values are available, delays can be measured in a delay PUF to detect unreliable bits, as we will explain in the next sections.

Reliability Assessment

The reliability of a delay PUF is directly related to the absolute value |δ C | of the delay difference δ C associated to each challenge C. Indeed, the larger the value, the smaller the probability to have a bit flip of the measured δ C sign due to measurement error. More formally, if we consider the Gaussian noise Z ∼ N (0, σ 2 ) added to δ C , the BER is the probability to have a bit flip for challenge C, and is given by the following Lemma 1. One has

BER(δ C ) = P sign(δ C + Z) = sign(δ C ) = Q |δ C | σ , (5.4)
where

Q(x) = 1 2 erfc( x √ 2 ).
Proof. Let Z ∼ N (0, σ 2 ) and δ C be a fixed value. Then

BER = P[sign(δ C + Z) = sign(δ C )] = P[(δ C + Z > 0, δ C < 0)] + P[(δ C + Z < 0, δ C > 0)] = P[Z > |δ C |, δ C < 0] + P[-Z > |δ C |, δ C > 0] = P[Z > |δ C |] = Q |δ C | σ since Z is symmetrically distributed.
C Error area δ C + Z ∼ N (δ C , σ 2 ) ∆ C ∼ N (0, Σ 2 ) PUF values (δ C ) distribution Measurement (δ C,t ) distribution
Error probability Table 5.1: BER for one bit according to the |δ C |/σ value.

Table 5.1 gives the BER one can expect for a given challenge. For a set of challenges, the BER has to be assessed on all the δ C values, which are assumed to be independent.

The average proportion of bit flips is the expectation of the BER over ∆ C , and is given by the following Lemma 2. One has

BER = E[BER(∆ C )] = 1 π arctan( 1 √ SNR
).

(5.5)

Proof. As shown in the proof of Lemma 1,

BER = P[sign(∆ C + Z) = sign(∆ C )] = P[Z > |∆ C |] = P[ Z σ > | ∆ C Σ | √ SNR].
Note that this probability is taken jointly over ∆ C , Z and that these are independent Gaussian variables, ∆ C ∼ N (0, Σ 2 ), Z ∼ N (0, σ 2 ). Therefore, X = ∆ C Σ and Y = Z σ are independent and follow standard normal distributions, and the formula becomes

BER = P[Y > |X| √ SNR].

CHAPTER 5. ON THE RELIABILITY OF PUFS

Since the probability distribution of (X, Y ) is isotropic, it is easily seen that BER equals

X Y θ = arctan( 1 √ SN R ) (1, √ SN R) Y > |X| √ SN R

Reliability Enhancement by Delay Knowledge

A classical and efficient method to enhance (reduce) the BER is to take advantage of ECCs, like the secure sketch methods presented by Dodis [START_REF] Dodis | Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data[END_REF] and exploited by reliable architectures like PUFKY [START_REF] Maes | Pufky: A fully functional puf-based cryptographic key generator[END_REF]. With this method, an enrollment phase takes place once, just after manufacturing, in order to build a public "helper data". The helper data, also called "secure sketch", can be either a n bit code-offset or a nk bit syndrome. During PUF usage, noise might corrupt the PUF value, but thanks to the secure sketch, the potential errors can be corrected by the ECC decoder.

We will investigate here another method to improve the reliability of the PUF that uses the knowledge of the δ C values to filter out unreliable bits. Therefore, ECC may not be necessary or at least less complex, which helps to reduce circuit complexity.

The BER can be decreased discarding the challenges which generate unreliable bits. These challenges are recorded during the enrollment phase in the helper data. This helper data is then used during the reconstruction phase of the PUF. This construction resembles the η-out-of-λ scheme by Škoric et al. [START_REF] Škoric | Robust key extraction from physical uncloneable functions[END_REF]. However, to make the computations tractable, instead of removing a fixed number of challenges, we remove bits that whose reliability is lower than a given threshold. Below we compute the resulting average reliability in terms of mean BER, and the average remaining entropy after bit-filtering.

Security Considerations

From the security point of view, this helper data does not unveil any information of the response bits, since the PUF responses to challenges are assumed independent. However, if an attacker could modify the helper data, she could reconstruct the PUF response, for example using an attack similar to the one described by Hiller et al. [START_REF] Hiller | Breaking Through Fixed PUF Block Limitations with Differential Sequence Coding and Convolutional BIBLIOGRAPHY Codes[END_REF].

An attacker could use the unreliable bits as a pivot to retrieve the key generated by the PUF. Indeed, suppose the attacker can exchange the reliability of bit i in and bit i -1 in the helper data, as shown in Fig. 5.4. If she noticed that the cryptographic result has not changed, that means that the key bits i -1 and i have the same value on average, as the unreliable bit is always biased towards '1' or '0' (the probability that it is exactly balanced is negligible). If she does the same with bits i and i + 1, she can deduce whether key bits i and i + 1 are the same, and consequently (by transitivity) if the reliable bits i -1 and i + 1 are the same. This method allows the attacker to retrieve the whole key.

For the attack to work, it suffices that the attacker knows whether the key is properly generated or not. In this respect, any prior knowledge about the value of the (secret) key is unnecessary, only whether or not it can be used, e.g., whether a secure boot (based on a master key derived from the PUF) unfolds well. In this respect, this attack is equivalent to a safe error attack in the field of embedded devices security [START_REF] Yen | Checking before output may not be enough against faultbased cryptanalysis[END_REF]. A natural countermeasure would be to have the helper data be checked for integrity (e.g., with a CRC). However, in an adversarial context, the attacker can change the helper data along with its CRC. Therefore, we have to assume that the helper data can only be read by an attacker, but cannot be modified. This can, for example, be achieved by storing it on ROM memory on the PUF. The declaration of "unreliability" is given at enrollment phase when the delay |δ C | for a challenge C is below a threshold T h, which has to be chosen to take into account the noise

R U R R 1 2 i i-1 i+1
R: Reliable U: Unreliable In what follows, we set T h = W • σ, where W expresses the capacity to filter the unreliable bits. Increasing W decreases the BER, but reduces the number of bits, hence the entropy. Figure 5.5 illustrates the distributions of ∆ C and the noise. It points out the unreliable area in the window [-T h, +T h] of width 2W σ.

δ C δ C + Z ∼ N (δ C , σ 2 ) δ C ∼ N (0, Σ 2 ) Unreliable area -Th Th 2W σ Reference values (δ C ) distribution (static randomness)
PUF delay distribution (with dynamic randomness) The average BER reduction after filtering the unreliable bits depends directly on T h = W σ and is given by the following Lemma 3.

BER f ilt = 2 erfc( W √ 2 √ SNR ) T (W, 1 √ SNR ) + 1 4 erf( W √ 2 √ SNR )(erf( W √ 2 ) -1) (5.6)

DELAY PUF RELIABILITY AND ENTROPY

83

where T represents Owen's T function:

T (h, a) = 1 2π a 0 e -1 2 h 2 (1+x 2 ) 1 + x 2 dx.
Proof. For the sake of simplicity, we will drop the subscript C from the random variable ∆ C . By definition of the filtered BER, we have that:

BER f ilt = +∞ -∞ p(∆ | |∆| > T h) • BER(∆) d∆.
This generic formulation, or very similar ones, have already been found before, for example by Delvaux [START_REF] Delvaux | Security Analysis of PUF-Based Key Generation and Entity Authentication[END_REF] (Eq 4.41). However, we will apply it here to a specific PUF, and can therefore derive a more explicit formulation. Indeed, we can find a closed form of E(BER f ilt ) after filtering the bits as:

BER f ilt = +∞ -∞ p(∆ | |∆| > T h)BER(∆) d∆ = +∞ -∞ 1 |∆|>T h (∆) p(∆) P(|∆| > T h) BER(∆) d∆ = 2 P(|∆| > T h) +∞ T h p(∆) • BER(∆) d∆ = 2 P(|∆| > T h) 1 2 √ 2πΣ +∞ T h e -∆ 2 2Σ 2 erfc( ∆ σ √ 2 ) d∆.
Using the following integral value for x, k > 0:

e -x 2 erfc(kx) dx = - 1 2 √ π(4T [ √ 2kx, 1 k ] + erf(x)(erf(kx) -1) + 1) + constant
(where T is Owen's T function, first introduced by Owen [START_REF] Owen | Tables for computing bivariate normal probabilities[END_REF]), and using a change of variables, we get that

BER f ilt = 2 P(|∆| > T h) (T ( T h σ , 1 √ SNR )+ 1 4 erf( T h √ 2Σ )(erf( T h √ 2σ ) -1)) or, since P(|∆| > T h) = erfc( W √ 2 √ SNR ) and T h Σ = W σ Σ = W √ SNR , BER f ilt = 2 erfc( W √ 2 √ SNR ) T (W, 1 √ SNR ) + 1 4 erf( W √ 2 • √ SNR )(erf( W √ 2 ) -1) .

Entropy After Filtering Out Unreliable Bits

The proportion of unreliable bits is given by

P(Bit unreliable) = P(|∆| < T h) = erf( T h √ 2Σ ) = erf( W √ 2SNR
).

(

In other words, the average remaining entropy of a circuit with n elements (thus, of complexity proportional to n) is equal to

H(n, W ) SN R = n • erfc( W √ 2SNR
).

(

With this method, it is necessary to increase the number of elements to generate a given entropy. The expected number of elements n, with n > h, to consider in order to obtain h bits of entropy is given by:

n = h 1 -P(Bit unreliable) = h erfc( W √ 2SNR ) . ( 5.9)
Figure 5.6 represents the average remaining entropy for a circuit, depending on the SNR and the target BER. This characterizes the tradeoff between reliability and entropy. If ever it is not possible to reach the required entropy, the device is discarded. The probability of this happening can also be computed. Since the obtained delays are independent (when choosing a Hadamard matrix for the challenges), the number of unreliable bits is given by a binomial distribution B(n, erf( W √ 2SNR

)) on a PUF with n elements. Thus,

THE "TWO-METRIC" METHOD

85

p discard = n i=n-h+1 n i erf( W √ 2SNR ) i erfc( W √ 2SNR ) n-i = I p d (n -h + 1, h) (5.10)
where I x (a, b) is the regularized incomplete beta function and p d is the probability of discarding a bit, p d = erf( W √ 2SNR ).

5.4

The "Two-Metric" Method

Motivation and Definition

Instead of extracting one PUF bit from the delay difference δ C as the sign of δ C , it can also be done by considering the interval between the first and third quartile of the ∆ C distribution:

b = 1{δ C ∈ [δ 1/4 , δ 3/4 ] = [-aΣ, +aΣ]}
where a = 0.674489... Let us call this method the "metric" M0. Figure 5.7 with Σ = 1 illustrates the bit extraction by the method M0 according to the value of ∆. The entropy is still of one bit with this metric M0 as the area for bit=0 and bit=1 is the same, namely 1/2. Let us consider now two metrics M1 and M2 as illustrated by Fig. 5.8 and Fig. 5.9 respectively. These metrics use two constants, T 1 > T 2 , such that

T 1 -T 2 φ(x) dx = T 2 -T 1 φ(x) dx = 1 2
and

T 2 0 φ(x) dx = 1 8 .
Hence, as shown in Fig. 5.10, there are eight octiles in the pdf of ∆ which are:

[-∞, -T 1 [, [-T 1 , -a[, [-a, -T 2 [, [-T 2 , 0], ]0, T 2 ], ]T 2 , a], ]a, T 1 ], ]T 1 , +∞].
Using this observation, we can now define a more refined bit extraction method, dubbed the "two-metric" method.

During the PUF enrollment phase, if we determine that the PUF response would be unreliable with metric M1, i.e. δ C is around -T 1 or T 2 , we choose the metric M2. On the other hand, if δ C is around -T 1 or T 2 , we choose the metric M2. The helper data now indicates the type of metric rather than the reliability. More formally, as

T 2 0 φ(x) dx = a T 2 φ(x)
M ∈ {M 1, M 2} metric ∈ {M 1, M 2} N for i ∈ {1, . . . , N } do ∆ ← PUF(c i ) if ∆ ∈ [-a, 0] or ∆ > a then metric i ← M 1 else metric i ← M 2 end if end for return metric

Reliability of the The "Two-Metric" Method

Supposing that the initial measurement ∆ is done without noise, we can deduce from Fig. 5.10 that the challenges with the highest bit error rate BER are those where ∆ is either close to 0, or around ±a. Computing those error rates, we find that the challenges with ∆ around 0 are actually those with the highest BER.

In the general case, where a, T 1 and T 2 must be multiplied by Σ, the probability to get a bit error is thus upper-bounded by

BER < +∞ T 2 Σ 1 √ 2πσ e -x 2 2σ 2 dx + +∞ T 1 Σ 1 √ 2πσ e -x 2 2σ 2 dx < 1 2 erfc( T 2 √ SN R √ 2 ) + 1 2 erfc( T 2 √ SN R √ 2 )
For instance, for a typical value A simulation shows that the average BER, for √ SN R = 15, is actually less than 10 -8 . The results of these simulations are shown in Fig. 5.11, and compared to the BER rates without helper data. These results have a relative margin of error of less than 1% for all estimates at the 95% confidence level 1 .

Security

The Helper Data contains the choice of a metric amongst M1 and M2. The question is to know if an attacker can retrieve the key by inverting the metric of the Helper Data, as explained above and illustrated in Fig. 5.4. Here we assume the attacker changes the metric metric i of bit i from M1 to M2. Let us call bit -1 , the bit value before the attack and bit the bit value after the attack. The attacker can not retrieve any information if:

P(bit = 0|bit -1 = 0) = P(bit = 1|bit -1 = 1)
and

P(bit = 1|bit -1 = 0) = P(bit = 0|bit -1 = 1)
For the two-metric method, these probabilities are all equal to 1 2 regardless of the value of the key bit when changing from one metric to the other. Therefore, there is no possibility for the attacker to gain any information about the key bits by changing the metric. Consequently the two-metric method is natively robust against such attacks.

Entropy

As all the bits are used, there is no loss of entropy as it is the case when using a single metric.

Translation for Various PUF Architectures

When applying our results on real PUF architectures, we must suppose that the output bits are independent and non-biased. By restricting the set of possible challenges, we can prove, under the assumption that the theoretical model describing the PUF is accurate, that the remaining output bits are indeed independent and non-biased. However, this is no longer true when the PUF behavior deviates from that predicted by its model. It is possible to ensure that the output bits are not biased and uniform using standard test suites, for instance those provided by NIST [START_REF] Bassham | 22 rev. 1a[END_REF]. If these tests fail, bias and correlation can be corrected by applying fuzzy extractor techniques [START_REF] Delvaux | Efficient fuzzy extraction of puf-induced secrets: Theory and applications[END_REF] prior to using reliability-enhancing methods.

RO-PUF

The RO-PUF has been first described by Suh and Devadas [START_REF] Suh | Physical unclonable functions for device authentication and secret key generation[END_REF]. In the general case, it uses a certain number of oscillating loops for which the oscillation frequencies are measured and compared. In the setting that we will analyze, and that had already been described in this seminal work, we will use 2n ring oscillators to generate n bits. To describe this PUF in our unified framework, we will define a challenge C as any n-bit string with Hamming weight exactly 1. If C m is such that c m i = 1 iff m = i, then the delay difference δ C m will correspond to the frequency difference between oscillators 2m and 2m + 1. Thus, the δ C m will be mutually independent. Therefore, our framework can be directly applied in order to estimate the reliability-entropy tradeoff in case filtering is used.

RO sum PUF

The RO sum PUF, or recombined oscillator, has been proposed by Yu and Devadas [START_REF] Yu | Recombination of physical unclonable functions[END_REF]. Instead of comparing the oscillator frequencies, they are measured, added or subtracted, before one bit is generated from the sign. More precisely, the 2n oscillators are divided into n pairs. Let C = (c i ) i be a challenge of length n. If d i is the delay difference for the two oscillators of the i-th pair, then the total delay is obtained as

δ C = n i=1 d i (-1) c i .
Here, d i should be modeled as a realization from a normal law, with variance Σ 2 0 . Therefore, we will have that ∆ C ∼ N (0, nΣ 2 0 = Σ 2 ). There are 2 n possible challenges, however, the delays for all these challenges will not be independent. It has been shown by Rioul et al. [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF], for a different PUF but the same delay model, that the challenges are mutually independent if, when converted to {±1} vectors instead of {0, 1} vectors, they are orthogonal. We can therefore find a subset of n challenges that are independent if a Hadamard matrix of rank n exists. This is always the case if n is a power of two or a multiple of 4 smaller than 668 [START_REF] Ðoković | Hadamard matrices of order 764 exist[END_REF]. Assuming this is the case, we can choose any such subset of challenges for the n possible challenges. Our framework can then be applied to this PUF.

Loop PUF

The Loop PUF, described by Cherif et al. [START_REF] Cherif | An easy-to-design PUF based on a single oscillator: The loop PUF[END_REF], strongly resembles the RO sum PUF, with the exception that one configurable ring oscillator is used, instead of 2n simple ROs for the RO sum PUF. For the Loop PUF, each RO comprises n configurable and balanced delay element pairs. During delay measurement, the signal only passes through one half of the delay elements, this half being determined by the input challenge. The same measurement is then done for the complementary challenge, so that the signal passes through the other half of the delay elements, and the delay difference is then computed. The mathematical model is thus very similar to that of the RO sum PUF, with some minor differences. For example, in the RO sum PUF, the delays for the individual ring oscillators are first quantified and then added, which might lead to some rounding errors. This is less the case for the Loop PUF, since a total delay is directly measured. Thus, there are only two delay quantifications for the Loop PUF.

As shown by Rioul et al. [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF], in order to obtain independent delay differences, and thus independent bits, the challenges need to be orthogonal, in the same sense as before. Thus, an entropy of n bit can be obtained by choosing a n × n Hadamard matrix for the challenges, if a Hadamard matrix of this size exists.

EXPERIMENTS AND VALIDATION WITH REAL SILICON

91

Experiments and Validation with Real Silicon

In this section, results are presented only for bit filtering. Because the two-metric method is not "tunable" and the SNR of the tests circuits is high, too many measurements would have been necessary in order to obtain a sufficient number of bit-flips to reliably estimate the BER.

Architecture of the Test Circuit

We used Loop PUFs with n = 64 delay cells for our experiment. The cells use 65 nm CMOS technology, and each test chip contains 49 PUFs, embedded in a 7 × 7 matrix. We performed the delay measurements during L = 2 14 Following [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF], we choose a 64 × 64 Hadamard matrix as the challenge matrix to control the 49 Loop PUFs. The 64 challenge responses can therefore be considered independent. We perform T = 1000 measurements for each challenge and each PUF per chip. This directly yields the responses for the Loop PUF. In order to simulate a RO-PUF, we fix a challenge index m and consider the 24 × T response delays:

δ 2j m,t -δ 2j-1 m,t , j ∈ [1, 24] .
In a similar fashion, for the RO sum PUF we choose a 48 × 48 Hadamard matrix C. For a fixed challenge index m of the Loop PUF, we then obtain 48 × T response delays:

           C •       δ 1 m,t δ 2 m,t . . . δ 48 m,t                  .

BER and Entropy Measurement

Results

Six test chips have been analyzed, and the measured BER and remaining entropy have been plotted in Fig. 5.12.

The error bars represent the range of values obtained among the tested chips. Although they do not share the exact same SNR, a middle value has been chosen, so that a simple comparison is possible. The SNR was calculated by estimating the variance of ∆ C and Z from the delay measurements of the test chips. Moreover, the range of measured SNRs is relatively small (between 180 and 250).

Discussion

For the remaining entropy, the measured and predicted values match quite closely. This seems to confirm the hypothesis of a Gaussian distribution for the average delay values. For the bit error rate however, the interpretation of the results seems more complicated. Indeed, while the BER for small filtering thresholds, and thus "large" BERs, seems to match our prediction, this is not the case for larger thresholds, at least for the RO-PUF simulation and the Loop PUF. We can see two explanations for this:

First, the sample size is probably not large enough to reliably estimate probabilities around 10 -8 . Indeed, for each chip, we record about 3 million samples, and thus, even one bit error would yield a BER, for that circuit, of more than 3 • 10 -7 . Therefore, the BERs for parameters W ≥ 4 come with a fairly large uncertainty.

The small sample size does not explain everything, however. When further analyzing the delay measurements, we notice that the noise distribution does not perfectly follow a Gaussian distribution. Indeed, on some chips, we observe multiple measurements that are more than 7σ away from the computed mean delay value, as taken over 1000 measurements. This should not happen more than once in about 500 million measurements, if the noise was truly Gaussian. Thus we must admit that the noise is not exactly Gaussian. More exactly, it seems to be more heavy-tailed than a Gaussian noise. This could be an artifact of our experimental setup. Indeed, it forces us to wait a relatively long time span between measures, and the outliers could be explained, for example, with voltage fluctuations (the Loop PUF is relatively sensible to supply voltages changes). On the other hand, it should not come to a great surprise that a physical phenomenon does not exactly follow a Gaussian distribution. In order to derive a more precise model, other types of noise 5.7. EFFECT OF ENVIRONMENTAL CHANGES: TEMPERATURE 93 distributions need to be considered.

One can further notice that the divergence from the expected BER is almost absent from the RO sum PUF simulation. This can be easily explained. A simulated delay measurement for the RO sum PUF corresponds to the sum of 48 independent Loop PUF delay measurements. If only one Loop PUF measure is an outlier relative to the expected Gaussian noise distribution, this will less affect the whole sum. This also explains why the RO-PUF exhibits less divergent behavior than the Loop PUF, as any outlier will be summed with another delay measurement. These results, however, are possibly artifacts of our experimental setup, if we suppose that external factors cause these outlier measures. Indeed, in a real RO-PUF or RO sum PUF, all measures would certainly be done in parallel, and might be affected by the same glitch at the same time. Therefore, this does not say anything about the intrinsic robustness of these three PUF types.

Effect of Environmental Changes: Temperature

PUFs are not necessarily used in the same environmental conditions they were enrolled at. Mainly two factors seem to be able to affect their behavior: temperature and input voltage [START_REF] Gassend | Silicon physical random functions[END_REF]. We will assume that the input voltage can be controlled, via an voltage regulator for instance, and not further investigate in this direction. However, it is more complicated to control the temperature at which the PUF will be used, and it would therefore be helpful if it was possible to model the PUF-response dependency on temperature. In this section, we propose and test such a model. A similar model has been proposed by Maes [START_REF] Maes | An accurate probabilistic reliability model for silicon PUFs[END_REF], but for delay PUFs, it is possible to more directly test the model and make more straightforward predictions.

Assumptions

Given our experiments, we think that it is safe to make the following assumption: The delay response of a given oscillator is linearly dependent on the temperature, but the proportional constant might vary among ring oscillators. Testing on the Loop PUF circuits yielded a linear regression R 2 score above 0.999 for every oscillator. In addition, we will assume that this proportional constant follows a normal law. The curve for different oscillators in Figure 5.13 seems to validate this kind of distribution. Since in general, only the differences between ring oscillators are being considered (for the RO-PUF as well as the RO sum PUF), we can suppose that the probability distribution is centered. More formally, let's denote the temperature by θ, and the linear dependency coefficient by , where is a realization of a random variable L ∼ N (0, σ θ ) . We therefore have the model for the temperature dependent PUF:

P θ : C → δ C + Z + θ, b = sign(δ C + Z + θ)
(5.11)

Average BER

We can now try to compute the average bit error rate over all average delays δ C and dependency coefficients . As a reminder, the BER is defined here as

BER θ = P [sign(∆ + Z + Lθ) = sign(∆)]
(5.12)

Since Z and Lθ are two centered independent Gaussian random variables, with variance respectively σ 2 and θ 2 σ 2 θ , the sum is also a Gaussian random variable with variance σ 2 + θ 2 σ 2 θ . Therefore, the result for the average BER obtained in 5.3.1 can be directly applied, by replacing σ with σ 2 + θ 2 σ 2 θ :

BER θ = 1 π arctan( σ 2 + θ 2 σ 2 θ Σ ) (5.13)
Thus, for the average BER, using the PUF at a temperature that is different from the enrollment temperature is equivalent to a loss of SNR. Of course, for individual delay measurements, this is not true, as the BER can exceed 0.5 if an inversion of the average sign happens due to the temperature difference, but it remains true for the average BER.

Effect on Delay PUFs

The RO-PUF and RO sum PUF are equally affected by the temperature dependency of the ring oscillators on the temperature. Indeed, for the RO-PUF, the delay difference is simply the difference of delay among two oscillators, and the model can be directly applied as is. For the RO sum PUF, the total delay difference is actually the sum of a larger number of ring oscillator-pair delays. However, since the sum of Gaussian random variables still follows a Gaussian distribution, the same formula applies for the RO sum PUF, where σ, σ θ and Σ are simply multiplied by the square root of the number of ring oscillator pairs. Since the average BER only depends on the ratio between these quantities, the BER formula is unchanged.

The case of the Loop PUF is a little different. Indeed, the delay differences are measured on the same oscillator, and different challenges should have a similar temperature dependency. However, as Figure 5.13 shows, this is not exactly the case. While the temperature dependency coefficients vary less between challenges of the same oscillator than between oscillators, the variance is not zero. The model seems also applicable to the Loop PUF, albeit with a lower standard deviation σ θ .

Impact on the "Two-Metric" Method

The "two-metric" method is more sensitive to a change in the variance of the delays, as both the helper data generation and the bit extraction depend on it. One solution is to systematically assess the value of Σ before transforming the delay difference into a response bit. For instance the estimation can be carried out as per:

Σ = 1 N N i=1 ∆ 2 i
where N is the number of challenges and ∆ i the time difference of the Delay PUF measured for each challenge i. Assuming a change in temperature and voltage only amounts to a change in Σ and σ, one can determine the new BER by simulation. The BER actually depends on the number of challenges, as shown in Fig. 5.14, because this number determines the precision of the estimate Σ.

While the BER is increased in this setting, it stays below 5 • 10 -8 for √ SN R equal to 15 and 128 challenges, and below 6 • 10 -7 for 64 challenges.

Because Σ is estimated using noisy measurements, Σ will actually overestimate Σ. Indeed, it is easy to see that

E[ Σ] = √ Σ 2 + σ 2 .
If the SNR is expected to be constant across different voltages and temperatures, this information could be used to improve the estimation of Σ. In any case, this requires more experiments to really assess the voltage and temperature impact on the SNR. Furthermore, because the value of Σ also influences the helper data generation, it is not easy to determine how the "two-metric" method is affected when enrollment and response generation are performed under different environmental conditions.

Conclusion

This chapter first presents the formalism to express the entropy and reliability of multiple delay PUFs: the RO-PUF, the RO sum PUF and the Loop PUF. We obtained a closed- The tradeoff between BER, entropy and complexity has been characterized. The resulting parameter selection for a given application is quite straightforward and simple. Practical experiments on few hundred PUFs designed in 65 nm CMOS process validate the theory. Testing the effect of temperature on the different types of PUFs is difficult when simulating with Loop PUFs. Tests with "native" PUFs might be necessary for a more thorough validation.

A second improvement technique, the "two-metric" method has also been proposed. This method is immune against helper-data tampering attacks and preserves the whole entropy while obtaining very low bit error rates. However, it is more sensitive to changes in environmental conditions. This poses an interesting challenge which, once solved, could make this method more practical to use.

The Gaussian model for process and noise variables are validated by these experiments up to a certain threshold. Beyond, the Gaussian model may not be valid at the far tail of the noise distribution, and an adequate model for the noise distribution is a subject for future work. Such a model would allow more efficiently designs of PUFs with very low error rates. In particular, this model for reliability (also sometimes termed steadiness) is a suitable metric for stochastic models being developed in ISO/IEC 20897 project [START_REF] Guilley | ISO/IEC NP 20897[END_REF].

5.A Verifying the Reliability of a PUF

Once a PUF has been designed, regardless of the methods employed to enhance its reliability, it is natural to verify that the key (or bit) error rate is sufficiently low for its intended application. In general, when given a PUF, the goal is to test whether its failure probability p is below some threshold ε. Suppose that we consider the PUF as a black box here: all we can do is request an identifier and check if the generated identifier is the expected one. How many times (say n) do we need to generate an identifier that is wrong no more than t times in order to be certain that the needed reliability is attained ?

Actually, as such, the problem is not well-posed. There is always the chance for an unreliable PUF to pass any stochastic testing, and for a reliable PUF to fail it. Therefore, we must specify the following parameters:

• What proportion of reliable PUFs (p ≤ ε) are allowed to be rejected ? Let us denote this proportion with α.

• What proportion of unreliable PUFs (p > ε) are allowed to pass ? Let us denote this proportion with β.

Now, the problem is as a hypothesis testing problem, but it is still ill-posed. That is because for any stochastic testing method that takes finite time, the probability of rejecting a PUF is a continuous function of its failure probability p. However, if α < 1β (which should be the case for any reasonable choice of these parameters), then the rejection probability would be discontinuous for p = ε, which is not possible. The second requirement thus needs to be somewhat relaxed. The final, well-posed problem is thus the following: given ε and δ, α and β, such that • a proportion α of reliable PUFs (p ≤ ε) might be rejected and • a proportion β of unreliable PUFs (p > ε + δ) might pass, how should the stochastic testing parameters n and t be chosen ?

5.A.1 Illustrating Example

For example, take n = 10 7 and t = 120, that is, 10 7 identifiers are generated by a PUF, and the PUF is rejected when there is a mismatch between the expected and generated identifier more than 120 times. The PUF rejection probability, as a function of its true error rate p, is computed in Figure 5.15. It shows a steep transition from a rejection rate of almost 0 to a rejection rate of almost 1 around p = t n = 1.210 -5 . For instance, a PUF with error probability 10 -5 will be rejected with probability 2.27% while a PUF with error probability 1.5 • 10 -5 will pass with probability 0.66%.

5.A.2 Finding n and t

As shown in the previous example, for fixed ε, δ, n and t, it is easy to compute α and β. However, it is more useful to fix α and β, and then compute the corresponding n and t. An exact solution is possible but it requires testing several values of n and t. For this procedure to be more efficient, it is better to start with a good approximate solution, and then exploring neighboring values. The simplest way to do so is to approximate the binomial distribution B(n, p) with the Gaussian distribution N (np, np(1p) 2 ). Then, t can be fixed as a function of n.

In order to do so, the z-score corresponding to α needs to be computed first. In other words, we need to determine z α such that P(N (0, 1) > z α ) = α This value can be found in standard tables or computed using the inverse error function provided in numerous mathematics-oriented function libraries. When using standard tables, it is important to mention that most are two-tailed standard normal tables, while a one-sided z-score is needed here. This corresponds to the z-score for 2 * α in a two-tailed standard normal table such as https://www.sheffield.ac.uk/polopoly_fs/1.43999! /file/tutorial-10-reading-tables.pdf.

Because of the scale invariance property of the normal distribution, we also have that

P[N (np, np(1 -p)) > np + z α np(1 -p)] = α.
Setting p = ε, the minimum number of failures to tolerate among n tries in order to reject less than a proportion α of reliable PUFs can be easily determined:

t ≥ nε + z α nε(1 -ε) .
A similar reasoning can be applied to fix n given β. First, a value z β needs to be determined that verifies P(N (0, 1) > z β ) = β.

We then have that

P[N (np, np(1 -p)) < np -z β np(1 -p)] = β.
Setting p = ε + δ, we then find a second constraint for t that is required in order to pass no more than a proportion β of non-reliable (p ≥ ε + δ) PUFs:

t ≤ n(ε + δ) -z β n(ε + δ)(1 -(ε + δ))
Ignoring the fact that both t and n need to be integers, we can solve for n and find an approximation as

n ≈ 1 δ 2 z 2 α ε(1 -ε) + z 2 β (ε + δ)(1 -ε -δ) + z α z β ε(1 -ε)(ε + δ)(1 -ε -δ)
As an example, for ε = 10 -5 , δ = 10

c i • X = n j=1 c i,j X j (i = 1, 2, . . . , M ) (6.1)
and the associated sign bits

B i = sign(c i • X) ∈ {±1} (i = 1, 2, . . . , M ). (6.
2)

The question addressed in this chapter is the following: What is the joint entropy of the sign bits

H(C) = H(B 1 , B 2 , . . . , B M )? (6.3)
In particular, can we evaluate the maximum entropy H(n) = max C H(C) attained for the full universe code C = {±1} n ? Despite appearances, this problem turns out to be largely combinatorial as shown below.

Notations and Definitions

Definition 11 (Challenge code). Let n > 0, M > 0 be two integers. A (n, M ) challenge code C is a subset C ⊆ {-1, +1} n of cardinality M . The elements of this subset are called codewords, and the i-th codeword is denoted by c i . By an abuse of notation, we identify the challenge code with the n × M matrix C, called the challenge matrix, which rows contain all codewords exactly once. The i-th row is c i , and conversely, for any codeword c ∈ C, i(c) denotes its row index.

The motivation for this problem comes from hardware security. Modern secure integrated circuits make use of hardware primitives called physically unclonable functions (PUFs) that can generate unique identifiers from challenges, such as described, for example, by Maes [START_REF] Maes | Physically unclonable functions: A study on the state of the art and future research directions[END_REF]. More formally, a PUF is a function that takes several challenges c 1 , c 2 , . . . , c M (the so-called challenge code) as inputs and returns the bitvector identifier (b 1 , b 2 , . . . , b M ). PUFs exploit small, uncontrollable physical variations of the manufacturing process that cannot be replicated, hence the name "physically unclonable".

x : C → {-1, +1} defined as f x (c) = sign(c • x), ( 6.4)
where sign is the sign function and • denotes the usual scalar product. Equivalently, f x is given by the sign vector b

= (b 1 , b 2 , . . . , b M ) ∈ {-1, +1} M such that b i = sign(c i • x) (i = 1, . . . , M ). ( 6.5)
The following notion of randomized PUF coincides with that of a PUF at a design stage, when it is not yet instantiated by a foundry fabrication process (cf. [121, Fig. 1]).

INTRODUCTION 103

Definition 13 (Randomized PUF). For a fixed (n, M ) challenge code, we define the random PUF as f X , where X = (X 1 , X 2 , . . . , X n ) and X i are i.i.d. standard normal random variables X i ∼ N (0, 1).

The corresponding random sign vector is then B = (B 1 , . . . , B M ), where

B i = sign(c i • X) (i = 1, . . . , M ) (6.6)
with probability distribution

P b = P[B = b] = P[B 1 = b 1 , B 2 = b 2 , . . . , B M = b M ] (b ∈ {-1, +1} M ).
We denote |supp(P b )| the cardinality of the support of P b .

To assess the security of a PUF, it is necessary that the entropy of the identifier's distribution is sufficiently high. The most natural definition is the Shannon entropy, characterizing the uncertainty about the PUF distribution. Depending on the desired application, other kinds of entropies may be relevant. The most conservative view is to consider the min-entropy H ∞ , which can be interpreted as the "cloning" entropy in the worst case, when the PUF to clone is obtained with probability max b∈{±1} P b . When using a PUF to generate a key, the min-entropy also characterizes the security of the key, as shown for example in [START_REF] Dodis | Key derivation without entropy waste[END_REF]. In other settings, the collision entropy allows for a more accurate security bound on the key derivation, as suggested by Skorski [START_REF] Skorski | Key derivation for squared-friendly applications: Lower bounds[END_REF] and Dodis et al. [START_REF] Dodis | Overcoming weak expectations[END_REF]. It accounts for PUF uniqueness, since it is related to the probability that no two generated keys are the same. In contrast, the max-entropy H 0 has no obvious practical interest apart from being an easily computable upper-bound of the Shannon entropy (and of all other Rényi entropies).

Definitions for the different kinds aforementioned entropies are given below. Each depends on the choice of a challenge code C. Definition 14 (Rényi entropies [125]). For α ≥ 0, the Rényi entropy of order α is defined as

H α (C) = 1 1 -α log 2 b∈{±1} M P α b .
As special cases (taking the limits when α approaches 1 or infinity) we have

H 0 (C) = log 2 |supp(P b )| (max-entropy) H 1 (C) = H(C) = b∈{±1} M P b log 2 1 P b (Shannon entropy) H 2 (C) = -log 2 b∈{±1} M P 2 b (collision entropy) H ∞ (C) = -log 2 max b∈{±1} M P b (min-entropy).
A well-known property of the Rényi entropies is that H α is non-increasing in α. Thus, for any code C, H

∞ (C) ≤ H 2 (C) ≤ H(C) ≤ H 0 (C). It is also easily seen that H 2 (C) ≤ 2H ∞ (C).
(i ∈ [1, n]) X X = (X 1 , X 2 , . . . , X n ) x i realization of X i M number of challenges C challenge code, a matrix defined by its rows (c i ) i∈[1,M ] sign sign(x) = 1 if x > 0, sign(x) = -1 if
x < 0, and sign(0) = 0. Other types of simulations also suggest a Gaussian distribution of process variations, and thus delay differences, in electronic circuits [START_REF] Chang | Statistical timing analysis considering spatial correlations using a single PERT-like traversal[END_REF]. This motivates the choice of modeling the delay differences of the Loop-PUF as independent Gaussian variables.

B i B i = sign(c i • X) B B = (B 1 , B 2 , . . . , B M ) b i realization of B i b realization of B P b P b = P[B = b]
Because they share the mathematical model with the Loop-PUF, definitions 12 and 13 also apply to the Arbiter PUF [START_REF] Gassend | Delay-based circuit authentication and applications[END_REF], for which the Gaussian model has been confirmed [START_REF] Majzoobi | Lightweight secure pufs[END_REF][START_REF] Tajik | Physical characterization of arbiter pufs[END_REF], and to the RO-sum PUF [START_REF] Yu | Recombination of physical unclonable functions[END_REF].

These process variations can then be exploited in different ways. For example, it is possible to build authentication protocols based on PUFs: an authentication server queries a PUF via a set of challenges and checks the PUF answer against a whitelist. In this way, counterfeit or overproduced chips can be detected. This requires no implementation of costly asymmetric cryptography primitives, and is therefore adapted to low-cost IoT devices. The PUF can also be used to generate a secret cryptographic key that is required for secure storage or communications with other devices. Using a PUF is more secure than directly storing the cryptographic key into memory, from where it might potentially be read or written by an attacker.

State of the Art

Results on the min-entropy

An upper bound of the min-entropy has been derived for the so-called RO-sum PUF by Delvaux et al. in [START_REF] Delvaux | Upper bounds on the min-entropy of RO sum, arbiter, feed-forward arbiter, and S-ArbRO PUFs[END_REF]. Since this PUF shares the same mathematical bound as the Loop-PUF, this result is also relevant for our analysis. The following upper-bound is valid for odd values of n:

H ∞ (n) ≤ -log 2   1 2   1 - n -1 n (n-3)/2 i=0 (2i)! (i!) 2 (4n) i     . ( 6

Exact values for small n

Exact results for the entropy and probability distribution of the Loop-PUF have been obtained in certain special cases. Rioul et al. showed in [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF] that the optimal challenge code when M ≤ n is given by a Hadamard code 1 C for which one can attain a uniform distribution of the Loop-PUFs, giving

H(C) = n.
The exact calculation of the PUF distribution of n delay elements for M ≥ n can be carried out only for very small values of n. Rioul et al. [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF] give the exact values of the Loop-PUF distribution, and thus H(C) for all n, M ≤ 3 using well-known closed-form formulas for orthant probabilities of bi-and trivariate normal distributions (see Lemma 5).

Results on the max-entropy

The max-entropy H 0 (n) is simply the logarithm of the number of different Loop-PUFs of n delay elements. This number has been computed for small values of n ≤ 10, because it

1 When such a Hadamard code exists, which implies that n = 1, 2 or a multiple of 4.

CLOSED-FORM EXPRESSIONS

107 actually corresponds to the number of so-called Boolean Threshold Functions (BTF) of n -1 variables. This number was determined up to n = 8 by Winder [START_REF] Winder | Enumeration of seven-argument threshold functions[END_REF], up to n = 9 by Muroga et al. [START_REF] Muroga | Enumeration of threshold functions of eight variables[END_REF] and finally up to n = 10 by Gruzling [START_REF] Gruzling | Linear separability of the vertices of an n-dimensional hypercube[END_REF]. Asymptotic estimates have also been published [START_REF] Zuev | Methods of geometry and probabilistic combinatorics in threshold logic[END_REF]. These results are recalled in Section 6.6.1.

Unfortunately, the quadratic behavior in n of the max-entropy H 0 (n) somehow overestimates the security of the PUFs, since it is much higher than the min-entropy, which is approximatively linear in n.

Our Contributions

In this work, we extend previous results in two directions.

First, we provide the exact values of the distribution of the Loop-PUF (for all possible challenges) for n = 3 and n = 4. This allows us to compute the exact values of all entropies in these cases. Such an exact computation comes as a surprise since no closed-form expression exists for the orthant probabilities of an M -dimensional Gaussian vector for M ≥ 4. In our computation, we leverage on the discrete nature of the challenge code to determine these probabilities up to M = 8.

Second, we introduce a novel algorithm for the simulation of equivalence classes (SEC). The SEC algorithm also finds all equivalence classes of challenge codewords corresponding to the same value of joint probabilities P b . Interestingly, this problem is purely of discrete combinatorial nature. The actual values of the corresponding probabilities are then estimated by Monte Carlo simulation, which allows us to compute all relevant entropies. We provide the resulting values of the entropies H 0 (n), H(n), and H 2 (n) up to n = 10.

The remainder of this chapter is organized as follows. Section 6.2 presents exact values of the distributions and entropies for the cases n = 3 and n = 4. Section 6.3 recalls results obtained from the study of Boolean threshold functions which allow to efficiently characterize the symmetries of the PUF distribution. The SEC algorithm is presented in Section 6.6 along with the entropies up to n = 10. Section 6.7 concludes.

Closed-form expressions

Preliminaries

In order to determine the closed-form expressions of the PUF distributions up to n = 4, we need the following lemmas.

Lemma 5 (Orthant probabilities for the bi-and trivariate normal distribution). Let n > 0, c 1 and c 2 two challenges, and

Y 1 = c 1 • X, Y 2 = c 2 • X. Let ρ = E[Y 1 Y 2 ] n the correlation coefficient of Y 1 and Y 2 . Then P[Y 1 > 0, Y 2 > 0] = P ++ = 1 4 + arcsin(ρ) 2π . ( 6

Case n = 3

By considering the challenge matrix

C 3 = 1 1 1 1 1 - 1 -1
, exact probabilities P b can be derived by using the formula for trivariate Gaussian, recalled in Equation (6.13). This yields an entropy of

H(C 3 ) = - 1 4 -3 arcsin 1 3 2π log 1 8 -3 arcsin 1 3 4π . ( 6.14)
For the matrix with four challenges

C 4 =   1 1 1 1 1 - 1 -1 - 1 1
  and the two sign vectors + ---and -+ ++, we have that P +---= P -+++ = 0.

By exploiting symmetries, it follows that eight sign vectors satisfy P ++++ = P ++--= P +-+-= P +--+ = P ----= P --++ = P -+-+ = P -++-= p and for the six remaining sign vectors P +++-= P ++-+ = P +-++ = P ---+ = P --+-= P -+--.

Furthermore, by adding complementary challenges, we have that p = p + 0 = P +--+ + P +---= P +--• = 1 8 -3 arcsin 1 3 4π using the generic formula for trivariate normal distributions. These findings are summarized in the table below.

H(C 4 ) = H(3) = -   1 -6 arcsin 1 3 π   log   1 8 -3 arcsin 1 3 4π   -6   arcsin 1 3 π   log   arcsin 1 3 π   . ( 6
.15)

Case n = 4

Similar techniques have been employed in order to compute entropies with n = 4. Because arcsin( 1 2 ) π is a rational number (it is in fact equal to 1 6 ), the results for n = 4 are much simpler, compared to the case n = 3.

In order to compute the distribution for the maximal challenge code, we first determine the distributions of smaller codes. Sign vectors with zero probability are determined 110 CHAPTER 6. ENTROPY ESTIMATION OF PUFS VIA CHOW PARAMETER according to Lemma 6. Those of equal probability are found with the help of Lemma 7. Using recurrence relations between the probabilities, we are then able to deduce the sign vector distribution for larger codes, when adding one codeword each time.

The first four codewords that are chosen are the lines of a Hadamard matrix of order 4:

C 4 = 1 1 1 1 S1 -1 - 1 1 -- 1 --1 .
As recalled before, the sign vector distribution is uniform for this challenge matrix.

The results when adding one additional codeword are summarized below. For the sign vectors, it is understood that the opposite sign vectors are also present in each probability class.

-Additional codeword ( 1 ): This code maximizes the entropies. As there are too many sign vectors per equivalence class to enumerate them all, we give here only their numbers.

Probability per sign vector Number of sign vectors

The Chow Parameters of PUFs

In the remainder of this section, we will consider PUFs for which the challenge code C contains all possible challenges. Seen as boolean functions, they correspond to a specific type of so-called boolean threshold functions (BTF).

Definition 16 (Self-dual BTF [START_REF] Goto | Some theorems useful in threshold logic for enumerating boolean functions[END_REF]). Let x ∈ R n be such that for all c ∈ {±1} n , c • x = 0. The self-dual BTF of size n and weight sequence x is the function f

x : {-1, +1} n → {-1, +1} defined as f x (c) = sign(c • x) (6.16)
where c • x = n i=1 c i x i is the usual scalar product. This definition coincides with that of a PUF with n variables. In the remaining sections of this chapter, we will thus use the term "PUF" to mean "self-dual BTF". BTFs have been studied since the 1950's as building blocks for Boolean circuits [START_REF] Winder | Single stage threshold logic[END_REF] and also find applications in machine learning [START_REF] Cover | Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition[END_REF]. Leveraging the correspondence between PUFs and BTFs, we adapt fundamental results from BTF theory to conveniently characterize PUFs.

All PUFs are Attainable

Recall that in our framework, the PUF parameters x ∈ R n are realizations of a random vector X ∈ R n . Under this probabilistic model a PUF becomes a randomized mapping f X such that f X (c) = sign(c • X) for any (deterministic) challenge c ∈ {±1} n . Lemma 8. For every PUF f x , we have P(f X = f x ) > 0.

In other words, every PUF f x can be reached by a realization of weights X with positive probability (even though one has P(X = x) = 0).

Proof.

By assumption all components of X are i.i.d. with symmetric density of support S containing 0. Hence the support S n of the density of X is an n-dimensional manifold containing the origin in its interior. Let x ∈ R n be fixed and let C x be the cone (scaleinvariant set) of all y ∈ R n such that f x = f y . This cone C x has apex 0 and contains the intersection of all half-spaces {y | sign(c • y) = sign(c • x)} where c ∈ {±1} n . Therefore, it is a n-dimensional manifold which intersects S n with positive volume. Hence P(f X =

f x ) = P(X ∈ C x ∩ S n ) > 0.

Chow Parameters Characterize PUFs

First introduced by Chow [START_REF] Chow | On the characterization of threshold functions[END_REF] and later studied by Winder [START_REF] Winder | Single stage threshold logic[END_REF] who gave them their name, the so-called Chow parameters uniquely define a Boolean threshold function. Their definition is especially simple for PUFs:

Definition 17 (Chow parameters). The Chow parameters p = (p 1 , . . . , p n ) ∈ Z n of a PUF f of size n is defined as p = c|f (c)=1 c (6.17)
where the vector sum is carried out componentwise.

We remark that for n ≥ 2, all Chow parameters are even integers. This is due to the fact that a sum of even number of elements ±1 must be even. More precisely,

p i mod 2 ≡ c|f (c)=1 c i mod 2 ≡ c|f (c)=1
1 mod 2 ≡ 2 n-1 mod 2 ≡ 0 mod 2. Theorem 6.3.1 (Chow's theorem [START_REF] Chow | On the characterization of threshold functions[END_REF]). Two PUFs with the same Chow parameters are identical.

For completeness, we give a new proof of Chow's theorem rewritten in our PUF framework. Such proof turns out to be very simple.

Proof. Let f x and f y be two PUFs with identical Chow parameters:

Consequence on the Max-Entropy

An upper bound on the max-entropy can be easily deduced from Chow's theorem.

Corollary 1.

There are no more than 2 n 2 PUFs of size n, i.e., the max-entropy of the PUF of size n satisfies

H 0 (n) ≤ n 2
(∀n ≥ 2). (

A more refined version, which can be rewritten as H 0 (n) ≤ (n -1) 2 + 1 for n > 1, can be found in [START_REF] Hu | Threshold Logic[END_REF]Corollary 10.2]. The proof of (6.22) is again particularly simple for PUFs.

Proof. The Chow parameters p i , i = 1 . . . n, satisfy

p i = c|f (c)=1 c i ≤ c|f (c)=1, c i =1
1 ≤ 2 n-1 (6.23) and similarly, p i ≥ -2 n-1 . Since there are 2 n-1 + 1 even integers between -2 n-1 and 2 n-1 , there can only be (2 n-1 + 1) n ≤ 2 n 2 different values taken by the Chow parameters. The conclusion follows from Chow's Theorem 6.3.1.

A lower bound on H 0 is also easily found from the representation of Definition 16, as given by the following Proposition. The corresponding bound for the number of BTFs was first established independently by Smith [START_REF] Smith | Bounds on the number of threshold functions[END_REF] and Yajima et al. [START_REF] Yajima | A lower bound of the number of threshold functions[END_REF] in the 1960s.

Proposition 1. The max-entropy satisfies

H 0 (n) >
(n -2) 2 2 (∀n ≥ 2). (6.24)

Proof. Recall from Lemma 8 that every PUF f x can be reached by a realization of weights X with positive probability. Hence it is sufficient to consider all f x for all x ∈ R n in order to lower-bound the total number of PUFs. Let f x a PUF of size n. Applying some small perturbation on x if necessary (without affecting f x ) we may always assume that all the c • x (c ∈ {±1} n ) take distinct values. Depending on how many of the 2 n-1 values of c • x are smaller/larger than 2c n x n+1 , we can construct 2 n-1 + 1 different PUF functions of size n + 1. Hence each PUF of size n gives rise to more than 2 n-1 PUFs of size n + 1. Therefore, H 0 (n + 1) > n -1 + H 0 (n).

The result follows by finite induction:

H 0 (n) > (n -1)(n -2) 2 + H 0 (2) > (n -2) 2 2 .
More recently, Zuev [START_REF] Zuev | Methods of geometry and probabilistic combinatorics in threshold logic[END_REF] has shown that, asymptotically, H 0 (n) > n 2 (1 -10 ln(n) ). Therefore, for the max-entropy, we have that H 0 (n) ∼ n 2 . As a result, instead of evaluating the probabilities of 2 2 n different PUFs, we will only have to evaluate about 2 n 2 . As apparent in the proof of Zuev [START_REF] Zuev | Methods of geometry and probabilistic combinatorics in threshold logic[END_REF]Theorem 1] although through different geometrical considerations on normal vectors of hyperplanes, we can further reduce the number of PUFs to be considered down by a factor of about 2 n n!. Section 6.4 will derive the exact compression factor using the equivalence classes on Chow parameters.

Order and Sign Stability of Chow Parameters

An important property of the Chow parameters p is that their share the same signs and relative order as the weights x. Lemma 9. Let f = f x be a PUF with weight x ∈ R n , and p ∈ Z n be the corresponding Chow parameters. Then • x i ≥ 0 =⇒ p i ≥ 0 and x i ≤ 0 =⇒ p i ≤ 0.

• x i ≤ x j =⇒ p i ≤ p j .
A similar result was shown by Chow in [START_REF] Chow | On the characterization of threshold functions[END_REF], although with another definition of Chow parameters. Again we give a simplified proof in the PUF framework.

Proof. We first prove that x i ≥ 0 =⇒ p i ≥ 0, the other case x i ≤ 0 =⇒ p i ≤ 0 being similar. Suppose that x i ≥ 0. Therefore, f (φ(c)) = 1 and φ(c) ∈ E + i . Hence, the bijection φ induces an injection from E - i to E + i . This implies that |E + i | ≥ |E - i | hence p i ≥ 0. To prove the second part, assume that x i ≤ x j for j = i. Let f : {±1} n-1 → {±1} be a PUF given by f (c ) = sign(c • x ), where c ∈ {±1} n-1 is obtained from c by dropping c i , x = x for any = j, and x j = x jx i ≥ 0. Say the Chow parameters of f is p . According to the first part of this lemma, we have p j ≥ 0. Now, expand the expression of p jp i as

p j -p i = c|f (c)=1 c j - c|f (c)=1 c i = 2 c|f (c)=1,c j =-c i c j = 2 c |f (c )=1
c j = 2p j ≥ 0.

Equivalence Classes and Chow Parameters

Since the X i are i.i.d. symmetric random variables, the joint probability distribution of the weights X = (X 1 , . . . , X n ) is invariant under permutations and sign changes. Therefore, all PUFs f x that can be obtained from one another by permuting or changing signs of their weights x 1 , x 2 , . . . , x n can be clustered together into equivalence classes of PUFs with the same probability P(f X = f x ).

We now establish several properties of these equivalence classes for PUFs, known as "self-dual" classes [START_REF] Goto | Some theorems useful in threshold logic for enumerating boolean functions[END_REF] in the context of BTFs. Zuev [START_REF] Zuev | Methods of geometry and probabilistic combinatorics in threshold logic[END_REF] had already mentioned 2 n n! elements per class in a special case. Our generalization (Theorem 6.4.2) is mentionned in a different form in [130, § 3.1.2] for calculating the total number of BTFs, yet we couldn't find formal proofs published in the literature.

We give a formal definition of the equivalence classes by the action of the group

G n = S n × {-1, +1} n (6.28)
where S n is the symmetric group of order n!. An element g = (σ, s) ∈ G n is determined by the permutation σ ∈ S n and the sign changes s ∈ {-1, +1} n .

Proposition 2. For any x = (x 1 , . . . , x n ) ∈ R n and g = (σ, s) ∈ G n define g • x :

G n × R n → R n such that (g • x) i = s i x σ(i) . ( 6
) i = (s 1 i s 2 σ 1 (i) x σ 1 (σ 2 (i)) ) i = (σ 1 • σ 2 , (s 1 i s 2 σ 1 (i) ) i ) • x = ((σ 1 , s 1 ) • (σ 2 , s 2 )) • x.
This shows that g • x defines a group action of G n on R n .

Thus we can say that the group G n acts on the PUFs of size n, the action being defined as

g • f x = f g•x .
(6.31)

In keeping with Lemma 9, we now show that the group action is carried over to Chow parameters: Theorem 6.4.1. Let f x a PUF of Chow parameters p, and let g ∈ G n . The Chow parameters of f g•x is g • p.

Proof. Let g = (σ, s) ∈ G n . For any challenge c, we have that f x (g -1 • c) = f g•x (c). Thus,

c|fg•x(c)=1 c i = c|fx(g -1 •c)=1 c i = c|fx(c)=1 (g • c) i = c|fx(c)=1 s i c σ(i) = s i p σ(i) = (g • p) i .
Changing the signs of the weights or permuting them is reflected by the same operation on the Chow parameters. This allows us to compute the size of the equivalence classes: where Stab(f ) = {g ∈ G n | g • f = f } is the stabilizer of f . The size of the orbit of f can therefore be deduced from the size of its stabilizer. Now the latter can be easily computed: Let g = (σ, s) ∈ G n such that g • f = f . Since g • p = p, we have σ(i) = j ⇐⇒ p i = s i • p j and s i = sign(p i ) • sign(p σ(i) ) except when p i = 0, in which case s i is unconstrained. The number of such g is exactly 2 mp(0) k∈N m p (k)!.

Monte-Carlo Algorithm

As seen in the introduction to the previous section, all PUFs in one equivalence class have the same probability. It follows that the probability of any particular PUF can be deduced from the probability of the class to which it belongs. Therefore, to determine the various entropies, it suffices to find a method that estimates the probabilities of the various equivalence classes.

In this section, we propose an algorithm that exploits a definition of a canonical PUF in any equivalence class in such a way that for given any PUF, it is trivial to determine the corresponding canonical PUF. As expected, only about 2 n 2 /2 n n! probabilities need to be estimated, instead of approximatively 2 n 2 .

Definition 18 (Canonical PUF). A canonical PUF of n variables is a PUF whose Chow parameters satisfy

p 1 ≥ p 2 ≥ • • • ≥ p n ≥ 0. (6.34)
The canonical form of a PUF f is the canonical PUF belonging to the same class, i.e., f = g • f where g ∈ G n is such that f is canonical.

This notion was first introduced by Winder [START_REF] Winder | Single stage threshold logic[END_REF] and is related to the concept of "prime" functions independently studied by Chow [START_REF] Chow | On the characterization of threshold functions[END_REF]. In other words, the Shannon entropy of the PUF distribution is simply the sum of the entropy of the equivalence classes and the average of their logarithmic size. The latter term can be estimated using the unbiased empirical mean, where a confidence interval can be determined using Student's t-distribution [START_REF] Student | The probable error of a mean[END_REF]. The former term, however, is an entropy, for which no unbiased estimator exists [START_REF] Paninski | Estimation of entropy and mutual information[END_REF]. The NSB estimator [START_REF] Nemenman | Entropy and inference, revisited[END_REF] has a reduced bias and a low variance. However, because we generated much more PUFs than equivalence classes (by a factor of at least 100000), the plug-in estimator, based on the empirical frequency estimates, performs quite well: Its bias can be upper bounded as described in [START_REF] Paninski | Estimation of entropy and mutual information[END_REF] and was found to be less than 0.01 bit. The results are summarized in Table 6.5.

Estimating the Collision Entropy H 2

The collision entropy was estimated using an unbiased estimator adapted from [ is an unbiased estimator for the power-sum f ∈Fn P(f ) 2 . As can be also checked, the variance of this estimator admits the same upper bound as the one described in [146, § 1.4.2]. This allows us to determine confidence intervals for the collision entropy as shown in Table 6.6.

[f ] = N [f ] •(N [f ] -1). We can compute E f ∈Fn/Gn N 2 [f ] |[f ]|N 2 = f ∈Fn/Gn E N 2 [f ] N 2 1 |[f ]| (6.40)

Estimating the Min-Entropy H ∞

In order to determine the min-entropy of the PUF distribution, one needs to estimate the probability of the most likely PUF. Our experiments, as well as those of Delvaux et al. [START_REF] Delvaux | Upper bounds on the min-entropy of RO sum, arbiter, feed-forward arbiter, and S-ArbRO PUFs[END_REF], strongly suggest that for a Gaussian distribution of the weights, the most likely PUFs are the 2n PUFs corresponding to the Boolean functions c i and c i , i = 1...n. The maximum likelihood estimator of that probability is simply the sample frequency, which is an unbiased estimator. A confidence interval for this estimator can be obtained [START_REF] Wilson | Probable inference, the law of succession, and statistical inference[END_REF], which yields a confidence interval for the min-entropy

H ∞ .
Because we have already determined that there are exactly 2n PUFs in the equivalence class of the most likely PUF, we only need to estimate a confidence interval on the sample frequency of the equivalence class. Once such an interval was obtained, for instance [p -, p + ], then the confidence interval for the min-entropy is given by [-log 2 (p + ) + log 2 (2n), -log 2 (p -) + log 2 (2n)].

The confidence intervals of the min-entropy are presented in Table 6 The results of the simulation, up to n = 10, are presented in Figure 6.2. The results show that the Shannon entropy is close to the max-entropy, which as seen in Section 6.3 is asymptotically equivalent to n 2 as n increases.

Conclusions and Perspectives

While it had been previously shown [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF] that the entropy of the loop-PUF of n elements could exceed n, the exact values were only known for very small values of n. Making the link with BTF theory using Chow parameters, we have extended these results to provide accurate approximations up to n = 10. Our results suggest that the entropy of the loop-PUF might be quadratic in n: This would be a very positive result for circuit designers, since it implies that the PUF has a very good resistance to machine learning attacks. However, because the min-entropy and collision entropy are much smaller (on the order of n) the resistance to cloning may not be as high as expected.

Two interesting theoretical aspects of the PUF entropy are still open: First, to what extent does the entropy of the PUF stay close to the max-entropy for larger values of n? Second, is it possible to obtain a quasi-quadratic entropy in n when choosing a small subset of all 2 n possible challenges? The latter point is of great practical interest since it would reduce the time required to obtain the PUF identifier while maintaining a high resistance to machine learning attacks.

For values of n larger than 10, our method seems to become too costly in space and time to produce accurate estimates of the PUF probability distributions under reasonable conditions. One could perhaps have recourse to entropy estimation methods that dispense with learning the distribution itself, such as the NSB estimation [START_REF] Nemenman | Entropy and inference, revisited[END_REF]. This could be used to check the predicted trend of the PUF entropy for increasing n. La deuxi ème moiti é de la th èse est consacr ée aux "physically unclonable functions" (PUFs). De ces circuits, on peut extraire des identifiants impr édictibles mais stables, gr âce à de petites variations incontr ôlables dans les propri ét és des semiconducteurs. Des garanties th éoriques pour deux caract éristiques fondamentales de certains PUFs sont pr ésent ées dans cette th èse: la stabilit é de l'identifiant, perturb ée par des bruits de mesure, et l'entropie disponible, d ériv ée du mod èle math ématique du PUF. Title : Formal methods for the analysis of cache-timing leaks and key generation in cryptographic implementations Keywords : Computer science, security, side-cannel, cache, PUF Abstract : Cryptography is ubiquitous in today's interconnected world, protecting our communications, securing our payment systems. While the cryptographic algorithms are generally well understood, their implementations have been less subject to formal verification. This has lead to successful breakages of implementions of most modern primitives: AES, RSA, ECDSA. . . In general, cryptographic implementations would benefit from stronger theoretical guarantees. In this thesis, we apply this line of reasoning to two different topics, one in software security, and the other in hardware security. The first half of this thesis explores cache-timing side channel vulnerabilities that arise when the time taken by a cryptographic operation, or the cache state after this operation, depends on sensitive information. This occurs if any branching operation depends on secret information such as a private key, or if memory is accessed at an address that depends on that secret. We developed a tool to detect and prevent such leaks in programs written in the C programming language. This tool is applied on most candidates of NIST's post-quantum standardization process in order to find cache-timing leakages. This process aims at replacing traditional cryptographic primitives such as RSA or ECDSA, broken by quantum computers, by safer alternatives. The development of such primitives is on the way, but the security of their implementations has received less scrutiny. We show how our tool is able to detect potential cache-timing leaks in a majority of the implementations and what mitigations are possible. The subject of the second half of this thesis are the socalled physically unclonable functions, or PUFs: elementary circuits from which stable but unpredictable identifiers can be extracted. They rely on small, uncontrollable changes in the semiconductor properties to exhibit unpredictable behavior. Theoretical guarantees concerning two fundamental characteristics of PUFs are derived in this thesis, for a large family of PUFs: the stability of the identifier, related to circuit noise, and the exploitable entropy, derived from the mathematical PUF model.

Institut

Figure 1 :

 1 Figure 1: Organisation du cache (exemple)

Figure 2 :

 2 Figure 2: Évolution du taux d'erreur moyen en fonction du rapport signal sur bruit

1 )

 1 où erf et erfc représentent respectivement la fonction d'erreur et la fonction d'erreur xvii

Figure 3 : 1 2 h 2 (1+x 2 ) 1 +

 311 Figure 3: Compromis entropie-fiabilité après filtrage par seuil

  déterminer précisément la variance des xviii

Shannon entropy H 1

 1 Collision entropy H 2 Min-entropy H 1 Min-entropy upper-bound

Figure 5 :

 5 Figure 5: Estimation des entropies des PUFs pour différentes valeurs de n

Figure 1 . 1 :

 11 Figure 1.1: Cache architecture on a modern hyper-treaded quadcore processor

Figure 1 . 3 :Figure 1 . 4 :Figure 1 . 5 :

 131415 Figure 1.3: Victim and attacker process access data at different cache lines.

Figure 2 . 1 :

 21 Figure 2.1: Comparison between source (a) and compiled (b) code (gcc with -02 optimizations)

Listing 2. 1 :

 1 C code with variables int foo(int a, int b) { int c = a + b; return c; } For instance, the code of Listing 2.1 defines three 4 variables: a, b, c and \RET. Each variable also defines a memory location with the same name.

Definition 5 (

 5 Pointer indirection). The pointer indirection level of a variable is the length of the pointer chain until the referenced value is attained. As such, indir(varname) = 0, indir(&varname) = 1, indir(&&varname) = 2, etc. Pointer dereferencing and the address of operation change the indirection level of a variable. Therefore, CHAPTER 2. STANALYZER • &(varname) = &varname • *(&varname) = varname

Listing 2. 4 :

 4 Indirect dependency flow example int foo (int a) { int b = 1; if (a > 0) b = -1; return b; }

Figure 2

 2 Figure 2.2: Example of a control flow graph with influence regions In the more complex example represented by Figure 2.2, two regions are highlighted.For the region 2, any variable modified during the execution of either BB2 or BB3 depends on the value of b at the beginning of BB4. Similarly, for region 1, any variable modified during the execution of either BB1, BB2, BB3 or BB4 depends on the value of a before the next basic block is executed.It is not immediately obvious why tracking indirect dependencies in order to perform leakage analysis is necessary. Indeed, keeping track of non-sensitive indirect dependencies is not useful, and when indirect dependencies are sensitive, the analyzed program cannot be constant-time. This would imply that the control flow depends on sensitive values, which contradicts the constant-time requirements. However, there are two reasons why it still might be be useful to consider indirect dependencies.First, the aim of our program is to determine all constant-time violations. When indirect dependencies are not considered, then some variables might falsely be considered non-sensitive, and leakages caused by them are missed. Second, some branching operations are compiled into constant-time code by modern compilers, and thus do not necessarily result in a constant-time violation (see Figure2.1). Our tool allows the user to flag branches as being safe, i.e. do not result in a constant-time violation. In this case,

2. 3 .Figure 2 . 3 :

 323 Figure 2.3: AST of the program described in Listing 2.5

  Figure 2.5: Example of C code with tagged variable

  lim n→∞ ψ n (G , L ; {cond; inst; step}) where (G , L ) = φ(G, L; init) Overestimating Dependencies The fixed point calculation might lead to false positive in some cases. Consider for instance the C code in Figure 2.6. Depending on the parity of the variable c, the function bar returns either a or b. Because the algorithm cannot determine the parity of c, the analysis will conclude that the return value of bar depends on a and b (as well as, of course, c).

Figure 2 . 6 :

 26 Figure 2.6: Example C code with variable swapping

9 FFigure 2 . 7 :Figure 2 . 8 :

 92728 Figure 2.7: Output from STAnalyzer on mbedtls' Blowfish implementation int bar(void) { int values[] = {1,2,3}; int j; #pragma STA secret j values[1] = j; for(int i = 0; i < 3; i++) { if (i%2 == 0){ // perform some operation // that leaks values[i] } } }

Figure 3 . 1 :

 31 Figure 3.1: Total number of potential vulnerabilities found for each analyzed candidate

  f8FELT f8multiply ( f8FELT a , f8FELT b ) { i f ( a == 0 | | b == 0 ) r e t u r n 0 ; r e t u r n f8antilog ( ( f8log ( a ) + f8log ( b ) ) % f8units ) ; } uint8_t f8log ( f8FELT a ) { s t a t i c c o n s t uint8_t f8LogTable [ 2 5 6 ] = { . . . } ; r e t u r n f8LogTable [ a ] ; } uint8_t f8antilog ( uint8_t a ) { s t a t i c c o n s t uint8_t f8AntiLogTable [ 2 5 6 ] = { . . . } ; r e t u r n f8AntiLogTable [ a ] ; } Listing 3.2: Implementation of multiplication inF 2 8 in LUOV uint64_t clmul ( uint64_t a , uint64_t b ) { uint64_t table [ 1 6 ] = { 0 } ; table [ 1 ] = a ; // . . .uint64_tb_lower = b & 0 x0f0f0f0f0f0f ; uint64_t b_upper = ( b >> 4 ) & 0 x0f0f0f0f0f0f ; u n s i g n e d c h a r * b_lower_nibbles = ( u n s i g n e d c h a r * ) &b_lower ; u n s i g n e d c h a r * b_upper_nibbles = ( u n s i g n e d c h a r * ) &b_upper ; out_upper = table [ b_upper_nibbles [ 3 ] ] ; out_lower = table [ b_lower_nibbles [ 3 ] ] ; // . . . out = ( out_upper << 4 ) ^out_lower ; r e t u r n out ; } Listing 3.3: Carryless multiplication in LUOV

Listing 3 . 9 :

 39 Uniform polynomial generation

  f o r ( i = 0 ; i < ROUNDS ; i++) { b = ( h1 [ ( i >> 3 ) ] >> ( i & 7 ) ) & 1 ; i f ( b == 0 ) { gf31_npack ( sm ,r0+i * N , N ) ; } e l s e i f ( b == 1 ) { gf31_npack ( sm , r1+i * N , N ) ; } // . . . } Listing 3.10: Commitment selection While the value of h1 (ch 2 in [83, Fig.

  f o r ( i n t j = 0 ; j < 8 ; j += 2 ) { uint8_t bitPair = ( ( byte >> ( 6 -j ) ) & 0 x03 ) ; i f ( bitPair < 3 ) { setChallenge ( challengeBits , round++, bitPair ) ; i f ( round == params->numMPCRounds ) { g o t o done ; } } } Listing 3.14: Ternary output generation

#

  d e f i n e b i t _ v a l u e ( v , i ) ( ( ( v ) [ ( i )>>LOG2 ] & ( 1ULL<<(( i ) & MOD) ) ) >> ( ( i ) & ← MOD) ) // . . . f o r ( i=0; i<NTS_KEM_PARAM_A ; i++) { a = p [ i ] ; bit_value = bit_value ( e_prime_ptr , a ) ; bit_set_value ( e_ptr , i , bit_value ) ; / * Permute e_prime * / } f o r ( ; i<NTS_KEM_PARAM_K ; i++) { a = p [ i ] ; bit_value = bit_value ( e_prime_ptr , a ) ; bit_set_value ( e_ptr , i , bit_value ) ; / * Permute e_prime * / bit_toggle_value ( ( packed_t * ) k_e , i-NTS_KEM_PARAM_A , bit_value ) ; / * Step← 8 : r e c o v e r i n g k_e * / } f o r ( ; i<NTS_KEM_PARAM_N ; i++) { a = p [ i ] ; bit_value = bit_value ( e_prime_ptr , a ) ; bit_set_value ( e_ptr , i , bit_value ) ; / * Permute e_prime * / } Listing 3.15: NTSKEM error decoding

  s t a t i c inline u n s i g n e d i n t gf_mul ( u n s i g n e d i n t a , u n s i g n e d i n t b ) { u n s i g n e d i n t tmp , mask ; tmp=a_pow_tab [ mod_s ( a_log_tab [ a]+ a_log_tab [ b ] ) ] ; mask=(a && b ) ? 0 xffffffff : 0 x0 ; r e t u r n tmp&mask ; } Listing 3.16: LAC finite field multiplication

  i f ( tmp > elp->deg ) { //memcpy c a u s e 70 c y c l e s gap gf_poly_copy(&pelp , &elp_copy , i ) ; elp->deg = tmp ; } e l s e { // j u s t f o r c o n s t a n t time gf_poly_copy(&elp_copy , elp , i ) ; tmp = elp->deg ; } Listing 3.18: LAC branch balancing

  i f ( memcmp ( c , c_v , CIPHER_LEN ) !=0) { // k=hash ( hash ( sk ) | c ) hash ( ( u n s i g n e d c h a r * ) sk , SK_LEN , buf ) ; hash ( buf , MESSAGE_LEN+CIPHER_LEN , k ) ; } Listing 3.19: LAC decapsulation failure check

Figure 4 . 1 :

 41 Figure 4.1: An oscillating chain of 5 inverters

Figure 4 Figure 4 . 2 :

 442 Figure 4.2: Ring Oscillator PUF RO PUF output: We suppose here that the RO PUF is used to output n = N/2 independent bits. Let d i denote the delay of the ring oscillator i. The RO PUF output is then equal to b = (sign(d 2i+1d 2i+2 )) i∈[0,n-1] .

Figure 4 . 4 :

 44 Figure 4.4: RO-sum PUF

n 77 J number of circuits j index of a circuit

 77 number of delay elements in the circuit i index of a delay element t index of a measurement T total number of measurements M total number of challenges m index of a challenge 5.2. DELAY PUF MODEL

Figure 5 .

 5 Figure 5.1 illustrates the distribution of ∆ C and the noise distribution around the value δ C associated to the challenge C. In this example, an error occurs when δ C + Z is negative.

  δ

Figure 5 . 1 :

 51 Figure 5.1: pdf of ∆ and noise for a given challenge C. |δ C |/σ value 0 1 2 3 4 BER 0.5 1.6 10 -1 2.3 10 -2 1.3 10 -3 3.2 10 -5 |δ C |/σ value 5 6 7 8 9 BER2.9 10 -7 9.9 10 -10 1.3 10 -12 6.2 10 -16 1.1 10 -19

Figure 5 . 2 :Figure 5 . 3 :

 5253 Figure 5.2: Polar representation of X and Y. the proportion of the hatched area on Fig. 5.2. This proportion is simply 2θ/2π, where tan(θ) = 1/ √ SNR by the geometric definition of the tan function. Thus, we simply have that BER = 1 π arctan( 1 √ SNR ). The expected BER is represented as a function of the SNR in Fig. 5.3. Although the expected BER (5.3.1) vanishes with the noise: lim SNR→+∞ BER = 0, it is easily seen that the expected BER remains quite high, > 10 -3 , even for large values of SNR (several thousands).

Figure 5 . 4 :

 54 Figure 5.4: Attacking the helper data by using unreliable bits as pivot

Figure 5 . 5 :

 55 Figure 5.5: Unreliable area vs distributions of ∆ C and the noise Z.

Figure 5 . 6 :

 56 Figure 5.6: Remaining average entropy after filtering unreliable bits as a function of the BER to reach.

Figure 5 . 7 :Figure 5 . 8 :

 5758 Figure 5.7: Metric M0: Bit extraction according to a and the pdf of ∆

Figure 5 . 9 :

 59 Figure 5.9: Metric M2: Bit extraction according to -T 2 , T 1 and the pdf of ∆ C

  dx, the choice of the metric is given by Alg. 5.4.1 and summarized in Fig. 5.10. Algorithm 5.4.1 Proposed PUF enrollment Input: Threshold a, related to the expected reliability Output: Vector of metric choices

Figure 5 . 10 :

 510 Figure 5.10: Choice of metric and extracted bit value.

1

  That is, for any BER estimate b, the confidence interval is included in the interval [b -0.01b, b + 0.01b].

Figure 5 . 11 :

 511 Figure 5.11: Average BER with and without two-metric helper data

  oscillation periods of the reference clock at f ref = 100 MHz. This allows us to simulate: • 49 Loop PUFs with 64 delay elements, or • 64 RO-PUFs with 24 delay elements, or • 64 RO sum PUFs with 48 delay elements.

Figure 5 . 12 :

 512 Figure 5.12: Experimental validation of the SNR and remaining entropy.

Figure 5 . 13 :

 513 Figure 5.13: Distribution of temperature dependency coefficients (for 49 distinct oscillators, as well as 64 challenges of the same oscillator, for three different oscillators)

Figure 5 . 14 :

 514 Figure 5.14: Average BER when Σ is known or unknown at measurement stage

Figure 5 . 15 :

 515 Figure 5.15: Rejection probability as a function of PUF error rate (n = 10 7 , t = 120)

Definition 12 (

 12 Physically unclonable function (PUF)). Let C be an (n, M ) challenge code. Let x = (x 1 , . . . , x n ) ∈ R n such that the scalar product c • x = 0 for all codewords c ∈ C. Then the physically unclonable function (PUF) with parameter x is the function f

Figure 6 . 1 :

 61 Figure 6.1: Distribution of delays obtained via circuit simulation

. 12 )

 12 Let c 3 be a third challenge vector and Y 3 = c 3 • X, and denote the correlation coefficients between Y i and Y j byρ i,j = E[Y i Y j ] n . Then

111 -

 111 1 1 -): Probability per sign vector Sign vectors 11 192 +++++,++--+,+-+-+,+--+-,++-+-,+-+++,+-++-,+---+,+-++++-+,++--++,++----, +-+-+-,+-+--+,+--+++,+--+--1 32 +++-++,+++-+-,+-++++,+-++-+ 1 64 ++-+++,++-++-,++-+-+,++-+--, +---++,+---+-,+----+,+-----,+-+-+--,+--++++,+-+-+++, +--+--+,++----+,++++++-,++++-++, +------,++--+--,+---+-+,+--+-+-, ++--+++,+---++-,+-+--+-,+----++ 1 96 +---+++,+-----+,+----+-,+---+--1 64 ++-+-++,+-++-++,+++-+-+,+++-++-, ++-++-+,+-++++-,+-++-+-,++-+--+, +++-+++,+-+++++,+++-+--,++-++++ 6.3. THE CHOW PARAMETERS OF PUFS Additional codeword ( -1 1 1

18 )

 18 Simplifying this expression by c|fx(c)=1, fy(c)=1c, we obtainc|fx(c)=1, fy(c)=-1 c = c|fx(c)=-1, fy(c)=1c,(6.19)

6. 3 .

 3 THE CHOW PARAMETERS OF PUFS 113 which is equivalent to c|fx(c) =fy(c) f x (c)c = 0. (6.20) Taking the scalar product with x, we get c|fx(c) =fy(c) f x (c)c • x = c|fx(c) =fy(c) |c • x| = 0 (6.21) which implies c•x = 0 whenever f x (c) = f y (c). Now we assumed that c • x is never zero by Def. 16. Thus f x = f y .

114 CHAPTER 6 .

 6 ENTROPY ESTIMATION OF PUFS VIA CHOW PARAMETERNow let x n+1 ∈ R be such that 2x n+1 is different from all the c • x, and definex = (x 1 , • • • , x n-1 , x nx n+1 , x n+1). For any challenge c = (c 1 , . . . , c n , c n+1 ), we havef x (c ) =    f x (c 1 , . . . , c n ) if c n = c n+1 sign( n i=1 c i x i -2c n x n+1 ) otherwise. (6.25)

  Let E + i (resp. E - i ) be the set {c | f (c) = 1, c i = 1} (resp. {c | f (c) = 1, c i = -1}). By definition, p i = c|f (c)=1 c i = |E + i | -|E - i |. (6.26)We show the existence of an injective mapping from E - i to E + i . Consider the one-to-one mapping φ : {±1} n → {±1} n defined byφ(c) j =    c j , j = i -c j , j = i (6.27) 6.4. EQUIVALENCE CLASSES AND CHOW PARAMETERS 115 For any c ∈ E - i , c i = -1, φ(c) i = +1 and n j=1 φ(c) j x j = n j =i c j x j + x i

Theorem 6 . 4 . 2 . 1 . 117 Proof.

 6421117 Let f be a PUF with Chow parameters p. Let m p (k) be the number of Chow parameters equal to k or -k ∈ Z, and let Orb(f ) = {g • f | g ∈ G n } the orbit of f by G n , that is, the equivalence class containing f . Then | Orb(f )| = 2 n n! 2 mp(0) k∈N m p (k)!-By applying the well-known orbit-stabilizer theorem (see for instance[141, p. 89]), we have| Orb(f )| = |G n | | Stab(f )| = |{±1} n | × |S n | | Stab(f

Proposition 3 (Proposition 4 .

 34 Unicity of the canonical PUF). Two canonical PUFs in the same class are equal.Proof. Since f and f are in the same equivalence class, their Chow parameters are identical up to sign changes and order. Since both are canonical, the signs and order are fixed. Their Chow parameters are thus identical and f = f . Let x = (x 1 , . . . , x n ) be a weight sequence of a PUF f = f x , and letg ∈ G n such that g • x = (x 1 , . . . x n ) satisfies x 1 ≥ x 2 ≥ . . . ≥ x n ≥ 0. (6.35)Then g • f is the canonical form of the PUF f .

For

  any PUF f , let [f ] denote the equivalence class of f with cardinality |[f ]|, P(f ) its probability, F n the set of all PUFs and F n /G n the quotient group induced by the action of the group G n . Then, letting P([f ]) = f ∈[f ] P(f ), one has H 1 (n) =f ]) log(P([f ])) + E[log(|[f X ]|)]. (6.39)

N 2

 2 ] = P([f ]) 2 from [146, § 2.2]. It follows that

122 CHAPTER 6 .

 6 Figure 6.2: Entropy estimates for n ≤ 10. The upper bound of the min-entropy (dashed line) is taken from [1].

  Titre : M éthodes formelles pour l'analyse de canaux cach és logiciels et la g én ération de cl és dans les impl émentations cryptographiques Mots cl és : Informatique, s écurit é, canaux auxilliaires, cache, PUF R ésum é : La cryptographie est omnipr ésente dans notre monde actuel hyperconnect é, prot égeant nos communications, s écurisant nos moyens de paiement. Alors que les algorithmes cryptographiques sont en g én éral bien compris, leurs impl émentations ont ét é v érifi ées avec moins d'insistance. Cela a men é à des attaques contre les impl émentations de la plupart des primitives modernes: AES, RSA, ECDSA. . . En bref, la s écurit é des impl émentations pourrait fortement b én éficier de meilleurs garanties th éoriques. Dans cette th èse, nous appliquons ce raisonnement à deux sujets diff érents, l'un portant sur la s écurit é logicielle, l'autre sur la s écurit é mat érielle.oe La premi ère moiti é de la th èse explore les canaux auxiliaires logiciels dits "cache-timing". Ce genre de vuln érabilit és apparaît lorsque la dur ée d'une op ération cryptographique, ou l' état du cache apr ès cette op ération, d épend d'une information sensible. C'est le cas lorsqu'une op ération de branchement d épend d'une information secr ète comme une cl é priv ée, ou si la m émoire est acc éd ée à une adresse qui d épend de ce secret.Nous avons d évelopp é un outil pour d étecter et pr évenir ce genre de fuites dans des programmes écrits en C, et l'avons appliqu é à la plupart des candidats du processus de standardisation de cryptographie post-quantique initi é par le NIST. Ce processus vise à remplacer des primitives cryptographiques traditionnelles comme RSA ou ECDSA, vuln érables aux ordinateurs quantiques, par des alternatives s ûres. Ces nouveaux algorithmes étant relativement r écents, leurs impl émentations ont ét é moins scrut ées. Dans cette th èse, nous appliquons notre outil à la plupart de ces algorithmes pour d étecter des fuites d'information potentielles, et expliquons comment les éviter.

  Polytechnique de Paris 91120 Palaiseau, France

Table 2 .

 2 1: Notation styles used in the remainder of this paper

	Notation	Description
	int x = y;

Table 2

 2

.2: State of the memory locations for the code in Listing 2.2 Definition 4 (Pointer). A pointer is a variable referencing one or more other memory locations. If the C code defines a pointer named varname, we will denote the variable by &varname if it is a pointer on an integral type, by &&varname if it is a pointer on a pointer on an integral type, etc. The referenced value will in any case be denoted by varname.

Table 2 .

 2 Definition 8 (Dependency graph operations). Given two dependency graphs G 1 and G 2 , the union of these two graphs is denoted by G 1 ∪ G 2 . The vertex set (resp. edge set) of this graph is equal to the union of the vertex sets (resp. edge sets) of G 1 and G 2 . Given a variable varname and a set of variables and values E, we denote by {varname → E} the graph with vertices E ∪ {varname} and edges {(varname, e)|e ∈ E}. Furthermore, given a graph G, we denote by [varname → E] G the graph obtained from G after removing all the edges starting from varname and adding the edges {(varname, e)|e ∈ E}.

3 provides an example of such a mapping that can be directly encoded into a dependency graph. Definition 6 (Dependency graph). The dependency graph G is a directed graph, where the vertices are memory locations (variables) and abstract values. Edges in G are only possible from memory locations to values and to other memory locations (or equivalently, there are no outgoing edges from values, only from memory locations). An edge between a memory location and an abstract value signifies that the data stored at that memory location might depend on the abstract value, and an edge from a memory location A to B means that A might contain the address of the memory location B. Definition 7 (Dependency graph notations). For a variable varname, we denote by G(varname) the neighbor vertices (memory locations and values) of varname in G. G M (varname) (resp. G V (varname)) represents the set of memory locations (resp. the set of values) among all the neighbors of varname in G. These notations are naturally extended for a set of variables S, G(S) = varnanme∈S G(varname), and a similar extension holds for G M and G V .

  .4.

	Table 2.4: Notation used in this section
	Notation	Description
	G L expr expr R	Dependency graph Set of leakages Variables that expr depends on

  varname). The example of computing dep(G, k) is visualized in Figure 2.4, where the set nodesToExplore is colored in gray. Visualization of Algorithm 2.3.1 applied to the dependency graph in Table 2.3 2.3. DESCRIPTION OF THE ALGORITHM

	Algorithm 2.3.1 Computing the dependency set for a given variable
	procedure Dependencies(G, varname) declVarname ← varname with indirection level corresponding to that of its declaration indirLevelDifference ← indir(declVarname) -indir(varname) nodesToExplore ← {declVarname} newNodesToExplore ← ∅ if indirLevelDifference < 0 then return varname end if for i = 1 to indirLevelDifference do for node ∈ nodesToExplore do newNodesToExplore ← newNodesToExplore ∪ G(node) end for nodesToExplore ← newNodesToExplore newNodesToExplore ← ∅ end for return {G(node)|node ∈ nodesToExplore} end procedure
	Initialization	i = 1	i = 2		Algorithm Output
	&&k	&&k	&&k			&&k
		&k	&k			&k
		i	j	k	i	j	k
					b 0	a 0
	Figure 2.4:

Table 2 .

 2

	5: Variable dependencies for various expressions
	expr	expr
	literal var expr 1 op 2 expr 2 op 1 expr var = expr var op 2 = expr &expr * expr var[expr]	∅ {var} expr 1 ∪ expr 2 expr expr expr ∪ {var} {&var | var ∈ expr } { * var | var ∈ expr } { * var} ∪ * expr

Table 2 .

 2 6: Dependency and leakage semantics for simple instructions

	Instruction to analyze	Result

Table 2 .

 2

7: Dependency and leakage semantics for simple instructions Instruction to analyze Result #pragma STA secret var φ G G ∪ {var → \SECRET} φ L L Table 2.8: Dependency graph at the end of function foo2

Variable (memory location) Values Pointed memory locations

Table 2 .

 2 11: Dependency and leakage semantics for loops

	Instruction	Result

while (expr) { inst } lim n→∞ ψ n (G, L; {expr; inst}) do { inst } while (expr); lim n→∞ ψ n (φ G (G, L; inst), L; {expr; inst}) for (init; cond; step) {inst}

Table 2 .

 2 12: Dependency and leakage semantics for function calls

	Expression	Result

Table 2 .

 2 and were obtained on a 2.4 GHz Intel i5 processor.

	Implementation Execution time (s)
	curve25519-donna 5.58 nacl_ed25519 7.39 nacl_salsa_20 1.05 nacl_sha512 3.44 mee-cbc 7.03 mbedtls_aes 46.50 mbedtls_sha256 2.87 mbedtls_blowfish 1.16 mbedtls_sha512 2.39 mbedtls_des 12.42 rlwe_sample 4.40

[START_REF] Yarom | Recovering OpenSSL ECDSA nonces using the FLUSH+RELOAD cache side-channel attack[END_REF]

: Verification times for cryptographic algorithms

Table 3 .

 3

	Vulnerability Type	Occurrences
	Gaussian sampling Other sampling Use of GMP Unsecure GF operations 12 3 13 4 Other leakage sources 31

1: Breakdown of vulnerabilities per type.

Table 3

 3

	.2: NIST PQC Round 2 Submissions (KEM Algorithms)
	Algorithm Name	Reference Implementation Implementation Optimized	Additional Notes
	BIKE ClassicMcEliece CRYSTALS-KYBER FrodoKEM HQC LAC LEDAcrypt NewHope NTRU NTRU Prime NTS-KEM ROLLO Round5 RQC SABER SIKE Three Bears	? ? ? ?	? ? ? ?	Uses C11 features. Uses C++. Only one leakage found. Uses C++. Uses C++.
	Implementation verified to be constant time. Constant-time violations found. Implementation assumed to be constant-time. ? Not analyzed.

Table 3 .

 3 3: NIST PQC Round 2 Submissions (Signature Algorithms)

	Algorithm Name	Reference Implementation Implementation Optimized	Additional Notes
	CRYSTALS-DILITHIUM FALCON GeMSS LUOV MQDSS Picnic qTESLA Rainbow SPHINCS+	?	?	Uses C++. AVX2 Implementation is constant-time. Assuming AES-NI is available.
	Implementation verified to be constant time. Constant-time violations found. Implementation assumed to be constant-time. ? Not analyzed.

Table 6 .

 6 1: Summary of Notations.

	Notation Explanation n number of delay elements in a PUF X i Gaussian random variable representing the delay difference of the i-th delay element

Table 6 .

 6

		2: Distribution for n = 3
	Size of equivalence class Probability per element
	8 6	1 8 -3 arcsin 1 arcsin 1 3 4π 3 π
	Therefore,

Table 6 .

 6 3: Exact entropies for n ≤ 4

		1 24		8
		1 192		64
		1 96		32
	In summary for n = 1, 2, 3, 4:
	n	1 2	3	4
	H(n) 1 2 3.6655... 6.2516... H 0 (n) 1 2 3.8073... 6.7004... H 2 (n) 1 2 3.54615... 5.71049...
	H

∞ (n) 1 2 3.20858... 4.58496...

  .[START_REF] Eldib | Synthesis of masking countermeasures against side channel attacks[END_REF] This defines a group action of G n on R n , where the inner product in G n is defined by(σ 1 , s 1 ) • (σ 2 , s 2 ) = (σ 1 • σ 2 , (s 1 i s 2 σ 1 (i) ) i ). (6.30)Proof. G n is clearly a group with identity e = (id, (1,• • • , 1)). For any (σ 1 , s 1 ), (σ 2 , s 2 ) ∈ G n and x ∈ R n , (σ 1 , s 1 ) • ((σ 2 , s 2 ) • x) = (σ 1 , s 1 ) • (s 2 i x σ 2 (i)

Table 6 .

 6 4: Exact values of H 0

	n	# PUFs	H 0 (bits)
	1 2 3 4 5 6 7 8 9 10 144130531453121108 57.0001. . . 2 1 4 2 14 3.8074. . . 104 6.7004. . . 1882 10.8781. . . 94572 16.5291. . . 15028134 23.8411. . . 8378070864 32.9640. . . 17561539552946 43.9974. . .
	6.6

.2 Estimating the Shannon Entropy H 1

  146, § 1.4.2]. Let N [f ] be the number of PUF samples that belong to the equivalence class of [f ] 120 CHAPTER 6. ENTROPY ESTIMATION OF PUFS VIA CHOW PARAMETER

	Table (exact values up to n = 4). 6.5: Confidence	intervals	at	the	95%	level	for	H 1
	n PUF Sample size		H 1 (bits)
	1 2 3 4 5 6 7 8 9 10	----10 10 10 10 10 10 2 • 10 10 2 • 10 10 3 • 10 12	1 2 3.6655. . . 6.2516. . . 10.0134 -10.0156 15.1903 -15.1925 21.9856 -21.9879 30.5628 -30.5645 41.0367 -41.0384 53.4737 -53.4740
						2

among a number of Poisson-distributed PUFs with parameter N , and N

  .7.

	Table (exact values up to n = 4) 6.7: Confidence	intervals	at	the	95%	level	for	H ∞
	n PUF Sample size 1 -2 -3 -4 -5 10 10 6 10 10 7 10 10 8 2 • 10 10 9 2 • 10 10 10 3 • 10 12	H ∞ (bits) 1 2 3.2086. . . 4.5850. . . 6.1006 -6.1008 7.7352 -7.7354 9.4731 -9.4735 11.3020 -11.3024 13.2123 -13.2132 15.1899 -15.1901

For 64-bit operating systems. In practice, only

[START_REF] Aldaya | Port contention for fun and profit[END_REF] bits are addressable on most common processors.

or a set of n memory addresses that map to the n possible cache lines of the victim memory address in case of a cache with n-way associativity

12 = log 2 (4096)

https://github.com/agl/ctgrind/

https://w1.fi/security/2019-1/ and https://w1.fi/security/2019-2/3.1. COLLECTING GROUND TRUTH: REDISCOVERY OF KNOWN CVES

SPHINCS

The SPHINCS-Haraka implementations ship with their own AES implementation which leaks the S-BOX accesses, but a real deployment is very likely to use a protected implementation or the AES-NI instruction set. Furthermore, warnings were reported for the Haraka variant, but this is due to a limitation in our tool: the implementation of this hash function represents the internal state with an array s_inc of type uint8_t [START_REF] Facon | Detecting cachetiming vulnerabilities in post-quantum cryptography algorithms[END_REF], where the last byte represents the number of bytes that were not processed yet. This is not a sensitive information, but because our analysis tool does not distinguish between dependencies inside the same array, it is considered sensitive and leakages are reported, but they are false positives. These false positives are also reported for the shake256 variant, for similar reasons. Other than that, no leaks were reported, and we conclude that the provided implementations are constant time.

Falcon While the original second round implementations included a variable-time Gaussian sampler, it was replaced by a constant-time sampler in an updated version [START_REF] Fouque | Updated falcon reference implementation[END_REF]. We analyzed this update, and the only reported warnings concerned rejection sampling. Thus, we verified that the updated implementation is indeed constant time.

NTRUPrime NTRUPrime uses AES, and the provided implementations exploit OpenSSL's implementation, which we assume is constant-time. The rest of the code was verified to be constant time.

NTRU

The provided implementation was verified to be constant time.

NewHope

The rejection sampling used in NewHope triggers a warning from our tool, but this is expected. Other than that, the code is constant time.

CRYSTALS-Kyber

The rejection sampling used in CRYSTALS-Kyber triggers a warning from our tool, but this is expected. Other than that, the code is constant time.

CRYSTALS-Dilitihium

The use of rejection sampling in several functions, as well as using recursive goto instructions to implement it, caused an unusually high number of false positives. Manual inspection of these false positives confirmed that the code is constant time.

CHAPTER 4. ON THE STOCHASTIC MODEL OF PUFS

Strong PUFs As a consequence, the PUF output for the strong PUFs (arbiter PUF, RO-sum PUF and loop-PUF) can be rewritten as follows:

) is distributed as an i.i.d. Gaussian vector. For the arbiter-PUF, a one-to-one transformation of the challenge needs to considered before the scalar product with the delay differences is taken. As this does not change the security and reliability considerations, we will ignore this transformation for the sake of simplicity.

In general, the response bits for different challenges are not independent. Although there can be as many as 2 n possible challenges, we showed that the entropy cannot be higher than about n 2 . Furthermore, for small values of n ≤ 10, the Shannon entropy is actually close to its theoretical maximal value. These findings, along with a description of the methods that allowed us to perform the simulations, are presented in Chapter 6, which is based on two arte icles, one presented at Allerton Conference on Communication, Control, and Computing (2019) [START_REF] Schaub | Entropy estimation of physically unclonable functions via Chow parameters[END_REF], the other published in Advances in Mathematics of Communications (2020) [START_REF] Schaub | Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem[END_REF].

Weak PUFs

The three aforementioned PUFs can be turned into weak PUFs by restricting the set of applicable challenges. As proven in e.g. [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF], using a Hadamard matrix as the challenge matrix allows to obtain independent response bits 1 . Therefore, the model of the weak PUF is b = (sign(x 1 ), sign(x 2 ), . . . , sign(x n )) where x = (x 1 , x 2 , . . . , x n ) is distributed as a vector of i.i.d Gaussian random variables.

Measurement Noise Distribution

PUF delay measurements are subject to several sources of noise. One such source is the measurement noise, altering the measured delays. It can be modeled as an additive Gaussian noise, independent from the circuit delays. Thus, the weak PUF model with noise becomes b = (sign(x 1 + y 1 ), sign(x 2 + y 2 ), . . . , sign(x n + y n )) where (y 1 , y 2 , . . . , y n ) is distributed as a vector of i.i.d Gaussian random variables with variance σ 2 , and similarly for the strong PUF model.

An analysis of the weak PUF model with noise, as well as the effect of reliabilityenhancing measures, is provided in Section 5.1, based on work published at Digital System Designs (2018) [START_REF] Schaub | An improved analysis of reliability and entropy for delay PUFs[END_REF]. Follow-up work that does not reduce the entropy as part of the reliability-enhancing measures, but uses a function more complicated than the sign function, is presented in Section 5.4 and is based on work published at IEEE International Workshop on Advances in Sensors and Interfaces (2019) [START_REF] Danger | Two-metric helper data for highly robust and secure delay PUFs[END_REF].

Chapter 6 Entropy Estimation of Physically Unclonable Functions via Chow Parameters

Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.

John von Neumann

This chapter merges the contributions published in collaboration with Olivier Rioul, Jean-Luc Danger, Sylvain Guilley and Joseph J. Boutros.

A physically unclonable function (PUF) is an electronic circuit that produces an intrinsic identifier in response to a challenge. These identifiers depend on uncontrollable variations of the manufacturing process, which make them hard to predict or to replicate. Various security protocols leverage on such intrinsic randomness for authentication, cryptographic key generation, anti-counterfeiting, etc. Evaluating the entropy of PUFs (for all possible challenges) allows one to assess the security properties of such protocols.

In this chapter, we estimate the probability distribution of certain kinds of PUFs composed of n delay elements. This is used to evaluate relevant Rényi entropies and determine how they increase with n. Such a problem was known to have extremely high complexity (in the order of 2 2 n ) and previous entropy estimations were carried out up to n = 7. Making the link with the theory of Boolean threshold functions, we leverage on the representation by Chow parameters to estimate probability distributions up to n = 10. The resulting Shannon entropy of the PUF is close to the max-entropy, which is asymptotically quadratic in n.

Introduction

Suppose we are given a (nonlinear) (n, M ) code C with M codewords c i ∈ {±1} n and n i.i.d. standard Gaussian variables X 1 , X 2 , . . . , X n ∼ N (0, 1). Let X = (X 1 , X 2 , . . . , X n ) Definition 15 (Full entropy). For any α ≥ 0, we define the full entropy H α (n) as the Rényi entropy for the (n, 2 n ) challenge code that contains all possible codewords.

The full entropy is highest among all codes, as shown in the following lemma. Lemma 4 (Full entropy is maximal). For any α ≥ 0 and any challenge code C,

which implies

Summing over all P b we obtain

The assertion follows by taking the logarithm on both sides of this inequality and multiplying by the negative constant 1 1-α . The case α < 1 is similar: The inequalities (6.7) and (6.8) are reversed because x α ≥ x for x ∈ [0, 1], but the constant 1 1-α is positive. Therefore, the same assertion follows. The cases α = 1 and α = ∞ are established by taking limits.

Notice that the maximum entropy H α (n) is always attained by a (n, 2 n-1 ) challenge code, by the following symmetry argument: since sign(c • x) = -sign ((-c) • x), the set {±1} n can be partitioned into two opposite sets where codewords in the second set bring no additional entropy. Indeed, adding a codeword c to a code C which already contains -c does not change the probabilities of the sign vectors, only their labeling. This leaves all Rényi entropies unchanged. Therefore, it is possible to obtain the maximum entropy with any (n, 2 n-1 ) code C satisfying c ∈ C =⇒ -c ∈ C. Table 6.1 summarizes the notations used in the remainder of this chapter.

Motivation

Definitions 12 and 13 correspond to a particular PUF that exploits the variability of n distinct delay elements (a so-called "Loop PUF"), where X 1 , X 2 , . . . , X n are independent Gaussian delay differences. This type of PUF has been first described by Cherif et al. [START_REF] Cherif | An easy-to-design PUF based on a single oscillator: The loop PUF[END_REF].

A previous modelization of the Loop PUF, obtained via Monte-Carlo simulations of the possible circuit behaviors, showed a distribution of delays close to a Gaussian distribution,

The bivariate case was already known to Hermite [START_REF] Stieltjes | Extrait d'une lettre adressée à M. Hermite[END_REF]. The extension to the trivariate case is a lesser known extension and can be found, for instance, in [START_REF] Abrahamson | Orthant probabilities for the quadrivariate normal distribution[END_REF]. A short proof of both formulas is given by Rioul et al. in [START_REF] Rioul | On the entropy of physically unclonable functions[END_REF].

Proof. Suppose that such a vector α exists. There is at least one component that is different from 0. Without loss of generality, suppose that α 1 = 0. We then have

In particular, this implies that

, the sign of the right-hand side of the expression is the opposite sign of α 1 . Thus, α 1 = -sign(c 1 • X), which contradicts our hypothesis.

Conversely, suppose that P b = 0. Therefore, the Gaussian vector (c i • X) i is degenerate, and its support is included in a sub-space of R M of dimension < M . In particular, it is included in some hyperplane of equation M i=1 a i x i = 0, where the a i are not all 0. Since P b = 0, this hyperplane is disjoint from the orthant defined by the signs of b, that is the set x 1 b 1 > 0, x 2 b 2 > 0, . . . , x M b M > 0. Therefore, we have that all a i b i have the same sign, that we can take positive. Since the support is included in the hyperplane defined before, we must have

for all X ∈ R n , and therefore M i=1 a i c i = 0. By setting α i = a i , the α i have the same signs as the b i and are not all 0, which concludes the proof. Proof. Permuting the columns or changing corresponds to a permutation or sign changes of the X i . For any s = (s 1 , s 2 , . . . , s n ) ∈ {-1, +1} n and σ ∈ S n , the joint distribution of X = (X i ) i and (s i X σ(i) ) are the same.

CLOSED-FORM EXPRESSIONS

Proof. Let us denote by p (resp p ) the Chow parameters of f (resp g • f ). The PUF obtained from weights x is g • f . From Lemma 9, the p i satisfy the same ordinal relations and have the same signs as the x i . Therefore, f is a canonical PUF.

These results allow us to efficiently estimate the PUF distribution by Monte-Carlo methods, as described in Algorithm 6.5.1. Such an algorithm can be used for any i.i.d. weight distribution with symmetric densities (not necessarily Gaussian). Algorithm 6.5.1 How to estimate the PUF distribution.

Entropies Estimation

In this section, we present the simulation results in the Gaussian case where the weights X i are i.i.d. ∼ N (0, 1). Exact values were already determined up to n = 4 in [START_REF] Schaub | Challenge codes for physically unclonable functions with Gaussian delays: A maximum entropy problem[END_REF].

Estimating the Max-Entropy H 0

According to Lemma 8, every PUF can be attained by some realization of weights. Therefore, the max-entropy of the PUF distribution is simply the logarithm of the total number of PUFs with n weights. This number is equal to the total number of BTFs of n -1 variables and has been computed up to n = 10 in [130, § 3.1.2], see Table 6.4.