Choice of MAC and handling it correctly

Question

I have recently learned that Encrypt-then-MAC is recommended when using symmetric encryption.

I have two closely related questions related to that, which is why I am posting them as one:

1. Looking at the different kinds of available MACs (UMAC, HMAC, etc.), does it matter which one I use? Meaning: does the choice of MAC depend on the cipher, or the mode of the cipher, or anything else? Or is it more a matter of personal preference which kind of MAC I use?

2. Am I assuming correctly that I can transmit a MAC together with the related ciphertext? Meaning: is it safe to append the MAC to the ciphertext upon transmission, or is there another way I should prefer (separate transport over secure channel, or something like that)?

Answer 1

1. There are various factors that go into choosing a MAC algorithm, for example: Use cases for CMAC vs. HMAC? documents CMAC vs. HMAC; I think HMAC is a reasonable default choice though (supported by Colin Percival: http://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html).

2. Yes, the MAC can be transmitted alongside the ciphertext, one thing to remember to do when verifying the MAC is to use a constant time comparison: http://codahale.com/a-lesson-in-timing-attacks/

Answer 2

There are no specific requirements for the choice of cipher and MAC in the Encrypt-then-MAC construction, except that both should individually achieve their respective security goals (typically semantic security and existential unforgeability).

Indeed, this is the major advantage of Encrypt-then-MAC over other constructions like MAC-then-Encrypt or Encrypt-and-MAC, which do require the cipher and MAC to satisfy additional properties in order to be secure. (For example, Encrypt-and-MAC may be horribly insecure if the MAC leaks information about the plaintext.)

The MAC may be, and usually is, transmitted alongside the ciphertext, often appended to it. If the MAC is of a type that requires a nonce input, this will also need to be sent alongside it. Using the Encrypt-then-MAC construction ensures that this leaks no information about the plaintext, even if the MAC is not privacy-preserving, since the MAC is computer over the ciphertext.

---

As for the choice of MAC, I agree with Alex Gaynor's suggestion of using HMAC as the default choice, if there's no specific need to use some other MAC. The main advantages of HMAC are that it's easy to use, requires no nonce, and is provably (assuming that the hash function used satisfies the necessary assumptions) secure and privacy-preserving (and, in fact, a PRF).

That said, there are sometimes reasons to choose other MACs. For example, HMAC requires a cryptographic hash function, whereas CMAC can be implemented using just a block cipher (which you're probably already using for encryption), which can make it more convenient for constrained platforms like embedded systems. Meanwhile, polynomial-evaluation MACs like UMAC / VMAC or Poly1305 can be extremely fast, but require a dedicated implementation and the use of a nonce.