3
$\begingroup$

libsodium documentation says that XChaCha20-Poly1305 can encrypt a message of arbitrary size.

However, the only specification available (still a draft) explains that under the hood the IETF version of ChaCha20-Poly1305 is used (in combination with HChaCha20 for key derivation), which implies at the very least a hard limit of 256GB because of the 32 bit counter.

Who is right, and how large can a message be at most to be safely encrypted with XChaCha20-Poly1305?

And what about the authenticated data?

$\endgroup$
2
$\begingroup$

You should email the libsodium maintainers and the internet-draft author and ask them to talk to each other to work out what they mean, and to clearly document the limits in the internet-draft. (They sometimes post here but not often.)

In principle, XChaCha provides $2^{256}$ 512-bit blocks of output under a single key, indexed by a 256-bit input. The only question is how they are carved up for messages vs. blocks within a message.

  • For the XSalsa20 stream cipher, the message number is 192 bits, and the block number is the remaining 64 bits, so the theoretical limit on the number of blocks per message is $2^{64}$, or $2^{70}$ bytes.
  • For the Salsa20 stream cipher as in eSTREAM and as in NaCl, and for the related ChaCha stream cipher, the message number is 64 bits and the block number is the remaining 64 bits, so again the limit on blocks per message is $2^{64}$.
  • For the IETF ChaCha stream cipher of RFC 7539, the message number is 96 bits and the block number is 32 bits, so messages are limited to 256 GB.
  • The current XChaCha-Poly1305 internet-draft, draft-arciszewski-xchacha-03, is defined in terms of the IETF ChaCha-Poly1305 AEAD of RFC 7539 as a subroutine, in §2, p. 3, but it follows the XSalsa20 API, so the message number—which is a parameter to the API—is 192 bits, but the block number—which is managed internally by the API—is 32 bits; the remaining 32 bits of the internal ChaCha input are fixed to zero.
  • In what libsodium seems to implement for crypto_aead_xchacha20poly1305_ietf, according to the XChaCha20-Poly1305 construction page (archived 2019-05-30) and the AEAD limitations table (archived 2018-11-07), the message number is 192 bits and the block number is 64 bits, like XSalsa20.
    • If the byte order of the block number is chosen appropriately, this should be compatible with draft-arciszewski-xchacha-03 in the sense that it can correctly implement any protocol following the internet-draft, but it also allows much larger messages that are not allowed by the internet-draft.
    • It is also possible that the block number encoding is mismatched so that libsodium's crypto_aead_xchacha20poly1305_ietf is incompatible with draft-arciszewski-xchacha-03—I haven't checked.

All that said, the distinction between a 32-bit block number and a 64-bit block number is essentially academic: the largest message any implementation is willing to receive is the largest amount of memory that an adversary waste in a denial of service before you can drop the message on the floor. It is hard to imagine applications for which this amount should reasonably be beyond a few megabytes, let alone 256 GB—larger messages can simply be broken up into smaller pieces at negligible additional cost since the per-piece overhead is at most a few dozen bytes, even if you include the 192-bit nonce and some formatting metadata.

$\endgroup$
  • $\begingroup$ I think you're significantly underestimating the size of messages some users may want to send and receive, especially if "send" actually means e.g. "write to a backup disk" and "receive" means "restore the backup". $\endgroup$ – Ilmari Karonen Jun 9 at 16:10
  • $\begingroup$ @IlmariKaronen Not at all. They should be broken up into smaller pieces. $\endgroup$ – Squeamish Ossifrage Jun 9 at 16:11
  • $\begingroup$ Arguably so, yes, but only because commonly used encryption modes tend to have low message size limits. There is no other reason why the use case I describe should need a chunked encryption scheme, and implementing one securely is nontrivial. (Of course, in practice most file encryption software seems to use homegrown schemes based on e.g. CBC+HMAC, if they do message authentication at all. But it would be nice if they could use standard AEAD modes instead.) $\endgroup$ – Ilmari Karonen Jun 9 at 16:18
  • $\begingroup$ @IlmariKaronen No, it's bad idea to do things in bulk like that because you can't drop forgeries on the floor sooner, so you're setting yourself up for denial of service of the receiver. For backups you probably also want deduplication and replication by erasure coding, for which you'll want to break things into chunks anyway. Breaking a sequential stream like this into chunks is not hard: e.g., use the chunk sequence number as the nonce, and never reuse a key for different streams (or incorporate a stream number into the nonce). $\endgroup$ – Squeamish Ossifrage Jun 9 at 16:36
  • $\begingroup$ Denial of service is not (much of) an issue if you don't accept unsolicited messages to begin with. For the backup file encryption example, sure, a corrupted backup file can result in the restorer wasting some minutes or hours decrypting it only to be told that it's invalid. But at that point the major issue is that the backup has somehow been corrupted, not that the corruption was only detected at the end of the decryption process, rather than, say, only 10% of the way through it (which cannot be guaranteed, anyway). $\endgroup$ – Ilmari Karonen Jun 9 at 17:18
