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 \times 4$矩阵，主密钥长度设置为128 bit。由Byte替换${\text{SB}}$、行移位变换${\text{SR}}$、列混合变换${\text{MC}}$、轮密钥加${\text{AK}}$、调柄加${\text{AT}}$这5种变换构成。其中前4种变换与AES-128完全一致，而调柄加变换每隔两轮注入一次调柄值，5种变换简述如下：

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

(2)行移位变换${\text{SR}}$：由行号值对每行循环左移，即第$i$行循环左移$i$ Byte($i = 0,1,2,3$)。

(3)列混合变换${\text{MC}}$：由AES算法的左乘矩阵，对状态的每列进行乘法运算。

(4)轮密钥加${\text{AK}}$：每轮输入值与对应子密钥异或加，本文记${k_0}$为主密钥，其余子密钥是由AES-128的密钥扩展方案生成${k_1},{k_2}, \cdots ,{k_{10}}$共10个128 bit子密钥。

(5)调柄加${\text{AT}}$：4 bit主调柄为$({t_0},{t_1},{t_2},{t_3})$，然后通过简单的线性变换将其扩展为8 bit的子调柄，记$t = {t_0} \oplus {t_1} \oplus {t_2} \oplus {t_3}$，则扩展的8 bit调柄为

记扩展的8 bit调柄为$T = ({t_0},{t_1},{t_2},{t_3},{t_4},{t_5},{t_6}, {t_7})$，将第$i$ bit异或加到前两行第$i$ Byte的最低比特位，字节位置如图1所示。子调柄加每隔两轮操作一次，即在第2, 4, 6, 8, 10轮注入扩展的8 bit子调柄。

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

下载: 全尺寸图片 幻灯片

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

2.2   符号说明

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

表 1  符号说明

符号	意义
$P$	明文
$C$	密文
$x_{i,(p,\cdots,r)}^{{\rm{I/SB/SR/MC/AK/AT}}}$	第$i$轮输入/字节替换/行移位变换/混合变换/轮密钥加/调柄加后的第$(p, \cdots ,r)$ Byte值
$\Delta x$	$x$的差分值
${k_{i,(p,\cdots,r)} }$	第$i$轮子密钥${k_i}$的第$(p, \cdots ,r)$ Byte值
$a{\not \to _{i - {\rm{round}}} }b$	差分$a$经$i$轮加密后不能得到差分$b$

下载: 导出CSV 

| 显示表格

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

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

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

类别	序号	区分器的输入差分(具体差分值)	区分器的输入差分(截断差分值)
一	1	(a,a,0,0,0,0,0,0,0,0,0,0,a,a,0,0)	(0,0,0,0,0,0,0,0,0,0,0,0,*,0,0,0)
	2		(0,0,0,0,0,0,0,0,0,0,0,0,0,*,0,0)
	3		(0,0,0,0,0,0,0,0,0,0,0,0,0,0,*,0)
	4		(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,*)
二	5		(*,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)
	6		(0,*,0,0,0,0,0,0,0,0,0,0,0,0,0,0)
	7		(0,0,*,0,0,0,0,0,0,0,0,0,0,0,0,0)
	8		(0,0,0,*,0,0,0,0,0,0,0,0,0,0,0,0)
注：a为8 bit具体值0x01，*为8 bit任意非零值。主调柄差分值为(1001)。

下载: 导出CSV 

| 显示表格

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

下载: 全尺寸图片 幻灯片

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

性质1　在选取的主调柄4 bit差分值为$(1,0, 0,1)$的情况下，对分组密码算法TweAES，可得如下6轮的相关调柄不可能差分区分器：

其中，$(\alpha )$的差分值为0x01，$(*)$为非零截断差分，输入差分的位置为$\Delta x_2^{{\text{AK}}}$，输出差分的位置为$\Delta x_8^{{\text{SR}}}$，差分传递过程如图2所示。

