DSA Nonce Generation Enables Private Key Recovery.md

jsrsasign – DSA Nonce Generation Bias via Incorrect compareTo Handling in Rejection Sampling

Summary

Field	Value
Package	jsrsasign (npm)
Affected versions	>= 7.0.0 (crypto-1.1.js random helper introduced)
Fixed version	Not yet released (patch proposed in this report)
Affected component	DSA signing path only (dsa-2.0.js, crypto-1.1.js)
Impact class	Non-uniform DSA nonce distribution (bias), enabling potential private key recovery
Primary CWE	CWE-697 (Incorrect Comparison)
Secondary CWE	CWE-330 (Use of Insufficiently Random Values)
CVSS 3.1 Score	7.4 High – CVSS:3.1/AV:N/AC:H/PR:N/UI:N/S:U/C:H/I:H/A:N

---

1. Root Cause

1.1 Incorrect Comparison in Rejection Sampling

crypto-1.1.js lines 390–395:

KJUR.crypto.Util.getRandomBigIntegerZeroToMax = function(biMax) {
    var bitLenMax = biMax.bitLength();
    while (1) {
        var biRand = KJUR.crypto.Util.getRandomBigIntegerOfNbits(bitLenMax);
        if (biMax.compareTo(biRand) != -1) return biRand; // vulnerable
    }
};

The logic assumes compareTo() returns only -1, 0, or 1. However, the underlying jsbn implementation (jsbn.js lines 211–219) returns any signed integer:

// return + if this > a, - if this < a, 0 if equal
function bnCompareTo(a) {
  var r = this.s - a.s;
  if (r != 0) return r;
  var i = this.t;
  r = i - a.t;
  if (r != 0) return (this.s < 0) ? -r : r;
  while (--i >= 0) if ((r = this[i] - a[i]) != 0) return r;
  return 0;
}

When biRand > biMax, compareTo() returns a negative value other than -1 (e.g., -2, -3, etc.). The condition != -1 incorrectly accepts these out-of-range values, breaking the rejection-sampling invariant.

1.2 Secondary Issue: Non-Robust Min/Max Guard

crypto-1.1.js lines 416–419:

var flagCompare = biMin.compareTo(biMax);
if (flagCompare == 1) throw "biMin is greater than biMax";  // fragile
if (flagCompare == 0) return biMin;

Using == 1 fails silently when compareTo returns any positive integer greater than 1, meaning the biMin > biMax guard may not trigger in all cases.

---

2. Affected DSA Call Path

dsa-2.0.js lines 204–205:

var k = KJUR.crypto.Util.getRandomBigIntegerMinToMax(
    BigInteger.ONE.add(BigInteger.ONE), // min = 2
    h.subtract(BigInteger.ONE)          // max = q-1
);

Call chain:

dsa-2.0.js  signWithMessageHash()
  → crypto-1.1.js  getRandomBigIntegerMinToMax(2, q-1)
    → crypto-1.1.js  getRandomBigIntegerZeroToMax(q-3)  ← vulnerable

---

3. Scope

• Affected: DSA nonce generation (signWithMessageHash in dsa-2.0.js).
• Not affected: ECDSA signing (ecdsa-modified-1.0.js), which uses an independent getBigRandom helper (line 98, used at lines 243/260) and does not go through this code path.

---

4. Security Impact

DSA security fundamentally requires the per-signature nonce k to be uniformly and independently sampled from [1, q-1]. This bug causes rejection sampling to accept a measurable fraction of out-of-range candidates, producing a biased, non-uniform nonce distribution.

A biased nonce distribution is a well-known precondition for lattice-based / Hidden Number Problem (HNP) attacks on DSA, which can recover the private key given enough signatures.

Practical conditions for exploitation:

• Attacker can collect a sufficient number of DSA signatures and corresponding message hashes from the target.
• Bias magnitude and required sample size are parameter-dependent and must be assessed empirically; key recovery is not guaranteed in every deployment.
• The bias rate is measurable and reproducible (see Section 5).

---

5. Proof of Concept

5.1 Functional PoC – Out-of-Range Acceptance

The following demonstrates that a value greater than biMax is accepted by the vulnerable condition when compareTo returns a negative value other than -1:

const BigInteger = require('jsrsasign').BigInteger;

// Simulate: biMax = 100, biRand = 200
const biMax = new BigInteger("100");
const biRand = new BigInteger("200");

const cmp = biMax.compareTo(biRand); // biMax < biRand → returns negative
console.log("compareTo result:", cmp);          // e.g. -1, -2, etc.
console.log("Accepted (buggy):", cmp != -1);    // may be true → BUG
console.log("Accepted (fixed):", cmp >= 0);     // false → CORRECT

5.2 Statistical PoC – Real DSA Signing Path

Collection script run against a real DSA key:

node poc/jsrsasign_randmod_outofrange/poc_collect_jsrsasign_dataset.js \
  --pem /tmp/weak_dsa.pem --num 5000 --out /tmp/weak_dataset.json

Observed output:

model overflow prob : 0.119440
overflow rate       : 0.063200
empirical/model     : 0.529

Interpretation:

