Security of basic SHA256 MAC in an authenticate-then-encrypt scheme

Question

I know the following construct is insecure if the MAC as defined below is appended to the encrypted message in an Encrypt then Authenticate (EtA) scheme.

$k_1$: encryption key
$k_2$: authentication key $m_1$: plaintext message
$c_1$: encrypted message (AES-CBC with random iv)
$IV$: from PRNG

where $k_1$ and $k_2$ are independent.

$$MAC = SHA256(m_1 || IV || k_2)$$ $$c1 = AES(k_1, IV, m_1)$$ $$SEND(c1 || MAC)$$

MAC is completely insecure because it is not a proper HMAC as defined by $H((k_1 \oplus opad) || H((k_1 \oplus ipad) || m_1))$. MAC can be easily compromised by an extension attack since the MAC is in the clear.

However, I am trying to determine if the above MAC becomes secure if it is included in the $c_1$ encryption of an Authenticate-then-Encrypt (AtE) scheme.

$$SEND(AES(k_1, IV, m_1 || MAC))$$

MAC is no longer in the clear and should not be vulnerable to the extension attack. I am aware of other general attacks on AtE schemes but my specific question is whether including a $MAC=SHA256(m_1 || IV || k_2)$ in the encrypted ciphertext is cryptographically secure for message authentication.

ie: Decrypt $c_1$ using $k_1$, then immediately verify decrypted MAC with $k_2$.

This is an academic question since in practice I would use AES-GCM for authenticated encryption.

Answer 1

Unfortunately your question doesn't fully specify the authenticated-encryption mode. In particular, AES is a block cipher, not a mode of operation, and only operates on plaintexts of some fixed length (128 bits for AES). So you need to fix a mode-of-operation for AES, such as CBC mode or CTR mode. (Never use ECB mode.)

Let's assume you used CBC mode. Then the final Authenticate-then-Encrypt mode you outline is indeed more commonly referred to as MAC-then-Encrypt or MAC-Encode-Encrypt. The latter is a bit more accurate, as it captures the fact that often one needs to encode the concatenation of the message and message authentication tag as a plaintext string that is compatible with the encryption mode of operation. For example, CBC mode only accepts plaintexts that are a multiple of the underlying block cipher's block size (for AES this is 128 bits).

In general MAC-Encode-Encrypt is never recommended for use in modern applications. Why? Because it's near impossible to implement correctly. One must first decrypt, then properly decode, and only then can check the MAC. The first two operations are done before checking authenticity and many clever attacks have shown how to confuse decryption implementations. See Lucky 13 for a recent example, and the included references to padding oracle attacks.