基于交换等价的缩减轮AES-128的密钥恢复攻击

张 丽 吴文玲 张 蕾 郑雅菲

(中国科学院软件研究所 北京 100190) (中国科学院大学 北京 100049)

分组密码在对称密码学中起着非常重要的作用，为加密提供了基础的工具，因此，它们是最受信任的加密算法，经常被用作构造其他加密算法的基础工具，这些算法的安全性证明是在假设底层分组密码是理想的情况下进行的.因此对分组密码安全性研究是具有非常重要的现实意义.2001年美国通过3年的征集和评选，新的高级加密标准(advanced encryption standard, AES)[1]得以诞生，成为了至今为止最广为人知和使用最广泛的分组密码.AES的安全性研究也一直是密码学中最重要的热点之一.AES已经被证明能够抵抗差分和线性密码分析.在过去20年的大量研究中只有biclique攻击[2]能比穷举搜索更快地突破全轮的AES，所以突破全轮的AES一直是密码研究人员努力的目标.

近些年，为了研究出更新更好的方法去实现对全轮AES的攻击，研究人员更加关注对于缩减轮的AES攻击上.对缩减轮AES的攻击之所以重要，有3个原因:1)它们使我们能够评估AES的安全冗余，即可以成功攻击的轮数与全轮AES的轮数之比.2)它们使我们能够开发新的攻击技术，随着进一步的改进，这些技术可能会变得更加有效.3)有许多建议使用缩减轮AES作为它们的组件，比如LED[3]，WEM[4]，ElmD[5]等.

当试图评估密码的安全性时，密码的非随机特性可用来区分密码与随机置换.其中密码分析最重要的工具之一无疑是差分密码分析.差分密码分析方法经过多年的发展，已经有了许多的变体，知名的变体方法有截断差分，不可能差分，高阶差分，飞来去器攻击和差分线性攻击.此外，近些年多面体密码分析[6]、子空间密码分析、yoyo game、混合密码分析[7]、交换等价攻击等方法的使用产生了许多好的分析结果.这些结果使得对AES进行越来越多的全新的、更有效的攻击成为可能.

对AES算法的安全性分析工作近些年已有许多优秀的成果.在FSE 2015 Tiessen等人[8]提出了第1个基于积分分析的6轮AES-128密钥恢复，作者研究了在保持其他信息不变的情况下，用一个秘密的8 b S盒去代替AES的S盒.随机选取的S盒有可能高度抵抗差分和线性攻击.结果表明对6轮AES密钥恢复的复杂度已经远小于穷举搜索.在Crypto 2016上，Sun等人[9]提出了第1个AES密钥独立5轮区分器.密钥独立意味着攻击不关心特定的轮密钥，与相关密钥攻击形成对比.他们利用AES列混合矩阵的特性，将4轮积分性质扩展到5轮.虽然他们的区分器需要整个密码本，但它为AES产生了一系列新的基础结果.后来，通过将4轮不可能差分性质扩展到5轮，它被改进为298.2选择明文和2107次计算代价.在FSE 2017，Grassi等人[10]提出了子空间密码分析方法，给出了5轮子空间迹和5轮不可能差分密钥恢复.在2017年的欧密会Eurocrypt上，Grassi等人[11]提出了第1个5轮选择明文区分器，它仅需要232选择明文，计算成本为235.6，存储内存大小为236B.

