Why should I use Authenticated Encryption instead of just encryption?

There are various different modes of operation for block cipher use, some of which provide "encryption" and some of which provide authenticated encryption.

Why should I use an authenticated encryption mode rather than just an encryption mode?

This question does not aim to discuss different modes of authenticated encryption vrs encryption modes (although a good answer might choose to): its aim is to justify why/when AE is better than 'plain' encryption.

-
Another answer can be found here on Security.SE as written by D.W. – figlesquidge Apr 2 '14 at 8:57

The crucial difference between plain encryption and authenticated encryption (AE) is that AE additionally provides authenticity, while plain encryption provides only confidentiality. Let's investigate in detail these two notions.

In the further text, we assume $K$ to be a secret key, which is known to authorized parties, but unknown to attackers.

Goals

Confidentiality (privacy) means that an attacker can not get any information about the plaintext $P$ from the ciphertext $E_K(P)$ except, possibly, for the length. In other words, the ciphertext looks like a random string for those who does not know $K$, even if they have some control over the plaintext. All the folklore encryption methods, from one-time pad to Enigma, provide confidentiality (under some assumptions) and only it.

Data authenticity (integrity) means that an authorized party (receiver), who possesses $K$, can check if the received data $D$ is genuine, i.e. it has been constructed only by a sender who knows $K$. The data can be cleartext or ciphertext, and there is a subtle difference what is authentic in each case: if the ciphertext is authenticated, then we know that the key owner authorized the ciphertext, but not necessarily plaintext. A traditional way to achieve authenticity is to use Message Authentication Code (MAC): $$H_K(D) = T,$$ where $T$ is called tag. In the world of public-key cryptography, the same goal is achieved with digital signatures.

What you need

A user is usually able to decide which of these properties he is looking for. For instance, if he knows that an attacker can not modify data, he may not need to authenticate it. However, if he needs both, there are secure as well as insecure ways to combine the schemes of two types. For example, a naive approach to use the same key $K$ in both schemes is dangerously insecure for most instantiations. Hence a combined scheme is recommended.

Authneticated encryption

Authenticated encryption (AE) provides confidentiality and data authenticity simultaneously. An AE scheme is usually more complicated than confidentiality-only or authenticity-only schemes. However, it is easier to use, because it usually needs only a single key, and is more robust, because there is less freedom for the user to do something wrong (see also a more elaborative answer).

As a separate feature, an authenticated encryption scheme may authenticate, but not encrypt, a part of its input, which is called associated data. For example, we may wish to encrypt the contents of an Internet packet, but we have to leave its header unencrypted but still bound to the internal data.

Security

We have not specified yet what we mean by a secure scheme. Apparently, there are several security notions, and the user has to choose among them according to the capabilities he expects from an adversary.

For confidentiality-only modes of operation the most popular security notion deals with chosen-plaintext attacks. Let $E$ be an encryption scheme. We assume that the adversary not only knows some plaintexts $P$, but is also able to choose some of them for the encryption (this is quite a practical situation). Hence, we allow the adversary to choose any plaintext for the encryption, and many times in a row. What we still require from a secure scheme is that it outputs randomly looking ciphertexts in each case: $$E_K(P_1),E_K(P_2),\ldots, E_K(P_n) \sim RandomString(|P_1|+|P_2|+\cdots+|P_n|)$$

The adversary can not distinguish the whole set of ciphertexts he obtains from an output of true random bit generator of the same length, even if the adversary repeats his plaintexts. The latter requirement implies that the scheme must be non-deterministic, and indeed, the confidentiality-only modes that satisfy these requirements are either probabilistic or nonce-based.

I note that there are folklore security notions that relate the security of the scheme with the ability to recover the key $K$ itself. This was relevant when the key could be used elsewhere, but this is far less common now, and the security notion described above is prevalent.

The security of authenticity modes is defined in a different way. Let $H_K$ be such scheme with the secret key $K$. We require that if the adversary chooses any data $D$ that has not been authenticated yet, then his chances to guess tag $T$ such that $$H_K(D) = T$$ are negligible. If he submits the pair $(D,T)$ to a verifier, he will get the answer $\perp$ (error).

Note that we have not talked about chosen-ciphertext attacks on confidentiality-only modes. These are attacks when the adversary is also able to send his own ciphertexts for decryption. While this setting also appears in practice (even though less often than chosen-plaintext attacks), the confidentiality-only schemes can not resist such attacks. To establish this sort of security, the user must turn again to the authenticated encryption.

