Impossible Differential Cryptanalysis of Eight-Sided Fortress Based on Mixed Integer Linear Programming

1.   引言

近年来，伴随无线传感器网络以及射频识别技术的发展和广泛应用，需要轻量级分组密码对资源受限的设备进行数据加密。这类算法具有效率高、功耗低、占用资源少等优点，且易于在软硬件上实现。目前提出了许多轻量级分组密码算法^[1-5]，比较经典的算法有PRESENT, LBlock, WARP等。

ESF算法是2013年Liu等人^[6]基于LBlock改进的轻量级分组密码算法，适用于传感器网络等资源有限的环境。该算法置换层采用了PRESENT中比特置换的设计思想，在提高软硬件实现效率的同时，使得硬件面积相比LBlock减少20个等效行。针对ESF算法的安全性分析主要是不可能差分密码分析^[7,8]，该分析的思想来源于差分密码分析，利用中间相错^[9]的原理推导出概率为零的差分路径，从而排除错误密钥。当所有错误密钥均被排除时，攻击者就可确定正确密钥。近些年，针对ESF算法的分析结果较多。2013年，刘宣等人^[10]首次给出了ESF算法的8轮不可能差分区分器，在此区分器基础上，通过前面加2轮后面加1轮的方法，实现了对该算法的11轮攻击；2016年，陈玉磊等人采用文献[11]中的区分器，通过向前添加1轮，向后添加2轮的扩展方式实现了相同轮数的攻击，与文献[10]相比，时间复杂度和数据复杂度均有效降低；2017年，高红杰等人^[12]同样采用文献[10]中的区分器，通过向前向后各添加2轮的扩展方式，实现了对ESF算法12轮攻击，与文献[11]相比，攻击轮数提高了一轮，数据复杂度仍保持不变；2018年，谢敏等人^[13]首次对ESF进行了相关密钥不可能差分分析，结合算法特点构造了两条10轮相关密钥不可能差分路径，对ESF分别进行了13轮和14轮不可能差分分析；2019年，李明明等人^[14]基于8轮截断不可能差分区分器，对ESF进行了13轮不可能差分分析，与文献[10-12]相比，实现了更多轮数的攻击；2021年，Li等人^[15]利用自动化搜索方法，对ESF算法进行了基于比特可分性质的积分分析，给出了ESF算法9轮积分区分器的自动搜索方法；同年，Wu等人^[16]同样采用自动化搜索方法搜索到9轮不可能差分区分器，并对其进行验证，且从中选取一条区分器，通过向前向后各添加3轮的扩展方式实现了15轮攻击，相比现有结果，攻击轮数明显提高。

受文献[17]的启发，本文的主要贡献包括两个方面：

(1) 利用ESF算法的结构特性，研究得到了$ S $盒的差分传播规律，构建了基于MILP的ESF差分搜索模型，并利用中间相遇的原理，得到了 ESF算法轮数更长的不可能差分区分器。

(2) 基于9轮不可能差分区分器，通过向前添加2轮和向后添加4轮的扩展方式，给出了15轮的扩展路径，并成功实现了15轮单密钥不可能差分攻击。攻击过程的数据复杂度和时间复杂度分别为$ {2^{60.16}} $和 $ {2^{67.44}} $。与文献[16]相比，数据复杂度和时间复杂度均明显降低。

本文第2节简要描述ESF算法；第3节给出ESF算法基于MILP的有效差分路径的搜索算法；第4节给出ESF算法的不可能差分分析；第5节总结全文。

2.   算法描述

为了便于算法描述，下面给出符号说明：

$ X$: 64 bit明文

$ Y $: 64 bit密文

$ {L_i} $: 第$ i $轮输出的左 32 bit

$ {R_i}$: 第$ i $轮输出的右 32 bit

$ K$: 80 bit的主密钥

$ {K_i}$: 第$ i $轮的 32 bit子密钥

$ {K_{i,j}}$: $ {K_i} $的第$ j $个半Byte

$ K_{i,j}^h$: $ {K_{i,j}} $的第$ h $bit

$ {S_i}$: $ 4 \times 4 $的第$ i $个$ S $盒

$ P$: 比特置换

