Rijndael-160的中间相遇攻击∗

苏崇茂

（1.广西金投互联网金融服务有限公司 南宁 530021）（2.广西金融投资集团有限公司 南宁 530021）

1 引言

Rijndael-b［1］按分组长度的不同划分为 Rijn⁃dael-128， Rijndael-160， Rijndael-192， Rijn⁃dael-224，Rijndael-256等五种加密算法类型，其中密钥长度分别为-128 bits，-192 bits，-256bits的Rijndael-128被选为新的高级加密标准（AES），而分组长度超过128 bits的类型称为大块Rijndael。本文主要关注Rijndael-160的分析结果：

1）2005年J.Nakahara等给出Rijndael-160的多重集攻击［2］：6轮多重集攻击的数据复杂度为234.5选择明文，时间复杂度为243.5次6轮Rijndael-160加密；7轮多重集攻击的数据复杂度为2129选择明文，时间复杂度为2133.5次7轮Rijndael-160加密。

2）2008年J.Nakahara等对Rijndael-160进行不可能差分攻击［3］：6轮攻击数据复杂度和时间复杂度分别为 2105.5选择明文和 2135次6轮Rijn⁃dael-160加密。

3）2008年L.Zhang等提高了Rijndael-160的不可能差分攻击［4］：6轮攻击数据复杂度和时间复杂度分别为293.2选择明文和2114.1次6轮Rijndael-160加密。7轮攻击数据复杂度和时间复杂度分别为2147选择明文和281.9次7轮Rijndael-160加密。

近年来随着大块Rijndael在哈希函数的构造和消息认证码（MAC）中的应用越来越广泛，目前的分析结果主要从不可能差分攻击和积分攻击两个角度来进行［5］，如何针对Rijndael密码给出新的安全性分析是当前的研究热点。

本文将侧重检查Rijndael-160抵抗中间相遇攻击的能力：基于Rijndael-160密码算法结构，设计了一个3、4轮相遇区分器，并由此给出6、7轮Ri⁃jndael-160密码新的安全性评价。

2 Rijndael-160密码算法

本小节简单描述Rijndael-160密码算法，更多的细节参见文献［1］。

Rijndael-160的数据分组长度为160bits，密钥长度范围128-256bits，并且以32bits为增量，相应的轮数为11/11/12/13/14轮。160bits分组数据按列存放，可表示为图1。

图1 Rijndael-160数据表示图

其轮函数由四个部件构成：

1）字节替换（SubBytes）

Rijndael-160中唯一的非线性变换，即把每个状态字节作用于一个相同的S盒。

2）行移位（ShiftRow）

Rijndael-160的字节行移位类似于AES，第一行循环左移0个字节，第二行循环左移1个字节，第三行循环左移2个字节，第四行循环左移3个字节。

3）列混淆（MixColumn）

Rijndael-160的列混淆是用一个可逆矩阵对每列状态字节进行相乘的操作。变换如下：

其中 x0，x1，x2，x3为列混淆前同一列的四个字节，y0，y1，y2，y3为列混淆后同一列的四个字节。

4）轮密钥加（AddRoundKey）

把160bits状态字节与160bits轮子密钥直接异或。

密钥扩展算法参见参考文献［1］。

3 中间相遇攻击基本思想

1977年W.Diffie和M.Hellman针对DES密码算法提出中间相遇攻击方法［6］。其基本思想是把一个密码算法可以看作两部分构成：

1）设明文Pi某个位置输入取遍0～255的所有值（例如第一个字节，记为x）而余下字节均固定，计算某个位置的输出（例如第一个字节，记为 y）可由函数 f表示：y=f(x)。其中 f由一些固定值和Ka决定。

2）通过明文Pi获得相应的密文Ci，对所有可能的Kb计算的第一个字节为 y'，检查是否有 y'=y成立，淘汰不满足该式的Kb。对所有的 i=1，2，...，n 重复以上步骤，错误的密钥将被过滤掉，最终获得正确密钥。

当前中间相遇攻击已广泛应用于分组密码分析中，如文献［7～12］等。

4 3轮Rijndael-160相遇区分器

性质1：考虑一个集合：M(0)={x，a1，a2，...，a19}，x取遍0～255的所有值，ai(1≤i≤19)取值固定。为经过3轮Rijndael-160加密M(0)之后的输出。函数 f:x→由 x 和确定的7个字节完全决定。差分∆Y(j)=f(j)⊕f(0)，1≤j≤17，则由x和确定的6个字节完全决定。

5 6轮Rijndael-160中间相遇攻击

6轮Rijndael-160的中间相遇基本攻击思路为：在上述3轮区分器的基础上，前面加1轮，后面加2轮构成6轮攻击；其中第5轮的轮密钥加RAK与列混合操作MC交换次序，见图2所示。其中*为加密过程中所涉及的字节，C为非考虑字节

具体攻击步骤如下：

