ionic-security-identifies-multiple-issues-in-javascript-cryptographic-library-cve-2018-8319_Ionic-blog_thumb

Ionic Security Identifies Multiple Issues in JavaScript Cryptographic Library (CVE-2018-8319)

At Ionic Security, our Research Team explores how to apply cryptographic techniques that – combined with the Ionic Data Trust Platform – can deliver new and unique value to companies that desire secure and scalable data security solutions.

Our team found three ECC implementation errors in the MSR JavaScript Cryptography Library, some of which result in vulnerabilities which can weaken private keys and may allow an attacker to forge digital signatures. The msrCrypto Library (v1.4) has been directly downloaded thousands of times, and incorporated into many NodeJS cryptographic projects through the NPM ‘msrcrypto’ package.

We disclosed these issues privately to Microsoft and worked with them to explain the problems and suggest fixes. Microsoft has now released CVE-2018-8319 which identifies these issues. After the release, we notified the NPM package owner of the CVE and they quickly released an updated version. Here, we are sharing additional details which we hope will help people understand the issues, quantify the risk, and learn from how we identified and tested them.

At a high level, the three errors were:

  1. Incorrect NIST P-521 curve parameters;
  2. conditional statement issue that sometimes causes the scalar multiplication to mistakenly return the point at infinity; and 
  3. coordinate conversion issue that causes a scalar multiplication error.

The first issue applied to a single curve, but the latter two applied to arithmetic over all elliptic curves. We’ll share more details of these issues below.

From these issues, we identified that certain ECC security protocols may be vulnerable to:

  • Differential Fault AttackThe coordinate conversion issue leaves a target system susceptible to a differential fault attack – much like the invalid curve attack – where an attacker can craft a request whose response reveals some information about the target’s private key, weakening its strength.
  • ECDSA Signature Forging: As explained here, the ECDSA allows a signer to generate a digital signature for a message using a private key, and anyone with access to the signer’s public key can validate the message signature. This attack could allow a malicious party to generate a digital signature for a message without access to the signer’s private key.

 

Discovery Process

Ionic is currently utilizing the ECC scripts in the msrCrypto library within a JavaScript implementation of a new technology (available to customers via a private beta). This technology is implemented across a variety of languages to support different customer’s needs. Each language utilizes an appropriate library, and we selected the Microsoft Research JavaScript Cryptography Library (msrCrypto) for JavaScript usage due in part to its speed. During our development, the msrCrypto ECC calculations were checked against the known answer tests from our C++ implementation. Computations on the curves P-256 and P-384 agreed, but arithmetic on the P-521 curve failed. The tests were validated using Mathematica as a tie-breaker, and it became apparent that something in the msrCrypto P-521 implementation wasn’t quite right. Since P-256 and P-384 both passed the known answer tests (KATs), it was quickly discovered that the P-521 curve parameters contained typos.

Later, we decided to narrow the functionality gap between the msrCrypto and Java’s Bouncy Castle libraries by supporting some additional elliptic curves – but mysterious errors appeared when we performed scalar multiplication. These had never been seen in our basic testing for the NIST curves, so it left us wondering: “Would we see such errors if we tested (say) a million scalar multiplications – a stress test?”

The million point stress test revealed that one in every 2,000 scalar multiplications failed by returning invalid points, due to what we call the coordinate conversion issue. The tests were rerun after patching that bug, and resulted in a single failure caused by the conditional statement issue. In retrospect, the conditional statement issue rarely occurs by chance (possibly once in every 224 tests), so we may have gotten lucky to catch it this way.

 

Testing And Diagnosis

For those curious, we briefly outline the steps taken to diagnose and patch the encountered errors, so that any interested parties can apply similar techniques to other libraries.

Why Mathematica? Production cryptographic libraries tend to be highly optimized and use sophisticated techniques to obtain marginal speedups – making them notoriously difficult to debug. What’s worse, few programming languages natively support arbitrary-precision arithmetic, but large integers and finite fields are cryptographic primitives. Many ECC libraries end up building their arithmetic from the ground up. Fortunately, mathematical languages such as Mathematica, Maple, Matlab, SageMath, etc. handle these complex objects with ease. Wanting to eliminate as many confounding variables as possible, we based our debug environment / test generator on a simple EC implementation in Mathematica: EllipticCurveAlgorithms.nb.

