# Message Authentication Codes

:::note[Technical Summary For Cryptographers]
We give a succinct summary of the cryptographic protocols we use for securely computing MACs:

* We use [HMACs](https://en.wikipedia.org/wiki/HMAC) with [SHA256](https://en.wikipedia.org/wiki/SHA-2) and [SHA512](https://en.wikipedia.org/wiki/SHA-2) hash functions.
* For secure computation we use [Garbled Circuits](https://en.wikipedia.org/wiki/Garbled_circuit) with the [Free-XOR](https://dl.acm.org/doi/10.1007/978-3-540-70583-3_40) technique and [Half-Gates](https://eprint.iacr.org/2014/756.pdf) optimizations.
* We use the SHA-256 and SHA-512 [circuits](https://dl.acm.org/doi/pdf/10.1145/3133956.3134060) of Campanelli et al.
* We use honest-majority three-party computation of [MRZ15](https://eprint.iacr.org/2015/931.pdf).
:::

## What is a Message Authentication Code?

A Message Authentication Code (MAC) is a cryptographic primitive that enables two parties to authenticate messages sent between them.
Consider two parties, Alice and Bob, who wish to communicate securely over an untrusted channel.
When Bob receives a purported message from Alice, he wants to ensure that the message was indeed sent by Alice and was not modified in transit.
This is where MACs come into play.
A MAC is a short string of bits (the MAC) that is computed from the message and a secret key shared between Alice and Bob.

Therefore, a MAC scheme consists of three algorithms:

* $\sf Gen()$: A key generation algorithm that outputs a secret key $k$.
* $\sf Auth(k,m)$: An authentication algorithm that takes a secret key $k$ and a message $m$ and outputs a MAC $\sf c$.
* $\sf Verify(k,m,c)$: A verification algorithm that takes a secret key $k$, a message $m$ and a MAC $c$ and outputs $\sf true$ if $c$ is indeed the MAC of $m$ with respect to the key $k$. Otherwise, it outputs $\sf false$.

The MAC scheme should satisfy the following properties:

* **Correctness**: For all $k$ output by $\sf Gen()$ and for all message $m$ we have:

$$
\sf Verify(k,m, Auth(k,m)) = true
$$

* **Security**: A malicious entity who does not know the secret key $k$ and wishes to authenticate some predetermined message $m^*$ should not be able to do this even if it is being given MACs of **other** messages of its choice.

:::note
MACs and Digital Signatures are not the same.
In the setting of Digital Signatures, each party holds a private signing key that is known to nobody else.

In the setting of MACs all parties hold a shared secret key that is known to all parties.
Therefore, digital signatures allow for *non-repudiation*.
This means that given a message $m$ and a signature for $m$, the signer cannot deny, in front of a third party, signing $m$: it is the only entity that could have signed $m$.
In contrast, MACs do not provide this property as all parties holding the key could have generated the MAC.
:::

## Hash-based MACs

One way to instantiate a MAC is by using a hash function.
This is commonly referred to as a hash-based MAC or an HMAC for short.
For a cryptographic hash function $\sf H$, the HMAC is defined as:

* $\sf Gen()$ outputs a sufficiently long random key $k$ (say, 128 bits).
* $\sf Auth(k,m)$ computes the MAC as:

$$
\sf c = H(k \oplus \text{pad}_1 || H(k \oplus \text{pad}_2 || m))
$$

where $\text{pad}_1$ and $\text{pad}_2$ are two fixed strings of bits (the padding).

* $\sf Verify(k,m,c)$ simply checks whether $c$ is equal to $\sf Auth(k,m)$.

## How are MACs related to API Keys?

Internet applications often use API keys to authenticate requests.
The most common way to use API keys is to include them in the request header.
This is a simple and effective way to authenticate requests, but it does not ensure that the request was not modified in transit.
Alternatively, API keys can be used as HMAC keys.
Then, when sending a request, the client computes the HMAC of the request and includes it in the request header.
The server, upon receiving the request, computes the HMAC of the request and compares it to the HMAC included in the request header.
In case of a mismatch, the server rejects the request.