[CFRG] [draft-irtf-cfrg-xchacha] Xchacha20 nonce wrap

[Antoine FERRON <[e-mail]>]

Dear crypto researchers and standard writers,

Some chairs members suggested to me that I share the following considerations to this CFRG mailing list, so that all members can discuss this point.
We are seeking great interest in the "XChaCha" IETF draft standard (https://tools.ietf.org/html/draft-irtf-cfrg-xchacha-03). We developed a new "secure cloud" service with client-side encryption. And we have selected the AEAD_XChaCha20_Poly1305 algorithm to encrypt the files chunks. So this algorithm is the root base of the system (https://github.com/bitlogik/guardata/blob/master/guardata/crypto/secretbox2.py#L65). We use libsodium (https://libsodium.gitbook.io)through the pyNaCl wrapper, which implements it (https://github.com/pyca/pynacl/blob/master/src/libsodium/src/libsodium/crypto_aead/xchacha20poly1305/sodium/aead_xchacha20poly1305.c) directly with SecretBox (https://github.com/pyca/pynacl/blob/master/src/libsodium/src/libsodium/crypto_secretbox/xchacha20poly1305/secretbox_xchacha20poly1305.c).
As I went deeper and deeper in the technical details of this matter, mostly to check everything is right and our system follows the standards, I stumbled upon a tiny but recurring issue about the standard (https://www.cryptopp.com/wiki/ChaChaTLS#Sharp_Edges). Indeed since the creation of the Salsa parent cipher, nothing was set forth about what should happen once the maximum nonce value is reached and the next block increments the nonce value. Well, initially the nonce is supposed to start at 0 and reaching the end is not realistic, or at least there are some limitations preventing this. But new usages of the cipher (as yours IETF draft) and larger file size can overpass this, so the issue is resurfacing. The most annoying effect is the fact the behaviour when the nonce wraps, can be different depending of the implementation. That is expected, since no standard are telling about this point. See the pending Crypto++ issue about ChachaTLS, which is fully related : https://github.com/weidai11/cryptopp/issues/790 was actually closed because no one cares : "no one has told what to do".
If I'm correct, using IETF Xchacha20, the nonce wrap can occur after 4x8 32 bits = 4 billions blocks, when the given "remaining 8 byte nonce" is near the maximum value 8x8 = 64 bits minus 1 (or 2) : 0xFFFFFFFFFFFFFFFF.
That means, that with a "random" nonce ending with 0xFFFFFFFFFFFFFFFE, the maximum file size before a nonce wrap happens is 256 GB (4 billion blocks of 64 bytes).

What are you personal opinions on this matter?
What do you recommend to enforce about this topic?

I can see different solutions :
Limiting the maximum file size when using XChacha20 to 256 GB, thus eliminating the issue possibility. That's just restricting the standard use, as it is supposed to accommodate "unlimited" size (2^64) with its extended nonce.

Accepting a nonce wrap of the 12 bytes counter, so let the maximum file size to "64 bits" (2^64-1). Observing the actual implementations, this would need to clarify what is the expected behaviour when the nonce wrapping happens :
just "cycle" it back to 0, or

increase the first word of the nonce, and rekey before resetting the nonce

The libsodium library (and also Botan) is doing the latest, meaning it :
defines the maximum file size for Xchacha20 to 64 bits long : crypto_aead_xchacha20poly1305_ietf_MESSAGEBYTES_MAX is 2^64-1-MacSz

changes the other nonce part when the 12 bytes internal nonce is back to 0.

As explained in the Crypto++ issue about this, I'm not a fan of the "key" nonce increment, as this is dangerous. This is described as a "wild memory write" in the Crypto++ issue. For example if anyone is using a previous used nonce set and this new incremented nonce will be unknown by the system, so it can reuse the same nonce as the one incremented. The risk is very low, since the nonce has an extended size, it is hard to track set of used nonce, and mostly used with a random generator. One can also just use incremented nonce as a method to prevent nonce reuse, and this automatic increment will screw everything up with very large files.

We would be grateful if the current IETF proposal could be updated with some details about this matter. Whatever the choice, distinctive and clear instructions are better that nothing, else this leads to implementations divergence, as this is already the case for existing affiliated standards. Any limitations or clarification are welcome, else people are doing "free" things which can be dangerous in terms of security. We thank you for your effort and time into standardising this, let us know your opinion.
Regards,
_____________________________________
Antoine FERRON
Président — BitLogiK

bitlogik.fr (https://bitlogik.fr) — PGP Key ID#22F95B31 (https://pgp.key-server.io/0xE353957C22F95B31)