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
- this is in fact an encrypt-then-MAC construction.
- 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:
- is true because the construction uses a stream cipher to encrypt the plaintext, then applies a MAC to the ciphertext.
- 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.