密码编码学与网络安全（第五版） 向金海 08-密码学hash函数.ppt

Chapter 11 密码学Hash函数 信息保障与安全信息保障与安全 哈希函数（杂凑函数） （1） Hash编码编码 ； （2） Hash函数； （3）散列编码编码 ： （4）散列函数； （5）单单向压缩压缩 函数。 哈希函数 在公钥密码的内容中，已经介绍了“单向函 数”的概念。而哈希函数是一类特殊的单向函 数。 设数据文件是任意长度的比特串x 。在密 码应用中，希望有这样的函数 y=H(x)，满足 ： （1）将x压缩成为固定长度的比特串y。 （2）不同的x一定要生成不同的y。 （3）由y的值无法倒算x的值。 哈希函数 实际性质：哈希函数 函数 y=H(x)满足 （1）将任意长度的比特串x压缩成为固定长度的比特串y。 （2）已知x，计算y=H(x)很容易；已知y，找一个x满足y=H(x)却 很困难。这一性质称为单向性。 （3）找(x1，x2)，x1x2，H(x1)= H(x2)，很困难。这一性质称为 无碰撞性。 这样的函数称为哈希函数。 * 华中农业大学信息学院 5 Hash函数 n浓缩任意长的消息M到一个固定 长度的取值 h = H(M) n通常假设hash函数是公开的且不 使用密钥（MAC使用密钥） nHash函数用户检测对消息的改变 n多种方式工作方式 n常用于产生数字签名 * 华中农业大学信息学院 6 Hash算法 nHash函数和分组密码的发展变化具有相 似性 q穷举攻击能力的增强 q算法的不断改进 q分组密码：从DES 到 AES qHash算法: 从MD4 、MD5 到 SHA-1、 RIPEMD-160、SHA-512、Whirlpool * 华中农业大学信息学院 7 哈希函数的应用 n消息认证 n 数字签名 n 口令保护、文件完整性等 Hash函数用于消息认证 * 华中农业大学信息学院 8 Hash函数用于消息认证 * 华中农业大学信息学院 9 Hash函数用于数字签名 * 华中农业大学信息学院 10 * 华中农业大学信息学院 11 12.1 MD512.1 MD5消息摘要算法消息摘要算法 n由Ronald Rivest设计 nMD2(1989), MD4(1990), MD5(1991) n产生128-bit的hash值 n直到现在仍是被广泛使用的hash算法 q最近已受到穷举攻击和密码分析攻击 n作为互联网的RFC1321标准 * 华中农业大学信息学院 12 MD5 概览 1.增加填充位。使得填充后的消息长度比512的某整数倍 少64位（即长度 448 mod 512，64位用于存放消息的 长度mod 264的结果） 2.填充长度（填充前消息的长度为K位，将mod264 的结 果填充到第一步的最后，最低有效位在前。） 3.初始化MD缓冲区(A, B, C, D) : 4个字共128-bit，每字 32bit. A = 67452301 B = EFCDAB89 C = 98BADCFE D = 10325476 1.以16个字（512bits）为分组处理消息 q用4轮（64次迭代）以16位操作对消息分组和缓冲区进行 处理 q把输出与缓冲输入相加作为新的缓冲值 2.把最后的缓冲值作为hash输出值（128比特） * 华中农业大学信息学院 13 MD5 处理过程 n CV0 = IV n CVq+1 = SUM32 CVq, RFI(Yq, RFH(Yq, RFG(Yq, RFF(Yq, CVq) n MD = CVL-1 其中： IV = 第三步定义的缓冲区ABCD的初值 Yq = 消息的第q个512位分组 L = 消息分组的个数（包括填充位和长度域） CVq = 处理消息的第q个分组时所使用的链接变量 RFx = 使用基本逻辑函数x的轮函数 MD = 消息摘要 SUM32 = 对输入字分别执行模232加法 * 华中农业大学信息学院 14 MD5 Overview * 华中农业大学信息学院 15 * 华中农业大学信息学院 16 MD5 压缩函数 n每一轮都由16步迭代构成: a = b + ( ( a + g( b, c, d ) + X k + T i ) s ) na, b, c, d 表示缓冲区的4个32位字,按照一定次序随迭代步骤而 变化 q每次迭代只更新缓冲区中的一个字a q16次迭代后，每个字被更新4次 n其中g ( b, c, d )表示每一轮的非线性函数，四轮依次为( F, G, H, I ) n s：32位的变量循环左移s位 nXk = Mq x 16 + k = 消息第q个512位分组的第k个32位字 nT i 是由 sin 导出的 32 bit 的常量 n+ ：模232加法 * 华中农业大学信息学院 17 MD5 压缩函数 * 华中农业大学信息学院 18 * 华中农业大学信息学院 19 * 华中农业大学信息学院 20 * 华中农业大学信息学院 21 * 华中农业大学信息学院 22 * 华中农业大学信息学院 23 * 华中农业大学信息学院 24 MD5的强度 nMD5的hash值依赖于消息的所有比特位 nRivest声称它对于已知攻击安全性足够好: qBerson 92 采用差分的方法对单轮的攻击 qBoer & Bosselaers 93 说明了如何找到碰撞 qDobbertin 96 提出的攻击对MD5最具威胁，可使MD5 压缩函数产生碰撞。 n结论是MD5似乎不久就会有风险 * 华中农业大学信息学院 25 * 华中农业大学信息学院 26 12.2 安全Hash算法(SHA-1) nSHA 由NIST 和NSA在1993年提出, 修订版于 1995年发布，称作SHA-1 n作为美国DSA数字签名方案的标准 qFIPS 180-1 1995, Internet RFC3174 q注意：算法是SHA, 标准称为SHS n产生160-bit hash值 n现在作为建议的hash算法 n基于MD4的设计 * 华中农业大学信息学院 27 SHA 概览 1.增加填充位 2.填充长度 3.初始化5个字(160-bit) 缓冲区(A, B, C, D, E) 为 (67452301, efcdab89, 98badcfe, 10325476, c3d2e1f0) 4.以16个字（512-bit ）为分组处理消息: q将分组的16个字扩充为80个字用于压缩过程中 q4轮，每轮20步迭代 q把输出和输入相加以形成新的缓冲区取值 5.将最后缓冲区的值作为hash值输出 * 华中农业大学信息学院 28 * 华中农业大学信息学院 29 SHA-1 压缩函数 n每轮20步迭代: (A, B, C, D, E) - (E + f(t, B ,C, D) + (A5)+Wt+Kt), A, (B30), C, D) na, b, c, d, e指缓冲区的5个字 nt 是迭代步数，0t79 nf(t, B, C, D) 为第t步所用的非线性函数 nWt 从当前消息分组中导出的32位的字 nKt 加法常量 * 华中农业大学信息学院 30 SHA-1 压缩函数 * 华中农业大学信息学院 31 * 华中农业大学信息学院 32 * 华中农业大学信息学院 33 SHA-1 verses MD5 n穷举攻击更加困难（SHA-1:160, MD5:128） n对已知攻击不存在风险 (与 MD4/5相比)（SHA-1 的设计原则尚未公开） n速度比MD5慢 (80 步，64 步) n两者设计都很简单紧凑 n低位结构和高位结构 qMD5:低位结构 SHA-1:高位结构 * 华中农业大学信息学院 34 SHA的修改 nNIST1981年已经发布了FIPS 180-2 n除SHA-1外，新增加了3个hash算法： SHA-256, SHA-384, SHA-512， 消息摘要的长度分别为：256，384，512 n