Hacker News Reader

Comment by SAI_Peregrinus | Hacker News Reader

This is an important point. The C standard does not define the time it takes for an operation to complete as "observable behavior", so compilers are *always* free to change timings, even with optimization disabled. It is fundamentally impossible to guarantee constant-time execution in Standard portable C. It's possible to use non-standard intrinsics and compiler directives to get such a guarantee, but that's not portable.

AFAIK Rust also doesn't guarantee timing. That's part of why Ring uses assembly for the constant-time bits (really Ring uses code from BoringSSL for that, and BoringSSL uses assembly for that reason and for performance.)

View on HN

Rust doesn't guarantee timing, but there are crates that carefully construct constant-time primitives that should work with current Rust, such as https://crates.io/crates/subtle-ng .

Personally, I would love to see enhancements to Rust and LLVM that would make it possible to provide such guarantees in pure Rust.

Word on the block is that there is a RFC to add support for secret types in LLVM, and Rust is waiting for them to also provide it in Rust [0].

[0]: https://github.com/rust-lang/rfcs/pull/2859

It doesn't seem to stop people from trying though: https://www.bearssl.org/constanttime.html

(This sort of thing is not my area of expertise, but has always made me uneasy...)

Yeah. That sort of thing works, right up until some compiler gets released that optimizes it out. It's "portable C", but the behavior it's trying to produce is non-portable.

Especially note his guideline to look at the assembly output. The best guarantee is to simply check that the compiler did what you wanted.

There are also some aspects that a compiler is unlikely to alter. EG if you write code with no secret-dependent branches, no normal compiler will insert any secret-dependent branches during optimization. It's generally safe to rely on the compiler not being actively malicious or de-optimizing code.

I don't think Intel/AMD make any guarantees about instructions being constant time either.

Correct, and don't provide any guarantees about electromagnetic side channel emissions or power side channels or…

The lack of a guarantee in assembly is less of a concern than the lack of a guarantee in C, since the CPU behavior is less likely to change unexpectedly than a C compiler.

Though Intel at least does provide a list of instruction latencies and throughputs, in their "Intel 64 and IA-32 Architectures Optimization Reference Manual"[1].

[1] https://www.intel.com/content/dam/www/public/us/en/documents...

Normally, rather than counting on two different codepaths to take the same number of cycles, assembly code written for constant execution time will always run all the same instructions unconditionally.

So, you don't have to know how many cycles every instruction takes; you just have to make sure you use instructions that don't take a data-dependent number of cycles.

This is only possible with resource aware types, it would be nice to import a function with resource constraints such as constant time, etc.

It should be possible to create constant-time C code, if the code avoids branching (if, case, goto), and all loops have a constant number of operations.

Expressing most algorithms this way is not impossible, but does nor feel natural for many.

> It should be possible to create constant-time C code, if the code avoids branching (if, case, goto), and all loops have a constant number of operations.

It fundamentally isn't, because there is no way (in standard C) to prevent the compiler from introducing performance differences. Even if you avoid control flow constructions, what if the compiler e.g. generates a separate codepath for when one particular variable is 0 (perhaps as part of arithmetic optimizations)? There's just no (standard) way to stop that happening, no matter how cleverly you write your code.

Sad! It's as if we might need some kind of simple portable assembly, one which straightforwardly translates simple constructs and formulas to the target machine code. Like, well, C used to be in 1975.

Jokes aside, I wonder if some kind of -Ox option could be standardized to switch off all optimizations, like -O0, and also guarantee no code rewriting for whatever other purposes.

Hand-crafting constant-time algorithms in assembly is even more error-prone.

In fairness assembly isn't what it was in 1975 either - with superscalar architectures and the dominance of caches these days even assembly is not as constant-time as you might expect.

Reply on news.ycombinator.com