Message Authentication Codes

Technical Summary For Cryptographers

We give a succinct summary of the cryptographic protocols we use for securely computing MACs:

• We use HMACs with SHA256 and SHA512 hash functions.
• For secure computation we use Garbled Circuits with the Free-XOR technique and Half-Gates optimizations.
• We use the SHA-256 and SHA-512 circuits of Campanelli et al.
• We use honest-majority three-party computation of MRZ15.

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