[SECURITY] Timing leaks in lib/native/bn.js

[soatok]

• Branching timing leaks

  • bcrypto/lib/native/bn.js

    Line 3556 in b73dbc6

    return x < 0n ? -x : x;

  • bcrypto/lib/native/bn.js

    Line 3435 in b73dbc6

    return neg ? -num : num;

• powm leaks the value of e

  • bcrypto/lib/native/bn.js

    Lines 3869 to 3897 in b73dbc6

    	function powm(x, e, m) {
    	assert(m > 0n);
    	if (e < 0n) {
    	x = invert(x, m);
    	e = -e;
    	} else {
    	x = mod(x, m);
    	}
    	if (e <= U32_MAX)
    	return rtl(x, e, m);
    	return slide(x, e, m);
    	}
    	function rtl(x, e, m) {
    	let r = 1n;
    	while (e > 0n) {
    	if ((e & 1n) === 1n)
    	r = (r * x) % m;
    	x = (x * x) % m;
    	e >>= 1n;
    	}
    	return r;
    	}

  • bcrypto/lib/native/bn.js

    Lines 3889 to 3893 in b73dbc6

    	if ((e & 1n) === 1n)
    	r = (r * x) % m;
    	x = (x * x) % m;
    	e >>= 1n;

  • (This also breaks any modular inversion that relies on fermat())

I wrote a library that implements constant-time algorithms in TypeScript if you want to mitigate these risks.

Further reading: [1] [2]

[soatok]

Addendum:

bcrypto/lib/js/ecdsa.js

Lines 471 to 472 in 4db0fee

	const b = this.curve.randomScalar(rng);
	const ki = k.mul(b).fermat(n);

Leaking the exponent leaks the value of k (because Fermat uses k-2 as e), which in turn leaks k.

Leaking the hidden number lets you recover secret keys through simple algebra.

EDIT: I'm tired so I keep missing tripping up on trying to describe the problem, but the solution is to harden against timing leaks.

[chjj]

The javascript backend is not designed for side-channel silence. Bcrypto used to have some attempts at this, but realistically there is no way to ensure the code generated by a JS JIT is constant-time. It's hard enough to do in C, but (in my opinion) impossible to do in JS. There are a number of reasons for this:

1. Javascript is a dynamic enough language that the compiler may insert branches in unexpected and unseen locations (this even happens in C for code that is written as constant-time, but there are more effective mitigations for it).
2. To add insult to injury, every JS engine is a JIT nowdays: the compiler may optimize and de-optimize code at it pleases. Not only can this affect timing in unforeseen ways, but it makes the generated code harder to verify. Your code may or may not have branches before or after it's optimized... a now-you-see-it, now-you-don't type of situation.
3. Different JS engines can wildly differ in their design and execution, making it impossible to make guarantees about such execution.
4. There's a number of other factors as well (stop-the-world garbage collection, compiler bounds checks, etc).
5. Claiming JS code is side-channel resistant gives users a false impression of security for the above reasons.

To make my point further:

return x < 0n ? -x : x; 

How do you know that is a branch? Perhaps it's a branch initially, but perhaps it gets transformed into a cmov instruction once the optimizer kicks in. This function will no doubt be inlined due to its size and such an optimization could happen at various locations in the code if the compiler determines that the branch is sufficiently unpredictable.

I do not believe your code can mitigate these risks (nor can my own). Personally, I think it is irresponsible to make guarantees about javascript code being side-channel resistant. The effective only mitigation I see for JS crypto implementations is blinding factors, which bcrypto does make use of (for signing).

If you want side-channel silence, you should only use the native backend, which is constant-time for any function that handles secret data. This task is accomplished by libtorsion. See the ctgrind tests.

In the future, we can look into compiling libtorsion to WASM, though it still remains to be seen whether the executed code would actually be side-channel resistant.

edit: Fixed some links and typos.

[chjj]

Leaking the exponent leaks the value of k (because Fermat uses k-2 as e), which in turn leaks k.

It's not really relevant given my last post, but just pointing out that this is incorrect as well. It uses k as the base, not the exponent.

k.mul(b).fermat(n); 

That line would be computed as (k*b)^(n-2) mod n. In other words, the exponent is constant and non-secret.

The blinding factor is there to hopefully mask any future operations as well.