Antoine Geimer

Frédéric Recoules

Lesly-Ann Daniel

Sébastien Bardin

A Systematic Evaluation of Automated Tools for Side-Channel Vulnerabilities Detection in Cryptographic Libraries

To protect cryptographic implementations from side-channel vulnerabilities, developers must adopt constant-time programming practices. As these can be error-prone, many side-channel detection tools have been proposed. Despite this, such vulnerabilities are still manually found in cryptographic libraries. While a recent paper by Jancar et al. shows that developers rarely perform side-channel detection, it is unclear if existing detection tools could have found these vulnerabilities in the first place.

To answer this question we surveyed the literature to build a classification of 34 side-channel detection frameworks. The classification we offer compares multiple criteria, including the methods used, the scalability of the analysis or the threat model considered. We then built a unified common benchmark of representative cryptographic operations on a selection of 5 promising detection tools. This benchmark allows us to better compare the capabilities of each tool, and the scalability of their analysis. Additionally, we offer a classification of recently published side-channel vulnerabilities. We then test each of the selected tools on benchmarks reproducing a subset of these vulnerabilities as well as the context in which they appear. We find that existing tools can struggle to find vulnerabilities for a variety of reasons, mainly the lack of support for SIMD instructions, implicit flows, and internal secret generation. Based on our findings, we develop a set of recommendations for the research community and cryptographic library developers, with the goal to improve the effectiveness of side-channel detection tools.

Introduction

Implementing cryptographic algorithms is an arduous task. Beyond functional correctness, the developers must also ensure that their code does not leak potentially secret information through side channels. Since Paul Kocher's seminal work [START_REF] Paul | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF], the research community has combed through software and hardware to find vectors allowing for side-channel attacks, from execution time to electromagnetic emissions. The unifying principle behind this class of attacks is that they do not exploit the algorithm specification but rather physical characteristics of its execution. Among the aforementioned attack vectors, the processor microarchitecture is of particular interest, as it is a shared resource between multiple programs. By observing the target execution through microarchitectural components (e.g., cache [START_REF] Liu | Last-Level Cache Side-Channel Attacks are Practical[END_REF][START_REF] Yarom | FLUSH+RELOAD: A High Resolution, Low Noise, L3 Cache Side-Channel Attack[END_REF], branch predictor [START_REF] Aciiçmez | Predicting Secret Keys Via Branch Prediction[END_REF][START_REF] Evtyushkin | BranchScope: A New Side-Channel Attack on Directional Branch Predictor[END_REF], DRAM [START_REF] Pessl | DRAMA: Exploiting DRAM Addressing for Cross-CPU Attacks[END_REF], CPU ports [START_REF] Cabrera Aldaya | Port Contention for Fun and Profit[END_REF]), an attacker can deduce secret information beyond what is normally possible with classical cryptanalysis. Side-channel primitives using these components allow an attacker to reconstruct secret-dependent control flow and table look-ups. This problem is exacerbated in multi-core processors and VM environments, where execution can be shared concurrently by multiple actors, and in trusted execution environments, where the privileged control of untrusted operating systems can be leveraged to perform controlled-channel attacks [START_REF] Xu | Controlled-Channel Attacks: Deterministic Side Channels for Untrusted Operating Systems[END_REF].

Consequently, multiple countermeasures to timing and microarchitectural attacks have been developed in the literature. Systemlevel approaches like StealthMem [START_REF] Kim | STEALTHMEM: System-Level Protection Against Cache-Based Side Channel Attacks in the Cloud[END_REF] modify the OS' behavior between context switches to minimize information sharing, while language-level approaches like type systems can be used to enforce proper information flow in the source code [START_REF] Almeida | Jasmin: High-Assurance and High-Speed Cryptography[END_REF]. Hardware-based approaches also enable securing components by design [START_REF] Purnal | Systematic Analysis of Randomization-based Protected Cache Architectures[END_REF][START_REF] Zhang | STBPU: A Reasonably Secure Branch Prediction Unit[END_REF]. However, these approaches are hardly practical as they rely on either large source code rewrites, or require system or hardware modifications. Manually writing a program such that it is free of such microarchitectural leakage is thus, by far, the most commonly employed countermeasure in cryptographic libraries [START_REF]BearSSL -Constant-Time Crypto[END_REF][START_REF] Daniel | The Security Impact of a New Cryptographic Library[END_REF]. In particular, the constant-time programming discipline [START_REF] Barthe | System-level Non-interference for Constant-time Cryptography[END_REF][START_REF] Daniel | The Security Impact of a New Cryptographic Library[END_REF] (CT) consists in writing a program such that its control flow, memory accesses and operands of variable-time instructions do not depend on secret data, and is considered the de-facto standard to protect against (non-transient) timing and microarchitectural attacks. Constanttime programming is an arduous task as its recommendations go against usual programming practices and requires knowledge of the literature on side channels. Moreover, the programmer must be mindful of compiler optimizations not preserving constant-time code [START_REF] Daniel | Binsec/Rel: Symbolic Binary Analyzer for Security with Applications to Constant-Time and Secret-Erasure[END_REF][START_REF] Simon | What You Get is What You C: Controlling Side Effects in Mainstream C Compilers[END_REF] and libraries not following these practices at all [START_REF] Thierry Kaufmann | When Constant-Time Source Yields Variable-Time Binary: Exploiting Curve25519-donna Built with MSVC[END_REF].

Problem. In the past decade, the research community has investigated automated ways of checking whether a program is leakagefree or not. Many different approaches have been proposed [START_REF] Bao | Abacus: Precise Side-Channel Analysis[END_REF][START_REF] Daniel | Binsec/Rel: Efficient Relational Symbolic Execution for Constant-Time at Binary-Level[END_REF][START_REF] Gras | ABSynthe: Automatic Blackbox Side-channel Synthesis on Commodity Microarchitectures[END_REF][START_REF] Langley | Ctgrind[END_REF][START_REF] Reparaz | Dude, is my code constant time?[END_REF][START_REF] Weiser | DATA -Differential Address Trace Analysis: Finding Address-based Side-Channels in Binaries[END_REF][START_REF] Wichelmann | MicroWalk: A Framework for Finding Side Channels in Binaries[END_REF], both static and dynamic, but despite this abundance of tools, side-channel vulnerabilities are still found regularly in cryptographic libraries [START_REF] Lou | A Survey of Microarchitectural Side-channel Vulnerabilities, Attacks, and Defenses in Cryptography[END_REF]. Two factors could explain this paradox: either these tools were not able to find such vulnerabilities, or the developers did not use them. A recent survey by Jancar et al. [START_REF] Jancar | They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks[END_REF] investigated the opinions of cryptographic libraries developers regarding side-channel detection frameworks. They found that while many were willing to include side channels in their threat models, very few actually used tools. While this provides answers for the second factor, the first one remains unexplored.

Goal. Our paper investigates this question by providing a thorough state of the art on side-channel detection frameworks and recent side-channel vulnerabilities. In particular, we restrict ourselves to vulnerabilities found in cryptographic libraries spanning five years (2017-2022). We only consider vulnerabilities exploited through passive microarchitectural side-channel attacks. Physical side channels [START_REF] Camurati | Screaming Channels: When Electromagnetic Side Channels Meet Radio Transceivers[END_REF][START_REF] Daniel Genkin | RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis[END_REF][START_REF] Kocher | Differential Power Analysis[END_REF][START_REF] Josyula | EMpowering Side-Channel Attacks[END_REF], active attacks (e.g., Rowhammer [START_REF] Kim | Flipping bits in memory without accessing them: An experimental study of DRAM disturbance errors[END_REF]) or transient execution attacks [START_REF] Canella | A Systematic Evaluation of Transient Execution Attacks and Defenses[END_REF][START_REF] Canella | Fallout: Leaking Data on Meltdown-resistant CPUs[END_REF][START_REF] Ragab | Rage Against the Machine Clear: A Systematic Analysis of Machine Clears and Their Implications for Transient Execution Attacks[END_REF][START_REF] Van Bulck | LVI: Hijacking Transient Execution through Microarchitectural Load Value Injection[END_REF] are out-of-scope.

We tackle the following research questions:

RQ1 How to compare these frameworks, as their respective publications offer differing evaluation? RQ2 Could an existing framework have detected these vulnerabilities found manually? RQ3 What features might be missing from existing frameworks to find these vulnerabilities?

Contributions. The contributions can be summarized as follows:

(1) We present a qualitative classification of the state-of-the-art tools for side-channel vulnerability detection. We classify 34 frameworks depending on multiple parameters such as the methods used, the type of outputs given by the analysis, or the type of programs analyzed (Section 4); [START_REF]Bug 200535 -Valgrind flags lots of uninitialized locations with programs compiled with "-static[END_REF] We compare a subset of these detection frameworks on a unified benchmark, comprised of representative cryptographic operations from 3 libraries, totaling 25 primitives. We found that asymmetric cryptographic primitives are still a challenge for most detection tools. This benchmark aims at ensuring a fair comparison between frameworks and help develop future efforts (Section 7); (3) We offer a classification of recently published side-channel vulnerabilities in cryptographic libraries, offering new insights into where to find potential vulnerabilities (Section 5); (4) We verify whether 4 of these vulnerabilities could have been detected with the aforementioned frameworks. We conclude that support for SIMD instructions, implicit flows, and internal secret generation is crucial for effective side-channel detection tools (Section 8).

Our whole evaluation framework is available for the community.

Scope

Language-based approaches for high-assurance cryptography-in particular used in the EverCrypt library [START_REF] Protzenko | EverCrypt: A Fast, Verified, Cross-Platform Cryptographic Provider[END_REF][START_REF] Zinzindohoué | HACL*: A Verified Modern Cryptographic Library[END_REF], FaCT [START_REF] Cauligi | FaCT: a DSL for timing-sensitive computation[END_REF], and Jasmin [START_REF] Almeida | Jasmin: High-Assurance and High-Speed Cryptography[END_REF][START_REF] Almeida | The Last Mile: High-Assurance and High-Speed Cryptographic Implementations[END_REF]-provide provably functionally correct and constanttime implementations of cryptographic primitives and libraries, but require a complete code rewrite in a dedicated language. In this paper, we consider out-of-scope such language-based approaches and focus on tools that are applicable to off-the-shelf libraries.

Program transformations and repair tools have been proposed to transform insecure programs into (variants of) constant-time programs [START_REF] Agat | Transforming Out Timing Leaks[END_REF][START_REF] Borrello | Constantine: Automatic Side-Channel Resistance Using Efficient Control and Data Flow Linearization[END_REF][START_REF] Brotzman | CaSym: Cache Aware Symbolic Execution for Side Channel Detection and Mitigation[END_REF][START_REF] Chattopadhyay | Symbolic Verification of Cache Side-Channel Freedom[END_REF][START_REF] Köpf | Transformational typing and unification for automatically correcting insecure programs[END_REF][START_REF] Molnar | The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks[END_REF][START_REF] Rane | Raccoon: Closing Digital Side-Channels through Obfuscated Execution[END_REF]116,[START_REF] Wu | Eliminating timing side-channel leaks using program repair[END_REF]. Because side-channel detection is not the main focus of these works, we only include them when they propose a novel detection phase.

