缩减轮GRANULE算法的中间相遇分析

Meet-in-the-Middle Attacks on Reduced-Round GRANULE

摘要: 轻量级分组密码是为计算资源受限的环境而设计的加密算法。它具有计算开销小、占用存储空间少、能耗低等优点，广泛用于嵌入式系统、智能卡以及物联网等应用场景。然而，为了追求更高的实现效率，设计轻量级分组密码算法时会牺牲部分安全性，所以有必要评估它的安全强度。本文利用中间相遇分析法对轻量级分组密码GRANULE算法的安全性进行了评估。首先，构造了7轮的GRANULE的中间相遇区分器，随后在它的前面接4轮、后面接3轮，构建了14轮的GRANULE中间相遇分析的攻击路径，并在结合GRANULE的轮密钥之间的一些线性关系之后，最终攻击需要的数据复杂度为2⁶⁰选择明文，时间复杂度为2^111.2次14轮GRANULE加密，存储复杂度为2^104.9个64比特块。此结果是对GRANULE安全性分析的有效补充，攻击结果表明GRANULE能较好地抵抗中间相遇攻击。

Abstract: Lightweight block cipher is an encryption algorithm designed for environments with limited computing resources. It has the advantages of low computational cost, less storage space occupation, and low energy consumption, and is widely used in application scenarios such as embedded systems, smart cards, and the Internet of Things. However, in order to pursue higher implementation efficiency, designing lightweight block cipher algorithms may sacrifice some security, so it is necessary to evaluate its security strength. In this article we evaluate the security of the lightweight block cipher GRANULE algorithm using the intermediate encounter analysis method. Firstly, a 7-round GRANULE intermediate encounter discriminator was constructed, followed by 4 rounds in front and 3 rounds behind it. 14-round GRANULE intermediate encounter analysis attack path was constructed, and after combining some linear relationships between GRANULE’s round keys. Data complexity is 2⁶⁰ chosen plaintexts, time complexity is 2^111.2 14-round GRANULE encryption, and storage complexity is 2^104.9 64-bit blocks. This result is an effective supplement to the security analysis of GRANULE, and the attack results indicate that GRANULE can resist intermediate encounter attacks well.

1. 引言

随着物联网、嵌入式系统和智能设备的快速发展，越来越多的终端被部署在计算能力弱、存储空间小、能耗要求严格的环境中，而这些设备同样面临着数据加密与安全通信的需求。传统分组密码算法如AES在这些场景中存在实现复杂、资源开销大等问题，往往难以高效运行。保证基本安全性的前提下，为了实现低功耗、小面积、高效率的加密操作，轻量级分组密码应运而生。

轻量级分组密码是一类为计算资源受限的环境而设计的加密算法，具有计算开销小、占用存储空间少、能耗低等优点，因而非常适用于嵌入式系统、智能卡以及物联网等应用场景。在这一领域的发展过程中，诸如WARP [1]、PRESENT [2]、Lblock [3]和GRANULE [4]等密码算法被广泛应用。然而，随着各类信息安全事件的频繁发生，数据保护的重要性日益凸显。然而，为了实现高效率，设计轻量级分组密码时通常会在一定程度上牺牲安全性，从而为潜在攻击留下了空间，因此研究轻量级分组密码的安全性非常必要。

GRANULE是BANSOD B和PATIL A等人在2018年提出的一款轻量级分组密码，该算法是一种Feistel-Substitution Permutation (Feistel-SP)结构，采用64比特的分组长度并迭代32轮。算法有两个版本：GRANULE-64/80和GRANULE-64/128，分别对应80比特及128比特的密钥长度[4]。GRANULE算法的轮函数设计中使用了8个4比特的S盒及两次循环异或和使得其满足混淆扩散原则，因此对其安全性的研究可以为选择安全高效的轻量级分组密码提供理论依据。2019年，石淑英等[5]基于一条GRANULE算法5轮不可能差分链，扩展6轮，构建了GRANULE-64/80算法的11轮不可能差分分析。2020年，武小年等[6]通过S盒输入/输出差分特征的规律，遍历搜索获得了几条GRANULE算法的7轮不可能差分区分器，但未进行密钥恢复攻击。2021年，赵晨曦[7]也利用S盒差分特征规律得到GRANULE算法的7轮不可能差分链，分别在前、后各扩展3轮，对GRANULE-64/80发起了13轮不可能差分攻击。2023年，刘先蓓等[8]利用中间相错技术构造了GRANULE算法7轮不可能差分区分器，同时将构造的区分器往前往后各扩展3轮，结合密钥的线性相关特征，对GRANULE-64/80发起了13轮不可能差分攻击。可以看出，研究者们主要是利用不可能差分攻击的方法对GRANULE-64/80算法进行了分析。

