Authenticated encryption

In this article, I will motivate why plain encryption does not meet the goals of modern security. I will then propose authenticated encryption as the ideal solution.

Plain encryption

Plain encryption provides confidentiality; in other words, an adversary in theory cannot recover the plaintext without knowing the secret key. However, plain encryption does not provide any way to detect if a ciphertext has been damaged or tampered with. As a result, an active adversary can tamper with data in storage and in transit. The target application will consume the modified data and react in undefined and potentially devastating ways, perhaps even leaking information about the plaintext. Let's first visualize plain encryption as a bijective function that maps plaintexts to ciphertexts. To allow for a practical visualization, consider the space of all 8-bit plaintexts (left) being mapped to the space of resulting ciphertexts (right):

 → 

The first thing to note is that the size of the plaintext space is equivalent to the size of the ciphertext space. Because this is a 1:1 mapping, each ciphertext contains only enough information to recover the original plaintext and nothing more; we have no consistent and secure way of determining whether the ciphertext has been tampered with. This means an adversary can flip arbitrary bits of a known ciphertext and always arrive at another valid ciphertext. It should be noted that both stream ciphers and CBC-mode encryption are malleable, meaning an adversary can effect local change in the plaintext via ciphertext tampering. Tampering with a CBC-encrypted block does not result in propagating corruption of plaintext blocks. The correct solution is to use authenticated encryption, which provides strong confidentiality, integrity and authenticity guarantees.

Authenticated encryption

Imagine we are able to sprinkle lots of decoy (invalid) ciphertexts amongst the valid ones, such that the valid ciphertexts are distributed throughout the space uniformly at random. To this end, we must define what it means for a ciphertext to be valid versus invalid. The way we achieve this is by employing verifiable redundancy. We need this redundancy to be a pseudorandom function of the input; in other words, if the adversary flips even a single bit of the encrypted plaintext then every bit of redundancy should flip with 50% probability. One possible method is to compute the MAC of the encrypted plaintext and use the result as our redundancy. Because the adversary does not know the secret key, she cannot feasibly predict the redundancy for a plaintext. Continuing the toy example, let's look at what happens when we add a single bit of redundancy, with invalid ciphertexts visualized as red squares:

 → 

We have effectively doubled the size and halved the density of the ciphertext space; now, 1 in 21 ciphertexts is valid. This means an adversary would have to make an average of 20 forgery attempts in order to arrive at a valid ciphertext. What if we add another bit of redundancy?

 → 

Now we've doubled the size and halved the density of the ciphertext space yet again; now, 1 in 22 ciphertexts is valid. The adversary would have to make an average of 21 forgery attempts in order to arrive at a valid ciphertext. For visualization purposes, let's perform four more doublings:

 → 
 → 
 → 
 → 

Now, 1 in 26 ciphertexts is valid, requiring an average of 25 forgery attempts from the adversary in order to locate a valid ciphertext. Another way to think of this is that for every valid ciphertext, there exists 26-1 invalid ciphertexts.

To actually make forgeries infeasible, we need enough verifiable redundancy to make the space sufficiently large and sparse. For 128-bit security, we use 128 bits of verifiable redundancy to ensure that it would take the adversary an average of 2127 attempts to land on a valid ciphertext. This would be equivalent to halving the density of valid ciphertexts 128 times in a row, resulting in a ciphertext space populated with 2128-1 invalid ciphertexts for every valid ciphertext. With a ciphertext space this sparse, it would actually be easier to just brute-force search for the 128-bit key!

As far as authenticated encryption algorithms go, we have the following inputs:

The output from the authenticated encryption algorithm is the ciphertext. The ciphertext is always larger than the plaintext due to the embedded redundancy used to achieve the sparseness property described above. Depending on the exact algorithm being used, the ciphertext may be a composition of multiple strings. In the case of Farfalle-SANE, the ciphertext is composed of the encrypted plaintext and the authentication tag. The length of the encrypted plaintext is identical to the length of plaintext and the authentication tag is the verifiable redundancy, which will typically be 128 bits.

The sender transmits the ciphertext and the receiver authenticates it by validating the embedded redundancy. If the redundancy does not check out, then the ciphertext is thrown out and an error is returned. Otherwise, the receiver decrypts to obtain the plaintext, which is guaranteed safe for consumption. The beauty of authenticated encryption is that the consuming application is given a surefire method by which to validate the ciphertext, regardless of the structure and contents of the plaintext. If a ciphertext is determined to be invalid, then the application can handle this in a consistent manner, and never has to come into contact with the invalid data. With plain encryption, the application might silently chug along with corrupted data, or possibly explode in some undefined way.

Space overhead and redundancy length

Given the vast sparseness described above, it may come as a surprise that the space overhead associated with authenticated encryption is minimal compared to the guarantees it provides. As stated above, to achieve a forgery probability of 2-t we simply need t bits of redundancy embedded within the ciphertext in general. As a concrete example, consider an application that wishes to protect arbitrary binary data in 64 KiB chunks. If we store t=128 bits of redundancy per chunk, then the space overhead is only 0.024%. If the overall size of the data is 1 GiB, then the total amount of space needed for the redundancy is only 256 KiB. For reference, here is a table of plaintext length versus space overhead, assuming 128 bits of redundancy:

Plaintext length Space overhead
0 bytes 100.00%
1 byte 94.12%
2 bytes 88.89%
4 bytes 80.00%
8 bytes 66.67%
16 bytes 50.00%
32 bytes 33.33%
64 bytes 20.00%
128 bytes 11.11%
256 bytes 5.88%
512 bytes 3.03%
1 kibibyte 1.54%
2 kibibytes 0.78%
4 kibibytes 0.39%
8 kibibytes 0.20%
16 kibibytes 0.10%
32 kibibytes 0.05%
64 kibibytes 0.02%

The key takeaway here is that authenticated encryption gives the best bang for the buck when used on a reasonable block size. In other words, trying to apply authenticated encryption on a field-by-field basis would lead to a lot of overhead. Instead, it is best to apply it to a batch of data, such as a fixed-size chunk of data or an entire record.

For some applications, 128 bits of redundancy may be overkill. For example, consider a web application with rate limiting to prevent an adversary from sending too many requests at once. In this case, it may be acceptable to have a forgery probability of e.g. 1 in 4 billion. For reference, here is a table of redundancy length versus forgery odds (rounded in favor of the adversary):

Redundancy length Forgery odds
0 bits 1 in 1
8 bits 1 in 256
16 bits 1 in 65 thousand
24 bits 1 in 16 million
(Powerball) 1 in 292 million
32 bits 1 in 4 billion
40 bits 1 in 1 trillion
48 bits 1 in 281 trillion
56 bits 1 in 72 quadrillion
64 bits 1 in 18 quintillion
72 bits 1 in 4 sextillion
80 bits 1 in 1 septillion
88 bits 1 in 309 septillion
96 bits 1 in 79 octillion
104 bits 1 in 20 nonillion
112 bits 1 in 5 decillion
120 bits 1 in 1 undecillion
128 bits 1 in 340 undecillion

It may be tempting to think that using redundancy longer than 128 bits leads to even more difficult odds for the adversary, but if we are using a 128-bit key then the key would become the weakest link in the chain. The adversary would simply target the key instead, which would be far simpler since it is an offline attack by nature (i.e., it does not require access to a decipher oracle).