网络安全-10-密码学Hash函数

1、n单纯的加解密算法无法保证抵抗下述攻击q伪装q内容修改q顺序修改q计时修改q发送方否认q接收方否认消息认证码数字签名不属于机密性范畴,属于数据完整性范畴Chapter 11 密码学密码学Hash函数函数哈希函数（杂凑函数）（1）Hash编码；编码；（2）Hash函数；函数；（3）散列编码：）散列编码：（4）散列函数；）散列函数；（5）单向压缩函数。）单向压缩函数。哈希函数 在公钥密码的内容中，已经介绍了“单向函数”的概念。而哈希函数是一类特殊的单向函数。 设数据文件是任意长度的比特串x 。在密码应用中，希望有这样的函数 y=H(x)，满足： （1）将x压缩成为固定长度的比特串y。 （2）不同的

2、x一定要生成不同的y。（一般情况） （3）由y的值无法倒算x的值。2022-5-20西安电子科技大学计算机学院5Hash函数函数n浓缩任意长的消息浓缩任意长的消息M到一个固定到一个固定长度的取值长度的取值 h = H(M) n通常假设通常假设hash函数是公开的且不函数是公开的且不使用密钥（使用密钥（MAC使用密钥）使用密钥）nHash函数用户检测对消息的改变函数用户检测对消息的改变密码学密码学Hash函数函数2022-5-20西安电子科技大学计算机学院7哈希函数的应用哈希函数的应用n消息认证消息认证n数字签名数字签名Hash函数用于消息认证2022-5-20西安电子科技大学计算机学院8Has

3、h函数用于消息认证2022-5-20西安电子科技大学计算机学院9Hash函数用于数字签名2022-5-20西安电子科技大学计算机学院10Hash函数的其他用途q给明文增加结构特征以保护密文q从口令衍生密钥q挑战-应答认证协议中q用来产生随机数2022-5-20西安电子科技大学计算机学院11密码学Hash函数的基本性质n单向性：对于预先给定的Hash值找不到对应的数据块 抗碰撞性：找不到不同的数据块对应相同的Hash值2022-5-20西安电子科技大学计算机学院12Hash函数 h=H(x)的安全性要求n函数参数q输入：可以任意长度q输出：必须固定长度n比特，一般n=128、160bitsn函数

4、特性q效率：给定x，计算H(x)h是容易的q单向性：给定h，要找x使H(x)h是困难的q弱抗碰撞特性：对于给定的y，找x，使H(x)H(y)是困难的q强抗碰撞特性（生日攻击）： 找(x1, x2)，x1x2，H(x1)= H(x2)是困难的q伪随机性：输出满足伪随机测试标准2022-5-20西安电子科技大学计算机学院13找碰撞：生日攻击n最多尝试2n1个报文，必有至少一对碰撞n问：平均尝试多少个报文，可以以1/2的概率找到一对碰撞？ 2n/2n类比问题（生日问题）q最多找365+1个人，则必有至少两个人生日相同q问：平均找多少个人，能以1/2的概率找到两人生日相同？23n如果采用64-bit的

5、Hash码，以一半概率找到碰撞的代价的数量级是2322022-5-20西安电子科技大学计算机学院14生日悖论2022-5-20西安电子科技大学计算机学院15Hash安全特性之间的关系抗原像攻击抗原像攻击抗弱碰撞攻击抗弱碰撞攻击抗强碰撞攻击抗强碰撞攻击2022-5-20西安电子科技大学计算机学院16Hash函数设计考虑n奇偶校验q异或XOR（或者累加）q只能检出奇数个比特错误nCRCq常用在帧校验q仍有很高的比率不能检出传输比特错误* 不能满足单向性和抗碰撞性n复杂的密码学用散列函数qMD2/MD5qSHA/SHA12022-5-20西安电子科技大学计算机学院17基于分组密码的散列函数的缺点n不

6、利于随机化q因为加密是可逆的，q分组密码存在规则性n分组密码通常很慢n分组密码分组长度小于散列值长度q通常64位或128位 vs. 128/160/256/384/5122022-5-20西安电子科技大学计算机学院19Hash算法算法nHash函数和分组密码的发展变化具有相函数和分组密码的发展变化具有相似性似性q穷举攻击能力的增强穷举攻击能力的增强q算法的不断改进算法的不断改进q分组密码：从分组密码：从DES 到到 AES qHash算法算法: 从从MD4 、MD5 到到 SHA-1、RIPEMD-160、SHA-512、Whirlpool2022-5-20西安电子科技大学计算机学院20n由由

7、Ronald Rivest设计设计nMD2(1989), MD4(1990), MD5(1991) n产生产生128-bit的的hash值值n直到现在仍是被广泛使用的直到现在仍是被广泛使用的hash算法算法q最近已受到穷举攻击和密码分析攻击最近已受到穷举攻击和密码分析攻击n作为互联网的作为互联网的RFC1321标准标准2022-5-20西安电子科技大学计算机学院21MD5 概览概览1.增加填充位。使得填充后的消息长度比增加填充位。使得填充后的消息长度比512的某整数倍的某整数倍少少64位（即长度位（即长度 448 mod 512，64位用于存放消息的位用于存放消息的长度长度mod 264的结果

