对缩短步数的HASH函数算法SHA-256、SHA-512的分析

论文摘要

Hash函数在现代密码学中起着重要的作用,又被称为杂凑函数、哈希函数或单向散列函数.它是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数.Hash函数可用于保证数据完整性和实体认证,同时也是多种密码体制和协议的安全保证.Hash函数最重要的用途之一是用在数字签名中,它是保证数字签名方案安全而有效的充分必要条件.将Hash函数应用到数字签名中可带来诸多好处:（1）可破坏数字签名方案的某种数学结构,诸如同态结构;（2）可提高数字签名速度;（3）无需泄露数字签名所对应的消息,可将签名泄露;（4）可将签名变换和加密变换分开来,允许用私钥密码体制保密,而用公钥密码体制实现签名,等等.从理论上来讲,安全的Hash函数的存在性依赖于单向函数的存在性.安全的Hash函数需要满足下面三个安全属性:（1）抗原根攻击:对任一预先给定的输出y,寻找一个消息x使得h（x）=y在计算上是不可行的.（2）抗第二原根攻击:对任一输入x,寻找另一个不同于x的消息x′,使得h（x）=h（x′）在计算上是不可行的.（3）抗碰撞攻击:找两个不同的消息x和x′,使得它们具有相同的杂凑值,即h（x）=h（x′）,在计算上是不可行的.目前标准的Hash函数分为两大类:MDx系列（MD4[24],MD5[25].HAVAL[37],RIPEMD[26],RIPEMD-128[10],RIPEMD-160[10]等）和SHA系列（SHA-0[16],SHA-1[17],SHA-256[18],SHA-384[18],SHA-512[18]等）.它们都与MD4有相似的结构和相同的设计理念.差分分析是由E.Biham和A.Shamir[2]于1990年提出的,它是针对对称密码体制（分组密码、流密码、Hash函数和MAC算法）的选择明文攻击最有效的方法之一.它的基本思想是通过分析特定明文差对结果密文差的影响来获得可能性最大的密钥.王小云等基于差分分析的思想,采用不同于传统异或差分的模差分分析方法,对一系列标准Hash函数算法MD4、MD5、RIPEMD、HAVAL、SHA-0、SHA-1[30,31,34,36]进行了分析.2006年,Florian Mendel等[21]对18步的SHA-256进行了分析,给出了一条差分路线,但没有给出满足此差分路线的条件,也没有给出正确的碰撞实例.2008年,Ivica Nikolié等[22]对SHA-256进行了很好的分析,给出了19步的近似碰撞,20、21步的碰撞,以及初始值自由的23步的碰撞等.根据王小云等提出的“比特追踪法”[28,29,30,31,34,36],本文对18步的SHA-256算法和SHA-512算法进行了分析.本文找出了文献[21]所给差分路线需要满足的条件.针对SHA-256函数中加和异或混杂的特点,本文采用了二进制表格的方式逐比特求出明文需要满足的条件.本文对所找的条件进行了程序实现,并给出了一个18步SHA-256的实际碰撞,寻找碰撞的时间复杂度为O(214).另外,本文首次对18步的SHA-512进行了攻击,找出了18步SHA-512的差分路线和差分路线所需要满足的条件.本文首先找出了移位寄存器需要满足的条件,然后又用二进制表格的方式找出了明文需要满足的条件.另外,本文对理论上分析的结果进行了程序实现,给出了一个实际碰撞,寻找碰撞的时间复杂度为O(214).

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
• 第二章 SHA-256、SHA-512算法描述
• 2.1 符号描述
• 2.2 SHA-256算法
• 2.3 SHA-512算法
• 第三章 HASH函数的攻击方法
• 3.1 生日攻击
• 3.2 中间相遇攻击
• 3.3 差分分析方法
• 3.4 比特追踪法
• 3.5 新模差分方法
• 第四章 18步SHA-256的分析
• 4.1 已有对SHA-256的分析
• 4.2 满足差分路线的条件
• 4.3 时间复杂度分析
• 4.4 18步SHA-256碰撞实例
• 第五章 18步SHA-512的分析
• 5.1 18步SHA-512差分路线
• 5.2 满足差分路线的条件
• 5.3 时间复杂度分析
• 5.4 18步SHA-512碰撞实例
• 参考文献
• 致谢
• 学位论文评阅及答辩情况表