Critical vulnerability in elliptic – weakness in elliptic curve cryptograph

[vkb-stack]

Hi Team,

I’d like to report a critical vulnerability related to the current elliptic packages. The issue is tied to a weakness in the elliptic curve cryptography implementation, which could potentially expose applications using this library to security risks.

Package: elliptic

Severity: Critical

Impact: Potential compromise of cryptographic strength

Details:CVE-2024-31497: PuTTY

Could you please investigate this and advise if there’s a fix or a recommended mitigation?

[soatok]

I'm curious if CVE-2024-31497 applies. Let's walk through the code:

elliptic/lib/elliptic/curves.js

Lines 109 to 134 in 9b77436

	defineCurve('p521', {
	type: 'short',
	prime: null,
	p: '000001ff ffffffff ffffffff ffffffff ffffffff ffffffff ' +
	'ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ' +
	'ffffffff ffffffff ffffffff ffffffff ffffffff',
	a: '000001ff ffffffff ffffffff ffffffff ffffffff ffffffff ' +
	'ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff ' +
	'ffffffff ffffffff ffffffff ffffffff fffffffc',
	b: '00000051 953eb961 8e1c9a1f 929a21a0 b68540ee a2da725b ' +
	'99b315f3 b8b48991 8ef109e1 56193951 ec7e937b 1652c0bd ' +
	'3bb1bf07 3573df88 3d2c34f1 ef451fd4 6b503f00',
	n: '000001ff ffffffff ffffffff ffffffff ffffffff ffffffff ' +
	'ffffffff ffffffff fffffffa 51868783 bf2f966b 7fcc0148 ' +
	'f709a5d0 3bb5c9b8 899c47ae bb6fb71e 91386409',
	hash: hash.sha512,
	gRed: false,
	g: [
	'000000c6 858e06b7 0404e9cd 9e3ecb66 2395b442 9c648139 ' +
	'053fb521 f828af60 6b4d3dba a14b5e77 efe75928 fe1dc127 ' +
	'a2ffa8de 3348b3c1 856a429b f97e7e31 c2e5bd66',
	'00000118 39296a78 9a3bc004 5c8a5fb4 2c7d1bd9 98f54449 ' +
	'579b4468 17afbd17 273e662c 97ee7299 5ef42640 c550b901 ' +
	'3fad0761 353c7086 a272c240 88be9476 9fd16650',
	],
	});

So we see that their P-521 code is using a generic curve construction, rather than special-purpose code. Not a good start.

The entire ECDSA signature function is defined here:

elliptic/lib/elliptic/ec/index.js

Lines 110 to 186 in 9b77436

	EC.prototype.sign = function sign(msg, key, enc, options) {
	if (typeof enc === 'object') {
	options = enc;
	enc = null;
	}
	if (!options)
	options = {};
	if (typeof msg !== 'string' && typeof msg !== 'number' && !BN.isBN(msg)) {
	assert(typeof msg === 'object' && msg && typeof msg.length === 'number',
	'Expected message to be an array-like, a hex string, or a BN instance');
	assert((msg.length >>> 0) === msg.length); // non-negative 32-bit integer
	for (var i = 0; i < msg.length; i++) assert((msg[i] & 255) === msg[i]);
	}
	key = this.keyFromPrivate(key, enc);
	msg = this._truncateToN(msg, false, options.msgBitLength);
	// Would fail further checks, but let's make the error message clear
	assert(!msg.isNeg(), 'Can not sign a negative message');
	// Zero-extend key to provide enough entropy
	var bytes = this.n.byteLength();
	var bkey = key.getPrivate().toArray('be', bytes);
	// Zero-extend nonce to have the same byte size as N
	var nonce = msg.toArray('be', bytes);
	// Recheck nonce to be bijective to msg
	assert((new BN(nonce)).eq(msg), 'Can not sign message');
	// Instantiate Hmac_DRBG
	var drbg = new HmacDRBG({
	hash: this.hash,
	entropy: bkey,
	nonce: nonce,
	pers: options.pers,
	persEnc: options.persEnc || 'utf8',
	});
	// Number of bytes to generate
	var ns1 = this.n.sub(new BN(1));
	for (var iter = 0; ; iter++) {
	var k = options.k ?
	options.k(iter) :
	new BN(drbg.generate(this.n.byteLength()));
	k = this._truncateToN(k, true);
	if (k.cmpn(1) <= 0 || k.cmp(ns1) >= 0)
	continue;
	var kp = this.g.mul(k);
	if (kp.isInfinity())
	continue;
	var kpX = kp.getX();
	var r = kpX.umod(this.n);
	if (r.cmpn(0) === 0)
	continue;
	var s = k.invm(this.n).mul(r.mul(key.getPrivate()).iadd(msg));
	s = s.umod(this.n);
	if (s.cmpn(0) === 0)
	continue;
	var recoveryParam = (kp.getY().isOdd() ? 1 : 0) |
	(kpX.cmp(r) !== 0 ? 2 : 0);
	// Use complement of `s`, if it is > `n / 2`
	if (options.canonical && s.cmp(this.nh) > 0) {
	s = this.n.sub(s);
	recoveryParam ^= 1;
	}
	return new Signature({ r: r, s: s, recoveryParam: recoveryParam });
	}
	};

The important bit is:

elliptic/lib/elliptic/ec/index.js

Lines 141 to 151 in 9b77436

	// Instantiate Hmac_DRBG
	var drbg = new HmacDRBG({
	hash: this.hash,
	entropy: bkey,
	nonce: nonce,
	pers: options.pers,
	persEnc: options.persEnc || 'utf8',
	});
	// Number of bytes to generate
	var ns1 = this.n.sub(new BN(1));

PuTTy's deterministic nonces were a specific pre-RFC6979 algorithm specific to PuTTy. This is using indutny's hmac-drbg package. so even if it is vulnerable, it's not exactly CVE-2024-31497.

According to this, it's generating n bits from the DRBG:

elliptic/lib/elliptic/ec/index.js

Line 156 in 9b77436

new BN(drbg.generate(this.n.byteLength()));

Based on what the hmac-drbg code appears to do, I believe this will fill up all 521 bits rather than leaving the top 9 zeroed out.

Thus, I think this is a false positive?

[soatok]

Follow-up: That code should probably use rejection sampling per RFC 6979. See #328 for related issues with not reducing modulo the group order.

[lkmorlan]

I think this is a duplicate of #344.