Annotate blocks that must run in constant time regardless of inputs

[steveklabnik]

Issue by zackw
Tuesday Oct 15, 2013 at 00:03 GMT

For earlier discussion, see rust-lang/rust#9859

This issue was labelled with: A-llvm in the Rust repository

---

In a whole bunch of security-related contexts it's important to write code that runs in constant time regardless of input; the obvious example is that if you compare two strings character-by-character for equality and break out of the loop when you hit the first difference, someone might learn how much of their forged authentication token (for example) was correct by measuring the time it took to fail.

Constant-time code requires careful programming, but in the general case it also requires compiler support -- at minimum, it has to be possible to disable optimizations that would convert a|b to a||b in the name of speed, or similar. Ideally, though, the compiler would verify that an annotated block would execute in constant time, and fail the compilation if it was impossible to guarantee that of the generated code.

I think the natural way to expose this in Rust is a #[constant_time] annotation that could be applied to blocks. Most of the heavy lifting, however, probably needs to be done in the LLVM core.

[hauleth]

I think that it could be done via wrapper like Wrapping. Add pub struct CT<T>(T) and define basic operations for that type. This will simplify implementation and will be backwards compatible.

[andersk]

The constant-time discipline can be enforced at source level without language changes, by taking advantage of lifetime parametricity. See #1814 (comment).

Providing the needed constant-time primitives in a way that avoids unsafe LLVM optimizations is a separate problem that needs to be addressed, but assuming those primitives can be provided, this allows you to guarantee that you’re combining them in safe ways. It’s probably sufficient to write the primitives in inline assembly.

[briansmith]

I suggest that this RFC be closed. In actual crypto code, operations on secret values that need to be constant time are interleaved with operations on non-secret values that do not need to be constant time. We want the optimizer to fully optimize the operations on non-secret data while only doing safe optimizations on the code that manipulates secret data. Accordingly, it's better to focus effort on annotations at the value level, not the code block level.

[gnzlbg]

@briansmith is there an rfc issue for the "annotations at the value level" discussion ?

[arielb1]

@gnzlbg

Nothing that I could find.

[Centril]

Closing in favor of #2533.