HMAC versus encrypted hash

Question

When encrypting a message with a symmetric key, it seems like the best practice is to first encrypt the message, then run the cipher text and key through HMAC, appending the result to the cipher text. The receiver can strip off the hash, HMAC the cipher text and key, and verify that the hashes match. This tells the receiver that the person who made the HMAC had the secret key, and that the message was not tampered with.

But why can't the sender instead hash the cipher text, then encrypt the hash with the secret key? The receiver would decrypt the hash with the same key, hash the cipher text, and verify that the hashes match. Wouldn't this give the receiver the same assurance, and isn't this how it's done in public key cryptography, when the sender wants to sign the cipher text?

Answer 1

Depending on your encryption algorithm and hash function, this can be wasteful at worst, and awkward to implement at a low level efficiently at best. In any case, great care must be taken to do it correctly. You can't think of this as the special case "AES+CBC+SHA256". You have to consider whether it is correct for every combination of cipher+mode and cryptographic hash (particularly considering cases where the hash size is not a multiple of the block size). For specific cases it may be fine, but generally use the system that was designed and analyzed for this purpose: (H)MAC.

Just to walk through it, let's say you're going to implement this with AES and SHA-224. So SHA-224 is 28 bytes long, and AES takes a 16 byte block. So we need two blocks. So we need a mode. CBC since that's what we probably used to encrypt the message? But I could get away with ECB since the input is "effectively random." OK, so maybe I scare people and and pick ECB (because usually that's really dangerous, but I explain it to them), but I still need a padding solution. PKCS7 I guess since that's what we're using for the message, but now I'm wasting 4 bytes in every message (an HMAC would be 28 bytes, but the cipher text is 32 bytes). Or I could switch to XEX mode maybe so I could use any length hash without wasting bytes? Have I made a mistake anywhere in there and accidentally broken the security?

See how many choices I'm making here? What I'm doing is reinventing a MAC by hand. There is no simple operation called "encrypt." That word masks a huge number of choices and implementation details. And I then need to make sure I've picked those in a way that don't create a problem. Lots of encryption systems are excellent under one set of assumptions, and completely broken under another set of assumptions. Combining two independently secure things together can break the whole system (length extension attacks are a favorite version of this). There's no simple thing called "encrypt" that is always both secure and efficient.

So what do we do? We use schemes (not just algorithms, but how we put together algorithms) that have been carefully designed, reviewed, and attacked for a long time. We strongly avoid inventing new schemes, even if they seem fine (and even if they actually are fine). And one very popular and well-analyzed MAC solution is the HMAC. So we use that one.

BTW, I went hunting for guidance once on whether it was safe to use the same key for encrypting as for the HMAC. As best I know, the answer is that nobody knows. That might entwine the two systems too much and leak information, or it might not. I don't believe it's been studied well enough to be certain. So I use separate keys in my systems. Our default position should be "it is insecure until it has been studied extensively, and then it may be provisionally trusted," not "it is secure until someone demonstrates an attack."

Answer 2

$\newcommand{\concat}{\mathop{\Vert}}\newcommand{\AES}{\mathrm{AES}}$You are asking whether you can take a secure—specifically, IND-CPA—message cipher $E_k$, say AES256-CTR, and a fixed public collision-/preimage-/2nd-preimage-resistant hash function $H$, say SHA-256, and compose them in the form $$c \concat E_k\bigl(H(c)\bigr), \quad \text{where} \quad c = E_k(m)$$ to encrypt a message $m$ with a key $k$, and get a secure authenticated encryption scheme—specifically, IND-CCA3. (I'm eliding details of nonces and input separation for the moment. Figuring out how to fit them into this post is left as an exercise for the reader.)

This looks awfully close to encrypt-then-MAC, with the putative MAC $(k, c) \mapsto E_k\bigl(H(c)\bigr)$. Unfortunately, on its own, that is not a secure MAC. However, the input $c$ is an encrypted message, so that analysis doesn't end the discussion.

This also looks close to encrypt-and-MAC with the putative MAC $(k, m) \mapsto E_k\bigl(H(E_k(m))\bigr)$, which maybe is secure but it would take careful analysis to say, partly because it's not used in isolation—you also reveal $E_k(m)$ to the attacker. I haven't done the analysis and I don't know anyone who has, so I won't say one way or another whether this is secure.

All that said, if you change this a little bit by using a secret choice of hash function $H_r$, giving $$c \concat E_k\bigl(H_r(c)\bigr), \quad \text{where} \quad c = E_k(m),$$ then you get the structure of, e.g., AES-GCM, which is a secure authenticated encryption scheme.

The family of functions $H_r$ in AES-GCM is called GHASH, and it isn't even preimage-resistant, let alone collision-resistant, to anyone who knows the index $r$—but $r$ is secret, perhaps derived alongside $k$ from some master key $k_0$. Since its security requirements are more modest—in technical jargon, it must be an $\epsilon$-almost-universal hash family—GHASH is very fast and cheap to evaluate compared to SHA-256 or any other collision-resistant hash function, as long as you have fast binary polynomial multiplication and reduction.

(In software, you need special CPU instructions to do this fast in constant time, which are not widely consistently adopted in CPU instruction sets or standard programming languages, just like you need special CPU instructions that aren't widely consistently adopted to evaluate AES fast in constant time. But you could use another stream cipher such as Salsa20 and another hash family such as Poly1305 which works in a prime field—these require no special CPU instructions to evaluate fast in constant time. Note, however, that this is a little different from NaCl crypto_secretbox_xsalsa20poly1305, which is structured to also defend against a reforgery attack on Carter–Wegman many-time authenticators like AES-GCM uses. For an even more variegated menagerie of authenticated encryption schemes, check out the CAESAR competition.)