Power side-channel attacks [START_REF] Kocher | Differential Power Analysis[END_REF] exploit data-dependent differences in the power consumption of a CPU to extract secrets. These attacks usually assume a stronger attacker model than timing microarchitectural attacks, typically requiring physical access to a device. The tools we consider in this survey explicitly restrict to the latter attacker model, hence they cannot find vulnerabilities related to power-based attacks.

Interestingly, recent frequency throttling side-channel attacks [START_REF] Liu | Frequency Throttling Side-Channel Attack[END_REF][START_REF] Wang | Hertzbleed: Turning Power Side-Channel Attacks Into Remote Timing Attacks on x86[END_REF] exploit the fact that power consumption can also influence the execution time of a program via dynamic voltage and frequency scaling features of CPUs. These attacks effectively bring power side-channels to the (micro-)architecture, making them exploitable without physical access, and blur the boundary between these two attacker models. We consider these attacks out-of-scope as they also affect constant-time programs and require different mitigations, traditionally used to protect cryptographic code against power-side channel attacks, such as masking [START_REF] Dj | Multiplicative Masking and Power Analysis of AES[END_REF][START_REF] Messerges | Securing the AES Finalists Against Power Analysis Attacks[END_REF] or blinding [START_REF] Joye | Protections against Differential Analysis for Elliptic Curve Cryptography[END_REF].

Finally, we focus on side-channel detection tools for cryptographic code and exclude tools targeting other libraries [START_REF] Wang | Time and Order: Towards Automatically Identifying Side-Channel Vulnerabilities in Enclave Binaries[END_REF][START_REF] Yuan | Automated Side Channel Analysis of Media Software with Manifold Learning[END_REF].

Related Work

The closest related work is a recent survey by Jancar et al. [START_REF]Constanttimeness verification tools[END_REF][START_REF] Jancar | They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks[END_REF], which analyzes how cryptographic developers ensure that their code is secure against microarchitectural attacks. In particular, this survey classifies existing tools for microarchitectural side-channel analysis, and identifies: (1) whether developers are aware of these tools or have experience with them, [START_REF]Bug 200535 -Valgrind flags lots of uninitialized locations with programs compiled with "-static[END_REF] what kind of tools developers are willing to use (specifically given the trade-off between strong guarantees and usability), [START_REF]Implement deterministic ECDSA sign (RFC6979[END_REF] what are the common shortcomings hindering the adoption of these tools. In contrast, we focus on technical differences between these tools in order to compare their actual capabilities. We also select a subset of promising tools and experimentally assess their scalability and ability to detect recent vulnerabilities from cryptographic libraries.

Yuan et al. [START_REF] Yuan | Automated Side Channel Analysis of Media Software with Manifold Learning[END_REF] compared 11 side-channels detection tools on 8 criteria, including some overlapping with ours. However, our classification aims at being more general and systematic by considering more general criteria and a broader set of tools.

Lou et al. presented a survey [START_REF] Lou | A Survey of Microarchitectural Side-channel Vulnerabilities, Attacks, and Defenses in Cryptography[END_REF] characterizing hardware and software vectors in microarchitectural side-channel attacks. While their work is more exhaustive in terms of characterizing sidechannel vulnerabilities in cryptographic libraries, our work is focused on vulnerabilities found in a recent period and its purpose is to understand why they were not found automatically. Barbosa et al. [21] proposed a systematization of the literature and a taxonomy of tools for computer-aided cryptography. Their survey encompasses formal, machine-checkable approaches for design-level security, functional correctness, and side-channel security. In contrast, we focus on side-channel security but consider a broader set of tools, not restricted to provably secure approaches.

Complementary to our work, Ge et al. [START_REF] Ge | A survey of microarchitectural timing attacks and countermeasures on contemporary hardware[END_REF] proposed a taxonomy of timing microarchitectural attacks and defenses. They give an overview of microarchitectural components that are susceptible to side-channel attacks and classify attacks according to the degree of hardware sharing and concurrency involved. Finally, they survey existing hardware and software countermeasures against these attacks. Similarly, Jakub Szefer [118] proposed a survey of microarchitectural channels, attacks and defenses with a stronger focus on microarchitectural features enabling covert and side channels.

Buhan et al. [START_REF] Buhan | SoK: Design Tools for Side-Channel-Aware Implementations[END_REF] presented a taxonomy of tools for protecting against physical side-channel attacks such as power consumption or electromagnetic emanations. Their survey encompasses tools for physical side-channel leakage detection, verification, and mitigation for pre-or post-silicon development stage. Conversely, our work focuses on (non-overlapping) tools for timing and microarchitectural side-channels detection in software.

Background

This section introduces the background to understand side-channel vulnerabilities, in particular the hardware and software vectors.

Microarchitectural side channels

Microarchitectural attacks use shared microarchitectural components to deduce secret information from a program executing on the same physical core, CPU, or socket. By probing a component state, the attacker can observe the changes the victim's execution induced on that state, thus gaining information on the victim. The type and quantity of information gained depend on the component and the way it was probed, e.g., branch predictors can expose the direction of branches taken by a victim [START_REF] Aciiçmez | New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures[END_REF], port contention allows an attacker to deduce which instructions the victim executes [START_REF] Cabrera Aldaya | Port Contention for Fun and Profit[END_REF], TLB attacks leak the victim's memory accesses at page-level resolution [START_REF] Gras | Translation Leak-aside Buffer: Defeating Cache Side-channel Protections with TLB Attacks[END_REF]. By far the most widely used component in attacks remains the cache. Multiple techniques have been developed to attack caches, to retrieve both the victim's control-flow and memory accesses, such as Prime+Probe [START_REF] Liu | Last-Level Cache Side-Channel Attacks are Practical[END_REF][START_REF] Percival | Cache Missing for Fun and Profit[END_REF] and Flush+Reload [START_REF] Yarom | FLUSH+RELOAD: A High Resolution, Low Noise, L3 Cache Side-Channel Attack[END_REF]. Some of these attacks can also be run remotely [START_REF] Billy | Remote Timing Attacks Are Still Practical[END_REF][START_REF] Brumley | Remote timing attacks are practical[END_REF]. They can be especially powerful in the context of trusted execution environment, such as Intel-SGX, where the untrusted operating system can be leveraged to perform controlled-channel attacks, enabling high-resolution and low-noise side channels [START_REF] Van Bulck | SGX-Step: A Practical Attack Framework for Precise Enclave Execution Control[END_REF][START_REF] Van Bulck | Microarchitectural Side-channel Attacks for Privileged Software Adversaries[END_REF][START_REF] Xu | Controlled-Channel Attacks: Deterministic Side Channels for Untrusted Operating Systems[END_REF]. A complete overview of microarchitectural side-channel attacks can be found in [START_REF] Ge | A survey of microarchitectural timing attacks and countermeasures on contemporary hardware[END_REF]118].

Side-channel vulnerabilities

The hardware vector represents only one aspect of side channels. To be exploitable, software must leak sensitive data in some way.

Memory accesses and control flow that depend on the secret are the most commonly identified sources of leakage in cryptographic software. We detail common side-channel pitfalls encountered in cryptographc implementations. An exhaustive look at vulnerabilities in cryptographic libraries is presented in [START_REF] Lou | A Survey of Microarchitectural Side-channel Vulnerabilities, Attacks, and Defenses in Cryptography[END_REF].

Control-flow. One example of secret-dependent control flow is the square-and-multiply implementation of modular exponentiation used in RSA, where the operation sequence depends on the bit value of the secret exponent, leading to timing attacks [START_REF] Paul | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF]. Scalar multiplication, the analogous operation for elliptic curve cryptography, suffers from a similar problem in double-and-add implementations. Variants of these implementations such as the sliding window and wNAF multiplication algorithms are preferred for their performance, but do not alleviate this vulnerability [START_REF] Benger | Just a Little Bit" : A Small Amount of Side Channel Can Go a Long Way[END_REF][START_REF] Percival | Cache Missing for Fun and Profit[END_REF]. To mitigate controlflow-based side-channel attacks, developers have resorted to either balancing [START_REF] Albrecht | Lucky Microseconds: A Timing Attack on Amazon's s2n Implementation of TLS[END_REF] or linearizing [START_REF] Molnar | The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks[END_REF] (i.e., eliminating) secret-dependent control-flow. The former solution, employed for instance in the Montgomery ladder algorithm [START_REF] Joye | The Montgomery Powering Ladder[END_REF] for scalar multiplication, is particularly challenging to get right as it remains vulnerable to attacks exploiting port-contention, branch predictors, and (instruction and data) cache attacks [START_REF] Yarom | Recovering OpenSSL ECDSA Nonces Using the FLUSH+RELOAD Cache Side-channel Attack[END_REF]. The latter is not a fool-proof solution either as it remains vulnerable to attacks exploiting secret-dependent memory accesses [START_REF] Gras | Translation Leak-aside Buffer: Defeating Cache Side-channel Protections with TLB Attacks[END_REF]. Modular inversion is another common operation that can be a source of side-channel leakage, in particular through the control flow of greatest common divisor (GCD) algorithms, such as the binary extended Euclidean algorithm (BEEA) [START_REF] Aciiçmez | New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures[END_REF]. Secret-dependent branches are also at the heart of padding oracles used to mount Bleichenbacher's attack [START_REF] Bleichenbacher | Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1[END_REF] or Lucky 13 [START_REF] Nadhem | Lucky Thirteen: Breaking the TLS and DTLS Record Protocols[END_REF].

Memory access. The original AES proposal describes how the cipher can be efficiently implemented using pre-computed tables with an access offset depending on the secret key, making it particularly vulnerable to cache attacks [START_REF] Daniel | Cache-Timing Attacks on AES[END_REF]. The aforementioned sliding window and wNAF multiplication algorithm also employs tables to store pre-computed values to speed up computations which, when accessed with a value derived from the secret, induce leakage through memory accesses [START_REF] Brumley | Cache-Timing Template Attacks[END_REF][START_REF] Liu | Last-Level Cache Side-Channel Attacks are Practical[END_REF].

Operand values. Secret-dependent operand values can also be a source of leakage if they influence the program running time. Early termination in integer multiplication on ARM has been shown to induce a timing leak [START_REF] Großschädl | Side-Channel Analysis of Cryptographic Software via Early-Terminating Multiplications[END_REF], with similar problem being found in x86 floating-point instructions [START_REF] Andrysco | On Subnormal Floating Point and Abnormal Timing[END_REF].

