Subject: [Cfrg] Review of draft-arciszewski-xchacha-02

From: Neil Madden <[email-masked]>
Date: Tue, 18 Dec 2018 12:14:42 +0000

I’ve had a good look through draft-arciszewski-xchacha-02 from an implementor’s perspective. I think it’s a good draft that describes the algorithms well. I have some comments on a few parts of the text below:

Section 1, Introduction:

The text currently says:

"However, a more straightforward strategy can prevent nonce misuse
   conditions in environments where a large number of messages are
   encrypted.”

We should be careful with the word “prevent” here. Nonce reuse can still happen with large random nonces, even if it is less likely - e.g., with a broken or compromised PRNG. See for example failures in the Android SecureRandom implementation that led to compromise of a Bitcoin transaction due to nonce reuse in an ECDSA signature [1]. In this case the random nonce would have been 256 bits I believe, so even larger than that for XChaCha.

I think “more straightforward” is also potentially subject to debate (if you ignore the S2V parts, SIV is pretty simple). Perhaps wording along the following lines:

“However, misuse resistant cipher constructions come at a cost in
performance as they must necessarily make two passes over the 
message to be encrypted. An alternative strategy can significantly 
reduce the chance of accidental nonce reuse in environments 
where a large number of messages are encrypted. [Simply use …]”

Ironically, the main reason that I am interested in XChaCha20 is precisely because the larger nonce makes it more suitable for use in an SIV construction, as per my recent draft.

Section 2.1 Motivation for XChaCha20-Poly1305:

It might be worth clarifying that a 96-bit nonce is too short to generate randomly where you need to encrypt lots of messages with the same key (more than a few million). If you are doing DH with forward secrecy and generating fresh keys for each message anyway, then a 96-bit random nonce is fine.

The text: "A more
   conservative threshold (2^-32 chance of collision) still allows for
   2^64 messages to be sent under a single key.”

This should say “still allows for 2^80 messages to be sent under a single key.”

2.2 HChaCha20

This could do with a reference to RFC 7539 section 2.3. It could be a bit clearer that the ChaCha20 block counter is replaced with the first 32 bits of the nonce (in little-endian) and the remaining 96 bits are used as per usual in ChaCha20.

I have verified the supplied test vector with an independent implementation of HChaCha20 that I wrote, and it matches.

2.3.1 XChaCha20 Pseudocode:

The code doesn’t include the 4 NUL bytes in the nonce it passes to ChaCha20.

Test vectors:

I have verified that the test vectors in A.1 and A.2 and produce the same results as documented.

[1] https://www.symantec.com/connect/blogs/android-cryptographic-issue-may-affect-hundreds-thousands-apps

Kind regards,

Neil

---

From: "Salz, Rich" <[email-masked]>
Date: Tue, 18 Dec 2018 13:16:35 +0000

To repeat what I said earlier, "XChaCha" is a bad name.  Can we use XNChaCha or something similar to show that is an extended NONCE, and not something like extended keysize or number of rounds?

---

From: Laurens Van Houtven <[email-masked]>
Date: Tue, 18 Dec 2018 08:49:56 -0600

Just another voice for an argument I'm sure has been made before: I agree
with the original spec, the best possible name is XChaCha20 and not
XNChaCha20 or whatever. Here's why:

- XSalsa20 already exists. "XNChaCha20" or whatever suggests that it's...
like XSalsa but with ChaCha and... whatever an N is. The N does not clarify
anything by itself; you'd have to read the spec anyway, and reading the
introductory paragraphs seems like a pretty low bar for using a
crytpographic primitive. Once you do that, you couldn't have any confusion
anymore about what's extended about this cipher. And you'd need to read
that anyway to know what the X meant in the first place :-
- A extended number of rounds wouldn't make sense for these ciphers. For
reduced rounds, that namespace already exists in e.g. Salsa20/8 (which is
Salsa20 but with 8 rounds [1]). There is no Salsa20 with more than 20
rounds because 20 rounds are already considered quite conservative; but if
you were to make a 24-round ChaCha, ChaCha20/24 would be the consistent
name for it.
- An extended key space wouldn't make sense for these ciphers, because they
already have 256 bit keys and target the security level you'd expect from
that.
- The name XChaCha20 is already in use in the popular libsodium library[2]
-- who arrived at the same name because, well, IMO the derivation is
obvious it's much more surprising to me anyone is suggesting something else
than that someone else got at the same name via the same process :-)

