What is more efficient to Encrypt then MAC or to MAC then encrypt

Question

I have been searching for resources on the internet about the efficiency of Encrypt then MAC, MAC then encrypt, MAC and encrypt, and hash then encrypt and I have come up short with all of them. Most sources will give what they will protect against but none will tell me what is more efficient in time and resource wise.

Answer 1

Encrypt-then-MAC and MAC-then-encrypt are about as efficient. When implemented with a block cipher, both require the same number $2\lceil n/b\rceil+1$ of block encryptions, for $n$-bit message and $b$-bit block.

When efficiency matters, it should be used authenticated encryption with integrity thru a universal hash, like AES-GCM or ChaCha-Poly1305: because the universal hash is much faster than CBC-MAC, there's a significant cost saving, for the same functionality as MAC-then-encrypt.

Answer 2

You aren't finding much about performance because it's basically the same. There's interesting stuff to say about their relative security but not a lot to say beyond “basically the same”.

Setting aside hash-then-encrypt which mostly doesn't work, there are three methods. Given a plaintext P:

• Encrypt-then-MAC: encrypt the plaintext C = E(P) and append the MAC of the ciphertext T = M(E(P)). In the other direction, given C || T, check that T is the MAC of C then decrypt C to find P.
• MAC-then-encrypt: calculate the MAC of the plaintext T = M(P) and encrypt the plaintext with the MAC appended E(P || T). In the other direction, decrypt the ciphertext, split the result as P || T and check that T = M(P).
• MAC-and-encrypt: encrypt the plaintext C = E(P) and append the MAC of the plaintext T = M(P). In the other direction, given C || T, decrypt C to find P and check that T is the MAC of P.

In all cases, for a message of length n, you need to calculate the MAC of n bytes and the encryption or decryption of n bytes. The difference is, at most, whether you need to encrypt/decrypt the MAC value. This is a constant cost (independent of the message length) and it's the same order of magnitude as other details of the algorithms, such as whether padding is involved, how the length of the message is encoded, how the key is prepared for use, etc. So there is no meaningful difference between the generic approaches.

Above I didn't take parallelization into account. It is attractive to do the authentication calculation and the encryption/decryption calculation in parallel if your hardware supports it. Taking for example encrypt-then-MAC, the input to the MAC is the output of encryption, so you can't do the two perfectly in parallel. On the contrary, MAC-and-encrypt allows the encryption and the MAC to be parallelized apart from the last step of encrypting the MAC. However, most primitives process the data one small block at a time from left to right, so as soon as encryption has processed one block, you can start the MAC operation with that block: thus encrypt-then-MAC can be parallelized as

1. Encrypt the first block.
2. MAC the first block while encrypting the second block.
3. MAC the second block while encrypting the third block.

and so on. Thus the parallelization penalty is only one block regardless of the message length. Furthermore, the parallelization penalty is inverted for decryption. As a result, even when considering parallelization, the performance differences are tiny, and they're inverted between encryption and decryption, so once again the generic construction matters less for performance than the details of the algorithms.