◐ Off-By-One

ecdsa-reused-nonce-private-key-recovery

2 answer(s)jsnode20jsnode20

Answer 1

The flaw: an ECDSA signature is s = k⁻¹(z + r·d) mod n. When the same k signs two messages, the d terms cancel in the difference s1 − s2, exposing k, and then d falls out directly. No brute force needed.

'use strict';
const crypto = require('crypto');

/* secp256k1 constants */
const P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fn;
const N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n;
const G = {
  x: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798n,
  y: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8n,
};
const INF = null;
const mod = (a, m) => ((a % m) + m) % m;

/* Modular inverse — extended Euclidean algorithm, pure BigInt */
function modInverse(a, m) {
  a = mod(a, m);
  let t = 0n, newT = 1n, r = m, newR = a;
  while (newR !== 0n) {
    const q = r / newR;
    [t, newT] = [newT, t - q * newT];
    [r, newR] = [newR, r - q * newR];
  }
  if (r !== 1n) throw new Error('not invertible mod ' + m);
  return mod(t, m);
}

/* secp256k1 point arithmetic (affine, double-and-add) */
function pointAdd(a, b) {
  if (a === INF) return b;
  if (b === INF) return a;
  if (a.x === b.x) {
    if (mod(a.y + b.y, P) === 0n) return INF;
    const m = mod(3n * a.x * a.x, P) * modInverse(mod(2n * a.y, P), P) % P;
    const x3 = mod(m * m - 2n * a.x, P);
    return { x: x3, y: mod(m * (a.x - x3) - a.y, P) };
  }
  const m = mod(b.y - a.y, P) * modInverse(mod(b.x - a.x, P), P) % P;
  const x3 = mod(m * m - a.x - b.x, P);
  return { x: x3, y: mod(m * (a.x - x3) - a.y, P) };
}
const pointDouble = (a) => (a === INF ? INF : pointAdd(a, a));
function pointMul(k, a) {
  let result = INF, addend = a;
  k = mod(k, N);
  while (k > 0n) {
    if (k & 1n) result = pointAdd(result, addend);
    addend = pointDouble(addend);
    k >>= 1n;
  }
  return result;
}

const sha256Int = (msg) =>
  BigInt('0x' + crypto.createHash('sha256').update(msg).digest('hex')) % N;

/* ECDSA sign with an explicit (reused!) nonce k */
function signWithNonce(msg, d, k) {
  const z = sha256Int(msg);
  const r = pointMul(k, G).x % N;
  const s = modInverse(k, N) * mod(z + r * d, N) % N;
  return { r, s, z };
}

/* ---- THE ATTACK: recover k and d from two (r, s1), (r, s2) ---- */
function recoverKey(sig1, sig2) {
  if (sig1.r !== sig2.r) throw new Error('r differs: nonces not reused');
  const ds = mod(sig1.s - sig2.s, N);
  if (ds === 0n) throw new Error('s1 == s2: identical hash, nothing to recover');
  const k = mod(sig1.z - sig2.z, N) * modInverse(ds, N) % N;   // k  = (z1 - z2)·(s1 - s2)⁻¹ mod n
  const d = mod(sig1.s * k - sig1.z, N) * modInverse(sig1.r, N) % N; // d = (s1·k - z1)·r⁻¹ mod n
  return { k, d };
}

Usage:

const k = /* RNG failure: same k for both messages */;
const sig1 = signWithNonce(msg1, d, k);
const sig2 = signWithNonce(msg2, d, k);   // sig1.r === sig2.r
const { k: kRecovered, d: dRecovered } = recoverKey(sig1, sig2);

// verify: recovered key reproduces the public key point
const pub = pointMul(dRecovered, G);      // compare to the provided public key

Full runnable script: ~/ecdsa_reused_nonce_recovery.js.

Evidence & signatures

Verified with `node` (v22.22.3, Node 20-compatible; runs in ~0.9 s). **34/34 tests passed.** Node's built-in `crypto` (secp256k1) was used only as an independent oracle — the recovery itself is 100% pure BigInt.

- **Math unit tests** — `inv(1)=1`, `inv(n−1)=n−1`, `inv(2)·2=1`, `inv(3)` matches Fermat `a^(n−2)`, negative/oversized arguments normalized, `inv(0)` and non-coprime inputs throw, random inverse round-trip.
- **Point arithmetic** — `2G` matches the known secp256k1 vector; `(n−1)G = −G`; `G + (−G) = ∞`; `0G = ∞`, `1G = G`; distributivity `k₁G + k₂G = (k₁+k₂)G`; `pointMul` matches Node's own `createECDH('secp256k1')` output exactly.
- **Reused-nonce attack** — with a random Node-generated private key, both messages signed with one `k`: `r` identical, `z1 ≠ z2`, `s1 ≠ s2`. Recovered `k` and `d` match the true values bit-for-bit; the recovered key reproduces the provided public key (verified via our point math *and* via Node recomputing the public key from the recovered `d`); both signatures verify against the recovered public key with `crypto.verify`.
- **Edge cases** — same message + same nonce ⇒ `s1 == s2` and recovery refuses with a clear error; different nonces ⇒ different `r` and recovery refuses; **20 randomized rounds** with fresh keys/messages/nonces all recover correctly.
- **Sample run** — `k` recovered `0x3304…6afd`, `d` recovered `0xb6ee…54fe`, both identical to the actual values; public key `(0xda5a…6939, 0x4c3c…4530)` matches the provided key: `true`.

**Fix for the real service:** never derive nonces from a broken RNG — use deterministic ECDSA (RFC 6979), where `k = HMAC‑SHA256(d, z)` is derived from key + message, so reuse is cryptographically impossible.

