Stream Ciphers

Every day, billions of messages are exchanged over the internet, including very sensitive messages like financial transactions and private user data. All this information often travels across untrusted networks, and so it must be protected from anyone attempting to intercept the communication. One way to securely exchange data is by encrypting the data before sending it over any network.

Encryption is a way to encode data so that only people who have ‘keys’ to the encoded data can ‘unlock’ or decrypt it. Depending on the type of keys used, encryption schemes can be broadly classified into two main categories. The first kind uses the same key for both encryption and decryption, and is called symmetric key cryptography. The second type is called asymmetric key cryptography, which instead uses different keys — one for encryption and a separate one for decryption.

This post is about symmetric key cryptography. More specifically, it is about how using even seemingly very simple operations like additions and multiplications is enough to secure the entire internet. To be even more specific, it is about the ChaCha20-Poly1305 cipher (an algorithm for encryption-decryption) actually works.

Caesar Cipher

One of the simplest encryption techniques includes the Caesar cipher, a type of simple substitution cipher. The message to be encrypted (called plaintext) is encoded by substituting its letters with the corresponding letters from an alphabet that is ‘shifted’ or ‘rotated’ by some amount:

Shift:

If the letters are encoded as a number determined by its position in the alphabet, then the encrypted letter for a plaintext letter m is E(m) = (m + k) mod 26, where k is the shift value. The encrypted message is often referred to as the ciphertext. Decryption has to reverse the encryption operation. So the decrypted letter for the ciphertext letter c is then D(c) = (c - k) mod 26.

ROT13 is a special case of a Caesar cipher, having a shift value of 13. The Latin alphabet has 26 letters; shifting the alphabet up by 13 positions is the same as shifting it down by 13 positions — so decryption is effectively the same as encryption. That is, for a plaintext message m and ciphertext c:

E(m) = (m + 13) mod 26 = (m - 13) mod 26 = c
D(c) = (c + 13) mod 26 = (c - 13) mod 26 = m

The only difference between encryption and decryption is the domain of the operators. While one operates on plaintexts, the other operates on ciphertexts — but that difference is purely in semantics.

Shift:

The shift parameter in the Caesar cipher determines how a message gets encrypted and decrypted — it acts as a ‘key’ for encrypting and decrypting the data. Only parties who have the knowledge about the keys can decrypt the messages encrypted with that key. While this is the main goal of symmetric encryption, the Caesar cipher is not a very good way to achieve this goal. This is because single-alphabet substitution ciphers like the Caesar cipher are not secure. They can be easily broken using brute force and frequency analysis attacks.

One-Time Pad

In the Caesar cipher, all the letters of the plaintext are shifted by the same amount, which is determined by a single-valued key. However, it can be argued that using separate shift values for each letter is more secure. The Vigenère cipher does exactly that — it is a cipher that employs multiple shift values for encrypting messages. The key here is multi-valued, and the each letter of the plaintext is shifted based on the values of the key. When the key is shorter than the message, the key is repeated until it matches the length of the message.

Key:

Again, decryption involves the reverse operation — subtracting the key values from the ciphertext.

We started with an assumption that using multiple shift values is somehow more secure than a single value. To understand why, imagine some random plaintext message. The distribution of letters in message would likely follow the frequency distribution of letters used in the language. Now imagine if the plaintext letters are shifted by a singular value. The distribution of the ciphertext would be similar to the plaintext, except only shifted by the value amount.

From the ciphertext distribution it easy to understand why a single-alphabet substitution cipher (eg. Caesar) is so insecure. Since each ciphertext letter corresponds to a single plaintext letter, it is very easy to break the encryption if any corresponding plaintext letter is found — and it can be found easily by trying to match up the frequency distributions.

But now imagine if there are now two different shift values. Half of the plaintext letters would get shifted by one value, and half of them by the other value. The distribution of the ciphertext would look slightly more ‘diffused’, and each ciphertext letter would now correspond to two possible plaintext letters.

So, using more shift values spreads the likelihood of a ciphertext letter corresponding to a plaintext letter over more letters. It means using more shift values increases the range of plaintext possibilities, and thus make it less likely to correctly guess the plaintext from the ciphertext.

Key:

Judging from the above example, one might assume the key only needs to be 26 values long (or the size of the chosen alphabet) to achieve maximum diffusion. Except it is not the case; the graph is misleading because it does not show the inherent structure of the entire key (and ciphertext) and only shows the aggregate values — the bars represent the total aggregated frequencies, but fail to show anything about the position of the keys and ciphertext.

