ChaCha20: change the current API (and recommendations)

This is a tie-together for Cryptography's side of the discussions in https://github.com/google/wycheproof/issues/90 and https://bugs.chromium.org/p/boringssl/issues/detail?id=614.

Status quo

The current ChaCha20 API in Cryptography is defined as follows:

algorithms.ChaCha20(key, nonce)

...where nonce is a bytes of exactly len(nonce) == 16. This means that it contains both the "nonce" and "counter" fields used by ChaCha20, and leaves it to the underlying implementation to determine the appropriate nonce/counter split.

As part of that, the current documentation also encourages uses to fully randomize the nonce input, with os.urandom(16):

https://cryptography.io/en/latest/hazmat/primitives/symmetric-encryption/#cryptography.hazmat.primitives.ciphers.algorithms.ChaCha20

Finally, the API implies that the underlying ChaCha20 implementation implementation is RFC 7539, when the two current underlying implementations (OpenSSL and LibreSSL) are not (due to a 64/64 nonce/ctr split rather than 96/32).

Put together, these three points mean that the current ChaCha20 API's internal implementations are more likely to diverge from RFC 7539 than they otherwise would be: if a user randomly initializes nonce, then the randomly initialized interior counter may be much closer to RFC 7539's block limit than a user might otherwise expect.

I have two proposals for resolving this: one that forces all implementations to behave as if they're RFC 7539 compliant, and another that explicitly separates the API into 64/64 and 96/32 implementations.

Proposal 1

My first proposal is a semi-breaking change. Behaviorally:

The API itself will change, with nonce becoming a 12-byte nonce rather than a 16-byte nonce;
Internally, the ChaCha20 API will initialize the 32-bit counter (to 0) and combine it with the nonce.
Optionally, the API could grow a new counter= argument, which would allow the user to explicitly initialize the counter to a specific value in [0, 2^32).

In effect, this would make the non-RFC-compliant implementations of ChaCha20 behave as if they're compliant within the well-defined parameters of the RFC (i.e., up to 256 GB of enciphering), and would ensure that the majority of users never exceed those parameters (since most users will not need to manually initialize the counter).

Notably, this would be a breaking API change in terms of public API parameters, but a non-breaking change in terms of documented behavior (since it would be a bugfix to enforce compliance with RFC 7539, as documented).

Proposal 2

My second proposal is non-breaking, but requires a documentation correction and a new API for the RFC 7539-compliant version of ChaCha20. Behaviorally:

The existing ChaCha20 API's documentation will be updated to emphasize that it isn't intended to be RFC 7539 compliant. We'd also add test cases to ensure compliance with the 64/64 variant, e.g. at what would be the 32-bit counter overflow point.
We'd add a new ChaCha20RFC API (with a better name than that), which would then support the RFC 7539 variant. This API would then use the pre-existing ChaCha20 API with a fixed 32-bit nonce, forcing all implementations to behave as if they're compliant (at least within the bounds defined by the RFC -- exceeding those bounds will still exhibit divergences).

This would be non-breaking. However, if a little bit of breakage is acceptable, I think combining this with a small change to ChaCha20 to make nonce only 8 bytes (and allow an optional 64-bit counter) would be the best of both worlds: doing so would eliminate any confusion over initial high counter values, and would make the RFC-compliant version's interior use of the non-RFC version slightly more explicit.

See also #8956.

cc @facutuesca

Another bug with the current documentation is it implies you need only avoid reuse on the full 128-bit nonce:

nonce – Should be unique, a nonce. It is critical to never reuse a nonce with a given key. Any reuse of a nonce with the same key compromises the security of every message encrypted with that key. The nonce does not need to be kept secret and may be included with the ciphertext. This must be 128 bits in length. The 128-bit value is a concatenation of 4-byte little-endian counter and the 12-byte nonce (as described in RFC 7539).

Though it's a little ambiguous because first it says the 128-bit thing is the nonce. Then it says the 128-bit thing is a concatenated counter and nonce.

It is not sufficient to simply use unique 128-bit nonces, because the counter will increment and you may collide there. It would be sufficient to say the 96-bit (or 64-bit) nonce portion is unique, but that would forbid AEAD constructions that use a single-block ChaCha20 call with (nonce, 0) to derive the MAC key, and another ChaCha20 call with (nonce, 1...) for the overall encryption. But understanding why that one is safe requires knowing the relationship between lengths and counter values.

RFC 7539 isn’t the only spec that this code needs to be able to support. In particular, Chacha20Poly1305 shows up in SSH (see the documentation at https://github.com/openssh/openssh-portable/blob/master/PROTOCOL.chacha20poly1305 from OpenSSH). That relies on a 64/64 split on the unique nonce vs. counter value, and also relies on being able to initialize the counter explicitly to specific byte string values (like 0 and little-endian 1). So, I’m not sure it is a good idea to enforce a specific split or other constraints on the allowed counter values. The current API leaves this up to the callers, and I think we’d want to maintain that as at least one of the API options.

If you wanted to add a higher-level API which built on this and provided specific splits and automatic counter initialization to simplify things for a caller looking for something like RFC 7539 support, I’d be ok with that, but I would suggest doing it as a very thin layer on the existing API which takes an already constructed 128 bit value.

RFC 7539 isn’t the only spec that this code needs to be able to support. In particular, Chacha20Poly1305 shows up in SSH (see the documentation at https://github.com/openssh/openssh-portable/blob/master/PROTOCOL.chacha20poly1305 from OpenSSH). That relies on a 64/64 split on the unique nonce vs. counter value, and also relies on being able to initialize the counter explicitly to specific byte string values (like 0 and little-endian 1).

Yep, this was a consideration behind the second proposal above: I didn't phrase it especially well, but the idea there would be to retain the 64/64 behavior with the existing ChaCha20 API, and then have an entirely new API (either a class, or a constructor that does the split correctly) that does the RFC-specified variant.

The more general problem here is that Cryptography's various backends don't all agree on which variant they implement :slightly_smiling_face: -- OpenSSL and LibreSSL appear to have intentionally (?) implemented the 64/64 variant, while BoringSSL provides the 96/32 RFC variant.

Being able to specify starting nonce values definitely makes sense. That's a good way to reserve a couple points in the counter space for the MAC key or whatever. The IETF AEAD does that too. It's specifically setting it to random values and relying on wraparound that's incoherent.

pyca / cryptography