Monocypher

Boring crypto that simply works

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:

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

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 a 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 offered Mike his bounty, which he gracefully declined.

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.

How did I fail to notice it?

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).

Update august 2019: Pwnie Award

From the Pwnie Awards.

Monocypher Super-Complicated Incredibly Hard To Exploit EdDSA Vulnerability Credit: Mike Pechkin

Elliptic curve Digital signature forgeries are fun to read about. You’ve got your integer lattices, your BKZ basis reductions, your Fourier-assisted search algorithms; it’s pretty much all there.

And sometimes you can just pass all zeroes as your signature.

Don’t use Monocypher, is what we’re saying.

Don't mess with maths you don't understand, is what I've learned. :-)