Eagle-eyed readers may have already raised some eyebrows in the previous example that used keys of length two. If an attacker knew that the key repeats every n letters, then instead of a ciphertext letter corresponding to multiple possible plaintext letters, it would map to only one possible letter — ciphertext letters that appear after every n letters will all have the same shift value (since the key also repeats), and hence the ciphertext letters will have a singular, definitive mapping.

And finding the original key is not particularly difficult. If the length of the key is somehow known, then n separate distributions can be constructed — one distribution for all the letters appearing after every n intervals in the ciphertext. These n frequency distributions can be viewed as n Caesar ciphertexts, all of which can be individually broken using the same method as the frequency analysis attack using a single distribution.

However this attack is not possible if the key does not repeat. In fact, removing repetition or any structure from the key makes it impossible to break the cipher, other than by brute-forcing all combinations. This effectively means that entire key must be random. Using a key which is at least as long as the plaintext, and is truly random will be perfectly secure. The proof is somewhat simple — it is impossible to exploit structures to find keys if there is no structure; every key is as likely as all the other possible combinations.

Key:

This cipher scheme is called the one-time pad. The only information that can possibly be leaked is the maximum length of a message.

But there is an important caveat: The one-time pad is only secure if the key is kept secret and is never reused. The moment the same key is used more than once, all its security benefits vanish. To understand why, consider two different messages that are encrypted with the same key. An attacker can subtract the ciphertext of one message from the other to find the plaintext (or more accurately, the differences between the plaintext). For example, if m1 and m2 are messages that are both encrypted with key k then:

c1 = (m1 + k) mod 26
c2 = (m2 + k) mod 26

Subtracting ciphertext c1 from c2 eliminates k and leaves m2 - m1 (mod 26). It might feel like the plaintext difference would be a garbled mess, but even the differences in plaintexts can expose structures within the individual plaintexts — which might end up leaking information about the original plaintexts.

It also goes without saying that the key must be kept secret. It should only be known by the communicating parties, and no one else.

Vernam Cipher

Another thing to note for the one-time pad is that the cardinality of key symbols must be equal (or greater than) the cardinality of the plaintext symbols — ie. if the size of alphabet of the plaintext is 26 symbols (letters) then the key must also contain at least 26 symbols, which map all the plaintext symbols to all the ciphertext symbols with equal probability. If the cardinality of the key is larger than the plaintext, then it must be ensured that the surplus key symbols do not break the uniform randomness constraint. All of the plaintext symbols must still map to the all ciphertext symbols with equal probability.

If the cardinality of key is smaller than the plaintext, then some of the ciphertext symbols are unreachable for a given plaintext symbol. For example, if the key cardinality is two (eg. the key values are 1, 2), but the plaintext cardinality is 26 (eg. English alphabet), then 24 of the letters are always unreachable for a given plaintext symbol. That is, ‘A’ will never map to any letter other than ‘B’ or ‘C’ (when the key values are 1, 2). This, as shown earlier, is not secure.

Key Cardinality:

So the key cardinality should never be smaller than the plaintext cardinality, and ideally both should be of the same size. The Vernam cipher is a type of one-time pad, that uses keys and plaintexts of cardinality two (binary plaintexts and binary keys). That is:

c = (m + k) mod 2
m = (c - k) mod 2

Where c is the ciphertext for the binary plaintext message m encrypted using binary key k. The padding (addition/subtraction) operations are performed using modulo-two arithmetic. Consequently, the ciphertext c is also binary.

An interesting property of modulo-two arithmetic is that addition and subtraction is the same operation, so similar to ROT13, the same operation can be used for encryption and decryption.

c = (m + k) mod 2
m = (c + k) mod 2

Key:

The Vernam cipher is useful because computers naturally store messages in binary, and more importantly, modulo two addition can be performed very quickly and efficiently by processors using XOR gates. So ciphertexts can be generated by combining the plaintext with a key using the XOR operation.

c = (m + k) mod 2 = m ^ k
m = (c + k) mod 2 = c ^ k

Key:

The binary key of the Vernam cipher is referred to as a keystream, as it is a stream of bits that is XOR’ed with the stream of plaintext bits to generate the ciphertext stream.

