Avoid branching following crypto/subtle

[bmperrea]

Following a question by @stevenroose in #621 I noticed there are a number of constant-time functions using branches that represent obviously equal computation time, particularly for comparison logic (<,<=,==). To better secure against timing attacks based on branch prediction it would be good to change this type of logic to pure bitwise operations following crypto/subtle.

To analyze the computation cost I made an example repo . Also, in my suggested changes to #621 I already started using some of this type of logic - see here.

I hope to make a PR of this sort myself sometime, but if there are any objections I would be interested to hear them ahead of time. Thanks!

[stevenroose]

I'd agree. Using crypto/subtle will probably also improve the readability of the btcec package.

[bmperrea]

Great - also I realized that one can keep similar performance to == for the equality check by using int64 like in the inequality checks in crypto/subtle - see the updates to my example repo.

[bmperrea]

I gave this a try on this branch in field.Normalize(). I found that there is a significant slow down in practice when compared to the current implementation. Here is an example of the results.

Current

$ go test --bench Norm
goos: darwin
goarch: amd64
pkg: github.com/bmperrea/btcd/btcec
BenchmarkFieldNormalize-8   	100000000	        14.3 ns/op

With Changes

BenchmarkFieldNormalize-8   	100000000	        19.9 ns/op

I think it would be difficult to do much better than this in terms of optimization and therefore I am less sure that my suggestion is worth the loss in performance. Perhaps this could be solved if there was a direct way to convert bool->int in golang. If the different in time is primarily due to processor optimizations different between branches then one would prefer to give up the performance in favor of a constant time implementation.

[bmperrea]

UPDATE: This performance appears to be purely due to compiler optimizations. For instance, if one changes m &= 1 to m &= 7 or another odd integer in the, and likewise replace 0 with an even integer in the &= statements the tests still pass since only the least-significant bit is set, but the runtime is much longer - 18.8 ns/op. It's unclear to me whether this leads to any non-constant run-time.

[bmperrea]

Update: There is an explicit timing difference in field.Normalize() demonstrated in this branch where I use a carefully chosen value due to the branches it follows in field.Normalize().

This comment therefore exposes a potential timing attack based on the non-constant runtime of field.Normalize(). Although it far from clear whether a practical timing attack to decipher private information could be mounted using this, there is an easy fix and I'll try to follow up with a pr shortly.

[l0k18]

Does this really have any relevance to btcd? There is no encrypted data on chain, no second party interactive session, and no contract between nodes and users regarding timeliness, best effort only. It is not likely a huge component of the sync slowness but making it perfectly constant time will definitely add 5% or more to initial sync time.