hash函数分析技术- Hash函数分析方法综述

《hash函数分析技术- Hash函数分析方法综述》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Hash函数分析方法综述报告人：吴双信息安全国家重点实验室中科院软件所2010年12月21日主要内容Hash函数简介不依赖算法的通用方法针对结构的分析方法针对具体运算的分析方法展望Hash函数简介>Hash函数的定义Hash函数的定义Hash函数的概念来源于计算机学中的Hash表密码学中的Hash函数是将任意长度的消息压缩为固定长度摘要的函数，是密码学中重要的基本模块Thisisaninputtoacrypto-graphichashfunction.Theinputisaverylo

2、ngstring,thatisreducedbythehashfunctiontoastringoffixedlength.Thereareadditionalsecurityh1A3FD4128A198FB3CA345932conditions:itshouldbeveryhardtofindaninputhashingtoagivenvalue(apreimage)ortofindtwocollidinginputs(acollision).Hash函数简介>Hash函数的安全要求Hash函数的

3、安全要求抗原象抗第二原象抗碰撞Hash函数简介>Hash函数的安全要求Hash函数的安全要求(n比特输出)原象第二原象碰撞pre-image2ndpre-imagecollision?x???hhhhhh(x)h(x)=h(x’)h(x)=h(x’)2n2n2n/2Hash函数简介>Hash函数的用途Hash函数的用途数字签名—破坏代数结构，抗碰撞，抗原象消息认证—伪随机性保护口令、确认保密信息—抗原象伪随机序列生成器(PRNG)、密钥生成函数(KDF)—伪随机性Hash函数简介>

4、对Hash函数的攻击对Hash函数的攻击寻找原象、第二原象可以进行伪造攻击（恢复密钥、伪造签名）寻找碰撞消息对可以进行欺诈攻击（代表不同意义的消息具有相同摘要）构造区分器伪随机性不够好会影响消息认证、密钥生成函数的安全性主要内容Hash函数简介不依赖算法的通用方法针对结构的分析方法针对具体运算的分析方法展望不依赖算法的通用方法>穷举攻击穷举攻击这里指利用穷举的方法寻找某个函数的原象对给定y求m使得F(m)=y，若F()的值域为n比特二进制空间，复杂度为2n当n较小时，穷举

5、是最直接有效的方法穷举攻击的优点：易并行处理（不可小视）当前，10万美元的硬件可以达到264的计算能力。成功案例：伪造X.509证书（MD5碰撞）适当的时候，可以将其他问题转化为原象问题不依赖算法的通用方法>穷举攻击穷举攻击M0Y0M1Y1Mi-1Yj-1MiYj不依赖算法的通用方法>生日攻击及其推广生日攻击不依赖算法的通用方法>生日攻击及其推广生日攻击Hash函数碰撞攻击的生日攻击界一般认为，对于n比特输出的理想Hash函数，碰撞攻击的复杂度上界为O(2n/2)对于随机选取的2n/

6、2个消息，找到一对碰撞的概率较高，约0.39对于随机选取的2n+1/2个消息，找到一对碰撞的概率约0.63不依赖算法的通用方法>生日攻击及其推广生日攻击生日攻击的时间空间复杂度随机选r=2n/2个消息，计算摘要并将摘要值作为索引存储（Hash表）。时间复杂度为r次Hash函数调用，r-1次查表，r个单元的存储空间因此时间和空间复杂度都是O(2n/2)空间复杂度O(1)的生日攻击collision利用Floyd链表找圈算法时间复杂度仍然是O(2n/2)xHH(x)不依赖算法的通用方法>生

7、日攻击及其推广多碰撞攻击不依赖算法的通用方法>生日攻击及其推广中间相遇技术问题：对于{0,1}n上的集合A、B，两者元素个数分别为r和s，问在这两个集合中找到一个公共元素的概率和复杂度是多少？将其中一个集合的元素建立Hash表，然后用另一个集合的元素去查表，找到公共元素的概率为rs/2n建表的时间和空间复杂度与集合大小相同，查表的时间复杂度与另一个集合大小相同于是中间相遇的时间复杂度为r+s，空间复杂度为min{r,s}不依赖算法的通用方法>生日攻击及其推广中间相遇技术空间复杂度为O(1

8、)的中间相遇攻击要求获取两个集合中一个元素的复杂度为O(1)，如果这条不满足，则这种方法不成立同样是利用Floyd链表找圈算法不同的是，迭代函数利用一个固定算法根据输入计算出一个指示比特的值用来决定将输入映射到A集合还是B集合找到一个圈的入口，如果它的两个父节点的指示比特不同，则攻击成功（50%概率）时间复杂度为O(r+s)不依赖算法的通用方法>生日攻击及其推广一般化生日攻击主要内容Hash函数简介不依赖算法的通用方法针对结构的分析方法针对具体运算