Subject: [Cfrg] RGLC on draft-irtf-cfrg-chacha20-poly1305-01.txt

From: Alexey Melnikov <[email-masked]>
Date: Thu, 02 Oct 2014 13:45:01 +0100

The authors of "ChaCha20 and Poly1305 for IETF protocols", 
draft-irtf-cfrg-chacha20-poly1305-01.txt believe the draft is ready for 
a RGLC.

This starts a two week research group last call, to end on 17 Oct 2014.

The draft is available at 
http://datatracker.ietf.org/doc/draft-irtf-cfrg-chacha20-poly1305/

Please do comment on the list, indicating whether you believe this draft 
is ready for publication. Please send your comments, indication of 
support for the publication or objections to the publication to the 
mailing list or directly to the RG chairs ([email-masked]).

Alexey,
As a co-chair.

---

From: Yoav Nir <[email-masked]>
Date: Mon, 6 Oct 2014 11:13:15 +0300

Hi.

As co-author of the draft, it's no surprise that I think it's ready. So
I'll just point out that:
 - The algorithms described have been implemented multiple times, both by
the authors and by others
 - At least two implementations were done by following the draft (and the
test vectors checked out)
 - At least one browser (Google Chrome) has these algorithms running in
production and used with the Google servers.

So I guess we've got the "running code" part down.

Yoav

On Thu, Oct 2, 2014 at 3:45 PM, Alexey Melnikov <[email-masked]>
wrote:

> draft-irtf-cfrg-chacha20-poly1305-01.txt believe the draft is ready for a
> RGLC.
>
> The draft is available at http://datatracker.ietf.org/
> doc/draft-irtf-cfrg-chacha20-poly1305/
>
> is ready for publication. Please send your comments, indication of support
> for the publication or objections to the publication to the mailing list or
> directly to the RG chairs ([email-masked]).
>
> Alexey,
> As a co-chair.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 6 Oct 2014 14:06:43 -0700 (PDT)

> So I guess we've got the "running code" part down.

  Very nice! It's good to see people with running code that implements
the proposals for which they are attempting to achieve rough consensus.
I guess we could call it "old school" :-)

  One suggestion is that since this takes a cipher and a separate MAC
function to create a composite, you should define this combined AEAD
mode to fit into the RFC 5116 AEAD abstraction. This will require a subtle
modification to section 2.8-- around formation of the AEAD, and
specification of maximal limits-- and the requisite IANA Considerations
in section 5.

  I understand that this is the CFRG and not any particular IETF WG
that produces standards for some protocol but given that you say your
running code includes some secure browser-to-server communication
it might be nice to include such a conversation (using, for example,
ssldump) as a separate test vector.

  regards,

  Dan.

>> a
>> support

---

From: James Cloos <[email-masked]>
Date: Mon, 06 Oct 2014 17:25:38 -0400

[I thought I sent on this subect weeks ago, but I cannot find it in
 the archives, ... -JimC]

I have to object to defaulting to a 96/32 split.

The rfc should specify Dan's 64/64 split as default, and only offer
96/32 as an option.

Chacha isn't only useful for in-flight encryption.  One should not
have to bother with multiple keys or IVs to encrypt large files.
And 128 Gigs is not all that large for things like backups (tar,
cpio, et cetera), disk images, some AV files and the like.

It is very reasonable to presume that larger and larger files will
become more and more common as the storage devices sizes and demand
for higher resolution media files each continue to escalate.

The RFC should be a valid reference for all potential uses of chacha.

Even in the IETF, OpenPGP encrypts files at rest.

Secsh should continue to use 64/64; OpenPGP and SMIME should add chacha
with 64/64; I would prefer 64/64 for TLS.

But if IPSEC insists on 96/32, that should be an option, not the primary
scenario.

-JimC
-- 
James Cloos <[email-masked]>         OpenPGP: 0x997A9F17ED7DAEA6

---

From: Yoav Nir <[email-masked]>
Date: Tue, 7 Oct 2014 00:50:02 +0300

Hi, Dan

Thanks for the kind words.

