Since Avalanche chose to screw me out of a $10k bug bounty, I've elected to publish this research for free for the benefit of the community. While I have no problem doing so, the key to being able to continue publishing such research is sustainability.

Thus, I have a tip jar (Bitcoin) hosted here for all those that would like to show their appreciation or simply contribute. Thanks!

Bitcoin: 1HJTmhDovvLTWosyucb2dEFKJwWAfQqKn2

ETH: 0xa84c0ae8c7aea26e5956c3b5febd167c93be0d05

Sadly, it's come to this. After reporting a potent issue in the Golang cryptographic library used by Avalanche on February 14th, 2023, I expected that the team was going to address this issue since it was so obvious and well-documented.

I'm not going to waste too much time re-summarizing the core issue at hand since they've already been covered ad nauseum in the Telegram channel and in previous posts on this blog.

AvalancheGo Does Not Generate Proper Signatures

We're going to prove that the AvalancheGo does not generate signatures properly. The AvalancheGo main repo can be found here.

Instructions:

git clone https://github.com/ava-labs/avalanchego.git
cd avalanchego
cd main

Once in the main/ directory, we're going to run rm -r main.go. We're going to replace this file with another one that I wrote to directly test the signatures generated with the repo.

I have that file hosted on GitHub as a gist. For those too lazy to visit, the source code is published below:

package main

import (
  "encoding/hex"
  "fmt"

  "github.com/ava-labs/avalanchego/utils/crypto"
)

func main() {
  // Hexadecimal private key
  privateKeyHex := "eeac0e3d8f0fcc32a553cc5ab8dad48a435bb4c047d95b06eb7a29a4a823e87c"

  // Parse the private key
  privateKeyBytes, _ := hex.DecodeString(privateKeyHex)

  // Create a new private key object from the parsed bytes
  // factory := &FactorySECP256K1R{}
  factory := &crypto.FactorySECP256K1R{}
  privateKey, err := factory.ToPrivateKey(privateKeyBytes)
  if err != nil {
    panic(err)
  }

  // Print the private key in hex format
  fmt.Printf("Private key: %x\n", privateKeyBytes)

  // Derive the public key from the private key
  publicKey := privateKey.PublicKey()

  // Print the public key in hex format
  fmt.Printf("Public key: %x\n", publicKey.Bytes())

  // Sign a message using the private key
  message := []byte("avalanchesignature")
  signature, err := privateKey.Sign(message)
  if err != nil {
    panic(err)
  }

  // Parse the signature
 // r, s, v, err := parseSignature(signature)
 // if err != nil {
 //   panic(err)
 // }

  // Print the signature and its components
  fmt.Printf("Signature: %x\n", signature)
//  fmt.Printf("r: %d\n", r)
//  fmt.Printf("s: %x\n", s)
//  fmt.Printf("v: %d\n", v)
}

Once we have the code, we're going to copy/paste it into the main/ directory and name it main.go.

Brief Explanation of What This Code Does

This code takes a hexadecimal private key (eeac0e3d8...823e87c).
The key is parsed.
We create a new private key from the parsed bytes using factory := &crypto.FactorySECP256K1R. I'm mentioning this part to make it clear that we're using the AvalancheGo library specifically (which we have linked in the header underneath the import statement).
The code then uses that same library to derive the public key from said private key.
We then sign a message. That message is avalanchesignature.
Code to parse the signature was omitted due to time constraints and it being slightly outside of the scope of what we need to do here
Signature is created with the private key signing over the message we identified in step 5. The function called to perform the signing operation is Sign, which is a call directly to the AvalancheGo library cited at the top in the import statement.

Iterating the Code

Assuming you all have edited main.go all you have to do now is enter the command: go run main.go.

This will result in the following output being spit back out at you:

Most importantly, we have the CompactSignature in DER format.

Expanding that value to derive the serialized DER hash yields us: 3045022100c5d2d9a05c2cdb34f4260dd18ba52eb5b041c8edb52eb9bae9b0743580adb9c302202f092fc8ae6fa720ebd99894ce9d7fcc473be582959eed8b9ac0b9a0c9265f06.

We'll see a bit further along that this signature, while valid, is not in accordance with the RFC6979 standard.

Comparing the Hash Produced to Decred's Library

Even though Decred is listed in the header of the secp256k1r.go file as an import, very little of the code pulls from functions in that library.

