Subject: [Cfrg] [RFC] [DRAFT] eXtended-nonce ChaCha and AEAD_XChaCha20-Poly1305 (updated)

From: Paragon Initiative Enterprises Security Team <[email-masked]>
Date: Fri, 5 Oct 2018 13:36:47 -0400

Good afternoon,

I've uploaded draft01, which contains some typo fixes and an additional
test vector for XChaCha20 directly.

https://datatracker.ietf.org/doc/draft-arciszewski-xchacha/

If anyone would like to contribute to this document directly, its
development is being facilitated on GitHub:
https://github.com/bikeshedders/xchacha-rfc

Of course, I'm also open to feedback/criticism via email as well.

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises <https://paragonie.com>

---

From: Scott Arciszewski <[email-masked]>
Date: Thu, 11 Oct 2018 14:29:00 -0400

Good afternoon,

I've submitted another updated draft.

Based on feedback received via Github, this revision includes a
clarification about HPolyC's use of XChaCha12.

Additionally, I included copy-and-paste-friendly versions of the test
vectors to aid developers in writing their unit tests.

At this point I'm comfortable with the state of the draft and would like to
move forward with the IESG process soon.

If anyone at CFRG has any remarks (positive, negative, or neutral), please
share them at your earliest convenience.

Scott Arciszewski

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 11 Oct 2018 12:48:55 -0700

> share them at your earliest convenience.

I'll just note that despite the relative simplicity of this construction I
consider it an important work item for the group. The general primitive
(which NaCl calls "secretbox") has proven incredibly popular, but right now
there is a schism between Salsa20-based boxes (original NaCl) and
ChaCha20-based ones (WireGuard, libsodium). The former has a heritage
through NaCl, whereas the latter is what probably makes the most sense for
IETF protocols as it's effectively an RFC 7539 extension.

