# Secure MAC and secure encryption schemes combined to form insecure Authenticated Encryption?

I'm reading up on Authenticated Encryption and can't really wrap my head around how a generally secure MAC and a generally secure encryption scheme can be combined into an insecure AE scheme, such as in MAC-and-Encrypt. I'd be fine with just having links to sources so that I may read up more about it on my own.

1. Consider MAC-and-encrypt with a cipher of AES-CTR using sequential nonces, and a MAC of HMAC-SHA256 on the plaintext of the message.

Obviously these are respectively a secure cipher and MAC, but send the same plaintext twice, and the adversary learns that it's the same plaintext. (Authenticate the nonce too, and this particular problem goes away, though.)

2. For a 128-bit string $m$, define $E_{k_1}(m) = \operatorname{AES}_{k_1}(m)$, and $M_{k_2}(m) = \operatorname{AES}_{k_2}(m)$.

Obviously these are respectively a secure cipher and (as a PRP approximation to a PRF) a secure MAC, but if $k_1 = k_2$, rather than using independent keys for MAC and encrypt as you should (or keys apparently independent, derived from a master key by a PRF, e.g. HKDF), bad things will happen when you try to compose these.

The standard reference on the security of generic composition of ciphers and MACs is Bellare and Namprempre 2004. There are various standard security notions for a putative authenticated cipher: indistinguishability (IND-) or nonmalleability (NM-), under chosen-plaintext attack (-CPA) or adaptive chosen-ciphertext attack (-CCA2); unforgeability of plaintexts (INT-PTXT) or of ciphertexts (INT-CTXT).

Bellare and Namprempre prove or provide counterexamples for all implications and nonimplications between these security properties. They also prove or provide counterexamples for the security properties generically attained or not by MAC-then-encrypt (MtE), encrypt-and-MAC (E&M), and encrypt-then-MAC (EtM), composed out of a cipher indistinguishable under chosen-plaintext attack (IND-CPA) and a MAC unforgeable or strongly unforgeable under chosen-message attack (UF-CMA, SUF-CMA).* The results hold for any deterministic or stochastic, stateless or stateful, cipher and MAC, as long as decryption and verification are deterministic and stateless.

If, like me, you find this menagerie of security notions dizzying, you may find it reassuring that they can be gathered into a single notion of authenticated encryption meaning IND-CCA2 and INT-CTXT (which collectively imply all the others, and are equivalent to another notion of IND-CCA3), which in turn can be extended to authenticated encryption with associated data. But the Bellare and Namprempre paper is helpful for studying the relations between the notions, and counterexamples for generic compositions where intuition might lead us astray into a false sense of security not provided by the standard definitions.

Beware that the story may be a little more complex than simply choosing a ‘mode of operation’ for a block cipher and choosing a MAC, as everything is in the misbegotten nonsense paradigm that is choosing modes of operation for a block cipher, a confusing paradigm that should have been left in the dumpster of history out back.

Example. If you pick CBC mode, then you need to decide what to do with messages that are not exactly multiples of 128 bits long. You might choose AES-CBC-PKCS7. But if you try to apply that in (say) MAC-then-encrypt, you effectively have MAC-then-format-then-encrypt, and the reverse procedure is decrypt-then-parse-then-verify. A lot happens before the verify stage, so this exposes opportunities for padding oracle attacks, because the adversary may have more than just a decryption oracle as is posited in the adaptive chosen-ciphertext attack model.

Even if you had only a UF-CMA MAC and not an SUF-CMA MAC, you are better off remembering encrypt-then-MAC as your go-to composition than you are with MAC-then-encrypt. Although perfectly safe use of EtM and MtE give the same security properites (IND-CPA and INT-PTXT), anything other than EtM exposes you to the cryptographic doom principle, because you are tempted to touch unauthenticated data, which is pure evil.

