Hacker News Reader

Comment by leni536 | Hacker News Reader

C and C++ are unsuitable for writing algorithms with constant-time guarantees. The standards have little to no notion of real time, and compilers don't offer additional guarantees as extensions.

But blaming the compiler devs for this is just misguided.

View on HN

That was my thought reading this article. If you want to produce machine code that performs operations in constant time regardless of the branch taken, you need to use a language that supports expressing that, which C does not.

Heck, CPUs themselves aren't suitable for constant time operations. At any time, some new CPU can be released which changes how quick some operations are.

Or microcode updates to existing CPUs!

Not always. At least for RISC-V there is the Zkt extension which guarantees data independent execution time for some instructions. I assume there's something similar for ARM and x86.

It does pretty much require you to write assembly though. I think it would definitely make sense to have some kind of `[constant_time]` attribute for C++ that instructed the compiler to ensure the code is constant time.

It is not a problem that different CPUs have different execution time, the problem is if the same CPU, running the same instruction has a timing difference depending on the data it operates on. In this regard CPUs have actually gotten better, specifically because it is a feature that AMD and Intel has pursued.

That includes branch predictions among other CPU optimizations.

If you have data-dependent branches then you have already lost. If you don't then I fail to see what data the branch predictor could possibly leak.

If you want to get very paranoid most instructions probably use slightly different amounts of power for different operands which will change thermal output which will affect CPU throttling. I'm not sure there are any true constant time instructions on modern high-performance CPUs. I think we have just agreed that some instructions are as close as we can reasonably get to constant time.

> If you want to produce machine code that performs operations in constant time regardless of the branch taken

Nobody is asking for that. That's the whole point. Crypto code that needs to be constant time in regards to secret data is needs to avoid branching based on secret data, but the optimizer is converting non-branching code into branching code.

What languages are suitable for writing algorithms with constant-time guarantees?

According to some comments under this submission, even x86 assembly isn't suitable, or only under specific circumstances that are generally not available in userspace.

At this time, the idea of a constant-time operation embedded into a language’s semantics is not a thing. Similar for CPU architectures. Our computing base is about being fast and faster.

Reply on news.ycombinator.com