Subject: [Cfrg] AEAD Construction in draft-nir-cfrg-chacha20-poly1305

From: Yoav Nir <[email-masked]>
Date: Sun, 11 May 2014 10:03:06 +0300

Hi

Over on a TLS list there’s a thread suggesting a change in the AEAD construction for the ChaCha20-Poly1305 draft.

The current construction is this:

  AAD || length(AAD) || Ciphertext || length(Ciphertext)

Where the lengths are 64-bit LE integers. Niels Möller suggested we change it as follows:

  AAD || pad || Ciphertext || pad || length(AAD) || length(Ciphertext)

Where both pad fields are used to get the length up to a multiple of 16. 

The reason for doing this is that the Poly1305 works in 128-bit blocks. If at the end of processing you don’t have an integral multiple of 16, this can screw with alignment and reduce performance.

As an example, consider a TLS record. The TLS AAD is 13-bytes long. After concatenating the 8-byte length field, you get a full 16-byte block, plus a 5-byte remainder (I’ve read one text calling this a “radical” - I like that). We then add the ciphertext, which we have to assume is at least 4-byte aligned. So for the next block, we copy 11 bytes into the Poly1305 state, and use that with the former leftover bytes as a 128-bit integer. The next block is at offset 11 from the beginning of the ciphertext, so treating that as a 128-bit integer involves either first copying it into a properly-aligned block, or else reduced performance operations. OTOH with the new construction, there is no radical, because of the 3 bytes of padding we add, so the alignment of the ciphertext is preserved. 

Does anyone have an objection to us making this change?  Any other opinions?

We also really need more reviews of the latest version of the draft ([1]). 

One more thing. We seem to have not only running code, but actual deployment. According to ([2]) 6.25% of TLS-enabled websites support ChaCha20. 

Yoav

[1] http://tools.ietf.org/html/draft-nir-cfrg-chacha20-poly1305-03
[2] https://lists.fedoraproject.org/pipermail/security/2014-April/001810.html

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 11 May 2014 14:19:00 +0300

> Where both pad fields are used to get the length up to a multiple of 16. 

- The padding is all zeroes and not transmitted, right?
- No padding after empty AAD/Ciphertext, right?

I can't see a way that change would affect security (can't generate collisions
in internal Poly1305 polynomial).

>From draft:

>   ChaCha20 runs 20 rounds, alternating between "column" and "diagonal"
>   rounds.  Each round is 4 quarter-rounds, and they are run as follows.
>   Rounds 1-4 are part of the "column" round, while 5-8 are part of the
>   "diagonal" round:

Should this be:

ChaCha20 runs 20 rounds, alternating between "column" and "diagonal"
rounds.  Each round is 4 quarter-rounds, and they are run as follows.
Quater-rounds 1-4 are part of the "column" round, while 5-8 are part
of the "diagonal" round:

?

-Ilari

---

From: Yoav Nir <[email-masked]>
Date: Sun, 11 May 2014 15:45:57 +0300

> - No padding after empty AAD/Ciphertext, right?

Yes to both.

> in internal Poly1305 polynomial).

Agree. We wanted to make sure we’re not missing something either about security or performance. 

> Quater-rounds 1-4 are part of the "column" round, while 5-8 are part

Definitely. Thanks.

Yoav