Re: [CFRG] XChacha20 counter size

2020-12-25 23:32 GMT+01:00 Loup Vaillant-David <loup@loup-vaillant.fr>:
> Hi, Merry Christmas,
> 
> I've just learned that draft-irtf-cfrg-xchacha-03 specifies a 32-bit
> counter. From what I can see, this is because it leans on the Chacha20
> variant described in RFC 8439.
> 
> This is problematic on two levels:
> 
> - This is a departure from existing implementations. XSalsa20 from
>   NaCl uses a 64-bit counter. XChacha20 in Libsodium also uses a 64-bit
>   counter. In general, all XChacha20 implementations I know of use a
>   64-bit counter.

I don't know about XSalsa20, but DJB's Salsa20 code as distributed with NaCl and from the Salsa20 homepage wraps shortly after overflowing a 32-bit counter, even if it's defined to have a 64-bit counter, so the originalism argument is not that strong.

He declined to acknowledge it as an issue because of the policy at https://nacl.cr.yp.to/valid.html, because he claimed support for counters larger than 32 bits is an incomplete experiment, and because there is an empty file named warning-256gb in the SUPERCOP benchmarks tarball.

https://groups.google.com/g/golang-announce/c/tjyNcJxb2vQ/m/n0NRBziSCAAJ

The Go XChaCha20 implementation will panic if the counter reaches 32 bits, per the draft.

> - A 32-bit counter limits the length of the messages to realistically
>   attainable lengths (256 GiB), thus introducing a new (and avoidable)
>   way to shoot ourselves in the foot.
> 
> If this draft is adopted as is, users could end up vulnerable when they
> switch to a pedantically conformant implementation. I believe we don't
> want that. XChacha20 has 256 bits available for the nonce and counter,
> we should use them all. Shrinking the counter down to 32 bits put end
> users at risk, without giving them any benefit in return.
> 
> My suggestion is the following: instead of leaning on the Chacha20
> variant described in RFC 8439, we should stick to the original
> Chacha20, as designed by DJB.
> 
> ---
> 
> While we're at it, I note that RFC 8439 is slightly at odds with
> existing implementations as well (I know of Libsodium and my own
> Monocypher). Instead of using a genuine 32-bit counter, we initialise
> the Chacha block just like the RFC say we should, then we pretend we
> had a 64-bit counter all along. That way we can use the same core loop
> for all variants: original DJB, IETF, and XChacha20.
> 
> The only difference is what happens when we overflow the 32-bit
> counter. This can happen in two cases:
> 
> - We use RFC 8439, and the message is too long (>256 GiB). This is
>   arguably an error, and the user must make sure it never happens.
> - We use XChacha20, and the message exceed 256 GiB. This should be
>   allowed, to eliminate a dangerous edge case.
> 
> Would it be possible to add an note to RFC 8439, that explicitly allows
> implementations to increment the least significant word of the nonce
> when the counter wraps back to zero?

Please don't. Overlapping ranges make bounds analysis way harder, and most importantly generating the same keystream for (key, nonce, large message) and (key, nonce + 1, message) is unexpected, contradicts the definition of the cipher, and can leak plaintext when sequential nonces are in use. Sequential nonces are a perfectly acceptable and widespread practice, especially with ChaCha20 where the nonce is too small for random nonces, although to be fair I don't know what endianness is most commonly in use.

In fact, if a library implements this behavior in plain ChaCha20, I would report it as a security issue. Either applications never generate messages longer than 256GiB, in which case failing after the overflow would make no difference, or they are insecure if they use sequential nonces in little endian.

If you offer a short-nonce long-counter variant, that's different since 32-bit counter overflow will not increase the application-provided nonce.

> That's a detail, though. My most
> important request remains that XChacha20 use all 64 bits for its
> counter.
> 
> Thank you for your time,
> Loup.
> 
> 
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
> 