Subject: [Cfrg] Fwd: I-D Action: draft-nir-cfrg-chacha20-poly1305-00.txt

From: Yoav Nir <[email-masked]>
Date: Mon, 27 Jan 2014 22:15:26 +0000

Hi

I've submitted the below draft about ChaCha20 and Poly1305. This document aims to describe the algorithms (and AGL's AEAD based on them) in such a way that an implementer will be able to write code that implements these functions with only this document as a reference. The intention is for this document to serve as a reference for future documents entitled "ChaCha20, Poly1305 and their use in XXX". I personally intend to use it for an IPsec document.

This version -00 is quite drafty, and I'm not sure of my calculations, especially in Poly1305 (I used "bc" for all of them). So this document needs review. IMO it could also make a good undergraduate project that will also help to verify the examples and test vectors interspersed throughout.  More test vectors is another thing this document needs.

This document

  *   does not introduce any new crypto - it's all from DJB and AGL.
  *   does not provide security proofs - there's plenty of that in academic papers, although I would be happy to link to those as informative references.
  *   does not have any timing data or performance numbers. Those are very platform-dependent, so I don't know if they're appropriate. If they are, I'll be happy to include them.

There are a few open issues I'd like to address:

  1.  When converting a 256-bit buffer into a pair of numbers, k & r, Adam's draft takes "r" from the first 128 bits, and "k" from the following bits. DJB's sample code seems to go the other way. I went with Adam's way.
  2.  In cases where buffers are converted to integers or vice versa, we used little-endian order. This is different from the way it's done in (for example) GCM and in many protocols. It's true that some parts of the ChaCha20 algorithm itself are explicitly little-endian
  3.  The lengths encoded in the AEAD construction are in bytes, whereas in GCM they are in bits.

Thanks

Yoav

Begin forwarded message:

From: <[email-masked]<mailto:[email-masked]>>
Subject: I-D Action: draft-nir-cfrg-chacha20-poly1305-00.txt
Date: January 27, 2014 1:45:46 PM GMT+02:00
To: <[email-masked]<mailto:[email-masked]>>
Reply-To: <[email-masked]<mailto:[email-masked]>>

A New Internet-Draft is available from the on-line Internet-Drafts directories.

       Title           : ChaCha20 and Poly1305 for IETF protocols
       Author          : Yoav Nir
Filename        : draft-nir-cfrg-chacha20-poly1305-00.txt
Pages           : 20
Date            : 2014-01-27

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.

The IETF datatracker status page for this draft is:
https://datatracker.ietf.org/doc/draft-nir-cfrg-chacha20-poly1305/

There's also a htmlized version available at:
http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-00

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.

Internet-Drafts are also available by anonymous FTP at:
ftp://ftp.ietf.org/internet-drafts/

_______________________________________________
I-D-Announce mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/i-d-announce
Internet-Draft directories: http://www.ietf.org/shadow.html
or ftp://ftp.ietf.org/ietf/1shadow-sites.txt

Email secured by Check Point

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 28 Jan 2014 01:34:54 +0200

>   Rounds 1-4 are part of the "column" round, while 5-8 are part of the
>   "diagonal" round:

Should the first "Rounds" be "Quaterrounds" or something?