随后，在2017年Grassi等人证明，通过加密明文空间的某些子空间的陪集，密文对的差分在状态空间的特定子空间中的次数总是8的倍数.亚密会Asiacrypt上，Rønjom等人介绍了Rijndael型分组密码设计的新基本特性，给出了基于Yoyo game[12]的新型3～6轮AES密钥区分器，打破了所有以前的记录.作者介绍了AES的新的确定性4轮属性，即通过对角线的任意子集交换而等价的明文对集合在4轮后加密到一组密文对集合，在最终的线性层之前的完全相同列中它们的差分都为0.该结果在混合密码分析中得到了进一步的探讨.在Asiacrypt 2019上，Bardeh和Rønjom提出了一种适用于类SPN分组密码的新技术——交换等价攻击[13].交换等价攻击属于差分密码分析，是一种选择明文攻击方法，它通过研究特定明文差分的交换性质以及对应密文的0差分模型，将分组密码与随机置换区分开，并在此基础上进行密钥恢复攻击.该文中给出了交换等价的定义，以及如何利用对明文状态进行交换等价及AES的性质来得到在最终的线性层之前的完全相同列中它们的差分都为0.结果表明，当明文从一个特定的集合(交换等价集)中选择时，AES的5轮和6轮选择明文区分器可以区别于随机置换.随后Bardeh基于交换等价的基础知识提出了5轮和6轮AES自适应选择密文区分器[14]，它是从密文出发做交换等价，去寻找解密后明文状态是否具有相同列差分为0，6轮自适应密文区分器需要有283数据和时间复杂度，因此交换等价攻击方法的提出可以看作是AES密码分析的一个巨大飞跃.在Africacrypt 2019中，Bardeh基于子空间的知识提出了对5轮AES的有效攻击[15].到目前为止，最好的密钥恢复攻击可以达到7轮AES.

本文的主要贡献有3个方面：

1) 基于由交换等价攻击提出的5轮自适应选择密文区分器上向前扩展一轮，提出了一个新的6轮AES-128密钥恢复攻击;

2) 攻击主要利用了AES列混合矩阵系数的基本性质.列混合矩阵的每一行或每一列都有3个和为0的元素，使得在选取明文时满足这一性质，另外使得一轮后的状态满足0差分指定状态;

3) 用分组长度为64 b的小版本AES实验验证了我们的理论结果，并且该实验结果支持我们的理论.

本文对6轮AES密钥恢复攻击的结果和已有的6轮AES密钥恢复的结果进行了比较，如表1所示，其中文献[14]中的结果是区分器的结果，其余均表示密钥恢复攻击结果.在数据复杂度、时间复杂度和存储复杂度3方面分别进行了对比，结果表明本文的数据复杂度、时间复杂度的结果是最优的.数据复杂度以选择明文(chosen plaintext, CP)数量/自适应选择密文(adaptive chosen ciphertext, ACC)数量表示，时间复杂度以加密(encryption, E)等价形式来表示，空间复杂度以128 b块大小为单位表示.我们假定一轮加密约等于20次查表[8].因其他文献中复杂度单位不一致，为了方便对比，在这里我们统一换算单位.

Table 1 Key-recovery Attacks on Round-reduced AES-128表1 6轮AES-128密钥恢复攻击

1 AES加密算法介绍

AES分组密码算法是美国于2001年颁布的高级加密标准，分组长度为128 b，128 b明文将内部状态初始化为一个4×4字节矩阵，即所有的运算均在有限域F28上进行.密钥长度分别为128 b，192 b和256 b，根据AES密钥长度的不同，迭代轮数和密钥长度关系为：AES-128的轮数为10轮；AES-192的轮数为12轮；AES-256的轮数为14轮.AES加密算法的轮函数由4种不同变换组成：

1) 字节代替变换(Subbytes,SB).S盒的变换就是字节代替变换的本质，它是一个作用于状态字节的非线性变换，在状态中，其每一个字节都会经过同一个8×8的S盒变换为另一个字节，简记为SB.

2) 行移位变换(Shiftrows,SR).AES加密算法中线性运算包括行移位变换，而且它的移位方案仅仅与状态有关，对一个状态的每一行循环左移不同的位移量，第0行不移位保持不变，第1行循环左移1 B，第2行循环左移2 B，第3行循环左移3 B，简记为SR.

列混合变换有2个基本性质：

性质1.列混合系数矩阵的每一行或每一列都有2个和为0的元素.

性质2.列混合系数矩阵的每一行或每一列都有3个和为0的元素.

4) 子密钥加变换(Addroundkey,ARK).轮子密钥长度是128 b，一个字为32 b.将一个轮子密钥按位异或到一个状态上.轮子密钥按顺序取自扩展密钥，简记为ARK.

此外，AES在第1轮加密之前，有一个白化密钥层，且最后一轮没有列混合变换.

