yoyo攻击在两种常见分组密码结构中的应用.pdfVIP

摘要

Yoyo攻击是一种基于截断差分的分组密码分析技术,近几年以低数据和低计算复杂度

的特点被越来越多的密码分析工作者们所熟知.在具体的密码分析中,攻击者可以根据每

一个目标结构的特点为其提供最适合的yoyo攻击模型.本文利用yoyo攻击对Lai-Massey结

构和收缩Feistel结构的安全性进行了分析,主要研究成果如下:

针对Lai-Massey结构的yoyo攻击:在内部变换是仿射正形变换的情况下,本研究为3轮

Lai-Massey结构提供了一个改进的yoyo区分器,并在此基础上首次给出3轮Lai-Massey结构

和4轮Lai-Massey结构的秘密轮函数恢复攻击.在攻击3轮Lai-Massey结构的第一轮的过程

中,我们发现正确对具有的性质以及明文方程的特点大大限制了yoyogame产出有效正确

对的效率,且以一个正确对为起点的yoyogame能够提供的有效方程个数最多为−1,无法

为第一轮轮函数提供满秩方程组.为了解决这一问题,一个自然的想法是在攻击过程中使

用多次yoyogame.考虑到降低攻击的复杂度,我们深入剖析正确对在yoyogame中的演变,

通过将密文空间和明文空间先后划分为个子集为我们的yoyo攻击提供新的视角.在这一

新视角下,我们的攻击得到了两方面的改进.一方面,我们在yoyogame的开端处设置自定

义密文池,与随机选择相比,密文池的建立大大降低了寻找正确对的数据量和计算量.此

外,yoyogame的内部过滤器可以借助简单的异或计算筛选掉所有错误对,即省去了求解错

误方程所需的计算量.另一方面,我们为降低yoyogame的使用次数提供了行之有效的选

择方案,很大程度地减少了复杂度的消耗.在剥去第一轮后,3轮Lai-Massey结构的剩余两

轮轮函数的查找表可以通过控制剩余结构的输入并访问输出的方式恢复.基于上述研究,

4轮Lai-Massey结构上的恢复攻击方案是首先构造用于剥去第四轮的新的yoyo攻击,然后借

助3轮Lai-Masey结构上的恢复攻击方案分解其余三轮.总的来说,完全恢复4轮Lai-Masey结

22

构需要的计算复杂度和的存储复杂度,其中≤.

11

针对收缩Feistel结构的yoyo攻击:首先,通过选定一个具有特定差分的正确对为起点

构造yoyogame,本攻击直接省去了筛选错误对所需的复杂度并在此基础上恢复了7轮收

缩Feistel结构的第一、二、六、七轮秘密轮函数.其次,将首尾四轮已恢复的秘密轮函数剥

去,使用控制剩余结构的输入并访问输出的方式恢复剩余三轮的秘密轮函数.整个攻击需

要+2的存储和+3的计算复杂度.

I

关键词:分组密码,Yoyo攻击,Lai-Massey结构,收缩Feistel结构,结构攻击

II

ABSTRACT

Yoyoattackisanattackonblockciphersbasedontruncateddifferential.Inrecentyears,

ithasbeenknownbymoreandmorecryptanalysisresearchersbecauseofitslowdataandlow

computationalcomplexity.Intheconcretecryptanalysis,theattackercanprovidethemostsuit-

ableyoyogamemodel