$ {\left[ i \right]_2}$: 常数$ i $的二进制表示

2.1   算法加密过程

ESF是一种轻量级分组密码算法，整体结构采用LBlock的设计准则和 PRESENT 线性层按比特置换的思想，以实现更快的扩散。ESF算法采用广义Feistel结构，算法的分组长度为64 bit，密钥长度为80 bit，迭代轮数为32轮。一轮算法加密流程如图1所示。

图  1  ESF 算法结构

下载: 全尺寸图片 幻灯片

加密流程如下：

(1) 输入 64 bit的明文

(2) 当 $ i = 1,2, \cdots ,31 $时，

(3) 当 $ i = 32 $时，

(4) 输出密文

ESF算法的轮函数为SPN结构，如图2所示，由混淆层和置换层构成，其中混淆层是一个$ 4 \times 4 $的非线性替换，由8个并行的$ S $盒构成，$ S $盒如表1所示；置换$ P $将32 bit的$ {b_{31}}||{b_{30}}|| \cdots ||{b_0} $映射为${c_{31}} ||{c_{30}}|| \cdots ||{c_0}$，即

图  2  ESF 算法轮函数

下载: 全尺寸图片 幻灯片

表  1  ESF的S盒

	$ \boldsymbol{x} $
	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
$ {S_0} $	3	8	f	1	a	6	5	b	e	d	4	2	7	0	9	c
$ {S_1} $	f	c	2	7	9	0	5	a	1	b	e	8	6	d	3	4
$ {S_2} $	8	6	7	9	3	c	a	f	d	1	e	4	0	b	5	2
$ {S_3} $	0	f	b	8	c	9	6	3	d	1	2	4	a	7	5	e
$ {S_4} $	1	f	8	3	c	0	b	6	2	5	4	a	9	e	7	d
$ {S_5} $	f	5	2	b	4	a	9	c	0	3	e	8	d	6	7	1
$ {S_6} $	7	2	c	5	8	4	6	b	e	9	1	f	d	3	a	0
$ {S_7} $	1	d	f	0	e	8	2	b	7	4	c	a	9	3	5	6

下载: 导出CSV 

| 显示表格

2.2   密钥扩展算法

ESF算法主密钥长度为80 bit，经过更新，每轮产生32 bit的轮子密钥。首先将$ K = ({k_{79}}{k_{78}} \cdots {k_1}{k_0}) $存储在寄存器中，取最左端的32 bit密钥作为$ {K_1} $，对于$ i = 1,2, \cdots ,31 $轮密钥更新如下：

(1) $ K < < < 13{\text{ ;}} $

(2) $ {\text{[}}{k_{79}}{k_{78}}{k_{77}}{k_{76}}{\text{] = }}{S_0}{\text{[}}{k_{79}}{k_{78}}{k_{77}}{k_{76}}{\text{]}}, $

　 $ {\text{[}}{k_{75}}{k_{74}}{k_{73}}{k_{72}}{\text{] = }}{S_0}{\text{[}}{k_{75}}{k_{74}}{k_{73}}{k_{72}}{\text{]}} $,

　 $ {\text{[}}{k_{47}}{k_{46}}{k_{45}}{k_{44}}{k_{43}}{\text{] = [}}{k_{47}}{k_{46}}{k_{45}}{k_{44}}{k_{43}}{\text{]}} \oplus {[i]_2} $;

(3) 取最左端的32 bit作为轮密钥$ {K_{i + 1}} $。

3.   基于MILP的有效差分路径搜索

3.1   ESF算法$ S $盒的差分传播特性

定义1　($ S $盒差分分布表^[17]) 设$ m,n \in \mathbb{N} $，从$ F_2^m $到$ F_2^n $的非线性映射(称$ S $盒)记为$ S:F_2^m \to F_2^n $，给定$ \alpha \in F_2^m,\beta \in F_2^n $，定义

其中 $ {N_S}(\alpha ,\beta ) $表示第$ \alpha $行第$ \beta $ 列的取值。由式(6)可构造ESF算法$ S $盒的差分分布表(此处以$ {S_0} $为例)，如表2所示。

表  2  ESF 的S₀盒差分分布表

	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