证明　首先，主调柄4 bit差分值为$(1,0,0,1)$，经过调柄扩展变换可得8 bit子调柄的差分值为$(1,0,0,1,1,0,0,1)$，将其异或加至对应字节的最低比特位，可得调柄加操作下注入的子调柄差分值为$(\alpha ,\alpha ,0,0,0,0,0,0,0,0,0,0,\alpha ,\alpha ,0,0)$。

其次，区分器输入差分$\Delta x_2^{{\text{AK}}}$在第$(0,1,12,13)$ Byte位置上差分值为$(\alpha )$，其余字节位置上差分值为0。$\Delta x_2^{{\text{AK}}}$与子调柄差分值异或加后，整体16 Byte差分值均为0。从第3轮开始，两轮加密的过程中差分值均为0，直到第4轮输出注入子调柄，使得$\Delta x_4^{{\text{AT}}}$在第$(0, 1, 12, 13)$ Byte位置上差分值为0x01，其余字节位置上差分值为0。经过第5轮${\text{SB}}$, ${\text{SR}}$变换后，可得差分$\Delta x_5^{{\text{SR}}}$在第$(0,9,12,13)$ Byte位置上差分值非零，经过列混合变换，可得差分$\Delta x_5^{{\text{MC}}}$在第2列上差分值均为0。

再次，区分器输出差分$\Delta x_8^{{\text{SR}}}$在第$12$ Byte位置上差分值为非零，其余字节位置上差分值为0。经过第8轮${\text{S}}{{\text{R}}^{{{ - 1}}}}$, ${\text{S}}{{\text{B}}^{{{ - 1}}}}$变换和第7轮脱密变换后，可得差分$\Delta x_6^{{\text{AT}}}$在第$(1,7,11,12)$ Byte位置上差分值为非零，其余字节位置上差分值为0。经过${\text{A}}{{\text{T}}^{{{ - 1}}}}$变换后，$\Delta x_6^{{\text{MC}}}$在第2, 3列中，分别只有第$6$ Byte，第$11$字节差分值非零，第2, 3列中的其余3 Byte差分为零。经过第6轮${\text{M}}{{\text{C}}^{{{ - 1}}}}$, ${\text{S}}{{\text{R}}^{{{ - 1}}}}$, ${\text{S}}{{\text{B}}^{{{ - 1}}}}$变换后，可得差分$\Delta x_5^{{\text{MC}}}$在第2列的第$(4,7)$Byte差分非零，这与之前差分$\Delta x_5^{{\text{MC}}}$在第2列上差分值均为0矛盾，故构造出不可能差分区分器。

综上

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

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

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

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

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

下载: 全尺寸图片 幻灯片

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

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

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

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

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

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

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

预处理阶段：

表$\varLambda$：对TweAES的${\text{S}}$盒，在给定非零输入差${\varDelta _{{\text{in}}}}$和非零输出差${\varDelta _{{\text{out}}}}$时，方程$S(x) \oplus S(x \oplus {\varDelta _{{\text{in}}}}) = {\varDelta _{{\text{out}}}}$平均能求出一个解，构造表$\varLambda$，索引为${({2^8} - 1)^2}$个非零差分$({\varDelta _{{\text{in}}}},{\varDelta _{{\text{out}}}})$，每个$({\varDelta _{{\text{in}}}},{\varDelta _{{\text{out}}}})$存储对应的一个输入值$x$。

表${{H}_1}$：第2轮子调柄差分经${\text{M}}{{\text{C}}^{{{ - 1}}}}$, ${\text{S}}{{\text{R}}^{{{ - 1}}}}$变换后，得到的一个具体差分值$\Delta x_2^{{\text{SB}}}$，故这个差分值可以得到区分器的输入差分，将其存入表${{H}_1}$。