• A measurable fraction of generated nonces fall outside the valid range [2, q-1] before the loop terminates.
• The empirical rate being lower than the model upper-bound is expected: the buggy check still rejects candidates where compareTo returns exactly -1, so only a subset of out-of-range values leak through.
• The bias is real, reproducible, and non-negligible (~6% overflow rate observed).

---

6. Recommended Fix

Minimal two-line patch to crypto-1.1.js:

// BEFORE (vulnerable):
if (biMax.compareTo(biRand) != -1) return biRand;

if (flagCompare == 1) throw "biMin is greater than biMax";

// AFTER (fixed):
if (biMax.compareTo(biRand) >= 0) return biRand;

if (flagCompare > 0) throw "biMin is greater than biMax";

The fix replaces sentinel-value comparisons with sign-based comparisons (>= 0, > 0), which are correct regardless of the magnitude of the integer returned by compareTo.

---

6a. Full PoC Script – poc_collect_jsrsasign_dataset.js

Reproduction steps:

npm install jsrsasign
node poc_collect_jsrsasign_dataset.js --num 5000
# or against a real key:
node poc_collect_jsrsasign_dataset.js --pem /path/to/dsa_private.pem --num 5000 --out dataset.json

An embedded 1024-bit DSA test key is included so the script runs with no external dependencies.

'use strict';

global.navigator = { appName: 'Netscape' };
global.window = global;

const crypto = require('crypto');
const fs = require('fs');

const rs = require('jsrsasign');
global.KJUR = rs.KJUR || global.KJUR;
global.KEYUTIL = rs.KEYUTIL || global.KEYUTIL;
global.BigInteger = rs.BigInteger || global.BigInteger;

if (typeof global.KJUR === 'undefined' || typeof global.BigInteger === 'undefined') {
  throw new Error('failed to initialize jsrsasign globals');
}

const DEFAULT_DSA_PEM =
  '-----BEGIN DSA PRIVATE KEY-----\n' +
  'MIIBuwIBAAKBgQCe0yehJAfI0tyaa5NZ+8SPKjF1BPM7SGYcSwN3j1W4GK8hkoW7\n' +
  'zfpg9j+W9cPAZzjXJDKjb0bWSQoP5wI4UXZx56vbQwxP+3Shf7bQzs7uKP3bSSc7\n' +
  'zRZaUg5Klxe00n7wbzQX32qeoto1BY8RmudqyAlaLEXuV2w9/oJT80SaTwIVAIMh\n' +
  'JMMYgpj41t0a2EEhwu8zpdUrAoGAcRrEBTuvUCqgoJq8t69yiFSV4e+w3hKdk8e7\n' +
  'FvDkuAoaENBAntUrzQ3wtVEfbgj3RxVRfpQG7dRdePDvFdkrJ+85jqe/k2X6E1kT\n' +
  'IhSfqEY1GH2id/FcvIyaKEI/6yMyIeXRrTbZJtLh4Mdw803ASmFvVWhSIqmxz0+O\n' +
  'z4fBm34CgYEAjK/ZZUzlGBjhVGE70LFO6XT73/xaGYAsQwEwK8hU1eF9rw1nRaSq\n' +
  'qORv+WtXyJNx+nLMoSoiSIIWRdH/dYaaJUmtf9EQzu/qVhbQC+WUEDbhoth7vPC/\n' +
  'vmw7Hhi6DTs69tNLrPYTJwoLX2fHhmjkuls+wKoo52LqH58uAWfgUjsCFHOzU4Zg\n' +
  'zqyYo79I5T+ItOEkZXwh\n' +
  '-----END DSA PRIVATE KEY-----\n';

function usage() {
  console.log('Usage: node poc_collect_jsrsasign_dataset.js [--out FILE] [--num N] [--pem FILE] [--no-secret] [--quiet]');
}

function parseArgs(argv) {
  const out = {
    out: 'jsrsasign_dataset.json',
    num: 5000,
    pemPath: null,
    includeSecret: true,
    quiet: false
  };
  for (let i = 0; i < argv.length; i++) {
    const a = argv[i];
    if (a === '--out' && i + 1 < argv.length)    { out.out = argv[++i]; continue; }
    if (a === '--num' && i + 1 < argv.length)    { out.num = Number(argv[++i]); continue; }
    if (a === '--pem' && i + 1 < argv.length)    { out.pemPath = argv[++i]; continue; }
    if (a === '--no-secret')                      { out.includeSecret = false; continue; }
    if (a === '--quiet')                          { out.quiet = true; continue; }
    if (a === '--help' || a === '-h')             { usage(); process.exit(0); }
    throw new Error('unknown argument: ' + a);
  }
  if (!Number.isFinite(out.num) || out.num < 1) throw new Error('--num must be a positive integer');
  out.num = Math.floor(out.num);
  return out;
}

function messageHashToDSAInteger(msgHashHex, q) {
  const nibbleLen = Math.floor(q.bitLength() / 4);
  return new BigInteger(msgHashHex.substr(0, nibbleLen), 16);
}

function toDec(bi) { return bi.toString(10); }

