I’d like to introduce substratum, a static analysis tool for identifying timing vulnerabilities in cryptographic software.
substratum analyzes assembly code to find vulnerabilities potentially exploitable by timing attacks, including architecture-specific instructions that are known to run in variable time, or operations that perform addressing based on sensitive data.
These vulnerabilities can easily be introduced by optimizing compilers, such that source code that plainly “looks to be constant-time” can fail to result in constant-time machine instructions after compilation. substratum performs its analysis on the actual assembly; any such compiler-introduced vulnerable instructions cannot escape it.
substratum is generic over a class of register-based architectures, including aarch64, x86-64, and riscv64, procured either by direct compilation (e.g. via LLVM, or GHC’s native code generator) or disassembly (via e.g. otool, objdump). It also encodes direct knowledge of various runtime patterns, namely rustc (Rust), Go, and GHC (Haskell), in order to filter out runtime-level noise that would otherwise produce large numbers of false positives.
In practice, I’ve found substratum to be invaluable for quickly and confidently producing software that must run in constant time at the assembly level. I have written my share of constant-time code, and know the pitfalls to look out for, but substratum has helped assure me that stuff I’ve written, either by hand or with the assistance of LLMs, actually runs in constant time on my target architecture by the time a compiler has finished optimizing (or otherwise mangling) my source code.
I’ve also found that substratum functions as an enormous productivity multiplier for LLMs when it comes to auditing constant-time software. Most interesting software will compile to hundreds of thousands or millions of lines of dense assembly, which can strain even the ability of “alien intelligence-level” LLMs to catch the runtime implications of every last instruction. substratum deterministically filters the non-constant-time signal in the assembly down to its essence, allowing a modern LLM to focus its formidable analytic power on the stuff that really matters.
substratum has been tested on an immense corpus of open-source cryptographic code, written in Rust, Go, Haskell (including the ppad cryptography stack), and C. I’ve also done substantial so-called mutation testing on this corpus, introducing intentional timing vulnerabilities into source code and making sure that substratum catches them. So, even as a new tool, it’s quite robust and battle-tested on both real-world and synthetic examples.
substratum exposed numerous interesting cases during the aforementioned rounds of experimentation and testing, but a particularly illustrative example I discovered arises in a specific Rust implementation of Bernstein-Yang inversion found in the wild. This implementation does not claim to run in constant time, and, indeed, as it appears to be targeted at the prover side in the zero-knowledge space, it does not necessarily need to run in constant time. But for the purpose of testing, I implemented a fix to make it run in constant time, and then tested substratum on the result.
The timing-vulnerable code is as follows, where ‘norm’ is ultimately used by ‘BYInverter::invert’, the full Bernstein-Yang inversion algorithm:
fn norm(&self, mut value: CInt<62, L>, negate: bool) -> CInt<62, L> {
if value.is_negative() {
value = value + &self.modulus;
}
if negate {
value = -value;
}
if value.is_negative() {
value = value + &self.modulus;
}
value
}The sign of ‘value’ at any point in the Bernstein-Yang algorithm is a
function of a secret input, and the above function branches on it
conditionally. An attacker who can accurately measure the time required
to run norm() can thus, in principle, extract information
about the secret, given enough samples.
The fixed version, which avoids branches, and thus semantically runs in constant time, is as follows:
fn norm(&self, value: CInt<62, L>, negate: Choice) -> CInt<62, L> {
let neg1 = (-(value.is_negative() as i64)) as u64;
let v1 = value.cond_add(&self.modulus, neg1);
let neg_mask = (-(negate.unwrap_u8() as i64)) as u64;
let v2 = v1.cond_neg(neg_mask);
let neg2 = (-(v2.is_negative() as i64)) as u64;
v2.cond_add(&self.modulus, neg2)
}Note that it depends on cond_add(), which is a
conditional add that is computed according to a fixed schedule, and so
also semantically runs in constant time:
fn cond_add(&self, other: &Self, mask: u64) -> Self {
let (mut data, mut carry) = ([0u64; L], 0u64);
for (i, d) in data.iter_mut().enumerate().take(L) {
let sum = self.0[i] + (other.0[i] & mask) + carry;
*d = sum & Self::MASK;
carry = sum >> B;
}
Self(data)
}Now. Though this source code certainly appears to have constant-time semantics, it is not, of course, what the machine ultimately runs. That is captured by the assembly code for the target platform, and this is what substratum analyses.
For aarch64, we observe the following substratum output on the
compiled assembly (the 'h_fr_invert' symbol is the
Bernstein-Yang inverter we’re ultimately interested in):
$ substratum scan -i example-aarch64.s \
--isa aarch64 \
--runtime rust \
--symbol h_fr_invert
ppad substratum v0.1.0
input example-aarch64.s · aarch64 att · rust
profile aarch64, csel available
BYInverter::invert
182 cond-branch b.ne LBB1_2
840 cond-branch b.ne LBB1_1
root h_fr_invert
reach 4 symbols · 1 with findings · 2 nct events
verdict-format aarch64-v3Note that it identifies two non-constant-time conditional branch
instructions, 'b.ne LBB1_2' and 'b.ne LBB1_1'.
An LLM quickly identifies these as being benign branches on public data
(loop counters); they do not represent vulnerabilities.
For x86-64, on the other hand, we observe the following:
$ substratum scan -i example-x86.s \
--isa x86_64 \
--runtime rust \
--symbol h_fr_invert
ppad substratum v0.1.0
input example-x86.s · x86_64 intel · rust
profile x86_64, cmov available
BYInverter::invert
215 cond-branch jne LBB1_2
1138 cond-branch jne LBB1_1
1170 cond-branch jbe LBB1_5
root h_fr_invert
reach 4 symbols · 1 with findings · 3 nct events
verdict-format x86_64-v2Note that on this platform we’ve accrued an extra non-constant-time
instruction, the conditional jump 'jbe LBB1_5'. Quick
analysis with an LLM demonstrates that this is not benign:
cmp r8, rsi ; r8 = top limb of 'value'
jbe LBB1_5 ; if not is_negative, jump to LBB1_5
mov r10, qword ptr [rdi + 40] ; otherwise do a bunch of stuff
mov rdi, r11 ; ..
mov rsi, r9
mov r12, rdx
mov r15, rcx
mov r11, rax
jmp LBB1_7 ; .. and then jump to LBB1_7
LBB1_5:
xor edi, edi
xor esi, esi
xor r12d, r12d
xor r15d, r15d
xor r11d, r11d
xor r10d, r10d
LBB1_7:
[..]The jump depends directly on a secret (‘r8’, the top limb of ‘value’), and the jump introduces two different code paths which are chosen depending on the value of the secret. The executable code thus contains a secret-dependent execution differential, even though the source code, and the assembly for a different architecture, did not.
This exploitable instruction was emitted due to a (misguided, in this context) LLVM optimization on x86-64 resulting from inspection of ‘mask’ in the conditional add function. A fix is to wrap it in a compiler-opaque black box, as follows (note that this is also how the ‘Choice’ type in Rust’s subtle crate prevents the compiler from learning about secret-derived flags and masks):
fn cond_add(&self, other: &Self, mask: u64) -> Self {
let mask = core::hint::black_box(mask); // optimizer-opaque
let (mut data, mut carry) = ([0u64; L], 0u64);
for (i, d) in data.iter_mut().enumerate().take(L) {
let sum = self.0[i] + (other.0[i] & mask) + carry;
*d = sum & Self::MASK;
carry = sum >> B;
}
Self(data)
}Using this version, substratum reports identical findings for both architectures (i.e., the two benign public loop counter instructions). There is no more secret-dependent vulnerability on x86-64.
substratum cannot flatly rule out all timing attacks statically, as it is unable to reason about microarchitectural side channels that exist below the assembly level, with respect to e.g. caches, branch prediction, speculative execution, and so on.
At the assembly level, though, substratum can certainly rule out major classes of timing attack statically. If you’re interested in using it to do so, get in touch.