jsrsasign_on_negative_exponent.md

jsrsasign: BigInteger.modPow Silent Wrong Result on Negative Exponent

Vulnerability Summary

Field	Value
Package	jsrsasign (npm)
Affected Versions	All versions ≤ 11.1.0 (all versions shipping Tom Wu's jsbn.js)
Affected Functionality	BigInteger.modPow() with a negative exponent
CWE	CWE-682 (Incorrect Calculation)
Suggested CVSS	6.5 Medium — CVSS:3.1/AV:N/AC:H/PR:N/UI:N/S:U/C:N/I:L/A:H
Impact	Silent production of mathematically incorrect results; cryptographic signature DoS

---

1. Root Cause

BigInteger.prototype.modPow (jsbn.js, bnModPow) bit-scans the exponent's internal two's-complement representation without first checking the sign:

// jsbn.js — bnModPow (simplified)
BigInteger.prototype.modPow = function(e, m) {
  var i = e.bitLength();   // ← reads raw bit length of two's complement
  // ...
  if (i == 0) return BigInteger.ONE;   // hit when exp = -1
  // ...
  // otherwise scans two's-complement digits of negative e → wrong large exponent
};

Two failure modes result:

Mode A — exp = -1: bitLength() returns 0 for -1 in two's-complement. The early-return guard fires immediately, returning 1 (i.e. a^0 mod m) for every base and modulus.

Mode B — exp = -k (k > 1): The function scans the two's-complement digit pattern of the negative number, computing a^(wrong_large_positive) mod m — a numerically plausible but mathematically wrong result.

In both cases:

• No exception is thrown.
• No warning is emitted.
• The return value is a valid BigInteger in the expected numeric range.

Comparison with Java

Java's BigInteger.modPow throws ArithmeticException for negative exponents. A correct implementation must either compute the modular inverse power or throw — silently returning a wrong value is the worst possible behavior for a cryptographic library.

---

2. Security Impact

2.1 Affected Scenario: Code Ported from Python or Other Languages

Python 3.8+ introduced pow(base, -1, mod) as a built-in way to compute modular inverses. Developers who port such code to JavaScript and write:

// Translated from Python: pow(k, -1, q)
const k_inv = k.modPow(new BigInteger('-1', 10), q);

will silently get 1 instead of the correct modular inverse (Mode A). In jsrsasign's own API, modInverse() is the established idiom, so this pattern is most likely to appear in code migrated from Python or other languages — it is not a common pattern among native jsrsasign users.

2.2 Consequence: Silent Signature DoS

When the wrong k_inv is used in a DSA-style signing flow:

s = k_inv * (hash + priv * r) mod q

the resulting signature component s is:

• Structurally valid: 0 < s < q passes all range checks.
• Mathematically incorrect: Every downstream verifier rejects the signature.
• Silent: No exception or log message is produced at signing time.

The result is a Denial of Service — a system that signs successfully but whose signatures are universally rejected by verifiers. Key material is not disclosed.

jsrsasign's own DSA.signWithMessageHash() uses modInverse() internally and is not affected by this bug.

---

3. Affected Code Path

Any direct call to BigInteger.prototype.modPow(e, m) where e is negative. This does not affect jsrsasign's built-in signing functions.

Pattern	Intent	Wrong Result (Mode)
a.modPow(-1, p)	Modular inverse	Returns 1 always (A)
a.modPow(-2, p)	(a²)⁻¹ mod p	Returns a^(wrong) mod p (B)
a.modPow(-k, p)	(aᵏ)⁻¹ mod p	Returns a^(wrong) mod p (B)

---

4. Proof of Concept

4.1 Baseline: Incorrect Results Across Multiple Cases

'use strict';
const { BigInteger } = require('jsrsasign');

const tests = [
  // exp = -1  → bitLength() = 0 → always returns 1
  { a: '2',  exp: '-1',  p: '5'  },
  { a: '3',  exp: '-1',  p: '7'  },
  { a: '7',  exp: '-1',  p: '19' },
  // exp = -k  → scans two's-complement bits → wrong large exponent
  { a: '5',  exp: '-2',  p: '23' },
  { a: '3',  exp: '-3',  p: '23' },
  { a: '2',  exp: '-10', p: '31' },
];

for (const t of tests) {
  const a = new BigInteger(t.a, 10);
  const e = new BigInteger(t.exp, 10);
  const p = new BigInteger(t.p, 10);

  // Correct: (a^(-1))^|e| mod p
  const correct = a.modInverse(p).modPow(e.negate(), p).toString(10);
  const got = a.modPow(e, p).toString(10);

  console.log(
    `${t.a}^(${t.exp}) mod ${t.p}:  correct=${correct}  got=${got}`,
    correct !== got ? ' *** WRONG ***' : ' OK'
  );
}

Output (jsrsasign v11.1.0, Node v18.19.1):

2^(-1) mod 5:    correct=3   got=1   *** WRONG ***
3^(-1) mod 7:    correct=5   got=1   *** WRONG ***
7^(-1) mod 19:   correct=11  got=1   *** WRONG ***
5^(-2) mod 23:   correct=12  got=6   *** WRONG ***
3^(-3) mod 23:   correct=6   got=16  *** WRONG ***
2^(-10) mod 31:  correct=1   got=16  *** WRONG ***

[Part 1] mismatches: 6/6

Mode A (exp = -1): bitLength() returns 0 for −1 in jsbn's two's-complement representation, triggering the early-return of BigInteger.ONE unconditionally — got=1 regardless of base or modulus.

Mode B (exp = -k): the function scans the two's-complement bit pattern of the negative exponent as if it were a large positive number, yielding a wrong but plausible result (got=6, got=16) with no exception raised.

4.2 Impact: DSA-Style Signing with Wrong k_inv

'use strict';
const { BigInteger } = require('jsrsasign');

const q    = new BigInteger('251', 10);   // subgroup order
const priv = new BigInteger('47', 10);    // private key
const k    = new BigInteger('123', 10);   // nonce
const hash = new BigInteger('200', 10);   // message hash
const r    = new BigInteger('173', 10);   // g^k mod p mod q

// Correct: extended GCD
const k_inv_ok  = k.modInverse(q);
const inner     = hash.add(priv.multiply(r)).mod(q);
const s_ok      = k_inv_ok.multiply(inner).mod(q);

// Buggy: negative exponent shorthand (e.g. ported from Python pow(k, -1, q))
const k_inv_bug = k.modPow(new BigInteger('-1', 10), q);  // silently returns 1
const s_bug     = k_inv_bug.multiply(inner).mod(q);

console.log('k_inv (correct)   =', k_inv_ok.toString(10));
console.log('k_inv (modPow -1) =', k_inv_bug.toString(10));  // prints: 1
console.log('s (correct)       =', s_ok.toString(10));
console.log('s (buggy)         =', s_bug.toString(10));
console.log('s_bug in (0, q)?  =', s_bug.compareTo(BigInteger.ZERO) > 0 &&
                                    s_bug.compareTo(q) < 0);

Output:

k_inv (correct)   = 100
k_inv (modPow -1) = 1        ← Mode A: always returns 1
s (correct)       = 31
s (buggy)         = 48
s_bug in (0, q)?  = true     ← structurally valid, mathematically wrong → verifier rejects

No exception or warning is raised at signing time.

---

5. Workaround

Use BigInteger.prototype.modInverse instead of modPow with a negative exponent.

// ✗ Do not use — silently returns wrong result
const k_inv = k.modPow(new BigInteger('-1', 10), q);

// ✓ Correct
const k_inv = k.modInverse(q);

// ✓ Correct: (a^k)^(-1) mod p
const result = a.modPow(k, p).modInverse(p);

Sanity check: k.multiply(k.modInverse(q)).mod(q).toString() must equal '1'.

---

6. Suggested Fix

In bnModPow (jsbn.js), add a sign check at the entry of the function:

BigInteger.prototype.modPow = function(e, m) {
  if (e.signum() < 0) {
    // Compute (base^|e|)^(-1) mod m — mathematically correct behavior;
    // note Java BigInteger.modPow throws ArithmeticException for negative exponents
    return this.modPow(e.negate(), m).modInverse(m);
  }
  // ... existing implementation unchanged
};

This matches the semantics of Java's BigInteger.modPow for negative exponents and is backward-compatible for all non-negative exponents.

---

7. Affected Versions

• Affected: All jsrsasign versions ≤ 11.1.0 — the entire version history ships Tom Wu's jsbn.js without modification to bnModPow
• Not affected: jsrsasign's own DSA.signWithMessageHash() and ECDSA signing, which use modInverse() internally
• Latest affected: jsrsasign 11.1.0 (February 2024)
• As of the report date, no fix has been released and no new version has been published in over 12 months

---

8. References

• Tom Wu, jsbn.js — http://www-cs-students.stanford.edu/~tjw/jsbn/
• Java SE BigInteger.modPow — throws ArithmeticException for negative exponents
• Python 3.8 pow(base, -1, mod) — correctly computes modular inverse via extended GCD
• CWE-682: Incorrect Calculation — https://cwe.mitre.org/data/definitions/682.html