Classifying side-channel vulnerability detection frameworks

As the concept of microarchitectural attacks has gathered attention only relatively recently, all the approaches we present here are less than a decade old. We structure this section in two large categories, static and dynamic, that represents a split in approaches but also in research communities: the first closer to program verification and the second to bug-finding. However, we strive to compare these approaches using broader parameters. Table 1 gives a comparison of the 34 detection frameworks we consider in this survey.

Criteria. In addition to comparing frameworks by their type (static or dynamic), we give a description of the precise method employed. While our efforts are independent from [START_REF]Constanttimeness verification tools[END_REF], there is a significant overlap between the two classifications. Yet the present one goes into more details, being enriched with additional criteria. Similarly to [START_REF]Constanttimeness verification tools[END_REF][START_REF] Jancar | They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks[END_REF], we detail the type of programs supported by the analysis (e.g., C, Java, binary code) and whether the approach is supported by a soundness claim. While analyzing the source code or LLVM is more practical as the program semantics is more easily extracted than in the binary, doing so poses the risk of missing vulnerabilities introduced by the compiler [START_REF] Daniel | Binsec/Rel: Symbolic Binary Analyzer for Security with Applications to Constant-Time and Secret-Erasure[END_REF][START_REF] Thierry Kaufmann | When Constant-Time Source Yields Variable-Time Binary: Exploiting Curve25519-donna Built with MSVC[END_REF][START_REF] Simon | What You Get is What You C: Controlling Side Effects in Mainstream C Compilers[END_REF]. A full soundness claim ( ) offers a formal guarantee that the analysis will not, in principle, accept insecure programs and so should not yield any false negatives. In practice, this may not be the case because of vulnerabilities outside the analysis' threat model, or because of bugs in the detection tool. Conversely, partial soundness ( ) claims cover tools that are sound under some restrictions (e.g., partial exploration of loops). In addition, our classification reports the policy enforced by these tools: (CT) constant-time proscribes secret-dependent control flow, memory accesses, and operands of variable time instructions;

(CO) cache-obliviousness requires the sequence of cache hits and misses w.r.t. a cache model to be independent from the secret input;

(CR) constant-ressource requires the execution cost (determined by a fixed instruction cost), to be independent from the secret input;

(CC) constant clock cycles requires the number of clock cycles to be independent from the secret input. Note that CT [START_REF] Almeida | Verifying Constant-Time Implementations[END_REF][START_REF] Barthe | System-level Non-interference for Constant-time Cryptography[END_REF] is strictly more conservative than CO and CR, and is the only policy that is secure w.r.t. the attacker scope considered in this paper. We also detail the type of outputs given by the analysis: estimation on the number of bits leaked (E), origin of the leakage (L), and whether a witness triggering the vulnerability is given (W). A tool reporting neither these three only reports the presence or absence of vulnerabilities on the target. We additionally report whether the tool supports blinding [START_REF] Joye | Protections against Differential Analysis for Elliptic Curve Cryptography[END_REF] (B), a defense that introduces additional randomness to computations to hinder inference of secret values. Finally, we offer a rough estimation of the tool scalability.

Limitation. Unfortunately there is no clear metric to quantify scalability without testing each tool. One possibility could be the number of instructions a tool can process per second, however not all publications make this information available and the concept of instruction can vary from one approach to another (LoC, IR or assembly instructions, counting unrolled loops or not, etc.). Furthermore, such metric would only be valid for one set of benchmarks on the same machine, whereas publications generally include different benchmarks on a variety of setup. We provide here a rough estimation, based on the claims made in the tools' publications. We differentiate tools able to analyze in a reasonable time: complex asymmetric primitives ( ), symmetric primitives ( ), and those struggling to scale even for these ( ).

Static analysis

Static analysis approaches attempt to derive security properties from the program without actually executing it, extracting formally defined guarantees on all possible executions through binary or source code analysis. As a formal exploration of every reachable state is unfeasible, program behavior is often approximated, making them prone to false positives. Static approaches were the first to be considered, as side-channel security is closely related to information flow policies [START_REF] Denning | Certification of Programs for Secure Information Flow[END_REF].

Logical reduction

Non-interference is a 2-safety property stating that two executions with equivalent public inputs and potentially different secret inputs must result in equivalent public outputs. This definition covers side channels by considering resource usage (e.g., address trace) as a public output. Approaches based on logical reduction to 1-safety transform the program so that verifying its side-channel security amounts to proving the safety of the transformed program.

Self-composition [START_REF] Barthe | Secure information flow by self-composition[END_REF] interleaves two executions of a program 𝑃 with different sets of secret variables in a single self-composed program 𝑃; 𝑃 ′ . Solvers can then be used to verify the non-interference property. This approach was used by Bacelar Almeida et al. [START_REF] Almeida | Formal verification of side-channel countermeasures using self-composition[END_REF] to manually verify limited examples, relying on a large amount of code annotations. ct-verif instead runs the two copies in lockstep, while checking their assertion-safety [START_REF] Almeida | Verifying Constant-Time Implementations[END_REF]. It is able to verify LLVM programs, leveraging the boogie verifier. Sidetrail [START_REF] Athanasiou | SideTrail: Verifying Time-Balancing of Cryptosystems[END_REF] reuses this to verify that secret dependent branches are balanced (assuming a fixed instruction cost and excluding memory access patterns), providing a counter-example when this verification fails.

However, such approaches suffer from an explosion in the size of the program state space. Blazer [START_REF] Antonopoulos | Decomposition instead of self-composition for proving the absence of timing channels[END_REF] verifies timing-channel security on Java programs by instead decomposing the execution space into a partition on secret-independent branches. Proving 2-safety is thus reduced to verifying 1-safety on each trace in the partition improving scalability at the cost of precision. Themis [START_REF] Chen | Precise Detection of Side-Channel Vulnerabilities using Quantitative Cartesian Hoare Logic[END_REF] uses static taint analysis to automatically annotate secret-dependent Java code with Hoare logic formulas as pre-and post-conditions. An SMT solver then verifies that the post-condition implies execution time differences remain bounded by given constant. Both tools provide a witness triggering the vulnerability otherwise.

Type systems

Approaches based on verifying type safety of a program differ from language-level countermeasures [START_REF] Almeida | Jasmin: High-Assurance and High-Speed Cryptography[END_REF][START_REF] Bond | Vale: Verifying High-Performance Cryptographic Assembly Code[END_REF], as the developer only needs to type the secret values with annotations instead of rewriting the program. The type system then propagates this throughout the program, similarly to static taint analysis. Type systems were considered relatively early to verify non-interference properties [START_REF] Agat | Transforming Out Timing Leaks[END_REF] and offer good scalability but their imprecision makes them difficult to use in practice.

VirtualCert [START_REF] Barthe | System-level Non-interference for Constant-time Cryptography[END_REF] analyzes a modified CompCert IR where each instruction makes its successors explicit. The authors define semantics for that representation, building the type system on top of it. An alias analysis giving a sound over-approximated prediction of targeted memory address is needed to handle pointer arithmetic. While this approach is more suited to a strict verification task, it can also provide a leakage estimate.

FlowTracker [START_REF] Rodrigues | Sparse representation of implicit flows with applications to side-channel detection[END_REF] introduces a novel algorithm to efficiently compute implicit information flows in a program, and uses it to apply a type system verifying constant-time.

Abstract interpretation

As a program semantics is generally too complex to formally verify non-trivial properties, abstract interpretation [START_REF] Cousot | Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints[END_REF] over-approximates its set of reachable states, so that if the approximation is safe, then the program is safe.

CacheAudit [START_REF] Doychev | CacheAudit: A Tool for the Static Analysis of Cache Side Channels[END_REF] performs a binary-level analysis, quantifying the amount of leakage depending on the cache policy by finding the size of the range of a side-channel function. This side-channel function is computed through abstract interpretation, and the size of its range determined using counting techniques. It was later extended to support dynamic memory and threat models allowing byte-level observations [START_REF] Doychev | Rigorous analysis of software countermeasures against cache attacks[END_REF] and more x86 instructions [START_REF] Mantel | A Systematic Study of Cache Side Channels Across AES Implementations[END_REF].

Blazy et al. [START_REF] Blazy | Verifying Constant-Time Implementations by Abstract Interpretation[END_REF] focus on the source code instead of the binary. Their tool is integrated into the formally-verified Verasco static analyzer, and uses the CompCert compiler. The analysis is structured around a tainting semantics that propagates secret information throughout the program.

STAnalyzer [START_REF] Schaub | Formal methods for the analysis of cache-timing leaks and key generation in cryptographic implementations[END_REF] uses data-flow analysis to report secret-dependent branches and memory accesses.

CacheS [START_REF] Wang | Identifying Cache-Based Side Channels through Secret-Augmented Abstract Interpretation[END_REF] uses an hybrid approach between abstract interpretation and symbolic execution. The abstract domain keeps track of program secrets-with a precise symbolic representation for values in order to confirm leakage-but keeps only a coarse-grain representation of non-secret values. To improve scalability, CacheS implements a lightweight but unsound memory model. [START_REF] King | Symbolic Execution and Program Testing[END_REF] (SE) denotes approaches that verify properties of a program by executing it with symbolic inputs instead of concrete ones. Explored execution paths are associated with a logical formula: the conjunction of conditionals leading to that path. A memory model maps encountered variables onto symbolic expressions derived from the symbolic inputs and the concrete constants. A solver is then used to check whether a set of concrete values satisfies the generated formulas. Recent advances in SMT solvers have made symbolic execution a practical tool for program analysis [START_REF] Cadar | Symbolic execution for software testing: three decades later[END_REF].

Symbolic execution Symbolic execution

CoCo-Channel [START_REF] Brennan | Symbolic path cost analysis for side-channel detection[END_REF] identifies secret-dependent conditions using taint-analysis, constructs symbolic cost expressions for each path of the program uses SE and reports paths that exhibit secretdependent timing behavior. Their cost model assigns a fixed cost per instruction, excluding secret-dependent memory accesses.

Several works use symbolic execution to derive a symbolic cache model and check that cache behavior does not depend on secrets. CANAL [START_REF] Sung | CANAL: a cache timing analysis framework via LLVM transformation[END_REF] models cache behaviors of programs directly in the LLVM intermediate representation by inserting auxiliary variable and instructions. It then uses KLEE [START_REF] Cadar | KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs[END_REF] to analyze the program and check that the number of hits does not depend on secrets. Similarly, CacheFix [START_REF] Chattopadhyay | Symbolic Verification of Cache Side-Channel Freedom[END_REF] uses SE to derive a symbolic cache model supporting multiple cache policies. In case of a violation, CacheFix can synthesize a fix by injecting cache hits/misses in the program. CaSym [START_REF] Brotzman | CaSym: Cache Aware Symbolic Execution for Side Channel Detection and Mitigation[END_REF] follows the same methodology and, to improve scalability, includes simplifications of the symbolic state and loop transformations, which are sound but might introduce false positives.