* Spoiler alert: Only EtM with IND-CPA cipher and SUF-CMA MAC generically provides all the security properties. EtM and MtE with IND-CPA cipher and UF-CMA MAC generically provide IND-CPA and INT-PTXT. With SUF-CMA instead of UF-CMA, MtE still doesn't provide IND-CCA2 or INT-CTXT because the cipher may be malleable. E&M doesn't even generically provide IND-CPA.

Combining a deterministic MAC and an encryption scheme by concatenating the MAC and the result of the encryption (MAC-and-encrypt) is insecure: enciphering the same message twice is recognizable by the MACs being identical, against the encryption's goal of hiding all characteristics of messages (the cipher is no longer CPA-secure).

Combinations that can be secure are MAC-then-Encrypt (which is different because the MAC is enciphered along the plaintext), and Encrypt-then-MAC (where the result of encryption including Initialization Vector is the input of the MAC). Both are theoretically secure if independent keys are used for MAC and encryption, but Encrypt-then-MAC has the practical advantage that the decryption is only attempted on good ciphertext, which guards against implementation goofs where it is delectably acted on alleged plaintext that did not yet pass the MAC check, which opens to attack.

If keys used for MAC and encryption are not independent, security of MAC-then-Encrypt and Encrypt-then-MAC depends on specifics. When restricted to a single key, we can use a secure Key Derivation Function to expand the key into two keys (one for the MAC, the other for the cipher), and can generally get away with using the same single key for very different cryptosystems (e.g. HMAC-SHA-256 for the MAC and AES-128-CTR for the cipher). Otherwise, using the same key for a MAC and a cipher can be insecure.

Here is an example of the later. Assume the AES-256 block cipher with encryption $E$ used per a single key

• for a MAC restricted to authenticating two blocks $B_0$ and $B_1$ with the MAC $E(E(B_0)\oplus B_1)$, which in itself is secure;
• and for CBC encryption with random IV, which in itself is secure.

With the two combined by encrypt-then-MAC, a 1-block message $M$ gives a 3-block cryptogram:

• the random $\text{IV}=B_0$,
• the CBC-encrypted block $E(\text{IV}\oplus M)=B_1$,
• the MAC $E(E(B_0)\oplus B_1)=E(E(\text{IV})\oplus E(\text{IV}\oplus M))$.

It follows that the third block of cryptogram for the all-zero plaintext is a constant, while it typically changes according to IV for other plaintext. And that breaks confidentiality under CPA, by allowing to recognize the all-zero plaintext.

I assume "perfectly" means not really that (one time pad etc.), but good-enough algorithms for today, like AES.

Then, it's the same even for eg. AES alone, without MAC. As you probably know, AES has a block size (16 byte), and pure raw AES itself works exactly on one block. Not 15 bytes, not 17, not 32, just always 16.
Given this, AES is assumed to be uncrackable in real world. (There were some weaknesses found, meaning it is not as secure as the inventors thought, but just decrypting something without key takes still way too much time etc. to be possible).

Now, if there is more (or less) data than 16 byte, there are block modes and padding schemes that give us a ways how to apply AES to any data size. Among them is ECB: If the data consists of multiple AES blocks, just use AES one each of them independtly, and nothing more.
ECB is also very discouraged because of its properties: Most notably, an attacker can see in the encrypted data which blocks of the plain text were equal (simply because the encrypted data there is equal too).
In many use cases for encryption, this is a big security problem. Despite AES being uncrackable, the attacker can gain some infos about the plaintext very easily. Just because of the way AES is used.

It's nothing different for auth. enc. schemes - the way encryption and MACs are combined may weaken the overall scheme.

On a different note, AES etc. are not pefect / good enough in all cases themselves. For example, AES losing much of it's strength if two data things are encrypted with two keys that are similar (in a specific way).

• So ECB mode obviously doesn't provide indistinguishability and this gets inherited to A&E. But this doesn't really answer my question, rather satisfies a niche pertaining to it. – Daniel B Jun 3 '18 at 12:59