The Vernam cipher keystream must have the same properties as the one-time pad key to have the same security guarantees. It must be at least as long as the plaintext stream, and should be truly random. The key must also never be reused as otherwise it can leak information about the plaintext.

So the keystream, just like the one-time pad, must be kept secret and truly random, and must never be repeated for it to be perfectly secure.

ChaCha20 Cipher

Although the Vernam cipher enables extremely fast and efficient encryption/decryption (since it is just a single XOR operation), and is perfectly secure, it is impractical as it relies on the secure and secret distribution of keys. If a key (which is at least the size of the message) can be securely transmitted, it makes more sense to simply send the message itself instead.

The impracticality arises from needing to exchange keys that are (at least) as long as the message. If there was a way to compress the key to a more practical size, the Vernam cipher would have been a lot more useful. Fortunately, there are ways to do this — well to be more accurate, there are ways to generate identical streams of random bits from identical seed (initial) values. So the communicating parties can exchange only the small seed values and generate the same keys, instead of exchanging keystreams that are as long as the plaintext. This makes this cipher a lot more practical.

The bad news: If the same keystream is generated from the same initial value, then the keystream is essentially tied to the seed value — it is not really random, it is deterministic. But here’s the good news: The key does not need to be truly random. It needs to be truly random for perfect security, but sometimes good-enough security is more than sufficient especially if it makes the cipher practical and actually usable.

So what differentiates perfect security from good enough security? What differentiates a truly random bitstream from a pseudorandom bitstream? The first question is easier to answer; the second will be discussed later. For the first question: If perfect security is defined as impossible to break, then ‘good enough’ security can be defined as the level of security that requires an unfeasibly large number of brute-force attempts to break the cipher, making any practical attack effectively impossible.

This ‘good enough’ security can be ensured if the generated randomness has no hidden patterns that can be exploited or reverse-engineered; and by ensuring all the possible values for the seed is big enough to deter brute-force attacks. For example, a one-way function that takes a 256-bit number as its input and then outputs a random bitstream for each of its possible inputs can be considered secure enough — if the random stream generator function is secure. This is because brute-forcing a hundred quattorvigintillion seed values (2^256) is practically infeasible.

This is the central idea behind the ChaCha20 cipher. In this cipher, a 512-bit seed is used for generating (pseudo)random keystreams — multiple rounds of ARX (add-rotate-XOR) operations are performed on the initial seed value to generate streams of pseudorandom values. These streams are then used to pad (XOR) the plaintext to get the ciphertext, and vice versa — padding the ciphertext to get the plaintext.

This ChaCha20 function f is fundamental in transforming the initial seed to a stream of random bits. But to understand how this function works, we first need to understand how exactly are the additions, rotations and XORs performed on the seed.

ARX Operations

In ChaCha20, a pseudorandom stream is generated from a 512-bit seed by first dividing the seed into a 4x4 block of 32-bit words.

These words are then rotated, added and XOR’ed with each other in a specific manner to generate a random block from the seed block. The sequence of addition, rotation, and XOR operations is strictly defined. The primary operation in this sequence is the quarter round function — it operates on four words at a time, and is defined as:

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

Where a, b, c, d are four 32-bit words from the 4x4 block. And a += b means adding a and b, and storing the result in a; b ^= c means XOR’ing b and c, and storing the result in c; d <<<= 8 means left rotating d by 8 bits. Performing the above twelve operations completes one quarter round; performing four quarter rounds makes up one full round.

Twenty of these rounds are performed in ChaCha20 — these twenty rounds are divided into odd and even rounds. On odd rounds (the first round, third round, fifth round, and so on), the quarter rounds are performed on the four columns of the block. While on even rounds (the second, fourth round etc), the quarter rounds are performed on the four left diagonals of the block.

Perform Quarter Round Reset
Round: 0

These operations effectively ‘diffuse’ the bits of the words with each other, generating a pseudorandom 512-bit block. However this pseudorandom block is not the final keystream. This block is first added to the original block, and only does it become (a part of) the final pseudorandom keystream.

The addition step is important since the mixing rounds are invertible. That is, it is possible to apply the reverse operations on the pseudorandom block to get the seed block. The ARX operations and this addition step together, however, make it practically impossible to derive the original seed block from an output pseudorandom block.

Counter & Nonce

So the ChaCha20 operations transform a 512-bit seed block to a 512-bit pseudorandom block. But these 512 random bits can only be used to encrypt 512 bits of a plaintext message. What is actually required, is a long stream of pseudorandom bits — a lot more than just 512 pseudorandom bits.