我们用R(*)=MC∘SR∘SB∘ARK(*)表示一轮加密AES.在本文中，为了方便描述，我们考虑保留最后一轮的MC作为全轮AES.此外，S盒被一个秘密的S盒取代，其他结构和组件与原AES加密算法相同.

2 交换等价攻击方法

本节我们主要介绍交换等价的概念和相关的定理.以及在自适应选择下5轮自适应密文区分器的原理.我们先给出一些基本的定义及定理.

2.1 基本定义及定理

一对状态定义了一个有2w tc(α⊕β)可能的列交换差分的集合，其中wtc(x)表示x的非零列的数量.现在可以定义3个相关的运算符，在一对AES状态之间交换对角、列和混合值.

其中L=MC∘SR.

概率为

P(|I|,|J|,|K|)=(2-8)4(|I|+|J|)-|K||J|-2|I||J|.

成立的概率为

我们注意到定理2的结果在解密方向上同样适用，通过应用适当的交换操作来考虑相应的线性层.

2.2 5轮自适应选择密文区分器

本节我们介绍基于交换等价的5轮自适应选择密文区分器.

成立的概率为

由于密文是随机的，在定理3中只考虑|K|=0的情况.Bardeh根据定理3的结果建立一个5轮的区分器.其主要思想是自适应地生成一个新的明文对为

其中α″⊕β″表示α′⊕β′经过5轮解密得到的新的明文状态对.Bardeh在文章中给出了一个例子，例如选取明文状态仅在第1，2对角活跃，另外2个对角取常数值，即d=2.且在混合操作时仅交换一列，即|I|=1.则根据定理3可得：该5轮自适应选择密文区分器概率为p5(|I|,0)=2-46，而随机置换的概率为prand=2-32×(4-d)=2-64.

如图1所示，上层图表示5轮自然加密状态，下层图表示应用了定理3得到的新的加密状态.其中灰色格表示差分活跃的字节，白格表示差分为0的字节，斜条格表示应用了混合交换操作后被交换的字节.

Fig. 1 5-round exchange trail图1 5轮交换迹示意图

3 对6轮AES-128的密钥恢复攻击

本节介绍是本文的主要内容，基于5轮自适应选择密文区分器，我们可以向前扩展一轮得到一个新的6轮AES-128密钥恢复攻击.

3.1 选择合适的明文集合

首先，我们期望所选择的明文经过一轮加密后满足5轮自适应选择密文区分器的输入状态，即R(p0)⊕R(p1)在2个对角保持活跃状态，剩余对角差分为0. 4个对角状态表示如图2所示：

Fig. 2 Diagonal state图2 对角状态示意图

基于AES列混合变换的基本性质2：列混合系数矩阵的每一行或每一列都有3个和为0的元素.如果在列混合变换的4个输入字节中有3个字节非0且有相同的值，剩余一个字节值为0，那么4个输出字节中将有2个0字节，该事件发生的概率为1.不失一般性，我们假设输入差分状态为[a,a,a,0]T，其中a∈F28且非0.那么可以得到输出差分状态中的前2个字节为0.

(1)

为了得到[a,a,a,0]T的输入差分状态，我们定义明文集合Aα,δ的形式，

(2)

其中,α,δ0,δ1∈F28,α是非0随机数，c是常数，那么对于每一个δ0,δ1，每一个明文集合包含216明文对.

3.2 寻找候选值δ0,δ1

从该集合中选取2个不同的明文状态p0∈Aα,δ0,δ1,p1∈Aα,δ0,δ1，满足仅第1对角有活跃状态，其余对角均取常数值.明文状态为

(3)

然后我们定义异或明文状态的密钥为k，且分为4个对角密钥为k=(k0,k1,k2,k3).第1对角的密钥为k0=(k0,0,k1,1,k2,2,k3,3)，2个明文状态经过1轮加密后得到中间状态x0,x1及差分x0⊕x1，中间状态差分x0⊕x1形式为

(4)

我们期望1轮加密后的中间状态差分x0⊕x1符合5轮自适应选择密文区分器的输入形式，即有2个对角保持差分活跃状态.此时如3.1节所述，如果中间状态差分x0⊕x1的第1列中有2 B为0，那么就满足区分器输入状态，即式(1).

