Closed tac0turtle closed 10 months ago
There are two operations that are not constant time in the signing algorithm:
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.
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.
Reproducible build with c dependency could be managed using nix
@elias-orijtech this perhaps could be up your alley.
zondax is looking into this
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.
@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.
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 :)
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:
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 ?
i believe we should look into using the cgo version more natively the issue that arises is around when geth is imported then the cwrappers conflict causing issues for users.
id propose we close this issue and work on the fixing the linking issue
I see... What we can do is add the constant time implementation for go users and solve this ticket since it is a security concern. Then start working on the issue related to the use of the cgo natively which I believe it will involve a different scope
Issue from tendermint in regards to secp256k1. this key is being added directly into the SDK