Block-cipher based vs Hash based MAC

Question

When it comes to MAC algorithms one can have many choices. CBC-MAC, CMAC, PMAC etc are some MAC algorithms that rely on block ciphers (ex AES) to generate a MAC. On the other hand HMAC is very popular on the Internet and relies on compression functions (ex SHA-1, MD5).

What are the drawbacks of each from a security perspective and how do you make a choice if you need to include MAC in your protocol?

Answer 1

Here are some advantages and disadvantages for each of the three classes of MACs, which I know about:

Based on block cipher

There are constructions where the security of the MAC is proven in terms of the security definition of a block cipher. This means as long as the block cipher is secure, the MAC will be secure.

There are constructions where encryption and MAC can be computed with almost no extra CPU cost compared to only encrypting.

Based on cryptographic hash (HMAC)

Assuming the underlying hash is secure, a HMAC guarantees that even an adversary who knows the key cannot produce two different messages for which the same HMAC value would be valid. Neither could an adversary produce a HMAC value which would be valid with two different keys.

One disadvantage is that security of HMAC cannot be proven based on the usual properties regarding collisions of the underlying hash. There could exist a secure cryptographic hash which would lead to an insecure MAC if used in an HMAC. Put differently, HMAC could be broken without ever finding a collision in the underlying hash.

Based on almost 2-universal classes of hash functions

This kind of MAC is provably secure.

Like a one-time-pad, this kind of MAC consumes key material. You will need some key material, that is used only for a single message.

Unlike a one-time-pad, the number of bits consumed does not grow with the message size. You can authenticate an arbitrarily large message using a constant number of key bits from your pool. (The key material also has a reusable part, that grows logarithmically in message size.)

Public key signatures based on cryptographic hash

It is possible to construct a public key signature using a cryptographic hash as the only underlying primitive. These can be proven secure based on the usual assumptions about the security of the underlying cryptographic hash.

A major drawback is that they are expensive to compute, and the signatures require a huge number of bits compared to other public key algorithms.

This is not really a MAC, because it is using asymmetrical keys. A signature could be used in place of a MAC, if it wasn't so expensive. The CPU time needed and the number of bits in a signature is prohibitive in many of the situations, where a MAC would be used.

Answer 2

Unsurprisingly, any secure MACs are a secure choice. Assessing their relative security beyond how many bits of security they offer isn't possible in general. However, there are some differences that don't depend on the protocol:

• Unmodified CBC-MAC is only secure for fixed length messages, otherwise it allows some forgeries.
• Block cipher based MACs allow you to use the same cryptographic primitive for both encryption and authentication, meaning both less code/hardware and fewer algorithms you need to trust.
• A block cipher MAC forces you to use a different key for encryption and authentication. You should do that regardless, but it is less likely that reusing a key for both AES encryption and HMAC is somehow vulnerable to attacks.