math/bits: guarantee Add, Sub, Mul, RotateLeft, ReverseBytes to be constant-time operations

[TuomLarsen]

I'm a heavy non-crypto user of bits.* and I'm afraid changes like #31229 will effect my performance. One way of keeping crypto people happy and users like me would be to have separate functions for both non-constant time and constant time addition, multiplication, ...

In the issue above I was reminded that the change affects only the fallbacks. I'm afraid promising that the fallbacks are constant time will later lead to constant time native implementations which could very well be slower than their non-constant time alternatives. For example, platforms which don't support carry flag are RISC-V and WebAssembly and it could happened that "a branch works out better" [1].

[1] https://gmplib.org/manual/Assembly-Carry-Propagation.html

[randall77]

RISC-V can generate the carry in constant time using a SLTU instruction.
Web assembly has a similar instruction. I don't know whether it guarantees constant time or not.

[smasher164]

The change for #31229 results in a neglible (if any) impact on performance. Also keep in mind that the software fallback would rarely be executed. Here is the output for benchstat:

name             old time/op  new time/op  delta
Add-4            1.44ns ± 0%  1.63ns ± 0%   ~     (p=1.000 n=1+1)
Add32-4          1.08ns ± 0%  1.05ns ± 0%   ~     (p=1.000 n=1+1)
Add64-4          1.46ns ± 0%  1.43ns ± 0%   ~     (p=1.000 n=1+1)
Add64multiple-4  0.73ns ± 0%  0.99ns ± 0%   ~     (p=1.000 n=1+1)
Sub-4            1.42ns ± 0%  1.42ns ± 0%   ~     (all equal)
Sub32-4          1.08ns ± 0%  1.47ns ± 0%   ~     (p=1.000 n=1+1)
Sub64-4          1.42ns ± 0%  1.47ns ± 0%   ~     (p=1.000 n=1+1)
Sub64multiple-4  0.72ns ± 0%  0.72ns ± 0%   ~     (p=1.000 n=1+1)

[bmkessler]

@smasher164 FYI, that benchmark looks to be testing the intrinsic path and not the pure Go fallback. When you test the pure Go version, you should run multiple counts to compare significant changes.

If carries are unpredictable (adding random numbers), then the constant time (branchless) code will likely be faster than the prior implementation because the carry branches will be poorly predicted.

[smasher164]

name             old time/op  new time/op  delta
Add-4            1.16ns ±11%  1.51ns ± 5%  +30.52%  (p=0.008 n=5+5)
Add32-4          1.08ns ± 0%  1.03ns ± 1%   -4.86%  (p=0.029 n=4+4)
Add64-4          1.09ns ± 1%  1.95ns ± 3%  +79.23%  (p=0.008 n=5+5)
Add64multiple-4  4.03ns ± 1%  4.55ns ±11%  +13.07%  (p=0.008 n=5+5)
Sub-4            1.08ns ± 1%  1.50ns ± 0%  +38.17%  (p=0.016 n=5+4)
Sub32-4          1.09ns ± 2%  1.53ns ±10%  +40.26%  (p=0.008 n=5+5)
Sub64-4          1.10ns ± 1%  1.47ns ± 1%  +33.39%  (p=0.008 n=5+5)
Sub64multiple-4  4.30ns ± 2%  4.08ns ± 4%   -5.07%  (p=0.032 n=5+5)

It seems that Add64 is the most significantly impacted benchmark, while the others have a ~30% slowdown.

[FiloSottile]

I prefer making the default secure, and if necessary offer a VariableTimeAdd which communicates the risk. This also has the advantage of letting us cross that bridge when and if we come to it. (That is, if it ever turns out a native implementation would actually be faster if not constant time.)

[TuomLarsen]

If Add64 is implemented as ADC on platforms which have such instruction, there is nothing "variable" in it. I think "constant" communicates better that it is always a constant time operation, no matter if ADC or a fallback is used.

[FiloSottile]

For someone doing a code review, it's reasonable to expect bits.Add to be constant time, and it requires prior knowledge to know that no, you should use bits.ConstantTimeAdd instead. Making bits.Add the constant time one solves this problem. No one will be upset to find out that in fact VariableTimeAdd is constant time sometimes, the other way around is not true.

When there are a safe and an unsafe API, the unsafe one must be the qualified one.

[TuomLarsen]

It is only true for crypto, constant time has no use for every other domain. By that perspective it's reasonable to expect that bits.Add adds two numbers, constant time or not.

[smasher164]

The choice of preserving semantics and timing by default should depend on the chance that the fallback is executed. For example, the FMA intrinsic proposed in #25819 has a decent chance of hitting the fallback on x86, arm, mips, and mips64. Additionally, the cost of using the FMA software fallback is orders of magnitude slower than a simple multiply and add. On the other hand, the chance of the bits.Add fallback being executed is much lower, given the add-with-carry instructions on most architectures. Additionally, the slowdown introduced by a constant time fallback is in the worst-case a factor of two.

[FiloSottile]

I find it appropriate that the FMA functions live in math, while Add, Sub and Mul live in math/bits.

That allows us to build the expectation that math/bits is constant time unless the name is screaming otherwise, which is not true of math, or math/big.

I am firmly convinced that even if safety is only relevant to one use case, the default should be safe, and an unsafe version can be added with a clear name. So if anyone thinks it's already time to add VariableTimeAdd, VariableTimeSub and VariableTimeMul, we can make this proposal about that. Otherwise, I think we should close this for now.

[jimmyfrasche]

@FiloSottile operations in math/bits are not documented as being constant time so I did not have that expectation, though it makes sense now that you say it. Should it be mentioned in the package documentation?

[TuomLarsen]

@smasher164 The chance of hitting a fallback might change over time, as hardware advances. I'm thinking about FMA the other way around: the compiler should do with a*b+c whatever it pleases but when explicitly asking for FMA it should do just one rounding. Meaning Add should do whatever is needed to make it fast, and ConstantTimeAdd would guarantee what it says.

@FiloSottile Obviously we don't agree on this one but I find you want to close it way too early, given how controversial the issue is (based on number of up- and down-votes). I would also find interesting what other core devs think about this.

Regarding of whether to call something "constant time" or "variable time". I think the most common use case should take precedence in naming to the special case. For example, a "hash function" is usually called just that as evidenced on Wikipedia, whereas to signify the importance of other properties, one usually calls it "cryptographic hash function". Meaning Add should do whatever compiler pleases to make it performant and only "crypto" Add should guarantee constant time operation.

So far we only discussed Add and Mul but there is also Div. At least on z86 DIVQ instruction has variable latency so I would assume it always needs to call a fallback, in order to preserve constant time performance.

One of the goals of #21835 @robpike stated is to "make math/bits support its operations more efficiently through the compiler". This will make it less performant, not more. In the same thread, @josharian implemented PCG using math/bits and there is no need for constant time Add as the generator is not intended for crypto in the first place.