Boring crypto that simply works

Vulnerability Disclosures

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

Critical failure of EdDSA checking

Discussion on Reddit.

Corrected in version 2.0.4 and 1.1.1. Affects everything below.

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

uint8_t zero[64] = {0};
if (crypto_check(zero, zero, 0, 0)) {
} else {

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 public key that doesn't make sense in the first place. Still, Mike Pechkin found several bugs in earlier versions of Monocypher, I couldn't dismiss his input out of hand. So I tried Libsodium and TweetNaCL. Libsodium, as expected, rejected the input (it has low order checks). My spidey senses went off when I saw that even TweetNaCl rejected the signature.

So I dug a little deeper, and found the following day that Monocypher accepted the signature even with a genuine public key. At this point, I had a critical vulnerability. The first one since 1.0.0. (There was another one before, also found by Mike Pechkin, but Monocypher wasn't deemed ready for production yet.) I offered Mike his bounty, but he gracefully declined.

Turned out crypto_check() wasn't an easy function to test. Its result is binary (accept or reject), and doesn't give a lot of insight about whatever error may lurk below. Fortunately, it reuse much the same code as crypto_sign(), so there is still little room for error.

Not zero, though.

The error was somewhere in the internal function ge_scalarmult_base(): multiplying the base point by zero yielded 0 instead of 1 (in packed form), which causes the rest of the computation to accept the signature. I was pretty surprised, because that function worked correctly for every other scalar. Only zero (and I suspect, but have not verified, 2^255-19, L, and a couple others).

Searching through the git history revealed that the bug was introduced by an optimisation, where I would perform the scalar multiplication in Montgomery space to speed up the computation by a factor of almost 2. I have yet to determine where the error is exactly.

Blacklist zero and other suspicious scalars could have been tempting, but I don't understand the math behind this problem yet, so I judged the approach unsafe. Instead, I just reverted the optimisation. The fix is available on version 2.0.4 and 1.1.1 (the 1.x.x branch is deprecated, but this was too big to ignore).

The speed of EdDSA is now halved, so I'm not too happy about it. I do plan to re-introduce the optimisation later, but I may need expert advice about how to deal with the edge cases correctly.

Incidentally, Monocypher still accepts non-sensical signatures when the public key is all zero. I was right about low order points. The reason why TweetNaCl didn't accept it was mere chance, because it used a different hash. Toggling the -DED25519_SHA512 flag for monocypher (to replace Blake2 by SHA512 for full Ed25519 compatibility) gives the same results as TweetNaCl, down to the internal buffer. Likewise, TweetNacl behaves the same as Monocypher when we replace SHA-512 by Blake2b.