Avalanche Protocol Signature Exploit: Part Three

Responding to the Avalanche team's internal report that they sent back to me after the first two reports I submitted to them on February 14th & 15th, 2023. For those curious, that report was published in the Librechain Telegram channel. Follow there and on Twitter for more information.

I'll try to keep my responses brief and to the point here so that our dialogue can remain as productive as possible.

AvalancheGo Signing Logic Review

Under this section, you identify the following operations:

Sign
SignHash
ecdsa.Sign
signRFC6979
secp256k1.NonceRFC6979
rawSigToSig

My first gripe is with this statement here: "The code used for signature generation and verification does not need to be in AvalancheGo to be invoked. Its absence in the source code of AvalancheGo is the standard pattern for calling a function on an external package."

Semantically, I don't understand it because at face value it sounds like you all are suggesting that code that does not exist can be invoked. However, I'm assuming what is meant here is that the function does not need to be defined in AvalancheGo in order for it to be invoked and defined in the same manner as specified in the library from which the command is inherited.

If I'm correct in my interpretation then, yes, we're in agreement here. However, the issue I raised was that certain functions alluded to weren't called at all in AvalancheGo (much less defined anywhere).

ecdsa.SignCompact

For some reason, the link referenced here underneath this function points to: https://github.com/decred/dcrd/blob/9408498fd00555dd268e4987e5c89cd53ab9051f/dcrec/secp256k1/ecdsa/signature.go#L755-L780

However, that is not where the library is inherited from.

The library used in secp256k1r.go inherits from: https://pkg.go.dev/github.com/decred/dcrd/dcrec/secp256k1/v3/ecdsa

Note if you remove the https://pkg.go.dev/ portion of the URL, you are left with the package name, which is github.com/decred/dcrd/dcrec/secp256k1/v3/ecdsa

The AvalancheGo code is even shown among the list of importers of this library on the Go pkg site.

In the ReadMe, it's noted that the library, "supports a custom 'compact' signature format which allows efficient recovery of the public key from a given valid signature and message hash combination".

The function in question referenced here (SignCompact), is defined in full here:

Specifically, the library defines the function as: func SignCompact(key *secp256k1.PrivateKey, hash []byte, isCompressedKey bool) []byte

As stated in the library, this function is defined as follows:

"SignCompact produces a compact ECDSA signature over the secp256k1 curve for the provided hash (which should be the result of hashing a larger message) using the given private key. The isCompressedKey parameter specifies if the produced signature should reference a compressed public key or not."

In the notes that you all passed back to me, you all referenced code located here: https://github.com/decred/dcrd/blob/9408498fd00555dd268e4987e5c89cd53ab9051f/dcrec/secp256k1/ecdsa/signature.go#L755-L780

The only thing that secp256k1r.go inherits is the function signature from the library. The values that are passed to that signature in another piece of code (not referenced in the Avalanche file in question).

For coherency purposes, I'm going to briefly walk down what the Decred code does (replacing their code notes with mine).

// this code iterates the SignCompact function as defined in the library
// the variables "key *secp256k1.PrivateKey", "hash []byte", and "isCompressedKey bool" are 
// all arguments passed to the function
func SignCompact(key *secp256k1.PrivateKey, hash []byte, isCompressedKey bool) []byte {
    sig, pubKeyRecoveryCode := signRFC6979(key, hash)
    // the code above is assigning 'key' and 'hash' (of function signRFC6979) to 'sig' and 'pubKeyRecoveryCode'
    // both 'sig' is re-defined using short variable declaration along with 'pubKeyRecoveryCode' 
    // the only way to derive a valid value for sig in the decred construction is for `signRFC6979` to be
    // defined, which it isn't in the AvalancheGo code. This code in decred is only defining the value
    // of these variables at RUNTIME and within the function (not globally)
    compactSigRecoveryCode := compactSigMagicOffset + pubKeyRecoveryCode
    // code above initializes "compactSigRecoveryCode" variable as the concatenation of 
    // compactMagicOffset and pubKeyRecoveryCode (the latter we just defined in the prev line)
    if isCompressedKey {
        compactSigRecoveryCode += compactSigCompPubKey
    }
    // code above dictates that if the boolean for "isCompressedKey" is true or '1'
    // then compactSigRecoveryCode becomes "compactSigRecoveryCode+compactSigCompPubKey"
    // ... (remainder of code redacted for brevity sake)
}