SE suffers from scalability issues when applied to 2-safety properties like constant-time verification. Daniel et al. [START_REF] Daniel | Binsec/Rel: Efficient Relational Symbolic Execution for Constant-Time at Binary-Level[END_REF] adapt its formalism to binary analysis, introducing optimizations to maximize information shared between two executions following a same path. Their framework Binsec/Rel offers a binary-level CT analysis, performing a bounded exploration of reachable states and giving counterexamples for the identified vulnerabilities.

Pitchfork [START_REF] Disselkoen | Finding and Eliminating Timing Side-Channels in Crypto Code with Pitchfork[END_REF] combines SE and dynamic taint tracking. It soundly propagates secret taints along all executions paths, reporting tainted branch conditions or memory addresses. Interestingly, Pitchfork can analyze protocol-level code by abstracting away primitives' implementations using function hooks, and analyzing them separately.

ENCIDER [START_REF] Yavuz | ENCIDER: Detecting Timing and Cache Side Channels in SGX Enclaves and Cryptographic APIs[END_REF] combines symbolic execution with taint analysis to reduce the number of solver calls. It also enables to specify information-flow function summaries to reduce path explosion.

Dynamic analysis

Dynamic analysis groups approaches that derive security guarantees from execution traces of a target program. Some form of dynamic binary instrumentation (DBI) is often used to execute the program and gather events of interest, such as memory accesses or jumps. Dynamic approaches differ in the events collected, and how traces are processed. They can be grouped depending on whether they reason on a single trace, or compare multiples traces together.

Trace comparison approaches

Statistical tests. Statistical tests can be used to check if different secrets induce statistically significant differences in recorded traces. Cache Template [START_REF] Gruss | Cache Template Attacks: Automating Attacks on Inclusive Last-Level Caches[END_REF] monitors cache activity to detect lines associated with a target event, then finds lines correlated with the event using a similarity measure. A first pass using page-level observations instead of lines can be used to improve scalability [START_REF] Schwarzl | Layered Binary Templating: Efficient Detection of Compiler-and Linker-introduced Leakage[END_REF]. Shin et al. [START_REF] Shin | Unveiling Hardwarebased Data Prefetcher, a Hidden Source of Information Leakage[END_REF] use K-means clustering to produce two groups of traces for each line. The confidence in the partition indicates which line is likely to be secret-dependent. DATA [START_REF] Weiser | DATA -Differential Address Trace Analysis: Finding Address-based Side-Channels in Binaries[END_REF] employs a Kuiper test then a Randomized Dependence Coefficient test to infer linear and non-linear relationships between traces and secrets. This was later extended to support cryptographic nonces as secrets [START_REF] Weiser | Big Numbers -Big Troubles: Systematically Analyzing Nonce Leakage in (EC)DSA Implementations[END_REF].

Mutual information (MI) can be used to quantify the information shared between secret values and recorded traces, with a non-zero MI score giving a leakage estimation. MicroWalk [START_REF] Wichelmann | MicroWalk: A Framework for Finding Side Channels in Binaries[END_REF] computes MI scores between input sets and hashed traces, with leakage location pinpointed using finer-grained instruction-level MI scores. MicroWalk-CI [START_REF] Wichelmann | Microwalk-CI: Practical Side-Channel Analysis for JavaScript Applications[END_REF] optimizes this process by transforming the traces in call trees, and adds support for JavaScript and easy integration in CI, following recommendations from [START_REF] Jancar | They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks[END_REF]. CacheQL [START_REF] Yuan | CacheQL: Quantifying and Localizing Cache Side-Channel Vulnerabilities in Production Software[END_REF] reformulates MI into conditional probabilities, estimated with neural networks. Leakage location is estimated by recasting the problem into a cooperative game solved using Shapley values. Contrary to other tools [START_REF] Bao | Abacus: Precise Side-Channel Analysis[END_REF][START_REF] Wichelmann | MicroWalk: A Framework for Finding Side Channels in Binaries[END_REF], CacheQL does not assume uniform distribution of the secret, nor deterministic executions traces.

STACCO [START_REF] Xiao | STACCO: Differentially Analyzing Side-Channel Traces for Detecting SSL/TLS Vulnerabilities in Secure Enclaves[END_REF] targets control-flow vulnerabilities specifically in TLS libraries running on SGX, focusing on oracles attacks [START_REF] Nadhem | Lucky Thirteen: Breaking the TLS and DTLS Record Protocols[END_REF][START_REF] Bleichenbacher | Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1[END_REF]. Traces recorded under different TLS packets are represented as sequences of basic blocks and compared using a diff tool.

Instead of recording traces, dudect [START_REF] Reparaz | Dude, is my code constant time?[END_REF] records overall clock cycles and compares their distribution with secret inputs divided in two classes (fix-vs-random). While this approach is simple and lightweight, it gives certainty that an implementation is secure up to a number of measurements. Contrary to other tools relying on an explicit leakage model, dudect directly monitors timings. Hence, vulnerabilities to other microarchitectural attacks like Hertzbleed might (in theory) be detected by dudect.

Fuzzing. Fuzzing techniques can be used to find inputs maximizing coverage and side-channel leakage. DifFuzz [START_REF] Nilizadeh | DifFuzz: differential fuzzing for side-channel analysis[END_REF] combines fuzzing with self-composition to find side-channels based on instruction count, memory usage and response size in Java programs. ct-fuzz [START_REF] He | ct-fuzz: Fuzzing for Timing Leaks[END_REF] extends this method to binary executables and cache leakage.

Single trace

Other approaches use only one trace to perform the analysis, sacrificing coverage for scalability. ctgrind [START_REF] Langley | Ctgrind[END_REF] repurposes the dynamic taint analysis of Valgrind to check CT by declaring secrets as undefined memory. This solution is easy to deploy and reuses familiar tools, but remains imprecise.

ABSynthe [START_REF] Gras | ABSynthe: Automatic Blackbox Side-channel Synthesis on Commodity Microarchitectures[END_REF] identifies secret-dependent branches using dynamic taint analysis. It employs a genetic algorithm to build a sequence of instructions based on interference maps evaluating contention created by each x86 instructions.

More precise approaches use SE to replay the trace with the secret as a symbolic value and check for CT violation. CacheD [START_REF] Wang | CacheD: Identifying Cache-Based Timing Channels in Production Software[END_REF] applies this approach to memory accesses. Abacus [START_REF] Bao | Abacus: Precise Side-Channel Analysis[END_REF] extends it to control-flow vulnerabilities, picking random values to check satisfiability instead of using a SMT solver. It also includes leakage estimation through Monte Carlo simulation.

Finally, CaType [START_REF] Jiang | Cache Refinement Type for Side-Channel Detection of Cryptographic Software[END_REF] uses refinement types (i.e., types carrying a predicate restricting their possible values) on a trace to track constant bit values and improve precision. CaType also supports implementations that use blinding.

Insights

Despite the relative youth of the field, a wide variety of approaches have been proposed. While initially more static approaches were proposed, dynamic ones soon followed after 2017. This might represent a shift in research communities, from a focus on verification to bug-finding and, critically, scalability. Indeed, dynamic approaches typically scale better than static ones. Yet, this advantage mainly applies to single-trace analysis approaches. For trace comparisonbased approaches, the scalability gain is less obvious as recording multiple traces can be time-consuming, particularly for statistical approaches requiring a large number of traces, or for slower algorithms (e.g., RSA). Single trace analyses however suffer from a critical lack of coverage, which could be alleviated through methods like fuzzing. SE has become a popular approach for both static and dynamic methods, as recent advances in SMT solvers make it practical for side-channel detection.

Both the static and dynamic communities could benefit from integrating approaches from one another. For example we find that Abacus' optimization of trying random values to satisfy SMT formulas would pair well with Binsec/Rel's optimizations sparing UNSAT formulas.

Classifying side-channel vulnerabilities

We give here a (non-exhaustive) overview of microarchitectural side-channel vulnerabilities which were subject to publications in security and cryptography conferences in the past five years, many of which were still found manually by researchers. Interestingly, most of these vulnerabilities are new manifestations of alreadyknown vulnerabilities (Section 5.1) and only few of them actually target new primitives or functionalities (Section 5.2).

Known vulnerabilities

Known vulnerabilities can resurface for two reasons: when knownvulnerable functions are used in new contexts, or in new libraries. In the first case, developers keep vulnerable functions in the codebase for performance reasons, carefully avoiding using them when manipulating secret data. This practice leaves the door open to new vulnerabilities in which these known-vulnerable functions (e.g., square-and-multiply) are used in a new context (e.g., key generation). In the second case, the lack of developer awareness may prevent side-channel mitigation transfer from one library to the other. This also includes libraries choosing to only partially mitigate the vulnerability, despite available secure alternatives.

New contexts

Featuring a decade-old code-base, OpenSSL is particularly susceptible to this kind of vulnerability, as side-channel protection in one module might not be correctly ported to another. In particular, OpenSSL sets a CT flag on BIGNUMs marking secret data so that they can be manipulated using secure functions. Recent publications have shown that such insecure-by-default approaches are particularly error-prone [START_REF] Cabrera Aldaya | Cache-Timing Attacks on RSA Key Generation[END_REF][START_REF] De Almeida Braga | PARASITE: PAssword Recovery Attack against Srp Implementations in ThE wild[END_REF][START_REF] García | Certified Side Channels[END_REF][START_REF] Tuveri | Side-Channel Analysis of SM2: A Late-Stage Featurization Case Study[END_REF][START_REF] Weiser | Single Trace Attack Against RSA Key Generation in Intel SGX SSL[END_REF].

ECDSA. Despite extensive research on mitigating scalar multiplication in ECDSA, Garcia et al. [START_REF] Pereida | Constant-Time Callees with Variable-Time Callers[END_REF] identified exploitable usage of modular inversion with the vulnerable BEEA [START_REF] Aciiçmez | New Branch Prediction Vulnerabilities in OpenSSL and Necessary Software Countermeasures[END_REF]. The vulnerable code path was taken because of a missing CT flag on the nonce.

SM2. The integration of the SM2 standard into OpenSSL did not inherit from lessons learned in ECDSA [START_REF] Tuveri | Side-Channel Analysis of SM2: A Late-Stage Featurization Case Study[END_REF]. In particular, SM2 signature generation directly called the vulnerable wNAF scalar multiplication with no padding done on the scalar, allowing timing attacks [START_REF] Benger | Just a Little Bit" : A Small Amount of Side Channel Can Go a Long Way[END_REF]. Failure to set the appropriate CT flag also resulted in the modular inversion using BEEA.

