Subject: [Cfrg] Fwd: New Version Notification for draft-nir-cfrg-chacha20-poly1305-05.txt

From: Yoav Nir <[email-masked]>
Date: Thu, 19 Jun 2014 15:58:43 +0300

Hi

This is version -05 of the document.  

Changes include:
  - Added some crypto papers as references for ChaCha (still looking for some for Poly1305)
  - Fixed some typos
  - Removed the TBD remarks about big vs little endianness, and lengths expressed in bits vs octets. Nobody seemed too interested in debating the  little+octets choices.

As before, we need reviews, especially for the Poly1305 key generations in section 2.6 ( http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-05#section-2.6 )

Thanks

Adam & Yoav

Begin forwarded message:

> From: [email-masked]
> Subject: New Version Notification for draft-nir-cfrg-chacha20-poly1305-05.txt
> Date: June 19, 2014 at 3:52:12 PM GMT+3
> To: Yoav Nir <[email-masked]>, Adam Langley <[email-masked]>, "Yoav Nir" <[email-masked]>, "Adam Langley" <[email-masked]>
> 
> 
> A new version of I-D, draft-nir-cfrg-chacha20-poly1305-05.txt
> has been successfully submitted by Yoav Nir and posted to the
> IETF repository.
> 
> Name:		draft-nir-cfrg-chacha20-poly1305
> Revision:	05
> Title:		ChaCha20 and Poly1305 for IETF protocols
> Document date:	2014-06-19
> Group:		Individual Submission
> Pages:		36
> URL:            http://www.ietf.org/internet-drafts/draft-nir-cfrg-chacha20-poly1305-05.txt
> Status:         https://datatracker.ietf.org/doc/draft-nir-cfrg-chacha20-poly1305/
> Htmlized:       http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-05
> Diff:           http://www.ietf.org/rfcdiff?url2=draft-nir-cfrg-chacha20-poly1305-05
> 
> Abstract:
>   This document defines the ChaCha20 stream cipher, as well as the use
>   of the Poly1305 authenticator, both as stand-alone algorithms, and as
>   a "combined mode", or Authenticated Encryption with Additional Data
>   (AEAD) algorithm.
> 
>   This document does not introduce any new crypto, but is meant to
>   serve as a stable reference and an implementation guide.
> 
> 
> 
> 
> Please note that it may take a couple of minutes from the time of submission
> until the htmlized version and diff are available at tools.ietf.org.
> 
> The IETF Secretariat
>

---

From: Watson Ladd <[email-masked]>
Date: Thu, 19 Jun 2014 11:04:14 -0300

On Thu, Jun 19, 2014 at 9:58 AM, Yoav Nir <[email-masked]> wrote:
>   - Removed the TBD remarks about big vs little endianness, and lengths
> expressed in bits vs octets. Nobody seemed too interested in debating the
> little+octets choices.
>
> As before, we need reviews, especially for the Poly1305 key generations in
> section 2.6 (
> http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-05#section-2.6 )

There is no problem with that section: if ChaCha is a PRF, then the
results are computationally indistinguishable from random.

However, the specification has several issues:

"arithmetically add" means what exactly? Addition modulo 2^32?

"integer addition without carry" meaning addition modulo 2^32?

Does the 0 word of the state or the 15 word of the state come first?

Cryptographically there are no problems.

Sincerely,
Watson Ladd

> To: Yoav Nir <[email-masked]>, Adam Langley <[email-masked]>, "Yoav
> Nir" <[email-masked]>, "Adam Langley" <[email-masked]>
>
>
> URL:
> http://www.ietf.org/internet-drafts/draft-nir-cfrg-chacha20-poly1305-05.txt
> Status:
> https://datatracker.ietf.org/doc/draft-nir-cfrg-chacha20-poly1305/
> Htmlized:
> http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-05
> Diff:
> http://www.ietf.org/rfcdiff?url2=draft-nir-cfrg-chacha20-poly1305-05
>
> Abstract:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Yoav Nir <[email-masked]>
Date: Thu, 19 Jun 2014 17:39:55 +0300

Hi, Watson

Thanks for the review.

I agree that the wording is clumsy. In the previous version of the draft, the text said, "the original input words are added to the output words”, and “add” could mistakenly be interpreted to mean concatenate. I’ll change it to “add modulu 2^32” and use that in both cases. 

The 0-th word of the state comes first, and that is easy to see from the examples, but I will say so explicitly the first time I use the word “serialize” (at the end of section 2.3).

As you say, ChaCha is a PRF, and DJB’s article says that there is nothing special about AES. But in DJB’s paper, a special key is used for AES to generate the Poly1305 keys. In this draft, the same key is used for ChaCha when it’s used to generate the Poly1305 key as when it’s used to encrypt traffic. We do make sure that the nonces are different, but it’s important to make sure that CFRG people (such as yourself) considered this before saying that cryptographically there are no problems. 

Thanks again

Yoav

---

From: Watson Ladd <[email-masked]>
Date: Thu, 19 Jun 2014 11:59:55 -0300

On Thu, Jun 19, 2014 at 11:39 AM, Yoav Nir <[email-masked]> wrote:
> Hi, Watson
>
> Thanks for the review.
>
> I agree that the wording is clumsy. In the previous version of the draft,
> the text said, "the original input words are added to the output words”, and
> “add” could mistakenly be interpreted to mean concatenate. I’ll change it to
> “add modulu 2^32” and use that in both cases.
>
> The 0-th word of the state comes first, and that is easy to see from the
> examples, but I will say so explicitly the first time I use the word
> “serialize” (at the end of section 2.3).
>
> As you say, ChaCha is a PRF, and DJB’s article says that there is nothing
> special about AES. But in DJB’s paper, a special key is used for AES to
> generate the Poly1305 keys. In this draft, the same key is used for ChaCha
> when it’s used to generate the Poly1305 key as when it’s used to encrypt
> traffic. We do make sure that the nonces are different, but it’s important
> to make sure that CFRG people (such as yourself) considered this before
> saying that cryptographically there are no problems.

This is how AES-GCM and the "Crypto in NaCl" secret_box function both
work: the encryption of counter zero
is reserved for use in the MAC.

Given a random K ChaCha(K, N||C) is a PRF. Therefore ChaCha(K, N||0)
(or whatever is used) is not predictable given
any other outputs, provided they are distinct.

This isn't an instance of generic composition, but it can still be
proven secure.

http://cr.yp.to/highspeed/naclcrypto-20090310.pdf

---

From: Yoav Nir <[email-masked]>
Date: Thu, 19 Jun 2014 22:13:26 +0300

> is reserved for use in the MAC.

Well, the GCM hash key is used differently. The hash key is used for the lifetime of the encryption key, whereas here it is generated anew for every packet or record. But you’re right. It seems like all we have to show is that the same nonce is never used for both an encryption and a MAC key calculation, and that’s pretty easy (the blockcount part of the nonce is always zero for MAC key derivation, and always non-zero for encryption), so I guess we’re safe.

Yoav

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 30 Jun 2014 13:53:40 +0300

> As before, we need reviews, especially for the Poly1305 key generations in section 2.6 ( http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-05#section-2.6 )

Editorial:

Section 2.8.1: The Ciphertext dump is seemingly missing 0x7f byte in
the ASCII version.

Section A.1 Test vector #4: Another ASCII 0x7f seems to be missing.

Section A.2 Test vector #3: Same as above, twice.

(for some odd reason, there are 0x7f bytes in other places, but those
properly appear as '.' in the ASCII dump (0x7f is not printable)).

Other stuff:

I actually wrote an implementation (I haven't optimized it so it is
slow).

The Poly1305 test vectors: All the nontrivial ones test non-mod16
lengths, which are not needed by the AEAD construction. Thus, if
using dedicated poly1305 routines, the cases needed for test
vectors may not be supported.

For this reason, whereas I run nearly every other test vector as
self-test in my code, I haven't coded the Poly1305 tests.

Also, I devised few edge cases that could happen in Poly1305 calculation,
and devised test cases to provoke those. Some of those (#3 and #7) caught
actual bugs where the two full AEAD test vectors didn't find one.

1) If one uses 130-bit partial reduction, does the code handle the
case where partially reduced final result is not fully reduced?

R:
02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
S:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
data: 
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
tag:
03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

2) What happens if addition of s overflows modulo 2^128?

R:
02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
S:
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
data:
02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
tag:
03 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

3) What happens if data limb is all ones and there is carry from lower
limb?

R:
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
S:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
data:
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
F0 FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
11 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
tag:
05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

4) What happens if final result from polynomial part is exactly 2^130-5?

