# 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:

- Chose a public key
`PK`

to impersonate. - Choose a message
`msg`

of size`msg_size`

to forge. - Let
`zero`

be an all zeroes 64-byte buffer. - Try
`crypto_check(zero, PK, msg, msg_size)`

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