0	16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	2	0	2	2	2	0	0	0	2	2	0	4	0
2	0	0	0	0	0	0	0	0	0	2	2	0	4	2	2	4
3	0	2	2	2	0	0	0	2	0	4	0	2	2	0	0	0
4	0	0	0	0	0	0	0	0	0	4	4	0	0	4	4	0
5	0	0	2	0	4	2	0	0	2	0	2	2	0	0	2	0
6	0	2	2	4	0	2	2	4	0	0	0	0	0	0	0	0
7	0	0	2	0	4	2	0	0	2	2	0	2	0	2	0	0
8	0	0	0	2	0	2	2	2	0	0	0	2	2	4	0	0
9	0	2	2	0	0	2	2	0	0	2	2	0	0	2	2	0
a	0	2	2	2	0	0	0	2	0	0	4	2	2	0	0	0
b	0	2	2	0	0	2	2	0	0	0	0	0	4	0	0	4
c	0	2	0	0	4	0	2	0	2	2	0	2	0	2	0	0
d	0	0	0	4	0	0	0	4	4	0	0	0	0	0	0	4
e	0	2	0	0	4	0	2	0	2	0	2	2	0	0	2	0
f	0	2	2	0	0	2	2	0	4	0	0	0	0	0	0	4

下载: 导出CSV 

| 显示表格

定理1^[18]　若给定$ S $盒的输入差分值，那么对应$ S $盒的输出差分值至少有1 bit的概率为1，且称概率为1的bit为未受干扰比特。

分析表2可知，给定$ {S_0} $盒的输入差分值，其输出差分存在一定的规律。例，当$ \alpha = 0010 $，$ \beta $的取值分别为$ 1001,1010,1100,1101,1110,1111 $，观察发现输出差分的第3 bit取值为1，其余3 bit的取值可为1或0，输出差分可记为$ 1 * * * $ ($ * $ 表示未知比特)。同理，根据ESF算法 8个S盒的差分分布表，给定 S 盒的输入差分值，输出差分值存在的传播特性如表3所示。

表  3  ESF的S盒差分传播特性

$ {S_0} $			$ {S_1} $			$ {S_2} $			$ {S_4} $			$ {S_5} $			$ {S_6} $
$ \alpha $	$ \beta $		$ \alpha $	$ \beta $		$ \alpha $	$ \beta $		$ \alpha $	$ \beta $		$ \alpha $	$ \beta $		$ \alpha $	$ \beta $
0010	$ 1 * * * $		0100	$ * 1 * * $		0010	$ * * * 1 $		0100	$ * * * 1 $		0100	$ * * * 1 $		0010	$ * * 1 * $
0100	$ 1 * * * $		1000	$ * 1 * * $		1000	$ * * * 1 $		1011	$ * * * 1 $		1011	$ * * * 1 $		0100	$ * * 1 * $
0110	$ 0 * * * $		1100	$ * 0 * * $		1010	$ * * * 0 $		1111	$ * * * 0 $		1111	$ * * * 0 $		0110	$ * * 0 * $

下载: 导出CSV 

| 显示表格

输入差分为某些值时，其输出差分存在相应的概率，如表4所示。

表  4  ESF的S盒差分概率传播特性

$ S $	$ {S_0} $	$ {S_6} $
$ \alpha $	$ 1000 $	$ 0001 $
$ \beta $	$ * * * * $	$ * * * * $
$ P $	$\dfrac{1}{8}$	$\dfrac{1}{8}$

下载: 导出CSV 

| 显示表格

3.2   基于MILP的有效差分路径搜索算法

利用逻辑状态模型和凸闭包计算，将3.1节中$ S $盒的差分传播特性用不等式表示，由此来移除不可能差分路径，使得可行域的集合逼近ESF算法的有效差分路径。搜索ESF算法加密方向有效路径见算法1。

