分组密码算法的安全性分析.doc

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