对TweAES的相关调柄多重不可能差分攻击

蒋梓龙 金晨辉

(战略支援部队信息工程大学 郑州 450001)

1 引言

在NIST轻量级密码标准竞赛中，TweAES算法[1]是进入到第2轮的认证加密候选算法。TweAES是类AES-128的可调分组密码，具体而言，是在AES-128算法[2]的基础上，可以额外选取4 bit主调柄，通过简单的线性运算将主调柄扩展为8 bit子调柄，将扩展的8 bit子调柄值与偶数轮输出进行异或加操作，即得到了TweAES算法。

不可能差分攻击[3,4]是差分攻击的一种变体，之后Tsunoo等人[5]提出了多重不可能差分的思想，Boura等人[6,7]和Li等人[8,9]运用多重不可能差分攻击，对分组密码算法AES, CLEFIA[10], LBlock[11]，Fox[12]等均得到很好的效果。经过了多年以来对AES-128的密码分析[13-18]，大量的分析结果涌现而出，Leurent等人[19]在2021年的欧洲密码年会上，详细地分析了AES的密钥生成算法，揭示了子密钥扩散的不完全性。在这些攻击方案中，最好的攻击结果可以攻击到7轮的AES-128，不可能差分攻击也取得了很好的攻击结果。TweAES算法在AES-128的基础上，新引入了4 bit主调柄，所以其安全性更值得深入研究。

TweAES算法设计报告[1]的第3.4.2小节，在选择调柄的条件下，设计者给出了TweAES算法对积分攻击、不可能差分攻击、截断差分攻击、中间相遇攻击的安全性分析。在这些攻击方案中，最有效的是不可能差分攻击，设计者构造了一个6轮的相关调柄不可能差分区分器，并给出了一个8轮的不可能差分攻击方案。Niu等人[20]利用自动求解器STP，搜索了更多高效TweAES算法的不可能差分区分器。此外，Niu等人还指出了TweAES算法设计报告中的8轮不可能差分攻击有瑕疵，其时间复杂度大于穷举攻击，所以不是一个有效攻击，并给出了对8轮TweAES算法的有效不可能差分攻击方案。

为进一步研究TweAES算法抵抗不可能差分攻击的安全性，本文提出了对TweAES算法的相关调柄多重不可能差分攻击。首先，本文构造了两条都需要攻击16 Byte子密钥的攻击路径，他们有相同的明文结构与14 Byte公共子密钥。因相同的明文结构和大量的公共密钥，攻击者可以利用同一个明文结构下的明密对，筛选两次子密钥，提高了攻击方案对子密钥筛选的效率。此外，本文利用密钥生成算法的不完全性，有针对性地选择了子密钥位置，可以提高主密钥恢复阶段的效率，从而改进整体攻击方案。

本文组织结构如下：第2节给出TweAES的算法描述和符号说明；第3节阐述6轮相关调柄的不可能差分区分器；第4节给出TweAES算法的8轮多重不可能差分攻击方案及复杂度分析；第5节总结全文。

2 基本概念

在本节，2.1节先简要描述了TweAES算法，2.2节对符号进行了说明。

2.1 TweAES算法描述

TweAES算法是基于AES-128的可调认证加密算法，属于SPN结构分组密码算法。其分组长度为128 bit，可看作一个16 Byte的 4 ×4矩阵，主密钥长度设置为128 bit。由Byte替换 SB、行移位变换SR 、列混合变换M C、 轮密钥加 AK、 调柄加A T这5种变换构成。其中前4种变换与AES-128完全一致，而调柄加变换每隔两轮注入一次调柄值，5种变换简述如下：

(1)字节替换S B：由AES算法中的16个S盒并置而成，对128 bit输入进行非线性变换。

(2)行移位变换S R：由行号值对每行循环左移，即第i行循环左移iByte(i=0,1,2,3)。

(3)列混合变换 M C：由AES算法的左乘矩阵，对状态的每列进行乘法运算。

(4)轮密钥加 AK：每轮输入值与对应子密钥异或加，本文记k0为主密钥，其余子密钥是由AES-128的密钥扩展方案生成k1,k2,...,k10共10个128 bit子密钥。

