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

张 丽 吴文玲 张 蕾 郑雅菲

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

摘 要 高级加密标准(advanced encryption standard, AES)是一种高安全性的密钥加密系统,在实际生活中受到了多方面认可及使用,自它诞生以来对于它的安全性问题的研究一直是密码学者最感兴趣的.目前对全轮的AES的攻击难度非常大,现有分析方法难以突破穷举搜索方法.朝着突破全轮AES的方向努力,近些年来研究人员十分关注对于缩减轮版本的AES攻击,并且已经涌现了许多优秀的分析方法,其中交换等价攻击——一种新的适合于类SPN分组密码设计的密码分析攻击技术广受关注.研究人员利用该技术得到了比以往更好的秘密密钥选择明文区分器和自适应选择密文区分器.使用了这一新技术,基于AES的5轮自适应选择密文区分器,在恢复密钥时利用了AES加密算法列混合变换系数矩阵的基本性质和0差分性质,提出了一种带有秘密S盒的6轮缩减轮AES-128的密钥恢复攻击,该攻击只要求251.5选择明文和257.42自适应选择密文的数据复杂度以及272时间复杂度.此外,一个小版本AES上的实验验证了提出的密钥恢复攻击.该版本AES块大小为64b,在状态中的每一个字是4b半字节,该实验结果也支持了该研究的理论.最后,当前的对6轮缩减轮AES-128密钥恢复攻击结果比已有的对缩减轮AES-128的密钥恢复攻击结果更优.

关键词 高级加密标准;区分器;交换等价攻击;密钥独立;密钥恢复攻击

分组密码在对称密码学中起着非常重要的作用,为加密提供了基础的工具,因此,它们是最受信任的加密算法,经常被用作构造其他加密算法的基础工具,这些算法的安全性证明是在假设底层分组密码是理想的情况下进行的.因此对分组密码安全性研究是具有非常重要的现实意义.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密钥恢复攻击

攻击方法数据复杂度时间复杂度存储复杂度交换攻击(本文)257.42ACC272E258积分攻击[8]264CP291.68E269交换攻击[13]283CP+283ACC283E不可能差分[16]291.5CP2122E289概率混合差分[17]272.77CP2104.93E233

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.

3) 列混合变换(Mixcolumns, MC).列混合用中的矩阵左乘状态矩阵的每列,元素之间的乘法运算定义在有限域F28上.其目的是将状态矩阵的每一列的元素进行混合,简记为MC,列混合系数:

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

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

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

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

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

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

2 交换等价攻击方法

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

2.1 基本定义及定理

定义1. 列交换差分[13].给定一对状态α,β和一个向量定义列交换差分状态的第i列差分定义为其中αiβi表示状态αβ的第i.

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

定义2. 列交换[13](column exchange).给定一对状态α,β和一个变量定义列交换为

很容易看出是通过在αβ之间交换独立的列得到的.因此,对于任意υ很容易得到

定义3. 对角交换[13](diagonal exchange).给定一对状态α,β和一个变量定义对角交换为

对角交换与列交换之间的关系是直接的,即表示一轮加密操作.

定义4. 混合交换[10](mixed exchange).给定一对状态α,β和一个变量定义混合交换为

其中L=MCSR.

因此可以得到混合交换和列交换之间的关系:进而可以推出对角交换和混合交换之间的关系:

定义5. 0差分模式[12](the zero difference pattern).令状态为x,定义0差分模式ν(x)=(z0,z1,z2,z3),其中表示二进制向量,如果状态x的第i列活跃则zi=0,否则为1.

对于在第1个线性层后或最后一个线性层前的状态为0的列,定义为:νm(x)=υ(L-1(x))和νd(x)=υ(SR(x)).对于子集I⊂{0,1,2,3},记表示二进制向量,如果iI,则否则为0.使用这种表示法来简化结果,避免使用更复杂的状态空间.

