`PartiallyBlindRSA.generateKey()` does not enforce the requested RSA modulus length

[aleister1102]

PartiallyBlindRSA.generateKey() currently uses the custom safe-prime generation path for RSAPBSSA keys, but it does not enforce that the generated RSA modulus matches the caller's requested algorithm.modulusLength.

Source references

• RSAPBSSA exposes the partially blind key-generation entrypoint in src/index.ts:

  • blindrsa-ts/src/index.ts

    Lines 103 to 110 in db4ed09

    	// RSAPBSSA is used to access the variants of the protocol.
    	export const RSAPBSSA = {
    	SHA384: {
    	generateKey: (
    	algorithm: Pick<RsaHashedKeyGenParams, 'modulusLength' | 'publicExponent'>,
    	): Promise<CryptoKeyPair> =>
    	PartiallyBlindRSA.generateKey({ ...algorithm, hash: 'SHA-384' }),
    	PSS: {

• PartiallyBlindRSA.generateKey() derives p and q from generateSafePrime(algorithm.modulusLength >> 1), multiplies them into n, and imports the result without checking the bit length of p, q, or n:

  • blindrsa-ts/src/partially_blindrsa.ts

    Lines 288 to 335 in db4ed09

    	static async generateKey(
    	algorithm: Pick<RsaHashedKeyGenParams, 'modulusLength' | 'publicExponent' | 'hash'>,
    	generateSafePrimeSync: (length: number) => sjcl.BigNumber | bigint = generateSafePrime,
    	): Promise<CryptoKeyPair> {
    	prepare_sjcl_random_generator();
    	// 1. p = SafePrime(bits / 2)
    	// 2. q = SafePrime(bits / 2)
    	// 3. while p == q, go to step 2.
    	let p: sjcl.BigNumber;
    	let q: sjcl.BigNumber;
    	do {
    	const p_tmp = generateSafePrimeSync(algorithm.modulusLength >> 1);
    	const q_tmp = generateSafePrimeSync(algorithm.modulusLength >> 1);
    	p = typeof p_tmp === 'bigint' ? new sjcl.bn(p_tmp.toString(16)) : p_tmp;
    	q = typeof q_tmp === 'bigint' ? new sjcl.bn(q_tmp.toString(16)) : q_tmp;
    	} while (p.equals(q));
    	// 4. phi = (p - 1) * (q - 1)
    	const phi = p.sub(1).mul(q.sub(1));
    	// 5. e = publicExponent
    	const e = new sjcl.bn(
    	'0x' +
    	Array.from(algorithm.publicExponent)
    	.map((x) => x.toString(16).padStart(2, '0'))
    	.join(''),
    	);
    	// 6. d = inverse_mod(e, phi)
    	// TODO: replace this applying Chinese Remainder Theorem.
    	const d = inverseMod(e, phi);
    	// 7. n = p * q
    	const n = p.mul(q);
    	// 7. sk = (n, p, q, phi, d)
    	const sk: BigSecretKey = { n, p, q, d };
    	// 8. pk = (n, e)
    	const pk: BigPublicKey = { e, n };
    	// 9. output (sk, pk)
    	return PartiallyBlindRSA.bigKeyPairToCryptoKeyPair(
    	{
    	secretKey: sk,
    	publicKey: pk,
    	},
    	algorithm,
    	true,

• In src/prime.ts, generatePrime() builds its random upper bound by starting from 2 and doubling bitLength times:

  • blindrsa-ts/src/prime.ts

    Lines 68 to 73 in db4ed09

    	// 2^b
    	const twoToN = new sjcl.bn(2);
    	for (let i = 0; i < bitLength; i++) {
    	twoToN.doubleM();
    	}
    	twoToN.normalize();

• The same function samples with sjcl.bn.random(twoToN, ...) and only forces oddness, not exact width:

  • blindrsa-ts/src/prime.ts

    Lines 78 to 84 in db4ed09

    	do {
    	prime = sjcl.bn.random(twoToN, SJCL_PARANOIA);
    	if ((prime.getLimb(0) & 0x1) == 0) {
    	prime = prime.addM(1).normalize();
    	}
    	i++;
    	} while (!millerRabinTest(prime, NUM_TRIES_PRIMALITY) && i < MAX_NUM_TRIES);

• sjcl.bn.random() returns any value < modulus:

  • blindrsa-ts/src/sjcl/index.js

    Lines 2832 to 2853 in db4ed09

    	sjcl.bn.random = function(modulus, paranoia) {
    	if (typeof modulus !== "object") { modulus = new sjcl.bn(modulus); }
    	var words, i, l = modulus.limbs.length, m = modulus.limbs[l-1]+1, out = new sjcl.bn();
    	while (true) {
    	// get a sequence whose first digits make sense
    	do {
    	words = sjcl.random.randomWords(l, paranoia);
    	if (words[l-1] < 0) { words[l-1] += 0x100000000; }
    	} while (Math.floor(words[l-1] / m) === Math.floor(0x100000000 / m));
    	words[l-1] %= m;
    	// mask off all the limbs
    	for (i=0; i<l-1; i++) {
    	words[i] &= modulus.radixMask;
    	}
    	// check the rest of the digitssj
    	out.limbs = words;
    	if (!out.greaterEquals(modulus)) {
    	return out;
    	}
    	}

• generateSafePrime() converts that unchecked q into p = 2q + 1 and returns it without exact-width enforcement:

  • blindrsa-ts/src/prime.ts

    Lines 95 to 103 in db4ed09

    	export function generateSafePrime(bitLength: number, NUM_TRIES_PRIMALITY = 20): sjcl.BigNumber {
    	const MAX_NUM_TRIES = bitLength ** 2;
    	const ONE = new sjcl.bn(1);
    	let prime: sjcl.BigNumber;
    	let i = 0;
    	do {
    	const q = generatePrime(bitLength - 1, NUM_TRIES_PRIMALITY);
    	prime = q.doubleM().addM(ONE).normalize();

• For comparison, the non-partially-blind BlindRSA.generateKey() path delegates to WebCrypto and does not use this custom prime generator:

  • blindrsa-ts/src/blindrsa.ts

    Lines 238 to 245 in db4ed09

    	static generateKey(
    	algorithm: Pick<RsaHashedKeyGenParams, 'modulusLength' | 'publicExponent' | 'hash'>,
    	): Promise<CryptoKeyPair> {
    	return crypto.subtle.generateKey({ ...algorithm, name: BlindRSA.NAME }, true, [
    	'sign',
    	'verify',
    	]);
    	}

Issue

This means the partially blind key-generation path does not enforce the caller's requested modulus size.

• The lower bound is missing, so prime candidates can be shorter than the requested bit width.
• The upper bound is off by one bit, so prime candidates can also be longer than requested.

Those width errors propagate through generateSafePrime() into PartiallyBlindRSA.generateKey(), which imports whatever modulus was produced instead of retrying until it gets the exact requested size.

I am intentionally keeping the claim narrow here: this issue is a key-size contract violation in the RSAPBSSA key-generation path. It is not a claim that every returned key is practically breakable, but that callers request an exact minimum security parameter and the library can silently return a different one.

In local reproduction, RSAPBSSA.SHA384.PSS.Randomized().generateKey({ modulusLength: 512, ... }) returned keys with publicKey.algorithm.modulusLength 511 and 513 instead of 512.

Suggested fix

Sample prime candidates in [2^(b-1), 2^b), or otherwise force the top bit while keeping the value below 2^b, and retry key generation until p, q, and final n all have the exact requested widths before importing the key.