To encrypt longer messages, more pseudorandom blocks are required. And these blocks must not repeat and must not be related to each other. If attackers find some correlation between the pseudorandom blocks, they can leverage it to find patterns in the ciphertext and possibly even break the cipher.

However, producing different blocks from the same initial state block is impossible. Since the ARX operations are deterministic, the same seed blocks will always produce the same pseudorandom blocks. The only way to generate different pseudorandom blocks is by altering the seed block itself.

Luckily, ChaCha20 already defines a standardized of altering the seed block to generate new pseudorandom blocks — the last four words (128 bits) of original 512-bit block are reserved for the sole purpose of modifying the initial state block, and generating new pseudorandom blocks. The four words are logically separated into two parts — a counter and a nonce. These are incremented to generate new pseudorandom blocks.

Decrement Counter Increment Counter

Incrementing the counter changes the seed block — sometimes, by only a single bit. But because of the diffusion introduced by the ARX operations, even a single bit difference cascades through the rounds and completely changes the output pseudorandom blocks. The output blocks are practically completely random and unrelated, preventing attackers from inferring correlations and breaking the cipher.

Perform Quarter Round Reset
Round: 0

The new output blocks generated by incrementing the counter together form a stream of pseudorandom bits — which can be used to encrypt data longer than just 512 bits.

To encrypt longer messages, the counter is incremented and new pseudorandom blocks are generated. This way, the counter also keeps track of the current block’s position in the keystream. To encrypt/decrypt a specfic section of a message, only that specific part of the keystream can be generated — by using the counter values corresponding to that portion of the keystream.

Decrement Counter Increment Counter
Counter:

However there is an issue when the counters represent/rely on the positional information of a message. For newer messages, the counter will reset to zero and start repeating values. So the initial blocks will be identical, even for different messages. This means the pseudorandom blocks and keystreams will also be identical.

As shown earlier, encrypting different data using the same keys (pseudorandom blocks, or pseudorandom keystreams) is very dangerous as it leaks plaintext data.

Decrement Counter Increment Counter

A simple solution to ensure seed blocks do not repeat is to use another ‘counter’ to keep track of messages as well. Instead of just having one counter that tracks positions of blocks inside messages, there can be another counter that tracks messages itself — this counter increments for every new message.

This way, even when the ‘positional’ counter resets and repeats for newer messages, the seed blocks still remain unique — since the new ‘message counter’ now has different (incremented) values. To prevent identical seed blocks and keystreams, this message counter must never repeat. This new ‘counter’ is called the nonce — Number used Once. Using the nonce only once ensures that keystreams are never identical.

The counter and nonce provide a simple yet powerful way to transform the seed block to generate enough pseudorandom bits to encrypt lots of really long messages — all from a single seed block.

Bit Constants

While extremely rare, there is a case when the entire seed block is all zeroes. Diffusing bits that are all zeroes with each other does not generate a pseudorandom block, instead it simply produces an all-zero block. Encrypting data with the all-zero block is dangerous as it does not encrypt the data at all since m ^ 0 = m.

To prevent the all-zero block, certain bits of the seed block are always non-zero. More specifically, the first four words (128 bits) of the seed block are specific constants, so the seed block is never all zeroes.

The constant values avoid the all-zero block, but really more importantly these constants introduce asymmetry if their values are chosen wisely. ChaCha20 has some rotational symmetry — different seed blocks can generate the same, rotated versions of the output block, if the seed blocks are specific rotated versions of itself. Having fixed asymmetrical values for certain words eliminates the possibility of this shift/rotate structure, preventing attackers from exploiting relationships between related seeds.

The constants in ChaCha20 do introduce asymmetry, and have the values 0x61707865, 0x3320646e, 0x79622d32, 0x6b206574. There is nothing special about these constants as they simply spell “expand 32-byte k” in ASCII in little endian.

Shared Key

The constants do not need to be exchanged securely; these are public and standardized. Similarly, exchanging the counter and nonce values securely would be very impractical as keep changing frequently. And in fact, in ChaCha20, these do not need to be securely exchanged either — the cipher is still secure.

The cipher remains secure because even if the constants, the counter and the nonce are non-secret, the remaining eight words (256 bits) are not. Attackers will need to brute force an average of 2^255 possible combinations to find the original seed block — which is completely impractical. These remaining eight words are used for the ‘actual key’ and need to be exchanged securely between the communicating parties.

