btcd
btcd copied to clipboard
btcsuite
btcec: Constant time field normalization.
The current implementation of field.Normalize() has a timing vulnerability exposed in issue #1079. This PR solves that issue by using methods outlined in the crypto/subtle reference library.
Several constant time comparison operators that return integers for use in further bitwise operations are defined and should be used in place of other branching statements in the btcec library (even if-else statements with equal-time branches are vulnerable to timing attacks based on branch-prediction!). I think this solves #1079, but please comment if you knows of any other place following this same-time branching statements pattern. For details comparing the performance of these functions to their same-time branching counterparts see my example repo. For a more full set of constant time functions see this other branch.
Credits to @stevenroose for questioning this pattern in #621. Also, a plug for everyone to suggest there be a direct bool2int conversion function in golang!
$ benchcmp old.txt new.txt
benchmark old ns/op new ns/op delta
BenchmarkAddJacobian-12 476 469 -1.47%
BenchmarkAddJacobianNotZOne-12 933 937 +0.43%
BenchmarkScalarBaseMult-12 40553 40816 +0.65%
BenchmarkScalarBaseMultLarge-12 40969 41249 +0.68%
BenchmarkScalarMult-12 131962 133058 +0.83%
BenchmarkNAF-12 774 900 +16.28%
BenchmarkSigVerify-12 184327 203190 +10.23%
BenchmarkFieldNormalize-12 16.3 16.3 +0.00%
BenchmarkParseCompressedPubKey-12 21344 21283 -0.29%
benchmark old allocs new allocs delta
BenchmarkParseCompressedPubKey-12 6 6 +0.00%
benchmark old bytes new bytes delta
BenchmarkParseCompressedPubKey-12 256 256 +0.00%
Unfortunately, there is a slowdown here comparable to the speedup found in a previous change to Normalize. However, as demonstrated in BenchmarkFieldNormalizeWithCarry basically all of this slowdown is due to the faster runtime of the average case of Normalize when using branching, and therefore the slowdown is unavoidable if the runtime is to be truly constant.
Thanks for the credits :)
Cool that you managed to do a proper constant time, I struggled with it at that time!
This change would be compatible with https://github.com/btcsuite/btcd/pull/621, right?
Also, you seem to have forgotten to run gofmt. It's always a good idea to run the goclean.sh command before committing, the Travis here runs it as well.
Thanks @stevenroose. It looks like that fixed the tests.
This is compatible with my suggested branch for #621, although it will probably require a simple rebase. If I am able to get this reviewed and merged then I would want to spend some more time with #621 to improve its performance and get it finished off as well. Great work on this stuff btw.
I added a commit with where I change the internals of constant_time to use int32 instead of int64. I realized we know that the 10 uint32 values in field will be less than 2^27 and thought that int32 might be more consistently performant on different architectures.
Thanks for the excellent review @davecgh. I have made the updates, squashed, and renamed the commit.
Updated based on good feedback in https://github.com/gcash/bchd/pull/78 . The timing got faster than it previously was for this PR since doing so - thanks @jimpo and @markblundeberg
UPDATE: actually based on results from benchstat none of the differences in timing here or before are statistically significant so I don't want to make too strong of a claim.