What tests? After a few customizations, the EC notebook was used to generate JSON files totaling a million randomly generated scalar multiplication KATs for the three NIST curves supported by msrCrypto: P-256, P-384 and P-521. These test files were fed into a custom Mocha test, which exercised msrCrypto to perform scalar multiplications for the inputs in each JSON file. The results from msrCrypto were compared to their respective KATs, and any errors (according to Mathematica at least) were flagged for further analysis.

Who was right? In order to reach a consensus, we ran the KATs through the Java Bouncy Castle library to broker the discrepancies between msrCrypto and Mathematica. A Java test harness was set up to accept the flagged KAT files and compute specific tests based on the marked inputs. In every instance, Bouncy Castle agreed with Mathematica.

How was it fixed? Print statements were added throughout the msrCrypto scalar multiplication and supporting functions to expose the step-by-step intermediate values used throughout the calculation. The Mathematica debugging rig proved helpful in verifying the inputs and outputs of each of the functions along the way. For both types of error (off-the-curve points and points at infinity), mistakes in the precomputed lookup table precipitated an incorrect final result.

The conditional statement issue was straightforward to find and patch; as at one step, the intermediate results suddenly became the point at infinity. The mistake in a conditional statement preceding the first wrongful assignment was quickly located.

The coordinate conversion issue took significantly more work to identify. While it was easy to verify that the precomputed lookup table contained off-the-curve points, the addition algorithm was different for Mathematica and msrCrypto – often it seems that no two EC libraries use the same scalar multiplication implementation. Two of the optimizations utilized in the msrCrypto library include a fixed number of registers to manage memory and minimize the number of operations, and the use of Jacobian coordinates to prevent costly divisions. We ended up recreating the fixed register addition algorithm in Mathematica, and found that the final transformation from Jacobian coordinates back to the ordinary (affine) coordinate was the culprit. During this conversion, a modular inverse is computed, which sometimes has fewer digits than the ensuing code expects, and the calculations go awry from there.

 

Vulnerability Deep Dive

In this section, we’ll get into an extremely detailed discussion of the issues, why they occurred, and what they look like in the code. If you just want to learn about the resulting attacks or the disclosure process and fixes, you may wish to skip this section.

Incorrect NIST P-521 Curve Parameters

This was the simplest error, and just required correcting the values in the curve’s definition. In the patch, Microsoft corrected the leading byte transpositions for P-521 accordingly:

Corrections to `curves_NIST.js`