算法1　搜索 ESF 算法加密方向的有效差分路径
输入： 64 bit的明文输入差分$ \Delta X $,
输出：加密后的输出差分集合$ {\text{List}}{\text{.}} $
1. $ {\text{set}} = \{ \Delta X\} $；
2. 如果$ {\text{set}} $中包含部分比特已知的差分；
3. for $ \Delta X $ in $ {\text{set}} $
2. 　$ {\text{List}}{\text{.append(}}\Delta X{\text{)}} $；
4. 　$ \Delta {x_0} - \Delta {x_1} - \Delta {x_2} + \Delta {x_3} - \Delta {y_0} + 2 \ge 0 $； #当$ {\alpha _0} = 0110, $ $ {\beta _0} = 0 * * * * $时的不等式约束，对于其他$ S $盒有类似性质
5.　$\Delta {r_1}{\text{ + } }\Delta { {\text{k} }_1} + \Delta {m_1} - 2d \ge 0,{{ d} } \ge \varDelta {r_1},{{ d} } \ge \varDelta { {\text{k} }_1},{{ d} } \ge \varDelta {m_1},{\text{ } }\varDelta {r_1}{\text{ + } }\varDelta { {\text{k} }_1} + \varDelta {m_1} \le 2$； #异或的约束条件 　6. 　$\displaystyle\sum\limits_{i = 0}^3 {\Delta {x_i} - 4A \le 0,} {\text{ } }\displaystyle\sum\limits_{i = 0}^3 {\Delta {x_i} - A \ge 0,} {\text{ 4} }\displaystyle\sum\limits_{i = 0}^3 {\Delta {y_i} - \displaystyle\sum\limits_{i = 0}^3 {\Delta {x_i} \ge 0,} {\text{ } } } {\text{ 4} }\displaystyle\sum\limits_{i = 0}^3 {\Delta {x_i} - \displaystyle\sum\limits_{i = 0}^3 {\Delta {y_i} \ge 0} {\text{ } } }$； #$ S $盒约束条件
7. 　$ S $盒差分传播特性得到的213个不等式约束条件；
8. 　利用GUROBI求解MILP模型，判断是否存在可行解；
9. 　若存在可行解，则输出$ {\text{set}}{\text{.append}} $(满足上述条件的输出差分$ \Delta Y $)；
10. ${\text{set = set } }-\left( {\Delta X} \right)$，重复执行上述步骤1-步骤9，直到$ {\text{set}} $全为未知的比特；
11. return List.

下载: 导出CSV 

| 显示表格

4.   ESF算法的不可能差分分析

4.1   不可能差分分析

不可能差分分析由差分分析演变而来，近年来成为分组密码安全性分析的常用方法之一。其基本思想是利用概率为0的差分路径来构建区分器，通过该区分器排除导致概率为0的差分出现的候选密钥，将筛选后剩下的密钥作为正确密钥。不可能差分的定义如下。

定义2　对于一个迭代分组密码算法，设明文对$ (X,{X^*}) $的差分值为$ \Delta X = \alpha $，第$ r $轮输出对$ (Y,{Y^*}) $的差分值为 $ \Delta Y = \beta $，若$P(\Delta Y = \beta | \Delta X = \alpha ) = 0$，则称$ (\alpha \nrightarrow \beta ) $为一条 $ r $轮不可能差分。

基于一条$ r - 1 $轮不可能差分区分器$ (\alpha \nrightarrow \beta ) $，$ r $轮不可能差分分析流程如下：

(1) 选择明文对$ (X,{X^*}) $满足输入差分$ \alpha $，加密得到相应的密文对$ (Y,{Y^*}) $；

(2) 猜测第$ r $轮的轮密钥$ {K_r} $，解密密文对，得到相应的中间值$ (D,{D^*}) $，判断$ D \oplus {D^*} = \beta $是否成立。若成立，则对应的猜测值为错误密钥。

(3) 重复以上步骤，直到密钥唯一确定。

假设通过上述攻击可以得到$ \left| K \right| $ bit密钥，且每个明密文对可以淘汰$ {2^{ - t}} $的密钥量，要保证正确密钥被唯一确定，所需明密文对$ n $必须满足

4.2   ESF算法的不可能差分攻击

基于3.2节中的算法1，从加解密方向各找一条概率为1的差分路径，利用中间相遇的思想，将其拼接并筛选出一条概率为0的最优差分路径，搜索轮数最长的不可能差分区分器流程见算法2。将此思想应用于不可能差分分析中，可获得轮数更长的不可能差分区分器。