Key generation. The RSA key generation process did not use side-channel protections, as single-trace attacks were thought to be impractical. Weiser et al. [START_REF] Weiser | Single Trace Attack Against RSA Key Generation in Intel SGX SSL[END_REF] proved this assumption false by exploiting secret-dependent control-flow in the BEEA used in key generation. Key generation was independently investigated through the test methodology Triggerflow [START_REF] Cabrera Aldaya | Cache-Timing Attacks on RSA Key Generation[END_REF][START_REF] Gridin | Triggerflow: Regression Testing by Advanced Execution Path Inspection[END_REF], finding additional issues stemming from the CT flag. Key parsing. Similar vulnerabilities were found in OpenSSL and MbedTLS' key format handling [START_REF] García | Certified Side Channels[END_REF], as key format standards leave a lot of flexibility to implementations. Differences in key format were found to induce different execution paths for a same operation, some calling vulnerable functions. This was the case for RSA key parsing/validation, and signatures for some elliptic curves. A similar problem was discovered earlier [START_REF] Cabrera Aldaya | Port Contention for Fun and Profit[END_REF].

SRP. The missing CT flag steers OpenSSL implementation of SRP, a password-authenticated key exchange protocol, to an insecure variant of modular exponentiation using square-and-multiply [START_REF] De Almeida Braga | PARASITE: PAssword Recovery Attack against Srp Implementations in ThE wild[END_REF].

PRG. Among the standard designs for pseudo-random generators (PRGs), CTR_DRBG generates a pseudo-random bit sequence using the AES cipher. Cohney et al. [START_REF] Cohney | Pseudorandom Black Swans: Cache Attacks on CTR_DRBG[END_REF] investigated implementations of CTR_DRBG in multiple libraries, finding that the T-Table variant of AES was used despite its well-known vulnerabilities.

New libraries

As the most popular cryptographic library [START_REF] Nemec | Measuring Popularity of Cryptographic Libraries in Internet-Wide Scans[END_REF], OpenSSL has received considerable attention from side-channel researchers. However, mitigations implemented in OpenSSL are not necessarily propagated to other libraries. MbedTLS RSA implementation uses the sliding-window method despite its vulnerability to cache attacks [START_REF] Liu | Last-Level Cache Side-Channel Attacks are Practical[END_REF][START_REF] Percival | Cache Missing for Fun and Profit[END_REF]. Despite the implementation's attempt to balance branches by calling the same function in both branches of the square-and-multiply, Schwarz et al. [START_REF] Schwarz | Malware Guard Extension: Using SGX to Conceal Cache Attacks[END_REF] successfully exploited secret-dependent data access using a cache attack within an SGX enclave. A similar attack was also performed on the so-called leftto-right variant from Libgcrypt, featuring exponent blinding [121]. Still in SGX, the secret-dependent branch itself remains vulnerable to branch shadowing [START_REF] Lee | Inferring Fine-grained Control Flow Inside SGX Enclaves with Branch Shadowing[END_REF], or to attacks based on interactions between interrupts and instruction execution time [START_REF] Puddu | Frontal Attack: Leaking Control-Flow in SGX via the CPU Frontend[END_REF]. Hassan et al. [START_REF] Hassan | Déjà Vu: Side-Channel Analysis of Mozilla's NSS[END_REF] illustrate this issue in the NSS library. While NSS' ECC code is forked from OpenSSL, mitigations such as nonce padding [START_REF] Billy | Remote Timing Attacks Are Still Practical[END_REF] are not implemented in NSS.

Some libraries implement pseudo constant-time instead of full constant-time to keep their code base easier to maintain. Such mitigations seek to address the Lucky 13 [START_REF] Nadhem | Lucky Thirteen: Breaking the TLS and DTLS Record Protocols[END_REF] attack by adding dummy MAC verification or random delays. Ronen et al. [START_REF] Ronen | Pseudo Constant Time Implementations of TLS Are Only Pseudo Secure[END_REF] demonstrate that they do not protect against cache attacks. Similarly, Ronen et al.

[108] showed that padding oracles leading to Bleichenbacher-like attacks were still present in libraries such as MbedTLS, s2n, or NSS, due to early termination in padding verification.

Vulnerabilities in new functionalities

Arithmetic functions. Genkin et al. [START_REF] Daniel Genkin | May the Fourth Be With You: A Microarchitectural Side Channel Attack on Several Real-World Applications of Curve25519[END_REF] targeted the X25519 key exchange implemented in Libgcrypt, finding that, while scalar multiplication is done using a branchless Montgomery ladder, the underlying finite field arithmetic functions were not constant-time. An early exit in the modular reduction function allowed the authors to mount a cache attack recovering the key. Aranha et al. [START_REF] Aranha | LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage[END_REF] discovered a similar issue in OpenSSL branchless Montgomery Ladder used for ECDSA. When initializing the algorithm, a conditional swap is done depending on a secret value. While the swap itself is constant-time, the following finite field multiplication is not.

Hash-to-element. The Dragonfly handshake used in Wi-Fi authentication converts a shared password to an elliptic curve point, by computing the point coordinate derived from the password and a counter. When the obtained point is invalid, the counter is incremented and the operation repeated, thus creating a timing channel. While the standard suggests fixing the repetitions number by adding dummy ones, Vanhoef and Ronen [START_REF] Vanhoef | Dragonblood: Analyzing the Dragonfly Handshake of WPA3 and EAP-pwd[END_REF] found that such mitigations were often incorrectly implemented, if at all, leaving implementations vulnerable to cache attacks [START_REF] De Almeida Braga | Dragonblood is Still Leaking: Practical Cache-based Side-Channel in the Wild[END_REF].

Post-Quantum Cryptography (PQC). BLISS-B signature generation involves sampling a secret polynomial from a Gaussian distribution. Sampling methods based on pre-computed tables were shown to be vulnerable to cache attacks [START_REF] Pessl | To BLISS-B or not to be: Attacking strongSwan's Implementation of Post-Quantum Signatures[END_REF] and branch tracing attacks [START_REF] Tibouchi | One Bit is All It Takes: A Devastating Timing Attack on BLISS's Non-Constant Time Sign Flips[END_REF]. A common approach in PQC is to construct a cryptographic scheme secure against chosen plaintext attacks then making it secure against chosen ciphertext attacks using a generic transformation. Such transformation can lead to key-recovery attacks if not constant time [START_REF] Guo | A Key-Recovery Timing Attack on Post-quantum Primitives Using the Fujisaki-Okamoto Transformation and Its Application on FrodoKEM[END_REF].

Insights

The majority of recent publications reproduce vulnerabilities which have been long known, but in new context and libraries. Analysis should not focus on detecting constant-time violations in their code, but rather detect their incorrect use in the wider code-base. Test methodologies like TriggerFlow [START_REF] Gridin | Triggerflow: Regression Testing by Advanced Execution Path Inspection[END_REF] are promising in this regard, and complementing them with fuzzing approaches could allow for wider exploration of cryptographic libraries. New vulnerabilities are not found in usual cryptographic primitives directly, but in newer protocols/schemes, or in lower-level utility functions. Detection tools thus need to be able to fully analyze programs, including utility functions, and scale to full protocol runs.

Tools considered

The rest of this paper is dedicated to comparing these approaches and characterizing them with regards to known vulnerabilities. We restrict ourselves to five tools: Abacus [START_REF] Bao | Abacus: Precise Side-Channel Analysis[END_REF], Binsec/Rel [START_REF] Daniel | Binsec/Rel: Efficient Relational Symbolic Execution for Constant-Time at Binary-Level[END_REF], MicroWalk-CI [START_REF] Wichelmann | Microwalk-CI: Practical Side-Channel Analysis for JavaScript Applications[END_REF], dudect [START_REF] Reparaz | Dude, is my code constant time?[END_REF], and ct-grind [START_REF] Langley | Ctgrind[END_REF]. Together, they are representative of the diversity of methods of the literature and used in practice, with a mix of static and dynamic tools. The first three tools are from academic publications, while the last two are known to be used by developers [START_REF] Jancar | They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks[END_REF]. Our selection is based on availability, ability to analyze binary code, scalability (from the claims in their publications), and guarantees provided by the tool.

Abacus

Abacus [START_REF] Bao | Abacus: Precise Side-Channel Analysis[END_REF] first obtains an execution trace by running the target program with concrete inputs using the binary instrumentation framework Intel Pin [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF]. Then, the SE engine replays the trace with the secret data set to symbolic values. Formulas are generated only for instructions manipulating secret values, otherwise concrete values are used. A control flow or memory access is represented as a function 𝑓 of the secret symbolic inputs 𝑘 and public concrete inputs 𝑚. The problem of whether an instruction violates CT is reformulated as whether ∃𝑘 1 , 𝑘 2 ∈ 𝐾, 𝑓 (𝑘 1 , 𝑚) ≠ 𝑓 (𝑘 2 , 𝑚), with 𝐾 the set of possible secrets. Contrary to prior work using DSE [START_REF] Wang | CacheD: Identifying Cache-Based Timing Channels in Production Software[END_REF],

Abacus does not use SMT solvers but randomly picks values for 𝑘 1 and 𝑘 2 , as it is often sufficient to trigger the leakage.

In practice, the developer must indicate which variable is secret either through an annotation or writing a custom Pin tool. We noted a flaw in that Abacus only registers the first annotation and ignores the subsequent ones. As such, for our experiments, we wrote a Pin tool letting us mark as secret an arbitrary number of buffers of arbitrary length. Finally, Abacus computes an estimation of the number of bits leaked.

Binsec/Rel

Binsec/Rel [START_REF] Daniel | Binsec/Rel: Efficient Relational Symbolic Execution for Constant-Time at Binary-Level[END_REF] uses SE for bug-finding and bounded-verification of constant-time at binary level. It lifts the target binary to an IR, performs SE along all program paths, and checks that control-flow and memory accesses do not depend on secret. More precisely, Binsec/Rel uses relational SE to model two executions of a program in the same SE instance, with the same public input but distinct secret inputs. SMT queries allow checking whether these pairs of path can diverge on control-flow or memory addresses. If a query is satisfiable, the program is insecure and the solver returns a counterexample triggering the vulnerability. Conversely, if all queries are unsatisfiable and the exploration is exhaustive, the program is secure. In practice, these queries are expensive, so Binsec/Rel uses optimizations to spare unsatisfiable queries, making it scale on secure programs. However, satisfiable queries may remain a bottleneck on insecure programs. Binsec/Rel2. The Binsec/Rel team has recently developed a second version, Binsec/Rel2 [START_REF]BinsecRel2[END_REF], with better general performance and architecture support (based on the latest version of the symbolic engine), easier set up (core-dump based initialization), and dedicated optimization for satisfiable queries-based on evaluation over prechosen concrete values.

