5
$\begingroup$

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.
    1. 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.

$\endgroup$
  • $\begingroup$ I think there's some composition theorem that states that at least your first case is secure. IIRC it followed (more or less) directly from the definition of a secure AEAD scheme as a scheme that has EUF-CMA and CPA security. $\endgroup$ – SEJPM May 15 '16 at 10:08
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This paper may be of interest. $\endgroup$ – puzzlepalace May 16 '16 at 2:25
  • $\begingroup$ I edited to mention that I did mean to use the stream cipher to mask the MAC for the MACs that require it. $\endgroup$ – Demi May 16 '16 at 14:44
  • $\begingroup$ I do not know of a generic proof of composition in such a case. It's worth trying to write one. $\endgroup$ – Yehuda Lindell May 16 '16 at 19:04
  • $\begingroup$ @YehudaLindell My edit includes a proof (albeit purely qualitative) $\endgroup$ – Demi May 17 '16 at 22:27
  • 1
    $\begingroup$ Indeed, my intuition goes with you and I agree that if there is any justice in the world then this would be secure. However, I have long ago given up on a just world. I would not be satisfied until a full proof is given (in a rigorous model, where the adversary has enc/dec oracles and so on), with a full reduction and so on. But, I strongly encourage you to do that! $\endgroup$ – Yehuda Lindell May 18 '16 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.