var curve_P521 = {
    name: "P-521",
    type: 0, // Curve Type 0 = Weierstrass, 1 Twisted Edwards
-    p: [0x10, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF],
+    p: [0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF],
-    a: [0x10, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC],
+    a: [0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFC],
-    b: [0x51, 0x95, 0x3E, 0xB9, 0x61, 0x8E, 0x1C, 0x9A, 0x1F, 0x92, 0x9A, 0x21, 0xA0, 0xB6, 0x85, 0x40, 0xEE, 0xA2, 0xDA, 0x72, 0x5B, 0x99, 0xB3, 0x15, 0xF3, 0xB8, 0xB4, 0x89, 0x91, 0x8E, 0xF1, 0x90, 0xE1, 0x56, 0x19, 0x39, 0x51, 0xEC, 0x7E, 0x93, 0x7B, 0x16, 0x52, 0xC0, 0xBD, 0x3B, 0xB1, 0xBF, 0x70, 0x35, 0x73, 0xDF, 0x88, 0x3D, 0x2C, 0x34, 0xF1, 0xEF, 0x45, 0x1F, 0xD4, 0x6B, 0x50, 0x3F, 0x00],
+    b: [0x00, 0x51, 0x95, 0x3E, 0xB9, 0x61, 0x8E, 0x1C, 0x9A, 0x1F, 0x92, 0x9A, 0x21, 0xA0, 0xB6, 0x85, 0x40, 0xEE, 0xA2, 0xDA, 0x72, 0x5B, 0x99, 0xB3, 0x15, 0xF3, 0xB8, 0xB4, 0x89, 0x91, 0x8E, 0xF1, 0x09, 0xE1, 0x56, 0x19, 0x39, 0x51, 0xEC, 0x7E, 0x93, 0x7B, 0x16, 0x52, 0xC0, 0xBD, 0x3B, 0xB1, 0xBF, 0x07, 0x35, 0x73, 0xDF, 0x88, 0x3D, 0x2C, 0x34, 0xF1, 0xEF, 0x45, 0x1F, 0xD4, 0x6B, 0x50, 0x3F, 0x00],
-    order: [0x10, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFA, 0x51, 0x86, 0x87, 0x83, 0xBF, 0x2F, 0x96, 0x6B, 0x7F, 0xCC, 0x10, 0x48, 0xF7, 0x90, 0xA5, 0xD0, 0x3B, 0xB5, 0xC9, 0xB8, 0x89, 0x9C, 0x47, 0xAE, 0xBB, 0x6F, 0xB7, 0x1E, 0x91, 0x38, 0x64, 0x90],
+    order: [0x01, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFA, 0x51, 0x86, 0x87, 0x83, 0xBF, 0x2F, 0x96, 0x6B, 0x7F, 0xCC, 0x01, 0x48, 0xF7, 0x09, 0xA5, 0xD0, 0x3B, 0xB5, 0xC9, 0xB8, 0x89, 0x9C, 0x47, 0xAE, 0xBB, 0x6F, 0xB7, 0x1E, 0x91, 0x38, 0x64, 0x09],
-    gx: [0xC6, 0x85, 0x8E, 0x60, 0xB7, 0x40, 0x40, 0xE9, 0xCD, 0x9E, 0x3E, 0xCB, 0x66, 0x23, 0x95, 0xB4, 0x42, 0x9C, 0x64, 0x81, 0x39, 0x50, 0x3F, 0xB5, 0x21, 0xF8, 0x28, 0xAF, 0x60, 0x6B, 0x4D, 0x3D, 0xBA, 0xA1, 0x4B, 0x5E, 0x77, 0xEF, 0xE7, 0x59, 0x28, 0xFE, 0x1D, 0xC1, 0x27, 0xA2, 0xFF, 0xA8, 0xDE, 0x33, 0x48, 0xB3, 0xC1, 0x85, 0x6A, 0x42, 0x9B, 0xF9, 0x7E, 0x7E, 0x31, 0xC2, 0xE5, 0xBD, 0x66],
+    gx: [0x00, 0xC6, 0x85, 0x8E, 0x06, 0xB7, 0x04, 0x04, 0xE9, 0xCD, 0x9E, 0x3E, 0xCB, 0x66, 0x23, 0x95, 0xB4, 0x42, 0x9C, 0x64, 0x81, 0x39, 0x05, 0x3F, 0xB5, 0x21, 0xF8, 0x28, 0xAF, 0x60, 0x6B, 0x4D, 0x3D, 0xBA, 0xA1, 0x4B, 0x5E, 0x77, 0xEF, 0xE7, 0x59, 0x28, 0xFE, 0x1D, 0xC1, 0x27, 0xA2, 0xFF, 0xA8, 0xDE, 0x33, 0x48, 0xB3, 0xC1, 0x85, 0x6A, 0x42, 0x9B, 0xF9, 0x7E, 0x7E, 0x31, 0xC2, 0xE5, 0xBD, 0x66],
-    gy: [0x10, 0x18, 0x39, 0x29, 0x6A, 0x78, 0x9A, 0x3B, 0xC0, 0x40, 0x5C, 0x8A, 0x5F, 0xB4, 0x2C, 0x7D, 0x1B, 0xD9, 0x98, 0xF5, 0x44, 0x49, 0x57, 0x9B, 0x44, 0x68, 0x17, 0xAF, 0xBD, 0x17, 0x27, 0x3E, 0x66, 0x2C, 0x97, 0xEE, 0x72, 0x99, 0x5E, 0xF4, 0x26, 0x40, 0xC5, 0x50, 0xB9, 0x10, 0x3F, 0xAD, 0x70, 0x61, 0x35, 0x3C, 0x70, 0x86, 0xA2, 0x72, 0xC2, 0x40, 0x88, 0xBE, 0x94, 0x76, 0x9F, 0xD1, 0x66, 0x50],
+    gy: [0x01, 0x18, 0x39, 0x29, 0x6A, 0x78, 0x9A, 0x3B, 0xC0, 0x04, 0x5C, 0x8A, 0x5F, 0xB4, 0x2C, 0x7D, 0x1B, 0xD9, 0x98, 0xF5, 0x44, 0x49, 0x57, 0x9B, 0x44, 0x68, 0x17, 0xAF, 0xBD, 0x17, 0x27, 0x3E, 0x66, 0x2C, 0x97, 0xEE, 0x72, 0x99, 0x5E, 0xF4, 0x26, 0x40, 0xC5, 0x50, 0xB9, 0x01, 0x3F, 0xAD, 0x07, 0x61, 0x35, 0x3C, 0x70, 0x86, 0xA2, 0x72, 0xC2, 0x40, 0x88, 0xBE, 0x94, 0x76, 0x9F, 0xD1, 0x66, 0x50],
    cf: 1  // co-factor
};
Conditional Statement Issue