This is worth noting because when the Avalanche team sent me a longform documented response to the "claims" I had raised, they erroneously (and falsely) claimed that their library inherited several functions from this library that it in fact, didn't.

Below is an excerpt from that communication.

The two functions in the screenshot above that the team referenced are Sign and SignHash.

This clearly isn't the case and proving otherwise was a trivial task handled through VSCode (see below).

The function takes us to the AvalancheGo Golang package.

Some functions derive from the Decred library, but this is not the library that governs how the secp256k1 signatures are formed.

This is a critical distinction to make because it is one of the chief claims that the Avalanche team made in their denial of the real attack vector their project faces.

Comparing Decred Signatures vs. Avalanche

The Decred code properly formulates signatures in accordance with RFC6979. As noted in one of the other reports published, the Avalanche team claimed that their code also provided such signatures. However, this is not true.

As a brief Proof of Concept for this issue, I took the same private key and message to be signed that you all saw earlier and produced a DER-encoded signature output that was different from what we saw with Avalanche's code.

That code can be found here.

Below is the literal code produced to create the signature.

package main

import (
    "encoding/hex"
    "fmt"

    "github.com/decred/dcrd/dcrec/secp256k1/v3"
    "github.com/decred/dcrd/dcrec/secp256k1/v3/ecdsa"
)

func main() {
    // Hexadecimal private key
    // (ignore) privateKeyHex := "99f0cf7355bffdeea25728a93848595f8ac65596f244501fd167717f969b18f2"

    // Decode a hex-encoded private key.
    pkBytes, err := hex.DecodeString("eeac0e3d8f0fcc32a553cc5ab8dad48a435bb4c047d95b06eb7a29a4a823e87c")
    if err != nil {
        fmt.Println(err)
        return
    }
    privKey := secp256k1.PrivKeyFromBytes(pkBytes)

    // Parse the private key
    // privateKeyBytes, _ := hex.DecodeString(privateKeyHex)

    // Create a new private key object from the parsed bytes
    // factory := &FactorySECP256K1R{}
    //  factory := &crypto.FactorySECP256K1R{}
    //  privateKey, err := factory.ToPrivateKey(privateKeyBytes)
    //  if err != nil {
    //   panic(err)
    // }

    // Print the private key in hex format
    fmt.Printf("Private key: %x\n", privKey)

    // Derive the public key from the private key
    // publicKey := privKey.PublicKey()

    // Print the public key in hex format
    // fmt.Printf("Public key: %x\n", publicKey.Bytes())

    // Sign a message using the private key
    message := "avalanchesignature"
    // message := []byte("Hello, world!")

    // messageHash := chainhash.HashB([]byte(message))
    signature := ecdsa.Sign(privKey, []byte(message))

    fmt.Printf("Signature: %x\n", signature)
    //  signature, err := privateKey.Sign(message)
    //  if err != nil {
    //   panic(err)
    //  }

    // Parse the signature

    // Print the signature and its components
    fmt.Printf("Signature: %x\n", signature)

    // Serialize and display the signature.
    fmt.Printf("Serialized Signature: %x\n", signature.Serialize())
}

func parseSignature(sig []byte) (r int64, s []byte, v int64, err error) {
    if len(sig) != 65 {
        err = fmt.Errorf("invalid signature length: %d", len(sig))
        return
    }
    r = int64(sig[0])
    s = sig[1:33]
    v = int64(sig[64])

    fmt.Printf("r: %d\n", r)
    fmt.Printf("s: %x\n", s)
    fmt.Printf("v: %d\n", v)
    return
}

Here is the Signature that Gets Produced: 3044022005c8e48a951107d993d2b787ddc1a3920343690dbaa306c1869299b396645704022058c37b2833467037be9cc49947f4a6920a3fa86c923a295376dc2a011e6a77e8

Here's the Avalanche signature we produced earlier: 3045022100c5d2d9a05c2cdb34f4260dd18ba52eb5b041c8edb52eb9bae9b0743580adb9c302202f092fc8ae6fa720ebd99894ce9d7fcc473be582959eed8b9ac0b9a0c9265f06

See the difference?

If the Avalanche library derived its signatures from the Decred Golang library, then it would've produced the same DER-encoded signature.

Compromising Validators on Avalanche

Disclaimer: We're merely going to walkthrough how someone could compromise validators (in theory). This has not been executed in practice by myself as it goes against my personal code of ethics. The author of this research shares no liability in how someone chooses to use this research. This is not a call to action or an encouragement to engage in any particular activity. Any and all consequences you incur for your actions are on you.

