论文部分内容阅读
杂凑函数是密码学领域的研究热点之一,主要应用于消息完整性认证、数字签名、电子货币等。一个杂凑函数主要包括迭代结构和压缩函数两部分。本文针对这两部分的安全性分析,主要做出了以下工作:(1)构造了具有2k(0<k<n/4-1.3)个起始点的变长“钻石树”结构的多碰撞,并据此提出了对强化MD结构杂凑函数的一个新的选择目标强制前缀且原像长度为2k+3块的原像攻击(即“牧群”攻击)。由于变长“钻石树”结构的多碰撞使得攻击过程中可利用的中间链接值的数量增大,故新的牧群攻击的计算复杂性降至O(2n-k/3+2n/2+k+1),且小于理想值O(2n);(2)利用Kelsey和Schneier提出的构造MD结构杂凑函数的可扩展消息的方法,提出了对带置换的MD结构杂凑函数的第二原像攻击,该方法可以找到块数t34的目标消息的第二原像,其计算复杂性约为k′2n/2+1+2n-k+2k,低于第二原像攻击的理想计算复杂性2n,这里的n表示杂凑值的比特数且k=min{floor(n/2-1.68),max{i:2i+i<t}};利用第二章中的变长的“钻石树”结构的多碰撞,提出了对带置换的MD结构杂凑函数的原像攻击,其计算复杂性为O(2n-k/3+2n/2+k+1)(0<k<n/2-1),低于理想值O(2n);(3)通过构造随机双长度压缩函数的模拟器,证明了对于任意区分器,如果访问的次数远低于O(2n),则杂凑值长度为2n-比特的双长度结构杂凑函数与随机函数是无差别的。此外,由于Lucks提出的杂凑值长度为n-比特的双管结构杂凑函数是双长度结构杂凑函数的一个特例,区别仅在于输出函数为截断函数,故我们对双长度压缩函数的模拟器做出了相应的改进,并证明了如果区分器D的访问次数低于O(2n/2),则基于随机压缩函数的双管杂凑函数H与随机OracleR是无差别的;(4)提出了对9-轮ECHO-512压缩函数的反弹攻击。首先在假定面向字节的差分为四种类型的前提下,给出了通过ECHO-512压缩函数轮变换的非线性层的所有截断差分路径以及它们的概率。然后依据给出的构造原则得到了两条新的4-轮截断差分路径,合并两条新的截断差分路径并将后者扩展一轮,我们得到了一条新的9-轮ECHO-512压缩函数截断差分路径,并利用融多种技术为一体的方法找到了满足整条差分路径的解,从而提出了对9-轮ECHO-512压缩函数的反弹攻击,其时间复杂性为O(2164),存储复杂性为O(296)。最后利用该结果构造了9-轮ECHO-512压缩函数的区分器,将其与理想压缩函数区分开来;此外,由于消息认证码(MAC)是带密钥的杂凑函数,故本文也对基于杂凑函数的消息认证码的安全性进行了研究,做出了下面的工作:(5)以产生扩展dBB碰撞的概率为区分器,提出了对基于MD5的封装MAC的自适应选择消息区分攻击,其数据复杂性为296、时间复杂性为296次封装MAC访问,表规模为289且成功率为0.87。然后我们将自适应选择消息区分攻击扩展为选择消息区分攻击,其数据复杂性增加为2113,表规模降低为266且成功率仍为0.87。