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

Hi,

See also this fairly recent thread. It doesn't discusses the nonce, but
it does discuss the counter fairly extensively:
https://mailarchive.ietf.org/arch/msg/cfrg/gjUrRYLw7DLzZQgxFbU5w0B7EIE/

Note that several (at least 2) crypto libraries, including Libsodium,
support all 3 flavours of Chacha20:

- DJB original: 64-bit counter,  64-bit nonce
- RFC 8439    : 32-bit counter,  96-bit nonce
- XChacha20   : 64-bit counter, 192-bit nonce

Libsodium specifically allows the 64-bit counter to wrap around upon
overflow. It does *not* allow the 32-bit counter to do the same (it
panics instead). This allows it to implement all 3 flavours of Chacha20
with the same core code (DJB original).

My own Monocypher behaves the same as Libsodium, but since portability
requirements prevents it from panicking, overflowing the 32-bit counter
causes a nonce increment instead (which is dangerous, so the manual
warns users not to overflow that counter).

Note that some implementations, most notably from SUPERCOP, implement
DJB original with only a 32-bit counter (they don't increment the most
significant word of the counter when the least significant one
overflows). I believe this behaviour is *incorrect*, even though it
happens only with huge messages.

In its current form, the XChacha20 draft leans on RFC 8439, which uses
a 32-bit counter, thus limiting messages to 256GiB. Any bigger seems to
be undefined behaviour as far as the standard is concerned. Not ideal
in my opinion.

---

One final though. This is my personal opinion, which I think mirrors
DJB's:
https://mailarchive.ietf.org/arch/msg/cfrg/aSSYF0lxGtGJyNXTYSpz_0cs4Ns/

XChacha20 is a low level primitive, and AEAD_XChaCha20_Poly1305 is a
low-level construction. They are not meant to be used directly, they'll
always be part of some bigger protocol. As such, I believe they should
be maximally flexible, if only to mitigate potential misuses at the
protocol level.

At the same time, protocol designers should acknowledge that such huge
messages are a bad idea for a number of reasons (it's harder to test,
incorrect implementations do exists…). Protocols should limit message
length to much shorter lengths, like a few dozens KiB, or perhaps even
a single network packet's size, depending on the use case.

The fact that protocol designers should not rely on huge message is not
an excuse for primitive implementers for not correctly supporting them.
Some protocols *will* make the mistake, we don't want to destroy all
security when they do.

The fact that primitive implementers behave correctly on huge messages
is not an excuse for protocol designers to rely on this. Some primitive
implementations *will* fail to support huge messages, we don't want
their limitations to result in an insecure system.

This XChacha20 RFC draft describes a primitive. As such, it should
support huge message sizes, even though (i) some implementations don't,
and (ii) protocols should never rely on that. In my opinion.

Loup.

On Thu, 2021-01-28 at 18:20 +0100, Antoine FERRON wrote:
> 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.
> 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. We use libsodium through the pyNaCl wrapper,
> which implements it directly with SecretBox.
> 
> 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. 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 — PGP Key ID#22F95B31
> 
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg