secp256k1: Not constant time

[tac0turtle]

Issue from tendermint in regards to secp256k1. this key is being added directly into the SDK

ValarDragon on Jul 29, 2018 •

Our current secp256k1 implementation isn't constant time. I haven't looked at the actual math parts yet, but the following two very minor things aren't constant time:

Our signature encoding is vartime in the parity of the signature. This is easy to fix. (This is present due to it being vartime in the previous DER encoding as well) This isn't really a problem, since the normal security of ECDSA assumes you get this extra bit of distinguishing s's parity, but we may as well fix it since we're only allowing one parity per #2091.

RFC6979 (Deterministic nonce generation): This is basically impossible to exploit, but I thought I may as well list it here. Every 2**224 signatures on average, RFC6979 will leak some timing information on how the nonce was created. Nothing needs to be changed here imo, since this is very much not a concern.

ValarDragon on Aug 28, 2018

I don't know how I missed this on my first read through this codebase, but there are two more cases of non-constant time ness, but these actually matter.

In the signRFC6979 function (called as part of Sign), the following two lines are present

inv := new(big.Int).ModInverse(k, N)
s := new(big.Int).Mul(privkey.D, r)

From the godocs " Modular exponentation of inputs of a particular size is not a cryptographically constant-time operation. ", thus this isn't constant time.

From conversation with @zmanian, this isn't a prelaunch concern.

ebuchman on Jan 23, 2019

@ValarDragon do you want to open this on the upstream btcd repo?

We will mitigate using #3163 and make clear in documentation that this lib isn't constant time until then.

[IdaTucker]

There are two operations that are not constant time in the signing algorithm:

• computation of the random point kG, which uses the ScalarBaseMultNonConst from the secp256k1 package.
• the computation of the modular inverse of k kinv := new(secp256k1.ModNScalar).InverseValNonConst(k)

We can use filippo.io/bigmod for fixing the modular inverse.
However, it will not be as simple to get a constant time ScalarBaseMult. The pieces are there, but we would need to add a constant-time table lookup and a special case of addition that makes assumptions on the inputs. Since such changes would almost certainly require an audit due to the sensitive nature of the code being affected, we feel it would be best not to follow this route.

Instead, we will use go-ethereum's go wrapper for the c implementation of ecdsa signatures over secp256k1 (by btc), which is constant time (since scalar inverse and multiplication are). The cosmos sdk already contains a copy of this code.
The issue with this option is that using c code with a wrapper for go-lang might make it harder to have reproducible builds. This being said, node operators have the option to build with c or not. The reproducible builds would need cgo disabled.

[ValarDragon]

I'm supportive of using cgo by default / whenever its available!

I think full nodes should be using this anyway for greater speed in tx processing.

I also think the non-constant timeness of secp256k1 is quite low risk given how we use it.

[yihuang]

Reproducible build with c dependency could be managed using nix

[odeke-em]

@elias-orijtech this perhaps could be up your alley.

[tac0turtle]

zondax is looking into this

[IdaTucker]

Hey, sorry for the delay with this one.
Using cgo, the secp256k1 Signing algorithm is already constant time.
However I noticed that the generation of the public key from the private key is not constant time, as it uses this function from dcred, which uses non constant time scalar base multiplication.
Is this something you would like us to fix, so that cgo builds also have constant time public key generation?
If not, this issue can probably be closed.

[bizk]

@tac0turtle
The non-constant function, only affects go version, while performing public key generation. This occurs due to some optimizations in the algorithm: when certain conditions are meet, some calculations are avoided. The overall algorithmic complexity is still O(N), so the difference should be marginal.

• This issue affects public key generation out of privates key
• It only affects Go usage, c-go version is safe (constant) to use.

While still marginal, it i a security issue that (in theory) could compromise users in the future.

I will be running some benchmarks, I'm also looking into de optimizing such function, so we can make go version constant time :)

[bizk]

I've been reviewing the available secp256k1 implementations on go pkgs, seems like most of the cases are using dcred or a cwrapper version. So here are a few options from less to more effort:

• Ignore the go implementation and call users to use C-go wrapper (this has been audited, and it is secure, but leaves anyone using the go version exposed)
• Add an implementation made on the following implementation. I've audited it and seems to be constant, I still need to check it against the specifications on the paper/theory.
• Spin off an edit over dcred implementation without the optimizations
• Create an implementation from scratchm, less desirable, this one involves more work and we would need to run audits

I would personally opt to use the implementation from foomiche, adding the code as is, and make the necessary testing to ensure that things are running as before. I don't think leaving a security hole is a good idea, we are safe for now until we are not anymore.

What are your thoughts @tac0turtle ?