Avalanche Protocol Signature Exploit: Part Two
Critical 0Day Ignored by Team Allows for Trivial Recovery of Validator Private Keys. Entire Project Should be Considered Compromised
This series includes each report I sent to the Avalanche protocol team detailing a potent zero-day vulnerability in their AvalancheGo implementation that allows for the recovery of private keys from signatures formed by nodes & validators. This vulnerability, which they refuse to patch, allows for the private keys of validators to be forged, which essentially renders the entire protocol compromised. If there's anybody out there that's using Avalanche at the time of writing...my best advice as an objective observer and researcher would be to remove any and all funds you have on this protocol ASAP.
Everything below includes what I sent to the Avalanche dev team on HackenProof as a follow-up to the initial report I sent to them about this issue. This was sent within 12-24 hours of the first report.
Official Report to Avalanche Developers (Part Two)
So after taking even more time to look through the code and speak to one of the former developers/maintainers of Avalanche's codebase (and supposed documentation manager as well), I came to a few epiphanies.
Avalanche's Javascript (avalancheJS) is good to go since it imports from the NPM library, 'ellpitic'. That library specifically notes that "ECDSA is using deterministic
kvalue generation as perRFC 6979. Most of the curve opeartions are performed on non-affine coordinates (either projective or extended), various windowing techniques are used for different cases." I'd have to go through and check again but I'm pretty sure that this exonerates AvalancheJS entirely (not sure how much this really matters though since the JS library is outside of the scope of what this bug bounty is looking to debug)The AvalancheGo code contains references to the proper library. It just doesn't call the function necessary to ensure that the 'k' is generated deterministically.
secpk1r.go
One file in particular in your Golang codebase is responsible for governing its implementation of secpk1.
That would be avalanchego/utils/crypto/secp256k1r.go, located here.
In the header of that file are two meaningful import statements (re-published below for convenience):
A) "github.com/decred/dcrd/dcrec/secp256k1/v3/ecdsa"
B) secp256k1 "github.com/decred/dcrd/dcrec/secp256k1/v3"
Both statements reference the Decred ecdsa/secp256k1 Golang library. We'll zero in on the secp256k1 library since that's most relevant to the topic at hand.
Please note that the hyperlink above takes us to v3, not v4 (latest iteration), in accordance to where the import statements point.
The 'homepage' for this Golang package lists the various features & capabilities of its secp256k1 library. Notably, the devs state:
"Package secp256k1 implements optimized secp256k1 elliptic curve operations."
"Specialized types for performing optimized and constant time field operations;
FieldValtype for working modulo the secp256k1 field prime" and "ModNScalartype for working modulo the secp256k1 group order"It allows for point addition, point doubling, scalar multiplication w arbitrary point, & scalar multiplication w the base point (the latter is worth mentioning since that operation is necessary for us to construct a proper signature proof using
secp256k)."Nonce generation via RFC6979 with support for extra data and version information that can be used to prevent nonce reuse between signing algorithms."
The last feature quoted above is the most relevant here for obvious reasons. When I saw that statement, I initially thought that this bug bounty was dead in the water.
However, upon closer examination of this particular library, I noticed that there was a specific function set aside and defined to ensure deterministic 'k' (nonce) generation for ECDSA (secp256k1) in accordance with RFC-6979.
Function NonceRFC6979
As shown above, the function is defined as: func NonceRFC6979(privKey []byte, hash []byte, extra []byte, version []byte, extraIterations uint32) *ModNScalar.
The library's authors note that "NonceRFC6979 generates a nonce deterministically according to RFC 6979 using HMAC-SHA256 for the hashing function. It takes a 32-byte hash as an input and returns a 32-byte nonce to be used for deterministic signing. The extra and version arguments are optional, but allow additional data to be added to the input of the HMAC. When provided, the extra data must be 32-bytes and version must be 16 bytes or they will be ignored."
Func NonceRFC6979 Absent From the Code
Nowhere in any of Avalanche's .go files is this function iterated.
Decred's secp256k1 library is the only one imported by Avalanche in their Golang codebase that's equipped to adequately serve as a library for the implementation of secp256k1. Within this library, the aforementioned function (
NonceRFC6979), is the only function within it that provisions for the creation of deterministic 'k' (nonces) values in accordance with RFC-6979 for secp256k1 signatures.The prior two statements being true means that there is nowhere in the code where
RFC-6979deterministic k nonces are provisioned.
That last factual statement iterated in #3 means that there is no secure means of generating the 'k' nonce for signature operations in Avalanche's Golang codebase because there are no other known secure means of generating the 'k' value outside of the specification outlined in RFC-6979 for secp256k1.
Therefore, whether a 'PoC' is provided or not, it should be considered virtually irrefutable that user private keys are likely at grave risk- even if the community is not suffering from widespread theft just yet. That only means that this fact has gone under the radar, which isn't too farfetched if Avalanche's developers made this oversight (that statement is not meant to be sarcastic or insulting in any way; just illuminating the fact that devs as brilliant as the ones working BTS on Avalanche can fail to catch things like this, so how much more likely is it that a random blackhat will notice?).
More Insight into the Omission
If we take a closer look at the secp256k1 library provided by Decred, we can see that the function (NonceRFC6979) is defined under a subsection of types called ModNScalar.
Notably, only two functions underneath this subtype of the secp256k library (ModNScalar) is called in the secpk1r.go file.
Those are encompassed at the end of the file between lines 278-289:
func verifySECP256K1RSignatureFormat(sig []byte) error {
if len(sig) != SECP256K1RSigLen {
return errInvalidSigLen
}
var s secp256k1.ModNScalar
s.SetByteSlice(sig[32:64])
if s.IsOverHalfOrder() {
return errMutatedSig
}
returun nil
}
Very specifically, I am referring to:
func s.SetByteSlice: "IsOverHalfOrder returns whether or not the scalar exceeds the group order divided by 2 in constant time." [func (s *ModNScalar) IsOverHalfOrder() bool]func s.SetByteSlice: "SetByteSlice interprets the provided slice as a 256-bit big-endian unsigned integer (meaning it is truncated to the first 32 bytes), packs it into the internal field value representation, and returns whether or not the resulting truncated 256-bit integer is greater than or equal to the field prime (aka it overflowed) in constant time." [func (f *FieldVal) SetByteSlice(b []byte) bool]
Otherwise, there are nearly 20 other functions available under this type that are never called for some reason.
Conversely - however, almost all defined functions under type PrivateKey and type PublicKey are iterated somewhere in secp256k1r.go.
New Suggestions for Improvement / Rectify the Situation
All that likely needs to be done is AvalancheGo going back into the code in that file (secpk1r.go), and including functions such as NonceRFC6979 to derive a secure, deterministic 'k' nonce value for each message signed using secp256k1.
Points Supporting Why This Change Should be Made
Its secure
It adheres to SOA and standard for secure secp256k1 signature generation
Averts the potential catastrophic loss of unfathomable proportions in an alternate scenario where no action is taken.
There are no tangible 'negatives', 'caveats' or "drawbacks" associated with this upgrade/fix in the way
secp256k1is implemented in the code.
Let's Check Out the Current secp256k1 Avalanche.go's Function for Signatures
func (k *PrivateKeySECP256K1R) Sign(msg []byte) ([]byte, error) {
return k.SignHash(hashing.ComputeHash256(msg))
}
Let's Check Out How Decred's secp256k1 Defines a Function for the Same Activity** (Signature)
type Signature struct {
r secp256k1.ModNScalar
s secp256k1.ModNScalar
}
// NewSignature instantiates a new signature given some r and s values.
func NewSignature(r, s *secp256k1.ModNScalar) *Signature {
return &Signature{*r, *s}
}
// Might as well serialize the signature while we're here, right?
func (sig *Signature) Serialize() []byte {
sigS := new(secp256k1.ModNScalar).Set(&sig.s)
if sigS.IsOverHalfOrder() {
sigS.Negate()
}
...
}
// *The* `signature.go` *file for Decred's project includes functions for converting a 'field value' to 'scalar modulo the group order'* (returning a boolean of 0/1 contingent on whether conversion resulted in `overflow`; `0` otherwise)
func fieldToModNScalar(v *secp256k1.FieldVal) (secp256k1.ModNScalar, uint32) {
var buf [32]byte
v.PutBytes(&buf)
var s secp256k1.ModNScalar
overflow := s.SetBytes(&buf)
zeroArray32(&buf)
return s, overflow
}
// *This is the code where the scalar modulo of a group order is converted to a field order* (not even sure what the point of this would be since the prime order of `secp256k` is so close to the value of the `finite field` [$F_p$])
func fieldToModNScalar(v *secp256k1.FieldVal) (secp256k1.ModNScalar, uint32) {
var buf [32]byte
v.PutBytes(&buf)
var s secp256k1.ModNScalar
overflow := s.SetBytes(&buf)
zeroArray32(&buf)
return s, overflow
}
The most marked difference between the two iterations of Decred's library (Avalanche vs Decred) can be seen in Decred's implementation of the 'sign' function as it accounts for the deterministically random 'k nonce value that this bug report centers around.
Specifically, the Decred signature.go file iterates the function as such (code notes included since that's a feature as well imo):
// sign generates an ECDSA signature over the secp256k1 curve for the provided
// hash (which should be the result of hashing a larger message) using the given
// nonce and private key and returns it along with an additional public key
// recovery code and success indicator. Upon success, the produced signature is
// deterministic (same message, nonce, and key yield the same signature) and
// canonical in accordance with BIP0062.
//
// Note that signRFC6979 makes use of this function as it is the primary ECDSA
// signing logic. It differs in that it accepts a nonce to use when signing and
// may not successfully produce a valid signature for the given nonce. It is
// primarily separated for testing purposes.
func sign(privKey, nonce *secp256k1.ModNScalar, hash []byte) (*Signature, byte, bool) {
// Author Note: This next collection of code notes shows how critical the RFC-6979 secp256k1 signature
// construction was for ensuring the soundness of the entire algorithm. Those notes are reposted from here
// --------------------------------------
// "The following is a paraphrased version for reference:
//
// G = curve generator
// N = curve order
// d = private key
// m = message
// r, s = signature
//
// 1.) Select random nonce k in [1, N-1] (author's note: notable that this is listed as the FIRST step in
// signature generation by the authors of Decred's secp256k1 library that Avalanche uses)
// 2.) Compute kG (this gives us the 'R' value, which is an x, y coordinate)
// 3.) r = kG.x mod N (kG.x is the x coordinate of the point kG)
// ... Repeat from step 1 if r = 0
// 4.) e = H(m)
// 5.) s = k^-1(e + dr) mod N [author's note: this is the signature proof right here!]
// ... Repeat from step 1 if s = 0
// 6. Return (r, s)
//
// This is slightly modified here to conform to RFC6979 and BIP 62 as follows:
//
// A. Instead of selceting a random nonce in step 1, use RFC6979 to generate a deterministic
// nonce in [1, N-1] parameterized by the private key, message being signed, and an iteration count for
// the repeat cases .
//
// B. Negate s calculated in step 5 if it is > N/2.
// ... This is done because both s and its negation are valid signatures (author's ntoe: since 'y' can take on
// either positive/negative values on the elliptic curve) modulo the curve order N,
// so it forces a consistent choice to reduce signature malleability (author's note: love this!
// Decred goes above and beyond here with the additional consideration to modulo the entire proof
// by 'n', which is the prime order of the cyclic subgroup for the curve itself).
//
// NOTE: Step 1 is performed by the caller.
//
// Step 2.
//
// Compute kG
//
// Note that the piont must be in affine coordinates (author's note: this is yet another important consideration)
k := nonce
var kG secp256k1.JacobianPoint
secp256k1.ScalarBaseMultNonConst(k, &kG)
kG.ToAffine()
// Step 3.
//
// r = kG.x mod N
// Repeat from step 1 if r = 0
r, overflow := fieldToModScalar(&kG.X)
if r.IsZero() {
return nil, 0, false
}
// Since the secp256k1 curve has a cofactor of 1, when recovering the public key from an ECSA
// signature over it, there are four possible candidates corresponding to the following cases:
//
// 1) The X coord of the random point is < N and its Y coord even
// 2) The X coord of the random point is < N and its Y coord odd
// 3) The X coord of the random point is >= N and its Y coord even
// 4) The X coord of the random point is >= N and its Y coord odd
//
// Rather than forcing the recovery procedure to check all possibel cases, this creates
// a recovery code that uniquely identifies which of the cases apply by making use of
// 2bits. Bit 0 identifies the oddness case and Bit 1 identifies the overlfow case (aka when
// the X coord >= N).
//
// It is also worth noting that making use of Hasse's theorem shows there are around
// log_2((p-n/p) ~= -127.65 ~= 1 in 2^127 points where the X coordinate is >= N. It is
// not possible to calculate these points sionce that would require breaking the ECDLP
// but, in practice this strongly implies that with extremely high probability that there
// are only a few actual points for which this case is true.
pubKeyRecoveryCode := byte(overflow<<1) | byte(kG.Y.IsOddBit())
// Step 4.
//
// e = H(m)
//
// Note that this actually sets e = H(m) mod N which is correct since it is only
// used in step 5 which itself is mod N.
var e secp256k1.ModNScalar
e.SetByteSlice(hash)
// Step 5 with modification B.
//
// s = k^-1(e + dr) mod N
// Repeat from step 1 if s = 0
// s = -s if s > N/2
kinv := new(secp256k1.ModNScalar).InverseValNonConst(k)
s := new(secp256k1.ModNScalar).Mul2(privKey, &r).Add(&e).Mul(kinv)
if s.IsZero() {
return nil, 0, false
}
if s.IsOverHalfOrder() {
s.Negate()
// Negating s corresponds to the random point that owuld have been generated by
// -k (mod N), which necessarily has the opposite oddness since N is prime,
// thus flip the pubkey recovery code oddness bit accordingly
pubKeyRecoveryCode ^= 0x01
}
// Step 6.
//
// Return (r, s)
return NewSignature(&r, s), pubKeyRecoveryCode, true
}
// That's not even all; from here the actual RFC6979 signature construction is included in the code
func signRFC6979(privKey *secp256k1.PrivateKey, hash []byte) (*Signature, byte) {
privKeyScalar := &privKey.Key
var privKeyBytes [32]byte
privKeyScalar.PutBytes(&privKeyBytes)
defer zeroArray32(&privKeyBytes)
for iteration := uint32(0); ; iteration++ {
k := secp256k1.NonceRFC6979(privKeyBytes[:], hash, nil, nil, iteration)
// Steps 2-6.
sig, pubKeyRecoveryCode, success := sign(privKeyScalar, k, hash)
k.Zero()
if !success {
continue
}
return sig, pubKeyRecoveryCode
}
// All the code is concluded with the following sign function
func Sign(key *secp256k1.PrivateKey, hash []byte) *Signature {
signature, _ := signRFC6979(key, hash)
return signature
}
}
Decred's Signature Verification = More Robust + Secure Too
In addition, Decred's signature verification scheme is more robust than the one currently implemented by Avalanche in their Golang codebase.
Avalanche's Current Go-based Construction for Sig Verification (from secp256k1r.go)
func (k *PublicKeySECP256K1R) Verify(msg, sig []byte) bool {
return k.VerifyHash(hashing.ComputeHash256(msg), sig)
}
func (k *PublicKeySECP256K1R) VerifyHash(hash, sig []byte) bool {
factory := FactorySECP256K1R{}
pk, err := factory.RecoverHashPublicKey(hash, sig)
if err != nil {
return false
}
return k.Address() == pk.Address()
}
Decred's Iteration of Signature Verification for secp256k per Their Project's Specifications
func (sig *Signature) Verify(hash []byte, pubKey *secp256k1.PublicKey) bool {
if sig.r.IsZero() || sig.s.IsZero() {
return false
}
var e secp256k1.ModNScalar
e.SetByteSlice(hash)
w := new(secp256k1.ModNScalar).InverseValNonConst(&sig.s)
u1 := new(secp256k1.ModNScalar).Mul2(&e, w)
u2 := new(secp256k1.ModNScalar).Mul2(&sig.r, w)
var X, Q, u1G, u2Q secp256k1.JacobianPoint
pubKey.AsJacobian(&Q)
secp256k1.ScalarBaseMultNonConst(u1, &u1G)
secp256k1.ScalarMultNonConst(u2, &Q, &u2Q)
secp256k1.AddNonConst(&u1G, &u2Q, &X)
if (X.X.IsZero() && X.Y.IsZero()) || X.Z.IsZero() {
return false
}
z := new(secp256k1.FieldVal).SquareVal(&X.Z)
sigRModP := modNScalarToField(&sig.r)
result := new(secp256k1.FieldVal).Mul2(&sigRModP, z).Normalize()
if result.Equals(&X.X) {
return true
}
if sigRModP.IsGtOrEqPrimeMinusOrder() {
return false
}
sigRModP.Add(&orderAsFieldVal)
result.Mul2(&sigRModP, z).Normalize()
return result.Equals(&X.X)
}
// *Also this brief call to an* `IsEqual` *function*
func (sig *Signature) IsEqual(otherSig *Signature) bool {
return sig.r.Equals(&otherSig.r) && sig.s.Equals(&otherSig.s)
}
Concluding Thoughts and Suggestions
To me, it seems like a no-brainer to 'copy' over Decred's implementation of secp256k1 since the Avalanche Golang library already imports directly from the project's secp256k1 library as it is. All Avalanche would have to do is update the version for the package they call (from v3 to v4), and adjust the
signandsignaturefunctions accordingly (anything beyond that is luxury)The signature scheme for secp256k1 implemented by Decred (using the same library called on by Avalanche Go) exemplifies the types of changes that Avalanche should look to embrace if they want to secure users from the imminent & likely burgeoning threat that they will have their wallets drained in lieu of this approach. To reiterate what was stated earlier in this 3rd report, the RFC 6979 specification for secure secp256k1 (deterministic) signatures is really the only standard that accomplishes such. Thus, there are no other audited, publicly specified and scrutinized methods for generating secp256k1 signatures that meet the bar.
While the developers of Avalanche may not necessarily consider this to be a 'bug', I believe that it absolutely is. One reason I make this claim is that the library (Decred's secp256k1) is referenced in the 'import' function in the header of the
secp256k1r.go(Avalanche) file already contains the RFC 6979 signature specification I've been mentioning. The actual function as defined by the library just wasn't included in Avalanche's codebase for some reason - which leads me to believe that this was just a mere oversight, mistake, etc., rather than a purposeful decision by the team. This deterministic nonce-based signature construction forsecp256k1is a prominent feature of the Decred secp256k1 library. As we saw from the code excerpts above, it was a major consideration that the devs of the library took into account whilst coding thesignature.gofile of the Decred file.
In my opinion, I believe the Avalanche development team should be in agreement with me that (a) the aforementioned changes in this 3rd report should be implemented at some point in the foreseeable future (b) the current iteration of Avalanche's Golang codebase that's devoid of these proposed changes serves as an existential threat that it poses the threat of complete compromise and total loss of funds of all those that use it - either directly or indirectly.
This risk should be seen as unpalatable by the Avalanche dev team. With that being said, I'm not proposing that the team shift into emergency protocol to make sweeping changes to very critical, sensitive pieces of the protocol over night - but given the critical nature of these proposed updates and the near guarantee that the pending catastrophic outcome facing Avalanche will be brought to fruition in lieu of affirmative action on this matter, I believe we're all collectively on the same page in our beliefs that something should be done. Soon.