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

[Robert Ransom <[e-mail]>]

On 1/27/14, Yoav Nir <[e-mail]> 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 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.

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
> GCM they are in bits.

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