1977年，Hellman和Diffie首次提出了中间相遇攻击的概念，其核心思想是小幅提升存储复杂度来换取时间复杂度的降低[9]，即时间–空间折中策略。随后，Demirci等人[10]分析AES时对此方法进行了改进，将攻击过程分为离线和在线两个阶段。离线阶段，攻击者的主要任务是构造一个中间相遇区分器，并在区分器前端部分构建一个$\delta$ -集，计算出与之对应的输出端有序序列，存储在预计算表中，为在线阶段的攻击做好准备。在线阶段，攻击者在区分器的前端和后端分别延拓数轮形成用于恢复密钥的路径。随后攻击者选择符合路径差分的明密文对，并猜测加解密过程中前端和后端需要猜测的密钥部分，对选定的明密文对进行加解密操作，再查询预计算表，寻找是否存在与加解密结果相匹配的项。若发现匹配项，表明猜测的密钥可能是正确的密钥，否则为错误密钥，将被过滤。当排除所有错误密码后，最终恢复正确密钥。中间相遇攻击还可以和多重集技术、差分枚举技术和密钥桥技术等技术结合形成更加高效的攻击，广泛适用于分组密码，提高分析效率，目前已对许多分组密码抵抗中间相遇攻击能力的评估，如AES [11]、MIBS [12]、Midori [13]、LBlock [14]等。因此，研究GRANULE抵抗中间相遇攻击的能力非常重要。

本文利用$\delta$ -集及差分枚举技术，结合GRANULE算法结构特性，获得了一个7轮中间相遇区分器，基于该区分器，前、后分别增加4轮、3轮，构建了14轮GRANULE-64/128的中间相遇攻击路径。攻击所需要数据复杂度为$2^{60}$ 个选择明文，时间复杂度为$2^{111.3}$ 次14轮GRANULE-64/128加密，存储复杂度为$2^{104.9}$ 个64比特块。此结果是对GRANULE-64/128抵抗中间相遇攻击的一个重要补充。

2. 预备知识

本节对文中的符号及GRANULE算法进行介绍。

2.1. 符号简介

(1) $M,C,K$ ：分别表示明文、密文和主密钥；

(2) $L_i,R_i$ ：分别表示第i轮左、右侧部分，$1\le i\le 32$ ；

(3) $L_i\left[j\right],R_i\left[j\right]$ ：分别表示第i轮左、右侧部分第j个半字节的值，$1\le i\le 32$ ，$0\le j\le 7$ ；

(4) $\Delta L_i\left[j\right],\Delta R_i\left[j\right]$ ：分别表示第i轮左、右侧部分第j个半字节的差分值，$1\le i\le 32$ ，$0\le j\le 7$ ；

(5) $Y_i\left[j\right]$ ：第i轮经过P置换后S盒输入的第j个半字节的值，$1\le i\le 32$ ，$0\le j\le 7$ ；

(6) $R{K}_i^{},R{K}_i^j$ ：分别表示第i轮使用的子密钥及它的第j个半字节，$1\le i\le 32$ ，$0\le j\le 7$ ；

(7) $<<<\alpha$ ，$>>>\beta$ ：分别表示循环左移$\alpha$ 比特、右移$\beta$ 比特；

(8) $\oplus$ ：异或操作；

