Lune

USENIX Security2016Top-tier venue

Verifying Constant-Time Implementations

José Bacelar Almeida, Manuel Barbosa, Gilles Barthe, François Dupressoir, Michael Emmi

Abstract

The constant-time programming discipline is an effective countermeasure against timing attacks, which can lead to complete breaks of otherwise secure systems. However, adhering to constant-time programming is hard on its own, and extremely hard under additional efficiency and legacy constraints. This makes automated verification of constant-time code an essential component for building secure software.

We propose a novel approach for verifying constanttime security of real-world code. Our approach is able to validate implementations that locally and intentionally violate the constant-time policy, when such violations are benign and leak no more information than the public outputs of the computation. Such implementations, which are used in cryptographic libraries to obtain important speedups or to comply with legacy APIs, would be declared insecure by all prior solutions.

We implement our approach in a publicly available, cross-platform, and fully automated prototype, ct-verif, that leverages the SMACK and Boogie tools and verifies optimized LLVM implementations. We present verification results obtained over a wide range of constant-time components from the NaCl, OpenSSL, FourQ and other off-the-shelf libraries. The diversity and scale of our examples, as well as the fact that we deal with top-level APIs rather than being limited to low-level leaf functions, distinguishes ct-verif from prior tools.

Our approach is based on a simple reduction of constant-time security of a program P to safety of a product program Q that simulates two executions of P. We formalize and verify the reduction for a core high-level language using the Coq proof assistant.

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.

85 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

  • SoK: Computer-Aided Cryptography cites Vale: Verifying High-Performance Cryptographic Assembly Code
  • SoK: Computer-Aided Cryptography cites HACL: A Verified Modern Cryptographic Library
  • SoK: Computer-Aided Cryptography cites Jasmin: High-Assurance and High-Speed Cryptography
  • HACL: A Verified Modern Cryptographic Library cites Vale: Verifying High-Performance Cryptographic Assembly Code
  • Jasmin: High-Assurance and High-Speed Cryptography cites Vale: Verifying High-Performance Cryptographic Assembly Code
  • Jasmin: High-Assurance and High-Speed Cryptography cites HACL: A Verified Modern Cryptographic Library
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers85

  1. HACL*: A Verified Modern Cryptographic LibraryJean Karim Zinzindohoué, Karthikeyan Bhargavan, Jonathan Protzenko, Benjamin BeurdoucheCCS 2017 · 258 citations
  2. Spectector: Principled Detection of Speculative Information FlowsMarco Guarnieri, Boris Köpf, José F. Morales, Jan Reineke et al.S&P 2020 · 177 citations
  3. SoK: Computer-Aided CryptographyManuel Barbosa, Gilles Barthe, Karthik Bhargavan, Bruno Blanchet et al.S&P 2021 · 169 citations
  4. Jasmin: High-Assurance and High-Speed CryptographyJosé Bacelar Almeida, Manuel Barbosa, Gilles Barthe, Arthur Blot et al.CCS 2017 · 157 citations
  5. Vale: Verifying High-Performance Cryptographic Assembly CodeBarry Bond, Chris Hawblitzel, Manos Kapritsos, K. Rustan M. Leino et al.USENIX Security 2017 · 147 citations

Builds on1

  1. "Make Sure DSA Signing Exponentiations Really are Constant-Time"Cesar Pereida García, Billy Bob Brumley, Yuval YaromCCS 2016 · 93 citations

Related papers

  1. Towards Efficient Verification of Constant-Time Cryptographic ImplementationsLuwei Cai, Fu Song, Taolue ChenFSE 2024 · 4 citations
  2. Decompiling for Constant-Time AnalysisSantiago Arranz-Olmos, Gilles Barthe, Lionel Blatter, Youcef Bouzid et al.OOPSLA 2026 · 1 citation
  3. Formal verification of a constant-time preserving C compilerGilles Barthe, Sandrine Blazy, Benjamin Grégoire, Rémi Hutin et al.POPL 2020 · 77 citations
  4. Binsec/Rel: Efficient Relational Symbolic Execution for Constant-Time at Binary-LevelLesly-Ann Daniel, Sébastien Bardin, Tamara RezkS&P 2020 · 76 citations
  5. "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
Dusk over the sea between two cliffs drawn in fine vertical lines