13
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Note that digital signatures are very slow, require large keys and in some manner sharing the public key securely. Many times the only need is to ensure the encrypted data is valid, e.g.: free from transmission errors. $\endgroup$ – zaph Jul 11 '16 at 16:34
  • $\begingroup$ Possible duplicate of What is the advantage of digital signatures over message authentication codes? $\endgroup$ – Biv Jul 11 '16 at 16:42
  • 1
    $\begingroup$ Digital signatures are generally taken over a MAC rather than over the entire message. $\endgroup$ – user207421 Jul 11 '16 at 20:35
  • $\begingroup$ did you mean hash (instead of MAC)? $\endgroup$ – Minaj Jul 11 '16 at 20:48
11
$\begingroup$

There are many advantages of MAC's 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 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.

$\endgroup$
  • $\begingroup$ Did you say TLS uses different keys for sending/signing Vs receiving/verification? I thought TLS uses a symmetric key once the negotiation phase is over. I actually thought this symmetric key is exchanged during the negotiation phase (and changed periodically). can u please clarify? $\endgroup$ – Minaj Jul 11 '16 at 17:27
  • $\begingroup$ But here is my thinking: If these symmetric keys are derived from the master key, they are still symmetric keys -- i.e., the same key shared between the sender and receiver. Otherwise what the sender encrypts, the receiver would not be able to decrypt -- right? $\endgroup$ – Minaj Jul 11 '16 at 17:34
  • $\begingroup$ Check the key derivation here. Yes, the keys are shared; at this time both peers trust each other; they can send any data over the channel. $\endgroup$ – Maarten - reinstate Monica Jul 11 '16 at 17:36
  • $\begingroup$ I would think that at this time the peers trust each other's identity (i.e., A is sure that he indeed is communicating with B on the other side of the channel). However, this would not mean that A cannot fake a message and claim it came from B since the key is shared. $\endgroup$ – Minaj Jul 11 '16 at 17:43
  • 1
    $\begingroup$ Note that in TLS the client may not even have a private key. The client often stays anonymous (client authentication is strictly optional for TLS). The idea is to protect against eavesdroppers and man-in-the-middle while providing authentication of the server to the client. TLS provides a secure channel, it doesn't provide non-repudiation or long term protection of messages. When the TLS connection is stopped all the session keys are tossed away. $\endgroup$ – Maarten - reinstate Monica Jul 11 '16 at 17:47
9
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Does this mean we overlook the risk that a peer could forge a message and claim it came from the other peer? I clearly understand the performance advantages of using MACs. My problem is the trust issue. $\endgroup$ – Minaj Jul 11 '16 at 17:40
  • 1
    $\begingroup$ This is ultimate pedantry, but you could build a hash-based signature scheme from a hash function implemented on top of a hardware block cipher, so your point about not having hardware support for digital signatures is not strictly correct. $\endgroup$ – pg1989 Jul 11 '16 at 17:48
  • 1
    $\begingroup$ @pg1989: true; I have moved the existing practical where it was intended to be, partially addressing your comment. $\endgroup$ – fgrieu Jul 11 '16 at 17:53
  • 1
    $\begingroup$ SPHINCS and XMSS are pretty practical, and post-quantum secure to boot! $\endgroup$ – pg1989 Jul 12 '16 at 0:11
  • 1
    $\begingroup$ @pg1989: true; see edit $\endgroup$ – fgrieu Jul 12 '16 at 5:12
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ SO you are saying that a typical TLS-protected transaction, a peer is not bothered that the other peer could fake a message? In what scenarios then would a peer be bothered about this? $\endgroup$ – Minaj Jul 11 '16 at 17:36
  • $\begingroup$ "So you are saying that a typical TLS-protected transaction, a peer is not bothered that the other peer could fake a message?" Yes, for example, when you download a page from Google, you aren't concerned that the browser might claim that it's actually a Yahoo page. "In what scenarios then would a peer be bothered about this?" Where you might want to send a message to a number of peers (and you don't trust those peers with the ability to fake another peer). $\endgroup$ – poncho Jul 11 '16 at 18:30
  • $\begingroup$ "Where you might want to send a message to a number of peers (and you don't trust those peers with the ability to fake another peer..." Can you please clarify? example? $\endgroup$ – Minaj Jul 11 '16 at 22:51
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If you have pre-shared keys it's trivial to exchange public keys as you also should ask yourself why you didn't use the medium you used for secret-key-exchange to also exchange public keys... $\endgroup$ – SEJPM Jul 11 '16 at 18:59
  • $\begingroup$ Not sure why this is downvoted. There are real-world cases where the public keys cannot be exchanged. For instance, the shared secret could be a password given over the phone or email. $\endgroup$ – user13741 Jul 11 '16 at 20:14
  • $\begingroup$ I think for most people the downvote reason (would have been) the scenario I described in my other comment. As for phone and mail: This is as secure as phone and e-mail (or other insecure media) and thus usually viewed really badly in terms of security. $\endgroup$ – SEJPM Jul 11 '16 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.