2.8 AEAD Construction

AEAD_CHACHA20_POLY1305 is an authenticated encryption with additional data algorithm. The inputs to AEAD_CHACHA20_POLY1305 are:

A 256-bit key
A 96-bit nonce -- different for each invocation with the same key
An arbitrary length plaintext
Arbitrary length additional authenticated data (AAD)

Some protocols may have unique per-invocation inputs that are not 96 bits in length. For example, IPsec may specify a 64-bit nonce. In such a case, it is up to the protocol document to define how to transform the protocol nonce into a 96-bit nonce, for example, by concatenating a constant value.

The ChaCha20 and Poly1305 primitives are combined into an AEAD that takes a 256-bit key and 96-bit nonce as follows:

First, a Poly1305 one-time key is generated from the 256-bit key and nonce using the procedure described in Section 2.6.
Next, the ChaCha20 encryption function is called to encrypt the plaintext, using the same key and nonce, and with the initial counter set to 1.
Finally, the Poly1305 function is called with the Poly1305 key calculated above, and a message constructed as a concatenation of the following:
- The AAD
- padding1 -- the padding is up to 15 zero bytes, and it brings the total length so far to an integral multiple of 16. If the length of the AAD was already an integral multiple of 16 bytes, this field is zero-length.
- The ciphertext
- padding2 -- the padding is up to 15 zero bytes, and it brings the total length so far to an integral multiple of 16. If the length of the ciphertext was already an integral multiple of 16 bytes, this field is zero-length.
- The length of the additional data in octets (as a 64-bit little-endian integer).
- The length of the ciphertext in octets (as a 64-bit little-endian integer).

The output from the AEAD is the concatenation of:

A ciphertext of the same length as the plaintext.
A 128-bit tag, which is the output of the Poly1305 function.

Decryption is similar with the following differences:

The roles of ciphertext and plaintext are reversed, so the ChaCha20 encryption function is applied to the ciphertext, producing the plaintext.
The Poly1305 function is still run on the AAD and the ciphertext, not the plaintext.
The calculated tag is bitwise compared to the received tag. The message is authenticated if and only if the tags match.

A few notes about this design:

The amount of encrypted data possible in a single invocation is 2^32-1 blocks of 64 bytes each, because of the size of the block counter field in the ChaCha20 block function. This gives a total of 274,877,906,880 bytes, or nearly 256 GB. This should be enough for traffic protocols such as IPsec and TLS, but may be too small for file and/or disk encryption. For such uses, we can return to the original design, reduce the nonce to 64 bits, and use the integer at position 13 as the top 32 bits of a 64-bit block counter, increasing the total message size to over a million petabytes (1,180,591,620,717,411,303,360 bytes to be exact).
Despite the previous item, the ciphertext length field in the construction of the buffer on which Poly1305 runs limits the ciphertext (and hence, the plaintext) size to 2^64 bytes, or sixteen thousand petabytes (18,446,744,073,709,551,616 bytes to be exact).

The AEAD construction in this section is a novel composition of ChaCha20 and Poly1305. A security analysis of this composition is given in [Procter].

Here is a list of the parameters for this construction as defined in Section 4 of [RFC5116]:

K_LEN (key length) is 32 octets.
P_MAX (maximum size of the plaintext) is 274,877,906,880 bytes, or nearly 256 GB.
A_MAX (maximum size of the associated data) is set to 2^64-1 octets by the length field for associated data.
N_MIN = N_MAX = 12 octets.
C_MAX = P_MAX + tag length = 274,877,906,896 octets.

Distinct AAD inputs (as described in Section 3.3 of [RFC5116]) shall be concatenated into a single input to AEAD_CHACHA20_POLY1305. It is up to the application to create a structure in the AAD input if it is needed.

2.8.1 Pseudocode for the AEAD Construction

pad16(x):
   if (len(x) % 16)==0
      then return NULL
      else return copies(0, 16-(len(x)%16))
   end