2
$\begingroup$

XChaCha20-Poly1305 is NOT the same as IETF ChaCha20-Poly1305. IETF ChaCha20 uses a 96-bit nonce and 32-bit counter, XChaCha20 uses a 192-bit nonce and 64-bit counter. The 64-bit counter lets it encrypt an absolutely staggering amount of data (1 Zettabyte) in a message. For all practical purposes there's no limit, since no one is going to be sending the entirety of the data of all the worlds computers in one message.

Therefore Libsodium's documentation is correct about XChaCha20. The IETF's documentation is correct about the IETF ChaCha20, but that's not what you're asking.

Poly1305 does not restrict the maximum size of the message being authenticated.

$\endgroup$
  • $\begingroup$ Where is the 64 bit counter defined? The draft spec of XChaCha20-Poly1305 in section 2.3 defines XChaCha20 as HChaCha20 (KDF) + IETF ChaCha20, and the latter has a 32 bit counter. $\endgroup$ – SquareRootOfTwentyThree Jun 9 at 6:13
  • $\begingroup$ libsodium's documentation is correct according to what? Correct documentation of its own implementation? What is your authority for the claim that ‘XChaCha20 uses a 192-bit nonce and a 64-bit counter’? Please cite sources. $\endgroup$ – Squeamish Ossifrage Jun 9 at 15:23
  • $\begingroup$ @SqueamishOssifrage It is correct according to section 2.1 of the draft spec already linked, the XSalsa paper, and the underlying mathematics of the overall construction. The limit of 64-bits on the counter is due to the block counter in the Salsa20 algorithm; ChaCha20 can be substituted for Salsa20 which means all of the basic rules carry over. $\endgroup$ – Kittoes0124 Sep 22 at 10:36
  • $\begingroup$ @Kittoes0124 §2.1 of the internet-draft is about the nonce, not about the block counter. The proposed XChaCha is not a direct analogue of XSalsa20 because it is limited to $2^{32}$ blocks per message, not $2^{64}$ blocks per message as XSalsa20 is. This is because it is defined in terms of IETF ChaCha which is limited to $2^{32}$ blocks per message (rather than djb ChaCha which allows up to $2^{64}$ blocks per message), as you can see in §2.3. $\endgroup$ – Squeamish Ossifrage Sep 22 at 15:07
  • 1
    $\begingroup$ @Kittoes0124 It's true the XSalsa20 paper has the only reasonable construction for key derivation used by anything one might call ‘XChaCha’, as libsodium and the internet-draft do. But ${>}2^{32}$-block messages aren't really reasonable, and IETF ChaCha is widely used. (By the way, if yer gonna be a stickler about djb nomenclature, consider keeping the 20's straight: ChaCha is to Salsa20 as ChaCha20 is to Salsa20/20; in ChaCha<r> or Salsa20/<r>, <r> is the number of rounds, while plain ChaCha and Salsa20 are the stream cipher families. ChaCha8 and Salsa20/12 also see some use in the world.) $\endgroup$ – Squeamish Ossifrage Sep 24 at 1:38
2
$\begingroup$

All the responses above are correct.

Libsodium (and Libhydrogen 0.x, that introduced this construction) uses a 64 bit block counter, effectively allowing an arbitrary large message to be encrypted under a given (key, nonce).

Arciszewski's draft restricts that counter to 32 bit, because this is easier to implement on top of an existing ChaCha20-IETF implementation (vs the original ChaCha20 design).

The former is compatible with the latter.

$\endgroup$
  • $\begingroup$ How can they be compatible to each other if they don't behave in the same way for plaintexts larger than 256GB? $\endgroup$ – SquareRootOfTwentyThree Jun 11 at 19:14
  • 2
    $\begingroup$ As written above, the former is compatible with the latter. The reverse is not true. That being said, the draft is... a draft, and is still subject to changes. If supporting a 64 bit counter happens to be something applications may actually need, this can be suggested on the draft's github repository: github.com/bikeshedders/xchacha-rfc $\endgroup$ – Frank Denis Jun 11 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.