(5)调柄加 AT ： 4 bit主调柄为(t0,t1,t2,t3)，然后通过简单的线性变换将其扩展为8 bit的子调柄，记t=t0⊕t1⊕t2⊕t3，则扩展的8 bit调柄为(t0,t1,t2,t3)→(t0,t1,t2,t3,t ⊕t0,t ⊕t1,t ⊕t2,t ⊕t3)

记扩展的8 bit调柄为T=(t0,t1,t2,t3,t4,t5,t6,t7)， 将第ibit异或加到前两行第iByte的最低比特位，字节位置如图1所示。子调柄加每隔两轮操作一次，即在第2, 4, 6, 8, 10轮注入扩展的8 bit子调柄。

图1 TweAES算法的轮函数图(偶数轮)

关于TweAES算法的更多细节可以查阅文献[1]。

2.2 符号说明

若无特殊说明，本文使用表1所示符号约定。

表1 符号说明

3 TweAES的6轮相关调柄不可能差分区分器

本文运用的TweAES的6轮相关调柄不可能差分区分器与文献[1,20]相似，本文的攻击方案用到了8个区分器，具体的输入差分和输出差分如表2所示。在这里以第1个区分器为例，对其进行简要阐述，具体的区分器差分传递过程如图2所示。

表2 TweAES的8个6轮相关调柄不可能差分区分器

本小节选取的主调柄4 bit差分值为 ( 1,0,0,1)，经过线性变换扩展的子调柄的8 bit差分值为(1,0,0,1,1,0,0,1)。注意，因为子调柄加操作是将1 bit值异或加至对应字节的最低比特位，所以子调柄差分非零字节对应的差分值均为0x01。以图2的不可能差分区分器为例，本文描述其性质如下：

图2 TweAES算法的6轮相关调柄不可能差分区分器

是算法TweAES的一个6轮的相关调柄不可能差分区分器。 证毕

其余的7个不可能差分区分器的证明，与上述证明类似。

4 TweAES的8轮多重不可能差分攻击

本节基于上述的两类6轮不可能差分区分器，提出8轮的多重不可能差分攻击方案。将上一节中，从第3轮到第8轮的6轮不可能差分区分器，分别往前和往后各扩展一轮，得到了第2轮到第9轮的8轮不可能差分攻击路径。用两类不可能差分区分器可以分别构造两条攻击路径，每条攻击路径需要攻击14 Byte子密钥，具体而言，第1条攻击路径需要攻击(k1,(0,1,5,6,10,11,12,15),k9,(0,7,9,10,12,13))，第2条攻击路径需要攻击 (k1,(0,1,5,6,10,11,12,15),k9,(0,3,6,9,12,13))。值得注意的是，两条攻击路径有相同的明文结构，并且有12 Byte的公共子密钥(k1,(0,1,5,6,10,11,12,15),k9,(0,9,12,13))。第1条攻击路径如图3所示。

图3 TweAES算法的8轮相关调柄不可能差分攻击路径

由文献[20]给出的8轮不可能差分攻击方案可知，时间复杂度最大的阶段在于数据处理阶段，即数据量过大，对明密文进行排序的时间远大于筛选错误子密钥的时间。针对这个情况，本文提出的改进可以降低所需要的数据量，从而可以降低整体攻击方案的时间复杂度，其降低数据量的思想如下：

(1)因为两条攻击路径有相同的明文结构，则对一个明文结构中的明密文，可以用两条不同的攻击路径去筛选子密钥。相较于只用一条攻击路径，极大地提升了对错误子密钥的筛选效率，从而可以减少攻击方案数据量。

(2)在每条攻击路径需要猜测14 Byte子密钥的情况下，有12 Byte的公共子密钥。在两条攻击路径筛选完毕后，得到候选子密钥(k1,(0,1,5,6,10,11,12,15),k9,(0,7,9,10,12,13))和 (k1,(0,1,5,6,10,11,12,15),k9,(0,3,6,9,12,13))，只有12 Byte公共子密钥(k1,(0,1,5,6,10,11,12,15),k9,(0,9,12,13))值相同时，才可以判定16 Byte子密钥(k1,(0,1,5,6,10,11,12,15),k9,(0,3,6,7,9,10,12,13))为候选密钥，此时错误密钥的通过率为2-96，可以再次提高对错误密钥的筛选效率，减少数据量。

