Re: [CFRG] XChacha20 counter size

[Loup Vaillant-David <[e-mail]>]

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

Oh. I had no idea the implementation deviated from the paper like that.
The paper explicitly says the maximum length of Salsa20 is 2^70 bytes,
and I naively assumed the author would respect his own specs.

TweetNaCl at least seems to have a proper 64-bit counter.


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

A nice thing to do. C however tends not to be as fortunate (no standard
way to panic, especially in embedded environments).


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

There is only 2 ways this can happen.

- The user exceeds 2^32 blocks. If you don't spill over the next word,
  the stream will still be repeated.

- The user starts the counter at a non-zero value, and expect overflow
  to wrap around. In this case, yes, you could have a collision with
  the next nonce, if the next message starts its own counter at zero.
  While theoretically possible, I don't see who would come up with
such 
  a peculiar design. It's not like someone who fails to notice that
  messages lengths should be limited, it's' actively asking for
  trouble.


> In fact, if a library implements this behavior in plain ChaCha20, I
> would report it as a security issue.

I thought Libsodium implemented this behaviour, but further tests
showed me that it actually detects the overflow and panics.

Monocypher definitely implements this behaviour, but since I have no
portable way to panic (Monocypher sticks to strictly conformant C99
with no dependency), the best thing I can do is make sure the manual
tell users not to overload that counter.

I could possibly have a proper 32-bit counter, but it wouldn't be any
better: it would wrap around instead of spilling over the next word,
and still trigger an insecure stream reuse.


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

Are you asserting that the only correct behaviour upon 32-bit overflow
is to panic? I wouldn't disagree, but alas, not everyone can afford it.


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

By default, I do. But that's only a default. I *also* offer an IETF
interface, and pray my users won't overflow my not-exactly-32-bit
counter.

Loup.