10.1: Definition

A MAC is like a signature that can be added to a piece of data, which certifies that someone who knows the secret key attests to this particular data. In cryptography, the term "signature" means something specific, and slightly different than a MAC. Instead of calling the output of a MAC algorithm a signature, we call it a "tag" (or, confusingly, just "a MAC").

Our security requirement for a MAC scheme is that only someone with the secret key can generate a valid tag. To check whether a tag is valid, you just recompute the tag for a given message and see whether it matches the claimed tag. This implies that both generating and verifying a MAC tag requires the secret key.

Definition 10.1 (MAC scheme)

A message authentication code \((\mathbf{M} \boldsymbol{C})\) scheme for message space \(\mathcal{M}\) consists of the following algorithms:

• KeyGen: samples a key.
• MAC: takes a key \(k\) and message \(m \in \mathcal{M}\) as input, and outputs a tag \(t\). The MAC algorithm is deterministic.

How to Think About Authenticity Properties

Every security definition we’ve seen so far is about hiding information, so how do we make a formal definition about authenticity?

Before we see the security definition for MACs, let’s start with a much simpler (potentially obvious?) statement: "an adversary should not be able to guess a uniformly chosen \(\lambda\)-bit value." We can formalize this idea with the following two libraries:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

The left library allows the calling program to attempt to guess a uniformly chosen "target" string. The right library doesn’t even bother to verify the calling program’s guess - in fact it doesn’t even bother to sample a random target string!

The GUESS subroutines of these libraries give the same output on nearly all inputs. There is only one input \(r\) on which they disagree. If a calling program can manage to find the value \(r\), then it can easily distinguish the libraries. Therefore, by saying that these libraries are indistinguishable, we are really saying that it’s hard for an adversary to find/generate this special value! That’s the kind of property we want to express.

Indeed, in this case, an adversary who makes \(q\) queries to the Guess subroutine achieves an advantage of at most \(q / 2^{\lambda}\). For polynomial-time adversaries, this is a negligible advantage (since \(q\) is a polynomial function of \(\lambda\) ).

More generally, suppose we have two libraries, and a subroutine in one library checks some condition (and could return either true or false), while in the other library this subroutine always returns false. If the two libraries are indistinguishable, the calling program can’t tell whether the library is actually checking the condition or always saying false. This means it must be very hard to find an input for which the "correct" answer is true.

The MAC Security Definition

We want to say that only someone who knows the secret key can come up with valid MAC tags. In other words, the adversary cannot come up with valid MAC tags.

Actually, that property is not quite enough to be useful. A more useful property is: even if the adversary knows valid MAC tags corresponding to various messages, she cannot produce a valid MAC tag for a different message. We call it a forgery if the adversary can produce a "new" valid MAC tag.

To translate this security property to a formal definition, we define two libraries that allow the adversary to request MAC tags on chosen messages. The libraries also provide a mechanism to let the adversary check whether it has successfully found a forgery (since there is no way of checking this property without the secret key). One library will actually perform the check, and the other library will simply assume that forgeries are impossible. The two libraries are different only in how they behave when the adversary calls this verification subroutine on a forgery. By demanding that the two libraries be indistinguishable, we are actually demanding that it is difficult for the calling program to generate a forgery.

Definition 10.2 (MAC secure)

Let \(\Sigma\) be a MAC scheme. We say that \(\sum\) is a secure MAC if \(\mathcal{L}_{\text {mac-real }}^{\Sigma} \approx \mathcal{L}_{\text {mac-fake }}^{\Sigma}\), where:

Figure \(\PageIndex{1}\): Copy and Paste Caption here. (Copyright; author via source)

Discussion:

• The adversary can see valid tags of chosen messages, from the GETTAG subroutine. However, these tags shouldn’t count as a successful forgery. The way this is enforced is in the CHECKTAG subroutine of \(\mathcal{L}_{\text {mac-fake }}\) - instead of always responding false, it gives the correct answer (true) for any tags generated by GETTAG.

  In order for the two libraries to behave differently, the adversary must call cHECKTAG on input \((m, t)\) such that \(m\) was never used as an argument to GETTAG (so that \(\mathcal{L}_{\text {mac-fake }}\) responds false) but where the tag is actually correct (so that \(\mathcal{L}_{\text {mac-real }}\) responds true).

• The adversary can successfully distinguish if it finds any forgery - a valid MAC tag of any "fresh" message. The definition doesn’t care whether it’s the tag of any particular meaningful message.

MAC Applications

Although MACs are less embedded in public awareness than encryption, they are extremely useful. A frequent application of MACs is to store some information in an untrusted place, where we don’t intend to hide the data, only ensure that the data is not changed.

• A browser cookie is a small piece of data that a webserver stores in a user’s web browser. The browser presents the cookie data to the server upon each request.

  Imagine a webserver that stores a cookie when a user logs in, containing that user’s account name. What stops an attacker from modifying their cookie to contain a different user’s account name? Adding a MAC tag of the cookie data (using a key known only to the server) ensures that such an attack will not succeed. The server can trust any cookie data whose MAC tag is correct.

• When Alice initiates a network connection to Bob, they must perform a TCP handshake:

  1. Alice sends a special SYN packet containing her initial sequence number \(A\). In TCP, all packets from Alice to Bob include a sequence number, which helps the parties detect when packets are missing or out of order. It is important that the initial sequence number be random, to prevent other parties from injecting false packets.

  2. Bob sends a special SYN+ACK packet containing \(A+1\) (to acknowledge Alice’s \(A\) value) and the initial sequence number \(B\) for his packets.

  3. Alice sends a special \(A C K\) packet containing \(B+1\), and then the connection is established.

  When Bob is waiting for step 3, the connection is considered "half-open." While waiting, Bob must remember \(B\) so that he can compare to the \(B+1\) that Alice is supposed to send in her final ACK. Typically the operating system allocates only a very limited amount of resources for these half-open connections.

  In the past, it was possible to perform a denial of service attack by starting a huge number of TCP connections with a server, but never sending the final ACK packet. The server’s queue for half-open connections fills up, which prevents other legitimate connections from starting.

  A clever backwards-compatible solution to this problem is called SYN cookies. The idea is to let Bob choose his initial sequence number \(B\) to be a MAC of the client’s IP address, port number, and some other values. Now there is nothing to store for half-open connections. When Alice sends the final ACK of the handshake, Bob can recompute the initial sequence number from his MAC key.

These are all cases where the person who generates the \(\mathrm{MAC}\) is the same person who later verifies the MAC. You can think of this person as choosing not to store some information, but rather leaving the information with someone else as a "note to self."

There are other useful settings where one party generates a MAC while the other verifies.

• In two-factor authentication, a user logs into a service using something they know (e.g., a password) and something they have (e.g., a mobile phone). The most common two-factor authentication mechanism is called timed one-time passwords (TOTP). When you (as a user) enable two-factor authentication, you generate a secret key \(k\) and store it both on your phone and with the service provider. When you wish to log in, you open a simple app on your phone which computes \(p=M A C(k, T)\), where \(T\) is the current date \(+\) time (usually rounded to the nearest 30 seconds). The value \(p\) is the "timed one-time password." You then log into the service using your usual (long-term) password and the one-time password \(p\). The service provider has \(k\) and also knows the current time, so can verify the MAC \(p\).

  From the service provider’s point of view, the only other place \(k\) exists is in the phone of this particular user. Intuitively, the only way to generate a valid one-time password at time \(T\) is to be in posession of this phone at time \(T\). Even if an attacker sees both your long-term and one-time password over your shoulder, this does not help him gain access to your account in the future (well, not after 30 seconds in the future).