8、）的结果）2.填充长度（填充前消息的长度为填充长度（填充前消息的长度为K位，将位，将mod264 的结的结果填充到第一步的最后，最低有效位在前。）果填充到第一步的最后，最低有效位在前。）3.初始化初始化MD缓冲区缓冲区(A, B, C, D) : 4个字共个字共128-bit，每字，每字32bit.A = 67452301 B = EFCDAB89C = 98BADCFE D = 103254764.以以16个字（个字（512bits）为分组处理消息）为分组处理消息q用用4轮（轮（64次迭代）以次迭代）以16位操作对消息分组和缓冲区进行位操作对消息分组和缓冲区进行处理处理q把输出与缓冲输入相加

9、作为新的缓冲值把输出与缓冲输入相加作为新的缓冲值 5.把最后的缓冲值作为把最后的缓冲值作为hash输出值（输出值（128比特）比特）2022-5-20西安电子科技大学计算机学院22MD5 处理过程处理过程n CV0 = IVn CVq+1 = SUM32 CVq, RFI(Yq, RFH(Yq, RFG(Yq, RFF(Yq, CVq)n MD = CVL-1其中：其中：IV = 第三步定义的缓冲区第三步定义的缓冲区ABCD的初值的初值Yq = 消息的第消息的第q个个512位分组位分组L = 消息分组的个数（包括填充位和长度域）消息分组的个数（包括填充位和长度域）CVq = 处理消息的第处理消

10、息的第q个分组时所使用的链接变量个分组时所使用的链接变量RFx = 使用基本逻辑函数使用基本逻辑函数x的轮函数的轮函数MD = 消息摘要消息摘要SUM32 = 对输入字分别执行模对输入字分别执行模232加法加法2022-5-20西安电子科技大学计算机学院23MD5 Overview2022-5-20西安电子科技大学计算机学院232022-5-20西安电子科技大学计算机学院242022-5-20西安电子科技大学计算机学院25MD5的强度的强度nMD5的的hash值依赖于消息的所有比特位值依赖于消息的所有比特位nRivest声称它对于已知攻击安全性足够好声称它对于已知攻击安全性足够好:qBerso

11、n 92 采用差分的方法对单轮的攻击采用差分的方法对单轮的攻击qBoer & Bosselaers 93 说明了如何找到碰撞说明了如何找到碰撞qDobbertin 96 提出的攻击对提出的攻击对MD5最具威胁，可使最具威胁，可使MD5压缩函数产生碰撞。压缩函数产生碰撞。n结论是结论是MD5似乎不久就会有风险似乎不久就会有风险2022-5-20西安电子科技大学计算机学院2612.2 安全安全Hash算法算法(SHA-1)nSHA 由由NIST 和和NSA在在1993年提出年提出, 修订版于修订版于 1995年发布，称作年发布，称作SHA-1n作为美国作为美国DSA数字签名方案的标准数字签

12、名方案的标准qFIPS 180-1 1995, Internet RFC3174q注意：算法是注意：算法是SHA, 标准称为标准称为SHS n产生产生160-bit hash值值 n现在作为建议的现在作为建议的hash算法算法 n基于基于MD4的设计的设计2022-5-20西安电子科技大学计算机学院27SHA 概览概览1.增加填充位增加填充位 2.填充长度填充长度3.初始化初始化5个字个字(160-bit) 缓冲区缓冲区(A, B, C, D, E) 为为 (67452301, efcdab89, 98badcfe, 10325476, c3d2e1f0) 4.以以16个字（个字（512-bi

13、t ）为分组处理消息）为分组处理消息:q将分组的将分组的16个字扩充为个字扩充为80个字用于压缩过程中个字用于压缩过程中q4轮，每轮轮，每轮20步迭代步迭代q把输出和输入相加以形成新的缓冲区取值把输出和输入相加以形成新的缓冲区取值5.将最后缓冲区的值作为将最后缓冲区的值作为hash值输出值输出2022-5-20西安电子科技大学计算机学院282022-5-20西安电子科技大学计算机学院29SHA-1 压缩函数压缩函数2022-5-20西安电子科技大学计算机学院30SHA-1 verses MD5n穷举攻击更加困难（穷举攻击更加困难（SHA-1:160, MD5:128） n对已知攻击不存在风险对已知攻击不存在风险 (与与 MD4/5相比相比)（SHA-1的设计原则尚未公开）的设计原则尚未公开） n速度比速度比MD5慢慢 (80 步，步，64 步步) n两者设计都很简单紧凑两者设计都很简单紧凑2022-5-20西安电子科技大学计算机学院31SHA的修改的修改nNIST1981年已经发布了年已经发布了FIPS 180-2n除除SHA-1外，新增加了外，新增加了3个个hash算法：算法： SHA-256, SHA-384, SHA-512，消息摘要的长度分别为：消息摘要的长度分别为：256，384，