>   AEAD Construction for Poly1305:
>   000  50 51 52 53 0c 00 00 00 00 00 00 00 0c 00 00 00|PQRS............
>   016  00 00 00 00 d3 1a 8d 34 64 8e 60 db 7b 86 af bc|.......4d.`.{...
>   032  53 ef 7e c2 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7|S.~....Q)n......
>   048  36 ee 62 d6 3d be a4 5e 8c a9 67 12 82 fa fb 69|6.b.=..^..g....i
>   064  da 92 72 8b 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6|..r..q.....)....
>   080  7e cd 3b 36 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3|~.;6...-w......
>   096  28 09 1b 58 fa b3 24 e4 fa d6 75 94 55 85 80 8b|(..X..$...u.U...
>   112  48 31 d7 bc 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65|H1..?....Kz..v.e
>   128  86 ce c6 4b 61 16 72 00 00 00 00 00 00 00      |...Ka.r.......

What are that stuff at the begnning (the first 20 bytes)? The
12 byte additional data + its length?

-Ilari

---

From: Robert Ransom <[email-masked]>
Date: Mon, 27 Jan 2014 16:21:51 -0800

On 1/27/14, Yoav Nir <[email-masked]> wrote:
> Hi
>
> I've submitted the below draft about ChaCha20 and Poly1305. This document
> aims to describe the algorithms (and AGL's AEAD based on them) in such a way
> that an implementer will be able to write code that implements these
> functions with only this document as a reference. The intention is for this
> document to serve as a reference for future documents entitled "ChaCha20,
> Poly1305 and their use in XXX". I personally intend to use it for an IPsec
> document.
>
> This version -00 is quite drafty, and I'm not sure of my calculations,
> especially in Poly1305 (I used "bc" for all of them). So this document needs
> review. IMO it could also make a good undergraduate project that will also
> help to verify the examples and test vectors interspersed throughout.  More
> test vectors is another thing this document needs.
>
> This document
>
>   *   does not provide security proofs - there's plenty of that in academic
> papers, although I would be happy to link to those as informative
> references.
>   *   does not have any timing data or performance numbers. Those are very
> platform-dependent, so I don't know if they're appropriate. If they are,
> I'll be happy to include them.
>
>   1.  When converting a 256-bit buffer into a pair of numbers, k & r, Adam's
> draft takes "r" from the first 128 bits, and "k" from the following bits.
> DJB's sample code seems to go the other way. I went with Adam's way.

You're confusing Poly1305 with Poly1305-AES.  Poly1305 uses a key of
the form (r, s) to authenticate one message; Poly1305-AES uses a key
of the form (k, r), takes a unique nonce n for each message, and
derives s = E_k(n).  Dr. Bernstein's standalone Poly1305
implementations do use the first half of the key bitstring as r and
the second half as s.

>   2.  In cases where buffers are converted to integers or vice versa, we
> used little-endian order. This is different from the way it's done in (for
> example) GCM and in many protocols. It's true that some parts of the
> ChaCha20 algorithm itself are explicitly little-endian

Every multi-byte value in ChaCha and Poly1305 is little-endian.

>   3.  The lengths encoded in the AEAD construction are in bytes, whereas in

That's a good thing.  It rules out bugs like
<http://cr.yp.to/talks/2009.02.28-3/slides.pdf>.

Section 3 (‘Implementation Advice’) states that the GMP-based Poly1305
implementation given as an alternate form of the specification in the
Poly1305-AES paper runs in constant time.  As far as I can tell, it
does not.  There is a constant-time ‘ref’ implementation in NaCl, and
I have portable 32-bit and 64-bit integer-multiplication
implementations as well.

Section 4 (‘Security Considerations’) discusses the risk that the
Poly1305 key derived from a ChaCha (key, nonce) pair will collide.
This is not a risk at all.  Poly1305 keys are supposed to be chosen
uniformly at random, and most of the effort of proving Poly1305-AES
secure was in bounding the security loss caused by the fact that AES
could not produce the same value of s for two different nonces.

Robert Ransom

---

From: Yoav Nir <[email-masked]>
Date: Tue, 28 Jan 2014 07:10:29 +0000

> Should the first "Rounds" be "Quaterrounds" or something?

1, 2, 3, and 4 are quarter-rounds. Together they make up a round. In this case, a column round.

> 12 byte additional data + its length?

It is. The AAD is "50:51:52:53:0c:00:00:00:00:00:00:00". Now that you mention it, I see that I omitted to include the AAD in my example. Will fix in the next revision (coming soon)

Thanks

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Tue, 28 Jan 2014 08:19:14 +0000

> implementations do use the first half of the key bitstring as r and

Thanks. I'll rename "k" to "s" to keep it consistent.

> Every multi-byte value in ChaCha and Poly1305 is little-endian.

True. Which is why I kept it like that. But note that there is a controversy running about endianness (endianity?) on the TLS list, this time about curve25519.

> I have portable 32-bit and 64-bit integer-multiplication

Thanks. I will change that text to point to NaCl as an example.

> could not produce the same value of s for two different nonces.

AES cannot, and if we took the entire 512-bits from ChaCha, they would not repeat either. But with taking only half the bytes, they will repeat much sooner. That is why you shouldn't use the first 64 bits of an AES-encrypted counter as an IV for 3DES. You'll likely get a collision after 2^32 messages, and you'll get an unacceptably high chance of collision much sooner. 

With taking 128 bits for s out of 512, the odds are much better, so they're acceptable. That is what the section says.

Yoav

---

From: Robert Ransom <[email-masked]>
Date: Tue, 28 Jan 2014 06:55:38 -0800

> AES cannot, and if we took the entire 512-bits from ChaCha, they would not
> repeat either. But with taking only half the bytes, they will repeat much
> sooner. That is why you shouldn't use the first 64 bits of an AES-encrypted
> counter as an IV for 3DES. You'll likely get a collision after 2^32
> messages, and you'll get an unacceptably high chance of collision much
> sooner.
>
> With taking 128 bits for s out of 512, the odds are much better, so they're
> acceptable. That is what the section says.

You missed the point entirely.  The attacker does not benefit from the
repeated use of a Poly1305 key unless he/she/it knows that the key
will be repeated.  Poly1305's security relies on the assumption that
the attacker has no information at all about its keys.

Using an injective function to derive s from a nonce, as in
Poly1305-AES, does give the attacker information about Poly1305's
keys.  Dr. Bernstein's proof that the security loss due to this
information leak is tolerably small, even after 2^64 messages,
justified a paper of its own
(<http://cr.yp.to/antiforgery/permutations-20050323.pdf>).

Robert Ransom

---

From: Yoav Nir <[email-masked]>
Date: Tue, 28 Jan 2014 15:43:17 +0000

> the attacker has no information at all about its keys.

Right. Thanks. I missed that only non-predictability was required (rather than non-repeatability). 

OK. Will fix.

Yoav

---

From: Yoav Nir <[email-masked]>
Date: Fri, 31 Jan 2014 21:41:39 +0000

Hi

I've submitted version -01 of this draft.

Changes include:
 - Adam Langley is now a co-author
 - Changed nonce size to 96 bits to match other AEAD, specifically RFC 5116
 - Fixed terminology to match the non-AES version of Poly1305 (thanks, Robert Ransom)
 - Fixed example for constant-time implementation of Poly1305 
 - Fixed security considerations

Yoav