(9) ${\left[i\right]}^2$ ：i的五位二进制表示；

(10) $\left|\right|$ ：二进制字符连接。

2.2. GRANULE算法介绍

GRANULE算法分组长度为64比特，左、右分支分别为32比特，整个算法经过32轮迭代。算法采用Feistel结构，见图1。该算法轮函数中，包含P置换、S盒、循环移位异或运算及轮密钥异或运算。下面具体介绍算法P置换、S盒及密钥编排算法。

Figure 1. GRANULE algorithm structure

图1. GRANULE算法结构

(1) P置换。该置换是对左分支字节重新排序。首先将左分支L分成8个半字节$l_0{l}_1{l}_2{l}_3{l}_4{l}_5{l}_6{l}_7$ ，则经过P置换后将得到$l_1{l}_3{l}_5{l}_2{l}_0{l}_7{l}_4{l}_6$ ，即

$l_1{l}_3{l}_5{l}_2{l}_0{l}_7{l}_4{l}_6=P\left(l_0{l}_1{l}_2{l}_3{l}_4{l}_5{l}_6{l}_7\right)$

(2) S盒。GRANULE算法采用8个并置的S盒，每一个S盒输入输出均为4比特，具体如表1所示。

Table 1. S box of GRANULE

表1. GRANULE的S盒

x	0	1	2	3	4	5	6	7	8	9	a	b	c	d	e	f
S(x)	e	7	8	4	1	9	2	f	5	a	b	0	6	c	d	3

(3) 密钥编排算法。GRANULE算法有两个版本：GRANULE-64/80和GRANULE-64/128，分别对应80比特密钥和128比特密钥。本文针对GRANULE-64/128进行密钥恢复攻击，在此仅介绍128比特版本的密钥编排算法。

将128比特的主密钥存入密钥寄存器K中，$K=K_{127}\left|\right|K_{126}\left|\right|\cdots \left|\right|K_1\left|\right|K_0$ 。第一轮子密钥$R{K}_1$ 为K最右端的32比特，即$R{K}_1=K_{31}{K}_{30}\cdots K_1{K}_0$ 。随后更新密钥寄存器K，以K最右端的32比特作为第r ($2\le r\le 32$ )轮子密钥$R{K}_r$ ，更新算法如下所示：

