Hacker News Reader

Comment by Aissen | Hacker News Reader

You don't really want branchless in security. The requirement is constant-time and side-channel resistance. The branchless algorithm is an implementation detail.

View on HN

Constant-time is not possible with branching code. If it's possible your code runs through different paths then your time is not constant. Or if you disagree with me show me branching ASM code that has exactly the same perf counters independent of input.

It’s possible to design an algorithm which branches and is also constant time. If, for all inputs, the instruction length (# of instructions executed) is the same even for different branch paths, then they must all run in the same time. This, of course, isn’t accounting for different (microscopic) execution times of individual instructions, but constant time isn’t really a measure of clock time anyway.

If your CPU is as simple as the one designed during a one quarter year uni class then sure. But that's simply not a realistic scenario with a modern CPU. Even if you have the same amount of instructions then branch prediction, memory latencies, super scalar execution and more will throw a wrench in that quickly. Even if you have the same instruction stream with different input data the latencies can be different. That is exactly what you are preventing with branchless code. It's been proven that it's possible to use this as an attack vector.

See a trivial example here: https://stackoverflow.com/questions/11227809/why-is-processi...

Where first massaging the data so the processing is branch predictor friendly results in a 6 time speedup. These things are not microscopic.

Reply on news.ycombinator.com