§10 Hash Functions and Hash-and-MAC

Hash Functions

Hash Functions: Definition

• Definition. A Hash Function with output length $l$ is a pair of probabilistic polynomial-time algorithms $(Gen, H)$ satisfying the following:
  • $Gen$ is a probabilistic algorithm that takes as input a security parameter $1^n$ and outputs key $s$.
  • $H$ takes as input a key $s$ and a string $x \in \{0,1\}^*$ and outputs a string $H^s(x) \in \{0,1\}^{l(n)}$ where $n$ is the security parameter that is implicit in $s$.

Collision-Finding Experiment $\text {Hash-coll}_{\mathscr{A}, \Pi}(n)$

• For a Hash Function $\Pi = (Gen, H)$, an adversary $\mathscr{A}$, and a security parameter $n$, the collision-finding experiment $\text {Hash-coll}_{\mathscr{A}, \Pi}(n)$ is defined as follows:
  1. A key $s$ is generated by running $Gen (1^n)$.
  2. The adversary $\mathscr{A}$ is given $s$ and outputs $x, x'$. If $\Pi$ is a fixed-length hash function for inputs of length $l'(n)$, then we require $x, x' \in \{0,1\}^{l'(n)}$.
  3. The adversary succeeds in finding a collision and the output of the experiment is defined to be $1$ if and only if $x \ne x'$ and $H^s(x) = H^s(x')$.

Security Definition

• Definition. A Hash Function $\Pi = (Gen, H)$ is collision-resistant if for all probabilistic polynomial-time adversaries $𝒜$ there is a negligible function $\epsilon$ such that

  $$\Pr[\text {Hash-coll}_{\mathscr{A}, \Pi}(n)] \le \epsilon(n)$$

Weaker Notions of Security

• Definition. Second-preimage or target-collision resistance. A Hash Function $\Pi = (Gen, H)$ is second preimage resistant if given $s$, and uniform $x$, it is infeasible for any PPT adversary to find $x' \ne x$, such that $H^s(x') = H^s(x)$.
  • Proposition. Collision Resistance $\Longrightarrow$ Second Preimage Resistance
• Definition. Preimage resistance. A Hash Function $Π = (Gen, H)$ is preimage resistant if given $s$, and uniform $y$, it is infeasible for any PPT adversary to find $x$, such that $H^s(x) = y$.
  • Proposition. Second Preimage Resistance $\Longrightarrow$ Preimage Resistance

Generic Attacks on Hash Functions

• Simple Collision-Finding Attack: Compute $H(x_1), \ldots , H(x_{2^n+1})$, for $2^n + 1$ distinct inputs.

  We are guaranteed to find a collision, by Pigeonhole Principle, if the output is of length $n$. Running time of the attack: $O(2^n)$.

• Birthday Attacks: Compute $H(x_1),\ldots, H(x_{2^{n/2}} )$.

  We are not guaranteed to find a collision. But with non-negligible probability, we can find two inputs that map to the same output. Running time of the attack: $O(2^{n/2})$.

Birthday Attacks for finding collisions

• Theorem. In the balls into bins problem with $m$ balls and $N$ bins, when $m$ is $\Theta(N^{1/2})$, the probability of a collision, i.e., of two balls falling into the same bin is approximately $50\%$.

• Theorem. Let $r_1,\ldots, r_m \in \{1,\ldots, N\}$ be independent identically distributed integers. When $m = 1.2\sqrt{N}$, then $\displaystyle \Pr\left[\exists i \neq j: r_{i}=r_{j}\right] \geq \frac{1}{2}$.

• Let $H^s : \mathscr{M} \leftarrow \{0,1\}^n$ be a hash function, with $|\mathscr{M}| \gg 2^n$.

  The following is a generic algorithm to find a collision in time $O(2^{n/2})$.

  1. Choose $2^{n/2}$ random messages in $\mathscr{M} : m_1,\ldots, m_{2^{n/2}}$.
  2. For $i = 1,\ldots,2^{n/2}$, compute $y_i := H^s(m_i) \in \{0,1\}^n$.
  3. Look for a collision, i.e., look for $y_i = y_j$. If not found, go back to step 1.

Birthday Attacks: Implications

• Implication: We need Hash Functions $H$ with $2n$-bit output length to get security against attackers trying to find collisions running in $2^n$ time.

Hash-and-MAC

The Hash-and-MAC construction (alternative to CBC-MAC)

• Hash-and-MAC construction: Let $\Pi = (Mac, Vrfy)$ be a MAC for messages of length $l(n)$, and let $\Pi_H = (Gen_H, H)$ be a hash function with output length $l(n)$.
• Construct a MAC $Π' = (Gen' , Mac' , Vrfy' )$ for arbitrary-length messages as follows:
  • $Gen'$: Given input $1^n$, choose uniform $k \in \{0,1\}^n$ and run $Gen_H(1^n)$ to obtain $s$, the key is $k' := \langle k, s \rangle$.
  • $Mac'$: Given input key $\langle k, s \rangle$ and a message $m \in \{0,1\}^*$, output $t \leftarrow Mac_k(H^s(m))$.
  • $Vrfy'$: Given input key $\langle k, s \rangle$, a message $m \in \{0,1\}^*$, and a MAC tag $t$, output $1$ if and only if $Vrfy_k (H^s(m), t) = 1$.

Security of Hash-and-MAC construction

• Theorem: If $\Pi$ is a secure MAC for short messages of length $l$, and $\Pi_H$ is collision-resistant, then the Hash-and-Mac construction $\Pi'$ is a secure MAC for arbitrary-length messages.

— Feb 28, 2023

§10 Hash Functions and Hash-and-MAC by Lu Meng is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. Permissions beyond the scope of this license may be available at About.