摘 要:综述了对Rijndael算法所提出的各种攻击并对其进行分析。同时对一些可能会导致对Rijndael攻击的新理论和研究结果做了分析和讨论。

　关键词:Rijndael 攻击方法 安全性分析

　　2000年10月,美国国家标准技术研究所(NIST)宣布Rijndael被确定为高级加密标准(AES)。本文给出目前攻击Rijndael密码的一些主要方法。

　　关于Rijndael的完整密码的系统规范本文并没有详细描述,读者可以参考文献[6]。本文仅对Rijndael算法所提出的攻击作一个整体的概述。另外还介绍了目前已经公布的可能可以破解Rijndael密码的思想。表1中总结了对于给定密钥长度所能攻破的方法的复杂性、攻击的轮数。在表1中已经公布的能攻破Rijndael密码的轮数都小于Rijndael密码的规定的轮数。例如,在2000年公布的基于不可能差分分析(impossible differential)的攻击方法只能对于6轮的128位密钥进行攻击,而其标准是10轮。

　　表1中,几乎所有的攻击(除了在2001年公布的攻击方法外)都是在NIST将其作为AES标准之前就已经公布了。因此可以得到结论:到目前为止,对于Rijndael密码的攻击还没有比穷尽密钥搜索攻击更有效的方法,已经公布的攻击思想不能形成有效的攻击。

　　对于Rijndael密码更详细的攻击的讨论的一些新思想将在下文中详细讨论。在后一部分列举和简单讨论了目前已知的对Rijndael密码的攻击方法,在第3部分对最近提出来的攻击Rijndael密码的新思想(代数攻击)进行讨论。

1 对Rijndael密码的攻击

1.1 差分和线性分析

　　差分和线性分析方法是到目前为止二种最有用的通用密码分析方法。对于这些攻击提供轮数低的复杂度是在设计Rijndael密码时的最基本的准则。

　　对于Rijndael密码来说,已经证明对于一个4轮的Rijndael密码来说,差分分析方法的概率上限是2-150,线性分析方法的概率上限是2-75。结合实际Rijndael密码的轮数,这些轮数对于抵抗上述攻击能够提供足够的安全性。对于这方面更详细的讨论可以参考文献[6]。

1.2 变量法

　　在变量法公布之后,线性和差分攻击方法在某些方面已经做了扩展,也公布了一些和它相关的攻击方法。最好的扩展方法是截段差分分析法(truncated differentials)。但是在设计Rijndael密码的时候就已经考虑到这种攻击方法,Rijndael密码能够比较好地抵抗这种攻击。其他的攻击方法还有:

　　不可能差分攻击:差分密码攻击是利用高概率特征或差分恢复密钥,不可能差分攻击是利用概率为0(或非常小)的特征或差分,其基本思想是排除那些导致概率为0(或非常小)的特征或差分的候选密钥。对5轮的Rijndael密码,可以用不可能差分攻击方法,它要求229.5个选择明文、231个密文、242个存储字和226小时的预先处理时间,该结果在参考文献[4]中做了改进,使得它可以攻击6轮的Rijndael密码。但是对于轮数更高的Rijndael密码,采用该方法攻击则没有更好的效果。

　　Square攻击:对Rijndael密码分析最有效的就是Square攻击,它是一个选择明文攻击,通过研究基于字节结构的密文来进行攻击。它对于和Rijndael密码的其中一轮有相似结构的任何密文都是有效的。这种攻击的其他名字还有“饱和攻击”(Lucks在参考文献[11]中提出,这种攻击能够破解具有7轮的192位和256位Rijndael密码),L.Knudsen和D.Wagner提出的“积分密码分析”,以及A.Biryukov和A.Shamir提出的“结构攻击”。

　　最初的Square攻击对6~7轮的Rijndael密码(例如AES-128和AES-192)的破解比穷尽密钥搜索攻击快。N.Ferguson等在减少破解的工作方面做了一些优化,因此,它能够在有256位相关密码的277个明文,2224个密文,破解9轮的AES-256密码。

Collision攻击:这种攻击是由Gilbert和Minier提出[9],它对于破解7轮的AES-128、AES-192、AES-256仍然是最好的破解方法。

