Table 1 Symbol Description
表1 符号说明
谢高淇 卫宏儒
(北京科技大学数理学院 北京 100083) (xiegaoqi@sina.cn)
ARIA密码算法 [1] 是韩国国家安全研究所提出的一种SPN(substitution-permutation network)结构 [2] 的密码算法，隶属于分组密码算法 [3] ，在2004年时，韩国工业部、商业部和能源部确定ARIA为韩国分组密码算法标准.在结构上，ARIA密码算法和AES(advanced encryption standard)算法 [4-5] 很相似，故很多用来分析AES算法的分析方法可以用来对ARIA密码算法进行分析，并取得了很好的效果.本文类比对AES算法的分析，结合对ARIA密码算法的研究，实现对ARIA密码算法新的攻击.
从文献[6-7]可知，不可能差分分析方法是由Biham和Knudsen提出的，一种使用不可能出现的差分即概率为0的差分特征过滤错误密钥猜测，从而得到正确密钥值的分析方法.一经提出，该方法便得到了广泛的应用，被应用于分析密码结构与算法.尤其是对AES算法的分析中效果良好，ARIA密码算法和AES算法结构上相似，不可能差分分析针对ARIA密码算法的分析也取得了非常好的效果.
本文所使用符号具体释义如表1所示：
Table 1 Symbol Description
表1 符号说明
ARIA密码算法是SPN结构型分组密码，分组长度为128 b，密钥长度为128 b,192 b,256 b，相应的轮数分别为12轮、14轮和16轮 [8] .128 b的数据分组对应一个4×4的表格，共16 B，如图1所示.
Fig. 1 The state of 128 b on ARIA
图1 ARIA的128 b状态
ARIA的轮函数由3个部件构成：
1) 混淆层(substitution layer, SL )
选用2个S盒 S 1 和 S 2 以及它们的逆 S -1 1 和 S -1 2 .每一个S盒定义为 F 28 上的1个可逆的非线性变换函数 S ：{0,1} 8 →{0,1} 8 .ARIA有2种类型的S盒层：
奇数轮采用的变换为
偶数轮采用的变换为
2) 扩散层(diffusion layer, DL )
扩散层是一个{0,1} 8×16 →{0,1} 8×16 的映射，为16 B的线性运算：
( y 0 , y 1 ,…, y 15 ) T = L ∘( x 0 , x 1 ,…, x 15 ) T ，
其中， L ( x )表示线性函数，“∘”是复合运算符.
其中：
y 0 = x 3 ⊕ x 4 ⊕ x 6 ⊕ x 8 ⊕ x 9 ⊕ x 13 ⊕ x 14 ，
y 1 = x 2 ⊕ x 5 ⊕ x 7 ⊕ x 8 ⊕ x 9 ⊕ x 12 ⊕ x 15 ，
y 2 = x 1 ⊕ x 4 ⊕ x 6 ⊕ x 10 ⊕ x 11 ⊕ x 12 ⊕ x 15 ，
y 3 = x 0 ⊕ x 5 ⊕ x 7 ⊕ x 10 ⊕ x 11 ⊕ x 13 ⊕ x 14 ，
y 4 = x 0 ⊕ x 2 ⊕ x 5 ⊕ x 8 ⊕ x 11 ⊕ x 14 ⊕ x 15 ，
y 5 = x 1 ⊕ x 3 ⊕ x 4 ⊕ x 9 ⊕ x 10 ⊕ x 14 ⊕ x 15 ，
y 6 = x 0 ⊕ x 2 ⊕ x 7 ⊕ x 9 ⊕ x 10 ⊕ x 12 ⊕ x 13 ，
y 7 = x 1 ⊕ x 3 ⊕ x 6 ⊕ x 8 ⊕ x 11 ⊕ x 12 ⊕ x 13 ，
y 8 = x 0 ⊕ x 1 ⊕ x 4 ⊕ x 7 ⊕ x 10 ⊕ x 13 ⊕ x 15 ，
y 9 = x 0 ⊕ x 1 ⊕ x 5 ⊕ x 6 ⊕ x 11 ⊕ x 12 ⊕ x 14 ，
y 10 = x 2 ⊕ x 3 ⊕ x 5 ⊕ x 6 ⊕ x 8 ⊕ x 13 ⊕ x 15 ，
y 11 = x 2 ⊕ x 3 ⊕ x 4 ⊕ x 7 ⊕ x 9 ⊕ x 12 ⊕ x 14 ，
y 12 = x 1 ⊕ x 2 ⊕ x 6 ⊕ x 7 ⊕ x 9 ⊕ x 11 ⊕ x 12 ，
y 13 = x 0 ⊕ x 3 ⊕ x 6 ⊕ x 7 ⊕ x 8 ⊕ x 10 ⊕ x 13 ，
y 14 = x 0 ⊕ x 3 ⊕ x 4 ⊕ x 5 ⊕ x 9 ⊕ x 11 ⊕ x 14 ，
y 15 = x 1 ⊕ x 2 ⊕ x 4 ⊕ x 5 ⊕ x 8 ⊕ x 10 ⊕ x 15 .
3) 轮密钥加(round key addition, RKA )
中间状态与128 b的轮子密钥进行异或操作，轮子密钥由密钥编排算法生成.
差分密码分析利用高概率特征(或差分)恢复密钥，而不可能差分密码分析方法的基本思想是利用概率为0的特征(或差分)，排除那些导致特征(或差分)概率为0的候选密钥.对于一条概率为0的差分路径，当使用正确密钥解密密文对时，得不到符合该路径的差分；但若使用猜测密钥解密密文对时，得到符合该路径的差分，则该猜测密钥值是错误的；通过这种方法来筛去所有的错误密钥猜测值，那么剩下的就是需要恢复的正确密钥.
利用不可能差分分析对 r 轮迭代密码进行分析的流程为：
步骤1. 寻找 r -1轮差分 α 0→ α r -1 ，使此特征成立的概率为0.
步骤2. 选择明文对( P , P ⊕ α 0 )，满足差分为 α 0，并进行 r 轮加密，所得密文记作 C 和 C * .
步骤3. 猜测第 r 轮轮密钥 k r 的所有可能值，对每一个猜测密钥分别对 C 和 C * 解密1轮，所得到的值记作 D 和 D * ；判断 D ⊕ D * = α r -1 是否成立，如果成立则对应的猜测值一定是错误密钥.
步骤4. 重复上述步骤，直到密钥唯一确定为止.
Fig. 2 Features of impossible differential on ARIA
图2 ARIA不可能差分性质
假设通过上述攻击可以得到| K |位密钥，每个明密文对可以淘汰2 - t 的密钥量，为保证正确的密钥被唯一确定，所需要的明密文对 N 必须满足：
(2 | K | -1)×(1-2 - t ) N <1，
当 t 比较大时可得：
N >2 t ×ln 2×| K |≈2 t -0.53 | K |，
观察此式可以发现，在实现不可能差分密码分析时，所需要猜测的密钥量基本不影响数据复杂度，这便是和其他攻击的不同之处.不可能差分密码分析方法的数据复杂度主要是由每个明密文对所能淘汰密钥的概率所决定的.
本文要构造7轮ARIA密码算法的不可能差分攻击，在新的4轮不可能差分路径的前边增加2轮，后边增加1轮，得到新的7轮不可能差分攻击路径.然后利用ARIA密码算法扩散层的性质，过滤无用的明密文对，大大降低复杂度，构成新的7轮ARIA算法的不可能差分攻击.
性质1 . 如图2所示，给定一明文对，满足仅在字节(1,12)处取值不相等，其他字节处相等.在经过4轮变换后，密文对不满足3个性质：
1) 2个密文在字节(3,11,12,13)处不相等；
2) 密文在其他字节处相等；
3) 密文差分在(3,11,12,13)处相等.
即：
(0, a 1 ,0,0,0,0,0,0,0,0,0,0, a 12 ,0,0,0)|→
(0,0,0, f ,0,0,0,0,0,0,0, f , f , f ,0,0)
是不可能的，其中 a 1 , a 12 , f 是非0值.
证明. ARIA的4轮变换可以分为前2轮变换和后2轮变换这2部分.
对于前2轮变换.假设输入差分为
(0, a 1 ,0,0,0,0,0,0,0,0,0,0, a 12 ,0,0,0)，
因为是用同一密钥对2个明文进行的加密运算，所以经过 RKA 后差分没有发生变化.
经过 SL ，差分变为
(0, b 1 ,0,0,0,0,0,0,0,0,0,0, b 12 ,0,0,0)，
其中， b 1 , b 12 为非0字节.
随后进行第1轮 DL 变换，差分变为
p =2 32 
2 64 =2 -32 ，
然后进行第2轮 RKA 和 SL 变换，差分变为
(0, c 1 , c 2 ,0,0, c 5 , c 6 , c 7 , c 8 , c 9 ,0, c 11 , c 12 ,0,0, c 15 )，
再进行第2轮的 DL 变换，差分变为
( d 0 , d 1 ,…, d 15 )，
其中，有 d 6 = d 11 = c 2 ⊕ c 7 ⊕ c 9 ⊕ c 12 .
至此，完成了ARIA前2轮变换.
再考虑：
(0,0,0, f ,0,0,0,0,0,0,0, f , f , f ,0,0)
经过2轮变化的逆过程.
经过1次 DL -1 变换，变成
(0, f ,0,0, f , f ,0,0, f ,0,0,0,0,0,0,0)，
然后再经过1次 SL -1 变换，差分变为
(0, e 1 ,0,0, e 4 , e 5 ,0,0, e 8 ,0,0,0,0,0,0,0)，
其中， e 1 , e 4 , e 5 , e 8 为非0值.
又因为异或子密钥不改变差分值，故直接继续进行下一次 DL -1 ，差分变为
( e 4 ⊕ e 8 , e 5 ⊕ e 8 , e 1 ⊕ e 4 , e 5 , e 5 ⊕ e 8 , e 1 ⊕ e 4 ,
0, e 1 ⊕ e 8 , e 1 ⊕ e 4 , e 1 ⊕ e 5 , e 5 ⊕ e 8 , e 4 , e 1 , e 8 ,
e 4 ⊕ e 5 , e 1 ⊕ e 4 ⊕ e 5 ⊕ e 8 )，
再经过1次 SL -1 和 RKA 变换后，差分变为
其中 
这是由于 
至此，ARIA的2轮逆运算结束.
然而，由经过第2次 DL -1 得到的差分值可得到 
于是 
矛盾，所以上述的4轮不可能差分性质是正确的.
证毕.
性质2 . 如图2所示，发现以下4个等式成立时，将使 
通过 DL 变换到 
时在10 B(0,2,3,4,7,9,10,12,13,14)处差分为0的概率为2 -32 ，而在随机的情况下此概率为2 -80 .这4个等式分别为
c 0 = c 13 = b 6 ⊕ b 8 ，
(1)
c 3 = c 14 = b 5 ⊕ b 11 ，
(2)
c 5 = c 8 = b 1 ⊕ b 15 ，
(3)
c 2 ⊕ c 4 ⊕ c 7 ⊕ c 9 ⊕ c 10 ⊕ c 15 =0.
(4)
证明. 定义一个明文集合结构，即在字节(0,2,3,4,7,9,10,12,13,14)处差分为0，其余字节差分不为0.在输出 处，若存在1个结构(2 48 个明文)，通过 DL -1 变换后，可以得到 c 0 = b 6 ⊕ b 8 和 c 13 = b 6 ⊕ b 8 ，则无论 b 6 和 b 8 为何值，式(1)都是以概率1成立的.
同理可证明式(2)和式(3)都成立.
同时，有：
c 2 = b 1 ⊕ b 6 ⊕ b 11 ⊕ b 15 ,
c 4 = b 5 ⊕ b 8 ⊕ b 11 ⊕ b 15 ,
c 7 = b 1 ⊕ b 6 ⊕ b 8 ⊕ b 11 ,
c 9 = b 1 ⊕ b 5 ⊕ b 6 ⊕ b 11 ,
c 10 = b 5 ⊕ b 6 ⊕ b 8 ⊕ b 15 ,
c 15 = b 1 ⊕ b 5 ⊕ b 8 ⊕ b 15 .
所以容易得证式(4)也是以概率1成立的.
假设4个等式在随机情况下的概率分别记为： p 1 , p 2 , p 3 , p 4 .此时，容易发现： p 1 =2 -8 ， p 2 =2 -8 ， p 3 =2 -8 ， p 4 =2 -8 ，即 
的数量为
由于 DL 是线性变换，则在 处有2 48 个，故满足以上4个等式的 
的概率为
p =2 48 2 80 =2 -32 .
证毕.
本文在3.1节已证明的4轮不可能差分路径的前边增加2轮变换，后边增加1轮变换，得到新的7轮不可能差分攻击，如图3所示.其中ARIA密码算法的最后1轮没有扩散层，取而代之的是轮密钥加( RKA ).
攻击过程如下：
步骤1. 定义一个由2 8×(16-2) =2 112 个明文构成的明文空间结构，这些明文在字节(6,11)处取固定值，在其他字节(0,1,2,3,4,5,7,8,9,10,12,13,14,15)处取遍所有值.这种结构共有 
个明文对.
步骤2. 取2 N 个上述结构(即2 N ×2 223 =2 223+ N 个明文对).选取明文对中在(0,1,2,4,5,6,7,8,9,10,14,15)这12 B处差分为0的密文对，满足这样的密文对有2 223+ N ×2 -8×(16-4) =2 127+ N 对.
Fig. 3 7-round impossible differential attacks on ARIA
图3 7轮ARIA不可能差分攻击
步骤3. 猜测密钥字节( k 8,3 , k 8,11 , k 8,12 , k 8,13 )，对每个保留下来的密文对( C , C )，分别进行计算：
⊕ k 8,3 )⊕ S 2 ( C (3)⊕ k 8,3 ), 
⊕ k 8,11 )⊕ S 2 ( C (11)⊕ k 8,11 ), 
⊕ k 8,12 )⊕ 
⊕ k 8,12 ), 
⊕ k 8,13 )⊕ 
⊕ k 8,13 ),
选择在字节(3,11,12,13)处差分 
相等的密文对.则密文对还剩余有2 127+ N ×2 -24 =2 103+ N 个.
步骤4. 猜测 k 1 的14 B，并利用性质2进行分析.
步骤4.1. 假设剩余的密文所对应的明文对为( P , P )，猜测( k 1,0 , k 1,13 )，计算：
⊕ k 1,0 )⊕ S 1 ( P (0) ⊕ k 1,0 ), 
⊕ k 1,13 )⊕ S 2 ( P (13) ⊕ k 1,13 ),
选择在字节(0,13)处差分 
相等的明文对.剩余明文对有2 103+ N ×2 -8 =2 95+ N 个.
步骤4.2. 猜测( k 1,3 , k 1,14 )，计算：
⊕ k 1,3 )⊕ 
⊕ k 1,3 ), 
⊕ k 1,14 )⊕ 
⊕ k 1,14 ),
选择在字节(3,14)处差分 相等的明文对.剩余明文对有2 95+ N ×2 -8 =2 87+ N 个.
步骤4.3. 类似地，猜测( k 1,5 , k 1,8 )密钥字节，计算：
⊕ k 1,5 )⊕ S 2 ( P (5) ⊕ k 1,5 ), 
⊕ k 1,8 )⊕ S 1 ( P (8) ⊕ k 1,8 ),
选择在字节(5,8)处差分 相等的明文对.剩余明文对还有2 87+ N ×2 -8 =2 79+ N 个.
步骤4.4. 猜测( k 1,2 , k 1,4 , k 1,7 , k 1,9 , k 1,10 , k 1,15 )密钥字节，计算：
⊕ k 1,2 )⊕ 
⊕ k 1,2 ), 
⊕ k 1,4 )⊕ S 1 ( P (4) ⊕ k 1,4 ), 
⊕ k 1,7 )⊕ 
⊕ k 1,7 ), 
⊕ k 1,9 )⊕ S 2 ( P (9) ⊕ k 1,9 ), 
⊕ k 1,10 )⊕ 
⊕ k 1,10 ), 
⊕ k 1,15 )⊕ 
⊕ k 1,15 ),
选择满足：
⊕ 
⊕ 
⊕ 
⊕ 
⊕ 
相应明文对.此时剩余的明文对为2 79+ N ×2 -8 =2 71+ N 个.
步骤4.5. 猜测( k 1,1 , k 1,12 )的值，计算：
⊕ k 1,1 )⊕ S 2 ( P (1) ⊕ k 1,1 ), 
⊕ k 1,12 )⊕ S 1 ( P (12) ⊕ k 1,12 ),
此时没有条件，所以没有过滤.
步骤4.6. 对于步骤4.1～4.5中的 
计算
选择 
在(0,2,3,4,7,9,10,12,13,14)这10 B处差分为0的明文对.因为这样的概率为 p =2 -32 ，所以明文对还剩余有2 71+ N ×2 -32 =2 39+ N 个.
步骤5. 猜测( k 2,1 , k 2,5 , k 2,6 , k 2,8 , k 2,11 , k 2,15 )的值，计算：
⊕ k 2,1 )⊕ 
⊕ k 2,1 ), 
⊕ k 2,5 )⊕ 
⊕ k 2,5 ), 
⊕ k 2,6 )⊕ 
⊕ k 2,6 ), 
⊕ k 2,8 )⊕ 
⊕ k 2,8 ), 
⊕ k 2,11 )⊕ 
⊕ k 2,11 ), 
⊕ k 2,15 )⊕ 
⊕ k 2,15 ),
选择差分 
在字节(1,5,6,8,11,15)处既相等又不为0的明文对.因为是不可能差分，所以猜测的子密钥字节均为错误的，必须排除掉.通过分析2 39+ N 个密文对，还剩余2 48 ×(1-2 -40 ) 2 39+ N 个错误值.令2 48 ×(1-2 -40 ) 2 39+ N <1，得到 N =7.
分析该攻击的时间复杂度：
在步骤3中，若同时计算4 B的值，时间复杂度为
而实际上，只需3×2 149 即可.由于可以先对2 B的值进行计算，然后进行比较.如若相等，进行下一步的计算；如若不相等，可直接舍弃，从而达到降低复杂度的效果.对于剩余的对，使用相同的方法进行计算，并和前面的值相比较.如若相等，便保留，如若不相等，则舍弃.同理，对剩余的对，使用相同的方法进一步过滤.此方法称为“early-abort”技术 [8] .
因为这一步只需要计算4 B的值，所以共需要
次1轮加密运算.
注意到下边的每一步中都有应用“early-abort”技术.
因为在步骤4中，只有 RKA 和 SL 这2种运算，故可以认为每一次的运算都相当于2 3的1轮运算.
所以步骤4中：
步骤4.1需要
次1轮加密；
步骤4.2需要
次1轮加密；
步骤4.3需要
次1轮加密；
步骤4.4需要
次1轮加密；
步骤4.5需要
次1轮加密；
步骤4.6只有DL变换操作，所以需要
次1轮加密.
步骤5需要的复杂度为
2 32 ×2×2 112 ×(2 46 ×2 16 +2 38 ×2 24 +2 30 ×2 32 + 
次1轮加密.
所以总的攻击复杂度为
次7轮加密运算.
从分析过程中的步骤1中可知，本文选择明文数为2 112 ，并选择2 N 个结构，其中 N =7，所以本文攻击共需要2 119 选择明文.
综上，本文的攻击复杂度为：2 119 选择明文和大约2 218 次7轮加密运算.
本文要构造8轮ARIA密码算法的不可能差分攻击，类似构造7轮ARIA密码算法的不可能差分攻击，在新的4轮不可能差分路径的前边增加2轮，后边增加2轮，得到新的8轮不可能差分路径.然后利用ARIA密码算法扩散层的性质，过滤掉无用的明密文对，从而构成8轮ARIA算法的不可能差分攻击.
性质3 . 如图4所示，发现5个等式成立时，将使 
通过 DL -1 变换到 
时在12 B(0,1,2,4,5,6,7,8,9,10,14,15)处差分为0的概率为2 -32 ，而在随机的情况下此概率为2 -96 .这5个等式分别为
h 0 = h 10 = h 13 = g 6 ⊕ g 13 ,
(5)
h 2 = h 9 = h 12 = g 11 ⊕ g 12 ,
(6)
h 3 ⊕ h 4 ⊕ h 8 =0,
(7)
h 1 ⊕ h 5 ⊕ h 11 =0,
(8)
h 6 ⊕ h 7 ⊕ h 14 =0.
(9)
证明. 定义一个明文集合结构，在字节(15)处差分为0，其余字节差分不为0.如果在输出 处有一个结构(2 32 个明文)，通过 DL -1 变换后，可以得到 h 0 = g 6 ⊕ g 13 , h 10 = g 6 ⊕ g 13 , h 13 = g 6 ⊕ g 13 ，所以无论 h 0 , h 10 , h 13 为何值，式(5)都以概率1成立的.
同理可证明式(6)也是成立的.
Fig. 4 8-round impossible differential attacks on ARIA
图4 8轮ARIA不可能差分攻击
同时，有 h 3 = g 11 ⊕ g 13 ， h 4 = g 11 ， h 8 = g 13 .所以容易得证式(7)也是以概率1成立的.同理， h 1 = g 12 , h 5 = g 3 , h 11 = g 3 ⊕ g 12 , h 6 = g 12 ⊕ g 13 , h 7 = g 3 ⊕ g 11 ⊕ g 12 ⊕ g 13 , h 14 = g 3 ⊕ g 11 .所以式(8)和式(9)也是成立的.
假设5个等式在随机情况下的概率分别记为： p 1 , p 2 , p 3 , p 4 , p 5 .此时，容易发现： p 1 =2 -16 , p 2 =2 -16 , p 3 =2 -8 , p 4 =2 -8 , p 5 =2 -8 ，即 
的数量为 
由于 DL -1 是线性变换，则在 处有2 32 个，故满足以上5个等式的 的概率为 p =2 32 2 64 =2 -32 .
证毕.
本文在3.1节的性质1已证明4轮不可能差分路径的前边增加2轮，后边增加2轮，得到新的8轮不可能差分攻击，如图4所示.其中ARIA密码算法的最后1轮没有扩散层，取而代之的是轮密钥加( RKA ).
攻击过程如下：
步骤1. 定义一个由2 8×(16-2) =2 112 个明文构成的明文空间结构，这些明文在字节(6,11)处取固定值，在其他字节(0,1,2,3,4,5,7,8,9,10,12,13,14,15)处取遍所有值.这种结构共有 个明文对.
步骤2. 取2 N 个上述结构(即2 N ×2 223 =2 223+ N 个明文对).选取明文对中在第16 B(15)处差分为0的密文对，满足这样的密文对有2 223+ N ×2 -8×(16-15) =2 215+ N 对.
步骤3. 猜测密钥字节
( k 9,0 , k 9,1 , k 9,2 , k 9,3 , k 9,4 , k 9,5 , k 9,6 , k 9,7 ,
k 9,8 , k 9,9 , k 9,10 , k 9,11 , k 9,12 , k 9,13 , k 9,14 ),
对每个保留下来的密文对( C , C )，分别进行如下计算：
⊕ k 9,0 )⊕ S 1 ( C (0)⊕ k 9,0 ), 
⊕ k 9,1 )⊕ S 2 ( C (1)⊕ k 9,1 ), 
⊕ k 9,2 )⊕ 
⊕ k 9,2 ), 
⊕ k 9,3 )⊕ 
⊕ k 9,3 ),
⋮ 
⊕ k 9,11 )⊕ 
⊕ k 9,11 ), 
⊕ k 9,12 )⊕ S 1 ( C (12)⊕ k 9,12 ), 
⊕ k 9,13 )⊕ S 2 ( C (13)⊕ k 9,13 ), 
⊕ k 9,14 )⊕ 
⊕ k 9,14 ),
选择 在字节(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14)处差分相等的密文对.则密文对还剩余有2 127+ N ×2 -112 =2 103+ N 个.
步骤4. 猜测 k 8 的15 B，并利用性质3进行分析.
步骤4.1. 对 
计算 
选择 
在(0,1,2,4,5,6,7,8,9,10,14,15)这12 B处差分为0的明文对.这样的概率为 p =2 -32 ，所以剩余的明文对还有2 103+ N ×2 -32 =2 71+ N 个.
步骤4.2. 猜测( k 8,0 , k 8,10 , k 8,13 )，并计算：
⊕ k 8,0 )⊕ 
⊕ k 8,0 ), 
⊕ k 8,10 )⊕ 
⊕ k 8,10 ), 
⊕ k 8,13 )⊕ 
⊕ k 8,13 ),
选择在字节(0,10,13)处差分 
相等的明文对.剩余的明文对有2 71+ N ×2 -16 =2 55+ N 个.
步骤4.3. 猜测( k 8,2 , k 8,9 , k 8,12 )，计算：
⊕ k 8,2 )⊕ 
⊕ k 8,2 ), 
⊕ k 8,9 )⊕ 
⊕ k 8,9 ), 
⊕ k 8,12 )⊕ 
⊕ k 8,12 ),
选择在字节(2,9,12)处差分 相等的明文对.剩余的明文对有2 55+ N ×2 -16 =2 39+ N 个.
步骤4.4. 猜测( k 8,3 , k 8,4 , k 8,8 )密钥字节，计算：
⊕ k 8,3 )⊕ 
⊕ k 8,3 ), 
⊕ k 8,4 )⊕ 
⊕ k 8,4 ), 
⊕ k 8,8 )⊕ 
⊕ k 8,8 ),
选择满足 h 3 ⊕ h 4 ⊕ h 8 =0的明文对.剩余的明文对为2 39+ N ×2 -8 =2 31+ N 个.
步骤4.5. 猜测( k 8,1 , k 8,5 , k 8,11 )密钥字节，计算：
⊕ k 8,1 )⊕ 
⊕ k 8,1 ), 
⊕ k 8,5 )⊕ 
⊕ k 8,5 ), 
⊕ k 8,11 )⊕ 
⊕ k 8,11 ),
选择满足 h 1 ⊕ h 5 ⊕ h 11 =0的明文对.剩余的明文对为2 31+ N ×2 -8 =2 23+ N 个.
步骤4.6. 猜测( k 8,6 , k 8,7 , k 8,14 )密钥字节，计算：
⊕ k 8,6 )⊕ 
⊕ k 8,6 ), 
⊕ k 8,7 )⊕ 
⊕ k 8,7 ), 
⊕ k 8,14 )⊕ 
⊕ k 8,14 ),
选择满足 h 6 ⊕ h 7 ⊕ h 14 =0的明文对.剩余的明文对为2 23+ N ×2 -8 =2 15+ N 个.
步骤5. 猜测 k 1 的14 B，并利用性质2进行分析.
步骤5.1. 假设剩余的密文所对应的明文对为( P , P )，猜测( k 1,0 , k 1,13 )，计算：
⊕ k 1,0 )⊕ S 1 ( P (0) ⊕ k 1,0 ), ⊕ k 1,13 )⊕ S 2 ( P (13) ⊕ k 1,13 ),
选择在字节(0,13)处差分 相等的明文对.剩余的明文对有2 15+ N ×2 -8 =2 7+ N 个.
步骤5.2. 猜测( k 1,3 , k 1,14 )，计算：
⊕ k 1,3 )⊕ ⊕ k 1,3 ), ⊕ k 1,14 )⊕ ⊕ k 1,14 ),
选择在字节(3,14)处差分 相等的明文对.剩余的明文对有2 7+ N ×2 -8 =2 N -1 个.
步骤5.3.类似地，猜测( k 1,5 , k 1,8 )密钥字节，计算：
⊕ k 1,5 )⊕ S 2 ( P (5) ⊕ k 1,5 ), ⊕ k 1,8 )⊕ S 1 ( P (8) ⊕ k 1,8 ),
选择在字节(5,8)处差分 相等的明文对.剩余的明文对还有2 N -1 ×2 -8 =2 N -9 个.
步骤5.4. 猜测( k 1,2 , k 1,4 , k 1,7 , k 1,9 , k 1,10 , k 1,15 )密钥字节，计算：
⊕ k 1,2 )⊕ ⊕ k 1,2 ), ⊕ k 1,4 )⊕ S 1 ( P (4) ⊕ k 1,4 ), ⊕ k 1,7 )⊕ ⊕ k 1,7 ), ⊕ k 1,9 )⊕ S 2 ( P (9) ⊕ k 1,9 ), ⊕ k 1,10 )⊕ ⊕ k 1,10 ), ⊕ k 1,15 )⊕ ⊕ k 1,15 ),
选择满足条件：
⊕ ⊕ ⊕ ⊕ ⊕
的明文对.此时剩余的明文对为2 N -9 ×2 -8 =2 N -17 个.
步骤5.5. 猜测( k 1,1 , k 1,12 )的值，计算：
⊕ k 1,1 )⊕ S 2 ( P (1) ⊕ k 1,1 ), ⊕ k 1,12 )⊕ S 1 ( P (12) ⊕ k 1,12 ),
此时没有条件，所以没有过滤.
步骤5.6. 对于步骤5.1～5.5中的 计算 
选择 在(0,2,3,4,7,9,10,12,13,14)这10 B处差分为0的明文对.因为这样的概率为 p =2 -32 ，所以明文对还剩余有2 N -17 ×2 -32 =2 N -49 个.
步骤6. 猜测( k 2,1 , k 2,5 , k 2,6 , k 2,8 , k 2,11 , k 2,15 )的值，计算：
⊕ k 2,1 )⊕ ⊕ k 2,1 ), ⊕ k 2,5 )⊕ ⊕ k 2,5 ), ⊕ k 2,6 )⊕ ⊕ k 2,6 ), ⊕ k 2,8 )⊕ ⊕ k 2,8 ), ⊕ k 2,11 )⊕ ⊕ k 2,11 ), ⊕ k 2,15 )⊕ ⊕ k 2,15 ),
选择差分 在字节(1,5,6,8,11,15)处既相等又不为0的明文对.因为是不可能差分，所以猜测的子密钥字节均为错误的，必须排除掉.通过分析2 N -49 个密文对，还剩余2 48 ×(1-2 -40 ) 2 N -49 个错误值.令2 48 ×(1-2 -40 ) 2 N -49 <1，得到 N =95.
分析该攻击的时间复杂度：
在步骤3中，本文依然使用“early-abort”技术，共需要
2×(2 310 ×2 16 +2 302 ×2 24 +2 294 ×2 32 +2 286 ×2 40 +
2 278 ×2 48 +2 270 ×2 56 +2 262 ×2 64 +2 254 ×2 72 +
2 246 ×2 80 +2 238 ×2 88 +2 230 ×2 96 +2 222 ×2 104 + 
次1轮加密运算.
因为在步骤4中，只有 RKA 和 SL 这2种运算，故可以认为每一次的运算都相当于2 3的1轮运算.
所以步骤4中：
步骤4.1只有 DL 变换操作，所以需要
次1轮加密；
步骤4.2需要
次1轮加密；
步骤4.3需要
次1轮加密；
步骤4.4需要
次1轮加密；
步骤4.5需要
次1轮加密；
步骤4.6需要
次1轮加密.
在步骤5中，同理，只有 RKA 和 SL 运算，可以认为每一次的运算都相当于2 3的1轮运算.
所以步骤5中：
步骤5.1需要
次1轮加密；
步骤5.2需要
次1轮加密；
步骤5.3需要
次1轮加密；
步骤5.4需要
次1轮加密；
步骤5.5需要
次1轮加密；
步骤5.6只有 DL 变换操作，所以需要
次1轮加密.
步骤6需要的复杂度为
2 32 ×2×2 112 ×(2 46 ×2 16 +2 38 ×2 24 +2 30 ×2 32 +
次1轮加密.
所以总的攻击复杂度为
次8轮加密运算.
在分析过程步骤1中，本文选择明文数为2 112 ，并选择2 N 个结构，其中 N =95，所以本文攻击共需要2 207 选择明文.
综上，本文的攻击复杂度为：2 207 选择明文和大约2 346 次8轮加密运算.
本文在证明不可能差分路径成立的基础上，根据ARIA密码的结构特征，在第3节中，于不可能差分路径前面增加2轮、后面增加1轮，实现了对ARIA分组密码算法的新的7轮不可能差分分析.研究表明，此路径下，7轮不可能差分攻击共需要2 119 选择明文和大约2 218 次7轮加密运算.与表2中7轮ARIA密码算法的不可能差分攻击结果相比较，攻击进一步降低了数据复杂度和时间复杂度.在第4节，本文首次提出了对ARIA密码算法的8轮不可能差分攻击，在不可能差分路径前面增加2轮、后面增加2轮，构成8轮ARIA密码算法的新攻击.研究表明，在此路径下，8轮ARIA密码算法的不可能差分攻击共需要2 207 选择明文和大约2 346 次8轮加密运算.但超过穷举搜索的攻击复杂度，故可认为在该路径下8轮不可能差分攻击中ARIA密码算法是安全的.
Table 2 Summary of Cryptanalysis of ARIA by Impossible Differential
表2 ARIA密码算法的不可能差分分析的安全性总结
在以后的研究中，着重寻找新的不可能差分路径，证明新的不可能差分性质，尝试降低8轮ARIA密码算法不可能差分攻击的时间复杂度和数据复杂度.由于ARIA算法和AES算法结构上相似，很多用来分析AES算法的分析方法对ARIA密码算法肯定具有一定的效果，所以继续对ARIA的其他分析方法进行研究，比如线性攻击、中间相遇攻击、积分攻击等，提高对ARIA算法的攻击轮数.同时，也可以将对ARIA密码算法的分析方法迁移到对AES密码算法的分析中，用来改进AES现有的分析结果.
参考文献
[1]Daesung K, Jaesung K, Sangwoo P, et al. New block cipher: ARIA[G] 
LNCS 2971: Proc of the 6th Int Conf on Information Security and Cryptology. Berlin: Springer, 2004: 432-445
[2]Chen Shaozhen. The Basis of Cryptography[M]. Beijing: Science Press, 2008 (in Chinese)(陈少真. 密码学基础[M]. 北京: 科学出版社, 2008)
[3]Stinson D. Cryptography Theory and Practice[M]. Translated by Feng Dengguo. 3rd ed. Beijing: Publishing House of Electronics Industry, 2009 (in Chinese)(Stinson D. 密码学原理与实践[M]. 冯登国, 译. 3版. 北京: 电子工业出版社, 2009)
[4]Liu Ya, Gu Dawu, Liu Zhiqiang, et al. New improved impossible differential attack on reduced-round AES-128[G] LNEE 114: Proc of Computer Science and Convergence. Berlin: Springer, 2012: 453-461
[5]Mala H, Dakhilalian M, Rijmen V, et al. Improved impossible differential cryptanalysis of 7-round AES-128[G] LNCS 6498: Proc of the 11th Int Conf on Cryptology in India. Berlin: Springer, 2010: 282-291
[6]Dunkelman O. Techniques for cryptanalysis of block ciphers[D]. Haifa, Israel: Technion-Israel Institute of Technology, Faculty of Computer Science, 2006
[7]Biryukov A, Wagner D. Slide attacks[G] LNCS 1636: Proc of the 6th Int Workshop on Fast Software Encryption. Berlin: Springer, 1999: 245-259
[8]Du Chenghang. Impossible differential analysis and middle encounter attack of block cipher algorithm ARIA[D]. Jinan: Shandong University, 2011 (in Chinese)(杜承航. 分组密码算法ARIA的不可能差分分析和中间相遇攻击[D]. 济南: 山东大学, 2011)
[9]Wu Wenling, Zhang Wentao, Feng Dengguo. Impossible differential cryptanalysis of reduced-round ARIA and Camellia[J]. Journal of Computer Science and Technology, 2007, 22(3): 449-456
[10]Li Shenhua, Song Chunyan. Improved impossible differential cryptanalysis of ARIA[C] Proc of the 2008 Int Conf on Information Security and Assurance. Los Alamitos, CA: IEEE Computer Society, 2008: 129-132
[11]Du Chenghang, Chen Jiezhe. Impossible differential cryptanalysis of ARIA reduced to 7 rounds[G] LNCS 6467: Proc of the 9th Int Conf on Cryptology and Network Security. Berlin: Springer, 2010: 20-30
[12]Su Chongmao. New impossible differential attack on 7-round reduced ARIA[J]. Journal of Computer Applications, 2012, 32(1): 45-48 (in Chinese)(苏崇茂. 7轮ARIA-256的不可能差分新攻击[J]. 计算机应用, 2012, 32(1): 45-48)
Xie Gaoqi , born in 1994. Master. His main research interests include cryptanalysis of block ciphers.
Wei Hongru , born in 1963. Associate professor. His main research interests include mathematics, information security and cryptography, and key technologies of Internet of things.
Xie Gaoqi and Wei Hongru
( School of Mathematics and Physics , University of Science and Technology Beijing , Beijing 100083)
Abstract ARIA cipher is a new block cipher proposed by some South Korean experts in 2003. The design principle of ARIA is similar to the AES, and it has relatively high security. ARIA was established as a Korean Standard block cipher algorithm by Korean Agency for Technology and Standards in 2004. Combining the features of ARIA algorithm, a new impossible differential attack on 7-round ARIA is proposed by adding 2-round at the beginning and 1-round at the end. It is shown that this new impossible differential attack requires a data complexity of about 2 119 chosen plaintexts and a time complexity of about 2 218 7-round ARIA encryptions. Compared with the previous impossible differential attacks, this attack efficiently reduces the data complexity and time complexity. Similar to the attack of 7-round, a new impossible differential attack on 8-round ARIA is proposed first time by adding 2-round at the beginning and 2-round at the end. It is shown that this new impossible differential attack requires a data complexity of about 2 207 chosen plaintexts and a time complexity of about 2 346 8-round ARIA encryptions. It has exceeded the attack complexity of exhaustive search attack, so we can believe that ARIA cryptographic algorithm is safe in this path of 8-round impossible differential attack.
Key words block cipher; ARIA cipher; impossible differential; time complexity; data complexity
摘 要 ARIA密码是2003年由韩国学者提出，并在2004年被选为韩国分组密码标准的新的分组密码算法.为了使用不可能差分方法对ARIA密码算法进行安全性分析，首先，根据ARIA密码的结构特征，构造一条4轮不可能差分路径，通过在不可能差分路径前面增加2轮、后面增加1轮的方式，对7轮ARIA密码算法进行不可能差分攻击.研究结果表明：7轮攻击共需要2 119 选择明文和大约2 218 次7轮加密运算.与已有结果相比较，该次攻击进一步降低了数据复杂度和时间复杂度.同时，在4轮不可能差分路径基础上，通过前面增加2轮、后面增加2轮的方式，首次提出了对ARIA密码算法的8轮不可能差分的新攻击.研究结果表明：8轮不可能差分攻击共需要2 207 选择明文和大约2 346 次8轮加密运算,已超过穷举搜索的攻击复杂度，故可认为在该路径下的8轮不可能差分攻击中ARIA密码算法是安全的.
关键词 分组密码；ARIA密码；不可能差分；时间复杂度；数据复杂度
中图法分类号 TP309
收稿日期 ： 2017-04-19；
修回日期： 2018-01-11
基金项目 ： 国家自然科学基金项目(61672509，U1603116)；内蒙古自治区科技创新引导奖励资金(2012)
This work was supported by the National Natural Science Foundation of China (61672509, U1603116) and the Oriented Award Foundation of Inner Mongolia Autonomous Region for Scientific and Technological Innovation (2012).
通信作者 ： 卫宏儒(weihr@ustb.edu.cn)