密码学Hash函数
Hash函数将可变长度的数据块 M M M作为输入，产生固定长度的Hash值 h = H a s h ( M ) h=Hash(M) h=Hash(M)
目标
- 输出的结果均匀分布且看起来随机
- 对于消息某一位或几位的改变极大可能改变Hash值
安全性
- 单向性
对于指定的Hash值找到对应的数据块不可行
- 抗碰撞性
找到不同数据块对应相同的Hash不可行
Hash函数用于确定数据是否被篡改，即保证完整性
Hash的应用
消息认证
消息认证是用来验证消息完整性的一种机制或服务。
消息认证确保收到的数据确实和发送时一样（无修改、插入、删除、重放）。要求消息认证机制确保发送方声称的身份真实有效。
Hash运算的结果必须安全传输。Hash值不能够轻易修改。
-
（a）提供保密性，完整性和认证性
-
（b）提供完整性和认证性
由Hash抗碰撞性保证安全
-
（c）提供完整性和认证性
添加双方商定的秘密值 s s s
由Hash单向性保证安全
-
（d）提供保密性，完整性和认证性
消息认证使用消息认证码MAC实现，即带密钥的Hash
数字签名
需求与安全性
安全性需求
-
输入长度可变
-
输出长度不变
-
效率
-
抗原像攻击（单向性）
-
抗第二原像攻击（抗弱碰撞性）
- 对于给定 x x x有 h = H a s h ( x ) h=Hash(x) h=Hash(x)，找到 y y y满足 h = H a s h ( y ) h=Hash(y) h=Hash(y)不可行
-
抗碰撞攻击（抗强碰撞性）
- 找到 x , y x,y x,y使 H a s h ( x ) = H a s h ( y ) Hash(x)=Hash(y) Hash(x)=Hash(y)不可行
-
伪随机性
穷举攻击
原像攻击和第二原像攻击
- 第一类生日攻击
对于给定 x x x有 h = H a s h ( x ) h=Hash(x) h=Hash(x)，找到 y y y满足 h = H a s h ( y ) h=Hash(y) h=Hash(y)
代价 2 m − 1 2^{m-1} 2m−1
- 第二类生日攻击
找到 x , y x,y x,y使 H a s h ( x ) = H a s h ( y ) Hash(x)=Hash(y) Hash(x)=Hash(y)
代价 2 m / 2 2^{m/2} 2m/2
- 攻击者产生真消息集合{ x ， x ′ . . . x，x'... x，x′...}，假消息集合{ y ， y ′ . . . y，y'... y，y′...}
- 在两个集合中寻找碰撞 H a s h ( x i ) = H a s h ( y j ) Hash(x_i)=Hash(y_j) Hash(xi)=Hash(yj)
- 将 x i x_i xi发送给发送方进行签名，叫消息替换为 y j y_j yj发送给接收方，则可以通过验证
一般认为160位Hash值是安全的
密码分析
典型的Hash结构
- 预处理（填充）
- 迭代
- 输出变换
安全的Hash算法
MD系列
-
填充
- l e n g t h = 448 m o d 512 length=448\mod512 length=448mod512
-
附加消息长度
-
初始化MD缓冲区
128位缓冲区
-
以512bit的分组为单位处理消息
-
输出
Hash值中的每一个比特是所有输入比特的函数
SHA系列
-
SHA-1：160bit
-
SHA-2
- SHA-256：256bit
- SHA-384：384bit
- SHA-512：512bit
SHA-1
-
填充
- l e n g t h = 448 m o d 512 length=448\mod512 length=448mod512
-
附加消息长度
-
初始化缓冲区
- 160位缓冲区
-
以512bit的分组为单位处理消息
- 迭代80轮
-
输出
SHA-3
海绵结构，输入输出长度可变