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

[Yoav Nir <[e-mail]>]

On Jan 28, 2014, at 2:21 AM, Robert Ransom <[e-mail]>
wrote:

> 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.

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

> 
>> 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.

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.

>> 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.
> 

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

> 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.

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