Is Encrypt+HMAC stronger than AEAD?

Question

There are a few posts that I've come across that seem to imply that using regular encryption and a MAC might be better than using the newer AEAD (ie: AES/GCM) modes.

https://www.daemonology.net/blog/2009-06-24-encrypt-then-mac.html

https://blog.cryptographyengineering.com/2011/12/matt-green-smackdown-watch-are-aead.html

My questions are thus:

Is an AEAD more likely to fail (being subject to chosen plaintext attacks, versus HMAC protecting the encrypted part more securely), and if so, does it fail in a more catastrophic way?

Assuming that you have securely generated both the HMAC and encryption keys, is Encrypt+HMAC therefore more secure?

Answer 1

This is something I tend to disagree somewhat with Colin Percival on.

You should use Encrypt-then-HMAC if and only if you can get it right. The biggest pitfall is using a short-circuiting string comparison versus a constant-time string comparison. Given the former, people can use timing attacks to forge valid HMACs for arbitrary ciphertexts. With an encryption mode like CBC, this could be used to read the contents of encrypted messages. Other pitfalls include accidentally implementing Encrypt-and-MAC or MAC-then-encrypt, which have historically had vulnerabilities related to their construction.

On the other hand, EAX and GCM modes provide this feature transparently. There are some concerns about potential side-channel attacks against dedicated AEAD modes, and there is also the conceptual issue of potentially passing unauthenticated packets to your decryption algorithm. You, of course, have to get details like unique IVs correct, but you also have this requirement for Encrypt-then-MAC.

That said, potential flaws in EAX and GCM implementations can be fixed for many people at once with patches to the relevant libraries. Flaws where non-cryptographers naïvely compare HMACs are epidemic, and even high-profile projects like Google's KeyCzar have made this simple mistake. If you absolutely know what you're doing, Encrypt-then-HMAC is a provably secure construct. If you don't know what you're doing, something like EAX or GCM may be found to have weaknesses, but they are assuredly better than implementing something yourself.

Edit: I may have made Encrypt-then-HMAC sound easier than it actually is. One other major pitfall of Encrypt-then-HMAC is not HMACing enough information, or not HMACing the information correctly. The HMAC must include the ciphertext, the additional authentication data, and the initialization vector. It probably must also (perhaps someone else can confirm or deny this) include a descriptor to identify the encryption algorithm used. To pass these fields into the HMAC, you must use a format that unambiguously delineates fields. The easiest way to do this is to prepend a 4-byte big-endian length before any variable-length field (usually just authentication data and ciphertext), but doing this for all fields is probably a good idea. If you don't HMAC all this information, an attacker can modify any of the data not included. If you don't HMAC them unambiguously, an attacker can manipulate message boundaries, which could allow him to conduct an exploit.

Edit 2: Another detail of Encrypt-then-HMAC I've forgotten. Hopefully you can see how hard this is to get right. Ideally, you should never reuse the same key across security contexts. I'm unaware of any attacks that would result from using your encryption key as the key for the HMAC, but best practice is to use a different key for encryption and authentication. One simple approach (assuming a 256-bit encryption algorithm and 256-bit HMAC) is to use a "virtual" 512-bit key. Use the first half for encryption and the last half for authentication. Another approach is to use a 256-bit key, but pass it through HKDF with a 512-bit output; use this as before: split it into two parts, use one for encryption and one for authentication.

Edit 3: I asked a highly relevant question on the security StackExchange a few months ago. Thomas Pornin's detailed answer may be helpful.

Answer 2

I think this question splits into two parts, the one is about AEAD in principle vs. Encrypt+HMAC, the other about AES-GCM.

As far as I know, Galois counter mode may have some weaknesses in the checksum, which might reduce its strength, and a well-known limitation to transfer size (64GB) before you definitely should renegotiate; read this paper for more information: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Ferguson2.pdf

I also recall reading a paper comparing the galois field MAC computation with poly1305 from DJB, pointing out that the prime modulus (2^130-5) has significantly better properties. That's not bad enough for practical attacks, though.

These weaknesses are related to the particular AEAD encryption scheme AES-GCM; others are more secure. Examples of AEAD cipher suites which are considered more secure than AES-GCM are ChaCha20+Poly1305 from DJB, and Keccak in duplex mode.

The general picture however is really that AEAD is much, much easier to get right as mere user of a cryptographic library than Encrypt+HMAC. That does not mean that they have to be technically different from Encrypt+HMAC, just that you use a library where both the encryption and the HMAC is combined, like e.g. ChaCha20+Poly1305. Technically, ChaCha20 is just a stream cipher without authentication, and Poly1305 is just authentication. On the other hand, Keccak in duplex mode is really computing both authentication and encryption with the same operation, so it's integrated by design.

Answer 3

As an important update, more recent research has revealed that the main way Encrypt-then-MAC is stronger than standardised AEADs is that it's committing if:

1. You use a single key for both encryption and authentication (not recommended) or derive the encryption key and MAC key from the same input keying material using a secure KDF (recommended). [Source]
2. You use a 256-bit+ authentication tag because you want collision resistance. [Source]

Simply put, being 'committing' means it should be infeasible for authentication to pass using multiple different keys and for the authentication tag to repeat for different messages and keys.

You would naively expect an AEAD to have this sort of property, but the popular standardised AEADs, such as (X)ChaCha20-Poly1305, AES-GCM, and AES-OCB, are not committing. This can allow for attacks in some scenarios, which can be exploitable in practice. It's a situation that feels reminiscent of length extension attacks, which were fixed in SHA3.

Encrypt-then-MAC is the current recommended solution by some of the commitment research authors. Thus, I would argue that committing Encrypt-then-MAC implementations with support for additional data (aka equivalent to AEADs) should be standardised and added to cryptographic libraries so they're as easy to use as regular AEAD modes. Then the only argument in favour of regular AEADs is that they're more efficient, but the gap depends on the MAC used (e.g. BLAKE3 can be faster than Poly1305).