Introduction to Modern Cryptography(6)

Introduction to Modern Cryptography Reading Notes

6 Hash Functions and Applications

哈希函数的定义

A hash function (with output length $\ell (n)$) is a pair of probabilistic polynomial-time algorithms $(\text{Gen},H)$ satisfying the following:

• $\text{Gen}$ is a probabilistic algorithm that takes as input a security parameter $1^n$ and outputs a key $s$. We assume that $n$ is implicit in $s$.
• $H$ is a deterministic algorithm that takes as input a key $s$ and a string $x\in \{0,1{\}}^{\ast }$ and outputs a string $H^s(x)\in \{0,1{\}}^{\ell (n)}$ (where $n$ is the value of the security parameter implicit in $s$).

If $H^s$ is defined only for inputs $x$ of length ${\ell }^{\prime }(n)>\ell (n)$, then we say that $(\text{Gen},H)$ is a fixed-length hash function for inputs of length ${\ell }^{\prime }(n)$. In this case, we also call $H$ a compression function.

在这里，攻击者往往会知道 $s$ 的值，因此 $s$ 放在 $H$ 的上标。

The collision-finding experiment ${\text{Hash-coll}}_{\mathcal{A},\mathcal{H}(n)}$ $(\mathcal{H}=(\text{Gen},H))$:

1. A key $s$ is generated by running $\text{Gen}(1^n)$.
2. The adversary $\mathcal{A}$ is given $s$, and outputs $x,x^{\prime }$ . (If $H$ is a fixed-length hash function for inputs of length ${\ell }^{\prime }(n)$, then we require $x,x^{\prime }\in \{0,1{\}}^{{\ell }^{\prime }(n)}$.)
3. The output of the experiment is defined to be $1$ if and only if $x=x^{\prime }$ and $H^s(x)=H^s(x^{\prime })$. In such a case we say that $\mathcal{A}$ has found a collision.

如果 $\text{Pr}[{\text{Hash-coll}}_{\mathcal{A},\mathcal{H}(n)}=1]\le \text{negl}(n)$，则称 $\mathcal{H}$ 是collision resistant的。

下面给出两个其他关于哈希安全的概念。

• Second-preimage resistance 给出 $s$ 和一个均匀分布的 $x$，一个PPT的 $\mathcal{A}$ 几乎无法找到 $x^{\prime }$ 使得 $x\ne x^{\prime },H(x)=H(x^{\prime })$
• Preimage resistance 给出 $s$ 和 $y=H^s(x)$ 对于一个均匀分布的 $x$，一个PPT的 $\mathcal{A}$ 几乎无法找到 $x^{\prime }$ 使得 $H(x)=H(x^{\prime })$ ($x^{\prime }$ 可以等于 $x$)

---

Merkle–Damgård 变换

Merkle–Damgård 变换可以将一个固定长度的哈希函数，用于任意长度的输入。

Let $(\text{Gen},h)$ be a compression function for inputs of length $n+n^{\prime }\ge 2n$ with output length $n$. Fix $\ell \le n^{\prime }$ and $IV\in \{0,1{\}}^n$. Construct hash function $(\text{Gen},H)$ as follows:

• $\text{Gen}$: remains unchanged.

• $H$: on input a key $s$ and a string $x\in \{0,1{\}}^{\ast }$ of length $L<2^{\ell }$ , do:

  1. Append a $1$ to $x$, followed by enough zeros so that the length of the resulting string is $\ell$ less than a multiple of $n^{\prime }$. Then append $L$, encoded as an $\ell$-bit string. Parse the resulting string as the sequence of $n^{\prime }$-bit blocks $x_1,...,x_B$.
  2. Set $z_0:=IV$.
  3. For $i=1,...,B$, compute $z_i:=h^s(z_{i-1}||x_i)$.
  4. Output $z_B$.

可以证明，如果 $(\text{Gen},h)$ 是 collision resistent 的，那么 $(\text{Gen},H)$ 也是。（证明先跳过）

---

使用哈希函数的消息认证

---

对哈希函数的一般攻击

---

The Random-Oracle Model

random-oracle model 将哈希函数视为一个随机函数，假设存在一个随机函数 $H$，只能通过黑盒访问 $H$ 获取 $H(x)$ 的值。

注意，random-oracle model 不是伪随机函数，因为伪随机函数只有在 key 保密时是伪随机的，但是所有群体都能计算 random-oracle model，不可能有一个保密的 key。

If $x$ has not been queried to $H$, then the value of $H(x)$ is uniform.

If $\mathcal{A}$ queries $x$ to $H$, the reduction can see this query and learn $x$.

The reduction can set the value of $H(x)$ (i.e., the response to query $x$) to a value of its choice, as long as this value is correctly distributed, i.e., uniform.