function collectSignaturesWithTelemetry(signer, q, num, quiet) {
  const util = KJUR.crypto.Util;
  const orig = util.getRandomBigIntegerMinToMax;
  const expectedMin = BigInteger.ONE.add(BigInteger.ONE);
  const expectedMax = q.subtract(BigInteger.ONE);

  const out = [];
  let captured = 0, overflowCount = 0;

  util.getRandomBigIntegerMinToMax = function (biMin, biMax) {
    const k = orig.call(this, biMin, biMax);
    if (biMin.compareTo(expectedMin) === 0 && biMax.compareTo(expectedMax) === 0) captured = k;
    return k;
  };

  try {
    for (let i = 0; i < num; i++) {
      while (true) {
        captured = 0;
        const msg = 'collect-' + i + '-' + crypto.randomBytes(16).toString('hex');
        const hashHex = KJUR.crypto.Util.hashString(msg, 'sha1');
        const h = messageHashToDSAInteger(hashHex, q);

        const sigHex = signer.signWithMessageHash(hashHex);
        const rsPair = signer.parseASN1Signature(sigHex);
        const r = rsPair[0], s = rsPair[1];

        if (captured === 0) continue;
        if (r.signum() === 0 || s.signum() === 0) continue;

        const overflow = captured.compareTo(q) > 0;
        if (overflow) overflowCount++;
        out.push({ h: toDec(h), r: toDec(r), s: toDec(s), raw_k: toDec(captured), overflow });
        break;
      }
      if (!quiet && (i + 1) % 1000 === 0)
        console.log('[collect] signatures=' + (i + 1) + ' overflow=' + overflowCount);
    }
  } finally {
    util.getRandomBigIntegerMinToMax = orig;
  }
  return { signatures: out, overflowCount };
}

function main() {
  const args = parseArgs(process.argv.slice(2));
  const pem = args.pemPath ? fs.readFileSync(args.pemPath, 'utf8') : DEFAULT_DSA_PEM;

  const key = KEYUTIL.getKey(pem);
  if (!key || !key.q || !key.p || !key.g || !key.y || !key.x)
    throw new Error('failed to parse DSA private key');

  const qBits = key.q.bitLength();
  const n = 1n << BigInt(qBits);
  const q = BigInt(key.q.toString(10));
  const bnd = n + 1n - q;
  const modelOverflowProb = Number(bnd) / Number(n - 1n);

  const signer = new KJUR.crypto.DSA();
  signer.setPrivate(key.p, key.q, key.g, key.y, key.x);

  const result = collectSignaturesWithTelemetry(signer, key.q, args.num, args.quiet);

  const outObj = {
    meta: {
      source: 'jsrsasign',
      generated_at: new Date().toISOString(),
      resolved_module: require.resolve('jsrsasign'),
      compareto_note: 'BigInteger.compareTo returns signed difference; != -1 leads out-of-range acceptance',
      num_signatures: result.signatures.length
    },
    params: {
      p: toDec(key.p), q: toDec(key.q), g: toDec(key.g), y: toDec(key.y),
      q_bits: qBits, B: bnd.toString(), model_overflow_prob: modelOverflowProb
    },
    signatures: result.signatures
  };

  if (args.includeSecret) outObj.params.x = toDec(key.x);
  fs.writeFileSync(args.out, JSON.stringify(outObj, null, 2));

  if (!args.quiet) {
    const empirical = result.overflowCount / result.signatures.length;
    const ratio = modelOverflowProb > 0 ? empirical / modelOverflowProb : 0;
    console.log('=== jsrsasign randmod_outofrange dataset collector ===');
    console.log('out                  : ' + args.out);
    console.log('q bits               : ' + qBits);
    console.log('q                    : ' + key.q.toString(10));
    console.log('B (=2^bits+1-q)      : ' + bnd.toString());
    console.log('model overflow prob  : ' + modelOverflowProb.toFixed(6));
    console.log('signatures           : ' + result.signatures.length);
    console.log('true overflow count  : ' + result.overflowCount);
    console.log('overflow rate        : ' + empirical.toFixed(6));
    console.log('empirical/model      : ' + ratio.toFixed(3));
  }
}

main();

---

7. Recommended Regression Tests

1. Unit – getRandomBigIntegerZeroToMax: Mock the RNG to return biMax + c where compareTo would return a non--1 negative; assert the value is rejected.
2. Unit – getRandomBigIntegerMinToMax: Mock compareTo to return a positive integer greater than 1; assert the biMin > biMax guard triggers correctly.
3. Integration – DSA signing: Instrument the nonce generator, sample ≥ 1000 signatures, verify all nonces fall within [2, q-1] and that the distribution passes a basic uniformity check (e.g., chi-squared test).

---

8. Affected Version Details

Component	Introduced in	Status
crypto-1.1.js random helpers	~7.0.0 (crypto 1.1.11)	Vulnerable
dsa-2.0.js signing	~7.0.0	Vulnerable (consumer of buggy helper)
ecdsa-modified-1.0.js signing	–	Not affected (independent RNG path)

All npm releases of jsrsasign >= 7.0.0 that include dsa-2.0.js are considered affected until a patched release is available.