crypto4c-ch12-Hash和MAC算法剖析.ppt

News：Hash算法分析的新近进展 MD5CRK was a distributed project started in March 2004 with the aim of demonstrating that MD5 is practically insecure by finding a collision using a birthday attack. MD5CRK ended shortly after 17 August 2004, when collisions for the full MD5 were announced by Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu [1] [2]. Their analytical attack was reported to take only one hour on an IBM p690 cluster. On 1 March 2005, Arjen Lenstra, Xiaoyun Wang, and Benne de Weger demonstrated [3] construction of two X.509 certificates with different public keys and the same MD5 hash, a demonstrably practical collision. The construction included private keys for both public keys. One-way Function 单向性 已知x，很容易计算y=f(x) 已知y，很困难计算x=f-1(y) 所谓难：在期望的时间和代价内不能完成。 举例 打碎/拼接 平方/开方 乘法/分解 * 单向函数存在否 还没有严格的数学证明 Trapdoor One-way Function 单向陷门函数 如果知道某个陷门(秘诀)，即能容易恢复x 举例 魔方的置乱/恢复 如果有那个口诀，就能很快恢复 查Google找”魔方 口诀” 加密/解密 One-way Hash Function 单向散列函数(单向+散列) h = H(m) 有的散列函数并不满足单向(抗冲突)性质 密码学上用的散列函数都是指单向散列函数 抗冲突性质 给定h，找m满足H(m)=h很难 给定m，找m’满足H(m’)＝H(m)很难 找m1和m2满足H(m1)＝H(m2)很难 举例 MD5、SHA-1 HASH 消息摘要 Message digest 对于任意给定的报文，产生固定长度的摘要信息 特性 单向 抗碰撞(弱、强) 举例 代替CRC等 很多软件发行时文件的MD5校验 MAC Hash Algorithm Structure 12.0 MD5 近几年对散列算法的分析就是从MD5上获得突破的，MD5的强抗碰撞特性被打破。但是MD5是目前仍广泛使用的散列算法，而且看起来强抗碰撞特性的丢失对实用影响不大。 MD5算法是很多其他散列算法的前身，包括SHA-1。MD5算法将逐渐被代替，如SHA-1、WHIRLPOOL、RIPEMD-160、SHA-2。 新型散列算法的设计工作正在积极实施中。 MD系列 作者：Ronald Rivest /~rivest/ MD2、MD4、MD5 RFC1319/1320/1321 /rfc/rfc1321.txt 应用 曾经是最广泛的摘要算法 但是较短(128bits) 而SHA1有160bits MD5 Detail 输入 任意长 输出 128bits 过程 填充在Y[L] 报文填充1～512bits，使之≡448mod512 填充64bits长度值 填充后报文被划分成512bits分组 初始MD寄存器(IV)（小数在前little endian/intel） AB＝EFCDAB89 C＝98BADCFE D分组处理 … MD5 Overview MD5 1 Loop 输入 128b＋512b(128*4) 输出 128b 过程 FGHI布尔函数 T[]是常量表 X[k]为512b分组中的 第k个32b字 T[i] = 232×abs(sin(i)) MD5 1/4 Loop 四个函数真値表 b c d F G H I 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 1 1 1 1 0 RFC