So two parties need to securely exchange only one 256-bit key to be able to encrypt and decrypt virtually unlimited number of messages. The other values do not need to be exchanged, or at least exchanged securely. The values of the counter always increment the same, predictable way — they do not need to be shared. The constants are public. The nonce, which varies per message, is needed to generate the correct keystream, but does not need to be securely transmitted.

In effect, just the key and nonce need to be shared, and moreover only the key needs to be securely transmitted.

All of this is ChaCha20 — a practical adaptation of the one-time pad (or more specifically the Vernam cipher). Rather than requiring an entire keystream to be shared securely, it only requires a 256-bit key to be shared securely. However, this practicality comes at the cost of perfect security, as the generated keystreams are not truly random. This tradeoff is acceptable though, as the cipher is still reasonably secure.

Authenticated Encryption

While ChaCha20 provides a way for securely encrypting and decrypting data, it does not have any built-in mechanism to prevent attackers from tampering with the ciphertext itself. In fact, if an attacker knows a certain message always appear at a certain position in the plaintext stream (eg. the payment amount information always appearing at some fixed offset in a transaction message), then attackers can modify that specific section of the ciphertext to modify the same section of the plaintext as well.

For example, an attacker might know the message contains “…owes $100…” at a specific section in the plaintext. They can XOR “…owes $100…” with “…owes $999…” , and then XOR it with the corresponding section of the ciphertext. When the receiver decrypts the modified ciphertext, they would get the tampered “…owes $999…” message.

ChaCha20 is not designed to detect nor protect against tampered ciphertexts. Because bit-flipping attacks can render the entire cipher useless, ChaCha20 is usually paired with an authenticator to detect tampered ciphertexts. This type of encryption scheme that simultaneously encrypts a message as well as validates its authenticity is referred to as authenticated encryption.

Hashing

There are multiple ways to verify the authenticity of a message. A simple (but naive) way is to very simply compare the sum of all the bytes of the ciphertext — comparing their checksums. The checksum is usually calculated using modular arithmetic to prevent the numbers from getting too big. The checksum of a ciphertext with bytes C1, C2, … Cq and some relatively big integer p is:

(C1 + C2 + ... + Cq-1 + Cq) mod p

Current Byte Block:
Checksum:

Goto Next Byte Block

A sender can encrypt a message, calculate its checksum, and then send the encrypted text along with its checksum. The receiver calculates the checksum of the ciphertext, and then can compare it with the one presented by the sender to verify the authenticity of the ciphertext.

However it is not secure at all. Attackers can modify a few bits of the ciphertext and still have a very high probability that the checksum of a modified ciphertext will produce the same checksum as the original ciphertext. For example, both the messages “…owes $209…” and “…owes $920…” will have the same checksum — since their bytes sum up to the same value.

Even in cases when the checksums differ, attackers can easily recalculate the checksum of the modified ciphertext, and send the altered checksum with the altered ciphertext.

For the authenticator to be secure, the checksum must not output same (colliding) values if its input message is different. In other words, a checksum must have adequate collision resistance. Checksums also need to be secure against forgery attempts.

Both of these problems come up because checksums are calculated by naively adding all the bytes of the plaintext message — this makes it trivial to recalculate the checksum since changes to the ciphertext result in predictable changes to the checksum. Collisions are also very likely because byte positions do not matter, and there is a high probability that small changes cancel each other out, leaving the checksum completely unchanged. Ideally, checksums should have very different values even for small input changes. Even better, they should output random-ish values to prevent attackers from finding the relationship between the checksum and the ciphertext and then using that information to create forged checksums.

A simple way to make the checksums collision resistant and sensitive to small changes is by performing a multiplication after every addition. This causes small changes to be multiplied, literally — and makes it difficult to predict how a checksum changes when its input changes (when the multiplier is not known, at least). Performing the multiplications and additions over a prime field further reduces the probability of collisions.

Modulus:
Multiplier:

Since calculating the checksum now involves repeated multiplication and addition, it is basically equivalent to evaluating a polynomial, where its coefficients are the bytes of the message. That is, the checksum for a message having bytes C1, C2, … Cq is:

(C1·x^q + C2·x^(q-1) + ... + Cq-1·x^2 + Cq·x^1) mod p