Security of authenticated encryption schemes is defined in two parts. First, similarly to confidentiality-only modes, the adversary must be unable to distinguish the ciphertexts from random strings. Secondly, whatever fake (not created on $K$) ciphertext she sends for decryption, she is likely to get $\perp$ in response.

Therefore, the authenticated encryption modes provides you also security against chosen-ciphertext attacks if it is needed.

How it works

There are numerous integrated authenticated encryption schemes: CCM, GCM, OCB, EAX, etc, where mechanisms that establish confidentiality and authenticity are tightly coupled. The design of these schemes is far beyond the topic. However, there is a simple composed scheme, well-known as Encrypt-then-MAC, that works as follows. Let $K_1,K_2$ be secret keys, $P$ be the plaintext, $E$ be some encryption mode, and $H$ be some MAC. Then the scheme $$\Pi_{K_1,K_2}: M\rightarrow E_{K_1}(M) || H_{K_2}(E_{K_1}(M))$$ is a secure authenticated encryption scheme if $E$ is a secure confidentiality mode and $H$ is a secure authenticity mode.

Additional features of authenticated encryption schemes

Besides providing both confidentiality and authenticity, authenticated encryption schemes may have a number of additional features. No scheme has them all, hence the best choice is determined by user's settings.

• Security level. A scheme guarantees confidentiality and data authenticity only up to some bound on the amount of encrypted data or decryption requests. This bound is typically much lower than the key space, and for AES-based modes does not usually exceed $2^{64}$.

• Parallelism If a lot of resources are available, one may desire to run the encryption, decryption, or verification in parallel. The modes that use chaining (like the ones derived from the CBC encryption or the sponge construction) are difficult to parallelize.

• Online encryption. We say that a scheme is online, if it allows to encrypt immediately when the data is available, without the knowledge of its length.

• Use of patents. One of the most interesting AE schemes, the OCB mode, is patented, and is less frequently used and analyzed because of this property. It is often desirable that the scheme is patent-free.

• Tag update. Most of the schemes, with a few exceptions like GCM, require to recompute almost entire ciphertext if a small portion of plaintext is modified. If the ciphertext can be updated quickly, it would allow much faster processing of large amounts of encrypted data, e.g., hard-drive encryption.

• Use of nonces or random IVs. Nonces and random IVs lead to distinct security models, which are often incompatible (schemes might be secure with nonces, but not with random IVs of the same length, or vice versa). While the nonce uniqueness might be harder to ensure, the random IVs need a separate random-number generation mechanism and leads to the ciphertext expansion.

• Variable key, nonce, or tag length. All the three parameters are usually restricted by the application that uses an AE scheme. In turn, AE schemes have their own, sometimes incompatible restrictions. The more variability the scheme has, the more applications it suits.

• Processing of associated data. All the modern schemes allow for the authentication of associated data, which is not encrypted. Some of them, however, can not preprocess AD before the plaintext is over, which might be a penalty on the performance.

The technical report by Rogaway is a comprehensive survey of confidentiality-only modes, MACs, and some authenticated-encryption modes. It also contains all formal details about security notions.

-
Nice answer! [+1] – e-sushi Dec 9 '13 at 22:51
I also liked the answer. I could add that in many practical situations, choice of authenticated encryption scheme is largely dictated by appropriate convention or protocols. It is very common for people to frown at authenticated encryption, but in practice I've seen both custom implementations of MAC-then-encrypt and encrypt-then-MAC to have flaws than uses of authenticated encryption. This is because it requires very much attention for detail to implement the combination correctly. – user4982 Dec 10 '13 at 17:57
This is one of the most fantastic answers I've ever seen on any SE site. Nice! – L0j1k Dec 12 '13 at 6:23
In terms of additional properties, avoiding the creation of side-channels (particularly timing side-channels) has been critical in assessing the security of an AE(AD) cipher suite. As a practical matter, this means that it is possible to implement the cipher such that it runs in a time that is unaffected by the key or input plaintext. – Martin Thomson Dec 9 '14 at 23:53

When we transmit information across an insecure channel, we wish for our data to be secure.

So, what does this mean? To discuss these we'll use the standard cryptographic situation of Alice and Bob. Alice wants to send something (the plaintext) across an insecure channel (what this means will be discussed) to Bob. This channel will be listened to by Eve (an eavesdropper) and Mallory (who tries to maliciously interfere) - what this means will be discussed in due course.