定理1[13]. I,J,K⊂{0,1,2,3}分别表示列集合,对角集合和0差分列集合,α,β表示2个随机状态.当状态差分αβK列为0时,对角集合J被交换等价于列集合被交换,即:

概率为

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

定理2[13]. 明文状态α,β在|K|个对角相等K⊂{0,1,2,3},假设0<wt(ν(R5(α)⊕R5(β)))<4,则对于I⊂{0,1,2,3}\K的关系

νm(R5(α)⊕R5(β))=

成立的概率为

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

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

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

定理3[14]. 令明文状态α,β表示2个明文状态,α′,β′∈表示经过5轮加密后的密文状态.假设0<wt(νd(αβ))<4,则对于I⊂{0,1,2,3}的关系

成立的概率为

由于密文是随机的,在定理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,其中aF28且非0.那么可以得到输出差分状态中的前2个字节为0.

(1)

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

(2)

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

3.2 寻找候选值δ0,δ1

从该集合中选取2个不同的明文状态p0Aα,δ0,δ1,p1Aα,δ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及差分x0x1,中间状态差分x0x1形式为

(4)

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

f=SRSBARK表示MC之前的操作,则f(p0)和f(p1)的第1列差分记为

f(p0)C1f(p1)C1=

(5)

其中SSB的简记,我们令式(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,0k1,1,k0,0k2,2), (δ0,δ1)=(k0,0k1,1,αk0,0k2,2), (δ0,δ1)=(αk0,0k1,1,k0,0k2,2), (δ0,δ1)=(αk0,0k1,1,αk0,0k2,2)

.

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

3.3 猜测正确密钥

对于每一个δ0,δ1值,都可以生成一对属于明文集合Aα,δ0,δ1中的明文状态(p0,p1),并且令明文p0的第1对角为令明文p1的第1对角为然后对明文进行6轮加密得到密文(c0,c1).再根据定义4对密文进行混合交换,因为设定在混合操作时仅交换一列,即|I|=1.假设我们令I={0},可以生成和原密文状态c0,c1具有相同的性质的7对新的密文对

再对新的密文对进行6轮解密得到对应的新明文,记作(p0,p1),如果新明文对满足一轮加密后的状态差分在第2,3对角活跃,即

vd(R(p0k)⊕R(p0k))= vd(0,1,1,0).

(6)

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

3.4 算法的主要攻击过程

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

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

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

3) 对密文对(c0,c1)进行定义4的混合交换操作,得到新的密文对共有7种不同的交换组合;

4) 取其中5对新的密文对进行6轮解密操作得到对应的新的明文对(p0,p1);

5) 检查新的明文对(p0,p1)经过一轮加密后的状态差分是否满足式(6);

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

攻击过程如算法1所示:

算法1. 6轮AES密钥恢复攻击算法.

输入:251.5个不同的明文;

输出:密钥k0

① for δ0from 0 to 28-1 do

② for δ1from 0 to 28-1 do

③ 选择明文的第1对角为且令取随机常数值;

c0enck(p0,6),c1enck(p1,6);/*明文加密6轮得到密文*/

⑤ for m from 0 to 5 do

/*取5对新密文对*/

|I|=1;

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

PP∪{(p0,p1)}

⑨ for all (p0,p1)∈P do

⑩ if wt(vd(enck(p0k,1)⊕

enck(p1k,1)))≠2 then

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

break and jump to next key

end if

end for

return k0

end for

end for

end for

3.5 复杂度计算

1) 数据复杂度

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

