How Ionic Security Fixed Two SJCL Bugs

Ionic Security uses publicly available libraries to implement some of its cryptographic primitives, such as elliptic curve scalar multiplication.  For this reason, Ionic is careful to distinguish between trusted and trustworthy libraries. To illustrate the difference between a library being trusted and earning trust, picture a bug that occurs if and only if some internal register is all 0s, or overflows. Such a condition may occur intermittently; say, once in every 100,000 scalar multiplications.  Or, it may be encountered exclusively, or primarily, when using certain elliptic curves. Now suppose that the library’s scalar multiplication is tested with 1,000 known answers for one of the elliptic curves, and a single test for each of the remaining supported curves. The library may be trusted by the public even though it is not trustworthy, and Ionic would be remiss to use it without more testing.

Previously, Ionic found a few such bugs in the popular MSR JavaScript Cryptography Library (MSRCrypto) by testing a million scalar multiplication known answers for each of three elliptic curves (above and beyond those provided in the published libraries). It was natural to ask whether the same known answers would pass in other popular elliptic curve libraries or reveal bugs, as it did with MSRCrypto.  We decided to test the Stanford Javascript Crypto Library (SJCL) next.

In this article, we report that one SJCL bug did indeed surface. In addition, we tracked down and fixed a second bug that had been known since 2015. Once the bugs were fixed and all three million known answer tests passed – plus a few additional tests to extend coverage to every curve SJCL supports – we gained confidence in the accuracy of SJCL’s elliptic curve scalar multiplication. This confidence extends to the primitives used in scalar multiplication: elliptic curve point doubling and addition. These, in turn, depend on operations in the underlying finite field, which depend on big number arithmetic. Each of these primitives was exercised thoroughly and passed the tests.

The two bugs that we found and fixed in SJCL are: an overflow in field element multiplication, and an error in the modular reduction of pseudo-Mersenne primes (sometimes called Solinas primes). Our thanks go out to Nils Thenhausen, who maintains SJCL, for merging this fix.

Impact

Prior to SJCL version 1.0.8, both the overflow and modular reduction bugs cause encryption and digital signature failures for valid messages and keys, and can lead to unexpected errors in the applications that depend on SJCL. The overflow bug potentially affects any code that uses multiplication of SJCL big numbers, which includes the elliptic curve cryptography module. SJCL uses a specialized modular reduction algorithm that worked for some elliptic curves, but not others – e.g., the SEC Group elliptic curve p224k1. The modular reduction patch fixes all the curves currently supported by SCJL. Of special concern, for either bug, are calls to sjcl.encrypt and sjcl.decrypt; and usage of sjcl.ecc.elGamal or sjcl.ecc.ecdsa.  For the overflow bug, any use of sjcl.bn.mul() is also at risk.

Overflow Bug

The overflow in field element multiplication arises from the fact that integers with over 53 bits cannot be stored in Javascript’s number type. Normally, the code in SJCL that uses mul() – defined in the code block below – ensures that each element of the inputs this.limbs and that.limbs is less than 224. The nested for loops in the code below can safely compute c[i+j] as the sum of up to 32 integer products of 24-bit limbs array elements, because

c[i+j] < 32 (224 × 224) = 253 .

Field Element Multiplication in bn.js

mul: function(that) {
    if (typeof(that) === "number") { that = new this._class(that); }
    var i, j, a = this.limbs, b = that.limbs, al = a.length, bl = b.length, out = new this._class(), c = out.limbs, ai, ii=this.maxMul;
  
    for (i=0; i < this.limbs.length + that.limbs.length + 1; i++) {
      c[i] = 0;
    }
    for (i=0; i<al; i++) {
      ai = a[i];
      for (j=0; j<bl; j++) {
        c[i+j] += ai * b[j];
      }
  
      if (!--ii) {
        ii = this.maxMul;
        out.cnormalize();
      }
    }
    return out.cnormalize().reduce();
}

Prior to our fix – which normalizes inputs to mul() before using them – limbs would, in rare cases, contain several elements with 25 or 26 bits. Even a 25-bit limit on limbs elements would cut the safe number of terms contributing to c[i+j] from 32 to just eight – too small for most of the elliptic curves SJCL supports. For example, one of the smaller curves, p224k1, uses a field with elements that would not fit in a limbs array of less than nine 25-bit integers.

When implementing the normalization that fixes the overflow bug, there were two options: mutate the inputs or allocate new memory for temporary variables. In the first option, the inputs are to normalized before computing the multiplication, and the second method normalizes copies of the inputs. Mutating the input was the simpler fix, but developers should be aware of this change in behavior for sjcl.bn.mul().

Modular Reduction Bug

In many of the field operations that support elliptic curve arithmetic, SJCL performs a fast modular reduction by the prime field’s modulus p. As noted above, p is assumed to be a pseudo-Mersenne prime – the sum of a handful of powers of 2, or their negatives. The small number of component powers of 2 in p makes fast modular reduction possible. Given a number n to reduce mod p, SJCL does the following:

  1. Approximate p by the closest power of 2. In p224k1, for example, p ~ 2224. Let u be this exponent, i.e., = 224.
  2. Approximate n as the most significant word v in the limbs array that represents n.  That is, n ~ 2(u-u%24)v.  Here, % is the modulus operator.
  3. Approximate the quotient of n/p as q=2(u-u%24)v/2u = v>>(u%24), which fits in one Javascript number.  Here >> is the right-shift operator.
  4. Compute the remainder r = n-q×(fast because p has just a few components)

