Subject: [CFRG] XChacha20 counter size

From: Loup Vaillant-David <[email-masked]>
Date: Fri, 25 Dec 2020 23:32:27 +0100

Hi, Merry Christmas,

I've just learned that draft-irtf-cfrg-xchacha-03 specifies a 32-bit
counter. From what I can see, this is because it leans on the Chacha20
variant described in RFC 8439.

This is problematic on two levels:

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

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

If this draft is adopted as is, users could end up vulnerable when they
switch to a pedantically conformant implementation. I believe we don't
want that. XChacha20 has 256 bits available for the nonce and counter,
we should use them all. Shrinking the counter down to 32 bits put end
users at risk, without giving them any benefit in return.

My suggestion is the following: instead of leaning on the Chacha20
variant described in RFC 8439, we should stick to the original
Chacha20, as designed by DJB.

---

While we're at it, I note that RFC 8439 is slightly at odds with
existing implementations as well (I know of Libsodium and my own
Monocypher). Instead of using a genuine 32-bit counter, we initialise
the Chacha block just like the RFC say we should, then we pretend we
had a 64-bit counter all along. That way we can use the same core loop
for all variants: original DJB, IETF, and XChacha20.

The only difference is what happens when we overflow the 32-bit
counter. This can happen in two cases:

- We use RFC 8439, and the message is too long (>256 GiB). This is
  arguably an error, and the user must make sure it never happens.
- We use XChacha20, and the message exceed 256 GiB. This should be
  allowed, to eliminate a dangerous edge case.

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? That's a detail, though. My most
important request remains that XChacha20 use all 64 bits for its
counter.

Thank you for your time,
Loup.

---

From: Taylor R Campbell <[email-masked]>
Date: Fri, 25 Dec 2020 23:36:59 +0000

> Date: Fri, 25 Dec 2020 23:32:27 +0100
> From: Loup Vaillant-David <[email-masked]>
> 

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.

>   counter. In general, all XChacha20 implementations I know of use a

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.

---

From: "Filippo Valsorda" <[email-masked]>
Date: Sat, 26 Dec 2020 00:58:52 +0100

>   counter. In general, all XChacha20 implementations I know of use a

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.

He declined to acknowledge it as an issue because of the policy at https://nacl.cr.yp.to/valid.html, because he claimed support for counters larger than 32 bits is an incomplete experiment, and because there is an empty file named warning-256gb in the SUPERCOP benchmarks tarball.

https://groups.google.com/g/golang-announce/c/tjyNcJxb2vQ/m/n0NRBziSCAAJ

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

> 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. Sequential nonces are a perfectly acceptable and widespread practice, especially with ChaCha20 where the nonce is too small for random nonces, although to be fair I don't know what endianness is most commonly in use.

In fact, if a library implements this behavior in plain ChaCha20, I would report it as a security issue. 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.

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

> That's a detail, though. My most
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Scott Arciszewski <[email-masked]>
Date: Fri, 25 Dec 2020 19:10:41 -0500

On Fri, Dec 25, 2020 at 6:59 PM Filippo Valsorda <[email-masked]>
wrote:

> 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.
>
> He declined to acknowledge it as an issue because of the policy at
> https://nacl.cr.yp.to/valid.html, because he claimed support for counters
> larger than 32 bits is an incomplete experiment, and because there is an
> empty file named warning-256gb in the SUPERCOP benchmarks tarball.
>
> 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.
> Sequential nonces are a perfectly acceptable and widespread practice,
> especially with ChaCha20 where the nonce is too small for random nonces,
> although to be fair I don't know what endianness is most commonly in use.
>
> In fact, if a library implements this behavior in plain ChaCha20, I would
> report it as a security issue. 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.
>
> If you offer a short-nonce long-counter variant, that's different since
> 32-bit counter overflow will not increase the application-provided nonce.
>

 As the author of the XChaCha RFC draft, I view making XChaCha20-Poly1305
incompatible with the IETF's ChaCha20-Poly1305 a non-goal.

---

From: Loup Vaillant-David <[email-masked]>
Date: Sat, 26 Dec 2020 01:22:12 +0100

> size for separate authenticated encryption.

I'm aware. And if I were to design even a file encryption system, I
would break up that file in chunks so that the application can process
each chunk with very little RAM, and commit the plaintext to disk only
when the chunk is only fully processed.

Yes, properly designed applications would never allow that. My problem
here is *improperly* designed applications. I don't want to see them
fail too badly.

> safely handle -- even if all the others are tiny -- dramatically
> drops compared to an application limited to 2^14 bytes per message
> like TLS.

