Why MACs are so important despite digital signatures doing everything a MAC can do and more?

Question

When an entity $A$ wants to send a message to entity $B$, he can attach a MAC to the message. Entity $B$ on receiving the message can use the pre-shared key to compute the same MAC and confirm if the message is untampered with.

This approach protects $A$ and $B$ from an external attacker who might want to mess with the message. However, it does not protect $A$ from $B$ or $B$ from $A$. For example, $A$ can craft a message and claim that it came from $B$ since $B$ is the only entity that shares this particular key with $A$.

Digital signatures eliminate this problem, since the MAC is replaced with a hash which is encrypted with the senders private key. Usage of the private key means that $A$ and $B$ cannot deny or forge messages between each other.

Which brings me to my question. Why do MACs continue to be so relevant when they are susceptible to the kind of attack described above? Under what circumstances would one prefer a MAC to a digital signature?

---

Note that I have been made aware that there is a question on here which seeks for a comparison between MACs and digital signatures. That question is different from mine since I am looking for concrete cases where MAC would be used instead of digital signatures. Can someone quote a protocol, application, etc, where the disadvantages of the MAC relative to digital signatures can be ignored?

Answer 1

There are many advantages of MACs over signatures.

For signatures, you need to use asymmetric key pairs. Public keys need to be trusted for this to work. Unfortunately, establishing trust is not that easy. Furthermore, you don't want to use a private key stored on, for instance, a smart card (which would require a PIN and would likely be too slow).

Instead, you can simply agree on an authentication key (or a key for an authenticated cipher). This allows much more efficient operations both regarding

• the speed of calculation of creation and verification of the authentication tag / signature and
• with regards to the size of the authentication tag / signature.

For many protocols the problem that the receiver can also spoof authentication tags is not a (huge) issue. It could be a bigger issue for protocols where the two participants use the same authentication key for both sending / signing messages and receiving / verification of messages. TLS, to name just one protocol, uses separate keys.

Answer 2

MACs have some advantages over digital signatures

1. The component of the computational cost that is independent of message size is much higher for digital signatures, to the point of being an obstacle and requiring milliseconds or/and dedicated hardware. We know no signature scheme where both signature and verification of short messages are of speed any comparable to a MAC. Even signature verification for Rabin and RSA with small exponent (which is fast compared to signature generation, or either operation with most other schemes) is slow compared to a good MAC implementation.
2. The increase in size is higher for digital signatures, by a factor of two or much more. For 128-bit security, the best signature schemes we know add at least 256 bits to signed messages (and that's for schemes with message recovery and some minimum message size; for schemes where the signature is an appendix to the message, that's often much more, like 4096 bits for RSA-PSS, 512 bits for ECDSA); while MACs do with 128 bits, or much less if we can live with a residual risk of forgery by supplying a random MAC (e.g. with a 32-bit MAC, odds that any forged message is accepted after 1000,000 attempts are less than 0.025%).
3. We can build MACs from block ciphers, which in turn have hardware support in common CPUs, when the most used digital signature schemes can not (and digital signature schemes built from symmetrical primitives have severe size penalty, e.g. >330,000 bit for SPHINCS). That conspires towards 1 above, and towards making code or hardware that performs digital signature significantly more complex, and harder to make secure against channel leakage (for the signature side) than a counterpart performing a MAC.
4. Public keys necessary for signature verification are significantly larger than secret keys used for MACs (also by a factor of two or much more) at equivalent security.

In application with many small pieces of data that need to be separately verifiable (including communication secured by SSL, TLS or equivalent), we often use MACs for lower computational and bandwidth overhead (1 and 2).

Indeed, MACs are susceptible to forgery by the verifier. But in many circumstances that's a non-issue, including when the key is a session key conventionally shared by only the sender and receiver/verifier (again including communication secured by SSL, TLS or equivalent); or in non-broadcast schemes when the sender is trusted and each receiver has a unique secret key (which does NOT necessarily require the sender to store a key per receiver, thanks to key diversification).

Answer 3

Can someone quote a protocol, application, etc, where the disadvantages of the MAC relative to digital signatures can be ignored?

Your particular attack is of no interest if B has nothing to gain to claim that it got message M from A.

As for concrete examples: the TLS record format, IPsec, SSH, the IES public key system; actually, any protocol that encrypts data for a specific peer (and so doesn't care if that peer could create a valid-looking record, as it's the only one who cares, and the peer would have little reason to fake itself).

Answer 4

This approach protects A and B from an external attacker who might want to mess with the message. However, it does not protect A from B or B from A. For example, A can craft a message and claim that it came from B since B is the only entity that shares this particular key with A.

This property (called non-repudiation) is not unconditionally an advantage, but rather can be desirable, undesirable or irrelevant depending on the situation. Some applications actually want deniable authentication. Think for example of a political whistleblower communicating with a journalist; both of them want to be sure they're talking with the other, but if the journalist's side of the communication is compromised the whistleblower would like to be able to deny that he told the journalist anything.

This is a topic with considerable currency, because many of the most notable examples are end-to-end encrypted instant-messaging protocols like Off-The-Record and Signal are designed to provide deniable authentication. One exposition of this (quoted from here):

One of OTR's primary features is a property called deniability. If someone receives an OTR message from you, they can be absolutely sure you sent it (rather than having been forged by some third party), but can't prove to anyone else that it was a message you wrote. This is a nice change compared to PGP signatures, for instance, where anyone who receives a PGP signed message can prove exactly who wrote it to anyone else.

Answer 5

Usually symmetric crypto is preferred thanks to its efficiency compared with public key crypto. Its primitives are faster compared with those in public key encryption. There is is of course a tradeoff in key management: How users share their secret key in a symmetric setting? Asymmetric encryption solves this problem with the assumption of a trusted PKI, or a trusted Key manager in case of IBE based encryption.

Answer 6

Public keys may not have been exchanged yet between A and B (maybe all they have at that point is a pre-shared secret).