令f=SR∘SB∘ARK表示MC之前的操作，则f(p0)和f(p1)的第1列差分记为

(5)

其中S为SB的简记，我们令式(5)的前3个字节简记为

β0=S(k0,0⊕α)⊕S(k0,0),β1=S(k1,1⊕α⊕δ0)⊕S(k1,1⊕δ0),β2=S(k2,2⊕α⊕δ1)⊕S(k2,2⊕δ1).

为了满足式(1)，需要满足β0=β1=β2,即β0=β1=β2时，中间状态第1列为0,0,z2,z3，这样就可以满足5轮区分器的输入要求，即在第2，3对角差分活跃.如图3所示:

Fig. 3 One round of encryption operation图3 1轮加密操作

如果我们令δ0,δ1遍历有限域F28×F28所有值可以得到至少4个值能够保证z0=z1=0，即，

(δ0,δ1)=(k0,0⊕k1,1,k0,0⊕k2,2), (δ0,δ1)=(k0,0⊕k1,1,α⊕k0,0⊕k2,2), (δ0,δ1)=(α⊕k0,0⊕k1,1,k0,0⊕k2,2), (δ0,δ1)=(α⊕k0,0⊕k1,1,α⊕k0,0⊕k2,2)

.

这样我们就可以找到候选值δ0,δ1，即找到正确密钥信息k0,0⊕k1,1和k0,0⊕k2,2.

3.3 猜测正确密钥

vd(R(p′0⊕k)⊕R(p′0⊕k))=vd(0,1,1,0).

(6)

那么就可以筛选出正确密钥，通过对7个新的明文对测试每个对角剩余的216个候选密钥来检测式(6)是否成立，如果成立，那么就可能过滤所有错误密钥.为了减少复杂度，我们对明文的4个对角状态独立进行检测，即对于每一个新的明文对，首先猜测新明文对(p′0,p′1)第1对角剩余的216密钥，经过一轮加密后，满足式(6)的密钥筛选概率为2-16；然后再依次猜测第2，3和4对角密钥，经过一轮加密后，分别满足式(6)的密钥筛选概率均为2-16；最后就可以和随机置换区分开.

3.4 算法的主要攻击过程

主要攻击过程由6个步骤构成：

1) 选择满足式(3)的明文状态(p0,p1)；

2) 对所选的明文状态进行6轮加密操作得到对应的密文对(c0,c1)；

4) 取其中5对新的密文对进行6轮解密操作得到对应的新的明文对(p′0,p′1)；

5) 检查新的明文对(p′0,p′1)经过一轮加密后的状态差分是否满足式(6)；

6) 满足式(6)的密钥则为正确密钥，不满足的则为错误密钥.

攻击过程如算法1所示：

算法1.6轮AES密钥恢复攻击算法.

输入：251.5个不同的明文；

输出：密钥k0

① forδ0from 0 to 28-1 do

② forδ1from 0 to 28-1 do

④c0←enck(p0,6),c1←enck(p1,6)；/*明文加密6轮得到密文*/

⑤ formfrom 0 to 5 do

/*取5对新密文对*/

|I|=1；

/*新密文对解密6轮得到新明文对*/

⑧P←P∪{(p′0,p′1)}

⑨ for all (p′0,p′1)∈Pdo

⑩ ifwt(vd(enck(p′0⊕k,1)⊕

enck(p′1⊕k,1)))≠2 then

/*检查是否满足判定条件(6)*/

3.5 复杂度计算

1) 数据复杂度

首先，该5轮自适应选择密文区分器的概率为2-46，可以构造223.5选择明文和247自适应密文.文献[14]为了减少数据复杂度，对区分器进行了优化，令3轮加密后的第2个对角差分为0，则密文状态仅有3列活跃，最终构造了235.5选择明文和239自适应密文.

2) 时间复杂度

对于每一个对角，猜测密钥的集合应该是216而不是2×216.因为δ0,δ1将遍历所有216个可能的值.足以测试k1,1=k0,0⊕δ0，k2,2=k0,0⊕δ1，并没有必要测试k1,1=k0,0⊕δ0⊕α和k2,2=k0,0⊕δ1⊕α.并且当我们知道k1,1⊕k0,0和k2,2⊕k0,0的值时，我们就可以得到第3个密钥信息k2,2⊕k1,1.

