A Lightweight and Provably Secure Authentication Protocol for Internet of Vehicles Using Physical Unclonable Function

1.   引言

万物联网的需求使得无线传感器、智能卡和RFID标签等受限设备的应用越来越广泛。针对资源受限环境下数据安全和隐私保护问题，兼顾安全和效率的轻量级密码算法的设计和分析成为研究热点。2013年6月，美国国家安全局提出了分别适用于软件和硬件环境的轻量级分组密码算法SIMON和SPECK^[1]。这两种算法一经提出，就受到广泛关注。随后，在CHES 2015上，Yang等人^[2]提出了一种新的轻量级分组密码Simeck算法。Simeck结合了SIMON和SPECK设计上的优点，在软件及硬件方面都有出色的表现。

针对Simeck算法安全性的分析，最初由设计者给出了Simeck算法差分分析和不可能差分分析的结果^[2]。随后，Bagheri^[3]对Simeck算法抗线性攻击的能力进行了评估。2016年，文献[4]针对Simeck48和Simeck64，给出了成功概率为1的差分分析的更好结果。随后，Blondeau等人^[5]给出了更长轮数带概率的差分分析结果。2018年，Zhang等人^[6]给出了Simeck算法零相关线性攻击的结果。对Simeck算法的积分攻击首先由文献[7]提出，Zhang等人^[7]构造了Simeck算法的积分区分器，分别给出了21/21/24轮Simeck32/48/64算法的积分攻击。

积分攻击是一种有效的选择明文攻击。1997年，Daemen等人^[8]提出一种新的分析方法攻击SQUARE算法。2001年，Lucks^[9]提出Saturation攻击，同年，Biryukov等人^[10]提出了Multiset攻击。随后，Knudsen等人^[11]在FSE 2002上提出了积分攻击的思想。积分攻击的原理是加密特定形式的选择明文，再对所得密文求和，通过积分值的不随机性将密码算法与随机置换区分开。积分攻击成功的关键是建立有效的积分区分器，近年来，提出了很多新的自动化算法搜索积分区分器，大大加快了积分区分器的搜索效率，提高了积分攻击的成功率。

本文对Simeck48和Simeck64在积分攻击下的安全性进行研究。首先，在文献[7]给出的Simeck48算法13轮积分区分器的基础上，标记区分器内部比特的状态，利用文献[12]提出的由内向外的扩展方法，向前解密2轮得到Simeck48算法15轮的高阶积分区分器，再根据Simeck算法Feistel的结构特点，在顶部加1轮得到16轮的积分区分器。然后利用该区分器，给出了24轮Simeck48算法的积分攻击。密钥恢复过程中利用等价子密钥技术和密钥扩展算法的性质减少了密钥猜测量，攻击过程结合中间相遇思想和部分和技术，降低了整个攻击算法的计算复杂度。攻击24轮Simeck48算法的时间复杂度为2⁹⁵，数据复杂度为2⁴⁶，存储复杂度为2^82.52。同样地，对于Simeck64算法，构造了20轮高阶积分区分器，部分解密9轮，猜测得到2¹⁰⁴个105 bit等价子密钥，在此基础上穷举23 bit等价子密钥，实现密钥的恢复。攻击29轮Simeck64数据复杂度为2⁶³，时间复杂度为2^127.3，存储复杂度为2^109.02。

本文的结构安排如下：第2节简要介绍Simeck算法，给出密钥扩展算法的性质和安全性分析的结果；第3节给出Simeck48算法积分攻击的具体过程和复杂度计算；第4节给出Simeck64算法积分攻击的新结果；第5节总结全文。

2.   Simeck算法

文中用到的符号说明如表1所示。

表  1  符号说明

符号	说明
Simeck2n(4n)	分组为2n，密钥为4n的Simeck算法
${{L} _i}$	第i轮左半部分输入nbit
${L_i}\left( j \right)$	${{L} _i}$第j bit
${{R} _i}$	第i轮右半部分输入nbit
${R_i}\left( j \right)$	${{R} _i}$第j bit
${K}$	主密钥${K} = ({{K} _3},{{K} _2},{{K} _1},{{K} _0})$
${\rm{r}}{{\rm{k}}_i}$	第i轮nbit的轮子密钥
$\oplus$	异或运算
$\&$,$\odot$	与运算
$< < < r$, $> > > r$	循环左移、右移rbit

下载: 导出CSV 

