ChaCha20-Poly1305 with long nonces – OpenSSL CVE-2019-1543
openssl.org
openssl.org
We found this through invariant fuzzing @ronomon/crypto-async (https://github.com/ronomon/crypto-async), which depends on OpenSSL.
The invariant fuzzing simply does a few thousand random roundtrips (encrypt, decrypt) through all the OpenSSL AEAD ciphers we want to support, corrupting any of {key, iv, ciphertext, aad, tag} and asserting that the authentication guarantee is maintained by the AEAD cipher.
In addition to the CVE, this quickly found a few small unrelated issues:
EVP_CTRL_AEAD_SET_TAG fails for OCB [1]
AEAD: EVP_CIPHER_CTX_iv_length is oblivious to EVP_CTRL_AEAD_SET_IVLEN [2]
EVP_CipherUpdate() setting AAD for AES-256-OCB returns incorrect `outlen` [3]
[1] https://github.com/openssl/openssl/issues/8331
Couldn't find anything about LibreSSL, so I guess it's not affected?
In the first place, support for longer-than-default nonces should never have been introduced by OpenSSL. But far worse, all along there was simply no implementation behind it for ChaCha20-Poly1305. The first 4 bytes were simply discarded.
The bug isn't OpenSSL throwing bytes away, the bug is OpenSSL acting as-if anything other than 96 bit nonces are acceptable.
It seems to me that using a long, explicit, random nonce is always preferable to using a short, implicit, sequential nonce. Are there any systems that really can't accommodate this?
The best would be to have a strong random nonce and a counter, or some combination of these, for example 64 bit counter appended to a 192 bit random vector.
Even just a 64 bit sequential counter would last almost 600 years at 10^9 encryption operations per second.