> specification of maximal limits-- and the requisite IANA Considerations

I’m not quite sure I follow. The construction uses a 96-bit nonce precisely so that we comply with RFC 5116. What requirement of 5116 are we not fitting into?

Yoav

---

From: Adam Langley <[email-masked]>
Date: Mon, 6 Oct 2014 14:53:04 -0700

On Mon, Oct 6, 2014 at 2:50 PM, Yoav Nir <[email-masked]> wrote:
> I’m not quite sure I follow. The construction uses a 96-bit nonce precisely
> so that we comply with RFC 5116. What requirement of 5116 are we not fitting
> into?

I think Dan is just saying that the limits need to be specified. For
example see page 8 in
https://tools.ietf.org/html/draft-agl-tls-chacha20poly1305-04#section-5
(although these values are wrong now).

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Yoav Nir <[email-masked]>
Date: Tue, 7 Oct 2014 00:55:56 +0300

> (although these values are wrong now).

Ah, I see. Thanks. I’ll get on it tomorrow.

Yoav

---

From: "Dan Harkins" <[email-masked]>
Date: Mon, 6 Oct 2014 15:35:00 -0700 (PDT)

> (although these values are wrong now).

  I'm sorry, I meant the formation of the AAD. Is it a single blob that
gets passed to the algorithm? Does the mode allow for multiple distinct
AAD inputs ala RFC 5297? What if the protocol I want to use with this
mode has several distinct blobs I want to use as AAD (like how IEEE Std
802.11 uses AAD with AEAD cipher modes-- take these bits and then
concatenate these addresses, etc)? I suspect it's all just a single
concatenated blob but it would help to say so explicitly and to define
the RFC 5116 interface.

  It obviously takes AAD since section 2.8 mentions it as something to
include as input to AEAD_CHACHA20-POLY1305. So I'm suggesting you
define what AAD looks like when it is delivered to the mode: "Distinct
AAD shall be concatenated into a single input to
AEAD_CHACHA20-POLY1305", for example.

  regards,

  Dan.

---

From: Nikos Mavrogiannopoulos <[email-masked]>
Date: Tue, 7 Oct 2014 11:57:13 +0200

> cpio, et cetera), disk images, some AV files and the like.

Would you really want to use an AEAD cipher for backup encryption in a
single pass? I mean a single bit corruption in 128 Gigs and you lost
everything as authentication would fail. Most probably backup
encryption software would split the large backup data into smaller
chunks that are authenticated and in that case the 96/32 split would
fit.

regards,
Nikos

---

From: James Cloos <[email-masked]>
Date: Tue, 07 Oct 2014 09:20:23 -0400

>>>>> "NM" == Nikos Mavrogiannopoulos <[email-masked]> writes:

NM> Would you really want to use an AEAD cipher for backup encryption in a
NM> single pass? I mean a single bit corruption in 128 Gigs and you lost
NM> everything as authentication would fail.

One should only loose the block which failed auth.

Ie, each block should be treated separately.

-JimC

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Tue, 07 Oct 2014 16:02:52 +0200

> Ie, each block should be treated separately.
I'm sorry if I'm missing something painfully obvious, but if each block is
treated separately, then why do you need a counter larger than 32 bits?

Manuel.

---

From: James Cloos <[email-masked]>
Date: Tue, 07 Oct 2014 10:22:23 -0400

>>>>> "MP" == Manuel Pégourié-Gonnard <[email-masked]> writes:

MP> ... if each block is treated separately, then why do you need a
MP> counter larger than 32 bits?

The counter increments for each 256bit block.

I'd expect two block sizes; the 256-bit chacha block and some arbitrary,
potentially larger poly1305 block, perhaps covering somewhere between 4
and 256 chacha blocks.

Each 256bit block gets its own counter value.

Each poly1305 block is vulnerable to loss due to corruption.  Although
even then it can be analyzed to attempt to recover as many bits as
possible --- since it is not on-the-fly, time is available to let people
make judgement calls.

Which reminds me of something I forgot to mention in this thread.

