对6轮Rijndael-128算法的拉格朗日插值攻击外文翻译资料

英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料

对6轮Rijndael-128算法的拉格朗日插值攻击

Jingmei Liu Shaopeng Chen Linsen Zhao

摘要——通过在第一轮选择4个字节的2³²对明文，生成2²⁴个Lambda;¹集，每个Lambda;¹集会让所有的输入字节在第五轮达到平衡，所以所有的2³²对输入明文将在第五轮前达到平衡。如果我们结合部分和技术，拉格朗日插值攻击可以完成。研究结果表明，攻击复杂度可以减少到2⁵⁰，比现有的最好结果2⁷²更好。

关键词：AES；Rijndael；拉格朗日插值攻击；平方攻击

I.引言

密码和密码分析不仅仅是对立的，而且相互依赖，这种矛盾促进了密码学的发展。Rijndael[1-2]是五大AES候选算法之一，根据密钥大小，有10、12、14轮。作为高级加密标准，Rijndael算法的安全性被世界各地的许多研究者分析。但是直到现在，还没有对完整版的Rijndael算法的成功的攻击。对于简化版的Rijndael算法攻击，它的设计者提出的平方[3-4]攻击是一种最有效的选择明文攻击，它能攻击四轮简化Rijndael算法，明文数量是2⁹。

插值攻击[5]是Kakobsen等人提出的一种分组密码攻击，它对分组密码的S盒对应简单代数函数很有效。它也适用于输出能被输出表示，这个输出对应的简单代数函数多项式次数不高或者元素不多。目前，插值攻击在对有简单代数结构的密码更有效。在文献[5]中，Nyberg和Knudsen提出了用插值攻击攻击了6轮分组密码，但是此密码对于普通差分分析被证明是安全的。此外，根据插值攻击，文献[6]证明了Kiefer提出的SHARK密码和分组密码是不安全的，文献[7]成功地用插值攻击攻击了SHARK分组密码。文献[8]分析了在有限域内不可约多项式次数的影响和输入输出对应的多项式之间的线性函数的影响，输入输出决定了多项式的次数和系数大小。目前，对AES的拉格朗日插值攻击的研究取得了一定成果。文献[9]利用拉格朗日插值攻击攻击了4-6轮的简单AES，但是攻击复杂度很高。

本文结合拉格朗日插值攻击和部分和技术，攻击了6轮AES-128算法。研究结果表明攻击复杂度减少到2⁵⁰，相比现有的最好结果提高了很多。

本文安排如下：第二节，我们描述AES的结构；第三节，我们介绍插值攻击；第四节，呈现AES的轮结构和等价变换；在第五节，我们结合插值攻击和部分和技术攻击了6轮AES-128。

II.AES结构的介绍

提及AES一般要对这个密码进行完整描述，但是我们这里只列出S盒这一重要步骤。S盒是AES中唯一的非线性部分，但是它实现了最重要的功能：混淆。混淆是香农信息理论的重要组成部分。所以我们可以认为它很大程度上决定了整个分组密码的安全。AES的S盒的结构如下：

AES用16字节密钥加密16字节明文，轮数为10。数组中每个字节的值是根据查找表来替换的。这个查找表S盒是三个变换的结合：（a）输入字节x：x=x^-1，其中x^-1由x²⁵⁴(xne;0)定义。这里我们应当注意这个“AES逆“等价于非零域元素在有限域中的标准域的逆，规定 0^-1=0。（b)中间值x可以看作8维的GF（2）向量，并用一个8times;8的GF(2)矩阵L_A进行变换。变换向量L_A·x以这种自然的方式被当作有限域中的一个元素。这里变换想象L_A可以从多项式模乘法运算推导出来：

其中 表示关于x的多项式表达式，x可以看作是8维的GF(2)向量。

（c）最后，AES的S盒输出结果为，其中加法是关于GF(2)的加法运算。

常数是用来消除不动点和相反的不动点的。它的设计者在有限域GF(2⁸)选取的字节逆运算是用来抵抗所有可能的线性和差分不变性。线性和差分不变性是差分和线性密码分析的基本内容。然而，通过使用有已知特性的简单代数运算，他们之间的结合或许有许多有趣而且在设计初期意想不到的代数特性。尽管直到现在没有弱点被找到，这个简单的代数表达式还是AES中最让人感兴趣和最不利的特性之一。

III.拉格朗日插值攻击的原理

插值攻击的原理是应用拉格朗日插值公式求取加密算法的明密文代数表达式。在有限域F中，给定2n和元素，其中互不相同。定义多项式

作为唯一的拉格朗日插值公式，它的次数小于等于n-1并且满足。

对有限域GF(2⁸)，加法和减法在字节上与位异或一致，乘法被定义为一个二元多项式乘法模一个次数为8的二元不可约多项式。Rijndael算法的不可约多项式是

AES算法的S盒的输入和输出之间的关系可以用以下代数表达式表示：

公式中的系数是十六进制数。现在我们给出一个改进拉格朗日插值攻击的重要定理。

定理：设，是上的一个满射，当 ，对 ，以下等式一定成立：.

证明：我们知道可以表达如下：

在这个等式中，分子分母都有个互不相同的项，且都不包含项。此外，分子分母的个不同的项中不包含0项，所以分母的个不同的项与分子的254个不同的项相等。于是对，我们有恒等于1。