As mentioned before, one of the issues with Avalanche not generating deterministic signatures per RFC6979's specification is that the signatures created lead to private key recovery.

Thus, as promised, we're going to walkthrough how one could compromise validators (in theory). This theory has not been executed in practice because I am neither hacker nor a blackhat of any sort

Even if the signatures produced by Avalanche are deterministic (which they are), if the nonces used in the creation of said signatures are biased in some way.

Lattice Attacks on ECDSA

The attack vector we're going to explore here is called a 'lattice attack' on ECDSA.

The guide we'll use can be found here. As noted in the post, "The attack is based on the theory of short vectors in lattices and uses the LLL algorithm to recover the private key from multiple (biased) signatures."

An example repo that explores this attack can be found here (with accompanying Python code). For diversity of options, here's another repo that you can reference that provides a guide/walkthrough on these attacks, with accompanying Python code.

If you're looking for a Python script reference that exploits this attack on Bitcoin signatures, look no further than here. If you're looking for some potentially exploitable signatures among the blockchain's extensive, 10+ year-long history of operation, this blog post should serve as an adequate reference.

Brief Dive into the Methodology

Don't worry, we're not going to dig into the trenches here as far as the mathematical principles behind lattice attacks. Instead, we're going to explore the methodology necessary to implement this attack in practice.

To start, refer to the brief excerpt from the 'Lattice Attacks on ECDSA' guide we referenced earlier.

Ok, so maybe I lied about the math part - but the above was published for coherency purposes.

From here, let's explore the example Python script given which generates 40 signatures over random messages deriving a private key. As stated in the post, "the signature[s] are generated so that the employed nonce are biased by having the first bias = 1 bytes set to zero."

The relevant Python code can be found below.

from ecdsa.ecdsa import curve_256, generator_256, Public_key, Private_key
from random import randbytes, randint

G = generator_256
p = G.order()

def genKeyPair():
    d = randint(1,p-1)
    pubkey = Public_key(G, d*G)
    privkey = Private_key(pubkey, d)
    return pubkey, privkey

def sign(privkey, bias):
    m = randbytes(32)
    nonce = randbytes(32 - bias)
    sig = privkey.sign(int.from_bytes(m, "big"), int.from_bytes(nonce, "big"))
    return (m, sig.r, sig.s)

pubkey,privkey = genKeyPair()
print('Public key:', (int(pubkey.point.x()), int(pubkey.point.y())))
print('Private key:', int(privkey.secret_multiplier))

SIGs = []
for _ in range(40):
    SIGs += [sign(privkey, 1)]

SIGs

Note that running this script requires installing the python module ecdsa first (pip install ecdsa).

From here, you'll need to have 'SageMath' installed in order to run the next bit of Python code.

If you're following along, please note that you're going to have to:

Find the relevant public key for the signatures you're examining (you can recover this trivially on Avalanche since th is is a feature of the signatures that are produced on that chain).
We're going to need to replace the elliptic curve parameters at the top of the file as well.

If you visit that blog post, the elliptic curve parameters presented are:

q = 115792089210356248762697446949407573530086143415290314195533631308867097853951
A = -3
B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
F = GF(q)
E = EllipticCurve(F,[A,B])
Gx = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
Gy = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
G = E(Gx,Gy)
p = 115792089210356248762697446949407573529996955224135760342422259061068512044369
assert G.order() == p

Here's what they should be (secp256k1):

q = 115792089237316195423570985008687907853269984665640564039457584007908834671663
A = 0
B = 0x07
F = GF(q)
E = EllipticCurve(F,[A,B])
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
G = E(Gx,Gy)
p = 115792089237316195423570985008687907852837564279074904382605163141518161494337
assert G.order() == p

Below that portion of the code, you would enter the public key. Then below that is where we extract the signatures.

As the code suggests: "# SIGs contains tuples (m, r, s) with (r,s) being a signature for m under P".

How Many Signatures are Needed?

According to recent research published in 2020, titled, 'LadderLeak: Breaking ECDSA With Less Than One Bit of Nonce Leakage', as its name suggests - only one bit of nonce leakage is necessary for private key recovery.

Just in case you didn't know:

That means if we're able to detect just one byte of nonce leakage over 4 signatures (for example), that would be more than sufficient. The example post we reference generated 30-40+ signatures (which is way more than enough).