I'd also prefer to see three RFCs.  One covering chacha itself
(including each of two, three or five quad-rounds[sic]), one for
poly1305 (including with chacha and aes (it's original spec)),
and the combination, referecing the first two.

Chacha on its own has value, too.

Dan's paper on aes/poly1305 makes it look like a better choice than gcm,
at least.  Maybe also better than ccm, et alia.

And then the third can be specific to on-the-fly.

-JimC

---

From: David Leon Gil <[email-masked]>
Date: Tue, 7 Oct 2014 11:09:09 -0400

(This I-D is really excellent; my comments are minor nits. I support moving
this along to RFC status ASAP.)

> test vectors checked out)

Re A.2: There are still no ChaCha20 test-vectors to ensure that implementations
use the correct counter rule.

I.e., what happens when the 32-bit block counter is 2^32 - 1? It is
rather critical
that implementations never reuse the keystream for block 0 in this construction.

I'd suggest, in light of the note in 2.8.1, that simply letting the counter mode
be non-separated is simplest. (This has the advantage that it retains
compatibility
with the original definition.[*])

(I have test-vectors for either option; but the authors would need to
pick one...)

--

Perhaps add a reference to the more recent paper by Namprempre et al.,
"Reconsidering generic composition" https://eprint.iacr.org/2014/206
(I believe this would be a N2-type scheme in their terminology.)

[*] I too think 2^32 blocks is not a large amount of data.

---

From: Ted Krovetz <[email-masked]>
Date: Tue, 7 Oct 2014 08:47:01 -0700

> [*] I too think 2^32 blocks is not a large amount of data.

If one views the chacha core as a PRF from 384 bits to 512 bits, then there are all sorts of ways to increase the lengths of the internal counter and/or external nonce. Here are a couple different data layouts for chacha core input that would allow longer counters.

You could shorten the key:

  224 bits of key ||
  96 bits of nonce ||
  64 bits of counter

Or, you could mix the key and nonce (allowing 16 byte nonces):

  first 192 bits of key ||
  ((last 64 bits of key) xor (first 64 bits of nonce)) ||
  last 64 bits of nonce ||
  64 bits of counter

If one uses only the "last 64 bits of nonce", this second suggestion becomes chacha as originally specified.

-Ted

---

From: Yoav Nir <[email-masked]>
Date: Tue, 7 Oct 2014 19:49:08 +0300

Hi, James

The 96/32 split is dictated by the recommendation in RFC 5116. While any sane use of symmetric keys will never use the same keys for either 2^96 messages or 2^64 messages, being able to safely split the range of acceptable nonces is an advantage. Neither regular IPsec nor regular TLS need this, but multi-sender IPsec (GDOI) and multi-sender DTLS can benefit.

As it is, the current TLS 1.3 draft defines AEAD ciphersuites as those described by RFC 5116. So yes, it’s possible to decide on a 64-bit nonce and state clearly in both this draft and the draft for ChaCha20-Poly1305 for TLS that we’ve decided to ignore the recommendation in 5116, but I don’t think that’s a good idea.

Yoav

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 7 Oct 2014 19:54:39 +0300

> at least.  Maybe also better than ccm, et alia.

Depends.

Poly1305 should be faster than CCM and unaccelerated GCM (plus that one
is really nasty to implement without side channels out the wazoo). HW-
accelerated GCM is faster and simpler than poly1305.

There are some platforms that do have HW AES but no HW GCM. But those
are fairly rare. AES/Poly1305 would be useful on such.

Some other things:
- GCM and original Poly1305(-AES) reuse R (this AEAD construct doesn't).
- Poly1305 is independent of encryption blocksize, whereas GCM is for
  128-bit ciphers only (it could be generalized to other sizes, but IIRC,
  it slows down as blocksize increases).

-Ilari

---

From: David Leon Gil <[email-masked]>
Date: Tue, 7 Oct 2014 12:54:25 -0400

On Tue, Oct 7, 2014 at 11:47 AM, Ted Krovetz <[email-masked]> wrote:
> If one views the chacha core as a PRF from 384 bits to 512 bits, then there are all sorts of ways to increase the lengths of the internal counter and/or external nonce.

Is there a reason not to define an "XChaCha" by analogy with XSalsa?
See http://cr.yp.to/snuffle/xsalsa-20110204.pdf

(The situation seems trickier for narrow PRPs, but ChaCha and Salsa
are both PRFs of the form you describe.)

---

From: James Cloos <[email-masked]>
Date: Tue, 07 Oct 2014 13:26:17 -0400

>>>>> "YN" == Yoav Nir <[email-masked]> writes:

YN> The 96/32 split is dictated by the recommendation in RFC 5116.

YN> Neither regular IPsec nor regular TLS need this, but multi-sender
YN> IPsec (GDOI) and multi-sender DTLS can benefit.

Yes, I read all of the prior discussions.

My argument is that 96/32 should be limited to those multi-sender
environments.

The RFC can spec 64/64, and then note that the upper 32 bits of the
counter can be initialized to something other than 0 whenever more
than 64 IV bits are required.

Just like it should mention that when not using reliable transports like
tcp and when the extra data includes any kind of a packet/frame number
which has a consistent function to the chacha counter, the receiver can
recognize missing packets and decode what it does get by basing its
chacha counter on said (authenticated) extra data.  Which would allow
dtls to avoid retransmission for things like rtp.

-JimC

---

From: Yoav Nir <[email-masked]>
Date: Sun, 12 Oct 2014 18:00:45 +0300

On Oct 7, 2014, at 1:35 AM, Dan Harkins <[email-masked]> wrote:

>>> Iâ€™m not quite sure I follow. The construction uses a 96-bit nonce
>>> precisely

Oh, I see. OK. Our construction does not make any particular provisions for multiple blobs of AAD. Of course the application is free to create such a structure by making it a series of TV or TLV, or if they really want to be fancy, a BER-encoded SEQUENCE (please don’t), but the code for ChaCha20-Poly1305 does not recognize such a structure.

> AEAD_CHACHA20-POLY1305", for example.

OK. I’ll add a sentence like that.

Thanks,

Yoav

---

From: Adam Langley <[email-masked]>
Date: Sun, 12 Oct 2014 10:22:58 -0700

> OK. I’ll add a sentence like that.

Note that concatenating distinct AD inputs is not safe: ["a", "bc"] is
then ambiguous with ["ab", "c"]. Applications are free to use any
scheme they want, but concatenation shouldn't be implicitly endorsed.

Cheers

AGL

---

From: Yoav Nir <[email-masked]>
Date: Sun, 12 Oct 2014 22:16:10 +0300

Yes, and section 3.3 of RFC 5116 says so, so I can just point at that.

Yoav

-----Original Message-----
From: "Adam Langley" <[email-masked]>
Sent: ‎10/‎12/‎2014 20:22
To: "Yoav Nir" <[email-masked]>
Cc: "Dan Harkins" <[email-masked]>; "[email-masked]" <[email-masked]>
Subject: Re: [Cfrg] RGLC on draft-irtf-cfrg-chacha20-poly1305-01.txt

Cheers

AGL

---

From: Yoav Nir <[email-masked]>
Date: Mon, 13 Oct 2014 14:32:23 +0300

On Oct 2, 2014, at 3:45 PM, Alexey Melnikov <[email-masked]> wrote:

> The authors of "ChaCha20 and Poly1305 for IETF protocols", draft-irtf-cfrg-chacha20-poly1305-01.txt believe the draft is ready for a RGLC.
> 
> The draft is available at http://datatracker.ietf.org/doc/draft-irtf-cfrg-chacha20-poly1305/
> 
> Please do comment on the list, indicating whether you believe this draft is ready for publication. Please send your comments, indication of support for the publication or objections to the publication to the mailing list or directly to the RG chairs ([email-masked]).
> 
> Alexey,
> As a co-chair.

Hi.

I haven’t submitted anything yet, but I’ve made a few changes to my local copy:
I’ve added the AEAD parameters from RFC 5116.
I’ve added the sentence suggested by Dan Harkins about combining several chunks of associated data (pretty much passing the responsibility for assembly/reassembly to the application)
I’ve changed the worked example for quarter-round, as suggested by Sean Parkinson (chose an example with the rotate-left amount not 16, because a rotate-left of 16 bits is similar to rotate-right of 16 bits)
I’ve added pseudo-code “implementations” to some of the algorithms, as suggested by Sean Parkinson

Things I didn’t do:
I did not change the counter/nonce split back to 64/64 as James Cloos suggested, because (a) that’s against a SHOULD in RFC 5116, and (b) it’s useful for multi-sender protocols, and (c) we had consensus for the change, and I don’t think we have consensus for the change back.
I did not switch to XChaCha as suggested by David Leon Gil
I did not incorporate the test vectors suggested by David because (a) they depend on suggested changes to hot the counter/nonce split, and (b) it might be addressed by limiting the amount of data that is allowed to be encrypted, which is in the draft (unless I totally misunderstood the suggestion)

For the (unpublished) draft with the changes, see:
 - TXT version: https://docs.google.com/document/d/1FnL6L_Ce_fnlqeRxSdoEUCbBQzz4m8r9ciy1dH9toC8/pub
 - HTML-ized version: https://docs.google.com/document/d/1SSICS0HBl0lot1hZJ8-XT7Q6JVJr9b0zQ6ZZUH4D-B0/pub

Yoav

---

From: "Salz, Rich" <[email-masked]>
Date: Mon, 13 Oct 2014 07:41:53 -0400

Ship it

--
Principal Security Engineer, Akamai Technologies
IM: [email-masked]<mailto:[email-masked]> Twitter: RichSalz

---

From: Yoav Nir <[email-masked]>
Date: Mon, 13 Oct 2014 14:43:35 +0300

Just waiting for RGLC to end.

On Oct 13, 2014, at 2:41 PM, Salz, Rich <[email-masked]> wrote:

> IM: [email-masked] Twitter: RichSalz

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 13 Oct 2014 15:24:19 +0300

> I’ve added the AEAD parameters from RFC 5116.

- Isn't K_LEN = 32, not 16?
- Isn't A_MAX = 2^64 - 1, not 2^64?
- AFAIK, RFC5116 requries returning the ciphertext and tag as single
  octet string (most likely concatenation).
- RFC5116 requires specifying relation between plaintext and
  ciphertext lengths (most likely |C|=|P|+16).
- RFC5116 recomends specifying just how badly things blow up
  if nonce is reused (AFAIK, XOR of plaintexts is revealed and
  arbitrary messages with that nonce may be forged).

Also, writing IANA consideration to register this
(AEAD_CHACHA20_POLY1305?) could be useful (as already suggested by
someone). Apparently the registry is called "AEAD algorithms" (at
least it is that way on IANA site, even if I can't find that in
RFC 5116). 

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Mon, 13 Oct 2014 15:41:31 +0300

> - Isn't K_LEN = 32, not 16?

Argh, shouldn’t write drafts after midnight.

> - Isn't A_MAX = 2^64 - 1, not 2^64?

Yes, see above. Fixed in my copy and Google docs.

>  octet string (most likely concatenation).

   An AEAD algorithm MAY structure its ciphertext output in any way; for
   example, the ciphertext can incorporate an authentication tag.

Following that, I calculated C_MAX to be P_MAX + 16.

>  ciphertext lengths (most likely |C|=|P|+16).

Yes.

>  arbitrary messages with that nonce may be forged).

Same authentication key and same keystream, so at least the XOR of the plaintexts is revealed and the same one-time Poly1305 is used. So if you know the plaintext and can choose the nonce, you will be able to encrypt another arbitrary message, but you will still fail tag calculation. I’ll add something to the security considerations.

> least it is that way on IANA site, even if I can't find that in

Will do.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Mon, 13 Oct 2014 16:32:25 +0300

>> least it is that way on IANA site, even if I can't find that in

OK. Done and done.

Thanks

Yoav