This issue resulted from a mistake in a conditional check of the mixedDoubleAdd function which can cause an erroneous (0,0) result. The mixedDoubleAdd function takes a point Q (represented in Jacobian form as (X1, Y1, Z1)) and a point L (represented in affine form as (x2,y2)) and returns the point P = 2Q + L (in Jacobian form). Rather than checking whether the z-coordinate of P is zero – i.e., all its digits are zero – the conditional statement checks whether the second digit of the z-coordinate is zero. The error and Microsoft’s correction is as follows:

Correction to the `mixedDoubleAdd` function in `cryptoECC.js`

                var temp3isZero = true;
      
                for (var i = 0; i < temp3.length; i++) {
-                   if (temp3[1] !== 0) {
+                   if (temp3[i] !== 0) {
                        temp3isZero = false;
                        break;
                    }
                }
      
                if (temp3isZero) {

The exact value of temp3 in the above code is

(Y– y2 Z13)– 3 X1 (X1 – x2 Z12)2 + (X1 – x2 Z12)3  (mod p),

and the error occurs when

[ temp3 (mod 248) ]  – [ temp (mod 224) ] = 0.

While this may seem complicated, the following is a practical example of how this issue causes an erroneous scalar multiplication result:

Example: Scalar multiplication

// initialize curve parameters and arithmetic operations
const curve = cryptoECC.createCurve("P-521"),
curveOps = new cryptoECC.EllipticCurveOperatorFp(curve);
 
// define input point and initialize output point
const x = cryptoMath.stringToDigits("6226095040242566415446936650360240966905799066935165165566586975890411317217790343573678460737077181579767415383024006362332654606788956101557874182074789048");
const y = cryptoMath.stringToDigits("2491672116746286474420412593950334035114094161891879412739951659905137162842641942197488347306647126050453280014688477831318554573396000123494501552070611155");
var inPoint = new cryptoECC.EllipticCurvePointFp(curve, false, x, y, null, false);
var outPoint = inPoint.clone();
 
// perform scalar multiplication
const k = cryptoMath.stringToDigits("6712705569953063273288282103116926980697299871683161891337635899733122182041341253412504499891442164589015728543164560562731036521277560960298619523862715143");
curveOps.scalarMultiply(k, inPoint, outPoint);
 
// print result
console.log({
  "x": cryptoMath.digitsToString(outPoint.x),
  "y": cryptoMath.digitsToString(outPoint.y)
});
 
// returns {x: "0", y: "0"}

In the previous example, the scalarMultiply function calls scalarMultiplyW which in turn calls mixedDoubleAdd. The multiplication error begins when the following intermediate addition is computed and persists on through the final output. We demonstrate this here, but most users would not directly utilize these functions:

Example: Mixed double addition

// initialize curve parameters and arithmetic operations
const curve = cryptoECC.createCurve("P-521"),
curveOps = new cryptoECC.EllipticCurveOperatorFp(curve);
 
// define Jacobian input point
const jacX = cryptoMath.stringToDigits("6226095040242566415446936650360240966905799066935165165566586975890411317217790343573678460737077181579767415383024006362332654606788956101557874182074789048");
const jacY = cryptoMath.stringToDigits("3376567685541142430372513786034166041650693352712604014537986004612002826138250204885480201896679156763934794854481465497248962372493513745313889827556979316");
const jacZ = cryptoMath.stringToDigits("2546131420633895200198405596579864312708503008901485305814071452526919839433918626354330384689119404473858877879809052850874228610579906316609784345799974104");
var jacPoint = new cryptoECC.EllipticCurvePointFp(curve, false, jacX, jacY, jacZ, true);
 
// define Affine input point
const affX = cryptoMath.stringToDigits("1327166397738673762199724492904220620087358433166740812604825781727630630427662550746520331881925607579011351292077381567671526314314759855646068007969448184");
const affY = cryptoMath.stringToDigits("1206727782612940574177357333507103745073235528346751086434034823915360608497143118462415018918318391998080104223027550511168297321885026718387762416692125780");
var affPoint = new cryptoECC.EllipticCurvePointFp(curve, false, affX, affY, null, true);
 
// perform mixed double addition
var outPoint = jacPoint.clone();
curveOps.mixedDoubleAdd(jacPoint, affPoint, outPoint);
 
// print result
console.log({
  "x": cryptoMath.digitsToString(outPoint.x),
  "y": cryptoMath.digitsToString(outPoint.y),
  "z": cryptoMath.digitsToString(outPoint.z)
});
 
// returns {x: "0", y: "1", z: "0"}

If the point at infinity is obtained during any of the mixedDoubleAdd computations within the scalar multiplication algorithm, then the final output will be (0,0). This means that if a scalar K = [ k0, k1, …, ki, ki+1, …, kd ]  fails after evaluating ki, it will fail for any other scalar that agrees with K up to the value ki. In this way, a single bug allows an attacker to construct an abundance of failures that cannot be screened out by point validation.

 

Coordinate Conversion Issue

The root cause of this issue is that the function convertToAffineForm (defined in EllipticCurveOperatorFp) calls the function modInv (defined in msrcryptoMath) when converting a Jacobian point (X,Y,Z) into its affine form (x,y) using the formula that follows:

Conversion from Jacobian coordinates to affine coordinates

x ← X/Z^2 
y ← Y/Z^3

By design, msrcyptoMath does not “know” that functions in EllipticCurveOperatorFp operate only on full-length byte arrays – those that have as many bytes as the modulus that defines the field. So when modInv occasionally has a result to return that can be expressed in a less than a full-length byte array, it returns the result with just the bytes needed.  convertToAffineForm feeds this short representation of z-1 to a MontgomeryMultiplier, which expects the full-length input.  As a result, Montgomery multiplication to get x and y by the above formulas fails.  This ends up polluting the table P, 3P, 5P, …, 31P (as noted above) because this table has affine entries.

To fix this, Microsoft added an optional boolean parameter to modInv, and used it everywhere in EllipticCurveOperatorFp that modInv is called.  The change to the definition of modInv is:

Correction to the `modInv` function in `cryptoMath.js`

-     function modInv(a, n, aInv) {
---
+     function modInv(a, n, aInv, pad) {
1039a1043
+         /// <param name="pad" type="Boolean" optional="true">True to pad the returned value to the length of the modulus (optional).</param>
1059c1063,1067
-             normalizeDigitArray(aInv);
+             if (pad) {
+                 normalizeDigitArray(aInv, n.length, true);
+             } else {
+                 normalizeDigitArray(aInv);
+             }

The use of the new signature for modInv that fixes the bug we reported is:

Correction to the `convertToAffine` function in `cryptoECC.js`

        function convertToAffineForm(point) {
            /// <param name="point" type="EllipticCurvePointFp"/>
 
            if (point.isInfinity) {
                point.z = null;
                setterSupport || (point.isAffine = true);
                return;
            }
 
            // DETERMINE 1/Z IN MONTGOMERY FORM --------------------------------
 
            // Call out to the basic inversion function, not the one in this class.
-             cryptoMath.modInv(point.z, curve.p, conversionTemp2);
+             cryptoMath.modInv(point.z, curve.p, conversionTemp2, true);
A Tale of Two Attacks

Arithmetic errors in ECC libraries are highly situational, so it is difficult to quantify the true impact of these vulnerabilities in general – as they depend on how the library is utilized by other developers in their projects. Here we present two types of attacks, but this does not preclude the possibility of other unforeseen exploits.

Differential Fault Attack

One method for exploiting the convertToAffine vulnerability (coordinate conversion issue) is to send the target (e.g., a service running this library) EC points that elicit errors in order to gain information about the target’s private key from the response. In particular, the attacker can learn whether certain intermediate values are used based on whether the final computation is “on” or “off” the curve.

Some information about msrCrypto’s implementation of EC arithmetic is required to understand this attack. The  cryptoECC.js  script in the msrCrypto library implements scalar multiplication using a regular signed window “double-and-add” algorithm with a window size of w = 5 or 6 bits, and makes use of the following optimizations: Montgomery modular multiplication, scalar recoding, arithmetic with Jacobian coordinates, and pre-computation of the window lookup table. See here for details about these algorithms and optimizations.

The first step in computing the scalarmultiplication k Pinvolves computing and storing the values

P, 3P, 5P, … , (2w -1) P,

which will be used as a window lookup table. The scalar value k (the target’s private key) is then recoded as an array of signed odd digits from ±1 to ±(2w-1) referred to as “windows”. For example, k=1234567 would be recoded as the windows [-25,21,21,5,1] for w=5, i.e.,

1234567 = 1×(25)+ 5×(25)+ 21×(25)+ 21×(25)1 – 25×(25)0.

The regular signed window “double-and-add” method is then applied to  k P = (kn (2w)n + … + k0 (2w)0 ) P.

Attack: Suppose that the target, Bob, uses a static private key k to compute scalar multiplication with the msrCrypto library. A malicious Mallory knows how Bob will calculate his pre-computation table, and can select a point P so that a single value (2i-1) P in the table encounters the coordinate conversion issue. If Bob’s response is off-the-curve, then he used the faulty table value within the scalar multiplication computation, so his private key contains either the digit (2i-1) or -(2i-1). Mallory can iterate this attack for all possible odd digits and thus weaken the strength of Bob’s private key.

Using windows of w=6 bits, a 256-bit private key is recoded as a d=43 digit array of signed odd numbers ±1,…,±63. If each signed odd digit is equally likely to occur in the private key, then it is expected that a random key will contain (2w+1)(1-(1-(2w+1)-1)d) = 24.2 distinct zero or odd digits. A private key that contains 25 of the possible 33 digits is reduced to approximately 235-bits of key strength. Similarly, a 512-bit private key is estimated to be reduced to 508-bits of security.

ECDSA Signature Forgery

While the coordinate conversion issue typically results in a value that is “off-the-curve”, an error caused by the conditional statement issue always returns the point at infinity (0,0). In the ECDSA, a signature (r,s) is used to verify that a message M has been signed using a private key k by checking that for (x,y) = (z s-1) G + (r s-1) QA  where z is derived from the hash of M, G is a public basepoint, and QA = k G is the public key generated from the private key k.

Attack: It may be possible for Mallory to select u2 ≠ 0 so that u2 QA = (0,0)  and  (z s-1) G = (x,y) such that r ≡ x (mod n). Likewise, it may be possible to choose  u1 ≠ 0  for which  uG = (0,0)   and  (x,y) = (r s-1) QA  where  r ≡ x (mod n).

 

Disclosure Process

Once discovered and confirmed, we initiated a coordinated vulnerability disclosure with Microsoft via the Microsoft Security Response Center (MSRC). We appreciate Microsoft’s commitment to resolving the issue and their quick work to resolve it.

After MSRC published the CVE, we observed that they had not appeared to notify the NPM maintainer, although we had mentioned the NPM package and its frequent usage (e.g., 560 downloads from NPM directly from 6/5/18 to 6/11/18). As the information was already public on 7/16/18, we notified the maintainer via the GitHub repository and he quickly released a new update within approximately 6 hours which should now distribute the fixed source code.

The detailed timeline is as follows:

Conclusion

If you are using the msrCrypto JS library, you should immediately update to the latest version. This may be a bit confusing due to the versioning of the NPM module: if you are using the copy from Microsoft, you want 1.4.1 or above, but if you are using the version from NPM, you need 1.4.2 or above. After updating, you should follow the recommendation in the Microsoft posting:

“If you are using the NIST P-521 curve, revoke and replace X.509 certificates issued using the NIST P-521 curve, and invalidate data signed by such certificates.”

However, we recommend the further steps of treating all static private keys as potentially compromised (regardless of the curve), since an attacker could have carried out the differential fault attack on a private key prior to the update. The above examples illustrate of how almost any error in ECC implementation can be exploited, so we suggest moving to new keys and not trusting previously used ones if you are uncertain of how these vulnerabilities effect your msrCrypto dependent application.

Most ECC attacks focus on a library’s lack of point validation, memory mismanagement, or other side-channel attacks, so it is an unusual problem to consider what happens when ECC arithmetic sporadically fails. We hope that this explanation of the bugs we found – along with the identification and debugging steps – has demonstrated some of the nuances of ECC libraries.

The Ionic Data Trust Platform is built upon the principle that a customer can have full control over their data and the keys with which it is protected – without needing to place trust in any external party. We often refer to this as “In Math We Trust” – a principle which we take seriously and apply to all the cryptographic primitives that support the Ionic Data Trust Platform.

 

###

Jonathan Burns, Colin McRae, and Ryan Speers

Close ()