算法2 寻找最长不可能差分区分器轮数
输入： 加密后的差分路径集合$ {\text{E}}{\text{.List}} $, 解密后的差分路径集合 　　　　 $ {\text{D}}{\text{.List}} $
输出：输出最长不可能差分区分器轮数
1. $ r = 0 $；
2. for $ i $ in range len($ {\text{E}}{\text{.List}} $)
3. 　for $ j $ in range len($ {\text{D}}{\text{.List}} $)
4. 　　if ${\text{E} }{{.{\rm{List}}[i]} } \ne {\text{D} }{{.{\rm{List}}[j]} }$；
5. 　　　if $ r > i + j $
6. 　　　　$ r = r $；
7. 　　　else
8. 　　　　$ r = i + j $；
9. return $ r. $

下载: 导出CSV 

| 显示表格

ESF算法的分组长度为64 bit，遍历所有可能差分的复杂度过高，故只对汉明重量为1的输入/输出差分进行搜索。基于算法2，搜索并选取其中一条9区分器$(0100{\text{ 0000 0000 0000}}) \nrightarrow (1000\; 0000 \; 0000 \; 0000)$，在此区分器基础上通过向前扩展2轮向后扩展4轮实现了对ESF算法进行15轮不可能差分攻击。具体路径如图3 所示，其中“$ * $”取任意值。

图  3  ESF的15轮不可能差分攻击

下载: 全尺寸图片 幻灯片

定理2　利用9轮不可能差分区分器对ESF算法进行15轮不可能差分分析，攻击过程明文量为$ 2^{60.16} $，时间复杂度为$ 2^{67.44} $。

依据 4.1 节中的攻击原理，不可能差分攻击过程如下。

(1) 选择明文结构：输入差分选择满足如式(8)形式的明文对

该结构由$ 2^{20} $个明文生成，共有 $ 2^{20} \times 2^{20} \times 1 / 2=2^{30} $个明文对。若选择$ 2^{n} $个明文结构，则构成$ 2^{n+39} $个明密文对。

(2) 密文筛选：输出差分选择满足如式 (9) 的密文对

经此步骤过滤大约剩余$ {2^{n + 39}} \times {2^{ - 16}}{\text{ = }}{2^{n + 23}} $个数据对。

(3) 猜测密钥：

(a) 猜测$ {K_{15}} $，共32 bit。在$ K $中对应的位置为${K_{57 - 54}},{K_{53 - 50}},{K_{49 - 46}},{K_{45 - 42}} $, ${K_{41 - 38}},{K_{37 - 34}}, {K_{33 - 30}},{K_{29 - 26}}$。对剩余密文对进行解密运算，由$ {L_{14}} < < < 7 = P \cdot S({R_{14}} \oplus {K_{15}}) \oplus {R_{15}} $可知，排除不满足$\Delta {L_{14}} = (0000{\text{ }}000 * {\text{ }}0000{\text{ }}000 * {\text{ }}0000{\text{ }}000 * {\text{ }}0000{\text{ }}000 * )$的数据对，则剩余数据对个数为${2^{n + 23}} \times {2^{ - 28}} = {2^{n - 5}}$。此步骤的时间复杂度为

(b) 猜测$ {K_{14,6}},{K_{14,4}},{K_{14,2}},{K_{14,0}} $。它们在$ K $中对应的位置为$ {K_{66 - 63}},{K_{58 - 55}},{K_{48 - 45}},{K_{40 - 37}} $，由于 $ {K_{57 - 55}} $, $ {K_{48 - 45}},{K_{40 - 37}} $在(a)中已被猜测，故只需猜测剩余5 bit。对剩余数据对进行一轮解密运算，依次验证式(10)

是否成立，经排除不满足式(10)的数据对后，剩余数据对个数为$ {2^{n - 5}} \times {2^{ - 16}} = {2^{n - 21}} $。此步骤的时间复杂度为

(c) 猜测$ {K_{13,0}} $。$ {K_{13,0}} $由(a)可得，只需验证式(11)即可

经排除不满足式(11)的数据对后，剩余数据对个数为$ {2^{n - 21}} \times {2^{ - {\text{3}}}} = {2^{n - 24}} $。此步骤的时间复杂度为

