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.
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.)
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&amp;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&amp;M doesn't even generically provide IND-CPA.