MicroWalk-CI

MicroWalk [START_REF] Wichelmann | MicroWalk: A Framework for Finding Side Channels in Binaries[END_REF] records multiple executions of the target function under different inputs using Intel Pin. The recorded trace contains branch targets and memory addresses encountered during the execution. Mutual information scores are then computed between the leakage trace and the input set, giving a quantification of the number of input bits leaked. MicroWalk offers various MI score granularity/performance tradeoffs, ranging from whole program MI-giving a coarse leakage quantification-to single instructionsfor exact leakage localization. MicroWalk-CI [START_REF] Wichelmann | Microwalk-CI: Practical Side-Channel Analysis for JavaScript Applications[END_REF] adds support for Javascript. Special attention has been paid to the framework's usability, with human readable reports compatible with CI features.

dudect

dudect [START_REF] Reparaz | Dude, is my code constant time?[END_REF] detects timing leakage through repeated timing measurements and comparison using a statistical test. The binary is executed under two different classes of secret inputs: one set to constant values and one set to values randomly selected before each measurement. The execution timings of the target function are then recorded by probing CPU cycle counters. Measurements above a certain percentile 𝑝 are assumed to be noise and are removed. An online t-test is then applied to determine whether the two distributions are distinguishable, with leakage being reported if the value passes a predefined threshold. While this approach is simple and easy to deploy, it only gives guarantees up to a certain number of measurements.

ctgrind

ctgrind [START_REF] Langley | Ctgrind[END_REF] uses Valgrind's memory error detector, Memcheck, to detect potential side-channel leakages. As Memcheck already detects branches and memory accesses computed on uninitialized memory, side-channel vulnerabilities can be found by marking secret variables as undefined, through a specific code annotation. Internally, Memcheck detects errors by shadowing every bit of data manipulated by the program with a definedness bit V [START_REF] Seward | Using Valgrind to Detect Undefined Value Errors with Bit-Precision[END_REF], propagated throughout the execution similarly to a taint analysis and checked when computing an address or a jump.

Applied to side-channel analysis however, this approach yields a considerable number of false positives, as errors unrelated to secret values are also reported. Still, ctgrind is particularly popular in cryptographic libraries for its simplicity and ease of deployment: ctgrind is used by 5 out of the 6 cryptographic libraries performing CT tests as reported by [START_REF] Jancar | They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks[END_REF].

Unified benchmark

To fairly compare the scalability and vulnerabilities reported by existing approaches (RQ1), we create a unified benchmark, comprised of representative cryptographic operations from 3 libraries, totaling 25 benchmarks. Table 2 presents our results.

Description and setup

Libraries. We include OpenSSL [START_REF]OpenSSL[END_REF], as it is one of the most popular cryptographic library [START_REF] Nemec | Measuring Popularity of Cryptographic Libraries in Internet-Wide Scans[END_REF] and has a long history of side-channel vulnerabilities. MbedTLS [START_REF]Mbed TLS[END_REF] is another popular library, particularly for embedded targets. Its maintainers consider side-channel attacks in their threat model, though it is a work in progress relevant mainly for new code. BearSSL [START_REF] Pornin | BearSSL[END_REF] is a smaller library with an emphasis on ease of deployment and security. In particular, the author makes clear claims on which functions are constant-time, which helps us establish a ground truth for our benchmark. For each of these libraries we pick the latest versions at the times of experiment (3.0.5, 3.1 and 0.6 respectively), and compile the libraries both as static 32 and 64-bits objects, to meet the detection tool requirements. While we keep library configurations close to their defaults, for MbedTLS, we disable support for VIA PadLock instructions and AES table generation code.

Algorithms. We chose widely-used cryptographic operations from both symmetric and asymmetric schemes. We target AES encryption, in both CBC and the authenticated GCM mode, as well as the Poly1305-Chacha20 AEAD scheme. We target RSA decryption with both PKCS#1 v1.5 and OAEP padding scheme. ECDSA signature generation using P-256 and EdDSA signature generation using Curve25519 are also included.

Implementations.

A library can include different implementations of a single algorithm with differing impacts on side-channel leakage, notably for AES. For OpenSSL we include the vulnerable T-table implementation and the secure vector permutation (VP) implementation. For BearSSL, we include its T-table implementation and its constant-time implementation, based on a bit-slicing (BS) approach. Such implementations also exist for OpenSSL, but not for our 32-bits configuration. Finally, we add a benchmark using OpenSSL's EVP API, which is the intended entry point for developers and dynamically selects the best implementation available.

