Smooth, Integrated Proofs of Cryptographic Constant Time for Nondeterministic Programs and Compilers
Formal verification of software and compilers has been used to rule out large classes of security-critical issues, but risk of unintentional information leakage has received much less consideration. It is a key requirement for formal specifications to leave some details of a system's behavior unspecified so that future implementation changes can be accommodated, and yet it is nonetheless expected that these choices would not be made based on confidential information the system handles. This paper formalizes that notion using omnisemantics and plain single-copy assertions, giving for the first time a specification of what it means for a nondeterministic program to be constant-time or more generally to avoid leaking (a part of) its inputs. We use this theory to prove data-leak-free execution of core cryptographic routines compiled from Bedrock2 C to RISC-V machine code, showing that the smooth specification and proof experience omnisemantics provides for nondeterminism extends to constant-time properties in the same setting. We also study variants of the key program-compiler contract, highlighting pitfalls of tempting simplifications and subtle consequences of how inputs to nondeterministic choices are constrained. Our results are backed by modular program-logic and compiler-correctness theorems, and they integrate into a neat end-to-end theorem in the Coq proof assistant.
Wed 18 JunDisplayed time zone: Seoul change
14:00 - 15:40 | |||
14:00 20mTalk | Verified Foundations for Differential Privacy PLDI Research Papers Markus de Medeiros New York University, Muhammad Naveed Amazon, Tancrède Lepoint Amazon, Temesghen Kahsai Amazon, Tristan Ravitch Amazon, Stefan Zetzsche Amazon, Anjali Joshi Amazon, Joseph Tassarotti New York University, Aws Albarghouthi Amazon, Jean-Baptiste Tristan Amazon DOI | ||
14:20 20mTalk | Automated Exploit Generation for Node.js Packages PLDI Research Papers Filipe Marques INESC-ID; Instituto Superior Técnico - University of Lisbon, Mafalda Ferreira INESC-ID; Instituto Superior Técnico - University of Lisbon, André Nascimento INESC-ID; Instituto Superior Técnico - University of Lisbon, Miguel E. Coimbra INESC-ID; Instituto Superior Técnico - University of Lisbon, Nuno Santos INESC-ID; Instituto Superior Técnico - University of Lisbon, Limin Jia Carnegie Mellon University, José Fragoso Santos INESC-ID; Instituto Superior Técnico - University of Lisbon DOI | ||
14:40 20mTalk | Robust Constant-Time Cryptography PLDI Research Papers Matthew Kolosick University of California at San Diego, Basavesh Ammanaghatta Shivakumar Virginia Tech, Sunjay Cauligi ICSI, Marco Patrignani University of Trento, Marco Vassena Utrecht University, Ranjit Jhala University of California at San Diego, Deian Stefan University of California at San Diego DOI | ||
15:00 20mTalk | Smooth, Integrated Proofs of Cryptographic Constant Time for Nondeterministic Programs and Compilers PLDI Research Papers Owen Conoly Massachusetts Institute of Technology, Andres Erbsen Google, Adam Chlipala Massachusetts Institute of Technology DOI | ||
15:20 20mTalk | Circuit Optimization using Arithmetic Table Lookups PLDI Research Papers Raghav Malik Purdue University, Vedant Paranjape Purdue University, Milind Kulkarni Purdue University DOI |