| 显示表格

2.1   Simeck算法的轮函数

Simeck算法是文献[2]提出的轻量级分组密码，设计思想结合了SIMON和SPECK算法的优点。为了满足不同的应用需求，Simeck算法按照分组长度和密钥长度的不同分为3个版本Simeck2n(4n), n=16, 24, 32，每个版本的Simeck参数如表2所示。

表  2  Simeck算法的参数

算法	分组长度	密钥长度	字长	轮数
Simeck	32	64	16	32
	48	96	24	36
	64	128	32	44

下载: 导出CSV 

| 显示表格

Simeck算法采用Feistel结构，其轮函数与SIMON算法类似，只有与运算，异或和循环移位操作，唯一的区别是循环移位常数不同。轮函数的迭代过程如图1所示，可以表示如式(1)

图  1  Simeck算法的轮函数

下载: 全尺寸图片 幻灯片

其中，${f} ({x} ) = ({x} \odot ({x} < < < 5)) \oplus ({x} < < < 1)$。

2.2   Simeck算法的密钥扩展算法

Simeck2n(4n)的密钥扩展算法借鉴SPECK算法，密钥迭代算法使用线性反馈移位寄存器(LFSR)来产生轮子密钥，初始主密钥K包含4个nbit字$({{K} _3},$${{K} _2},{{K} _1},{{K} _0})$，作为LFSR的初始状态$({{t} _2},{{t} _1},{{t} _0},{\rm{rk} _0})$。为了更新寄存器状态以生成轮子密钥，复用轮函数并使用轮常数${{c} _i}$作为轮密钥。对于$0 \le {i} < {T} - 1$，状态更新过程如式(2)

其中，${c} = {2^n} - 4$, ${({z_j})_i}$是序列${z_j}$的第i bit。Simeck32(64)和Simeck48(96)使用同一个m-序列${z_0}$, Simeck64(128)则使用另外一个m-序列${z_1}$。

对于Simeck2n(4n)，通过研究Simeck密钥扩展算法的规律不难发现，开始4轮的密钥${\rm{rk} _0}$, ${\rm{rk} _1}$, ${\rm{rk} _2}$, ${\rm{rk} _3}$分别等于${{K} _0}$, ${{K} _1}$, ${{K} _2}$, ${{K} _3}$, 且${\rm{r}}{{\rm{k}}_{i + 4}}$只由${\rm{r}}{{\rm{k}}_i}$, ${\rm{r}}{{\rm{k}}_{i + 1}}$和${{c} _i}$决定，与其它轮子密钥无关。基于上述发现，本文给出密钥扩展算法的性质。

性质1　对于Simeck2n(4n)算法，当$0 \le {i} \le$${T} - 4$时，${\rm{r}}{{\rm{k}}_i} = {\rm{r}}{{\rm{k}}_{i + 4}} \oplus f({\rm{r}}{{\rm{k}}_{i + 1}}) \oplus {c_i}$。

证明　当${i} \ge 3$时，联立Simeck密钥扩展算法的式(2)，可得${\rm{r}}{{\rm{k}}_{i{\rm{ + 1}}}} = {t_i} = {\rm{r}}{{\rm{k}}_{i{\rm{ - 3}}}} \oplus f({t_{i - 3}})$$\oplus {c_{i - 3}}$。此外，由式(2)可知，${t_{i - 3}} = {\rm{r}}{{\rm{k}}_{i{\rm{ - 2}}}}$。因此，${\rm{r}}{{\rm{k}}_{i{\rm{ + 1}}}}$可以由${\rm{r}}{{\rm{k}}_{i{\rm{ - 3}}}}$, ${\rm{r}}{{\rm{k}}_{i{\rm{ - 2}}}}$和${{c} _{i - 3}}$唯一表示

即对于任意的$0 \le {i} \le {T} - 4$，都有${\rm{r}}{{\rm{k}}_{i{\rm{ + 4}}}} = {\rm{r}}{{\rm{k}}_i}$$\oplus f({\rm{r}}{{\rm{k}}_{i{\rm{ + 1}}}}) \oplus {c_i}$。等式两边同时异或${\rm{r}}{{\rm{k}}_{i{\rm{ + 4}}}} \oplus {\rm{r}}{{\rm{k}}_i}$，成立

证毕

更进一步，如果需要求解${\rm{r}}{{\rm{k}}_i}$的某一特定比特，则有以下性质。

