Constant-time support coming to LLVM: Protecting cryptographic code

Summary

Trail of Bits has developed constant-time coding support for LLVM 21, providing developers with compiler-level guarantees that their cryptographic implementations remain secure against branching-related timing attacks. This work introduces the __builtin_ct_select family of intrinsics and supporting infrastructure that prevents the Clang compiler, and potentially other compilers built with LLVM, from inadvertently breaking carefully crafted constant-time code. This post will walk you through what we built, how it works, and what it supports. We’ll also discuss some of our future plans for extending this work.The compiler optimization problemModern compilers excel at making code run faster. They eliminate redundant operations, vectorize loops, and cleverly restructure algorithms to squeeze out every bit of performance. But this optimization zeal becomes a liability when dealing with cryptographic code.Consider this seemingly innocent constant-time lookup from Sprenkels (2019):uint64_t constant_time_lookup(const size_t secret_idx, const uint64_t table[16]) { uint64_t result = 0; for (size_t i = 0; i < 8; i++) { const bool cond = i == secret_idx; const uint64_t mask = (-(int64_t)cond); result |= table[i] & mask; } return result;}This code carefully avoids branching on the secret index. Every iteration executes the same operations regardless of the secret value. However, as compilers are built to make your code go faster, they would see an opportunity to improve this carefully crafted code by optimizing it into a version that includes branching.The problem is that any data-dependent behavior in the compiled code would create a timing side channel. If the compiler introduces a branch like if (i == secret_idx), the CPU will take different amounts of time depending on whether the branch is taken. Modern CPUs have branch predictors that learn patterns, making correctly predicted branches faster than mispredicted ones. An attacker who can measure these timing differences acro...