IV.Rijndael算法的等价轮变换

首先我们给出活跃字节Lambda;集的定义，这里我们只考虑在GF(2⁸)中的元素。

定义：Lambda;集是一个包含2⁸个状态的群，这些状态只在两个字节上不同，其余字节均相等。对任意状态，满足以下性质：

第一个不等式成立的条件是位置(i,j)上的字节是活跃字节，第二个等式成立的条件是位置(i,j)上的字节不是活跃字节。

有k个活跃字节的Lambda;群称为群。

在6轮拉格朗日插值攻击中，我们需要调整Rijndael算法的轮变换中基本变换的顺序，在没有影响加密效果的前提下，在算法的轮变换中四个基本变换的顺序可以任意调整。在6轮拉格朗日插值攻击中，需要把轮密钥加放在行置换和列混合之前，如图1，图中灰色网格表示活跃字节。加之前的轮密钥为。这两个轮变换是等价的，字节替换结果记作X，， 。

在6轮拉格朗日插值攻击中，我们认为加密过程是根据其等价过程执行的，所以便于在两轮中运算数据。

V.关于6轮AES算法的改进拉格朗日插值攻击

这部分，将给出两种改进的6轮AES算法的拉格朗日插值攻击。第一种改进算法将在下面给出，称为改进方法1。

假设第6轮的四个密钥字节猜测是k₀、k₁、k₂、k₃，第5轮密钥字节猜测为k₄，对应的四个明文字节是c₀、c₁、c₂、c₃。最后两轮的解密过程是 ，，必须要注意的是第五轮变换应当有它的等价形式来实现，k₄是变换密钥，即 ，其中K是第五轮的猜测轮密钥。因为只有一个字节的情形在拉格朗日插值攻击中会被研究，因此可以部分计算出。例如，第一个字节的解密过程可以写成，进一步缩写为，所以，猜测密钥字节的过程也表示2²⁴级输入输出的拉格朗日插值攻击情况，每一组输入和输出的组合数是2⁸。密钥字节有2⁴⁰个可能值，因此我们进行不超过2⁷²次的解密运算，我们就可以计算出正确的密钥字节。

但是方法1中的计算过程可以得到改进。如果可以通过分割来实现解密运算，则可以减少计算复杂度。这个方法叫做部分和技术，我们称为方法2。

第一步，我们猜测密钥字节，计算 ，用来表示它。然后我们把密钥字节、跟结合起来，它们构成三元组。同样地，我们计算这三元组的数量。对于每个猜测的值，应该用相似的计算统计量来衡量，其计算复杂度为。

第二步，基于猜测字节和，我们开始猜密钥字节k₂，计算 ，用来表示它。如果我们结合密钥字节和，他们构成个元组 ，我们计算元组的数目。这个统计量是基于三元组的，它们的数目是，密钥字节的数目也是，所以其计算复杂度是。

然后我们在已经猜测的和的基础上接着猜测，计算，记为。显然，有种可能的值，计算复杂度为。

最后，我们在和的基础上猜测密钥字节，计算的值，计不用值的数目。得出计算复杂度为。

所以，对每个猜测的值，拉格朗日插值攻击的判断是在的256个可能的值中挑选255个值来构建拉格朗日多项式，最后一个用来证明密钥的正确性。如果验证没有通过，就可以推断出密钥字节的猜测是错误的。如果验证通过，那么所猜测的值可以作为候选值，我们继续使用多个选择明文组来排除错误的候选值。上述四个步骤的总计算量是。

新的攻击方法和现有的攻击方法之间的攻击复杂性结果的比较将在表1中给出。

VI.总结

相对于文献[9]中提及的方法，本文的两种改进的关于拉格朗日插值攻击的方法在算法复杂度上有显著改善。但是目前它只有对6轮AES-128算法有一个比较低的攻击复杂度。它是否能攻击更高的轮数还需要有进一步的研究。

致谢

这项研究由中国国家自然科学基金（6093199），111项目（B08038）和“中央大学的基础研究基金（K5051201014）支持。

参考文献

[1] J. Daemen, V. Rijmen, “Proposal AES, Rijndael[C] ,”Proceedings from the First Advanced Encryption Standard Candidate Conference, National Institute of Standards and Technology (NIST). 1998.

[2] National Institute of Standard and Technology. Advanced Encryption Standard FIPS197 [S]. November 26,2001.

[3] J. Daemen,V. Rijmen, “The Design of Rijndael:AES-The Advanced Encryption Standard,” ISBN:978-3-642-07646-6(Print) 978-3-662-04722-4(Online).

[4] X. Lai, “On the design and security of block cipher ETH Series in Information Processing[J], ” Vol.1, Konstanz, Hartung-Gorre Verlag,1992.

[5] T. Jakobsen, L.R. Knudsen, “The interpolation attack on block ciphers[C ],” Proceedings of Fast Soft ware Encryption . Berlin:Springer Verlag, 1997, pp28-40 .

[6] T. Jakobsen. “Attacks on block ciphers of low algebraic degree [ J],”Journal of Cryptology, Vol.14, 2002, pp197-210 .

[7] S. Moriai, T. Shi moyama, T. Kaneko, “Interpolati on attacks of the block cipher:SNAKE [ C ], ” Knudsen L.

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[138914]，资料为PDF文档或Word文档，PDF文档可免费转换为Word