UPEC-PN: Exhaustive constant time verification of low-level software using property checking

Abstract:
With the prevalence of timing side channel attacks against software implementations of cryptographic algorithms, the constant time programming paradigm has received increased attention. Constant time programming demands that the execution of a program does not have any exploitable dependencies on secret data. However, implementing a program in such a fashion is not a simple task. In this paper, we propose UPEC-PN, a novel methodology for semi-automatically analyzing a given software binary and verifying its compliance with the constant time paradigm. The methodology is based on property checking and exhaustively checks all possible runs of the target software for security vulnerabilities due to violation of constant-time execution. To ensure scalability, we use program netlists, an ISA-level representation of the software as a combinational hardware circuit, as the underlying computational model. We use a 2-safety approach, instantiating the program netlist under test twice and perform interval property checking. The properties are formulated such that any counterexample shows an exploitable dependency on secret data. We conducted a case study on software implementations of the RSA and AES encryption algorithms compiled for the RISC-V ISA. In both studies, we were able to detect a number of possible side channels due to violation of constant time execution.