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\}^∗\) 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'(n) > \ell(n)\), then we say that \((\text{Gen}, H)\) is a fixed-length hash function for inputs of length \(\ell'(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))\):
- A key \(s\) is generated by running \(\text{Gen}(1^n)\).
- The adversary \(\mathcal{A}\) is given \(s\), and outputs \(x, x'\) . (If \(H\) is a fixed-length hash function for inputs of length \(\ell'(n)\), then we require \(x, x' \in \{0, 1\}^{\ell'(n)}\).)
- The output of the experiment is defined to be \(1\) if and only if \(x = x'\) and \(H^s(x) = H^s(x')\). In such a case we say that \(\mathcal{A}\) has found a collision.
如果 \(\text{Pr}[\text{Hash-coll}_{\mathcal{A},\mathcal{H}(n)}=1]\leq\text{negl}(n)\)，则称 \(\mathcal{H}\) 是collision resistant的。
下面给出两个其他关于哈希安全的概念。
- Second-preimage resistance 给出 \(s\) 和一个均匀分布的 \(x\)，一个PPT的 \(\mathcal{A}\) 几乎无法找到 \(x'\) 使得 \(x\neq x',H(x)=H(x')\)
- Preimage resistance 给出 \(s\) 和 \(y=H^s(x)\) 对于一个均匀分布的 \(x\)，一个PPT的 \(\mathcal{A}\) 几乎无法找到 \(x'\) 使得 \(H(x)=H(x')\) (\(x'\) 可以等于 \(x\))
Merkle–Damgård 变换
Merkle–Damgård 变换可以将一个固定长度的哈希函数，用于任意长度的输入。
Let \((\text{Gen}, h)\) be a compression function for inputs of length \(n + n' \geq 2n\) with output length \(n\). Fix \(\ell \leq n'\) 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\}^∗\) of length \(L < 2^{\ell}\) , do:
- 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'\). Then append \(L\), encoded as an \(\ell\)-bit string. Parse the resulting string as the sequence of \(n'\)-bit blocks \(x_1,...,x_B\).
- Set \(z_0 := IV\).
- For \(i=1,...,B\), compute \(z_i := h^s(z_{i−1}|| x_i)\).
- 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.