Vulnerability Disclosures

Some vulnerabilities are serious enough they must be addressed behind closed doors. Here is what happened for each of them.

Critical failure of EdDSA checking (2018-06-20; fixed in 2.0.4, 1.1.1)

Effect

When presented with an all zero signature, the crypto_check() function accepted as legitimate 50% of messages on average. This allowed the attacker to forge messages with the following procedure:

1. Chose a public key PK to impersonate.
2. Choose a message msg of size msg_size to forge.
3. Let zero be an all zeroes 64-byte buffer.
4. Try crypto_check(zero, PK, msg, msg_size).
5. If the signature is accepted, the attack is successful. Otherwise, go back to step 2.

The attack is expected to succeed in 2 attempts on average.

Cause

The error was in the ge_scalarmult() internal function. To speed up computation, the Edwards point was converted to Montgomery space, then the scalar multiplication was performed with the Montgomery ladder, and the point was converted back to Edwards space.

This does not work in all cases, for 3 reasons:

• Curve25519 and Edwards25519 are birationally equivalent. It’s like a bijection, except when the denominators of the conversion functions are zero.
• The algorithm used to recover the Y coordinate does not work in all cases.
• The Montgomery ladder conflates points zero and infinity.

When performing signature verification, the signature is under the control of the attacker, potentially allowing them to exploit any error. Even if such errors only happen in exceptional cases, a signature can be specially crafted to trigger them.

How it was corrected

The optimisation has been reverted and replaced by a classical double and add ladder. The complete addition law of twisted Edwards curves guarantees the absence of special cases, and thus ensures the vulnerability has been corrected.

Wycheproof test vectors have also been added to the test suite to ensure non-regression, and probe for any other vulnerability. None was found. The tests pass as expected.

Timeline

On Wednesday the 20th of June 2018, Mike Pechkin informed me, Loup Vaillant, that crypto_check() accepted the all zero input as valid:

uint8_t zero[64] = {0};
if (crypto_check(zero, zero, 0, 0)) {
    printf("Rejected\n");
} else {
    printf("Accepted\n");
}

I initially thought this was because of the all zero public key, which is a low order key. Monocypher makes no guarantee when you verify with an invalid public key. Still, Mike Pechkin found several bugs in earlier versions of Monocypher, I couldn’t dismiss his input out of hand. I tried libsodium and TweetNaCl. libsodium, as expected, rejected the input (it has low order checks). TweetNaCl also rejected the signature. That I did not expect.

I dug deeper and found the following day that Monocypher accepted the signature even with a genuine public key. We had a critical vulnerability. The first one since 1.0.0.

I searched through the git history, and found the bug was introduced by a mostly working, but ultimately faulty, conversion to Montgomery space and back. I reverted the patch, and shipped the fix 4 days later, in versions 2.0.4 and 1.1.1 (the 1.x.x branch is deprecated, but it still had to be fixed).

To ensure the vulnerability doesn’t go back, I added tests that verify the all zero signature is never accepted with legitimate keys. Later, when I became aware of the Wycheproof test vectors, I added them immediately. They didn’t reveal any other vulnerability.

The correction temporarily halved the speed of signatures and verification. The performance loss was recovered later by using standard optimisations: Combs, sliding windows, and double scalar multiplication.

How could this happen?

As catastrophic as it was, the error was fairly subtle. The conversion I was trying to do was mostly correct, but ultimately had exploitable exceptions. I failed to notice it for three reasons:

• I did not look up the term “birational equivalence” and treated that as if it was a bijection.
• I did not read the paper about recovering the v coordinate carefully enough and failed to notice the exceptions.
• I did not look up the exact properties of the Montgomery ladder and failed to learn that it conflated zero and infinity.

Simply put, I played with maths I didn’t fully understand. Never again. Monocypher now only uses stuff I either stole from somewhere else (like field arithmetic, taken from ref10), or understand completely (like sliding windows and combs).