Current Byte Block:
Checksum:

This is a type of polynomial rolling hash, and the checksum here is called a hash. These hashes have much lower chances of collisions than the simple checksum method, for an integer multiplier x and a big prime p.

While the rolling polynomial hashes make collisions a lot less likely, it does not solve the forgery issue. If an attacker know the multiplier x they can easily recalculate the hash of a modified ciphertext and send that instead. In fact, attackers can find the multiplier rather easily — the multiplier is simply the root in the polynomial hash expression, which can be calculated using existing algorithms.

The above attack relies on being able to find the root of the polynomial. One way to block these type of attacks is by masking the constant term (the hash) to prevent the attackers from finding the root. That is, for a polynomial [hash] expression:

(C1·x^q + C2·x^(q-1) + ... + Cq-1·x^2 + Cq·x^1) ≡ y (mod p)

The constant y (the output hash) is needed to quickly solve for the root. So, if the hash values are not made public, attackers will not be able to find the the root efficiently. Without the multiplier (the root), attackers cannot forge hashes for modified ciphertexts, while the probability of a collision remains close to zero.

A way to mask the hash value is to simply encrypt them before sending it. This can be done using a one-time pad — padding the real value with a random value. In effect, the value that is sent to the receiver is then:

(H(C, x) + k) mod N
H(C, x) = (C1·x^q + C2·x^(q-1) + ... + Cq-1·x^2 + Cq·x^1) mod p

Where the addition of k over mod N acts as the one-time pad, used for padding and masking the polynomial hash H(C, r). So the complete hashing scheme now takes in two secret values: a secret multiplier x and a secret one-time pad k.

Current Byte Block:
Keyed Hash:
Padded Hash:

Goto Next Byte Block

Since the hash is now masked, the actual value of the constant term in the polynomial is hidden from attackers, preventing them from finding its root to create forgeries.

There aren’t many ways to break this hashing scheme. In fact, it is provably secure for a big enough prime p and modulus N, and for a random pad k sampled from a finite field of size N. In short, the above hashing technique prevents attackers from tampering with ciphertexts — or more accurately, it ensures that any tampering with the ciphertext is easily detected.

But the above solution does not actually ‘solve’ the problem. It simply shifts the problem from the secure exchange of the hash to the secure exchange of the multiplier and the one-time pad. In other words, this method relies on the secret exchange of the multiplier and the one-time pad — data that is at least as long as the hash itself (since the one-time pad needs to be at least as long as the hash; the multiplier is ideally of the same size as well). Which then begs the question: Why not send the hash secretly, instead of secretly sending the one-time pad and multiplier?

This is a very valid question in isolation, but as discussed, these authenticators are often paired with stream ciphers — which usually have an already existing mechanism for generating pseudorandom numbers from a small seed. So, the seed used for encrypting plaintexts can also be used to derive a random multiplier and one-time pad; there is no separate need for securely exchanging the multiplier and pad.

So, the ciphertexts and the (padded) hashes can be sent publicly without leaking the original plaintexts, and making forgeries infeasible — as long as the initial seed values are exchanged securely. But how exactly do these hashes integrate with ChaCha20?

ChaCha20-Poly1305

A widely used polynomial rolling hash function is Poly1305. It uses the same construction as the hash functions outlined above, and is frequently used alongside ChaCha20 as a ciphertext authenticator. As its name suggests, the hash is evaluated over a prime field with modulus 2^130 - 5. The hash, if used as an authenticator, is then also masked using a one-time pad; and then (usually) reduced to 128-bits. That is:

H(C, x) = (C1·x^q + C2·x^(q-1) + ... + Cq·x^1) mod 2^130-5
T = (H(C, x) + k) mod 2^128

Where H(C, x) is a polynomial rolling hash, in which the bytes of the ciphertext C are as its coefficients, and x is the multiplier — evaluated over the prime field 2^130-5. Meanwhile k is a one-time pad (a random number). The tag T is the modular addition of the two numbers over the integer 2^128.

Current Block:
Keyed Hash:
Padded Hash (Tag):

Generate New KeysGoto Next Byte Block

If you observe the illustration above, you will notice a few things. First, the coefficients of the polynomial C1, C2, … Cq are not 16 bytes (128 bits), but 17 bytes. Poly1305 defines interpreting the 16-byte ciphertext chunks as 17-byte coefficients by appending a byte with value 0x01 to each of the 16-byte chunks of the ciphertext. If the final chunk is smaller than 16 bytes, then 0x01 is appended to the last chunk, and the remaining bits are zero padded to 17 bytes.

