密码学Hash函数基础

密码学Hash及其应用

Hash函数 $H$ 可将不定长的数据块 $M$ 作为输入，产生固定长度的Hash值 $h = H (M)$
一个好的Hash函数要求对于大的输入集合使用该函数，产生的结果均匀且看起来随机

在安全应用中使用的Hash函数称为密码学Hash函数，密码学Hash函数有如下几种应用

消息认证

当Hash函数用于提供消息认证功能时，Hash值通常称为消息摘要

假设A要给B发送消息M，则A计算Hash值 $h = H (M)$ 并将 $h$ 和消息一同发送
B接收到消息后执行相同Hash计算，若Hash值结果不相同，则推断接受到的消息或Hash值遭到了篡改

消息认证中Hash值必须以安全得方式传输，否则会受到中间人攻击
即攻击者截获消息和消息摘要，篡改消息并重新计算Hash值后再重新发送给接收人

一般的，消息认证是通过消息认证码MAC，即带密钥的Hash函数实现的

数字签名

Hash函数可以和公钥密码结合提供数字签名

假设假设A要给B发送消息M，则A用自己的私钥加密消息摘要，B则用A的公钥解密并验证消息摘要
若消息M需要保密，则可以继续使用B的公钥对M和加密后的消息摘要进行加密

产生单向口令、构建PRNG等其他应用

密码学Hash的安全性

安全要求

密码学Hash除了要满足Hash函数的基本要求外，还要求满足

单向性（抗原像攻击）：对指定的Hash值找到对应的数据块在计算上不可行
抗碰撞性：找到两个不同数据块对应相同Hash值在计算上不可行，它又可以分为
- 抗弱碰撞性（抗第二原像攻击）：对任何给定数据块x，找到满足y≠x且 $H (x) = H (y)$ 的y在计算上不可行
- 抗强碰撞性（抗碰撞攻击）：找到任何满足 $H (x) = H (y)$ 的偶对(x,y)在计算上不可行

满足抗弱碰撞性的Hash函数称为弱Hash函数，满足抗强碰撞性的则称为强Hash函数

一个Hash函数如果是抗强碰撞的，那它一定是抗弱碰撞的，反之则不一定
此外抗强/弱碰撞的Hash函数不一定是抗原像攻击的，反之亦然

如图所示，在不同环境下对密码学Hash有不同要求

原像攻击和第二原像攻击

原像攻击和第二原像攻击中，攻击者对给定的Hash值h，试图随机选择 $y$ ，直到满足 $H (y) = h$ 的 $y$ 出现

对于输出为 $m$ 位的Hash函数，攻击者平均要尝试 $2^{m - 1}$ 次才能找到满足条件的 $y$

这个结论等价于证明攻击者尝试 $2^{m - 1}$ 次找到满足条件的 $y$ 的概率为 $\frac{1}{2}$ ，证明如下
若函数 $H$ 有 $n$ 个可能输出，取 $k$ 个随机 $y$ ，至少有一个输出满足 $H (y) = h$ 的概率为 $p = 1 - (1 - \frac{1}{n})^{k}$
由 $x \to 0$ 时 $(1 + x)^{k} = 1 + k x$ 可知，当 $n$ 很大时， $p = 1 - (1 - \frac{k}{n}) = \frac{k}{n}$
因此当 $k = \frac{n}{2}$ 时 $p = \frac{1}{2}$

碰撞攻击

碰撞攻击中，攻击者试图找到两个消息x和y，满足 $H (x) = H (y)$

根据生日悖论，该攻击的穷举规模比原像攻击和第二原像攻击要更小
实际上，若已知一个在1到n之间均匀分布的随机整数变量，则在 $\sqrt{n}$ 次取值后重复的概率就会大于 $\frac{1}{2}$
因此对于输出为 $m$ 位的Hash函数，大约在 $\sqrt{2^{m}} = 2^{\frac{m}{2}}$ 次尝试后就会找到两个由相同Hash值的x、y

安全Hash总体结构

典型的安全Hash函数结构由Merkle提出，包括SHA在内的目前所使用的大多数Hash函数都是这种结构

首先将输入消息分为L个固定长度的分组，每一分组长为b位，最后一个分组不足b位时填充为b位，最后一个分组包含输入的总长度

由于输入中包含长度信息，攻击者必须找出长度相等且Hash值相同的两条消息，或找出长度不等但长度后Hash值相同的消息，从而增加了攻击的难度

安全Hash函数结构就是使用压缩函数 $f$ 对消息分组迭代压缩
每一轮 $f$ 的输入为上一轮的结果和本轮分组

Merkele发现，若压缩函数 $f$ 具有抗碰撞性，则该迭代Hash也具有抗碰撞性