搜索
Hash函数分析方法综述报告人：吴双信息安全国家重点实验室中科院软件所2010年12月21日主要内容Hash函数简介不依赖算法的通用方法针对结构的分析方法针对具体运算的分析方法展望Hash函数的定义Hash函数的概念来源于计算机学中的Hash表密码学中的Hash函数是将任意长度的消息压缩为固定长度摘要的函数，是密码学中重要的基本模块Thisisaninputtoacrypto-graphichashfunction.Theinputisaverylongstring,thatisreducedbythehashfunctiontoastringoffixedlength.Thereareadditionalsecurityconditions:itshouldbeveryhardtofindaninputhashingtoagivenvalue(apreimage)ortofindtwocollidinginputs(acollision).1A3FD4128A198FB3CA345932hHash函数简介Hash函数的定义Hash函数的安全要求抗原象抗第二原象抗碰撞Hash函数简介Hash函数的安全要求Hash函数的安全要求(n比特输出)?h(x)hxh(x)h?h(x’)h?h?==原象pre-image碰撞collision2n2n2n/2h(x’)h(x)h第二原象2ndpre-imageHash函数简介Hash函数的安全要求Hash函数的用途数字签名—破坏代数结构，抗碰撞，抗原象消息认证—伪随机性保护口令、确认保密信息—抗原象伪随机序列生成器(PRNG)、密钥生成函数(KDF)—伪随机性Hash函数简介Hash函数的用途对Hash函数的攻击寻找原象、第二原象可以进行伪造攻击（恢复密钥、伪造签名）寻找碰撞消息对可以进行欺诈攻击（代表不同意义的消息具有相同摘要）构造区分器伪随机性不够好会影响消息认证、密钥生成函数的安全性Hash函数简介对Hash函数的攻击主要内容Hash函数简介不依赖算法的通用方法针对结构的分析方法针对具体运算的分析方法展望穷举攻击这里指利用穷举的方法寻找某个函数的原象对给定y求m使得F(m)=y，若F()的值域为n比特二进制空间，复杂度为2n当n较小时，穷举是最直接有效的方法穷举攻击的优点：易并行处理（不可小视）当前，10万美元的硬件可以达到264的计算能力。成功案例：伪造X.509证书（MD5碰撞）适当的时候，可以将其他问题转化为原象问题不依赖算法的通用方法穷举攻击穷举攻击不依赖算法的通用方法穷举攻击M0M1Mi-1MiY0Y1Yj-1Yj生日攻击不依赖算法的通用方法生日攻击及其推广生日攻击Hash函数碰撞攻击的生日攻击界一般认为，对于n比特输出的理想Hash函数，碰撞攻击的复杂度上界为O(2n/2)对于随机选取的2n/2个消息，找到一对碰撞的概率较高，约0.39对于随机选取的2n+1/2个消息，找到一对碰撞的概率约0.63不依赖算法的通用方法生日攻击及其推广生日攻击生日攻击的时间空间复杂度随机选r=2n/2个消息，计算摘要并将摘要值作为索引存储（Hash表）。时间复杂度为r次Hash函数调用，r-1次查表，r个单元的存储空间因此时间和空间复杂度都是O(2n/2)空间复杂度O(1)的生日攻击利用Floyd链表找圈算法时间复杂度仍然是O(2n/2)不依赖算法的通用方法生日攻击及其推广H(x)xHcollision多碰撞攻击不依赖算法的通用方法生日攻击及其推广中间相遇技术问题：对于{0,1}n上的集合A、B，两者元素个数分别为r和s，问在这两个集合中找到一个公共元素的概率和复杂度是多少？将其中一个集合的元素建立Hash表，然后用另一个集合的元素去查表，找到公共元素的概率为rs/2n建表的时间和空间复杂度与集合大小相同，查表的时间复杂度与另一个集合大小相同于是中间相遇的时间复杂度为r+s，空间复杂度为min{r,s}不依赖算法的通用方法生日攻击及其推广中间相遇技术空间复杂度为O(1)的中间相遇攻击要求获取两个集合中一个元素的复杂度为O(1)，如果这条不满足，则这种方法不成立同样是利用Floyd链表找圈算法不同的是，迭代函数利用一个固定算法根据输入计算出一个指示比特的值用来决定将输入映射到A集合还是B集合找到一个圈的入口，如果它的两个父节点的指示比特不同，则攻击成功（50%概率）时间复杂度为O(r+s)不依赖算法的通用方法生日攻击及其推广一般化生日攻击不依赖算法的通用方法生日攻击及其推广主要内容Hash函数简介不依赖算法的通用方法针对结构的分析方法针对具体运算的分析方法展望对MD结构的通用攻击MD结构简介针对结构的分析方法对MD结构的通用攻击H0M1FM2FMiFMnFHnM1M2Mi…………消息填充对MD结构的通用攻击长度扩展攻击在已碰撞的消息对后面增加消息块来构造新的碰撞对多碰撞攻击MD结构的多碰撞代价远远低于构造随机函数的多碰撞长消息第二原象攻击通过可扩展消息构造对长消息的第二原象攻击集群攻击攻击者选择摘要h，给定前缀P，攻击者构造出后缀S使得H(P||S)=h(指定前缀第二原象)木马消息攻击攻击者给定后缀S，被攻击者选择前缀P并计算h=H(P||S)，攻击者得到h以后构造出P||S的第二原象针对结构的分析方法对MD结构的通用攻击主要内容Hash函数简介不依赖算法的通用方法针对结构的分析方法针对具体运算的分析方法展望差分分析介绍不考虑算法运算中的具体值，而是考虑两个不同值在运算的过程中，两者的异或差分的变化规律分析算法具体实现中使用的基本运算的差分特性来构造的攻击分析异或、模加、布尔函数、S盒等的差分传播特性针对具体运算的分析方法差分分析差分分析介绍差分路径的概念差分顺序传播的轨迹针对具体运算的分析方法差分分析压缩函数V0V1V2V3V4……Vn-1Vn压缩函数V’0V’1V’2V’3V’4……V’n-1V’nMM’=压缩函数……差分路径差分分析介绍压缩函数……差分路径针对具体运算的分析方法差分分析差分分析介绍针对具体运算的分析方法差分分析差分分析介绍如何理解独立性假设从数学上来讲，独立性假设是错误的密码学和数学区别：密码算法的攻击者关心的是什么？不是对概率和复杂度的精确计算，而是要进行实际的(practical)攻击精确计算概率太困难（密码算法都会破坏代数结构）对hash函数而言，目标是要找到碰撞对、原象因此在对概率和复杂度的计算上独立性假设是已知的最合理的假设，实验结果往往也和理论估计值接近只需要对目标算法的强度有一个大致的把握实际攻击是否能成功与概率计算的精确程度无关针对具体运算的分析方法差分分析比特级差分分析针对的对象：布尔函数、循环移位、模加、异或等。这些运算的差分特征的各比特之间具有一定的独立性对于布尔函数而言，它的差分特征各比特之间完全独立，因此分析一个比特的情况就足够了对于模加而言，由于进位的存在，比特差分之间有可能会互相影响针对具体运算的分析方法差分分析比特级差分分析针对具体运算的分析方法差分分析循环区分器针对具体运算的分析方法循环区分器字节级分析针对的对象：使用S盒、MDS扩散结构的字节级算法如AES等S盒具有差分均匀性，不存在高概率差分特征，可以抵抗传统的差分分析S盒使得差分特征比特之间的代数关系变得复杂，对代数攻击也有一定抵抗作用针对具体运算的分析方法差分分析字节级分析积分攻击考虑不同运算对各种集合的影响，而不考虑对单个值的影响截断差分将S盒的多个差分特征进行捆绑，作为截断差分特征，极大提高差分特征的概率反弹攻击利用S盒的差分特征预计算表，对截断差分路径进行拼接，并利用迭代状态和消息中的自由度找到满足连接段差分路径的解，再让截断差分路径从中间向两端传播针对具体运算的分析方法差分分析针对密钥扩展的攻击很多Hash函数可以看做是基于分组密码构造的，如MD4、MD5、SHA1等虽然它们并不是基于已经存在的分组密码构造的但是它们拥有与分组密码类似的结构具有类似密钥扩展的消息扩展针对具体运算的分析方法针对密钥扩展的攻击局部碰撞利用密钥扩展算法存在的周期特性轮数较少的局部碰撞路径可以利用密钥中差分出现的周期性进行传递对SHA0、SHA1的攻击中都使用了这种方法由于使用了5个迭代寄存器，SHA-0存在6轮局部碰撞路径利用周期性的消息扩展算法，局部碰撞需要的消息差分将重复出现，于是可以将若干局部碰撞组合得到整个算法的差分路径针对具体运算的分析方法针对密钥扩展的攻击连接-切割技术(spliceandcut)利用密钥扩展和迭代结构进行的原象攻击将迭代过程的首位相接，然后从特定部位断开，同时选择不同的消息字然后进行中间相遇成功地对多个基于分组密码的hash函数进行了理论上的原象攻击全轮MD5的原象攻击全轮Tiger的原象攻击针对具体运算的分析方法针对密钥扩展的攻击起点匹配点逆向处理密钥扩展的技巧首先假设各子密钥之间独立，求得它们的具体值以后再考虑它们之间是否满足扩展关系可以用来推导类AES结构的差分路径对MD5、SHA0、SHA1等的另一种原象攻击技术针对具体运算的分析方法针对密钥扩展的攻击主要内容Hash函数简介不依赖算法的通用方法针对结构的分析方法针对具体运算的分析方法展望展望SHA-3竞赛带动hash函数分析技术飞速革新反弹攻击、循环区分器、连接-切割技术等有效的分析手段都是这一时期提出未来的研究热点方向反弹攻击的改进和更广泛的应用布尔函数遭遗弃，ARX结构差分特性难以把握，需要更多更深入有效的研究分析各种新结构可能会带来的通用攻击方法谢谢