(d) 猜测$ {K_{1,7}},{K_{1,5}},{K_{1,3}},{K_{1,1}} $。它们在$ K $中对应的位置为$ {K_{79 - 76}},{K_{71 - 78}},{K_{63 - 60}},{K_{55 - 52}} $，由于$ {K_{55 - 52}} $在(a)中已被猜测，只需猜测剩余12 bit。计算${L_0} < < < 7 = P \cdot S({R_0} \oplus {K_1}) \oplus {R_1}$，保留满足$\Delta {L_0} = (0 * 0 * {\text{ }}0 * 0 * {\text{ }}0 * 0 *$$ 0 * 1 * {\text{ }}0 * 0 * {\text{ }}0 * 0 * {\text{ }}0 * 0 * {\text{ }}0 * 0 * ) $ 的数据对。过滤后剩余数据对个数为 ${2^{n - 24}} \times {2^{ - 4}} = {2^{n - 28}}$。此步骤的时间复杂度为

(e) 猜测 $ {K_{2,6}} $。排除不满足$ {S_6}({R_{1,6}} \oplus {K_{2,6}}) \oplus $$ {S_6} ({R_{1,6}} \oplus \Delta {R_{1,6}} \oplus {K_{2,6}} \oplus \Delta {K_{2,6}}) = \Delta R_{2,7}^2||\Delta R_{2,5}^2||\Delta R_{2,3}^2||\Delta R_{2,1}^2 $ 的数据对，经这一步排除，剩余数据对的个数为 $ {2^{n - 28}} \times {2^{ - {\text{3}}}}{\text{ = }}{2^{n - {\text{31}}}} $。此步骤的时间复杂度为

上述的15轮不可能差分攻击过程中，共猜测得到53 bit子密钥，经过分析$ {2^{n - 31}} $个数据对后，错误密钥还剩 $ {2}^{53}\times (1-{2}^{-4}{)}^{{2}^{n-31}} $个，而当 $ n \approx 40.16 $ 时，有 $ ({2}^{53}-1)\times (1-{2}^{-4}{)}^{{2}^{n-31}} < 1 $ 成立，此时我们认为已将错误密钥全部淘汰。

攻击过程的数据复杂度为

攻击过程的时间复杂度为

4.3   结果对比

对ESF算法分析的常用方法是不可能差分分析。本文根据ESF算法的结构特性和$ S $盒的差分传播特性，实现了对ESF的15轮不可能差分攻击。与文献[16]相比，在攻击轮数相同的条件下，时间复杂度和数据复杂度均得到有效降低。对比结果如表5所示。

表  5  ESF 分析方法结果对比

攻击轮数	分析方法	时间复杂度	数据复杂度	文献
11	不可能差分分析	$ {2^{75.5}} $	$ {2^{59}} $	文献[10]
11	不可能差分分析	$ {2^{32}} $	$ {2^{53}} $	文献[11]
12	不可能差分分析	$ {2^{60.45}} $	$ {2^{53}} $	文献[12]
13	截断不可能差分分析	$ {2^{61.99}} $	$ {2^{77.39}} $	文献[14]
14	相关密钥不可能差分分析	$ {2^{43.95}} $	$ {2^{62}} $	文献[13]
15	不可能差分分析	$ {2^{70.02}} $	$ {2^{64.3}} $	文献[16]
15	不可能差分分析	$ {2^{67.44}} $	$ {2^{60.16}} $	本文

下载: 导出CSV 

| 显示表格

5.   结束语

本文利用ESF算法的$ S $盒差分传播特性，基于中间相遇思想，构建基于MILP的自动化搜索模型，搜索ESF的不可能差分区分器。选取了其中一条区分器，利用$ S $盒的输入输出差分特征，分别向前添加2轮向后添加4轮，对ESF算法进行15轮不可能差分攻击，且攻击的时间复杂度低于穷举攻击的复杂度，与现有结果相比，攻击效果也有较大的提升。在后续工作中，将考虑将多种分析方法结合，并优化搜索算法，找到更好的不可能差分区分器，进一步提高不可能差分攻击的轮数。