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

海绵结构，输入输出长度可变