Oh. I didn't know. I'll study those limits in more detail, thanks.

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

Okay.

Loup.

---

From: Loup Vaillant-David <[email-masked]>
Date: Sat, 26 Dec 2020 02:55:39 +0100

> 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

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.

---

From: Loup Vaillant-David <[email-masked]>
Date: Sat, 26 Dec 2020 13:03:04 +0100

> As the author of the XChaCha RFC draft, I view making XChaCha20-
> Poly1305 incompatible with the IETF's ChaCha20-Poly1305 a non-goal.

Understand that my proposal *is* compatible.

On section 2.3.1 of your draft, you specify the following pseudocode:

    xchacha20_encrypt(key, nonce, plaintext, blk_ctr = 0):
        subkey = hchacha20(key, nonce[0:15])
        chacha20_nonce = "\x00\x00\x00\x00" + nonce[16:23]

        return chacha20_encrypt(subkey, chacha20_nonce,
                                plaintext, blk_ctr)

The only difference between that and Libsodium is what happens when the
message exceeds >256GiB. A use case that as far as I understand RFC
8439 does not define. Implementations have 3 realistic choices when
dealing with such undefined behaviour:

1. Wrap the counter back to zero, and trigger an insecure stream reuse.
   This is what happens when we naively implement XChacha20 on top of
  
RFC 8439. This would disclose the authentication key, one of the
  
worst vulnerability possible.

2. Panic, crash, or report an error. This is typical of misuse aware
   libraries. I have no problem with this behaviour. It's a bit
   limiting, but at least it's secure.

3. Increment the next word, currently occupied by the nonce. This is
   what naturally happens when we derive XChacha20 from DJB's Chacha20.
   As much as we may disapprove of gigantic messages, this one at least
   does not break all security, and is a nice alternative for libraries
   who cannot (or will not) report an error.

I don't want incompatibility with RFC 8439. All I'm asking here is that
we disallow (1), and allow (3).

Loup.

---

From: Loup Vaillant-David <[email-masked]>
Date: Sat, 26 Dec 2020 20:59:21 +0100

> drops compared to an application limited to 2^14 bytes per message

I did some digging, and in the case of Poly1305 as used in RFC 8439,
the number of messages is irrelevant. Only their maximum length
matters. Security does *not* drop as you send more messages. You can
send as many messages as you want.

I speculate (but don't know) that it might be because unlike GCM, the
secret multiplier is not reused across messages. (AES GCM could have
done the same, but it would have meant computing 2 additional blocks
per message instead of just one.)

The security bounds given by DJB's Poly1305 paper say that it was
designed this way specifically to preserve security as we send more
messages. Only message length matters. This is shown again in the
current AEAD limits draft:

   v = number of attempts
   p = target adversary attack probability
   l = maximum message length (in blocks)
   u = number of users or keys (multi-key attack)

   v <= (p * 2^103) / (l * u)

The biggest possible messages with a 64-bit counter would be 2^68
blocks (we have 4 Poly1305 blocks per Chacha20 block). So:

   v <= (p * 2^103) / (2^68 * u)
   v <= (p * 2^35) / u

That's the theoretical limit, though.  One does not simply encrypt 2^70
bytes in one block (my laptop barely exceeds 2^32 bytes per second).
More realistic (yet unreasonable) length would be in the Terabyte
range. With 8TiB, we'd have 2^43 bytes, or 2^39 blocks:

   v <= (p * 2^103) / (2^39 * u)
   v <= (p * 2^64) / u

Inadvisable for sure, but not broken either. Stream repetition would be
many orders of magnitude worse. In my opinion, the fact that short
messages are better does not justify breaking all security for long
messages. I'd sooner specify that applications "MUST" crash if the
input message is bigger than some threshold.

Loup.

---

From: Taylor R Campbell <[email-masked]>
Date: Sat, 26 Dec 2020 21:29:41 +0000

> Date: Sat, 26 Dec 2020 20:59:21 +0100

The probability of each forgery attempt's success _independently_ is
bounded by 8*floor(L/16)/2^106, where L is the maximum message length.

If the adversary makes q forgery attempts, then the probability of
succeeding at _any_ forgery is bounded by q*8*floor(L/16)/2^106.

Note that both the number of forgery attempts _and_ the maximum
message length figure into this bound.

References:
https://cr.yp.to/highspeed/naclcrypto-20090310.pdf#page=30
https://eprint.iacr.org/2014/613.pdf#page=4

> per message instead of just one.)

ChaCha/Poly1305 and AES-GCM are no different in this respect: for
fixed number of messages and total bytes encrypted, the forgery
probability is proportional to q/L for both of them, with a different
constant factor arising from differences in Poly1305 and GHASH.