(3)利用密钥生成算法的不完全性，找到了子密钥间的关联，从而可以更高效地在主密钥恢复阶段筛选错误候选密钥。这样本文的攻击方案就可以在主密钥恢复阶段，筛选更多的错误密钥，从而可以减少一定的数据量。

利用上述的改进，本文的攻击方案对3项复杂度均有所改进。

4.1 TweAES的8轮相关调柄不可能差分攻击步骤

本文攻击步骤包括：预处理阶段、数据处理阶段、子密钥筛选阶段和主密钥恢复阶段，一共4个部分。分别阐述如下：

数据处理阶段：先选取两个主调柄记作T1,T2，且两个主调柄的差分值为( 1,0,0,1)。在明文的(2, 3, 4, 7, 8, 9, 13, 14)这8 Byte位置取固定值，遍历其他8 Byte，可以得到 264明文，将其称为一个明文结构。对每个明文结构下的 264明文，用两个调柄T1, T2对这 264个明文进行加密查询，分别可以得到两组 264个密文。以两组密文的12 Byte (1, 2,3, 4, 5, 6, 7, 8, 10, 11, 14, 15)共24 Byte为指标，运用快速排序技术[20]对明文及对应的两组密文一同排序，将其存入表Ω中，再选取对应的有效明密对。

第1条攻击路径的有效明密对：选取在密文的(1, 2, 3, 4, 5, 6, 8, 11, 14, 15)这10 Byte值相同的密文段，分别从两组密文中各取一个组成密文对，则保证了主调柄差分值为 ( 1,0,0,1)，且满足第1条攻击路径的明密对差分要求。在只使用一对主调柄的条件下，一个明文结构可以生成2128-80=248个有效明密对。

第2条攻击路径的有效明密对：选取在密文的(1, 2, 4, 5, 7, 8, 10, 11, 14, 15)这10 Byte值相同的密文段，分别从两组密文中各取一个组成密文对，则保证了主调柄差分值为 ( 1,0,0,1)，且满足第2条攻击路径的明密对差分要求。在只使用一对主调柄的条件下，一个明文结构可以生成248个有效明密对。

本文选取 2n个明文结构，每条攻击路径可得2n+48对有效明密对。

(5) 明文结构中的全部有效明密文对筛选完毕后，用下一个明文结构重复(1)至(4)步。若全部明文结构均已检测完毕，进入主密钥恢复阶段。

主密钥恢复阶段：现有两个候选子密钥表G1K和G2K，其中索引地址上值为0的为候选子密钥，值为1的为错误子密钥，设每个表中有Nk个候选密钥。只有12 Byte公共子密钥值相同时，才可以判定16 Byte(k1,(0,1,5,6,10,11,12,15),k9,(0,3,6,7,9,10,12,13))子密钥为候选密钥，故1 6 B y t e 候选密钥有(Nk)2×2-96个。

文献[18,19]研究了AES的密钥生成算法，本文利用子密钥扩散的不完全性，提高主密钥恢复的效率。如表3所示，第9轮子密钥后12 Byte，只与第1轮部分子密钥字节相关。故本文先穷举部分第1轮子密钥字节，对比验证排除部分错误候选密钥后，再穷举第1轮其余部分子密钥字节，直至得到全部的第1轮子密钥。如果还未唯一确定正确密钥，再用加密验证排除剩余的错误密钥，直至得到正确密钥。现在已知第1轮子密钥k1,(0,1,5,6,10,11,12,15)与第9轮子密钥k9,(0,3,6,7,9,10,12,13)。主密钥恢复阶段的具体步骤如下：

(1) 穷举第1轮子密钥中的5 Bytek1,(3,7,9,13,14)，此时第1轮子密钥只有3 Bytek1,(2,4,8)未知，由表3知k9,(12)与k1,(2,4,8)无关，则可以由第1轮子密钥计算密钥k9,(12)的 值，若与候选密钥k9,(12)的值不相符，则判定其为错误密钥排除。检测完还有(Nk)2×2-96×240×2-8=(Nk)2×2-64个候选密钥。