The result is not quite a full reduction, but the remainder r is near a small multiple of p. After this, reduction of r to a number between 0 and p is a comparatively inexpensive task.

The technique used to accomplish step 4 uses two pre-computed arrays: fullOffset and fullFactor. The snippet below, from strongReduce(), accomplishes step 4.

Computation of n – q x p

l = limbs[i] & this.fullMask;
limbs[i] -= l;
for (k=0; k<this.fullOffset.length; k++) {
  limbs[i+this.fullOffset[k]] -= this.fullFactor[k] * l;
}
this.normalize();

In the above code,

  • The line limbs[i] -= 1 subtracts q×2u.  The for loop subtracts the rest of q×p.
  • The product, this.fullFactor[k]*l, must be an integer or this.normalize() will later truncate limbs[i+this.fullOffset[k]] to an integer, causing an arithmetic error.
  • this.fullMask is -2u%24, so the local variable, l, is a multiple of 2u%24.
  • this.fullFactor[k] is 2-b for some b, so this.fullFactor[k]*l is only guaranteed to be an integer if u%24 is at least b.

The bug we fixed is in the definition of a pre-computed array, this.fullOffset.  This definition caused the exponent b in this.fullFactor to exceed the exponent u%24 in l. This resulted in fractional values of limbs[i+this.fullOffset[k]], and arithmetic errors ensued.

Of the eight elliptic curves supported by SJCL, the bug mainly affected the 224-bit elliptic curve p224k1. However, the bug also prevented modular reduction of user-defined pseudo-Mersenne primes and support of additional elliptic curves. The reason p224k1 is sensitive to the bug is that this.fullMask happens to be a relatively small power of 2:

this.fullMask=-2u%24=2224%24=-28.

The exponent 8, which had to be as large as b, failed that condition more easily than in, say, p256k1 where this.fullMask=-216.

The Bug Hunt

Once the bugs were identified, via our testing and reading through the repository’s reported issues concerning SJCL elliptic curve arithmetic, we narrowed the problems down by comparing actual against correct internal computations. In many cases, Mathematica scripts provided the correct internals for comparison. For the overflow bug, we also developed a Big Number Javascript Library that takes limbs arrays and strings as inputs and writes outputs in string format.

At one point, the Big Number String Library computed a different result for a multiplication from the one sjcl.bn.mul() computed. To see why, we used the sjcl.bn.toString(), instead of the Big Number String Library, to format the inputs. Making this call to toString() mysteriously fixed the bug! Further analysis revealed that sjcl.bn.toString() normalizes its input – which turned out to be the fix sjcn.bn.mul() needed.

The modular reduction bug was quickly isolated to strongReduce(). From there, a lot of the work was understanding what the modular reduction algorithm was trying to do.  Once it was clear that this.fullMask has to contain a higher power of 2 than the power of 1/2 in this.fullFactor, our understanding of the reduction algorithm guided us to the right place to fix: this.fullOffset, which determines the powers of 1/2 in this.fullFactor.

Disclosure Process

Once the bug fixes were identified, we coordinated disclosure and correction with Nils Thenhausen, who maintains SJCL. Nils implemented the fix we suggested for the modular reduction bug, and a fix very similar to our suggestion for the overflow bug.

The detailed timeline is as follows:

DateAction
10/08/18Initiated contact with [email protected] with a high-level description and outlined our disclosure policy.
10/09/18Received a reply from Nils at [email protected] asking for more details about the impacts. We replied describing the impacts and provided patches.
10/25/18Nils confirmed that our patches worked, but requested additional regression tests.
10/30/18Sent further details about the modular reduction issue and regression tests for both issues.
11/07/18Nils accepted the regression tests, and requested credit information.
11/08/18Sent Ionic acknowledgement information.
11/12/18Commits made on GitHub (https://github.com/bitwiseshiftleft/sjcl/pull/376/commits).
New SJCL release on npm is 1.0.8 (https://www.npmjs.com/package/sjcl/v/1.0.8).

Conclusion

If you are using the SJCL library, you should update to the latest version, 1.0.8. If you have a reason to use the previously broken elliptic curve, p224k1, it should now be possible. Though no number of random known answer tests can guarantee that a library is bug-free, a million tests per elliptic curve now pass. This many successful tests should bolster confidence in SJCL’s implementation of big number and elliptic curve arithmetic.

These findings also help pose the right questions about elliptic curve libraries we have not tested externally yet: How many known answer tests they already have, what elliptic curves are covered in the tests, and how evenly the tests cover the supported curves. Similar questions and expectations also extend to other types of cryptography, such as symmetric key ciphers. We encourage anyone interested in the reliability of cryptographic products to help us investigate such questions, and to stay tuned for more of our findings.  Anyone wishing to coordinate these efforts can contact us at:

math@ionicsecurity.com

Ionic Security is committed to building trust in a untrusted world, and strives to develop trustworthy products like Ionic Machina. The Ionic Applied Research team will continue serving as friendly neighborhood cryptographers through continued testing and disclosure of the results.

###

Colin McRae and Jonathan Burns