R:
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
S:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
data:
FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
FB FE FE FE FE FE FE FE FE FE FE FE FE FE FE FE
01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
tag:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

5) What happens if final result from polynomial part is exactly 2^130-6?

R:
02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
S:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
data:
FD FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF
tag:
FA FF FF FF FF FF FF FF FF FF FF FF FF FF FF FF

6) What happens if 5*H+L-type reduction producess 131-bit intermediate
result?

R:
01 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00
S:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
data:
E3 35 94 D7 50 5E 43 B9 00 00 00 00 00 00 00 00
33 94 D7 50 5E 43 79 CD 01 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
tag:
14 00 00 00 00 00 00 00 55 00 00 00 00 00 00 00

7) What happens if 5*H+L-type reduction produces 131-bit final result?

R:
01 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00
S:
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
data:
E3 35 94 D7 50 5E 43 B9 00 00 00 00 00 00 00 00
33 94 D7 50 5E 43 79 CD 01 00 00 00 00 00 00 00 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
tag:
13 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Mon, 30 Jun 2014 17:49:02 +0300

> properly appear as '.' in the ASCII dump (0x7f is not printable)).

Gah!  I actually fixed my hex dump code, but didn’t run some of the buffers again.  Will fix.

> self-test in my code, I haven't coded the Poly1305 tests.

I wrote those test vectors before version -04, when Poly1305 was not 16-byte aligned. Poly1305 might still find a use in a NULL_with_Poly1305 ciphersuite or in IPsec AH, so I’ll leave those test vectors in there.

And I will add yours as well in the next iteration.

Thanks!