(2) 穷举第1轮子密钥中的1 Bytek1,(4)，此时第1轮子密钥只有2 Bytek1,(2,8)未知，由表3知k9,(6)与k1,(2,8)无关，则可以由第1轮子密钥计算密钥k9,(6)的 值，若与候选密钥k9,(6)的值不相符，则判定其为错误密钥排除。检测完还有(Nk)2×2-64×28×2-8=(Nk)2×2-64个候选密钥。

(3) 穷举第1轮子密钥中的1 Bytek1,(8)，此时第1轮子密钥只有1 Bytek1,(2)未知，由表3知k9,(9,10,13)与k1,(2)无关，则可以由第1轮子密钥计算密钥k9,(9,10,13)的 值，若与候选密钥k9,(9,10,13)的值不相符，则判定其为错误密钥排除。检测完还有(Nk)2×2-64×28×2-24=(Nk)2×2-80个候选密钥。

表3 AES-128中第9轮子密钥后12 Byte与第1轮子密钥关联

(4) 穷举第1轮子密钥中的1 Bytek1,(2)，此时得到了全部16 Byte第1轮子密钥，可以由第1轮子密钥计算密钥k9,(0,4,7)的 值，若与候选密钥k9,(0,4,7)的值不相符，则判定其为错误密钥排除。检测完还有(Nk)2×2-96个候选密钥。若此时仍有多个候选密钥，则通过加密验证排除剩余的错误密钥，直至得到正确密钥。

4.2 复杂度分析

主密钥恢复阶段：由AES-128的密钥生成算法，由k1计 算出k9需要8次查表。故第1步所需的时间复杂度为(Nk)2×2-96×240×23=(Nk)2×2-53次查表，第2步所需的时间复杂度为(Nk)2×2-64×28×23=(Nk)2×2-53次查表；第3步所需的时间复杂度为(Nk)2×2-64×28×23=(Nk)2×2-53次查表，第4步所需的时间复杂度为(Nk)2×2-80×28×23=(Nk)2×2-69次查表，若最后仍有候选密钥需加密验证，则需要(Nk)2×2-96次8轮AES加密验证。由文献知，一轮AES加密约为20次查表。主密钥恢复阶段所需的时间复杂度为4步所需时间总和，故主密钥恢复阶段时间复杂度为Tmk=3×(Nk)2×2-53+20×(Nk)2×2-96次查表。存储复杂度最大的在第2 步 ， 需 要(Nk)2×2-64×(22×8)=(Nk)2×2-56.54bit。

综上，本文攻击方案的数据复杂度为 2n+64；存储复杂度为 2113b i t；时间复杂度为Ttotal=Td+Tsk+Tmk。本文取n=58.10 ，可得Td=2128.10次查表，Tsk=2117.10次查表，Nk=287.26，Tmk=2123.10次 查 表， 则Ttotal=Td+Tsk+Tmk=2128.14次查表。故本文攻击方案所需的数据复杂度为 2122.10个 选择明文，存储复杂度为2113bit，时间复杂度为 2128.14/(20×8)≈2120.82次8轮AES加密。本文的攻击方案改进了时间、数据、存储3项复杂度，表4给出了与TweAES算法相关的攻击结果。

表4 TweAES的攻击结果

5 结束语

本文提出了对8轮TweAES算法相关调柄的多重不可能差分攻击。首先，本文利用两类不可能差分区分器，构造了两条攻击路径，每条攻击路径需要攻击16 Byte子密钥。值得注意的是，两条攻击路径有相同的明文结构和14 Byte的公共子密钥，攻击者可以利用同一个明文结构下的有效明密文对，筛选两次子密钥，且因为有大量的公共子密钥，可以提高攻击方案对子密钥筛选的效率。其次，本文利用密钥生成算法的不完全性，有针对性地设置子密钥字节位置，利用子密钥之间的相关性，提高主密钥恢复效率，从而改进整体攻击方案的结果。本文的攻击方案在时间、数据、存储3项复杂度结果上均有所改进，所需的数据复杂复杂为 2122.10个选择明文，时间复杂度为2120.82次8轮AES加密，存储复杂度为2113bit。