第1步：对于性质1中的6个常量字节即26×8=248个可能的参数值，由性质1计算函数。进一步，对于每个 f，计算∆Y(i)=f(i)⊕f(0)，1≤i≤18，把此序列存储在一张哈希表H中。

第2步：定义一个明文空间结构：满足在字节（0，5，10，15）取遍0～255所有值，其余字节取固定值。选择1个上述结构，在选择明文攻击下，6轮Rijndael-160加密这一结构，获取相应的密文。猜测，并做以下处理：

图2 6轮相遇攻击示意图

2）选择19个明文，其对应第2轮输出字节（0）处值x=0，1，…，18，其余字节均为固定值。存储这19个明文，记为

新攻击所需的数据复杂度为24×8=232选择明文。预计算阶段的时间复杂度为19×26×8/6≈249.5次6轮Rijndael-160加密。第2步1）的时间复杂度为232×240×/6≈269.4次6轮Rijndael-160加密。第3步1）所需的时间复杂度为19×240+40/6≈281.5次6轮Rijndael-160加密。

6 7轮Rijndael-160中间相遇攻击

7轮Rijndael-160的中间相遇与6轮攻击类似，只是在3轮区分器的基础上增加一轮。

若直接进行预处理，计算的复杂度将超过穷搜索复杂度，可以利用时空折中的方法，即以增加数据复杂度和时间复杂度的代价来降低预处理复杂度 。 记为第n轮第i行第j列加密处理所涉及的常量字节。令(，概率为 P(，则预处理阶段需要猜测15个字节。新攻击的数据复杂度为248×24×8=280选择明文，预计算阶段的时间复杂度为19×215×8/6≈2121.5次7轮Rijndael-160加密。时间复杂度为19×248×240+40/7≈2129.4次7轮Rijn⁃dael-160加密。

表1 已知的Rijndael-160攻击结果对比

7 比较

由表1可以看出：6轮Rijndael-160或者7轮Rijndael-160的攻击中，中间相遇攻击的数据复杂度最低。

8 结语

本文检查Rijndael-160算法抵抗中间相遇攻击的能力：基于Rijndael-160算法设计了一个3、4轮区分器，并由此给出了6、7轮Rijndael-160的新攻击。结果表明：6轮Rijndael-160或者7轮Rijn⁃dael-160的攻击中，中间相遇攻击的数据复杂度最低。

［1］J.Daemen，V.Rijnmen.The Design of Rijndael AES：The Advanced Encryption Standard［M］.Berlin， Spring⁃er-Verlag，2002：30-45.

［2］J.Nakahara，D.S.de Freitas，Phan，et al.New Multiset At⁃tacks on Rijndael with Large Blocks［C］//Mycrypt 2005.Springer-Verlag，2005.LNCS3715：277-295.

［3］J.Nakahara，I C.Pavao.Impossible-differential Attacks on Large-Block Rijndael［C］//ISC 2007.Springer-Verlag，2007.LNCS4779：104-117.

［4］L.Zhang，W.Wu，J.Park，et al.Improved Impossible Dif⁃ferential Attacks on Large-Block Rijndael［C］//ISC 2008，Springer-Verlag，2008.LNCS5222：298-315.

［5］ Y.Sasaki.Known-Key Attacks on Rijndael with Large Blocks and Strengthening ShiftRow Parameter［C］//IW⁃SEC 2010.Springer-Verlag，2010.LNCS6434：301-315.

［6］ H.Diffie，M.Hellman：Exhaustive Cryptanalysis of the NBSData Encryption Standard［J］.IEEEComputer.1977，10（6）：74-84.

［7］H.Demirci，H.Selcuk：A Meet in the Middle Attack on 8-Round AES［C］//Fast Software Encryption 2008.Springer-Verlag，2008.LNCS5086：116-126.

［8］ H.Demirci，I.Taskin，M.Coban，et al.Improved Meet-in-the-Middle Attacks on AES［C］//INDOCRYPT 2009，Springer-Verlag，2009，LNCS5922：144-156.

［9］O.Dunkelman，N.Keller，A.Shamir.Improved Single-Key Attacks on 8-Round AES［C］//ASIACRYPT 2010，Springer-Verlag 2010，LNCS6477：158-176.

［10］Y.Wei，J.Lu，Y.Hu.Meet-in-the-Middle Attacks on 8 Rounds of the AES Block Cipher under 192 Key Bits［C］//ISPEC 2011， Springer-Verlag 2011， LNCS 6672：222-232.

［11］ G.Sekar，N.Mouha，V.Velichkov，B.P reneel.Meet-in-the-Middle Attacks on Reduced-Round XTEA［C］//Topics in Cryptology-CT-RSA 2011.Spring⁃er-Verlag，2011，LNCS6558：250-267.

［12］苏崇茂，韦永壮，马春波.10轮3D分组密码算法的中间相遇攻击［J］.电子与信息学报，2012，34（3）：694-697.