Limits. These common operations are not all supported in the same way. BearSSL only supports RSA decryption with OAEP padding, where only OpenSSL supports EdDSA. While we favor deterministic ECDSA as it derives the secret from the key without any PRNG, OpenSSL does not support it at the time of our experiments [START_REF]Implement deterministic ECDSA sign (RFC6979[END_REF]. We thus use the non-deterministic version.

Benchmark design. We limit ourselves to simple test harnesses, limiting the number of auxiliary operations before the target cryptographic operation in order to avoid introducing extra issues in terms of scalability, instruction support, or non-determinism. Only the input of the target operation are marked as secret. For symmetric ciphers we mark the shared key as secret, for RSA the secret key parameters (including the CRT parameters), for elliptic curves the secret scalar. For each benchmark, the arrays containing secret values are also marked as such at the beginning of the main. While ideally we would run all the selected detection tools on the same binary for a given benchmark, the tools have conflicting requirements. As such, for each benchmark we produce both a 32-bits and a 64-bits version, the latter being used only by Microwalk.

Evaluation protocol. We compare the numbers of vulnerabilities found by each tool and the running times of the analysis. All experiments are run on a laptop equipped with an i7-8650U processor running Ubuntu 20.04 LTS. For Abacus, Microwalk and both versions of Binsec/Rel, the vulnerability count is taken directly from the tool output, corresponding to the number of unique leaky instructions. For ctgrind, some post-processing is needed on the output.

First, ctgrind reports a single leaking instruction multiple times if it is reached in different contexts, so we deduplicate the reported error count. Second, as ctgrind is based on Valgrind, errors unrelated to constant-time are also be reported. For example, on statically linked programs, Valgrind reports problems from glibc functions [START_REF]Bug 200535 -Valgrind flags lots of uninitialized locations with programs compiled with "-static[END_REF]. To remedy this, we generate a suppression file by first running the program without annotating the secret. As a result, errors independent of the secret are not reported. The running time of the analysis is measured as the total time from first invoking the tool to its exit. For Binsec/Rel, this includes generation of the coredump when needed. For Abacus, this includes the time needed to record a trace using Pin, as such our running times are generally longer than those in the original publication [START_REF] Bao | Abacus: Precise Side-Channel Analysis[END_REF]. For dudect, computations of the t-test score are done in batches of 5000 measurements, repeated until the analysis either finishes or times out. New inputs are generated for each measurement. We additionally thrash the cache by accessing a large array between each run of the targeted algorithm to limit cache side-effects. Microwalk is set up to generate 16 traces, as recommended by the authors [START_REF] Wichelmann | Microwalk-CI: Practical Side-Channel Analysis for JavaScript Applications[END_REF]. We supply for each trace a different set of inputs and use the number of unique leaking instructions reported by the tool. : the tool crashed. : the analysis timed-out after 3600 s. †: the analysis terminated early (e.g., unsupported instructions). ‡: the analysis starts from a core-dump (Binsec/Rel2 only)

Results and discussion

Table 2 reports, for each tool, the running time of the analysis (T) and the number of unique vulnerabilities (#V) found when appropriate. We also report in column S whether the analysis finds the overall program is secure ( ), insecure ( ) or if no statement can be made ( ). As dynamic tools only model a limited number of executions, they can only report and . Static tools can report and , reporting when the analysis times out or stops early without finding vulnerabilities. For Binsec/Rel we also report the time required to find a first vulnerability (t). Symmetric primitives. For simpler symmetric cryptography such as AES-CBC and authenticated schemes like AES-GCM or Poly1305-Chacha20, tools that report a number of vulnerabilities tend to agree with each other. In general, the tools scale reasonably well on such primitives. Implementations using constant-time techniques such as vector permutations (VP) or bit-slicing (BS) are reported as secure while those based on table lookups (T) yield a consistent number of vulnerabilities. dudect can determine that these implementations are insecure, but the OpenSSL T-table implementation as it preloads tables in the cache before accessing them.

While these numbers are consistent, there are two notable exceptions. First, ctgrind and Microwalk show less vulnerabilities in MbedTLS AES-GCM implementation than other tools. For the former, this discrepancy stems from a bug within Valgrind, where upon encountering two consecutive vulnerable memory accesses, the error reporting for one will "shadow" the other. This is relevant in this benchmark as MbedTLS' GHASH function is implemented using 64-bit integers which, in 32-bit, are compiled into two mov instructions. We have not encountered this issue in other benchmarks. For the latter, this could be explained by the fact that Microwalk does not report CT violation where the leakage quantified is too small, whereas tools not providing such quantification will report these in any case. Second, in the OpenSSL's EVP implementation of AES-GCM, ctgrind reports a large number of vulnerabilities while other tools do not. For Binsec/Rel2, this is unsurprising as its analysis stops upon reaching unsupported AES-NI instructions used by the EVP implementation. The vulnerabilities reported by ctgrind are all located in the GHASH implementation, which employs table look-ups to perform multiplications in 𝐺𝐹 (2 128 ), a potential vulnerability identified in [START_REF] Käsper | Faster and Timing-Attack Resistant AES-GCM[END_REF]. Microwalk reports a few vulnerabilities as well, located in functions used to select which implementations to run Asymmetric primitives. In the case of more complex asymmetric cryptography, results vary highly between tools. For Abacus, no vulnerabilities are found when the analysis finishes, however, we observe multiple crashes. Analyses often time out on both Binsec/Rel and Binsec/Rel2, only finding a handful of vulnerabilities. For OpenSSL and MbedTLS these vulnerabilities are located in BIGNUM conversion functions called before the target cryptographic operation. Such functions have been found to be vulnerable before [START_REF] Weiser | Big Numbers -Big Troubles: Systematically Analyzing Nonce Leakage in (EC)DSA Implementations[END_REF][START_REF] Yuan | CacheQL: Quantifying and Localizing Cache Side-Channel Vulnerabilities in Production Software[END_REF], we see here that they are also a source of scalability issues. For dudect, the need to generate inputs for each measurement is a significant bottleneck, in particular for RSA where key generation is a costly operation. As a result of slower key generation in MbedTLS and BearSSL, the respective RSA benchmarks time out before finishing a single set of measurements. In the case of ctgrind, analyses finishes very quickly, however the large number of vulnerabilities found makes interpreting these results complicated, with most vulnerabilities being found in BIGNUM functions. Microwalk provides similarly high vulnerability counts, though with analysis times in the order of minutes. We note that among these vulnerabilities we find again some related to implementation selection, in particular for OpenSSL.

Unsupported instructions. Unsupported instructions can have a crucial impact on the analysi' results. The vulnerable GHASH implementation is rarely reached in practice, as OpenSSL steers the execution to constant-time variants making uses of carry-less multiplication (CLMUL) instructions. However Valgrind emulates the results of cpuid to only include instruction sets it supports. Its analysis thus does not reach the CLMUL implementation, instead defaulting to a vulnerable function. The results we obtained with Abacus contrast with the authors' own RSA and ECDSA benchmarks [START_REF] Bao | Abacus: Precise Side-Channel Analysis[END_REF]. While the authors did not disclose which configurations were used to compile the libraries, disassembling their benchmarks shows that, at least for OpenSSL, assembly implementations were disabled. Such implementations are included in our benchmark, yielding SIMD instructions unsupported by Abacus. While in some cases these cause Abacus to crash, it is also possible they lead to under-tainting, explaining the low vulnerability counts.

False positives. Both ctgrind and Binsec/Rel2 report violations in RSA-bearssl and ECDSA-bearssl, which is surprising given BearSSL constant-time policies. A closer inspection reveals that the RSA implementation computes the actual bit length of RSA primes by counting the number of nonzero bytes, triggering secret-dependent control-flow, while ECDSA performs an early exit if the key is not well-defined. While these violations are technically true CT violations, they are not exploitable vulnerabilities. Microwalk on the other hand does not report these CT violations as they do not result in differences in traces for the inputs we used. In both cases, Binsec/Rel2 reports a subset of the vulnerabilities reported by ctgrind, which can be explained by a different notion of unique vulnerability between both tools. Indeed, Binsec/Rel2 only reports a single violation when leaking the same data on different locations, whereas ctgrind reports multiple locations leaking the same data. Finally, violations are reported in RSA and ECDSA implementations of OpenSSL and MbedTLS, however these implementation use blinding, making the violations unexploitable in practice. This non-determinism could introduce differences in traces which can be reported as vulnerabilities by tools like Microwalk. We note however that Microwalk features a way to spoof the outputs of rdrand which can alleviate this problem.

Leakage quantification. We did not report the numbers given by Abacus and MicroWalk, as there is no standard way of computing leakage quantification or determining their severity. Moreover, leakage quantification is far from a practical notion of exploitability, as even a single bit of leakage or less can be exploited [START_REF] Aranha | LadderLeak: Breaking ECDSA with Less than One Bit of Nonce Leakage[END_REF].

Improvements over Binsec/Rel. Binsec/Rel may struggles to fully analyze insecure programs, even simpler ones like AES. This issue is alleviated in Binsec/Rel2 thanks to the chosen value optimization. is able to finish analyzing symmetric primitives in times comparable to even dynamic tainting approaches like ctgrind, finding the same number of vulnerabilities. While scalability remains an issue for asymmetric primitives, Binsec/Rel2 is able to analyze the OpenSSL implementation of Ed25519 faster than a dynamic method like Abacus. The ability to start the analysis from a coredump solves initialization issues (e.g., global function pointers) that cannot be avoided in Binsec/Rel, while limiting the amount of instrumentation required.

Case-study: vulnerability validation

We now employ the tools described in Section 6 to determine if the vulnerabilities in Section 5 could have been discovered automatically (RQ2), and determine features that are missing from existing frameworks to find them (RQ3).

Description and setup

Targeted vulnerabilities. We consider vulnerabilities from three publications: [START_REF] Cabrera Aldaya | Cache-Timing Attacks on RSA Key Generation[END_REF] focused on RSA key generation in OpenSSL 1.0.2k, [START_REF] García | Certified Side Channels[END_REF] focused on key format handling in OpenSSL 1.1.1a, and MbedTLS 2.18.1 (in particular P256 keys for the former and RSA keys for the latter), and [START_REF] Daniel Genkin | May the Fourth Be With You: A Microarchitectural Side Channel Attack on Several Real-World Applications of Curve25519[END_REF] focused on ECDH decryption in Libgcrypt 1.7.6. Following our typology (Section Section 5), the first two papers describe vulnerabilities stemming from functions known to be vulnerable, but accidentally used in a new context, while the third one represents a new vulnerability.

Benchmark design. While we are interested in checking for CT violations in these vulnerable functions, a library developer without prior knowledge is unlikely to analyze the right function (e.g., GCD, modular exponentiation). More realistically, such developer would instead check the larger context in which this function is used (e.g., RSA key generation). As such, we are interested in detecting CT violations not just in the vulnerable function itself, but also in its calling context, where detection tools might struggle with scalability, or other usability issues. We thus run the detection tools on simple programs calling the vulnerable functions directly and the higher-level operation.

Evaluation protocol. We compare the number of vulnerabilities and running times of the analysis from Binsec/Rel2, Abacus, ctgrind and dudect with their configurations from Section 7.

Results and discussion

Table 3 reports, for each tool, the running time of the analysis (T) and the number of vulnerabilities (#V) found when available. Abacus report vulnerabilities only upon finishing the analysis, and thus reports none when there is a timeout. Additionally for each tool, we report whether a vulnerability useful for the publications' attacks is reported (V). The higher-level operations are listed in bold, while the vulnerable functions used are listed immediately below the corresponding operation. General results. In general, Binsec/Rel2, ctgrind, and dudect report the same programs as secure (i.e., P256 sign and RSA keygen), and the rest as insecure, with the exception of the modular reduction in Libgcrypt, for which Binsec/Rel2 times-out without finding vulnerabilities. Microwalk however finds almost all programs insecure, with error counts wildly different from ctgrind. In contrast, Abacus only reports a single program as insecure. This is possibly due to unsupported instructions, once again limiting the tool ability to properly taint secret data. Additionally, the analysis will times out in multiple cases, returning no results. The ability to output violations as soon as they are found would, thus, greatly improve usability. In general, we find that ctgrind and Microwalk in particular are able to find most of the relevant vulnerabilities in both the target functions and their calling contexts. While the relevant vulnerabilities can generally be found, the high number of reported vulnerabilities, in particular for ctgrind, complexifies the interpretation of these results. We note that many of these vulnerabilities stem from BIGNUM manipulation functions. These CT violations are often already known by developers, and so, as pointed out by Jancar et al. [START_REF] Jancar | They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks[END_REF], the ability to ignore violations in parts of the code would represent a clear usability improvement. Additionally, both ctgrind and Microwalk report vulnerabilities found in standard functions (e.g., malloc). These are usually ignored by both tools, however they are included as our binaries are statically linked. Contrasting with ctgrind, Binsec/Rel2 found few vulnerabilities. We note that the analysis often gets stuck early in the program, during BIGNUM conversion steps, and times out. Specifically, benchmarks involving GCD computations and modular inversion are susceptible to path explosion, a common limitation of static SE, which leads to unexplored program behaviors.

V #V S T (s) V #V S T (s) V #V S T (s) V #V S T (
Implicit flows. Implicit flows happen when the value of a variable may differ depending on secret-dependent control flow. While none of the tools we considered explicitly tracks implicit information flows, these can produce trace difference which Microwalk can detect. Our benchmarks shows that ignoring them leads to an underestimation of the number vulnerabilities in cryptographic programs. For example, MbedTLS implements a comparison function in which the return value depends on whether a secret-dependent branch is taken (a typical case of an implicit flow). MbedTLS GCD Internal secrets. The way the secret is utilized in some operations can pose problems for detection tools. For RSA key generation, there is by definition, no initial values to mark as secret. For P256 signature generation, the secret exploited in publications is the cryptographic nonce generated internally. Other operations making use of PRNG are also affected similarly. In both of these cases our "black-box" experimental setup does not allow us to mark the secret appropriately and as such, the detection tools we used cannot find vulnerabilities. In practice, it is possible to mark such secrets by deviating from our setup. For example, the authors of Abacus wrote a special pintool to mark the cryptographic nonce as secret, Surprisingly, Microwalk is able to find the vulnerabilities in these functions despite no clear way to correlate the traces with the inputs. We conjecture that this is due to trace differences induced by the randomness of the generation process. but their solution lacks generality. Another option is to add annotations within a library's source code, something that developers are generally opposed to. For processes involving random number generation, a tool could consider the output of the entropy source as an input to the target function.

Recommendations

We now formulate recommendations to the research community and to cryptographic library developers based on the insights obtained with our experimental evaluation.

Recommendations to research community

R1. Support of SIMD instructions. Research prototypes like Abacus often only support basic x86 instructions. However, as shown in Section 7, libraries heavily use SIMD instruction sets (e.g., AVX2), now commonly supported in CPUs. These implementations are now typically selected in priority. As such, supporting SIMD instructions in detection tools is now crucial, and evaluating a tool on implementations specifically selected to not use SIMD instructions may mislead developers on the tool usability.

R2. Support of implicit information flows. Future tools should investigate the possibility of detecting CT violations stemming from implicit information flows, in particular for static tools and dynamic tools using a single trace. We argue that by ignoring them, a detection tool can underestimate the amount of vulnerabilities, giving developers a false sense of security. Yet, considering implicit flows is challenging and can impact scalability. Only three tools explicitly support implicit flows [START_REF] Jiang | Cache Refinement Type for Side-Channel Detection of Cryptographic Software[END_REF][START_REF] Rodrigues | Sparse representation of implicit flows with applications to side-channel detection[END_REF][START_REF] Yuan | CacheQL: Quantifying and Localizing Cache Side-Channel Vulnerabilities in Production Software[END_REF], while trace-comparison-based dynamic tools might only provide a partial support.

R3. Support of internal secrets. The community should investigate side-channel vulnerabilities in operations where the secret is generated internally, such as key generation and PRNG [START_REF] Cabrera Aldaya | Cache-Timing Attacks on RSA Key Generation[END_REF][START_REF] Cohney | Pseudorandom Black Swans: Cache Attacks on CTR_DRBG[END_REF][START_REF] Puddu | Frontal Attack: Leaking Control-Flow in SGX via the CPU Frontend[END_REF]. None of the tools in our classification explicitly support them, although in practice we found Microwalk promising in this regards. The ability to set the output of an entropy source, beyond a clear usability advantage, could be extended to be marked as secret. Recently, a test methodology to detect usage of vulnerable functions in key generation was proposed [START_REF] Gridin | Triggerflow: Regression Testing by Advanced Execution Path Inspection[END_REF], however it requires knowing vulnerable points in advance.

R4. Support for randomization-based defense. Blinding introduces randomization during computations to hinder inference of secrets via side-channels [START_REF] Joye | Protections against Differential Analysis for Elliptic Curve Cryptography[END_REF]. It poses an additional challenge for detection tools as the leakage does depend on the secret, but not in an exploitable way, leading to false positives. Only 3 out of the 34 tools we considered in Table 1 support blinding.

R5. Usage of a standardized benchmark. We recommend the community to adopt a standardized benchmark of cryptographic implementations to evaluate side-channel detection tools. Such benchmark would facilitate comparing detection tools to one another, in particular in terms of usability and scalability. We thereby propose to the community our benchmark, which can be readily adopted and extended in the future.

R6. Improve usability. As pointed out in Section 8, reporting results before the analysis end is crucial for benchmarks that times out. We also echo a point made in [START_REF] Jancar | They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks[END_REF]: being able to ignore vulnerabilities from some parts of the code helps interpreting the results, particularly for approaches like ctgrind. For static tools, the ability to write stubs adding limited support for system calls and dynamic allocation was essential in our experiments with Binsec/Rel, as we cannot expect developers to avoid using them. The ability to start the analysis from a coredump (as in Binsec/Rel2) also greatly simplifies the instrumentation needed to initialize the analysis.

Recommendations to developers

R7. Make libraries more analysis friendly. Static analysis tools often require more instrumentation than dynamic ones. In particular, the selection of implementations at run-time poses a challenge. While for experiments using Binsec/Rel2 we were able to bypass this issue by initializing the memory from a coredump, we can only analyze one implementation and have little control over which one is chosen. We recommend that libraries expose in their API, at least for testing purposes, functions to directly call different implementations, as done for example by OpenSSL AES implementations.

Conclusion

We surveyed and classified state-of-the-art side-channel detection tools, and propose a unified benchmark allowing fair experimental comparison. Our findings show that existing tools can still struggle to analyze complex primitives and can miss vulnerabilities. We issued recommendations for the research and developer community to improve existing tools and encourage their usage. Beyond these recommendations we note that the research communities for microarchitectural and physical side-channel detection both evolved independently, with little overlap [START_REF] Buhan | SoK: Design Tools for Side-Channel-Aware Implementations[END_REF]. With the advent of frequency scaling side-channels like Hertzbleed [START_REF] Wang | Hertzbleed: Turning Power Side-Channel Attacks Into Remote Timing Attacks on x86[END_REF] extracting a timing side-channel from power consumption, this boundary is blurred. To properly address such vulnerabilities, the two communities should focus on bridging the gap between them, borrowing insights from physical side-channel detection and move beyond the constant-time model.

1

 1

  1 https://github.com/ageimer/sok-detection/ 2 Preliminaries

Table 1 :

 1 Comparison table of vulnerability detection frameworks.

	Ref	Year Tool	Type	Methods	Scal. Policy Sound Input	L W E B Available
	[85]	2010 ct-grind	Dynamic Tainting	CT	Binary	✓		✓
	[15]	2013 Almeida et al.	Static	Deductive verification	CT	C source
	[55]	2013 CacheAudit	Static	Abstract interpretation	CO	Binary		✓	✓
	[22]	2014 VirtualCert	Static	Type system	CT	C source		✓	✓
	[70]	2015 Cache Templates Dynamic Statistical tests	CO	Binary	✓		✓
	[13]	2016 ct-verif	Static	Logical verification	CT	LLVM			✓
	[107] 2016 FlowTracker	Static	Type system	CT	LLVM	✓		✓
	[56]	2017 CacheAudit2	Static	Abstract interpretation	CT	Binary		✓
	[28]	2017 Blazy et al.	Static	Abstract interpretation	CT	C source
	[17]	2017 Blazer	Static	Decomposition	CR	Java	✓
	[48]	2017 Themis	Static	Logical verification	CR	Java	✓ ✓
	[127] 2017 CacheD	Dynamic DSE	CO	Binary	✓ ✓
	[136] 2017 STACCO	Dynamic Trace diff	CR	Binary	✓		✓
	[106] 2017 dudect	Dynamic Statistical tests	CC	Binary			✓
	[117] 2018 CANAL	Static	SE	CO	LLVM	✓		✓
	[47]	2018 CacheFix	Static	SE	CO	C	✓ ✓		✓
	[34]	2018 CoCo-Channel	Static	SE, tainting	CR	Java	✓
	[19]	2018 SideTrail	Static	Logical verification	CR	LLVM	✓ ✓ ✓	✓
	[114] 2018 Shin et al.	Dynamic Statistical tests	CO	Binary	✓
	[132] 2018 DATA	Dynamic Statistical tests	CT	Binary	✓	✓	✓
	[133] 2018 MicroWalk	Dynamic MIA	CT	Binary	✓	✓	✓
	[110] 2019 STAnalyzer	Static	Abstract interpretation	CT	C	✓		✓
	[95]	2019 DifFuzz	Dynamic Fuzzing	CR	Java	✓		✓
	[126] 2019 CacheS	Static	Abstract interpretation, SE	CT	Binary	✓ ✓
	[35]	2019 CaSym	Static	SE	CO	LLVM	✓ ✓
	[54]	2020 Pitchfork	Static	SE, tainting	CT	LLVM	✓ ✓		✓
	[66]	2020 ABSynthe	Dynamic Genetic algorithm, RNN	CR	C source	✓		✓
	[72]	2020 ct-fuzz	Dynamic Fuzzing	CT	Binary	✓ ✓		✓
	[51]	2020 Binsec/Rel	Static	SE	CT	Binary	✓ ✓		✓
	[20]	2021 Abacus	Dynamic DSE	CT	Binary	✓	✓	✓
	[74]	2022 CaType	Dynamic Type system	CO	Binary	✓	✓
	[134] 2022 MicroWalk-CI	Dynamic MIA	CT	Binary, JS ✓	✓	✓
	[140] 2022 ENCIDER	Static	SE	CT	LLVM	✓ ✓		✓
	[141] 2023 CacheQL	Dynamic MIA, NN	CT	Binary	✓	✓ ✓	✓ †
	(D)SE: (Dynamic) Symbolic Execution, MIA: Mutual Information Analysis, (R)NN: (Recurrent) Neural Network, E: estimation of the number of
	bits leaked, L: origin of the leakage, W: witness triggering the vulnerability, B: support for blinding.

† Not available at the time of writing.

Table 2 :

 2 Vulnerability detection. #V: number of reported vulnerabilities, S: status ( secure; insecure; unknown), t: time to first bug in seconds, T: analysis time in seconds.

			Binsec/Rel			Binsec/Rel2		Abacus		ctgrind	Microwalk	dudect
	Benchmarks	#V S	t (s)	T (s)	#V S t (s) T (s) #V S	T (s)	#V S T (s) #V S	T(s)	S	T (s)
	AES-CBC-bearssl (T)	20	0.05		36	0.02 0.10 36	3.65	36	0.16 36	1.39	100.51
	AES-CBC-bearssl (BS)	0	-	16.77	0	-	0.31	0	10.69	0	0.17	0	1.55
	AES-GCM-bearssl (T)	20	0.05		36	0.02 0.22 36	6.23	36	0.18 36	1.51	8.69
	AES-GCM-bearssl (BS)	0	-	53.32	0	-	0.48	0	14.79	0	0.17	0	1.73
	AES-CBC-mbedtls (T)	20	0.1		68	0.03 0.17 68	5.73	68	0.19 68	1.54	0.63
	AES-GCM-mbedtls (T)	20	0.27		84	0.05	0.4	84	261.76	76	0.19 71	1.90	0.89
	AES-CBC-openssl (EVP)	0	-		0 † ‡	-	21.92 0	103.59	0	0.66	9	5.35
	AES-GCM-openssl (EVP)	0	-		0 † ‡	-	21.19 0	104.27	70	0.71	8	5.66
	AES-CBC-openssl (T)	20	0.05		36	0.02 0.16 36	3.02	36	0.18 20	1.38
	AES-CBC-openssl (VP)	0 †	-	0.06	0 ‡	-	0.59	0	1.01	0	0.19	0	1.68
	PolyChacha-bearssl (CT)	0	-	9.72	0	-	0.18	0	1.3	0	0.16	0	1.43
	PolyChacha-bearssl (SSE2) 0 †	-	0.05	0	-	0.11	0	1.17	0	0.15	0	1.34
	PolyChacha-mbedtls	0	-	18.62	0	-	0.49	0	5.02	0	0.18	0	2.95
	PolyChacha-openssl (EVP) 0	-		0 ‡	-	21.55		100.19	0	0.67	8	5.41
	Chacha20-openssl	0	-	0.77	0	-	0.09	0	3.77	0	0.15	0	1.36
	Poly1305-openssl	0	-	0.26	0 ‡	-	0.35		1.19	0	0.17	0	1.70
	RSA-bearssl (OAEP)	0	-		2	0.03			356.41	87	0.57	0	146.52
	RSA-mbedtls (PKCS)	1	1.60		5 ‡	0.21			2193.2	39	0.96 137	826.23
	RSA-mbedtls (OAEP)	1	1.46		5 ‡	0.21			2203.89 48	0.98 137	847.27
	RSA-openssl (PKCS)	1	26.50		1 ‡	0.44		0	551.72 321	1.32 46	52.06	618.73
	RSA-openssl (OAEP)	1	29.02		1 ‡	0.46			535.91 546	1.73 61	59.90	771.3
	ECDSA-bearssl	2	1.82		2	0.84		0	246.62	7	0.41	0	109.31
	ECDSA-mbedtls	0	-	0.54	0 † ‡	-	0.19	0	467.11	50	0.81 132	314.26	224.30
	ECDSA-openssl	0	-	2252.36 1 ‡	51.		0	202.72	14	1.22 28	13.76
	EdDSA-openssl	0	-		0 ‡	-	25.63 0	59.87	0	1.03	8	9.86

Table 3 :

 3 Vulnerability detection. V: whether the right vulnerability is found #V: number of reported vulnerabilities, S: status ( secure; insecure; unknown), T: analysis time in seconds.

	Binsec/Rel2	Abacus	ctgrind	Microwalk	dudect
	Benchmarks

  function uses the result of this comparison function in a (secretdependent) conditional jump. As a result, ctgrind only reports the secret-dependent branch in the comparison function as vulnerable, but not the one in the GCD computation. While a CT violation is still reported, a developer is not able to fully appreciate how vulnerable the program is without taking into account these implicit flows. Microwalk on the other hand, is able to detect the difference and correctly reports the conditional jump in GCD as vulnerable. This illustrates a clear advantage that trace comparison methods have over other dynamic methods.

Acknowledgments

This work benefited from the support of the ANR-19-CE39-0007 MIAOUS, ANR-20-CE25-0009 TAVA, PEPR PP Secureval and PEPR PP Rev projects.