The misunderstanding here on Avalanche dev's end seems to be in the assumption that the variables declared within the body of the SignCompact function in Decred's signature.go file (located in a different, non-referenced codebase), is transposable to the SignCompact' fucntion as defined in AvalancheGo's secp256k1r.go` code.

This is not the case. It's also not possible, logical or in line with Golang's code construction (or that of any programming language).

i'm hoping that we're on the same page with this moving forward.

signRFC6979

As noted in the Avalanche dev notes, this function is explicitly only defined in Decred's code (signature.go). There is no function signature for signRFC6979.

This is defined in the Decred source file that you all reference in your annotations at line 622 as thus:

// signRFC6979 generates a deterministic ECDSA signature according to RFC 6979
// and BIP0062 and returns it along with an additional public key recovery code
// for efficiently recovering the public key from the signature.
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++ {
        // here, the 'k' variable is generated by through the result returned by the 
        // NonceRFC6979 function of the secp256k1 library which takes in the private key
        // and the hash of the message as inputs for the HMAC-SHA256 algorithm 
        // the result of the HMAC-SHA256 is the value given to 'k' as a variable (initialized); nonce
        k := secp256k1.NonceRFC6979(privKeyBytes[:], hash, nil, nil, iteration)
        // the variables 'sig' and 'pubKeyRecoveryCode' are assigned after the 'sign' function is iterated
        // with the 'privKeyScalar', 'k' (nonce we just derived), and 'hash' [all defined within this function]
        // are passed to the 'sign' function (lowercase 's' for sign), which is defined in line 548. 
        // there are a few critical constructions of the 'sign' function in decred's code which are absent from 
        // the AvalancheGo code construction - but we'll touch on that afterward. 
        // ultimately, the biggest contribution made to the code via this function is the definition of 's' and 'r'
        sig, pubKeyRecoveryCode, success := sign(privKeyScalar, k, hash)
        k.Zero()
        if !success {
            continue
        }

        return sig, pubKeyRecoveryCode
    }
}

Under #4 in the 'AvalancheGo Signing Logic Review', you all write: "The comment at the start of the function (which is called in “3) SignCompact”) states that the purpose of the entire function is to 'generate a deterministic ECDSA signature according to RFC 6979'".

I think the issue here is you all are getting a bit too fixated on the idea of the signature being deterministic vs. the validity of the signature produced.

To be clear, there is no dispute from me that the signatures that AvalancheGo produces are deterministic - without a doubt. The issue is that those signatures are not generated in a secure manner. The means by which that can be done is facilitated through the handling and generation of the nonce that's constructed as part of secp256k1 signature operations.

Ignore the Code Notes for a Second

I know that the code notes above signRFC6979 state that it "generates a deterministic ECDSA signature according to RFC 6979...", but that's not what that function is specifically purposed for.

Its role in the greater scheme of this scheme we're looking at (in Decred's codebase), is to solicit the private key and the hash of the message that is to be signed for the purposes of piping those two variables into HMAC-SHA256.

As noted in your developer notes returned to me, the specific function responsible for piping inputs into HMAC-SHA256 is NonceRFC6979. The inclusion of the NonceRFC6979 function within the body of the signRFC6979 function is not the default behavior. Specifically, that function was called to provide a 'short variable declaration' for 'k', which serves as our nonce value for the signature operation.

All the NonceRFC6979 does (by itself) take inputs (typically private key & message hash plus any other ancillary params & the # of iterations) and pipe them into the HMAC-SHA256 construction. That's it.

It is up to the developer/coder to use the 'short variable declaration' feature of Golang to assign the output of this resolution to a variable ('k' in the case of Decred's code). Also, it is the developer's responsibility to ensure that the function is called explicitly as that is the only way the code can specify what values, exactly, we want to pass to that function as an argument.

To reiterate, those values were derived by the signRFC6979 function, which is one not defined anywhere in any of the imported libraries. This is a custom, unique function that is defined for the purpose of being iterated at runtime.

There's no reason to suggest or propose that this function is iterated anywhere in the AvalancheGo code.

secp256k1.NonceRFC6979

We've already covered this function (NonceRFC6979) for the most part in the response that I provided above.

The signature.go file for Decred didn't need to define the function since it's derived from one of the imported libraries listed explicitly at the file's header (their secp256k1 Golang library).

None of This Code is Iterated or Called in AvalancheGo

Again, to be clear - this function is neither called nor invoked anywhere in the Avalanche Golang code.

Referring back to the initial function that was referenced (SignCompact), that function is defined by its corresponding library (function signature), which has already been pointed out explicitly.

The inclusion of the variable signRFC6979 within the body of that function in Decred's codebase (signature.go) has no bearing or relevance on the code in AvalancheGo.

If anything, that Decred file should be used as a blueprint for proper implementation that AvalancheGo can use because it makes it explicitly clear that the compliant signatures we're looking for here do not just generate automatically as it appears Avalanche devs are trying to imply for some reason (no code on planet earth works this way).

How AvalancheGo Actually Signs Code

We'll start with the Sign function, which is used & defined in AvalancheGo's code is thus:

func (k *PrivateKeySECP256K1R) Sign(msg []byte) ([]byte, error) {
    return k.SignHash(hashing.ComputeHash256(msg))
}

All this code above says is:

Use the private key (newly generated) to perform the Sign function on the 'msg'.
Performing the task outlined in #1 will return the results of the SignHash function (when executed with our private key) on the sha256 hash of the msg.
What we wrote in #2 falls in line with how the Sign function is defined in the actual library, which is: func Sign(key *secp256k1.PrivateKey, hash []byte) *Signature.

Nowhere in AvalancheGo's code is the NonceRFC6979 construction iterated.

Also, yes, it must be specifically called to be iterated because that output is what's piped into the nonce for the signature operation (no mention of a 'nonce' value at all in the AvalancheGo documentation).

Again, the fact that the signatures are generated deterministically are neither here nor there because the nonce is what counts in this construction.

Avalanche Protocol Signature Exploit: Part Three

Comments

Avalanche Exploit

Avalanche Protocol Signature Exploit: Part Four

More from this blog

Bitcoin March 2025 Price Analysis Update

Understanding How Upgradable Smart Contracts Work (WazirX)

WazirX Transaction Analysis

WazirX Background Information

Bitcoin Price Analysis (September 18th, 2024)

AvalancheGo Signing Logic Review

ecdsa.SignCompact

signRFC6979

secp256k1.NonceRFC6979

None of This Code is Iterated or Called in AvalancheGo

How AvalancheGo Actually Signs Code

Command Palette

Comments

Avalanche Exploit

Avalanche Protocol Signature Exploit: Part Four

More from this blog

AvalancheGo Signing Logic Review

ecdsa.SignCompact

signRFC6979

secp256k1.NonceRFC6979

None of This Code is Iterated or Called in AvalancheGo

How AvalancheGo Actually Signs Code