Encrypt-then-MAC paradigm

Question

I read that the Encrypt-then-MAC paradigm is provably secure.

From what I understand, when using for example AES for encryption and HMAC_SHA256 for MAC generation (and the keys $K_1 \neq K_2$), this means the following:

1. $ciphertext = AES_{K_1}\{plaintext\}$
2. $mac = HMAC\_SHA256_{K_2}\{ciphertext\}$
3. send: $ciphertext \;\|\; mac$

I have two questions regarding this construction:

1. Does it negatively affect security to calculate a hash value of the ciphertext before MAC calculation? Like exchanging step $2.$ with this: $HMAC\_SHA256_{K_2}\{SHA256(ciphertext)\}$.
2. What security properties are offered by this construction in general -- because I don't understand, what about this construction is provably secure.

Answer 1

Does it negatively affect security to calculate a hash value of the ciphertext before MAC calculation? Like exchanging step 2. with this: HMAC-SHA256(SHA256(ciphertext)).

Technically, yes, but not significantly. In order to attack the scheme you propose, the attacker would have to be able to do at least one of two things: (1) Find an attack on the (standard) HMAC-SHA256 scheme; or (2) Find a collision for SHA256. Currently, the cryptographic community believes that one can safely assume an attacker can do neither of these things. (Contrary to what some may expect, an ability to do the second does not imply an ability to do the first.)

What security properties are offered by this construction in general -- because I don't understand, what about this construction is provably secure.

What do you mean by "this construction"? Do you mean Encrypt-then-Mac, or HMAC-SHA256?

If you meant Encrypt-then-MAC, David Cary provided a link to this question, and you might find the answers helpful. To summarize, one can prove that an attacker cannot learn information about the plaintexts (aside from their lengths), and cannot create a ciphertext that will pass the MAC integrity check. Here, attackers are assumed to have the ability to conduct chosen message attacks; that is, we assume that the attacker can convince or trick one of the parties into sending some messages of the attacker's choosing, and show that having this power is not enough for the attacker to "break" the scheme. (This is very conservative: in the real world, most attackers won't have this ability.) We also assume that the encryption algorithm and the MAC algorithm are themselves secure, and use independently chosen, random keys.

If you meant HMAC-SHA256, then see the second part of my answer to another question. Proving that HMAC-SHA256 has the properties discussed there requires making some (reasonable) assumptions about SHA256.

In both cases, the proofs are not "absolute". We need to make assumptions about the underlying algorithms, and the proof only shows that the probability of the attacker succeeding is very small, provided you don't do something like use the same key to encrypt petabytes of data.

Note: In your question, you wrote Ciphertext = AES_K(Plaintext). But this is (almost always) wrong! AES can only work on 16-byte strings. To encrypt longer strings, you need to use AES inside of some mode of operation.

Answer 2

Will try to give answer to 2nd and then 1st of the questions, since 2nd's answer opens up 1st's.

Back to basics: MAC is Message Authentication Code, which gets attached to the message and provides authentication of the message upon receipt. Authentication here means:

• Detection of any change made to the original message either by error in transmission or tampering by an attacker.
• Detection of a completely forged message by an attacker.

This all means we have to generate the MAC value from the whole message being sent. When the message is cipher text, then to protect the message MAC should be generated from the cipher text, and all of it as it is in the message, which means any IV and what not included.

If we are sending a message which contains cipher text and other data which are plain text, then we need to MAC the whole message again. Because again MAC is to protect the whole message.

Question then: does this protection of the message also mean protection of the plain text? Yes it does, because there is one to one relationship between cipher text and plain text. If cipher is good so is plain text.

I read some references against this saying if by mistake a different key was used to decrypt the cipher text, we won't be able to detect this when Encrypt-then-MAC is used. But protection against wrong key usage is wrong expectation from MAC. MAC is supposed to provide detection of errors or tampering of the message, not provide mechanism of detection of wrong key usage during decryption. MAC usage doesn't even know if encryption is used or not, it protects the message.

If an application is prone to using wrong keys, then correct thing to do is to prevent it from doing so. And one way this can be accomplished by is, including a key identifier in the message, so that receiver will know exactly what key to use. If this is done, the message will now be cipher plus the key identifier. The MAC will be generated from these, since that is the message now. And that means any tampering of the value of the key identifier will be detected too.

If instead MAC-then-Encrypt is used, there is no way to authenticate the message, since message itself won't have a MAC attached to it. That opens up attack surfaces like "Padding Oracle Attack", which relies on receiver not being able to detect forged or tampered messages, due to lack of MAC in the message.

With Encrypt-then-MAC, actually more accurately to call it "Always MAC protect the whole message" case, receiver will detect tampering or forged message immediately without doing any more processing. It is safer!

Now to 1st question, the above answer by given by Seth is a good one. My only addition to it would be why would you want to do that anyway? In one of the comments the explanation to why was given as:

"..My reasoning is when I have something like HMAC(some || concatenaed || fields || ciphertext), it might be possible for an attacker to shift the boundary between "fields" and the ciphertext, because ciphertexts usually don't have a fixed length...."

Reminder again, you need to HMAC your whole message and as is!, so that you are protecting your whole message as is. In other terms what you pass into HMAC has to be the whole message and as is. The receiver will have to do the same for validation. If your message structure is open to shifting boundaries between parts of them, then you have problem with your message structure. Solution to that will not come from using additional SHA call. Solution to that would be changing your message structure and format not to allow such boundary shifting; such as including length specifiers for variable length parts, separators etc.

Then since you have to HMAC your whole message as is, those length specifiers, seperators and etc will be included as part of the value that is passed to the HMAC function. Which means you won't have boundary shifting problems to worry about there, as long as your message itself is fine in that regard. If not, you have a problem to solve before coming to HMAC call.

Hope this helps.