论文部分内容阅读
虽然早在1949年Shannon就提出了现代分组密码算法设计所遵循的两大安全性准则——混淆(Confusion)与扩散(Diffusion),但是现代分组密码算法的研究却真正开始于20世纪70年代中期,以数据加密标准DES的颁布为标志。20世纪90年代差分分析、线性分析等分析方法的出现以及计算能力的突飞猛进,促使美国和欧洲分别开始了AES以及NESSIE工程。这些征集工作极大地推动了分组密码算法的设计与分析理论的发展。由于差分分析与线性分析的有效性,种种基于这两种分析方法的新的分析模型被逐渐引入到分组密码算法分析领域。差分分析关注密码算法中出现的差分值的高概率传播现象并围绕此特性构建模型进行密钥恢复攻击。作为差分分析的衍生方法,不可能差分从另一个角度关注算法结构:利用算法中不可能出现的差分(概率为0)来排除错误的密钥猜测(正确密钥下不可能出现的差分)。由于不可能差分在对诸多算法的分析中取得的显著成果,以及线性分析与差分分析的相似性(都是基于算法结构中出现的高概率事件进行密钥恢复),线性领域中类似于不可能差分这样强有力的分析工具的存在性成为值得考量的问题。2012年,Bogdanov与Rijmen提出的零相关线性分析的概念(Zero-Correlation Linear Cryptanalysis)开启了这个方向的研究。线性分析依赖于分组密码算法中存在的具有高概率偏差的线性逼近(或者线性壳),而零相关线性分析则从另一个角度入手,依赖于分组密码算法中存在的相关度为零(偏差为零)的线性逼近。Bogdanov和Rijmen展示了如何利用算法中存在零相关线性逼近进行密钥恢复攻击。然而对于高数据复杂度的需求极大的限制了零相关线性分析的应用。借鉴多重线性分析的思想,FSE 2012上Bogdanov和Wang利用大量零相关线性逼近,提出用区分统计分布的形式进行密钥恢复的新模型——多重零相关线性分析。新模型能够利用l条零相关线性逼近,将攻击所需的数据复杂度降为(?)(2n/(?))(n为目标算法的分组长度)。新模型的数学建模过程中,依赖的强假设条件通常并不能满足,零相关线性分析模型仍待完善。同年的ASIACRYPT上,Bogdanov等人提出多维零相关线性分析新模型在维持基本相同的数据复杂度的情况下,消除了对强假设条件的依赖,这一模型的提出标志着零相关线性分析模型的成熟。快速傅里叶变换(FFT)技术最初是由Collard等人在ICISC 2007上引入到分组密码分析领域。Collard等人指出在特定条件下部分算法的线性分析的时间复杂度可以通过FFT技术进行改进。由于基于线性分析与基于多重零相关线性分析的密钥恢复攻击过程之间的相似性,FFT技术同样可以用来改进多重零相关线性分析的时间复杂度。FFT技术已经被整合到线性分析、多重零相关线性分析以及及积分攻击的攻击过程中。虽然FFT技术获得了广泛应用,但是FFT的现有理论要求密钥恢复攻击过程中的部分加解密阶段仅有子密钥异或操作和至多一个子密钥模加操作。这一要求限制了FFT技术在ARX算法分析领域的应用。扩展的FFT技术以及对29轮CAST-256算法的多重零相关线性分析本文中通过对FFT技术的理论基础——循环矩阵(Circulant Matrix)理论的考察,发现即使在部分加解密阶段存在多个子密钥模加的情形,FFT技术仍然可以用来改进这一阶段的时间复杂度。这一发现拓展了FFT技术在密码分析领域的应用。在此基础之上,我们重新考察了CAST-256在零相关线性分析模型下的安全性。通过将FFT技术整合到多重零相关线性分析技术,本文中给出了29轮CAST-256的多重零相关线性分析结果,这一结果在是无弱密钥假设条件下CAST-256的最好分析结果。HIGHT的多维零相关线性分析HIGHT是韩国信息安全局参与设计的轻量级分组密码算法并发表在CHES 2006并且随后被采纳为ISO标准算法之一。HIGHT是采用8分支的Type-Ⅱ广义Feistel结构的32轮分组密码算法,并且在第一轮之前以及最后一轮之后都有白化密钥层。通过跟踪线性掩码在HIGHT算法内的传播,本文构造了16轮HIGHT上的零相关线性逼近。在16轮零相关线性逼近的基础之上,通过优化的密钥猜测顺序以及逐比特的部分和(Partial Sum)技术,我们首次给出了26轮HIGHT(包含全部白化密钥,第4轮到第29轮)的密钥恢复攻击。另外,本文给出了27轮HIGHT(包含全部白化密钥,第4轮到第30轮)的密钥恢复攻击。相比于已经公开发表的对HIGHT的最好分析结果(不考虑Biclique等攻击方法)——Chen等人在AFRICACRYPT 2012上利用不可能差分分析技术对27轮HIGHT(包含全部白化密钥,第4轮到第30轮)的密钥恢复攻击,本文中给出的对27轮HIGHT的攻击结果在存储复杂度方面有着显著的改进。E2的多维零相关线性分析E2是由日本NTT公司设计的128比特分组长度的分组密码算法,是AES征集过程中首轮的15个候选算法之一,而其设计理念被应用到ISO标准算法Camellia算法的设计之中,因此E2的安全性得到了密码分析学者的关注。E2的主密钥可以为128、192、256比特,分别用E2-128,E2-192,E2-256来指代这三个版本的E2算法,其轮数都为12轮。在E2的安全性分析方面,本文构建了6轮E2算法上的零相关线性逼近。在此基础之上,本文给出了不考虑初始变换IT和最终变换FT的8轮的E2-128以及9轮的E2-256算法的密钥恢复攻击。与已有的针对E2的不可能差分分析结果相比,本文的分析结果能够多攻击一轮。而与之前的截断差分分析结果相比,本文中对8轮E2-128的攻击在时间复杂度方面更具优势。另外,本文中也给出了考虑初始变换IT和最终变换FT时对6轮E2-128以及7轮E2-256算法密钥恢复攻击,这也是针对E2的首个考虑初始变换IT和最终变换FT的攻击结果。由于零相关线性分析的有效性,零相关线性区分器与其它区分器之间的内在联系受到关注。Bogdanov等人在ASIACRYPT 2012上指出在一定条件下零相关线性区分器等价于积分区分器并据此提出积分零相关攻击的概念。与FFT技术的应用相似,ARX算法上的零相关线性逼近通常不符合ASIACRYPT 2012中的模式,无法从相应结果中获益。ARX算法中零相关线性区分器与积分区分器之间的联系以及改进的SHACAL-2分析结果本文中详细考察了ARX算法的通用零相关线性逼近的模式以及其与积分区分器之间的联系并指出在该模式下零相关线性区分器仍然可以转化为积分区分器。据此,本文中构造的12轮SHACAL-2算法上零相关线性逼近被转化成为积分区分器。在该积分区分器的基础之上,本文对30轮和32轮的SHACAL-2算法进行了密钥恢复攻击。相关密钥条件下对23轮LBlock算法的不可能差分分析本文最后一部分的工作关注LBlock算法在相关密钥条件下安全性分析,采用的具体的分析模型是经典的相关密钥不可能差分分析。LBlock算法Wu和Zhang在ACNS2011上发表的轻量级分组密码算法。该算法采用64比特的分组长度以及80比特的主密钥,并且是基于改造过的Feistel结构设计而成,总轮数共32轮。更长的相关密钥不可能差分路径通常意味着攻击者能够攻击更多的轮数。为了构造更长的轮数的相关密钥不可能差分路径(之前最好相关密钥不可能差分路径能够覆盖15轮LBlock算法),本文中设计了一个相关密钥不可能差分路径搜索算法。通过将全部的密钥空间划分为互不相交的子集,本文中成功构建了16轮LBlock上的相关密钥不可能差分路径,并在此基础上,给出了23轮LBlock的相关密钥不可能差分分析结果。