Cryptographic Side-Channels (Timing Leaks) in JSBN

[soatok]

Issue Summary

JSBN contains a lot of timing leaks that make it unsuitable for cryptographic use. However, JSBN is broadly used in JavaScript implementations of asymmetric cryptography.

Modular Exponentiation

JSBN's implementation of modular exponentiation can be found here. The critical loop of this implementation can be found here. For odd moduli larger than 255 (a.k.a. any cryptographic usage), Montgomery reduction is used.

• The first step of each iteration of the critical loop contains a branch controlled by secret data.
• The result of the previous step (w) controls how many times this loop iterates (i.e. the number of low 0 bits).
• Finally, there's another secret-dependent loop bound located at the end of the critical loop. The sum of these implementation details is that the bits of your exponent will be leaked (breaking SRP and Diffie-Hellman protocols).

Interestingly, the base (called g in the critical loop) is never directly leaked in this loop, which would superficially make it only safe for RSA encryption.

(However, values derived directly from the base are passed as parameters to mulTo(), which passes to the Montgomery reduction functions linked above. At minimum, this leaks via comparison.)

Modular Inversion

JSBN's implementation of modular inversion can be found here.

• This code continues for as long as the lowest bit of v (the number being inverted) is cleared (equal to 0).
• This code accesses variables based on a conditional branch (see bignum comparison below). If these two variables are physically located on different memory chips that take a perceptible difference of time to read from, the memory access pattern will be visible to the CPU.
• After the first loop iteration, the bits of u control a while loop iteration.

Bignum Comparison

The implementation of compareTo() can be found here. I've reproduced the algorithm below, but reformatted it to be more legible.

// (public) return + if this > a, - if this < a, 0 if equal
function bnCompareTo(a) {
    var r = this.s - a.s;
    if (r != 0) {
        return r;
    }
    var i = this.t;
    r = i - a.t;
    if (r != 0) {
        return this.s < 0 ? -r : r;
    }
    while (--i >= 0) {
        if ((r = this[i] - a[i]) != 0) {
            return r;
        }
    }
    return 0;
}

It should be clear that this will return a value quicker if the first limb differs between this and a than if a later limb differs. This function leaks information about the two numbers being compared.

Exploitation and Impact

Timing leaks are pernicious to cryptographic implementations. A cache-timing attack on software AES famously revealed the secret key in an attack that took about 65 milliseconds to conclude.

The main exploitation path for a library like JSBN is to have malicious code running in another browser window or service worker that probes the JavaScript engine (i.e. v8 in Chrome) to perform this sort of timing attack. For prior art, see Rowhammer, Meltdown, and Spectre.

If successful, this will leak the following for the respective asymmetric cryptography algorithms.

Algorithm / Operation	What Gets Leaked
RSA encryption	Message (base in exponentiation)
RSA signing	Private key (exponent)
Diffie-Hellman	Private key (exponent)
SRP	Private key (exponent x)
ECDSA signing	One-time secret k (via modular inverse)

Mitigations

The only effective mitigation is to make the JSBN code constant-time. I've previously written an open source constant-time implementation of bignum arithmetic in TypeScript (which can be trivially compiled to JavaScript).

My code uses constant-time conditional swaps instead of branches and peasant multiplication (which side-steps variable time multiplication opcodes on some architectures). It also avoids touching the high bit of JavaScript numbers, which the v8 engine uses to store a flag and would create a memory access timing leak.

This can serve as a reference implementation for recommending patch strategies to JSBN.

Disclosure Timeline

• 2022-04-08: Reported to the Xfinity Open Source program on Bugcrowd, which advertises jsbn as "in scope".
• 2022-04-10: Bugcrowd employee closes as "not applicable" because I didn't write an exploit.
  • For a bit of background: I am not an exploit developer, and it would probably take me hundreds of hours of research and education to pull off the most basic exploit demo that works against any JavaScript engine with significant market share. That's not a good use of my time, especially since that's the barrier put in place to get Bugcrowd's triage team to take a report seriously.
• 2022-04-10: I push back on this unrealistic hurdle towards the report being even looked at by Xfinity's team. I request disclosure, arguing, "If it's not applicable, there's logically no harm in disclosure."
• 2022-04-10: Bugcrowd employee agrees to check with the team and update the ticket.
• 2022-05-06: Comcast PSIRT says they've informed Andy of the details.

• 2022-06-14: Comcast PSIRT says they still haven't heard back from Andy, and denied my disclosure request.

  Since we don't author or maintain this code, we do not have any authority to grant a disclosure request. However you might be able to engage with them on the repository, or develope a further PoC that would enable validation of your claims.

• 2022-06-14: Immediate public disclosure on GitHub issue tracker.

[krishnaUIDev]

Any update on this issue? I am looking alternative ways to fix this issue.

[soatok]

Well, it's been more than two years. I'm guessing @andyperlitch won't be fixing it?