[1]: https://cr.yp.to/snuffle/812.pdf
[2]: https://libsodium.gitbook.io/doc/advanced/stream_ciphers/xchacha20

lvh

On Tue, Dec 18, 2018 at 7:17 AM Salz, Rich <[email-masked]> wrote:

> To repeat what I said earlier, "XChaCha" is a bad name.  Can we use
> XNChaCha or something similar to show that is an extended NONCE, and not
> something like extended keysize or number of rounds?
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Tony Arcieri <[email-masked]>
Date: Tue, 18 Dec 2018 08:05:06 -0800

> something like extended keysize or number of rounds?

As someone who routinely vocalizes the names of these constructions,
they're already a bit unwieldy. I wish we would've Curve25519 => Curve255
and Ed25519 => Ed255 just to make them easier to pronounce.

I'd rate "XChaCha" as "good" on the pronounceability scale, and XNChaCha...
less so

-- 
Tony Arcieri

---

From: Kyle Rose <[email-masked]>
Date: Tue, 18 Dec 2018 11:13:13 -0500

On Tue, Dec 18, 2018 at 9:50 AM Laurens Van Houtven <[email-masked]> wrote:

> - XSalsa20 already exists.
>

This was exactly the point I was going to make. Whether or not it's ideal
nomenclature, it's established and understandable to everyone with enough
context to care what XChaCha is.

(Also, "There are only two hard things in Computer Science: cache
invalidation and naming things.")

Kyle

---

From: Scott Arciszewski <[email-masked]>
Date: Tue, 18 Dec 2018 11:28:18 -0500

Thanks for the review and feedback, Neil.

I've made some other changes on Github and was going to get draft03 ready
today. I'll incorporate your suggestions as well.

Aside: Based on the responses to the "Adoption call for
draft-arciszewski-xchacha" thread
<https://www.ietf.org/mail-archive/web/cfrg/current/msg09854.html>, I
believe this will also be the last draft before CFRG adoption (which
presumably will change the filename in future editions).
Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>

On Tue, Dec 18, 2018 at 7:15 AM Neil Madden <[email-masked]> wrote:

> I’ve had a good look through draft-arciszewski-xchacha-02 from an
> implementor’s perspective. I think it’s a good draft that describes the
> algorithms well. I have some comments on a few parts of the text below:
>
> Section 1, Introduction:
>
> The text currently says:
>
> We should be careful with the word “prevent” here. Nonce reuse can still
> happen with large random nonces, even if it is less likely - e.g., with a
> broken or compromised PRNG. See for example failures in the Android
> SecureRandom implementation that led to compromise of a Bitcoin transaction
> due to nonce reuse in an ECDSA signature [1]. In this case the random nonce
> would have been 256 bits I believe, so even larger than that for XChaCha.
>
> I think “more straightforward” is also potentially subject to debate (if
> you ignore the S2V parts, SIV is pretty simple). Perhaps wording along the
> following lines:
>
> Ironically, the main reason that I am interested in XChaCha20 is precisely
> because the larger nonce makes it more suitable for use in an SIV
> construction, as per my recent draft.
>
> It might be worth clarifying that a 96-bit nonce is too short to generate
> randomly where you need to encrypt lots of messages with the same key (more
> than a few million). If you are doing DH with forward secrecy and
> generating fresh keys for each message anyway, then a 96-bit random nonce
> is fine.
>
> The text: "A more
> This could do with a reference to RFC 7539 section 2.3. It could be a bit
> clearer that the ChaCha20 block counter is replaced with the first 32 bits
> of the nonce (in little-endian) and the remaining 96 bits are used as per
> usual in ChaCha20.
>
> I have verified the supplied test vector with an independent
> implementation of HChaCha20 that I wrote, and it matches.
>
> [1]
> https://www.symantec.com/connect/blogs/android-cryptographic-issue-may-affect-hundreds-thousands-apps
>
> Kind regards,
>
> Neil