As the post notes: "The...attack works even if nonce have just 1 biased bit, and using some ad-hoc lattices and parameters can work even when only a fraction of a nonce bit is a biased, i.e. is either 0 o;r 1 with probability > 50%."

Thus, if any signature generated by these validators has just ONE biased nonce, then we can successfully recover the private key.

Note: If you need an online resource for SageMath, then consider using CoCalc

Aggregating Signatures on Avalanche

First, we're going to go check out the documentation that Avalanche has on their validators.

You can find that here.

We're going to manipulate the many endpoints provided by Avalanche API to aggregate a number of signatures from a particular validator on the chain. For that, we're going to go check out avascan.

The total list of validators can be found here.

For convenience, let's go ahead and sort the validator list to show us validators in order by the total amount of $AVAX they have staked (in descending order; that means the validators with the most $AVAX will be listed at the top).

Let's see what that list pulls back for us on the block explorer.

From what we can see above, none of these validators (shown in the screenshot), are likely to be viable candidates because they don't have any delegates.

However, if we scroll further down the list, we'll find some ample candidates that are staking just under the 3 million $AVAX limit.

How much is that in USD value?

At the time of writing, the project boasts a $6 billion+ valuation, with each $AVAX token trading for $19.57 a piece at the time of writing.

Quick math tells us that 2.9 million of these tokens represent an approximate value of $50,468,975.15.

Among this list, we only need to choose one candidate. Let's opt for NodeID-D5yA7HbEr8AJ4yzwVZXsDtb4xhKkTRz73.

For the purposes of this theoretical example, we chose this vaildator because it has tons of transactions that can be scraped.

Moving forward, let's see if we can't aggregate more information about this validator.

We can see its beneficiary address is: P-avax1j3mllmr3a54pc9px37pc7fn4ekc9wuwuuf0lz3

If we visit the Avalanche subnet explorer, we can view more information about this particular validator.

From here, we're going to swap over to the X Chaint o glean more information about this asset. To expedite this search, I'm going to just take you straight to a TX of interest, which you can find here.

From this TX alone, we can find two different relevant signatures:

tiAQL+agsAV6EKPX7omdL41Ugzvzta9sLGsQREYPQYYR98wCviQwm2d7qipbgsQsdNqTLq716uyNfCtx3BwNswA=>
32otPdTjtKceXl3NKJCq89zRFY/36RfA9VGAmO9tnZJUEcBi7he3QeDfjXyaXH7ziv8ryFOO6UNuywNXPLKzfQE=>

Here's another TX of interest:

BXQU15VUZG5tW7PlHwpqzFcxTuwNegVeRohLFrUxrhVqEJSYlG1Nr9RgUsCCiltjvzkGBQbXKI77C5btYpEXPQA=>
PrXlD5Z3CP1ifBS3LctG5OvH6OC7EG7MaDdS3kPCCX5nodttkCveAzjCMmFx8HehxItTl/LW2PhH7TFtsKr5lgE=>

Again, another one.

AnxV6hF/aT8oqGwsHjzaIfqt3d+g1X+AHZI8nikLnDVCUo7FZzsTTPVxi/ZCW6j9jNvwrCgJ4S6bvA1dgA+/tAA=>

In total, the signatures we were able to briefly scrape here are

tiAQL+agsAV6EKPX7omdL41Ugzvzta9sLGsQREYPQYYR98wCviQwm2d7qipbgsQsdNqTLq716uyNfCtx3BwNswA=>
32otPdTjtKceXl3NKJCq89zRFY/36RfA9VGAmO9tnZJUEcBi7he3QeDfjXyaXH7ziv8ryFOO6UNuywNXPLKzfQE=>
BXQU15VUZG5tW7PlHwpqzFcxTuwNegVeRohLFrUxrhVqEJSYlG1Nr9RgUsCCiltjvzkGBQbXKI77C5btYpEXPQA=>
PrXlD5Z3CP1ifBS3LctG5OvH6OC7EG7MaDdS3kPCCX5nodttkCveAzjCMmFx8HehxItTl/LW2PhH7TFtsKr5lgE=>
AnxV6hF/aT8oqGwsHjzaIfqt3d+g1X+AHZI8nikLnDVCUo7FZzsTTPVxi/ZCW6j9jNvwrCgJ4S6bvA1dgA+/tAA=>