2 一些新的理论和分析

　　尽管前面介绍了能够对简化的Rijndael密码的攻击方法,但是这些方法对Rijndael密码本身的攻击并没有任何效果。上述的大多数攻击方法都和称为“代数攻击”的方法有关,可以简要地归纳为如下步骤:

　　(1)收集信息阶段:密码分析者将密文表达为有很多变量的一系列简单方程。这些变量包括明文、密文和密钥中的位或字节,还有一些中间计算结果和轮密钥。

　　(2)攻击阶段:密码分析者利用输入的数据,例如明文—密文对等,代替在第一步中得到的方程中的变量,并且用各种办法将方程解出来,这样就可以根据求出的变量来恢复密钥。

　　按照Rijndael密码的设计原则,Rijndael密码是用一些比较巧妙的方程表达式来实现的。虽然从单纯的数学角度来看,要从这些方程组表达式得到密码的密钥非常困难,但是也可能利用其他的一些方法比较容易地解决。已经有一些方法利用Rijndael密码的代数结构来破解密码。但是到目前为止还没有能够进行有效攻击的方法,大多数文章的结论还有待于进一步研究和探讨。下面讨论在这方面最新的一些研究成果和理论。

　　(1)连分式。Ferguson,Schroeppel和Whiting[8]得出一个关于Rijndael密码的闭公式,该公式可以看作是由一个连分式生成的。在5轮以后中间结果的任何字节都可以表示为如下表达式:

　　在上述表达式中,每个K是一个字节,它依赖于扩充了的密码中的一些字节;每个Ci是一个已知的常数;每个*是一个给定的指数或下标。但是这些值依赖于它们所包含符号的求和变量。一个完全扩展的式(1)的版本有2²⁵项。为了破解一个10轮的Rijndael密码(AES-128),密码分析者可以通过二个这种类型的方程来利用计算的中间结果。第一个方程可以将5轮以后的中间变量作为明文字节函数;第二方程可以将6～10轮以后的中间变量作为明文字节函数。结合二个方程可以得到一个含有226个未知变量的方程。通过重复这个方程2²⁶/16个给定的明文/密文对,从信息理论的意义上来说,就有足够多的信息能够解出未知变量。但是到目前为止,还没有任何人公开发表能够具体地去寻找一种算法来解决这样一类问题的方程。

　　(2)XSL。Courtois and Pieprzyck[5]通过研究发现,在Rijndael密码中使用的S-盒可以通过一系列隐含的二次布尔方程表达。用字母x₁,……x₈表示输入的位,用字母y1,……y8表示输出的位。则存在如下形式的等式:

　　其中函数f为二次方程。

　　从理论上来说,只需要8个像(2)式的方程就能够定义S-盒,但是Courtois and Pieprzyck经研究发现,能够构建多于所需要的方程个数。此外,他们还宣称这些特定的方程可以有助于简化解决问题的复杂性。他们发现一个算法,该算法在处理这个问题的时间复杂度低于指数。可是有很多的研究者怀疑他们计算的正确性。例如Don Coppersmith曾说过“我坚信Courtois-Pieprzyk的工作是有漏洞的。他们把线性独立的方程个数估计过多了,他们所得到的结果事实上没有足够的线性方程来解决问题”。此外,他还说“这种方法有一定的优点,也值得去研究,但是并不能像他们所说的那样能够破解Rijndael密码。”T.Moh也怀疑他们计算方法的正确性。无论如何,在假设他们的计算方法正确的前提下,破解密码的复杂性的最好估计是2255步(对于不同参数的复杂性的计算可以参见文献[5]的8.1节)。这就意味着,他们的攻击仅仅可以破解Rijndael密码为256位的密钥(AES-256)。因为相应的穷尽密钥搜索攻击的复杂度为2256。现在还不清楚Rijndael密码的什么属性影响到该攻击的复杂性。这种攻击方法对AES的影响不会太大,因为即使这种攻击方法完全正确,AES的安全性也比DES好得多。

　　(3)嵌入法。Murphy and Robshaw[12]定义了分组密码BES,它是对128字节为一组而不是128位为一组的对象来处理。按照Murphy and Robshaw的观点,BES密码的代数结构甚至比Rijndael密码的代数结构更简单。此外,Rijndael密码能够被嵌入BES密码中,也就是说有如下映射φ:

