Subject: Re: [TLS] Comments on draft-nir-cfrg-chacha20-poly1305-02

From: [email-masked] (Niels Möller)
Date: Thu, 08 May 2014 09:32:36 +0200

I'm going back to look at the draft-nir-cfrg-chacha20-poly1305-02 draft,
from an implementation point of view.

One thing that I think is suboptimal is that some buffering is required
between the chacha encryption and the mac.

First consider the case that the ad | length(ad) is a multiple of the
poly1305 blocksize (i.e., 16 bytes, and with the current draft this
would happen when length(ad) mod 16 = 8). Then for authentication, the
crypto text starts at a poly1305 block boundary. So each encrypted
chacha block, 64 bytes, lines up nicely as 4 poly1305 blocks. For a
software implementation, there's some potential for short-circuiting the
conversion from integers to octets and back. For a hardware
implementation, I think it would also be pretty straight-forward to do
those 4 poly1305 blocks in parallel if desired.

On the other hand, if cryptotext doesn't start at a poly1305 block
boundary, i.e., the general case, the cryptotext has to be buffered and
shifted around when split into poly1305 blocks. The above software
optimizations get much more complex or impossible. And I would imagine
(but I'm no hardware designer) that it adds significant complexity for a
hardware implementation.

Is this something you'd want to address? After all, high performance is
one of the primary design goals for both chacha and poly1305. The easiest
way I see is to change the formatting for authentication to

  ad | pad1 | cryptotext | pad2 | length(ad) | length(cryptotext)

where pad1 and pad2 are the minimum number of zero bytes needed to get
to 16-byte boundary. The length fields fill up a poly1305 block of their
own, and I think they should definitely use little-endian encoding,
since that's what poly1305 uses and little-endian makes it easier to
assemble the block without going via any byte representation.

There are some other possibilities, taking advantage of the fact that
poly1305 has an unambibuous encoding for short blocks. E.g, if the ad is
the single byte "a", 0x61, zero-padding produces the poly1305
coefficient 0x10000000000000061, but one could also represent it as
0x161, as is specified for a final, short, block in poly1305-aes. With
some care, I think one could even drop both length fields. What's needed
is to use the poly1305 short block encoding for the final ad and crypto
text blocks, and in addition make sure that the ad *always* is
terminated with a short block, by adding an empty block (poly1305
coefficient 0x1) between ad and cryptotext in case the ad length is a
multiple of 16.

Another minor point: The unused 32 bytes of the first chacha block
(after the 32 bytes used for the poly1305 subkeys), could they be
considered a separate (and optional) output? When chacha-poly1305 is
used in openssh, they encrypt the packet length field separately, and
they seem to be using another instance of chacha for that, with an
independent key. Which seems a bit unnecessary when there are plenty of
left over keystream bytes from the chacha-poly1305 instance they use for
the message payload.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

---

From: Adam Langley <[email-masked]>
Date: Thu, 8 May 2014 10:35:17 -0700

>   ad | pad1 | cryptotext | pad2 | length(ad) | length(cryptotext)

I think this might be a good idea, thanks!

I happen to be meeting with some hardware folks tomorrow (although not
about this) and I'll see whether they agree that this would be useful.
(Although I'm less sure about moving the lengths to the end.)

> coefficient 0x1) between ad and cryptotext in case the ad length is a

My feeling is that this is getting too complex for the resulting benefit.

> left over keystream bytes from the chacha-poly1305 instance they use for

Implementations could certainly extract this if they wished, although
I'd like to stay in the RFC 5116 framework for AEADs in the spec.

For SSH's use, I guess this would complicate their AEAD implementation
because they would need to break it up: they need to calculate the
first block to decrypt the length and then they can figure out what
the ciphertext is. Actually, if they were going to use the leftover
keystream bytes from the first block for the length then I would
imagine that they would use a separate ChaCha call to calculate it and
then, if they decrypt the length and find they have a whole record to
process, call the AEAD function, which will redundantly calculate the
first block again.

Cheers

AGL

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

---

From: [email-masked] (Niels Möller)
Date: Thu, 08 May 2014 21:02:30 +0200

> (Although I'm less sure about moving the lengths to the end.)

I think it's good to have fix alignment for the length fields (even if
that's less important than alignment for the cryptotext), and
putting both lengths together at the end seemed to make that slightly
simpler. But, e.g.,

  ad | pad1 | length(ad)

with pad1 smallest needed to get the length(ad) field to *end* at a
16-byte boundary would work fine too. I have no strong opinion here.

>> poly1305 has an unambibuous encoding for short blocks. [...]  With
>> some care, I think one could even drop both length fields.

> My feeling is that this is getting too complex for the resulting benefit.

I agree the benefit is questionable. You get the possibility to have ad
or message larger than 2^64 bytes, which isn't going be terribly useful
anytime soon. And it's cleaner in some way, but that's a question of
taste; others could argue that taking advantage of poly1305 internals is
ugly.

Regards,
/Niels