性质2　对于Simeck2n(4n)算法，当$0 \le {i} \le$${T} - 4$, $0 \le {j} < {n}$时，${\rm{r}}{{\rm{k}}_i}(j) = {\rm{r}}{{\rm{k}}_{i{\rm{ + 4}}}}(j) \oplus ({\rm{r}}{{\rm{k}}_{i{\rm{ + 1}}}}(j)$$\odot {\rm{r}}{{\rm{k}}_{i{\rm{ + 1}}}}((j - 5){\rm{mod}}n)) \oplus {\rm{r}}{{\rm{k}}_{i{\rm{ + 1}}}}((j - 1){\rm{mod}}n) \oplus {c_i}(j)\;$。

根据Simeck密钥扩展算法的性质，可以利用轮数较高的轮子密钥来求解轮数较低的轮子密钥，进而减少攻击过程中密钥的猜测量。

2.3   Simeck算法的安全性分析

Simeck48和Simeck64算法的安全性分析主要集中在差分和线性攻击，不可能差分和零相关攻击，积分攻击等。表3，表4分别列出了对Simeck48, Simeck64主要攻击结果。

表  3  Simeck48的主要攻击结果

算法	攻击方法	攻击轮数	数据复杂度	存储复杂度	时间复杂度	成功概率	参考文献
Simeck48(96)	差分攻击	20	${O} ({2^{46}})$	–	275	1	文献[2]
Simeck48(96)	差分攻击	26	${O} ({2^{47}})$	–	262	1	文献[4]
Simeck48(96)	差分攻击	28	${O} ({2^{46}})$	–	268.3	0.468	文献[5]
Simeck48(96)	线性攻击	19	${O} ({2^{45}})$	–	294	1	文献[3]
Simeck48(96)	不可能差分	24	${O} ({2^{48}})$	${O} ({2^{74}})$	294.7	1	文献[2]
Simeck48(96)	零相关攻击	24	${O} ({2^{48}})$	${O} ({2^{65.06}})$	291.6	1	文献[6]
Simeck48(96)	积分攻击	21	${O} ({2^{34}})$	${O} ({2^{66}})$	295	1	文献[7]
Simeck48(96)	积分攻击	24	${O} ({2^{46}})$	${O} ({2^{82.52}})$	295	1	本文

下载: 导出CSV 

| 显示表格

表  4  Simeck64的主要攻击结果

算法	攻击方法	攻击轮数	数据复杂度	存储复杂度	时间复杂度	成功概率	参考文献
Simeck64(128)	差分攻击	26	${O} ({2^{63}})$	–	2121	1	文献[2]
Simeck64(128)	差分攻击	33	${O} ({2^{63}})$	${O} ({2^{63}})$	296	1	文献[4]
Simeck64(128)	差分攻击	35	${O} ({2^{63}})$	–	2116.3	0.555	文献[5]
Simeck64(128)	线性攻击	27	${O} ({2^{61}})$	–	2120.5	0.477	文献[3]
Simeck64(128)	不可能差分	25	${O} ({2^{64}})$	${O} ({2^{79}})$	2126.6	1	文献[2]
Simeck64(128)	零相关攻击	28	${O} ({2^{64}})$	${O} ({2^{97.67}})$	2123.06	1	文献[6]
Simeck64(128)	积分攻击	24	${O} ({2^{35}})$	${O} ({2^{90.46}})$	2127	1	文献[7]
Simeck64(128)	积分攻击	29	${O} ({2^{63}})$	${O} ({2^{109.02}})$	${2^{127.3}}$	1	本文

下载: 导出CSV 

| 显示表格

3.   24轮Simeck48算法的积分攻击

3.1   Simeck48算法的积分区分器

对于Simeck48算法，文献[7]构造了13轮的积分区分器。具体形式为

其中，${\cal A}$表示4个活动比特，${\rm A}$表示1个活动比特，$C$表示1 bit的固定值，U表示4 bit的任意值，$*$表示1 bit的任意值，B表示1个平衡比特。区分器的输入有34个活动比特，区分器输出状态中右半部分第22个比特${C_R}(22)$是平衡的。