Second, the 128-bit multiplier has some structure. Poly1305 specifies the multiplier as a 16-byte integer where the top four bits of bytes of r[3], r[7], r[11], and r[15], as well as the bottom two bits of r[4], r[8], r[12] are all zeroes. This is not for security. In fact, this sacrifices some security, but this restriction was chosen (alongside the prime 2^130 - 5), because it makes calculations faster.

The rest of Poly1305 is similar to the padded hash function described above. The output from the polynomial evaluation (the multiplications-additions of the ciphertext with r) is reduced using modulo 2^128. A 128-bit (16-byte) one-time pad s masks the polynomial output, and results in a 128 bit tag or MAC.

Poly1305 is typically used alongside ChaCha20, and there is a specification defining how the two interact. The ChaCha20-Poly1305 specification defines reserving the first block of the ChaCha keystream (block with counter value zero) to derive r and s. The rest of the keystream (generated using non-zero counter values) can be used for encrypting the plaintext message.

So a single 256-bit ChaCha key is enough for both encryption and authentication — it derives both the pseudorandom keystream as well as the secrets for Poly1305. Since the ChaCha keystream is pseudorandom and non-recurring across different messages, the pad s of Poly1305 inherits these properties, and thus remains secure.

It is worth noting that there are slight differences between ChaCha20 and the ChaCha20 used in ChaCha20-Poly1305. Unlike ChaCha20, the initial state in ChaCha20-Poly1305 uses a 32-bit counter and 96-bit nonce instead of a 64-bit counter and 64-bit nonce.

This allows more messages to be encrypted using the same key, albeit shorter ones. But it is not a problem, since a 32-bit counter still allows for encryption of messages up to 256 GiB in size.

Associated Data

Sometimes ciphertexts can be paired with some associated plaintext data, which do not need or should not be encrypted, but still need to be verified — data such as message timestamps, addresses, protocol versions, etc. This cleartext data is often sent alongside the ciphertext, and both are authenticated using a single MAC. This additional data is called associated data, and the authenticated encryption scheme that authenticates the associated data alongside the ciphertext, is referred to as authenticated encryption with associated data, or AEAD.

ChaCha20-Poly1305 can authenticate ciphertext C along with some associated data AD by concatenating together, and treating them as a single unit to generate the MAC. The ChaCha20-Poly1305 specification defines AD and C to be separately padded to make their total sizes an even multiple of sixteen bytes. The padded AD and C as well as two other 64-bit fields, len(AD) and len(C), are concatenated. Poly1305 then produces the MAC of this concatenated string.

This is basically the entirety of ChaCha20-Poly1305, a stream cipher used for encrypting messages, and authenticating the encrypted messages along with optional associated data. It used in TLS, SSH, WireGuard, and other protocols. It is likely that the data on this webpage was encrypted with ChaCha20 and then verified using Poly1305.

The next section is a brief discussion on the security of ChaCha20-Poly1305. Feel free to skip to the end.

Security Guarantees

The probability that attackers cannot decrypt a given ciphertext relies on the security of ChaCha20. Meanwhile the possibilities of forgeries depends on the security of Poly1305, as well as ChaCha20.

Poly1305 Security

Since the output of Poly1305 is combined with a pseudorandom pad, it is as secure as the algorithm used to generate pseudorandom number. However, it does not imply that it is perfectly secure if the pad is purely random — since collisions are still possible as the of the size of the MAC is finite.

Consider a prime field GF(p), taken as x mod p where x ∈ ℤ and p is prime. Then, for some polynomial of degree one, e.g. a·x = h where a,x,h ∈ GF(p) — there exists, at most one solution or root for x. The probability that x will produce h for a given a is 1/n, where n is the number of all possible values for x. That is, n = p.

Coefficient (a):
Result (h):

For a polynomial of degree two, e.g. a·x^2 + b·x = h, there can be at most two solutions for x. The probability that x produces h for a given pair a,b is at most 2/n. Where n is the total number of possible values for x. Here again, n = p.

Coefficient (a):
Coefficient (b):
Result (h):

Similarly, for a q degree polynomial, e.g. C1·x^q + C2·x^(q-1) + … + Cq·x^1 = h, there are at most q number of roots for x, such that x ∈ GF(p). The probability that x produces h for some given coefficients is, at most q/n — where n is again the number of possible values for x.

