XChaCha20 unnecessarily limits keystream to 256gb

[jpdoyle]

XChaCha20 can support a full 64-bit keystream for any given nonce, so the MAX_BLOCKS limit of 96-bit-nonce ChaCha20 shouldn't apply.

Technically this wouldn't comply with https://tools.ietf.org/html/draft-arciszewski-xchacha-03 but a cursory glance through the counter handling code makes me think that nothing would actually go wrong -- everything is done with a 64bit counter and split into two 32bit words in the backends.

As a side note, I'm preeeeetty sure that in this implementation 32-bit counter "overflows" would roll over to the next nonce instead of actually leading to nonce reuse. Not great, but #64 may not have been as critical as it looked.

[tarcieri]

Unfortunately this is one of those things where XChaCha20 is a non-standard construction with no spec, and thus no clear guidance around data volume limits.

Internally the counters are 64-bit, but all implementations presently respect the data volume limits of the IETF construction. The former is largely the result of legacy: the initial implementation of the chacha20 crate did not support the IETF construction at all, only the original legacy "djb" variant, and it was subsequently modified to support both, but both (or rather, all variants including XChaCha20) presently respect the IETF-suggested data volume limits.

RFC8439 Section 2.3. says the following:

Note also that the original ChaCha had a 64-bit nonce and 64-bit
block count. We have modified this here to be more consistent with
recommendations in Section 3.2 of [RFC5116]. This limits the use of
a single (key,nonce) combination to 2^32 blocks, or 256 GB, but that
is enough for most uses.

The mention of RFC5116 Section 3.2 mostly appears to be in regard to the use of a 96-bit nonce, and the choice of a 32-bit counter the effect of the modified 96-bit nonce (over the original "djb" 64-bit nonce) being to supply 32-bits of leading counter value, effectively splitting the 64-bit counter in half.

In XChaCha20, that upper (in terms of ChaCha core inputs) 32-bit counter value (i.e. upper half of the 64-bit counter) is always initialized to 0 (by way of the first 4 bytes of the non-extended nonce), which I think is what you're getting at here.

So this is one of those things where I could go either way, and for lack of a true spec it's unclear which way to go. https://tools.ietf.org/html/draft-arciszewski-xchacha-03 appears to be assuming that XChaCha20 implementations will be composed in terms of the IETF implementation at its core, with its prescriptive use of a 32-bit counter value. Indeed that's how the chacha20 crate is implemented now, although it wouldn't be too hard to remove that restriction as it still uses a 64-bit counter.

In terms of parity with other implementations, libsodium's AEAD limitations documentation gives the separate data volume limits you're suggesting, with a limit of 2^64 for XChaCha20.

[jpdoyle]

My understanding of the mess around 256gb was that:

• chacha20 originally had a 64-bit nonce, which is rather small
• the only variant which would reasonably have only a 32bit counter limit is the ietf 96-bit nonce version (since the upper 32 bits of the "counter" spot were used for the extra nonce)
• most sensible implementations still used the 64-bit counter as a counter, meaning you would start using iv+1 after 256gb if you violated the spec
• one particularly birdbrained asm implementation used a 32bit int directly for the counter, leading to a looping keystream instead of an unexpected nonce change, and the author did not handle disclosing this well

Enforcing the 32-bit counter for 96-bit chacha20 is totally sensible to catch dangerous misuse. However, I'm pretty sure the implementations we have here don't have the looping-keystream problem, and for things like 64-bit-nonce chacha20 and xchacha20 it would be nice to be able to encrypt multi-terabyte tarballs.

[tarcieri]

In absence of an XChaCha20 RFC providing explicit advice, I'm weakly in favor of aligning with the implementation in libsodium, which uses a 64-bit counter for XChaCha20.

[jpdoyle]

Forgive me if this is off-topic, but do you know what the warning-4gb file in https://github.com/floodyberry/supercop/blob/master/crypto_stream/chacha20/krovetz/vec128/warning-4gb is supposed to signify? No worries if you don't know and/or don't want to speculate about the intentions of Mr "4K is enough plaintext for anyone", but it's even more obscure than warning-256gb.

[tarcieri]

No idea, nor does it appear to be references anywhere in the code contents.

[jpdoyle]

The code seems to be using unsigned long long, and the looping-at-256gb problem comes from:

#define INC(x)    _mm256_add_epi32(x, _mm256_set_epi32(0,0,0,2,0,0,0,2))

so idk what the 4gb problem could really be unless sizeof(long long) == 4.

Regardless, the implementation here doesn't seem to have that problem, since counter management is outside the vectorized backend. I have some time available this week -- I'll try to get a PR with some test cases ready for review.