I imagine we'll see this sort of construction pop up quite a bit in future
protocols, including not just WireGuard but things like JWT work. An RFC
for XChaCha seems like an important prerequisite for e.g. a full WireGuard
RFC (with WireGuard having seen quite a bit of success in the "rough
consensus and running code" sense).

-- 
Tony Arcieri

---

From: Jason Cooper <[email-masked]>
Date: Thu, 11 Oct 2018 20:41:58 +0000

Hi Scott,

> Of course, I'm also open to feedback/criticism via email as well.

This has been a long-sought low-hanging goal of mine, and I'm glad to
see someone picking it up!

I've asked this question before[1], and it seems now is the proper time
to bring it up again.  When DJB wrote "Extending the Salsa20 nonce"[2],
he included a security analysis of the construction.  To date, I've not
seen a similar proof for extending the Chacha20 nonce.

It seems as though care was taken to select the 256 bits (Section 2.2 of
your current version) which were not nibbles originally containing the
key.  Similar selection was done in XSalsa20.

So, my question is: Why is this ok?  I freely admit I've neither the
experience nor the mathematical prowess to understand DJB's XSalsa20
proof.  And it certainly *seems* correct to follow the pattern for
XChaCha20.

However, I'd really like to see this addressed in the RFC.  Either by
providing a similar proof to XSalsa20, or by referencing it and
justifying the extension.

Thanks,

Jason.

[1] http://www.metzdowd.com/pipermail/cryptography/2017-December/033256.html
[2] https://cr.yp.to/snuffle/xsalsa-20110204.pdf (referenced in RFC)
    https://cr.yp.to/snuffle/xsalsa-20081128.pdf (referenced in my email)

---

From: Scott Arciszewski <[email-masked]>
Date: Thu, 11 Oct 2018 17:42:57 -0400

Hi Jason,

I strongly agree that this is an important question to tackle. I've taken
my first swing at addressing it here:
https://github.com/bikeshedders/xchacha-rfc/pull/9

The construction seems "obvious", and it's easy to extend the same
arguments in the XSalsa20 paper (in particular regarding the design of
HSalsa20) to ChaCha. The logic is quite straightforward between the two
designs. However, I similarly cannot find any papers formalizing this
argument.

Note: Lacking any university affiliations, I don't have any means of
getting a formal peer-reviewed paper published (that I'm aware of, anyway).
If anyone else would like to take the initiative on this, it would be
greatly welcomed and appreciated.

Aside from that, if anyone can sanity-check the argument being made here,
please feel free to do so.

Scott Arciszewski

On Thu, Oct 11, 2018 at 4:42 PM Jason Cooper <[email-masked]> wrote:

> [1]
> http://www.metzdowd.com/pipermail/cryptography/2017-December/033256.html

---

From: "D. J. Bernstein" <[email-masked]>
Date: 12 Oct 2018 01:30:21 -0000

Jason Cooper writes:
> So, my question is: Why is this ok?

Alice has hired Bob to build a box that computes HSalsa20 using Alice's
secret key. She isn't giving Bob her secret key, but she's giving Bob a
box that computes Salsa20 using her secret key.

Can Bob still do his job? Yes! Bob builds his HSalsa20 box around
Alice's Salsa20 box. Whatever input comes into Bob's HSalsa20 box, Bob
passes the same input to the Salsa20 box. Bob then extracts certain
words from the Salsa20 output, and subtracts the corresponding input
words, to obtain the HSalsa20 output.

Salsa20 is designed so that an attacker given access to Alice's Salsa20
box can't detect any patterns in the outputs produced by the box. Is it
possible that HSalsa20 is weaker---that an attacker can detect patterns
in the outputs of the HSalsa20 box that Bob built?

The answer is no. Show me an attacker who can see patterns in the
outputs of Bob's HSalsa20 box, and I'll show you an attacker who can see
patterns in the outputs of Alice's Salsa20 box. The second attacker
simply builds the same box that Bob did, and hires the first attacker!

---Dan

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Fri, 12 Oct 2018 13:26:31 +0000

Hi Scott,

it’s nice to see work that creates alternatives to deterministic nonces.

As I understand it, the motivation for this draft is to enable the use of random nonces.  Why not define it as a randomized AEAD algorithm, so that the nonce is dispensed with entirely?   (In  RFC 5116 terms, a randomized algorithm can have a maximum nonce length of zero).    That way, the security of the algorithm does not depend on the user’s ability to provide random nonces, there is no need to document the security requirements (or any other requirements) around that input, and the nonce generation can be tested along with the algorithm.

A couple of other comments: there needs to be a security considerations section (especially if guidance on nonce generation is needed) and there should be an IANA section that creates registry entries for this algorithm.

If nonces are pseudorandomly generated, either inside or outside of the algorithm, then users need to be careful about things like fork() and VM cloning that can undermine security by causing unintentional nonce reuse.

best

David

From: Cfrg <[email-masked]<mailto:[email-masked]>> on behalf of Paragon Initiative Enterprises Security Team <[email-masked]<mailto:[email-masked]>>
Date: Friday, October 5, 2018 at 1:36 PM
To: "[email-masked]<mailto:[email-masked]>" <[email-masked]<mailto:[email-masked]>>
Subject: [Cfrg] [RFC] [DRAFT] eXtended-nonce ChaCha and AEAD_XChaCha20-Poly1305 (updated)

Good afternoon,

I've uploaded draft01, which contains some typo fixes and an additional test vector for XChaCha20 directly.

If anyone would like to contribute to this document directly, its development is being facilitated on GitHub: https://github.com/bikeshedders/xchacha-rfc

Scott Arciszewski
Chief Development Officer
Paragon Initiative Enterprises<https://paragonie.com>

---

From: Scott Arciszewski <[email-masked]>
Date: Fri, 12 Oct 2018 11:10:22 -0400

Hi David,

Why not define it as a randomized AEAD algorithm, so that the nonce is
> dispensed with entirely?

I actually do precisely that in my high-level abstractions that wrap
libsodium's crypto_aead_xchacha20poly1305_*(). See the PASETO draft for
example.

However, the API provided by the incumbent implementations do not force
developers to use random nonces. It wouldn't be good form for me to add
this requirement.

This RFC draft captures what existing implementations have already been
doing for years.

Scott Arciszewski

On Fri, Oct 12, 2018 at 9:26 AM David McGrew (mcgrew) <[email-masked]>
wrote:

> As I understand it, the motivation for this draft is to enable the use of
> random nonces.  Why not define it as a randomized AEAD algorithm, so that
> the nonce is dispensed with entirely?   (In  RFC 5116 terms, a randomized
> algorithm can have a maximum nonce length of zero).    That way, the
> security of the algorithm does not depend on the user’s ability to provide
> random nonces, there is no need to document the security requirements (or
> any other requirements) around that input, and the nonce generation can be
> tested along with the algorithm.
>
> A couple of other comments: there needs to be a security considerations
> section (especially if guidance on nonce generation is needed) and there
> should be an IANA section that creates registry entries for this algorithm.
>
>
> If nonces are pseudorandomly generated, either inside or outside of the
> algorithm, then users need to be careful about things like fork() and VM
> cloning that can undermine security by causing unintentional nonce reuse.
>
> best
>
> David
>
> From: Cfrg <[email-masked]> on behalf of Paragon Initiative
> Enterprises Security Team <[email-masked]>
> To: "[email-masked]" <[email-masked]>