If deg(f(x)) = Q
=> x can have at most Q roots

Now assume a message m has a polynomial hash h. The probability of another distinct message m’ having the same hash digest h will then depend on the on the degree of its polynomial. The polynomial in Poly1305 is of the form C1·r^q + C2·r^(q-1) + … + Cq·r^1. The coefficients of the polynomial are constructed from 16-byte chunks of a message, and thus, the degree of the polynomial is ⌈L/16⌉ — where L is the length of the message. So the probability of a message m’ having the (same) hash h is at most ⌈L/16⌉/n.

If bytes(m) = L
=> deg(f(x)) = ⌈L/16⌉
=> x can have, at most, ⌈L/16⌉ roots

Since the indeterminate of the polynomial in Poly1305 r is a 128-bit number with 22 bits always set to zero, the total number of possible values for r is 2^106. Thus, the probability of a message having a specific hash is at most ⌈L/16⌉/2^106.

Let m != m' be two messages of length up to L bytes
If h(m) ≡ h(m') (mod p)
=> h(m) - h(m') ≡ 0 (mod p)
=> f(x) = h(m) - h(m')
=> deg(f(x)) = ⌈L/16⌉
=> x can have, at most, ⌈L/16⌉ roots

However, the polynomial is evaluated in GF(p) — the result is h ∈ [0, 2^130 - 5), while the hash in Poly1305 is designed to be of 128 bits. So h is reduced modulo 2^128. Discarding two bits from h causes some outputs to be congruent to others. More specifically, there are eight congruent values (mod 2^128) for H(m) - H(m’) ≡ 0.

This increases the differential probability to 8·⌈L/16⌉/2^106, at most — because there are now eight times as many possibilities for two messages to have the same hash.

Now if D forgery attempts are made, then the probability of a single successful forgery is at most D·8·⌈L/16⌉/2^106. The probability of forgeries is independent of the number of messages authenticated — if the pad is uniformly random.

However, the Poly1305 pad in ChaCha20-Poly1305 is generated using a pseudorandom ChaCha20 block — it is not guaranteed to be truly uniformly random. If the probability of distinguishing a ChaCha20 block from a truly random keystream is δ, then the probability of a successful forgery is, at most δ + D·8·⌈L/16⌉/2^106.

ChaCha20 Security

The randomness of the ChaCha20 output stream determines its security, as well as the security of Poly1305. This can be tested statistically.

Changing the initial state of a ChaCha20 block (even by a single bit flip) should ideally create a new uniform random block of bits. That is, the individual probability of all the bits of the output block flipping should be half — on average, half the bits should flip for a change in the initial state. Or more specifically, the number of bit flips due to changes the initial state should form a binomial distribution centered around half the bit length of the output block.

Random Block Thousand Random Blocks Reset

Empirical evidence suggests that it is the case. ChaCha20 generates blocks that appear uniformly random. Evaluating the randomness analytically is much more difficult however, because the interaction between the bits of the block quickly grows complex with each round. While there are ways to measure the avalanche effect — small changes flipping roughly half the bits, there is no proof that ChaCha20 blocks blocks can be distinguished (or not) from truly uniform random bitstreams.

There are however other ways to test its security — for example, using linear, differential or rotational cryptanlysis. ChaCha with six rounds has been broken, but there have been no successful attacks on twenty rounds of ChaCha.

ChaCha20-Poly1305, therefore is generally considered secure.

Other Ciphers

Although other stream ciphers exist, ChaCha20 is the most widely used cipher currently. Other types of symmetric encryption, such as block ciphers are also widely used for encryption and decryption. These generally use substitution and permutation boxes to diffuse the data blocks in place, instead of generating a keystream.

Another detail that was glossed over was the secure exchange of the 256-bit keys. This entire cryptosystem relies on the secure distribution of the shared keys. It is achieved using asymmetric key cryptography. This field of cryptography is quite different from the ciphers mentioned above — usually relying on the properties of number theory and group theory instead — but is equally interesting.

References

• Daniel J. Bernstein: ChaCha, a variant of Salsa20
• Daniel J. Bernstein: The Poly1305-AES message-authentication code
• Moxie Marlinspike : The Cryptographic Doom Principle
• IRTF RFC 8439: ChaCha20 and Poly1305 for IETF Protocols