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.
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:
- Incorrect NIST P-521 curve parameters;
- A conditional statement issue that sometimes causes the scalar multiplication to mistakenly return the point at infinity; and
- A 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 Attack: The 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.
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.