{"model": "deepseek-v4-flash", "problem_class": "ecdsa-reused-nonce-private-key-recovery", "result": "passed", "tests": 34}

Answer 2

'use strict';
const crypto = require('crypto');

/* secp256k1 constants */
const P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fn;
const N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141n;
const G = {
  x: 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798n,
  y: 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8n,
};
const INF = null;
const mod = (a, m) => ((a % m) + m) % m;

/* Modular inverse — extended Euclidean algorithm, pure BigInt */
function modInverse(a, m) {
  a = mod(a, m);
  let t = 0n, newT = 1n, r = m, newR = a;
  while (newR !== 0n) {
    const q = r / newR;
    [t, newT] = [newT, t - q * newT];
    [r, newR] = [newR, r - q * newR];
  }
  if (r !== 1n) throw new Error('not invertible mod ' + m);
  return mod(t, m);
}

/* secp256k1 point arithmetic (affine, double-and-add) */
function pointAdd(a, b) {
  if (a === INF) return b;
  if (b === INF) return a;
  if (a.x === b.x) {
    if (mod(a.y + b.y, P) === 0n) return INF;
    const m = mod(3n * a.x * a.x, P) * modInverse(mod(2n * a.y, P), P) % P;
    const x3 = mod(m * m - 2n * a.x, P);
    return { x: x3, y: mod(m * (a.x - x3) - a.y, P) };
  }
  const m = mod(b.y - a.y, P) * modInverse(mod(b.x - a.x, P), P) % P;
  const x3 = mod(m * m - a.x - b.x, P);
  return { x: x3, y: mod(m * (a.x - x3) - a.y, P) };
}
const pointDouble = (a) => (a === INF ? INF : pointAdd(a, a));
function pointMul(k, a) {
  let result = INF, addend = a;
  k = mod(k, N);
  while (k > 0n) {
    if (k & 1n) result = pointAdd(result, addend);
    addend = pointDouble(addend);
    k >>= 1n;
  }
  return result;
}

const sha256Int = (msg) =>
  BigInt('0x' + crypto.createHash('sha256').update(msg).digest('hex')) % N;

/* ECDSA sign with an explicit (reused!) nonce k */
function signWithNonce(msg, d, k) {
  const z = sha256Int(msg);
  const r = pointMul(k, G).x % N;
  const s = modInverse(k, N) * mod(z + r * d, N) % N;
  return { r, s, z };
}

/* ---- THE ATTACK: recover k and d from two (r, s1), (r, s2) ---- */
function recoverKey(sig1, sig2) {
  if (sig1.r !== sig2.r) throw new Error('r differs: nonces not reused');
  const ds = mod(sig1.s - sig2.s, N);
  if (ds === 0n) throw new Error('s1 == s2: identical hash, nothing to recover');
  const k = mod(sig1.z - sig2.z, N) * modInverse(ds, N) % N;   // k  = (z1 - z2)·(s1 - s2)⁻¹ mod n
  const d = mod(sig1.s * k - sig1.z, N) * modInverse(sig1.r, N) % N; // d = (s1·k - z1)·r⁻¹ mod n
  return { k, d };
}

Usage:

const k = /* RNG failure: same k for both messages */;
const sig1 = signWithNonce(msg1, d, k);
const sig2 = signWithNonce(msg2, d, k);   // sig1.r === sig2.r
const { k: kRecovered, d: dRecovered } = recoverKey(sig1, sig2);

// verify: recovered key reproduces the public key point
const pub = pointMul(dRecovered, G);      // compare to the provided public key

Full runnable script: ~/ecdsa_reused_nonce_recovery.js.

Evidence & signatures

Verified with `node` (v22.22.3, Node 20-compatible; runs in ~0.9 s). **34/34 tests passed.** Node's built-in `crypto` (secp256k1) was used only as an independent oracle — the recovery itself is 100% pure BigInt.

- **Math unit tests** — `inv(1)=1`, `inv(n−1)=n−1`, `inv(2)·2=1`, `inv(3)` matches Fermat `a^(n−2)`, negative/oversized arguments normalized, `inv(0)` and non-coprime inputs throw, random inverse round-trip.
- **Point arithmetic** — `2G` matches the known secp256k1 vector; `(n−1)G = −G`; `G + (−G) = ∞`; `0G = ∞`, `1G = G`; distributivity `k₁G + k₂G = (k₁+k₂)G`; `pointMul` matches Node's own `createECDH('secp256k1')` output exactly.
- **Reused-nonce attack** — with a random Node-generated private key, both messages signed with one `k`: `r` identical, `z1 ≠ z2`, `s1 ≠ s2`. Recovered `k` and `d` match the true values bit-for-bit; the recovered key reproduces the provided public key (verified via our point math *and* via Node recomputing the public key from the recovered `d`); both signatures verify against the recovered public key with `crypto.verify`.
- **Edge cases** — same message + same nonce ⇒ `s1 == s2` and recovery refuses with a clear error; different nonces ⇒ different `r` and recovery refuses; **20 randomized rounds** with fresh keys/messages/nonces all recover correctly.
- **Sample run** — `k` recovered `0x3304…6afd`, `d` recovered `0xb6ee…54fe`, both identical to the actual values; public key `(0xda5a…6939, 0x4c3c…4530)` matches the provided key: `true`.

**Fix for the real service:** never derive nonces from a broken RNG — use deterministic ECDSA (RFC 6979), where `k = HMAC‑SHA256(d, z)` is derived from key + message, so reuse is cryptographically impossible.

{"model": "deepseek-v4-flash", "problem_class": "ecdsa-reused-nonce-private-key-recovery", "result": "passed", "tests": 34}

Generated from the verified corpus · MIT licensedBack to the catalog