Confidentiality: When Alice sends a message to Bob, we demand that an eavesdropper Eve who listens in to their communication cannot learn anything about the content of their messages.

Justification: Otherwise, Eve might learn something that Alice/Bob do not want to share

Solution: We use encryption, which transforms the plaintext into a ciphertext that (in an information theoretic sense) only contains information about the plaintext that cannot be feasibly extracted. This means that (paraphrasing Goldwasser) anything Eve can learn about the plaintext given she knows the ciphertext, she can also deduce without the ciphertext.

Even in this case, we must be careful. Just because a scheme holds up against a passive attacker (someone who just listens in to the message stream), doesn't make it strong against an active attacker. For example, consider CBC mode is used. It is secure under the IND-CPA game, which you may feel makes it secure. However, in the CCA game we allow the attacker to ask for the decryption of messages (although not the decryption of the ciphertext). What he can do, given ciphertext $c={\small IV}||c_1||\dots||c_n$ is ask for the decryption of $c'=a||c$, where $a$ is some non-empty message. This is not equal to the ciphertext, thus is allowed under the game, and by taking just the last $n$ blocks he can extract the decryption of the ciphertext.

Such an example is not as contrived as you may think, since what we model as a decryption oracle might well exist in that the attacker may be able to get strings decrypted, but that the data they can ask to decrypt might have to begin with a specific string (similar to the idea of an SQL injection).

Authenticity: When Bob receives a message, he knows it was definitely from Alice.

Justification: Otherwise, Mallory could send a message to Bob claiming it's from Alice without Bob knowing. In provable security, we're very lenient on what it means for Mallory to create a fake message - he wins if he can create any message that Bob accepts (even if its almost the same as one Alice has already sent him). There are lots of ways of doing this, such as replay, reordering or bit-flipping attacks.

Solution: To achieve authentication alone, we can use a MAC.

Authenticity and confidentiality: Alice and Bob communicate confidentially, and each message is authentic.

Justification: If a stream is only confidential (ie encryption but not authenticated encryption) then an eavesdropper might be able to modify the message in transit, even though they would not know what this was. For example, suppose Alice&Bob are using the perfectly secure One Time Pad (OTP) with secret key $k$ and message $m$:

$$A \text{ sends } c = m\oplus k \to B \\ \prec M\text{ intercepts } c\succ \\ M \text{ sends } c' = c\oplus h \to B \text{ (for some value }h) \\ B \text{ recieves } c' \text{ from M, but thinks it is} c \text{ sent from } A \\ B \text{ decrypts } m' = c'\oplus k = c \oplus h$$ This means that $B$ has received message $m'$, but he thinks it is $m$.

So, suppose the protocol is not authenticated and Mallory knows the message Alice is going to send Bob is "I agree to send £??? to account #????" for some values of ???. Even if they can't find out exactly what the account is, and so maybe they're not able to send the payment to their own account, they can change it so it's no longer Alice's account.

Solution: Authenticated Encryption!

A good article that explains the need for AE is this blog post by Matthew Green. A more technical introduction to Modes of operation is this paper by Rogaway.

-
The only encryption scheme that ensures information-theoretic security is the one-time pad. IND-CPA encryption schemes only guarantee that the information cannot be extracted from the ciphertext by a probabilistic poly-time adversary. – pg1989 Dec 6 '13 at 22:47
Ah yes that was unclearly (/incorrectly!) written. Thanks for editing it in - I was going to put it as 'contains no information <that can be extracted>' – figlesquidge Dec 6 '13 at 22:50
Actually, many "confidentiality-only" modes actually even don't give good confidentiality when attacked by an active attacker (which can modify the messages or mount chosen plaintext or chosen ciphertext attacks). Therefore these modes in practice (for a communication channel) need to be used together with some MAC even to just obtain the confidentially part. An AE mode just combines these into one. – Paŭlo Ebermann Dec 6 '13 at 23:32
@PaŭloEbermann / Anyone else: I really don't think I've written a good answer here (its friday night after all!) but I just wanted to put down some first thoughts. Feel free to add your own answers / edit this one / write your own off this. If people think my answer is "close enough" to a good one (which rereading it I don't) then you're welcome to just edit in, or reuse my words in yours. – figlesquidge Dec 7 '13 at 0:00
I think AE also provides integrity (en.wikipedia.org/wiki/Authenticated_encryption) so might want to add that as well.. – TheRookierLearner Dec 7 '13 at 17:32