chacha20_aead_encrypt(aad, key, iv, constant, plaintext):
   nonce = constant | iv
   otk = poly1305_key_gen(key, nonce)
   ciphertext = chacha20_encrypt(key, 1, nonce, plaintext)
   mac_data = aad | pad16(aad)
   mac_data |= ciphertext | pad16(ciphertext)
   mac_data |= num_to_8_le_bytes(aad.length)
   mac_data |= num_to_8_le_bytes(ciphertext.length)
   tag = poly1305_mac(mac_data, otk)
   return (ciphertext, tag)

2.8.2 Example and Test Vector for AEAD_CHACHA20_POLY1305

For a test vector, we will use the following inputs to the AEAD_CHACHA20_POLY1305 function:

Plaintext:

4c 61 64 69 65 73 20 61 6e 64 20 47 65 6e 74 6c  Ladies and Gentl
65 6d 65 6e 20 6f 66 20 74 68 65 20 63 6c 61 73  emen of the clas
73 20 6f 66 20 27 39 39 3a 20 49 66 20 49 20 63  s of '99: If I c
6f 75 6c 64 20 6f 66 66 65 72 20 79 6f 75 20 6f  ould offer you o
6e 6c 79 20 6f 6e 65 20 74 69 70 20 66 6f 72 20  nly one tip for
74 68 65 20 66 75 74 75 72 65 2c 20 73 75 6e 73  the future, suns
63 72 65 65 6e 20 77 6f 75 6c 64 20 62 65 20 69  creen would be i
74 2e                                            t.

AAD:

000  50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7              PQRS........

Key:

000  80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f  ................
016  90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f  ................

IV:

000  40 41 42 43 44 45 46 47                          @ABCDEFG

32-bit fixed-common part:

000  07 00 00 00                                      ....

Setup for generating Poly1305 one-time key (sender id=7):

    61707865  3320646e  79622d32  6b206574
    83828180  87868584  8b8a8988  8f8e8d8c
    93929190  97969594  9b9a9998  9f9e9d9c
    00000000  00000007  43424140  47464544

After generating Poly1305 one-time key:

    252bac7b  af47b42d  557ab609  8455e9a4
    73d6e10a  ebd97510  7875932a  ff53d53e
    decc7ea2  b44ddbad  e49c17d1  d8430bc9
    8c94b7bc  8b7d4b4b  3927f67d  1669a432

Poly1305 Key:

000  7b ac 2b 25 2d b4 47 af 09 b6 7a 55 a4 e9 55 84  {.+%-.G...zU..U.
016  0a e1 d6 73 10 75 d9 eb 2a 93 75 78 3e d5 53 ff  ...s.u..*.ux>.S.

Poly1305 r = 455e9a4057ab6080f47b42c052bac7b

Poly1305 s = ff53d53e7875932aebd9751073d6e10a

keystream bytes:

9f:7b:e9:5d:01:fd:40:ba:15:e2:8f:fb:36:81:0a:ae:
c1:c0:88:3f:09:01:6e:de:dd:8a:d0:87:55:82:03:a5:
4e:9e:cb:38:ac:8e:5e:2b:b8:da:b2:0f:fa:db:52:e8:
75:04:b2:6e:be:69:6d:4f:60:a4:85:cf:11:b8:1b:59:
fc:b1:c4:5f:42:19:ee:ac:ec:6a:de:c3:4e:66:69:78:
8e:db:41:c4:9c:a3:01:e1:27:e0:ac:ab:3b:44:b9:cf:
5c:86:bb:95:e0:6b:0d:f2:90:1a:b6:45:e4:ab:e6:22:
15:38

Ciphertext:

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

AEAD Construction for Poly1305:

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

Note the four zero bytes in line 000 and the 14 zero bytes in line 128

Tag:

1a:e1:0b:59:4f:09:e2:6a:7e:90:2e:cb:d0:60:06:91