论文部分内容阅读
在分组密码分析中,yoyo攻击是一类既可以用于密码结构分析,又可以用于密钥恢复的攻击方法,该方法最为突出的特点是具有低数据和计算复杂度,因此近年来吸引了大量学者研究兴趣。至今,yoyo攻击已成为评估密码算法安全性的重要工具之一。本文对yoyo攻击方法展开研究,将该方法用于密码结构分析及具体算法密钥恢复,取得下列研究成果:给出适用于第二类广义Feistel结构(Type-II结构)的yoyo攻击:本文对保密内部函数的7轮Type-II结构进行了恢复,通过分析不动点的出现概率和yoyo圈中存在个数,给出了Type-II结构的yoyo圈长刻画,证明了每个正确起点的yoyo圈平均提供的有效方程量为2n个,难以构成满秩方程组,因此使用单个yoyo迭代圈往往只能提供恢复内部函数查找表的部分值;本文进而提出短圈判定技术,给出判定部分恢复的查找表的正确性条件,提出利用多个yoyo圈在正确查找表上共同恢复内部函数的方法。实验表明,当内部函数为7比特时,原yoyo在恢复Type-II内部函数所用的时间是本文攻击方法的9倍,从已有实验结果来看,随着内部函数规模增大,本文攻击方法效率提升将更加明显。利用yoyo攻击给出减轮3D算法和减轮Saturnin算法的最佳现实可行复杂度的密钥恢复攻击:本文提出的方法首次在现实可行的复杂度条件下攻破了7轮3D算法和5轮Satunin算法。对7轮3D算法,本文首先利用超级S盒和巨型S盒建立了6轮yoyo区分器,该区分器只需要1个选择明密文对和1次加解密。在此区分器基础上,本文结合中间相遇方法提出了7轮3D算法密钥恢复攻击,该攻击需要21 6选择明密文对,92存储空间和O(218.5)次加解密计算。对5轮Saturnin算法,本文用类似的方式找到了4超级轮区分器并在此基础上完成5超级轮密钥恢复攻击,该攻击恢复完整256比特密钥的数据复杂度为231选择明密文对,时间复杂度为O(239)超级轮加密计算。提出密钥集缩减技术:在Saturnin算法的设计报告中,对比算法描述,我们发现其程序实现部分(文献[42]中算法1)遗漏了奇数轮指标的S层,这使得该算法一个超级轮中仅含单个S层,我们称之为单S层版本。针对这种单S层版本Saturnin算法,本文提出密钥集缩减技术以降低yoyo攻击复杂度。该技术主要思想是通过选择零差分元胞数较多的返回明文对降低密钥穷举量,使用多数据过滤,进而逐步缩减候选密钥集。使用该技术完成5超级轮密钥恢复攻击大约需要239.1选择明密文对和O(246)超级轮加密。结合中间相遇技术后,可以将数据复杂度降为228.17选择明密文对,时间复杂度与Saturnin原版攻击一致,由此佐证了设计一个超级轮包含两个S层的必要性。值得注意的是,密钥集缩减技术不使用关于超级S盒的性质,也不受限于yoyo攻击,在分析扩散性较强的算法时可以有效降低计算代价。