MAC - Message Authentication Code

Encryption in general does not solve the problem of message integrity.

The aim of message authentication code is to prevent any adversary from modifying the message sent by one party to another, or from injecting a new message, without the receiver detecting that the message did not originate from the intended party.

Formally, A message authentication code or $\text{MAC}$ consists of three probabilistic polynomial time algorithms $\text{(Gen, Mac, Vrfy)}$ such that:

1. the key generation algorithm $\text{Gen}$ takes as input the security parameter $1^n$ and outputs a key $k$ with $|k| \ge n$
2. the tag generation algorithm $\text{Mac}$ takes as input a key $k$ and a message $m \in \{0, 1\}^*$ and outputs a tag $t$ i.e. $t \leftarrow \text{Mac}_k(m)$
3. the deterministic verification algorithm takes as input $k$, a message $m$ and a tag $t$. It outputs a bit $b$ with $b=1$ as valid and $b=0$ as invalid tag i.e. $b := \text{Vrfy}_k(m, t)$

Security of MACs:

Formally, The message authentication experiment $\text{Mac-forge}_{\mathcal{A}, \Pi}(n)$:

1. a key $k$ is generated by running $\text{Gen}(1^n)$
2. the adversary $\mathcal{A}$ is given input $1^n$ and oracle access to $\text{Mac}_k(\cdot)$. the adversary eventually outputs $(m, t)$. Let $\mathcal{Q}$ be the set of queries that $\mathcal{A}$ asked its oracle.
3. $\mathcal{A}$ succeeds iff
   1. $\text{Vrfy}_k(m, t) = 1$
   2. $m \notin \mathcal{Q}$

The intuitive idea behind the definition is that no efficient adversary should be able to generate a valid tag on any new message that was not previously sent by one of the communicating parties.

A message authentication code is secure if for all PPT adversaries $\mathcal{A}$,

Fixed Length Mac:

Pseudorandom functions are a natural tool for constructing secure message authentication codes. If the tag $t$ is obtained by applying it on $m$, then forging a tag requires the adversary to correctly guess the value of the pseudorandom function at a new input $m^\prime$.

Construction:

Let $F$ be a pseudorandom function.

• $\text{Mac}$: on input a key $k \in \{0, 1\}^n$ and a message $m \in \{0, 1\}^n$, output the tag $t := F_k(m)$
• $\text{Vrfy}$: on input a key $k \in \{0, 1\}^n$, a message $m \in \{0, 1\}^n$ and a tag $t \in \{0, 1\}^n$, output $1$ iff $t = F_k(m)$.

Discussion:

• If $F$ is pseudorandom function, then the above construction is a secure fixed length MAC for messages of length $n$.

CBC-MAC:

Basic Construction:

Insecure Construction Ahead

This basic scheme is not secure in the general case when messages of different lengths may be authenticated Please refer here to understand why this scheme is not secure.

Let $F$ be a pseudorandom function and a fix length function $n \gt 0$

• $\text{Mac}$: on input a key $k \in \{0, 1\}^n$ and a message $m$ of length $l \cdot n$
  1. Parse $m$ as $m = m_1, \dots, m_l$ where $|m_i| = n$
  2. Set $t_0 = 0^n$. Then $t_i = F_k(t_{i-1} \oplus m_i)$
  3. Output $t_l$ as the tag.
• $\text{Vrfy}$: on input a key $k \in \{0, 1\}^n$, a message $m$ and tag $t$
  1. if $m$ is not of length $l.n$ output $0$
  2. output $t == \text{Mac}_k(m)$

CBC-MAC vs CBC encryption

1. CBC mode encryption uses random $IV$ and this is crucial for security. CBC-MAC’s $IV$ is $0^n$ and this is also crucial for security. random $IV$ is not secure for CBC-MAC

Secure CBC-MAC for arbitrary length messages:

There are two ways the above construction can be modified. Here we will discuss only one.

1. Prepend the message $m$ with its length $|m|$ and then compute basic CBC-MAC on the result

Hash Functions