因此,对于239自适应密文,我们可以生成239×7对新的新密文对以及对应的239×7新明文(p0,p1).此时猜测每一个对角的216剩余密钥时,错误密钥满足式(6)的概率为2-16×7=2-112,因此错误密钥通过的个数为239×7×216×2-112≈2-54.19≪1.实际上,我们仅考虑5对新的密文对,去检查是否符合式(6)也是足够的.对于错误密钥,这5对新的密文对满足式(6)的概率为2-16×5=2-80,因此错误密钥通过的个数为239×5×216×2-80≈2-22.68≪1.所以用5对就可以过滤掉错误密钥,而不需要7对.在实验中,当前5对测试成功时,攻击者总是可以通过生成更多的对来消除不确定性,并且不会影响每次攻击的总数据复杂度.因此,要找到正确密钥k0,0,k1,1,k2,2,k3,3,我们需要235.5×216=251.5选择明文和239×216×5≈257.42自适应选择密文.

2) 时间复杂度

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

步骤5中复杂度的计算:对于每一个新明文对(p0,p1)的每一个对角的密钥我们要检查是否满足式(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对中的每一对新明文对(p0,p1)的每一个密钥我们要检查是否满足式(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® CoreTM i7-9700 CPU @ 3.00 GHz,内存为16 GB.实验验证了所提出的密钥恢复攻击的有效性,所以实验结果支持理论结果.

5 总 结

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

参考文献

[1]Daemen J,Rijmen V. The design of rijndael: AES—The advanced encryption standard[C] //Proc of Information Security and Cryptography, 2nd eds. Berlin: Springer, 2002: 1-8

[2]Bogdanov A,Khovratovich D, Rechberger C. Biclique cryptanalysis of the full AES[C] //Proc of the 17th Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2011: 344-371

[3]Guo Jian, Peyrin T, Poschmann A, et al. The LED block cipher[G] //LNCS 6917: CHES 2011. Berlin: Springer, 2011: 326-341

[4]Cho J, Choi K Y, Dinur I, et al. WEM: A new family of white-box block ciphers based on the even-mansour construction[G] //LNCS 10159: CT-RSA 2017. Berlin: Springer, 2017: 293-308

[5]Bossuet L, Datta N, Mancillas-López C, et al. ElmD: A pipelineable authenticated encryption and its hardware implementation[C] //Proc of IEEE Transactions Computers65. Berlin: Springer, 2016: 3318-3331

[6]Tiessen T. Polytopic cryptanalysis[G] //LNCS 9665: EUROCRYPT 2016. Berlin: Springer, 2016: 214-239

[7]Grassi L. Mixture differential cryptanalysis: A new approach to distinguishers and attacks on round-reduced AES[C] //IACR Transactions Symmetric Cryptology ISSN 2519-173X. Berlin: Springer, 2018: 133-160

[8]Tiessen T, Knudsen L, Kölbl S, et al. Security of the AES with a secret s-box[G] //LNCS 9054: FSE 2015. Berlin: Springer, 2015: 175-189

[9]Sun Bing, Liu M, Guo Jian, et al. New insights on aes-like SPN ciphers[G] //LNCS 9814: CRYPTO 2016. Berlin: Springer, 2016: 605-624

[10]Grassi L,Rechberger C, Rønjom S. Subspace trail cryptanalysis and its applications to AES[C] //Proc of IACR Transactions Symmetric Cryptol. Berlin: Springer, 2016: 192-225

[11]Grassi L, Rechberger C, Rønjom S. A new structural-differential property of 5-round AES[G] //LNCS 10211: EUROCRYPT 2017. Berlin: Springer, 2017: 289-317

[12]Rønjom S, Bardeh N, Helleseth T. Yoyo tricks with AES[G] //LNCS 10624: ASIACRYPT 2017. Berlin: Springer, 2017: 217-243

[13]Bardeh N, Rønjom S. The exchange attack: How to distinguish six rounds of AES with 288.2 chosen plaintexts[G] //LNCS 11923: ASIACRYPT 2019. Berlin: Springer, 2019: 347-370

[14]Bardeh N. A key-independent distinguisher for 6-round aes in an adaptive setting[EB/OL]. IACR Cryptol. ePrint Arch. 2019 [2021-04-23]. https://eprint.iacr.org/2019/945.pdf

[15]Bardeh N, Rønjom S. Practical attacks on reduced-round AES[G] //LNCS 11627: AFRICACRYPT 2019. Berlin: Springer, 2019: 770-783

[16]Cheon J, Kim M, Kim K, et al. Improved impossible differential cryptanalysis of rijndael and crypton[G] //LNCS 2288: ICISC 2001. Berlin: Springer, 2001: 39-49

[17]Grassi L. Probabilistic mixture differential cryptanalysis on round-reduced AES[G] //LNCS11959: SAC 2019. Berlin: Springer, 2019: 53-84

[18]Cid C, Murphy S, Robshaw M. Small scale variants of the AES[G] //LNCS 3557: FSE 2005. Berlin: Springer, 2005: 145-162

Key-Recovery Attack on Reduced-Round AES-128 Using the Exchange-Equivalence

Zhang Li, Wu Wenling, Zhang Lei, and Zheng Yafei

(Institute of Software, Chinese Academy of Science, Beijing 100190) (University of Chinese Academy of Sciences, Beijing 100049)

Abstract The advanced encryption standard (AES) is a kind of high-security secret key cryptosystem. It has been widely recognized and used in real life. Since its birth, the research on its security has been the most interesting to cryptographers. At present, it is very difficult to break the full round AES, and the existing analysis methods are difficult to break through the exhaustive search method. So in recent years, researchers have focused on the attacks which can break reduced-round versions of AES, and there are a lot of excellent analysis methods that have emerged, among them, exchange-equivalence attacks, a new cryptanalytic attack technique suitable for SPN-like block cipher designs is widely concerned. Using this technology, researchers have obtained better the secret-key chosen plaintext distinguisher and adaptive chosen ciphertext distinguisher. In this paper, we run through this new technology, based on 5-round adaptive chosen ciphertexts distinguisher on AES, and at the same time, we use a basic property of the Mixcolumns coefficient matrix and a zero difference property to present a new key-recovery attack on 6-round reduced-round AES-128 with a single secret S-Box that requires only 251.5 chosen plaintexts and 257.42 adaptively chosen ciphertexts data complexity and 272 time complexity. In addition, we practically verified our key-recovery attack on a small-scale variant of the AES. The block size of the small-scale AES is 64 bits, and each word is a 4-bit nibble in the state matrix. The experimental result supports our theory. Finally, the results of the current key-recovery attack on 6-round Reduced-Round AES-128 are better than the previously known attack on Reduced-Round AES-128.

Key words advanced encryption standard (AES); distinguisher; exchange-equivalence attack; key-independent; key-recovery attack

收稿日期2021-06-07;修回日期: 2021-07-28

基金项目国家自然科学基金项目(62072445)

This work was supported by the National Natural Science Foundation of China (62072445).

(zhangli2021@iscas.ac.cn)

中图法分类号 TP309

Zhang Li, born in 1994. PhD. Her main research interests include cryptanalysis of block ciphers.

张 丽,1994年生.博士.主要研究方向为分组密码的密码分析.

Wu Wenling, born in 1966. PhD, professor, and PhD supervisor in the Chinese Academy of Sciences. Senior member of CCF. Her main research interests include design and cryptanalysis of block ciphers and Hash functions, and cryptography.

吴文玲,1966年生.博士,教授,中国科学院博士生导师,CCF高级会员.主要研究方向为分组密码和Hash函数的设计与密码分析以及密码学.

Zhang Lei, born in 1981. PhD, associate professor. Her main research interests include design and cryptanalysis of block ciphers and Hash functions, and cryptography.

张 蕾,1981年生.博士,副教授.主要研究方向为分组密码和Hash函数的设计与密码分析以及密码学.

Zhang Yafei, born in 1981. PhD. Her main research interests include design and cryptanalysis of block ciphers.

郑雅菲,1988年生.博士.主要研究方向为分组密码的设计与密码分析.