表${{H}_2}$：由第1类区分器的4种截断式输出差分，经${\text{MC}}$, ${\text{AT}}$变换后，得到的${2^{10}}$个具体差分值$\Delta x_8^{{\text{AT}}}$，故这${2^{10}}$个差分值可以得到第1类区分器的输出差分，将这${2^{10}}$个差分$\Delta x_8^{{\text{AT}}}$存入表${{H}_2}$。

表${{H}_3}$：由第2类区分器的4种截断式输出差分，经${\text{MC}}$,${\text{AT}}$变换后，得到的${2^{10}}$个具体差分值$\Delta x_8^{{\text{AT}}}$，故这${2^{10}}$个差分值可以得到第3类区分器的输出差分，将这${2^{10}}$个差分$\Delta x_8^{{\text{AT}}}$存入表${{H}_3}$。

表$G_{{K}}^1$：以8 Byte密钥${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$为索引，构造${2^{64}}$个表$G_{{{Ki}}}^1$，其中${K_i}$为8 Byte密钥${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$具体值。每个表$G_{{{Ki}}}^1$有${2^{48}}$ bit空间，以这${2^{48}}$个对应子密钥${k_{9, (0,7,9,10,12,13)}}$具体值，初始化时这${2^{48}}$个值全为0。这${2^{64}}$个表$G_{{{Ki}}}^1$构成大表$G_{{K}}^1$，用来记录第1条攻击路径筛选出的错误密钥。

表$G_{{K}}^2$：以8 Byte密钥${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$为索引，构造${2^{64}}$个表$G_{{{Ki}}}^2$，其中${K_i}$为8Byte密钥${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$具体值。每个表$G_{{{Ki}}}^2$有${2^{48}}$ bit空间，以这${2^{48}}$个对应子密钥${k_{9, (0,3,6,9,12,13)}}$具体值，初始化时这${2^{48}}$个值全为0。这${2^{64}}$个表$G_{{{Ki}}}^2$构成大表$G_{{K}}^2$，用来记录第2条攻击路径筛选出的错误密钥。

注意，表$\varLambda$可以用来并行计算出S层的输入输出具体值。在子密钥筛选阶段，表${{H}_1}$, ${{H}_2}$和${{H}_3}$可以用来直接查表求解子密钥，将计算出的错误子密钥标记为1用表$G_{{K}}^1$和$G_{{K}}^2$记录，故不用再反复进行加脱密计算，从而改进子密钥筛选阶段的时间复杂度。

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

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

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

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

子密钥筛选阶段：对每个明文结构用4步筛选错误子密钥，将一个明文结构中的全部${2^{n + 48}}$对有效明密对检测完毕后，再用下一个明文结构的有效明密文对检测，错误的子密钥记录在表$G_{{K}}^1$和$G_{{K}}^2$中。第1～2步利用第1条攻击路径，排除部分的错误子密钥$({k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}, {k_{9, (0,7,9,10,12,13)}})$；第3～4步利用第2条攻击路径，排除部分错误的子密钥$({k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}, {k_{9, (0,3,6,9,12,13)}})$。检测完全部的明密对后，由表$G_{{K}}^1$和$G_{{K}}^2$中的候选密钥，在主密钥恢复阶段得到主密钥。子密钥筛选阶段的具体步骤如下：

(1) 利用第1条攻击路径，求解${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$。对于表$\varOmega$中符合第1条攻击路径的明密文对，以明文对差分为${\varDelta _{{\text{in}}}}$，表${{H}_1}$中的差分为${\varDelta _{{\text{out}}}}$，查表$\varLambda$可得$x_1^{{\text{AK}}}$，计算$x_1^{{\text{AK}}} \oplus P$可得密钥${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$，以密钥${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$为索引查找表$G_{{{Ki}}}^1$。

(2) 对当前的明文对，求解${k_{9, (0,7,9,10,12,13)}}$。由当前明文对对应的密文对，对密文对进行${\text{S}}{{\text{R}}^{{{ - 1}}}}$变换后，得到的差分为${\varDelta _{{\text{out}}}}$，以表${{H}_2}$中的${2^{10}}$个差分为${\varDelta _{{\text{in}}}}$，查表$\varLambda$可得$x_9^{{\text{SB}}}$，计算${\text{SR}}(x_9^{{\text{SB}}}) \oplus C$可得${2^{10}}$个密钥${k_{9, (0,7,9,10,12,13)}}$，判断其均为错误子密钥，将表$G_{k1, (0,1,5{\text{,}}6,10,11,12,15)}^1$中这${2^{10}}$个错误子密钥${k_{9, (0,7,9,10,12,13)}}$对应的索引地址上的值改为1。

(3) 利用第2条攻击路径，求解${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$。对于表$\varOmega$中符合第2条攻击路径的明密文对，以明文对差分为${\varDelta _{{\text{in}}}}$，表${{H}_1}$中的差分为${\varDelta _{{\text{out}}}}$，查表$\varLambda$可得$x_1^{{\text{AK}}}$，计算$x_1^{{\text{AK}}} \oplus P$可得密钥${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$，以密钥${k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}$为索引查找表$G_{{{Ki}}}^2$。

(4) 对当前的明文对，求解${k_{9, (0,3,6,9,12,13)}}$。由当前明文对对应的密文对，对密文对进行${\text{S}}{{\text{R}}^{{\text{ - 1}}}}$变换后，得到的差分为${\varDelta _{{\text{out}}}}$，以表${{H}_3}$中的${2^{10}}$个差分为${\varDelta _{{\text{in}}}}$，查表$\varLambda$可得$x_9^{{\text{SB}}}$，计算${\text{SR}}(x_9^{{\text{SB}}}) \oplus C$可得${2^{10}}$个密钥${k_{9, (0,3,6,9,12,13)}}$，判断其均为错误子密钥，将表$G_{k1, (0,1,5{\text{,}}6,10,11,12,15)}^2$中这${2^{10}}$个错误子密钥${k_{9, (0,3,6,9,12,13)}}$对应的索引地址上的值改为1。

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

主密钥恢复阶段：现有两个候选子密钥表$G_{{K}}^1$和$G_{{K}}^2$，其中索引地址上值为0的为候选子密钥，值为1的为错误子密钥，设每个表中有${N_k}$个候选密钥。只有12 Byte公共子密钥值相同时，才可以判定16 Byte$({k_{1, (0,1,5{\text{,}}6,10,11,12,15)}}, {k_{9, (0,3,6,7,9,10,12,13)}})$子密钥为候选密钥，故16 Byte候选密钥有${({N_k})^2} \times {2^{ - 96}}$个。

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

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

密钥字节	关联字节		密钥字节	关联字节		密钥字节	关联字节
4	A16\{0,2,8,10}		8	A16\{0,1,4}		12	A16\{0,1,2,4,5,8,10}
5	A16\{1,3,9,11}		9	A16\{1,2,5}		13	A16\{1,2,3,5,6,9,11}
6	A16\{0,2,8,10}		10	A16\{2,3,6}		14	A16\{0,2,3,6,7,8,10}
7	A16\{1,3,9,11}		11	A16\{0,3,7}		15	A16\{0,1,3,4,7,9,11}
注：密钥字节为第9轮子密钥字节位置，A16代表全部16 Byte，关联字节指与第1轮子密钥字节的关联：如${k_{9, (4)}}$与4 Byte子密钥${k_{1, (0,2,8,10)}}$无关，只需要知道子密钥${k_1}$其余的12 Byte，即可由AES-128的密钥生成算法得到。

下载: 导出CSV 

| 显示表格

(1) 穷举第1轮子密钥中的5 Byte ${k_{1, (3,7,9,13,14)}}$，此时第1轮子密钥只有3 Byte ${k_{1, (2,4,8)}}$未知，由表3知${k_{9, (12)}}$与${k_{1, (2,4,8)}}$无关，则可以由第1轮子密钥计算密钥${k_{9, (12)}}$的值，若与候选密钥${k_{9, (12)}}$的值不相符，则判定其为错误密钥排除。检测完还有${({N_{{k}}})^2} \times {2^{ - 96}} \times {2^{40}} \times {2^{ - 8}} = {({N_{{k}}})^2} \times {2^{ - 64}}$个候选密钥。

(2) 穷举第1轮子密钥中的1 Byte ${k_{1, (4)}}$，此时第1轮子密钥只有2 Byte ${k_{1, (2,8)}}$未知，由表3知${k_{9, (6)}}$与${k_{1, (2,8)}}$无关，则可以由第1轮子密钥计算密钥${k_{9, (6)}}$的值，若与候选密钥${k_{9, (6)}}$的值不相符，则判定其为错误密钥排除。检测完还有${({N_{{k}}})^2} \times {2^{ - 64}} \times {2^8} \times {2^{ - 8}} = {({N_{{k}}})^2} \times {2^{ - 64}}$个候选密钥。

(3) 穷举第1轮子密钥中的1 Byte ${k_{1, (8)}}$，此时第1轮子密钥只有1 Byte ${k_{1, (2)}}$未知，由表3知${k_{9, (9,10,13)}}$与${k_{1, (2)}}$无关，则可以由第1轮子密钥计算密钥${k_{9, (9,10,13)}}$的值，若与候选密钥${k_{9, (9,10,13)}}$的值不相符，则判定其为错误密钥排除。检测完还有${({N_{{k}}})^2} \times {2^{ - 64}} \times {2^8} \times {2^{ - 24}} = {({N_{{k}}})^2} \times {2^{ - 80}}$个候选密钥。

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

4.2   复杂度分析

记本文选取${2^n}$个明文结构，则攻击方案所需要的数据复杂度是${2^{n + 64}}$个选择明文。在一条攻击路径下，一个错误子密钥通过一个有效明密文对的概率是$p = {2^{ - 102}}$，则经过${2^{n + 48}}$个有效明密文对检测后，候选密钥量个数${N_{{k}}} = ({2^{112}} - 1) \times {(1 - p)^{{2^{n + 48}}}}$。各个阶段的复杂度分析如下所示。

预处理阶段：时间复杂度可忽略不计，存储复杂度主要是构造表$G_{{K}}^1$和$G_{{K}}^2$所需的存储空间，一共所需的存储复杂度为$2 \times {2^{64}} \times {2^{48}} = {2^{113}}$ bit。

数据处理阶段：主要为排序算法所需的时间，故数据处理阶段的时间复杂度为${T_{\text{d}}} = {2^n} \times {2^{64}} {\log _2}({2^{64}}) = {2^{n + 70}}$。为降低存储复杂性，本文先用一个明文结构里的全部有效明密对，作用于两条攻击路径，排除错误子密钥。然后释放存储空间，再存储下一个明文结构的明密文，故明密文所需的存储复杂度为${2^{64}} \times 160$ bit。

子密钥筛选阶段：第1步所需的时间复杂度为${2^{n + 48}}$次查表，第2步所需的时间复杂度为${2^{n + 48}} \times {2^{10}} = {2^{n + 58}}$次查表；第3步所需的时间复杂度为${2^{n + 48}}$次查表，第4步所需的时间复杂度为${2^{n + 48}} \times {2^{10}} = {2^{n + 58}}$次查表，故子密钥筛选阶段的时间复杂度为${T_{{\text{sk}}}} = {2^{n + 59}}$次查表。

本文的攻击方案，是以一个有效明密文对检测出错误密钥后，将其记录在对应表$G_{{K}}^1$和$G_{{K}}^2$上，然后释放明密文空间，存储下一个明文结构中的数据，故明密文所需的存储复杂度为${2^{64}} \times 160$，主要的存储复杂度仍是构造表$G_{{K}}^1$和$G_{{K}}^2$，具体为$2 \times {2^{64}} \times {2^{48}} = {2^{113}}$bit。

主密钥恢复阶段：由AES-128的密钥生成算法，由${k_1}$计算出${k_9}$需要8次查表。故第1步所需的时间复杂度为${({N_{{k}}})^2} \times {2^{ - 96}} \times {2^{40}} \times {2^3} = {({N_{{k}}})^2} \times {2^{ - 53}}$次查表，第2步所需的时间复杂度为${({N_{{k}}})^2} \times {2^{ - 64}} \times {2^8} \times {2^3} = {({N_{{k}}})^2} \times {2^{ - 53}}$次查表；第3步所需的时间复杂度为${({N_{{k}}})^2} \times {2^{ - 64}} \times {2^8} \times {2^3} = {({N_{{k}}})^2} \times {2^{ - 53}}$次查表，第4步所需的时间复杂度为${({N_{{k}}})^2} \times {2^{ - 80}} \times {2^8} \times {2^3} = {({N_{{k}}})^2} \times {2^{ - 69}}$次查表，若最后仍有候选密钥需加密验证，则需要${({N_{{k}}})^2} \times {2^{ - 96}}$次8轮AES加密验证。由文献知，一轮AES加密约为20次查表。主密钥恢复阶段所需的时间复杂度为4步所需时间总和，故主密钥恢复阶段时间复杂度为${T_{{\text{mk}}}} = 3 \times {({N_{{k}}})^2} \times {2^{ - 53}} + 20 \times {({N_{{k}}})^2} \times {2^{ - 96}}$次查表。存储复杂度最大的在第2步，需要${({N_{{k}}})^2} \times {2^{ - 64}} \times (22 \times 8) = {({N_{{k}}})^2} \times {2^{ - 56.54}}$bit。

综上，本文攻击方案的数据复杂度为${2^{n + 64}}$；存储复杂度为${2^{113}}$bit；时间复杂度为${T_{{\text{total}}}} = {T_{\text{d}}} + {T_{{\text{sk}}}} + {T_{{\text{mk}}}}$。本文取$n = 58.10$，可得${T_{\text{d}}} = {2^{128.10}}$次查表，${T_{{\text{sk}}}} = {2^{117.10}}$次查表，${N_{{k}}} = {2^{87.26}}$，${T_{{\text{mk}}}} = {2^{{\text{123}}{\text{.10}}}}$次查表，则${T_{{\text{total}}}} = {T_{\text{d}}} + {T_{{\text{sk}}}} + {T_{{\text{mk}}}} = {2^{128.14}}$次查表。故本文攻击方案所需的数据复杂度为${2^{122.10}}$个选择明文，存储复杂度为${2^{113}}$ bit，时间复杂度为${2^{128.14}}/(20 \times 8) \approx {2^{120.82}}$次8轮AES加密。本文的攻击方案改进了时间、数据、存储3项复杂度，表4给出了与TweAES算法相关的攻击结果。

表 4  TweAES的攻击结果

分析方法	轮数	时间复杂度	数据复杂度	存储复杂度	调柄个数	参考文献
截断差分	5	226	25 CP	228.58	2	[1]
积分攻击	6	245	25 KP	–	24	[1]
不可能差分	6	2119	2119 CP	278.17	2	[1]
不可能差分	7	2100	299 CP	270	2	[20]
不可能差分*	8	2127	2127 CP	296	24	[1]
不可能差分	8	2124.36	2124.28 CP	2118.81	2	[20]
不可能差分	8	2120.82	2122.10 CP	2113	2	本文
CP：选择明文　　KP：已知明文　　–：复杂度较小忽略不计 *：由文献[20]修正后，时间复杂度超出穷举攻击，本表列出的为文献[1]中所声称的复杂度。

下载: 导出CSV 

| 显示表格

5.   结束语

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