• Hash functions are simply functions that take inputs of some length and compress then into short fixed-length outputs
• A good hash function is the one that yields few collisions, where a collision is a pair of distinct items $x$ and $x^\prime$ such that $H(x) = H(x^\prime)$
• Collision-resistant hash functions are similar in spirit. The goal is to avoid collisions. However there are fundamental differences. For one, the desire to minimise collisions in the setting of data structures becomes a requirement in the setting of cryptography.

Collisions resistance

A function is collision resistant if it is infeasible for any probabilistic polynomial time algorithm to find a collision in $H$.

Formally, we consider keyed hash functions. That is $H$ is a two-input function that takes as input a key $s$ and a string $x$, and outputs a string.

The requirement is that it must be hard to find a collision in $H^s$ for a randomly generated key $s$.

There are at least one differences between the keys in this context and what we have seen till now. The key $s$ is generally not kept secret and collision resistance is required even when the adversary is given the key $s$.

Unkeyed Hash Functions

Cryptographic hash functions used in practice generally have a fixed output length and are usually unkeyed meaning that the hash function is just a fixed function

This is problematic from a theoretic standpoint since for any such function there is always a constant time algorithm that outputs a collision in $H$

However, the unkeyed cryptographic hash functions used in real world are collisions resistant for all practical purposes since colliding pairs are unknown and computationally difficult to find.

Domain Extension: Merkle Damgard Transform

Hash functions are often constructed by first designing a collision resistant compression function handling fixed length inputs and then using domain extension to handle arbitrary length inputs.

Merkle Damgard transform is a common approach for extending a compression functions to a full fledged hash function while maintaining the collision resistant property.

The existence of this transform means that when designing collision resistant hash functions we can restrict our attention to the fixed length case.

Message Authentication using Hash functions

Hash and MAC

The idea behind hash and MAC approach is simple

1. an arbitrarily long message $m$ is hashed down to a fixed length string $H^s(m)$ using a collision resistant hash function
2. A fixed length $\text{MAC}$ is applied to the result

The above construction is secure for arbitrarily long messages $m$ if the $\text{MAC}$ is a secure MAC function and the hash function $H^s$ is a collision resistant hash function.

HMAC:

good reference: https://crypto.stackexchange.com/questions/1070/why-is-hk-mathbin-vert-x-not-a-secure-mac-construction

Construction:

• Let $(\text{Gen}_H, H)$ be a hash function constructed using Merkle Damgard transform to a compression function $(Gen_H, h)$ taking inputs of length $n + n^\prime$.

• Let $\text{opad}$, $\text{ipad}$ be a fixed constants of length $n^\prime$

• define MAC as follows:

• $\text{Gen}$: on input $1^n$, run $\text{Gen}_H(1^n)$ to obtain key $s$. Also choose uniform $k \in \{0, 1\}^{n^{\prime}}$. Output key $\langle s, k\rangle$

• $\text{Mac}$: on input key $\langle s, k\rangle$ and message $m \in \{0, 1\}^*$, output

  $$t := H^s((k \oplus \text{opad}) \mathbin{||} H^s((k \oplus \text{ipad}) \mathbin{||} m))$$

• $\text{Vrfy}$: on input key $\langle s, k\rangle$ and message $m \in \{0, 1\}^*$ and a tag $t$, output $1$ iff

  $$t = H^s((k \oplus \text{opad}) \mathbin{||} H^s((k \oplus \text{ipad}) \mathbin{||} m))$$

Roles of $\text{ipad}$ and $\text{opad}$

The reason is that this allows security of HMAC to be based on the potentially weaker assumption that $(Gen_H,H)$ is weakly collision resistant.

This is a defensive strategy that paid off when it was discovered that the hash function $\text{MD5}$ is not collision resistant.

The collision finding attacks on $\text{MD5}$ did not violate weak collision resistance and $\text{HMAC-MD5}$ was not broken even though $\text{MD5}$ was.

This gave developers time to replace $\text{MD5}$ in $\text{HMAC}$ implementations without immediate fear of attack.

The above discussion suggests that independent keys should be used in the outer and inner computations. for reasons of efficiency, a single key $k$ is used but the key is used in combination with $\text{ipad}$ ad $\text{opad}$ to derive two other keys.