在该积分区分器的基础上，用“1”标记比特活跃，用“0”标记常数比特，得到向量(1000, 1000, 1100, 1110, 1111, 1111, 1001, 1001, 1101, 1111, 1111, 1111)刻画算法的积分状态，利用文献[12]提出高阶积分的扩展方法，向前解密2轮得到15轮的高阶积分区分器，区分器的输入形式为：$({\rm{ACAA}},{\rm{ACAA}},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A})$，有46个活动比特，区分器输出状态中右半部分第22个比特${C_R}(22)$仍是平衡的。

进一步，基于Feistel结构，令$({L_1},{R_1}) =$$({\rm{ACAA}},{\rm{ACAA}},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A})$，可以向前扩展1轮得到16的高阶积分区分器。区分器的输入$({{L} _0},{{R} _0}) = ({{R} _1},{f} ({{R} _1}) \oplus {{L} _1})$，区分器输出状态中右半部分第22个比特${C_R}(22)$是平衡比特。利用该区分器向后加8轮，可以攻击24轮的Simeck48算法。攻击过程中利用等价子密钥技术和密钥扩展算法的性质减少密钥猜测量，结合中间相遇思想和部分和技术，降低攻击的复杂度。

3.2   降低复杂度的技术

(1) 等价子密钥技术

