Is there an upper limit to plaintext size in XSalsa20Poly1305?

Question

While fiddling with the NaCl implementation in Go, specifically SecretBox, a general crypto question came up after reading the documentation.

Quote:

Package secretbox encrypts and authenticates small messages.

I haven't seen this before. Is there a maximum size? What constitutes as a small message?

I've looked for some paper or documentation explaining that line, and I even went through the source, but I can't find any related information anywhere which explains the noted limit when it comes to the size of the message.

Practically, I just successfully encrypted hundreds of megabytes of data. So, I am really puzzled as to why the docs say it was specified for small messages only. Currently, I am guessing that there is a cryptographic reason for this which I simply may not be able to find.

So – to recap – what I'm asking is: in Salsa20, is there a limit to the message size that is possible? If there is, can you additionally provide a hint where I can find a related reference/paper for me to look at?

Update:

The issue that I opened has been resolved, and the documentation updated to clarify the limits.

Answer 1

As a comment points out, it’s most probably a mistake/error in the docs.

If you look at “What is the PRG period of stream ciphers such as RC4 or Salsa20?”, you’ll find an answer which explicitly points out the limits of Salsa20 (quote)

…Salsa20 used as a stream cipher, it uses a 64-bit block counter and 64-bytes blocks, limiting its capacity to $2^{73}$ bits. After that, the counter would rollover, and thus the output.

That’s a 1180591620717411303424 bytes (around and about 1180591620 Terabyte) maximum size until rollover, which I wouldn’t really call “small”. But that might just be me…

For reference purposes, see the Salsa20 paper (PDF).

EDIT

^{Comment by Eclipse:}
SecretBox uses Poly1305 so could it be something about how they work together?

I also don’t see any reason the use of Poly1305 would limit things. If you – for example – look at RFC 7539: ChaCha20 and Poly1305 for IETF Protocols, you’ll read a usefull hint (on page 20) which – from my point of view – practically excludes Poly1305 as the source of any “small message” limits.

Quote:

…, the ciphertext length field in the construction of the buffer on which Poly1305 runs limits the ciphertext (and hence, the plaintext) size to 2^64 bytes, or sixteen thousand petabytes (18,446,744,073,709,551,616 bytes to be exact).

When you look at page 6 of that RFC, you’ll read that that RFC assumes it’s safe to handle 247,877,906,880 bytes (nearly 256 GB) with Poly1305. So Poly1305 doesn’t really seem to be a limiting factor either which might explain a “small message” comment like that.

All that’s left is a potential limitiation in the implementation itself. If you can’t find “small message” limits in the sourcecode either – which you already checked and confirmed to not exists – an error in the docs is most likely. In the end, the statement …small messages seems to be nothing but a “small” glitch in the docs which causes superfluous confusion where it shouldn’t.

Answer 2

(To clarify the answer in general about why small bounds and why not init/update/finalize streaming, for anyone who doesn't want to bother following the whole discussion about Go in particular on GitHub...)

The cryptography does not impose a meaningful limit:

• XSalsa20 produces up to $2^{64}$ 64-byte blocks, or $2^{70}$ bytes, of output per key per nonce.
• The adversary's probability of success for forgery of a Poly1305 tag is under $8\ell/2^{106}$, where $\ell$ is the maximum number of 16-byte blocks in a message. For example, for messages of up to a megabyte, this is $1/2^{87}$.

(If you processed one 64-byte block of data every nanosecond, it would take centuries to fill $2^{64}$ 64-byte blocks. And although the forgery probability for a single megabyte message is a thousand times that for a single kilobyte message, it likely costs a thousand times as much to attempt a single megabyte forgery as it does to attempt a single kilobyte forgery.)

But there is a limit you need to think about in your protocol: How much memory are you willing to let the adversary waste before you can reject a forgery?

Sensible protocols put small bounds on this. How small is small? It depends on the protocol, but it is almost certainly no more than you want to fit in a single contiguous buffer in memory in your application.

If you don't put a small bound on this, you may be tempted to let your application start processing a stream of input data before you can tell whether to reject it as a forgery or not, as in, e.g., gpg < foo.tgz.gpg | tar zxf -. This is a serious mistake, because you're no longer relying on cryptography to authenticate inputs controlling your application, but instead relying on whatever logic your application might have to authenticate the inputs—which, in many applications like tar that happily execute every command sent to them, is none at all.