We've already gathered 5 addresses here, which should represent a reasonable start for any hacker/bad actor interested in experimenting with the LLL attack on the blockchain.

If there aren't enough signatures in this sample, then there are certainly other validators and accompanying transactions that can be extracted in order to sufficiently test the LLL attack. Taking the effort to scrape said transactions is outside of the scope of this report.

Conclusion

Not paying me a bug bounty is one issue. That makes Avalanche a bunch of assholes, sure. But not paying me and not fixing it? What the fuck is up w that? Since they refuse to address this problem, this should be considered a backdoor.

Non-Technical Explanation for How Curious This Issue is

It’s really hard to find valid code that employs secp256k1 in 2023 that doesn’t properly craft signatures.

For reference, the Bitcoin source code accounts for this properly. Ethereum’s source accounts for this properly (virtually all popular ETH repos used for crafting signatures do; goethereum, eth-sign, foundry, etc.).

The library that Avalanche’s Go code pulls from (Decred), includes the necessary functions to deploy this properly. The Avalanche team could’ve literally copy/pasted their code to fix this.

What’s astounding is they’ve included everything necessary for sig generation EXCEPT for the proper nonce generation. They don’t have the BLS signatures properly deployed (debugged those files, they run back several errors).

This is Not an “Edge Case” Niche Issue

This idea of recovering private keys may seem complex to some, which can lead to the mentality that what I'm describing here is some rare, edge case never-would-happen-in-real-life type of vulnerability (not to sound condescending; this is high-level math at the end of the day).

But that could not be further from the truth.

This attack vector that Avalanche has left open has been known for years and there is EXTENSIVE literature, research, etc. that documents the catastrophic impact of improper signature generation.

Some Examples of Past Compromises and Exploits

Remember when Sony got hacked back in 2010 and basically all their user data, games etc got leaked + the master key they were using? Yeah, that was this flaw: https://www.bbc.co.uk/news/technology-12116051.amp
You guys know “Trail of Bits”? They’re a huge auditor for smart contracts & crypto in this space. Well-respected, yadda yadda. They published an in-depth breakdown about this very issue in 2020 (well worth the read): https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/
An entire paper published in 2019 where researchers literally crack hundreds of Bitcoin, Ethereum & Ripple (latter is curious since they use ed25519 not secp256k1) wallets: https://eprint.iacr.org/2019/023.pdf
This person purposefully crafted two transactions on Ethereum that were signed using the same nonce. He wanted to see if any attackers would notice and take his funds. Within 24 hours, all the funds in the wallet were drained (this matches what researchers have found, which is that there are already people out there scanning the blockchain for improperly formed signatures so they can recover the private key & drain the wallet of funds) - https://bertcmiller.com/2021/12/28/glimpse_nonce_reuse.html
This is an in-depth guide illustrating how hundreds of Bitcoin private keys were trivially cracked on Bitcoin's blockchain using nothing but the signatures (this link includes hundreds of private keys & a list of transactions + tx data like opcodes & redeem scripts + a very detailed explanation of how these keys were recovered + the revelation that funds were already siphoned from these addresses) - https://strm.sh/studies/bitcoin-nonce-reuse-attack/

"You Have to be Some Sort of Expert Programmer or Coding Genius to Exploit This Then, Right?"

No!

In addition to (or in conjunction) with the resources published above, there are also the following code repos and guides for recovering private keys in this manner.

Simple python script for recovering private keys from signatures that reuse the same nonce - https://github.com/bytemare/ecdsa-keyrec
Another repo with a simple python script showing you how (just input the values & run it!) - https://github.com/Marsh61/ECDSA-Nonce-Reuse-Exploit-Example/blob/master/Attack-Main.py
Another great simple repo (this user has some awesome solidity-based repos) - https://github.com/tintinweb/ecdsa-private-key-recovery
For recovering Bitcoin private keys specifically - https://github.com/daedalus/bitcoin-recover-privkey
Recovering ethereum private keys when nonce is generated by concatenating private key + hash(message) [this is what avalanche does] = https://github.com/jonasnick/ecdsaPredictableNonce
Cracking ECDSA with LLL attacks - https://github.com/daedalus/BreakingECDSAwithLLL
That trailofbits article has example code - https://blog.trailofbits.com/2020/06/11/ecdsa-handle-with-care/

Final Word

Let Avalanche forever exist as a case study in sheer stupidity, arrogance and apathy. Sincere apologies to anyone that sunk their money into this scam.

Librechain