等价子密钥技术是由Isobe等人^[13]在ASIACRYPT 2013首次提出，结合Simeck算法轮函数的具体运算，把第$i$轮的子密钥${\rm{r}}{{\rm{k}}_i}$移动到第$i - 1$轮，其中$i = 17,18, ·\!·\!· ,24$，可以得到等效子密钥${K'\!_i}$。如图2所示，以${\rm{r}}{{\rm{k}}_{23}}$为例。

图  2  等价子密钥技术

下载: 全尺寸图片 幻灯片

图2(a)为Simeck算法本来的结构，为了等效移动${\rm{rk} _{23}}$而不改变算法结构，${\rm{rk} _{23}}$需要异或到相应位置，如图2(b)所示。此外，${\rm{rk} _{23}}$可以进一步转移，与${\rm{rk} _{22}}$异或，如图2(c)所示。因此，${\rm{rk} _{23}}$等价于${K'\!_{23}}$，同样地，可以通过类似的处理进行移动，即${\rm{rk} _{22}} \oplus ({\rm{rk} _{23}} < < < 1)$等价于${K'\!_{22}}$。以此类推，${K'\!_i}$仅与${\rm{r}}{{\rm{k}}_i}$有关，并且这种关系是线性的。在攻击过程中，注意到${K'\!_{16}}$在区分器内部，所以恢复密钥时不需要猜测。

(2) 中间相遇策略

根据积分攻击的原理，对猜测的子密钥，如果$\oplus {{R} _{16}}(22) = 0$，那么猜测值是候选密钥。因此，进行部分解密的目标是找到使得$\oplus {{R} _{16}}(22) = 0$子密钥比特。根据Feistel结构特性式(5)成立

进一步

因此，$\oplus {{R} _{16}}(22) = 0$等价于

这个过程如图3所示。

图  3  中间相遇策略

下载: 全尺寸图片 幻灯片

采用中间相遇策略，独立计算$\oplus (({L'\!_{16}}(22)$$\odot {L'\!_{16}}(17))\oplus {L'\!_{17}}(22))$，将所有猜测的密钥和结果一起存储在表${\rm{T}}{{\rm{b}}_1}$中；独立计算$\oplus {R'\!_{17}}(21)$，并将猜测的密钥和结果存储在另一个表${\rm{T}}{{\rm{b}}_2}$，其中，${L} {'\!_i}$和${R} {'\!_i}$表示使用了等价子密钥技术后的中间状态。最后，通过检查这两个表之间的匹配得到正确的候选密钥，从而降低复杂度。在计算过程中，使用部分和技术来降低时间复杂度。

(3) 部分和技术

部分和技术是Ferguson等人^[14]在FSE 2000提出的，用以改进对Rijndael算法的攻击结果，随后，部分和技术广泛应用于分组密码的积分攻击^[15,16]。下面具体给出利用部分和技术恢复Simeck48密钥的过程。

3.3   Simeck48算法的密钥恢复过程

攻击最终的目标是恢复Simeck48的96-bit密钥，需要独立计算$\oplus (({L} {'\!_{16}}(22) \odot {L} {'\!_{16}}(17)) \oplus {L} {'\!_{17}}(22))$和$\oplus {R} {'\!_{17}}(21)$，分别存储在表${\rm{T}}{{\rm{b}}_1}$和表${\rm{T}}{{\rm{b}}_2}$中。

(1) 计算表${\rm{T}}{{\rm{b}}_1}$的过程

计算$\oplus (({L} {'\!_{16}}(22) \odot {L} {'\!_{16}}(17)) \oplus {L} {'\!_{17}}(22))$，总共需要猜测79 bit 密钥，具体过程如图4所示。

图  4  Tb₁的计算

下载: 全尺寸图片 幻灯片

(a) 对于2²⁴个猜测密钥${K'\!_{23}}$和2⁴⁶个密文，设置2⁴¹个1 bit计数器${{\rm {Re}} _1}$，计算得到${L} {'\!_{22}}(1,2,5 \sim 7,9 \sim$$22)||{R} {'\!_{22}}(0 \sim 2,4 \sim 22)$的值，给相应的计数器的值增加1，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{46}} \times {2^{24}} \times 1/24{\rm{ + }}{2^{46}} \times {2^{24}} \times 22/$$(24 \times 24) \approx {2^{66.42}}$。

(b) 对于2²²个猜测密钥${K'\!_{22}}(0{\rm{ \sim 2}},{\rm{4 \sim }}22)$和保留下来的${\rm{R}}{{\rm{e}}_1}$的位置，设置2³³个1 bit计数器${{\rm {Re}} _2}$，计算得到${L} {'\!_{21}}(2,6,7,10 \sim 12,14 \sim 17,19 \sim 22)||{R} {'\!_{21}}$$(1,2,5 \sim 7,9 \sim 22)$的值，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{46}} \times {2^{41}} \times 19/(24 \times$$24) \approx {2^{82.08}}$。

(c) 对于2¹⁰个猜测密钥${K'\!_{21}}(1,2,6,{\rm{7}},{\rm{11}},{\rm{12}},{\rm{16}},$${\rm{17}},{\rm{21}},{\rm{22}})$和保留下来的${\rm{R}}{{\rm{e}}_2}$的位置，设置2³⁰个1 bit计数器${\rm{R}}{{\rm{e}}_3}$，计算${L} {'\!_{20}}(5,7,9 \sim 22)||{R} {'\!_{20}}(2,6,$$7,11,12,16,17,21,22)||{L} {'\!_{21}}(10,14,15,19,20)$的值，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{56}} \times {2^{33}} \times 9/(24 \times 24) \approx {2^{83.00}}$。

(d) 对于2⁷个猜测密钥${K'\!_{21}}(5,{\rm{9}},{\rm{10}},{\rm{14}},{\rm{15}},{\rm{19}},$${\rm{20}})$和保留下来的${\rm{R}}{{\rm{e}}_3}$的位置，设置2²³个1 bit计数器${\rm{R}}{{\rm{e}}_4}$，计算得到${L} {'\!_{20}}(7,11,12,15 \sim 17,20 \sim 22)||$${R} {'\!_{20}}(2,6,7,10 \sim 12,14 \sim 17,19 \sim 22)$的值，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{63}} \times {2^{30}} \times 5/(24 \times 24) \approx {2^{86.15}}$。

(e) 对于2⁷个猜测密钥${K'\!_{20}}(6,{\rm{10}},{\rm{11}},{\rm{15}},{\rm{16}},{\rm{20}},$${\rm{21}})$和保留下来的${\rm{R}}{{\rm{e}}_4}$的位置，设置2¹⁸个1 bit计数器${\rm{R}}{{\rm{e}}_5}$，计算得到${L} {'\!_{19}}(2,6,7,11,12,16,17,21,22)||$${R} {'\!_{19}}(11,15,16,20,21)||{R} {'\!_{20}}(7,12,17,22)$的值，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{70}} \times {2^{23}} \times 5/(24 \times 24) \approx {2^{86.15}}$。

(f) 对于2⁵个猜测密钥${K'\!_{20}}(2,{\rm{7}},{\rm{12}},{\rm{17}},{\rm{22}})$和保留下来的${\rm{R}}{{\rm{e}}_5}$的位置，设置2¹⁴个1 bit计数器${\rm{R}}{{\rm{e}}_6}$，计算得到${L} {'\!_{19}}(12,16,17,21,22)||{R} {'\!_{19}}(7,11,12,15 \sim$$17,20 \sim 22)$的值，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{75}} \times {2^{18}} \times 4/(24$$\times 24) \approx {2^{85.83}}$。

(g) 对于2⁷个密钥${K'\!_{19}}({\rm{7}},{\rm{11}},{\rm{12}},{\rm{16}},{\rm{17}},{\rm{21}},{\rm{22}})$和保留下来的${\rm{R}}{{\rm{e}}_6}$的位置，由密钥扩展算法的性质1和性质2可知，因为${K'\!_{19}}{\rm{ = }}{\rm{rk} _{19}} \oplus ({\rm{rk} _{20}} < < < 1)$, ${\rm{rk} _{19}}{\rm{ = }}{\rm{rk} _{23}} \oplus {f} ({\rm{rk} _{20}}) \oplus {{c} _{19}}$，又根据等价子密钥与原始子密钥的线性关系，${\rm{rk} _{23}}$和${\rm{rk} _{20}}$可以由已经猜测的密钥比特直接算出，所以${K'\!_{19}}({\rm{7}},{\rm{11}},{\rm{12}},{\rm{16}},{\rm{17}},$${\rm{21}},{\rm{22}})$不需要猜测。而且计算过程与中间状态无关，所以相较于解密过程，计算复杂度忽略不计。设置2⁷个1 bit计数器${\rm{R}}{{\rm{e}}_7}$，计算得到${L} {'\!_{18}}({\rm{17}},{\rm{22)}}||$${R} {'\!_{18}}({\rm{12}},{\rm{16}},{\rm{17}},{\rm{21}},{\rm{22}})$的值，给相应的计数器的值增加1，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{75}} \times {2^{14}} \times 5/(24 \times 24) \approx {2^{82.15}}$。

(h) 对于2³个密钥${K'\!_{18}}({\rm{12}},{\rm{17}},{\rm{22}})$和保留下来的${\rm{R}}{{\rm{e}}_7}$的位置，与第(g)步类似，根据密钥扩展算法的性质和等价子密钥与原始子密钥的关系，可知计算${K'\!_{18}}({\rm{12}},{\rm{17}},{\rm{22}})$的复杂度忽略不计。设置2³个1 bit计数器${\rm{R}}{{\rm{e}}_8}$，计算得到${L} {'\!_{17}}(22){\rm{||}}{R} {'\!_{17}}({\rm{17}},{\rm{22}})$的值，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{75}} \times {2^7} \times 2/(24 \times 24) \approx {2^{73.83}}$。

(i) 对于密钥${K'\!_{17}}({\rm{17}},{\rm{22}})$以及保留下来的${\rm{R}}{{\rm{e}}_8}$的位置，猜测4-bit ${K'\!_{20}}(14,19)$和${K'\!_{21}}(13,18)$，计算出${K'\!_{17}}{\rm{(17,22)}}$这2-bit 的密钥值，计算复杂度约为3轮Simeck48加密运算。计算得到$(({L} {'\!_{16}}$$(22) \oplus {K'\!_{17}}{\rm{(22))}} \odot ({L} {'\!_{16}}(17) \oplus {K'\!_{17}}{\rm{(17)}})) \oplus {L} {'\!_{17}}(22)$的值，和猜测的密钥比特一起存储在表${{\rm {Tb}} _1}$。这一步的时间复杂度为${2^{79}} \times {2^3} \times 1/(24 \times 24) + {2^{79}} \times 3 \times$$2/(24 \times 24) \approx {2^{73.64}}$。

(2) 计算表${\rm{T}}{{\rm{b}}_2}$的过程

计算$\oplus {R} {'\!_{17}}(21)$，总共需要猜测65 bit密钥，具体过程下所示。

(a) 对于2²²个猜测密钥${K'\!_{23}}(0,1,3 \sim 21,23)$和2⁴⁶个密文，设置2³³个1 bit计数器${\rm{R}}{{\rm{e}}_1}$，计算得到${L} {'\!_{22}}(1,5,6,9 \sim 11,13 \sim 21)||{R} {'\!_{22}}(0,1,4 \sim 6,8 \sim 21)$的值，给相应的计数器加1，保留计数器的值为奇数的值。这一步时间复杂度为${2^{46}} \times {2^{22}} \times 22/(24 \times$$24){\rm{ + }}{2^{46}} \times {2^{22}} \times 19/(24 \times 24) \approx {2^{63.29}}$。

(b) 对于2¹⁹个猜测密钥${K'\!_{22}}(0,1,4 \sim 6,8 \sim$$21)$和保留下来的${\rm{R}}{{\rm{e}}_1}$的位置，设置2²⁵个1 bit计数器${\rm{R}}{{\rm{e}}_2}$，计算得到${L} {'\!_{21}}(6,10,11,14 \sim 16,18 \sim 21)||$${R} {'\!_{21}}(1,5,6,9 \sim 11,13 \sim 21)$的值，给相应计数器的值增加1，保留计数器的值为奇数的值。这一步时间复杂度为${2^{41}} \times {2^{33}} \times 15/(24 \times 24) \approx {2^{68.74}}$。

(c) 对于2¹⁵个${K'\!_{21}}(1,5,6,9 \sim 11,13 \sim 21)$和保留下来的${\rm{R}}{{\rm{e}}_2}$位置，设置2¹⁶个1 bit计数器${\rm{R}}{{\rm{e}}_3}$，计算${L} {'\!_{20}}(11,15,16,19 \sim 21)||{R} {'\!_{20}}(6,10,11,14 \sim 16,18 \sim$$21)$的值，保留计数器的值为奇数的值。时间复杂度为${2^{56}} \times {2^{25}} \times 10/(24 \times 24) \approx {2^{75.15}}$。

(d) 对于2⁹个猜测密钥${K'\!_{20}}(6,10,11,14 \sim 16,$$19 \sim 21)$和保留下来的${\rm{R}}{{\rm{e}}_3}$的位置，设置2⁹个1 bit计数器${\rm{R}}{{\rm{e}}_4}$，计算得到${L} {'\!_{19}}(10,16,21)||{R} {'\!_{19}}(11,15,16,$$19 \sim 21)$的值，给相应的计数器的值增加1，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{65}} \times {2^{16}} \times 6/(24 \times 24) \approx {2^{74.42}}$。

(e) 对于2⁵个密钥${K'\!_{19}}(11,15,16,20,21)$和保留下来的${\rm{R}}{{\rm{e}}_4}$的位置，因为${K'\!_{19}}{\rm{ = }}{\rm{rk} _{19}} \oplus ({\rm{rk} _{20}} < < < 1)$，由性质1可知${\rm{rk} _{19}}{\rm{ = }}{\rm{rk} _{23}} \oplus {f} ({\rm{rk} _{20}}) \oplus {{c} _{19}}$，又根据等价子密钥与原始子密钥的关系，${\rm{rk} _{23}}$和${\rm{rk} _{20}}$可以由已经猜测的密钥比特直接算出，所以${K'\!_{19}}(11,15,16,20,$21)不需要猜测。计算过程与中间状态无关，所以相较于解密过程，计算复杂度可以忽略不计。设置2⁴个1 bit计数器${\rm{R}}{{\rm{e}}_5}$，计算得到${L} {'\!_{18}}(21)||{R} {'\!_{18}}(10,$16,21)的值，给相应的计数器的值增加1，保留计数器的值为奇数的那些值。这一步的时间复杂度为${2^{65}} \times {2^9} \times 3/(24 \times 24) \approx {2^{66.42}}$。

(f) 对于密钥${K'\!_{18}}(16,21)$和保留下来的${\rm{R}}{{\rm{e}}_5}$的位置，密钥${K'\!_{18}}(16,21)$可以由已经猜测的密钥比特唯一解出，计算复杂度约为加密2轮Simeck48运算。计算得到$\oplus {R} {'\!_{17}}(21)$的值，和猜测的密钥一起存储在表${\rm{T}}{{\rm{b}}_2}$中。时间复杂度为${2^{65}} \times {2^4} \times 1/(24 \times 24){\rm{ + }}$${2^{65}} \times (2 \times 2)/(24 \times 24) \approx {2^{60.15}}$。

因为只考虑1个平衡比特，所以总的密钥候选空间从${2^{65 + 14 + 0}} = {2^{79}}$减少到2⁷⁸。再加上剩余的${K'\!_{20}}(0,1,3,4,5,7,8,13,18,23)$, ${K'\!_{21}}(0,3,4,8,23)$和${K'\!_{22}}(1,23)$这17 bit的密钥，仍然有2⁹⁵个候选密钥。针对这2⁹⁵个候选密钥检测明密文是否匹配，进一步根据等价子密钥和轮子密钥的关系和密钥扩展算法，可以由轮子密钥解出正确的主密钥。

24轮Simeck48算法的积分攻击的过程可以概括如下：

步骤 1　构造一个包含2⁴⁶个明文的集合，该集合中的明文满足以下性质：加密1轮后的输出形式为$({\rm{ACAA}},{\rm{ACAA}},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A})$。进一步，加密明文获得相应密文；

步骤 2　猜测子密钥${K'\!_{i} }(17 \le {i} \le 23)$的部分比特，并且部分解密2⁴⁶个密文8轮来计算$\oplus (({L} {'\!_{16}}(22)$$\odot {L} {'\!_{16}}(17)) \oplus {L} {'\!_{17}}(22))$，计算结果和79 bit猜测密钥一起存储在表${{\rm {Tb}} _1}$中；

步骤 3　猜测${K'\!_{i} }(18 \le {i} \le 23)$的部分比特，并且部分解密2⁴⁶个密文7轮来计算$\oplus {R} {'\!_{17}}(21)$，计算结果和65 bit猜测密钥一起存储在表${{\rm {Tb}} _2}$中；

步骤 4　对每个候选的子密钥，猜测${K'\!_{i} }(20 \le$${i} \le 23)$剩余的17 bit密钥，根据性质1计算得到主密钥，利用两组明密文对检查密钥的正确性，筛选得到正确的主密钥。

3.4   复杂度计算

24轮Simeck48积分攻击的数据复杂度为2⁴⁶个选择明文。

构造${\rm{T}}{{\rm{b}}_1}$和${\rm{T}}{{\rm{b}}_2}$的时间复杂度分别为${2^{87.75}}$和${2^{75.83}}$，所以攻击过程中步骤2和步骤3总的时间复杂度为${2^{87.75}}{\rm{ + }}{2^{75.83}} \approx {2^{87.75}}$次24轮Simeck48加密，而步骤4的时间复杂度为2⁹⁵次24轮Simeck48加密。所以，总的攻击时间复杂度约为2⁹⁵次24轮Simeck48加密。

存储的内容包括${\rm{T}}{{\rm{b}}_1}$和${\rm{T}}{{\rm{b}}_2}$。对于${\rm{T}}{{\rm{b}}_1}$，存储复杂度为${2^{82.52}}$ Byte。对于${\rm{T}}{{\rm{b}}_2}$，存储复杂度为${2^{68.19}}$ Byte。所以，总的存储复杂度约为${2^{82.52}}$ Byte。

4.   29轮Simeck64算法的积分攻击

文献[7]中给出Simeck64算法15轮积分区分器，区分器的输入形式为：$({\rm{ACCC}},{\rm{CCCC}},{\rm{CCCC}},$${\rm{ACCC}},{\rm{AACC}},{\rm{AAAC}},{\cal A},{\cal A},{\rm{ACCC}},{\rm{CCCA}},{\rm{CCCA}},$${\rm{ACCA}},{\rm{AACA}},{\cal A},{\cal A},{\cal A})$，区分器输出状态中右半部分第28个比特${C_R}(28)$是平衡的。在该积分区分器基础上，向前做高阶积分扩展，得到19轮的积分区分器$({\rm{AAAC}},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},{\cal A},$${\cal A},{\cal A})$，进一步，基于算法 Feistel结构，可以向前扩展1轮得到20轮的高阶积分区分器。

利用该区分器，攻击29轮的Simeck64算法。攻击过程与3.3节类似。在部分解密9轮Simeck64算法恢复密钥的计算过程中，使用部分和技术和密钥扩展算法的性质来降低时间复杂度。猜测得到2¹⁰⁴个105 bit等价子密钥，在此基础上穷举23 bit等价子密钥，从而实现全密钥的恢复。29轮Simeck64积分攻击的数据复杂度为2⁶³，时间复杂度为2^127.3次，存储复杂度为2^109.02。

5.   结束语

本文给出了轻量级分组密码算法Simeck积分攻击的新结果。在已有积分区分器的基础上，通过向前做高阶积分扩展，分别得到16轮Simeck48和20轮Simeck64算法的积分区分器。利用等价子密钥技术、中间相遇策略，结合部分和技术和密钥扩展算法的性质，实现了24轮Simeck48和29轮Simeck64的积分攻击。与已有积分攻击的结果相比，本文明显提高了Simeck48和Simeck64算法积分攻击的轮数，分别提高了3轮和5轮。下一步如何利用减少复杂度的技术推广积分攻击算法的应用范围，将是值得研究的工作。