Annotate blocks that must run in constant time regardless of inputs

[zackw]

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.

[pnkfelix]

• Minor detail: Note that Rust's annotation system currently only supports attaching annotations to items, not blocks.
• I believe there is a fair amount of academic research on this topic. I recall at least one paper that used an effect system to "ensure" that all the paths in a call-graph took the same amount of time. I cannot find the reference though; I thought it was POPL 2000, but have not found it despite skimming some of the papers listed at http://www.informatik.uni-trier.de/~ley/db/conf/popl/popl2000.html

[reem]

Triage. This seems useful, but very complex and probably out of scope for now.

[klutzy]

Agreed that it's out of scope since it requires llvm-side guarantee.

It's possible to write constant-time code with asm!, although it needs extra care. I previously wrote a syntax extension which converts simple functions into constant-time code via asm!.

[steveklabnik]

I'm pulling a massive triage effort to get us ready for 1.0. As part of this, I'm moving stuff that's wishlist-like to the RFCs repo, as that's where major new things should get discussed/prioritized.

This issue has been moved to the RFCs repo: rust-lang/rfcs#847