　　在这个方程中,K代表密钥,x代表明文。Murphy and Robshaw通过研究得出BES的一些性质。但是BES的属性不能转换为Rijndael密码的性质。

　　Murphy and Robshaw相信,如果将XSL方法应用到BES,则解决步骤的复杂性将比直接将XSL方法应用到Rijndael密码的复杂性大大降低。

　　(4)双密文攻击。在文献[1]中介绍了双密文的概念,它基本是“嵌入”技术的归纳。其基本内容为:如果取三个不可逆映射f,g和h,则存在一个双密文DUAL满足:

　　在这个方程中,K代表密文密钥,x代表明文。这个方程表示对于一个给定的明文和密钥双密文产生相同的密文文本。从这个意义上来说,双密文等价于原来的密文。因此,可以实现和分析双密文而不是原来的密文。在文献[1]中确定了Rijndael密码中的240个双密文。到现在,还没有关于双密文有何漏洞的报导。一个类似的概念,称为Rijndael-GF[6]。已经证明,对于抵抗差分和线性密码分析,Rijndael-GF族密码系统的密文都具有相同的安全性。

　　(5)Plaintext-dependent Repetition Codes攻击。2003年1月8号,Eric Filiol发表了一篇文章[3],在该文中他宣称可以用一种非常简单、快速和惟密文的攻击方法来攻击AES。其基本思想是:假设pi,ci和ki分别为AES的明文、密文和密钥位。这些位的变化范围总是0~127,0是第一个字节的最重要的位,127是最后一个字节最不重要的一个位。例如c71是密文中第9个字节的最重要的位。在文章中,作者宣称如果明文是以形式:

　　以大概是0.50003的概率成立。如果该论断能成立,则该方法对AES的攻击大约只须231步即可。目前,这种论断还没有取得一致的认可,有些密码分析者怀疑其正确性。

3 结束语

　　在本文中,主要展示和讨论了到目前为止,所有关于Rijndael密码系统的密码分析成果。此外还讨论了有可能能够破解Rijndael密码的一些新的可能的攻击方法。但是有些方法还有待于进行进一步的证明和探讨。

参考文献

1 Barkan E,Biham E.In how many ways can you write Rijndael?In:Proceedings of Asiacrypt′02,Queenstown,

New Zealand,2002

2 冯登国.密码分析学.北京:清华大学出版社,2000

3 杨义先,孙伟,钮心.现代密码新理论.北京:科学出版社,2002

4 Cheon J H,Kim M J,Kim K et al.Improved Impossible Differential Cryptanalysis of Rijndael and Cryp ton,Information Security and Cryptology-ICISC 2001,2001

5 Courtois N T,Pieprzyk J.Cryptanalysis of block ciphers with overdefined systems of equations.In:

Proceedings of Asiacrypt′02,Queenstown,New Zealand,2002

6 Daemen J,Rijmen V.The Design of Rijndael.Information Security and Cryptography,Springer Verlag,2002

7 Ferguson N,Kelsey J,Lucks S et al.Improved cryptanalysis of Rijndael.In:Proceedings of Fast Software

Encryption-FSE′00,New York,NY,USA,April,2000

8 Ferguson N,Schroeppel R,Whiting D.A simple algebraic representation of Rijndael.In:Proceedings of

Selected Areas in Cryptography-SAC′01,Toronto,Ontario,Canada,August,2001

9 Gilbert H,Minier M.Acollision attack on seven rounds　of Rijndael.In:Proceedings of the Third Advanced

Encryption Standard Conference,New York,USA, April,2000

10 Knudsen L R,Wagner D.Integral cryptanalysis(extended abstract).In:Proceedings of Fast Software

Encryption-FSE′02,Leuven,Belgium,February,2002

11 Lucks S.Attacking seven rounds of Rijndael under 192-bit and 256-bit keys.In:Proceedings of the

Third Advanced Encryption Standard Conference,New　York,USA,April,2000

12 Murphy S,Robshaw M J B.Essential algebraic structure within the AES.In:Proceedings of Crypto′02,

Santa Barbara,California,USA,2002