Using a message sequence number as the nonce so you can quickly reject
outdated message numbers mitigates the issue for ChaCha/Poly1305, for
the reason you describe.  But that's not as relevant for XChaCha,
which is meant for applications where you may not have a reliable
message sequence number.

They also do scale differently in the number messages and total bytes:
AES-GCM is quadratic where ChaCha/Poly1305 is linear, because AES-GCM
is held back by AES as a PRP.  I attempted to sketch the qualitative
differences in this table in the Daence paper:

https://eprint.iacr.org/2020/067.pdf#page=5
source code: https://github.com/riastradh/daence/blob/master/adv.py

(Daence guarantees the adversary's advantage is below 1/2^32 per key
as long as you process at most 2^52 messages of at most 2^38 bytes
under each key, even if you manage to attain _both_ limits at the same
time for a single key.  I chose this so the usage limits wouldn't have
to be explained by a complicated series of tables and prose like
AES-GCM-SIV's <https://tools.ietf.org/html/rfc8452#page-12>.)

> In my opinion, the fact that short messages are better does not
> justify breaking all security for long messages. I'd sooner specify
> that applications "MUST" crash if the input message is bigger than
> some threshold.

No objection to making the XChaCha draft clearer about what the hard
limit is.  I am a big fan of clearly articulated usage limits.

---

From: Loup Vaillant-David <[email-masked]>
Date: Sat, 26 Dec 2020 23:38:41 +0100

The facts you lay out seem to agree with me, yet your wording suggests
that you don't...

> bounded by 8*floor(L/16)/2^106, where L is the maximum message

Yes it is.

> succeeding at _any_ forgery is bounded by q*8*floor(L/16)/2^106.

Of course. With q attempts chances of success are multiplied by q.

> message length figure into this bound.

I noticed that they do. I will note however that the number of messages
do not appear in the formula. You were saying in your first message
that the number of sent messages matter (unless it was the number of
*received* messages?):

""" 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 bound however suggest that it doesn't. Message length and number
of messages don't compete. Only the maximum message length matters.

> constant factor arising from differences in Poly1305 and GHASH.

Ah, my speculation was wrong, then. Thanks.

But I have to disagree about "total bytes encrypted". It's "maximum
message length". It doesn't matter whether you send 1 message of 4KiB
or 1 million, forgery probability will still be proportional to q/2^12.

> Using a message sequence number as the nonce so you can quickly
> reject outdated message numbers mitigates the issue for
> ChaCha/Poly1305, for the reason you describe.  But that's not as
> relevant for XChaCha, which is meant for applications where you may
> not have a reliable message sequence number.

Wait a minute, what do sequence numbers have to do with anything? All
the sources I have seen so far do not mention the relevance of
rejecting outdated nonces.

> I attempted to sketch the qualitative

Ah, *there* is the crucial detail you didn't repeat here:

""" We suppose for the sake of presentation on two-dimensional paper
""" that the adversary can attempt about a million times as many
""" forgeries as there are legitimate messages encrypted by the user.

This assumes that the number of attempts an adversary can make is
directly proportional to the number of sent messages. I disagree with
this assumption, at least to some extent. In real systems, the number
of forgery attempts an adversary can make is equal to the number of
messages the *recipient* can (and will) attempt to authenticate.

 +---------------------+--------------------+------------------+
 | number of messages  | number of messages | Max number of    |
 | Alice sends         | Bob can receive    | forgery attempts |
 +=====================+====================+==================+
 |        10           |        100         |       100        |
 +---------------------+--------------------+------------------+
 |        90           |        100         |    100 again     |
 +---------------------+--------------------+------------------+
 |     1 million       |        100         |    still 100     |
 +---------------------+--------------------+------------------+

(In the last line, Alice is sending too many messages, Bob will not
receive them all.)

I reckon that in practice, we tend to size systems so they can accept
as many messages as they get, and not much more. But this is an
indirect relationship. If I were Wikileaks, I may receive many more
forgery attempts than genuine messages from the actual whistle-blower.
Yet it is critical that I process them all, so I can actually receive
the genuine messages. It doesn't matter that the whistle-blower only
sends 3 messages per week. What does matter is that three letter
agencies are sending millions of forgeries per day.

(I do acknowledge that the high number of forgery attempts means I
should limit message length to compensate. If your point was that
message length and number of forgery attempts compete… Yes, I admit
that they do. And no, I didn't know. Thanks for teaching me that.)

> limit is.  I am a big fan of clearly articulated usage limits.

Perfect :-)

Loup.