Improved Multiple Signal Classification Algorithm for Direction of Arrival Estimation Based on Covariance Matrix of Cross-correlation

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轮不可能差分攻击，且攻击的时间复杂度低于穷举攻击的复杂度，与现有结果相比，攻击效果也有较大的提升。在后续工作中，将考虑将多种分析方法结合，并优化搜索算法，找到更好的不可能差分区分器，进一步提高不可能差分攻击的轮数。