密码学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_security

原像攻击和第二原像攻击

原像攻击和第二原像攻击中，攻击者对给定的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+kx$可知，当$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$的输入为上一轮的结果和本轮分组

hash_structure

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