Encryption - ChaCha20

Chacha20 is a stream cipher derived from Salsa20 created in 2008 by Daniel J. Bernstein.

Features

Stream cipher

A stream cipher encrypts data one byte at a time compared to a block cipher which does it on a block of a specific length.

Symmetric encryption

It is most often used in symmetric encryption where the same key is used for both encryption and decryption, with in this context a key length of 256-bits.

ARX cipher

In this ARX cipher only three operations are used: add, rotate and xor ensuring constant time execution.

Hardware independent

These simple operations make the algorithm independent of specific hardware features.

Comparison with AES

ChaCha20 and AES are often used in similar contexts. AES is certainly more established and benefit from hardware implementation for peak performance however its design is more complex and prone to human error. Chacha20 simpler yet robust approach makes it an ideal candidate for situation where hardware features are lacking and performance is still expected.

Algorithm steps

Overview

secret key    --    pseudo-random       (keys)
nonce          | -> number generator -> k0..kn
block-counter --                      |
                    (message) m0..mn XOR -> c0..cn (cipher)

Pseudo-random number generator

The pseudo-random number generator generated the different key strings.

Data Layout

The data is put in a 4x4 block of 32 bits, 512 bits in total.

| x00 | x01 | x02 | x03 |
| x04 | x05 | x06 | x07 |
| x08 | x09 | x10 | x11 |
| x12 | x13 | x14 | x15 |

| "expa"  | "nd 3"  | "2-by" | "te k" |
| key     | key     | key    | key    |
| key     | key     | key    | key    |
| counter | counter | nonce  | nonce  |

Constant

The first 128 bits have "expand 32-byte k" as a constant to avoid a zeroed key producing a zeroed output.

Key

The following 256-bits contains the original secret key.

Block counter

The 64-bits after that have the block counter for jumping to different part of the file.

Nonce

And the remaining 64bits the nonce or number used once allowing the generation of different key strings while keeping the same previously mentioned 256-bits key.

Round function

The round function is subdivided in 4 quarter-rounds operating alternatively on columns or diagonals and is repeated 20 times.

// column quarter-round(a, b, c, d)
quarter-round(x00, x04, x08, x12)
quarter-round(x01, x05, x09, x13)
quarter-round(x02, x06, x10, x14)
quarter-round(x03, x07, x11, x15)

// diagonal quarter-round(a, b, c, d)
quarter-round(x00, x05, x10, x15)
quarter-round(x01, x06, x11, x12)
quarter-round(x02, x07, x08, x13)
quarter-round(x03, x04, x09, x14)

Quarter Round

The quarter round operate on 4 32-bits words updating either a column or a diagonal values using add, rotate and xor.

a  b  c  d
|  |  |  |
+<-.  |  |
.------>xor
|  |  |  .
|  |  | <16
|  |  +<-.
| xor<.  |
|  .  |  |
| <12 |  |
+<-.  |  |
.------>xor
|  |  |  .
|  |  | <8
|  |  +<-.
| xor<.  |
|  .  |  |
| <7  |  |
|  |  |  |
ˇ  ˇ  ˇ  ˇ

// definition quarter-round(a, b, c, d)
a = a + b; d = d xor a; d = d <16;
c = c + d; b = b xor c; b = b <12;
a = a + b; d = d xor a; d = d <8;
c = c + d; b = b xor c; b = b <7;

Penultimate Step

After the 20 rounds, the original block needs to be added to the result.

Last Step

With the key strings generated, they can be XOR with the message to obtain the cipher text.