Re: [CFRG] XChacha20 counter size

[Taylor R Campbell <[e-mail]>]

> Date: Fri, 25 Dec 2020 23:32:27 +0100
> From: Loup Vaillant-David <[e-mail]>
> 
> - 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.

An application that accepts 256 GiB messages is an application that's
already prepared to shoot itself in the foot.  Individual messages
shouldn't be that long -- especially messages transmitted over the
internet.  You should break large messages into pieces of reasonable
size for separate authenticated encryption.

Exactly what is `reasonable' varies from application to application,
depending on how much memory they can tolerate an adversary wasting
before rejecting a forgery, but >256 GiB is definitely unreasonable.

The NaCl authors recommend limiting messages, e.g. to 4096 bytes as is
the limit in the NaCl tests: https://nacl.cr.yp.to/valid.html
https://groups.google.com/g/boring-crypto/c/BpUmNMXKMYQ/m/EEwAIeQdjacJ

This is also relevant for authenticators based on universal hashes
like AES-GCM and ChaCha/Poly1305, whose security depends linearly on
the _maximum_ message length (not just the total amount of data):
Accept a single 256 GiB message, and the number of messages you can
safely handle -- even if all the others are tiny -- dramatically drops
compared to an application limited to 2^14 bytes per message like TLS.

> - 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.

Many Salsa20 and ChaCha implementations, including a number in
SUPERCOP and the implementations named amd64-xmm5 and amd64-xmm6
published by the designer (https://cr.yp.to/snuffle.html) silently
repeat the key stream if you try to use them for more than 2^32
blocks.