Can one make a secure AEAD from any secure cipher and any secure MAC?

Question

Can one make a secure AEAD from any secure cipher and any secure MAC using encrypt-then-MAC:

• with independent keys and IVs (any cipher and MAC)
• if the cipher is a stream cipher (including a block cipher in CTR mode), using parts of the keystream (not used to encrypt plaintext) as the MAC key or keys and IV?

If so, then all of the following would be secure:

• A stream cipher plus GHASH (of which GCM becomes a special case), with the stream cipher being used to mask the GHASH output.
• A stream cipher plus any other Wegman-Carter authenticator, such as Poly1305, again with the stream cipher used to mask the output
• A stream cipher plus HMAC.

Proof of the first two cases: since encrypt-then-MAC is secure we need only to show that

1. this is in fact an encrypt-then-MAC construction.
2. that the MAC is secure (we already know by assumption that the stream cipher is secure).

Firstly, we can assume that the parts of the keystream used for the MAC and to encrypt plaintext are independent, as any dependencies would be a distinguisher against the stream cipher. Therefore:

• 1. is true because the construction uses a stream cipher to encrypt the plaintext, then applies a MAC to the ciphertext.
• 2. is true because the stream cipher is a secure PRF, so there is no way (for a resource-bounded attacker) to compute the (secret) MAC key (and block used to encrypt the MAC) from the (potentially known to attacker) part of the keystream used to encrypt plaintext. Therefore, the attacker has no knowledge of the internal state of the MAC, and so the composition is secure if the MAC is. For most Carter-Wegnam MACs, this is known unconditionally.

I have seen various special cases proven secure, but not the general case.

Answer 1

The encrypt-then-MAC paradigm works as long as the encryption is CPA secure and the MAC is secure under the standard definition. However, such a MAC must be secure for multiple messages. Therefore, using GHASH or Wegman-Carter authentication is not sufficient. (Indeed, in GCM, the result of GHASH is masked and not directly output.)

The proof of the general composition appears in two papers: The order of encryption and authentication... by Hugo Krawczyk, and Authenticated encryption: relations among notions... By Mihir Bellare and Chanathip Namprempre.

---

It is important to note that the paper by Krawczyk actually shows that in some important cases it is secure to MAC-then-encrypt. However, this is only true when the operations is atomic and it is impossible to know whether the MAC was incorrect or another error occurred.

However, in practice this is almost impossible to do right and has been the cause of multiple attacks on SSL over the past years. Therefore, this part of the paper should not be seen as saying that it's OK to every MAC-then-encrypt.