Lune

PLDI2020Top-tier venue

Constant-time foundations for the new spectre era

Sunjay Cauligi, Craig Disselkoen, Klaus von Gleissenthall, Dean M. Tullsen, Deian Stefan, Tamara Rezk, Gilles Barthe

Abstract

The constant-time discipline is a software-based countermeasure used for protecting high assurance cryptographic implementations against timing side-channel attacks. Constanttime is effective (it protects against many known attacks), rigorous (it can be formalized using program semantics), and amenable to automated verification. Yet, the advent of microarchitectural attacks makes constant-time as it exists today far less useful.

This paper lays foundations for constant-time programming in the presence of speculative and out-of-order execution. We present an operational semantics and a formal definition of constant-time programs in this extended setting. Our semantics eschews formalization of microarchitectural features (that are instead assumed under adversary control), and yields a notion of constant-time that retains the elegance and tractability of the usual notion. We demonstrate the relevance of our semantics in two ways: First, by contrasting existing Spectre-like attacks with our definition of constant-time. Second, by implementing a static analysis tool, Pitchfork, which detects violations of our extended constant-time property in real world cryptographic libraries.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

57 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • "They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks cites Spectre Attacks: Exploiting Speculative Execution
  • "They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing Attacks cites Constantine: Automatic Side-Channel Resistance Using Efficient Control and Data Flow Linearization
  • Constantine: Automatic Side-Channel Resistance Using Efficient Control and Data Flow Linearization cites Spectre Attacks: Exploiting Speculative Execution
  • Constantine: Automatic Side-Channel Resistance Using Efficient Control and Data Flow Linearization cites ZombieLoad: Cross-Privilege-Boundary Data Sampling
  • Constantine: Automatic Side-Channel Resistance Using Efficient Control and Data Flow Linearization cites RIDL: Rogue In-Flight Data Load
  • Constantine: Automatic Side-Channel Resistance Using Efficient Control and Data Flow Linearization cites Meltdown: Reading Kernel Memory from User Space
  • ZombieLoad: Cross-Privilege-Boundary Data Sampling cites Spectre Attacks: Exploiting Speculative Execution
  • GoFetch: Breaking Constant-Time Cryptographic Implementations Using Data Memory-Dependent Prefetchers cites Spectre Attacks: Exploiting Speculative Execution
  • GoFetch: Breaking Constant-Time Cryptographic Implementations Using Data Memory-Dependent Prefetchers cites Meltdown: Reading Kernel Memory from User Space
  • RIDL: Rogue In-Flight Data Load cites Spectre Attacks: Exploiting Speculative Execution
  • RIDL: Rogue In-Flight Data Load cites Meltdown: Reading Kernel Memory from User Space
  • Meltdown: Reading Kernel Memory from User Space cites Spectre Attacks: Exploiting Speculative Execution
  • Swivel: Hardening WebAssembly against Spectre cites Spectre Attacks: Exploiting Speculative Execution
  • Swivel: Hardening WebAssembly against Spectre cites ZombieLoad: Cross-Privilege-Boundary Data Sampling
  • Swivel: Hardening WebAssembly against Spectre cites RIDL: Rogue In-Flight Data Load
  • Swivel: Hardening WebAssembly against Spectre cites Meltdown: Reading Kernel Memory from User Space
  • SoK: Practical Foundations for Software Spectre Defenses cites Spectre Attacks: Exploiting Speculative Execution
  • SoK: Practical Foundations for Software Spectre Defenses cites ZombieLoad: Cross-Privilege-Boundary Data Sampling
  • SoK: Practical Foundations for Software Spectre Defenses cites Meltdown: Reading Kernel Memory from User Space
  • SoK: Practical Foundations for Software Spectre Defenses cites Swivel: Hardening WebAssembly against Spectre
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers57

  1. Swivel: Hardening WebAssembly against SpectreShravan Narayan, Craig Disselkoen, Daniel Moghimi, Sunjay Cauligi et al.USENIX Security 2021 · 74 citations
  2. "They're not that hard to mitigate": What Cryptographic Library Developers Think About Timing AttacksJan Jancar, Marcel Fourné, Daniel De Almeida Braga, Mohamed Sabt et al.S&P 2022 · 61 citations
  3. SoK: Practical Foundations for Software Spectre DefensesSunjay Cauligi, Craig Disselkoen, Daniel Moghimi, Gilles Barthe et al.S&P 2022 · 59 citations
  4. GoFetch: Breaking Constant-Time Cryptographic Implementations Using Data Memory-Dependent PrefetchersBoru Chen, Yingchen Wang, Pradyumna Shome, Christopher W. Fletcher et al.USENIX Security 2024 · 52 citations
  5. Constantine: Automatic Side-Channel Resistance Using Efficient Control and Data Flow LinearizationPietro Borrello, Daniele Cono D'Elia, Leonardo Querzoni, Cristiano GiuffridaCCS 2021 · 43 citations

Builds on10

  1. Spectre Attacks: Exploiting Speculative ExecutionPaul Kocher, Jann Horn, Anders Fogh, Daniel Genkin et al.S&P 2019 · 2,435 citations
  2. Meltdown: Reading Kernel Memory from User SpaceMoritz Lipp, Michael Schwarz, Daniel Gruss, Thomas Prescher et al.USENIX Security 2018 · 1,456 citations
  3. SOK: (State of) The Art of War: Offensive Techniques in Binary AnalysisYan Shoshitaishvili, Ruoyu Wang, Christopher Salls, Nick Stephens et al.S&P 2016 · 1,085 citations
  4. ZombieLoad: Cross-Privilege-Boundary Data SamplingMichael Schwarz, Moritz Lipp, Daniel Moghimi, Jo Van Bulck et al.CCS 2019 · 464 citations
  5. RIDL: Rogue In-Flight Data LoadStephan van Schaik, Alyssa Milburn, Sebastian Österlund, Pietro Frigo et al.S&P 2019 · 408 citations

Related papers

  1. Enforcing Fine-grained Constant-time PoliciesBasavesh Ammanaghatta Shivakumar, Gilles Barthe, Benjamin Grégoire, Vincent Laporte et al.CCS 2022 · 11 citations
  2. Preservation of Speculative Constant-Time by CompilationSantiago Arranz-Olmos, Gilles Barthe, Lionel Blatter, Benjamin Grégoire et al.POPL 2025 · 8 citations
  3. Binsec/Rel: Efficient Relational Symbolic Execution for Constant-Time at Binary-LevelLesly-Ann Daniel, Sébastien Bardin, Tamara RezkS&P 2020 · 76 citations
  4. Formal verification of a constant-time preserving C compilerGilles Barthe, Sandrine Blazy, Benjamin Grégoire, Rémi Hutin et al.POPL 2020 · 77 citations
  5. Decompiling for Constant-Time AnalysisSantiago Arranz-Olmos, Gilles Barthe, Lionel Blatter, Youcef Bouzid et al.OOPSLA 2026 · 1 citation
Dusk over the sea between two cliffs drawn in fine vertical lines