步骤5中复杂度的计算：对于每一个新明文对(p′0,p′1)的每一个对角的密钥我们要检查是否满足式(6)，那么每一次需要2×4次S盒查表，共需要216次和5×239×216新的明文，所以这一步所需的时间复杂度为

2×4×(5×239×216)×216≈276.32.

另外，在对新明文检查时，我们对新明文的4个对角状态同时且独立得去检查，过滤掉不满足式(6)的密钥，该步所需时间复杂度为276.32×4≈278.32.

所以总时间复杂度为278.32，一轮加密约等于20次查表或16次S盒查表[9]，所以总时间复杂度约为272次6轮加密.

3) 空间复杂度

我们需要存储239×5×216新明文，因此需要一个顺序表大小为257.42.另外去检查满足条件的状态对时，需要把明文经过一轮后的状态分别放到大小为232的存储表中去寻找碰撞.所以最终需要空间复杂度为257.42+232×4≈258个AES-128块.

4 小版本AES实验验证

小版本[18]AES(small-scale AES)分组长度为64 b，64 b明文将内部状态初始化为一个4×4半字节矩阵，在矩阵中每一个字是4 b.密钥长度为64 b.轮函数和AES一致，其中字节代替变换使用的是4 b S盒.行移位变换和列混合变换保持不变.

采用和第3节相同的攻击方法，我们可以得到复杂度分析：

数据复杂度.区分器在小版本AES的规模下成立的概率应为2-23，因为AES的字节是属于有限域F28，小版本AES的半字节属于有限域F24，所以经过优化后最后区分器概率为2-35，我们构造了218选择明文和220对自适应密文.我们考虑了5对新的密文对，去检查是否符合式(6).因为这5对新的密文对满足式(4)的概率为2-8×5=2-40，因此错误密钥通过的概率为220×5×28×2-40≈2-11.68≪1.所以用5对就可以过滤掉错误密钥.因此，要找到2个半字节的密钥，我们需要218×28=226选择明文和220×28×5≈230.32自适应选择密文.

时间复杂度.对于总计算复杂度，测试猜测密钥的集合应该是28.考虑δ0,δ1将遍历所有28个可能的值.因此，步骤5：对于5对中的每一对新明文对(p′0,p′1)的每一个密钥我们要检查是否满足式(6)，那么每一次需要2×4次S盒查表，共需要28次和5×220×28新的明文，所以这一步所需的时间复杂度为

2×4×(5×220×28)×28≈241.32.

另外，在对新明文检查时，我们可以对新明文的4个对角状态同时且独立得去检查，过滤掉不满足式(6)的密钥，该步所需时间复杂度为241.32×4≈243.32.

所以总时间复杂度为243.32，一轮加密约等于20次查表或16次S盒查表，所以总时间复杂度约为236次6轮加密.

空间复杂度.我们需要存储5×220×28新明文，因此需要一个顺序表大小为230.32.另外去检查满足条件的状态对时，需要把新明文一轮加密后的状态分别放到大小为216的存储表中去寻找碰撞.所以最终需要空间复杂度为230.32+216×4≈230.32个AES-64块.

通过在C/C++语言中实现了小版本AES，如算法1所示，总共进行了10次测试.所使用的计算机参数为lntel®CoreTMi7-9700 CPU @ 3.00 GHz，内存为16 GB.实验验证了所提出的密钥恢复攻击的有效性，所以实验结果支持理论结果.

5 总 结

在本文中，我们提出了一种对于6轮AES新的密钥恢复攻击结果.该攻击过程利用了基于交换等价提出的5轮自适应选择密文的区分器和AES列混合操作系数矩阵的基本性质，通过在5轮自适应选择密文区分器前扩展一轮，利用列混合操作系数矩阵的基本性质和0差分性质恢复第1轮所需的密钥.结果表明，本文提出的密钥恢复攻击结果在秘密S盒下是最优的结果.另外，我们用一个小版本的AES去测试来支撑理论结果的正确性.