18.3.3 ChaCha20 encryption algorithm

The ChaCha20 cipher uses the ChaCha20 block function – with the same key and home, and increasing block counter – to generate a key stream block. The key stream blocks are concatenated into a key stream. The cipher subsequently XORs the key stream to the plaintext. Algorithm 8 shows the complete ChaCha20 encryption process. The notation pi … j denotes the i-th to the (j − 1)-th bytes of variable p.

Alternatively, ChaCha20 XORs the key stream block with a plaintext block before generating the next key stream block. Especially on embedded devices with constrained resources, this mode saves valuable memory. If the plaintext is not a multiple of 512 bits, the superfluous key bits from the last key stream block are discarded.

  Algorithm 8: ChaCha20 encryption process.

Require: Arbitrary size plaintext p, 256-bit key k, 96-bit nonce n, and 32-bit initial counter value ctr
 Ensure: Encrypted message c
 
 for j = 0 … ⌊len(p)∕64⌋− 1 do
 s ← chacha20_block(k,ctr + j,n)
 b ← p64j … (64j+63)
 c ← c + (b ⊕ s)
 end for
 if len(p) mod 64≠0 then
 j ←⌊len(p)∕64⌋
 s ← chacha20_block(k,ctr + j,n)
 b ← p64j … len(p)−1
 c ← c + (b ⊕ s)0 … len(p) mod 64
 end if
 return c =0

To summarize, ChaCha20 takes the following as input:

• A 256-bit key
• A 32-bit initial counter
• A 96-bit nonce
• A plaintext of arbitrary length

It outputs a ciphertext of the same length. ChaCha20’s decryption is identical to encryption: the ChaCha20 block function is used to generate the key stream, which is, in turn, XORed with the cipher text to obtain the plaintext.

18.4 Poly1305

Poly1305 is a message authentication code specified in RFC 8439 [131]. It takes a 256-bit one-time key k and an arbitrary length plaintext m, and produces a 128-bit tag used to authenticate message m.

The key k is partitioned into two parts, which RFC 8439 refers to as r and s. The pair (r,s) must be unique and unpredictable for each Poly1305 invocation. The 16-byte part r may be constant, but must undergo the following modification, referred to as clamping in RFC 8439:

• The four highest bits of bytes 3, 7, 11, and 15 must be set to 0 (in other words, these bytes must be smaller than 16).
• The two bottom bits of bytes 4, 8, and 12 must be set to 0 (in other words, these bytes must be divisible by 4).

Part s, the other 16-byte part of the secret key k, must be unpredictable. However, r and s can also be (pseudo)randomly generated for each new Poly1305 invocation.

Poly1305 pseudocode is shown in Algorithm 9. It takes a 256-bit one-time key and an arbitrary-size message m, and outputs a 128-bit tag t, which is used to verify the integrity and authenticity of message m. First, the key k is divided into r and s, and r is clamped. Next, the constant prime p is set to 2130 − 5 and the accumulator a is set to 0.

In the next step, the plaintext message m is divided into 16-byte blocks.le˙bytes˙to˙num function then reads the block, concatenated with the byte 0x01, as a little-endian number. For example, if the value of a 16-byte block of message m is as follows:

43 72 79 70 74 6f 67 72 61 70 68 69 63 20 46 6f

then the concatenated result is as follows:

6f 46 20 63 69 68 70 61 72 67 6f 74 70 79 72 43 01

and the result of assigning n the concatenated value read as the little-endian number is as follows:

n = 016f4620636968706172676f7470797243

If the message block is 16 bytes long, the above operation is equivalent to adding 2128 to the message block. If the block is shorter than 16 bytes, the above operation is equivalent to adding 2120, 2112, 2104, or any other power of 2 down to 28 that is evenly divisible by 8. Next, add accumulator a to the number n, and multiply it by r modulo p.

After the loop is finished, add the secret key s to the accumulator a, and return the 128 least significant bits in little-endian order as the tag t.

  Algorithm 9: Poly-1305 algorithm.

Require: Arbitrary length message m, 256-bit one-time key k
 Ensure: 128-bit tag t
 r ← le_bytes_to_num(k0 … 15)
 r ← clamp(r)
 s ← le_bytes_to_num(key16 … 31)
 a ← 0
 p ← (1 ≪ 130) − 5
 for i = 1 … ⌈len(m)∕16⌉ do
 n ← le_bytes_to_num(msg16(i−1) … 16i ∥ 0x01)
 a ← a + n
 a ← (r · a) mod p
 end forfor
 a ← a + s
 return num_to_16_le_bytes(a)