ct_eq could be more-constant in time

[ssbr]

tl;dr: ct_eq doesn't guard against effectively short-circuiting from compiler optimizations.

This probably isn't a very big deal, btw -- for example, it turns out BoringSSL is substantially the same -- but I am a nerd.

(Sorry if I'm reading the wrong version of the code and there's some intrinsic-y/inline-asm-y versions that address this.)

[T]::ct_eq has the following comparison loop:

// This loop shouldn't be shortcircuitable, since the compiler
// shouldn't be able to reason about the value of the `u8`
// unwrapped from the `ct_eq` result.
let mut x = 1u8;
for (ai, bi) in self.iter().zip(_rhs.iter()) {
    x &= ai.ct_eq(bi).unwrap_u8();
}
x.into()

The idea is that you don't short-circuit the loop early, and each iteration takes the same amount of time (e.g. uses integer operations that are constant time, not variable-time integer operations or predictable branches), so it will be constant time.

That's correct with the code as-written, but compiler optimizations are allowed to mess with the behavior. For example, it could compile down to the equivalent of:

for (ai, bi) in self.iter().zip(_rhs.iter()) {
    if ai.ct_eq(bi).unwrap_u8() == 0 {
      return 0.into();
    }
}
1.into()

... among other things.

In the implementations I'm familiar with, the fix goes in two parts. First, they try make the accesses to ai and bi volatile reads, so that the compiler can't just skip them or mutate them in arbitrary ways. Then, they make the writes to x volatile, so that the compiler isn't allowed to optimize on data dependency.

volatile reads in the loop

fn ct_eq(&self, other: &$t_u) -> Choice {
    let x: $t_u = self ^ other;
    let y: $t_u = (x | x.wrapping_neg()) >> ($bit_width - 1);
    ((y ^ (1 as $t_u)) as u8).into()
}

This is all pure, side-effect free code, so the compiler is allowed to skip it if it knows how. Using blackbox() or similar would prevent this, and force at least the reads.

volatile writes to the accumulator

Going back to [T]::ct_eq:

let mut x = 1u8;
for (ai, bi) in self.iter().zip(_rhs.iter()) {
    x &= ai.ct_eq(bi).unwrap_u8();
}
x.into()

Even if we force the compiler to perform every comparison, and do it in constant time, that doesn't keep the loop itself constant time. There is no particular guarantee that the value of x has to be data-dependent on the result of those volatile reads. Consider the following "optimized" version of the function, which could be in effect produced by a compiler as an optimization to improve instruction-level parallelism:

let mut it = self.iter().zip(_rhs.iter())
while let Some((ai, bi)) = it.next() {
    if ai.ct_eq(bi).unwrap_u8() == 0 {
        for (ai, bi) in it {let _ = ai.ct_eq(bi);}
        return 0.into();
    }
}
1.into()

This still performs the same number of volatile reads, and evaluates to the same value, and so is a valid optimization. But it cuts the data dependency: the leftover volatile reads can be executed in parallel or out of order with the code depending on the return value of the ct_eq function, causing it to effectively short-circuit from the point of view of calling code.

I don't know that the optimization would be worth it or even faster in practice, and don't think any existing compilers do it, but it is theoretically possible, and other implementations of constant time comparison guard against this by making the writes to the x accumulator volatile.

Past work

• CPython: hmac.compare_digest could try harder to be constant-time. python/cpython#84968
• Tink: tink-crypto/tink@335291c

[ssbr]

Incidentally I looked into it and talked with some people, and I think the answer for projects like BoringSSL is that these optimizations don't yet exist, and they have testing infrastructure that would catch it. Any solution that isn't inline assembly is unsound, so it's really the test infra that catches it, and avoiding volatile allows autovectorization. So if subtle has test suites that would detect failed constant-time on a new compiler release, it is actually better not to perform volatile accesses or add value barriers or any of that, and the better fix would just be to document why.

[tarcieri]

I would agree there's a problem with the overall strategy subtle uses, which is to insert its volatile read in the constructor for Choice, rather than using it on access ala the BlackBox type.

In curve25519-dalek we observed LLVM determining when a mask was zero and inserting a branch. Rewriting the affected code to use subtle rather than manually implementing masking seemed to address the issue, but it has left me worried about cases where there is no sort of optimization barrier on access, as the window between construction and access seems like an opportunity for LLVM to insert such branches.

As @ssbr noted however, it doesn't seem to in practice, at least for now, or at least I have failed to come up with a subtle PoC which is able to result in LLVM inserting a branch some time after Choice has been constructed.

It's also worth noting you can perform various boolean logic on Choice after it's been constructed, and that also seems like it has the potential for LLVM to replace bitwise arithmetic/masking with branches.