$\{\begin{array}{l}K<<<31;\\ \left[K_3{K}_2{K}_1{K}_0\right]\leftarrow S\left[K_3{K}_2{K}_1{K}_0\right];\\ \left[K_7{K}_6{K}_5{K}_4\right]\leftarrow S\left[K_7{K}_6{K}_5{K}_4\right];\\ \left[K_{70}{K}_{69}{K}_{68}{K}_{67}{K}_{66}\right]\leftarrow \left[K_{70}{K}_{69}{K}_{68}{K}_{67}{K}_{66}\right]\oplus {\left[i\right]}^2;\end{array}$

3. 14轮GRANULE中间相遇攻击过程

这一章节主要介绍7轮中间相遇区分器的构造以及14轮中间相遇攻击的具体过程。

3.1. 7轮GRANULE中间相遇区分器

通过列举多条中间相遇区分器，找到一条在预计算过程中猜测的中间参数最少的中间相遇差分链，见图2。图2详细展示了中间相遇差分链$\left(R_1\left[7\right];R_8\left[4\right],R_8\left[5\right]\right)$ 的具体结构，其中白色表示该半字节位置的差分为零，灰色表示此半字节位置的差分受区分器输入差分影响，黑色表示此半字节位置差分影响区分器的输出差分，同时受区分器输入差分影响。

定理１：若$\delta$ -集满足$R_1\left[7\right]$ 活跃，其他位置非活跃，则经过7轮GRANULE加密后输出差分序列：$R_8^0\left[4\right]+R_8^1\left[4\right]$ ，$R_8^0\left[4\right]+R_8^2\left[4\right]$ ，$\cdots$ ，$R_8^0\left[4\right]+R_8^{15}\left[4\right]$ ，$R_8^0\left[5\right]+R_8^1\left[5\right]$ ，$R_8^0\left[5\right]+R_8^2\left[5\right]$ ，$\cdots$ ，$R_8^0\left[5\right]+R_8^{15}\left[5\right]$ 可由$Y_2\left[5\right]$ ，$Y_3\left[7,6,2,1\right]$ ，$Y_4\left[7~0\right]$ ，$Y_5\left[7~0\right]$ ，$Y_6\left[7~3\right]$ 共26个参数表示。

证明：如图2所示，假设区分器输入差分满足$\Delta R_1\left[7\right]$ 为非零差分，其他位置均为零差分。

(1) 猜测$Y_2\left[5\right]$ ，则第二轮S盒的输入值已知，经过S盒后与密钥进行异或，因为异或操作、移位操作、分组置换不会改变差分值，因此第二轮右侧的输出差分$\Delta R_2$ 已知，也即第三轮左侧输入差分$\Delta L_3$ 已知；

(2) 因为$\Delta L_3\left[6,5,4,3\right]$ 非零，经P置换后，$\Delta Y_3\left[7,6,2,1\right]$ 非零，因此猜测$Y_3\left[7,6,2,1\right]$ ，则第三轮右侧的输出差分$\Delta R_3$ 已知；

(3) 因为$\Delta L_4=\Delta R_3$ 已知，猜测$Y_4\left[7~0\right]$ ，则第四轮右侧的输出差分$\Delta R_4$ 已知；

(4) 同理，猜测$Y_5\left[7~0\right]$ 的值，则第五轮右侧的输出差分$\Delta R_5$ 已知；

(5) 猜测$Y_6\left[7~3\right]$ 的值，则获得第六轮右侧的输出差分$\Delta R_6$ ，即第7轮左侧的$\Delta L_7\left[5\right],\Delta L_7\left[4\right]$ 已知；

此时，不需要再另外猜测Y，即可得到第8轮右侧的$\Delta R_8\left[5\right],\Delta R_8\left[4\right]$ ，即$R_8\left[5\right],R_8\left[4\right]$ 的30个4比特差分序列可以由$Y_2\left[5\right]$ ，$Y_3\left[7,6,2,1\right]$ ，$Y_4\left[7~0\right]$ ，$Y_5\left[7~0\right]$ ，$Y_6\left[7~3\right]$ 这26个参数表示。

由定理1可知，$R_8\left[5\right],R_8\left[4\right]$ 处，这$15\times 2$ 个4比特差分序列仅有$2^{26\times 4}=2^{104}$ 种取值，而非$2^{30\times 4}=2^{120}$ 种取值。

Figure 2. The specific structure of the intermediate encounter differential chain $\left(R_1\left[7\right];R_8\left[4\right],R_8\left[5\right]\right)$

图2. 中间相遇差分链$\left(R_1\left[7\right];R_8\left[4\right],R_8\left[5\right]\right)$ 的具体结构

3.2. 14轮GRANULE中间相遇攻击

基于上述的7轮区分器，在前端加4轮，后面接3轮，对14轮GRANULE进行中间相遇攻击，攻击路径见图3。攻击分为离线和在线两个部分，具体如下。

离线阶段：计算120比特差分序列的所有$2^{104}$ 种可能值，并存储于哈希表中。

在线阶段：选择符合图3路径的明文对，构造对应的$\delta$ -集，猜测部分轮密钥得到差分序列$\Delta R_8\left[5\right],\Delta R_8\left[4\right]$ ，检查是否与离线阶段建立的哈希表中的项匹配。若没有相匹配的项，则猜测密钥为错误。删除错误密钥后，在剩余密钥基础上穷搜恢复完整主密钥。具体过程如下：

(1) 选择符合图3的明文$M^0=L_1^0\left|\right|R_1^0$ ，猜测密钥$R{K}_1^{7~5}$ 、$R{K}_1^{3~0}$ ，部分加密$M^0$ 得到$L_2^0\left|\right|R_2^0$ ；

(2) 猜测密钥$R{K}_2^7$ 、$R{K}_2^5$ 、$R{K}_2^4$ 、$R{K}_2^0$ ，部分加密$L_2^0\left|\right|R_2^0$ 得$L_3^0\left|\right|R_3^0$ ；

(3) 猜测密钥$R{K}_3^7$ ，部分加密$L_3^0\left|\right|R_3^0$ 得$L_4^0\left|\right|R_4^0$ 。因为$R_5^0=L_4^0$ ，所以可得区分器的输入端$L_5^0\left|\right|R_5^0$ ；

(4) 已知$L_{15}\left|\right|R_{15}$ 及其差分，需要猜测$R{K}_{14}^{7~0}$ ，对$L_{15}\left|\right|R_{15}$ 进行解密即可得到$L_{14}\left|\right|R_{14}$ 和$\Delta L_{14}\left|\right|\Delta R_{14}$ ；

(5) 猜测$R{K}_{13}^{7~0}$ ，对$L_{14}\left|\right|R_{14}$ 进行解密即可得到$L_{13}\left|\right|R_{13}$ 和$\Delta L_{13}\left|\right|\Delta R_{13}$ ；

(6) 对于$L_{13}\left|\right|R_{13}$ ，$L_{13}$ 经过S盒之后得到的输出差分与$\Delta R_{13}$ 异或即可得到区分器的输出差分$\Delta R_{12}\left[5\right]$ ，$\Delta R_{12}\left[4\right]$ ；

(7) 检查解密所得差分序列是否存在于离线阶段建立的哈希表中。若不存在，否则删除猜测密钥。在对剩余密钥穷举搜索进而恢复完整主密钥。

此时，在整个攻击过程中，一共猜测了轮密钥$R{K}_1^{7~5}$ 、$R{K}_1^{3~0}$ 、$R{K}_2^7$ 、$R{K}_2^5$ 、$R{K}_2^4$ 、$R{K}_2^0$ 、$R{K}_3^7$ 、$R{K}_{13}^{7~0}$ 、$R{K}_{14}^{7~0}$ ，由密钥关系可知，$R{K}_1^0$ 的最低位与$R{K}_2^7$ 的最高位一样，所以在此处可少猜一位密钥，共111个密钥。

Figure 3. Attack path encountered in the middle of round 14 GRANULE

图3. 14轮GRANULE中间相遇攻击路径

3.3. 复杂度分析

由于选择明文$M^0$ 要求1个半字节差分为零，15个半字节差分非零，故攻击所需数据量为$2^{15\times 4}=2^{60}$ 个选择明文。

离线阶段时间复杂度为$2^4\times 2^{26\times 4}$ 次部分加密，约为$2^4\times 2^{26\times 4}/14\approx 2^{104.2}$ 次14轮GRANULE加密；存储为$2^{26\times 4}=2^{104}$ 个120比特差分序列，$120/64=1.875\approx 2^{0.9}$ ，故存储复杂度约为$2^{104.9}$ 个64比特块。

在线阶段经过$2^4\times 2^{111}$ 次部分加解密，约为$2^4\times 2^{111}/14\approx$ $2^{111.2}$ 次14轮GRANULE加密。

综上，对14轮GRANULE中间相遇攻击所需的最终攻击需要的数据复杂度为$2^{60}$ 选择明文，时间复杂度为$2^{111.2}$ 次14轮GRANULE加密，存储复杂度为$2^{104.9}$ 个64比特块。

4. 结论

本文利用$\delta$ -集及差分枚举技术，结合GRANULE算法结构特性，获得了一个7轮中间相遇区分器，基于该区分器，前、后分别增加4轮、3轮，构建了14轮GRANULE-64/128的中间相遇攻击路径。攻击所需要数据复杂度为$2^{60}$ 个选择明文，时间复杂度为$2^{111.2}$ 次14轮GRANULE-64/128加密，存储复杂度为$2^{104.9}$ 个64比特块。此结果是对GRANULE-64/128抵抗中间相遇攻击的一个重要补充。

基金项目

安徽省高校自然科学重点项目(2024AH050011)。