基于MILP的BORON中间相遇分析

MILP-Based for Middle-Meeting Cryptanalysis of BORON

摘要: BORON是新设计的超轻量级分组密码，被广泛应用于资源受限的设备中保护数据安全，然而受计算和存储资源限制，设计者可能为了追求高的软硬件实现效率而适度降低安全性。为了保障它在实际系统中有足够安全强度，需要评估BORON抵抗各种密码分析方法的能力。本文分析了BORON抵抗中间相遇攻击的能力。具体来说，利用混合整数线性规划自动化搜索算法，找到多条5轮中间相遇差分链，在此基础上构造了9轮的中间相遇分析路径，基于该路径最后恢复9轮BORON的密钥。整个攻击需要的时间、数据和存储复杂度分别为2^95.84次9轮加密、2^42.00个选择明文和2^94.90个64比特块。此结果是对BORON安全性分析的重要补充。

Abstract: BORON is a recently designed ultra-lightweight block cipher that is widely used to protect data security in resource-constrained devices; however, due to computational and storage resource constraints, designers may moderately reduce the security in order to pursue high hardware and software implementation efficiency. In order to guarantee its sufficient security strength in real systems, it is necessary to evaluate the ability of BORON to resist various cryptanalysis methods. In this paper, we analyse the ability of BORON to resist the middle-meeting attacks. Specifically, multiple 5-round middle-meeting differential chains are found using mixed-integer linear programming automated search algorithms, the 5 rounds of middle-meeting differential distinguisher based on the 9 rounds of middle-meeting differential attack, the 9 rounds of middle-meeting differential cryptanalysis of the BORON-128 requires time, data, memory complexities of 2^95.84 9-round encryption times, 2^42.00 chosen plaintext and 2^94.90 64-bit blocks; The attack results providing an important supplement to the security analysis of BORON.

1. 引言

随着物联网技术的快速发展，物联网设备已经广泛应用于各个领域，这些设备存储了大量的敏感的数据信息，因此，保证这些数据的安全成为了重中之重。现如今，加密技术成为确保数据安全的关键手段之一。但传统加密算法在计算资源有限的物联网环境中显得笨重且不够高效。为了解决这一问题，轻量级分组密码应运而生。

轻量级分组密码是一种专门设计用于计算资源受限环境的加密算法。它们具有计算量小、存储空间小和功耗低的特点，非常适合嵌入式系统、智能卡和物联网设备等场景。在轻量级分组密码的发展历程中，诸如Piccolo [1] 、PRESENT [2] 、Prince [3] 、Lblock [4] 、CRAFT [5] 等算法均有着广泛的应用场景。但近年来信息安全事件不断涌现，使得数据安全保障工作越发重要。轻量级分组密码在设计时往往为了追求高的软硬件实现效率，常常会牺牲部分安全性，这可能成为数据安全保障的一个薄弱环节，因此研究轻量级分组密码的安全性非常重要。

BORON [6] 算法是2017年由Gaurav BANSOD等人提出的超轻量级SPN (Substitution-Permutation Network)结构的分组密码，共25轮，最后一轮输出结果与白化密钥进行异或得到密文。BORON有两个版本，分别为主密钥长度为80比特的BORON-80和主密钥长度为128比特的BORON-128。目前已经有一些针对BORON的安全性研究。Liang [7] 等在2019年使用自动化搜索算法搜寻到了8轮BORON-80的差分区分器和9轮的BORON-128的线性区分器，并在此基础上提出了对9轮BORON-80差分攻击和11轮的BORON-128的线性攻击。攻击9轮的BORON-80需要256次9轮BORON-80加密、263个选择明文和224个64比特块；攻击11轮的BORON-128需要2123次11轮BORON-128加密、263个选择明文和242个64比特块。Li [8] 等在2020年使用基于MILP (混合整数线性规划)的自动化搜索算法搜寻到了6轮的积分区分器，并在此基础上提出了对7轮、8轮和9轮BORON的积分攻击。攻击7轮BORON需要254.19次7轮BORON加密、254个选择明文，攻击8轮BORON需要258.34次8轮BORON加密、256.32个选择明文，攻击9轮BORON需要294.06次9轮BORON加密、257.90个选择明文，但文中并未指出需要多少存储复杂度。Wu [9] 等在2021年尝试对BORON进行不可能差分攻击，但文中出现了非零输入经过S盒后会得到零输出的错误，会对攻击过程及结果造成影响，因此本文不考虑这篇文章的结果。目前，对于BORON-128仅有差分、线性分析和积分攻击。

近年来，中间相遇分析 [10] 已经成功地评估了众多知名分组密码的安全性，如美国国家标准与技术研究院(NIST)提出的加密标准算法AES [11] 等，因此中间相遇攻击已成为非常重要的密码分析方法。同时，一些自动化搜索模型如MILP [12] 可以进一步提高中间相遇攻击的效率。但是截止目前还没有公开发表的BORON抵抗中间相遇攻击的能力的研究。

本文通过使用MILP求解模型寻找到了数条5轮BORON的中间相遇差分链，从中选取预计算过程中需要猜测参数个数最少的中间相遇区分链。在此区分链前端扩展1轮，后端扩展3轮形成9轮的BORON中间相遇攻击路径。对9轮BORON-128的中间相遇攻击所需的数据复杂度为2⁴²个选择明文，时间复杂度为2^95.84次9轮BORON加密，存储复杂度为2^94.90个64比特块。本文评估了BORON抵抗中间相遇攻击的能力，是BORON的安全性研究的重要补充。

2. 预备知识

2.1. BORON算法介绍

BORON算法是2017年由Gaurav BANSOD等人提出的超轻量级SPN结构的分组密码，共25轮，最后一轮输出结果与白化密钥进行异或得到密文。BORON有两个版本，分别为主密钥长度为80比特的BORON-80和主密钥长度为128比特的BORON-128。

轮函数 将64比特的输入划分为4个相同大小的块，每个块16比特，以每个块为单位进行轮函数迭代。BORON算法的轮函数如图1所示，轮函数由轮密钥、置换层和线性层组成，每一轮的输入先和轮密钥进行异或，得到的结果进入16个相同的4比特的S盒进行非线性操作，S盒如表1所示，S盒的输出结果依次进行分组置换、移位操作、异或操作，最终产生密文。

Figure 1. The round function of BORON

图1. BORON轮函数

Table 1. 4-bits S box

表1. 4-bits S盒

密钥调度 将BORON-128的128比特的主密钥K记为 $k_{127}\parallel k_{126}\parallel \cdots \parallel k_1\parallel k_0$ ，并把主密钥K的低位64比特作为初始轮密钥RK₀，然后将初始轮密钥经由S盒和移位操作，产生每一轮新的密钥，最终扩展成25轮的轮密钥RK，具体的密钥扩展算法如算法1所示。

2.2. 符号标记

1) M、C、K：明文、密文和主密钥；

2) $M^i$ ：第i个明文；

3) $X_i\left[j\right]$ ：第i轮输出的第j个比特， $\text{1}\le i\le \text{25}$ ， $0\le j\le \text{63}$ ，最右边为最低位；

4) $R{K}_i\left[j\right]$ ：第i轮使用的子密钥的第j个比特， $\text{1}\le i\le \text{25}$ ， $0\le j\le \text{63}$ ，最右边为最低位；

5) $Y_i\left[j\right],\Delta Y_i\left[j\right]$ ：第i轮轮密钥加密输出的第j个比特位置的值和差分；

6) $Z_i\left[j\right],\Delta Z_i\left[j\right]$ ：第i轮S盒输出的第j个比特位置的值和差分；

7) $W_i\left[j\right],\Delta W_i\left[j\right]$ ：第i轮分组置换、移位操作输出的第j个比特位置的值和差分；

8) $Y_i^r\left[j\right]$ ：第i轮 $Y^r$ 在第j个比特位置的值；

9) Ω：S盒输入和输出差分模式的向量；

10) *：此半字节处的差分是未知的；

11) $\oplus$ ：异或操作；

12) <<<i：循环左移i比特。

2.3. 中间相遇分析简介

Hellman和Diffie在1977年首次提出了中间相遇攻击方法，而后中间相遇攻击方法一直发展至今，并和许多新技术结合形成了更有效的攻击方法。中间相遇攻击中有一种近年来非常有效的攻击思想是将加密算法分成三个部分：区分器、区分器前端和区分器后端。整个攻击过程分为离线部分和在线部分。离线部分主要是在区分器输入端部分选取一个活动的位置构建 $\delta$ -集，再将其进行几轮加密后，计算区分器输出端的有序序列，并将 $\delta$ -集和有序序列对应关系存储在预计算表中。在线阶段则需要猜测区分器前端和区分器后端的部分密钥，对选定的明密文进行加解密，并查看在预计算表是否有匹配，当匹配时则说明猜测的密钥可能是正确的密钥，否则是错误的。

2.4. 构造MILP模型

MILP方法的主要思想是将寻找中间相遇区分器的问题转化为数学优化问题。BORON主要包含三个操作：异或操作、分组置换操作和S盒操作。下面将给出这三个操作的约束条件。

异或操作 在BORON中会频繁出现异或操作，假设 $a,b,c\in {\left\{0,1\right\}}^4$ ， $a\oplus b=c$ ，使用不等式组(1)对异或操作进行约束：

$\{\begin{array}{l}a+b+c\ge 2r\hfill \\ a\le r,b\le r,c\le r\hfill \end{array}$ (1)

分组置换操作 在BORON中，分组置换层一般用来表示第i轮的输出和第i+1的输入之间的联系。使用不等式组(2)对分组置换层进行约束：

$Y_i^j=X_{i+1}^{\pi }\left(j\right)$ (2)

S盒操作 假设 $m\times n$ 的S盒的其输入差分和输出差分分别记为 $\left(x_0,x_1,\cdots ,x_{m-1}\right),\left(y_0,y,\cdots ,y_{n-1}\right)$ ，则可以用不等式组(3)来描述S盒的传播规则：

$\{\begin{array}{l}{A}_t-x_i\ge 0,i\in \left\{0,1,\cdots ,m-1\right\}\hfill \\ -A_t+{\displaystyle \underset{j=0}{\overset{m-1}{\sum }}{x}_j}\ge \text{0}\hfill \end{array}$ (3)

其中 $A_t\in \left\{0,1\right\}$ 是一个表示该S盒是否活跃的虚拟变量。当且仅当 $x_0,x_1,\cdots ,x_{m-1}$ 不全为零时用 $A_t=1$ ，即代表该S盒为活跃S盒。 $m+n$ 维的向量Ω表示S盒的输入输出差分模式，即 $\Omega =\left(x_0,x_1,\cdots ,x_{m-1},y_0,y,\cdots ,y_{n-1}\right)\in F_2^{m+n}$ ，然后用H来表示所有的S盒可能的输入输出差分模式的凸包，并使用约减算法 [13] 对H进行去冗余操作，得到H的一个子集，将这个子集放入SageMath中，生成对应的不等式组。使用更少的不等式建立MILP模型来精确描述S盒的输入输出差分模式。

3. 基于MILP自动搜索Boron中间相遇区分器

BORON的加密过程由S盒、分组置换、和轮密钥异或组成(异或操作的约束在之前已详细讨论)。本文的中间相遇区分器只在单密钥情况下使用。

S盒 BORON的S盒的差分分布表如表2所示，将表中元素表示为差分模式 $\Omega =\left(x_0,x_1,\cdots ,x_{m-1},y_0,y,\cdots ,y_{n-1}\right)\in F_2^{m+n}$ ，并将差分模式放入SageMath工具中生成了352个不等式，再经过削减算法的去冗余后最终使用了不等式组(4)中的23个不等式即可描述S₀的差分性质，在此展示部分不等式，完整的S盒约束不等式见附录。因为BORON一共有16个S盒，因此需要368个不等式即可刻画所有S盒。

Table 2. The DDT of S box

表2. S盒的差分分布表

$\{\begin{array}{l}-x_3+x_1-x_0-y_2-y_1+3\ge 0\\ x_3-3x_2+x_1-x_0-3y_3-2y_2-3y_1-y_0+10\ge 0\\ -x_3-3x_2+x_1+x_0-3y_3-3y_2-2y_1-y_0+10\ge 0\\ -x_3-2x_2+2x_1-x_0-y_3+2y_2+2y_1-y_0+4\ge 0\\ ⋮\\ -2x_3-2x_2-x_1+2x_0-2y_3-y_2-y_1+y_0+7\ge 0\\ 2x_3-2x_2-x_1-2x_0-2y_3-y_2-y_1+y_0+7\ge 0\\ -2x_3-3x_2-3x_1+x_0-3y_3+y_2-2y_1-y_0+11\ge 0\\ x_3-3x_2-3x_1-2x_0-3y_3-2y_2+y_1-y_0+11\ge 0\end{array}$ (4)

分组置换层 假设 $x_i,y_i$ 分别表示BORON置换层的输入和输出，则置换层不等式的建立如不等式组(5)所示：

$\{\begin{array}{l}{x}_0-y_2=0\\ x_1-y_3=0\\ x_2-y_0=0\\ x_3-y_1=0\end{array}$ (5)

4. 9轮BORON中间相遇攻击过程

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

4.1. 5轮BORON区分器的构造

在获得需要的不等式后，即可开始寻找中间相遇区分器。在算法2中使用Gurobi求解器求解模型M，在保证至少有一个输入差分和一个输出差分是活跃的前提下，搜索到多条中间相遇区分器。表3仅列出部分4条中间相遇差分链，其中(i;j,k)表示区分器输入端活跃半字节位置为 $X_i$ ，输出端活跃半字节位置为 $X_j,X_k$ 。对表中的四条中间相遇差分链进行分析，发现差分链(4;4,5)需要用到的参数个数最少。图2详细展示了中间相遇差分链(4;4,5)的具体结构。

为了描述区分器，定义一个 $\delta$ -集 $\left\{M^0,M^1,\cdots ,M^{15}\right\}$ 满足 $X_1\left[19~16\right]$ 活跃，而 $X_1\left[63~20,15~0\right]$ 非活跃，则经过5轮Boron加密后输出差分序列： $X_6^1\left[23~16\right]\oplus X_6^0\left[23~16\right]$ ， $X_6^2\left[23~16\right]\oplus X_6^0\left[23~16\right]$ ， $\cdots$ ， $X_6^{15}\left[23~16\right]\oplus X_6^0\left[23~16\right]$ ，可以由 $Y_1^0\left[19~16\right]$ ， $Y_2^0\left[15~12\right]$ ， $Y_2^0\left[31~28\right]$ ， $Y_3^0\left[59~56\right]$ ， $Y_3^0\left[55~52\right]$ ， $Y_3^0\left[43~40\right]$ ， $Y_3^0\left[39~36\right]$ ， $Y_3^0\left[27~24\right]$ ， $Y_3^0\left[11~8\right]$ ， $Y_3^0\left[7~4\right]$ ， $Y_4^0\left[63~60\right]$ ， $Y_4^0\left[59~56\right]$ ， $Y_4^0\left[55~52\right]$ ， $Y_4^0\left[51~48\right]$ ， $Y_4^0\left[47~44\right]$ ， $Y_4^0\left[43~40\right]$ ， $Y_4^0\left[39~36\right]$ ， $Y_4^0\left[35~32\right]$ ， $Y_4^0\left[31~28\right]$ ， $Y_4^0\left[27~24\right]$ ， $Y_4^0\left[15~12\right]$ ， $Y_4^0\left[11~8\right]$ ， $Y_4^0\left[7~28\right]$ ， $Y_4^0\left[27~24\right]$ ， $Y_4^0\left[15~12\right]$ ， $Y_4^0\left[11~8\right]$ ， $Y_4^0\left[7~4\right]$ ， $Y_4^0\left[3~0\right]$ ， $Y_5^0\left[63~60\right]$ ， $Y_5^0\left[55~52\right]$ ， $Y_5^0\left[51~48\right]$ ， $Y_5^0\left[27~24\right]$ ， $Y_5^0\left[23~20\right]$ 29个参数表示，其中， $Y_r^0\left[i\right]=X_r^0\left[i\right]\oplus R{K}_r^0\left[i\right]$ 。即 $X_6\left[23~20\right],X_6\left[19~16\right]$ 处，30个4比特差分序列仅有 $2^{29\times 4}=2^{116}$ 种取值，而非 $2^{15\times 2\times 4}=2^{120}$ 种取值。

Table 3. The middle-meeting distinguisher

表3. 搜索到的中间相遇区分器

证明：如图2所示，其中白色表示该半字节位置的差分为零，灰色表示此半字节位置的差分受区分器输入差分影响，黑色表示此半字节位置差分影响区分器的输出差分，同时受区分器输入差分影响。

假设区分器输入差分满足 $\Delta X_1\left[19~16\right]$ 为非零差分，在其他位置均为零差分。猜测 $Y_1^0\left[19~16\right]=X_1\left[19~16\right]\oplus R{K}_1\left[19~16\right]$ ，则第一轮S盒的输入差分已知，因为分组置换、移位操作、异或操作不会改变差分值，因此第一轮的输出差分已知；第二轮输入差分已知，猜测非零差分处的值 $Y_2^0\left[15~12\right],Y_2^0\left[31~28\right]$ ，则第二轮的输出差分已知；同样的，猜测非零差分处的值 $Y_3^0\left[59~56\right],Y_3^0\left[55~52\right],Y_3^0\left[43~40\right],Y_3^0\left[39~36\right],Y_3^0\left[27~24\right],Y_3^0\left[11~8\right],Y_3^0\left[7~4\right]$ ，则第三轮的输出差分已知；猜测非零差分处的值 $Y_4^0\left[63~60\right],Y_4^0\left[59~56\right],Y_4^0\left[55~52\right],Y_4^0\left[51~48\right],Y_4^0\left[47~44\right],Y_4^0\left[43~40\right],$ $Y_4^0\left[39~36\right],Y_4^0\left[35~32\right],Y_4^0\left[31~28\right],Y_4^0\left[27~24\right],Y_4^0\left[15~12\right],Y_4^0\left[11~8\right],Y_4^0\left[7~4\right],Y_4^0\left[3~0\right]$ ，则第四轮的输出差分已知；猜测非零差分处的值 $Y_5^0\left[63~60\right],Y_5^0\left[55~52\right],Y_5^0\left[51~48\right],Y_5^0[27~24],Y_5^0\left[23~20\right]$ 则第五轮的输出差分已知，即 $X_6\left[23~20\right],X_6\left[19~16\right]$ 30个4比特差分序列可以有上述29参数表示。

证毕。

Figure 2. 5 rounds middle meeting distinguisher

图2. 5轮中间相遇区分器

4.2. 9轮中间相遇攻击的具体过程

基于上述的5轮区分器，在前端加一轮，后面接三轮，对9轮Boron-128进行中间相遇攻击，攻击路径如图3所示。攻击分为在线和离线两个部分，具体如下。

4.2.1. 离线阶段

计算120比特差分序列的所有2¹¹⁶种可能值，并存储于哈希表中。

4.2.2. 在线阶段

1) 选择明文 $M^0=X_0^0$ ，猜测密钥 $R{K}_1\left[63~60,51~48,23~20\right]$ ，部分加密 $M^0$ 得到区分器的输入端 $X_1\left[19~16\right]$ 。

Figure 3. 9 round middle meeting attack

图3. 9轮中间相遇攻击示意图

2) 在区分器输入端构造 $\delta$ -集，令 $X_2\left[19~16\right]$ 遍历所有16种可能值，具体为令 $X_2^0\left[23~16\right]$ 异或15种非零差分， $X_2\left[63~20\right]$ 与 $X_2\left[15~0\right]$ 为未知常值。

3) 猜测状态 $Y_1^0\left[39~32,23~20,11~4\right]$ ，部分解密 $\delta$ -集，即可得到明文输入的活跃差分，与 $M^0=X_0^0$ 异或即可得符合5轮区分器特性的16个明文集合，并获得对应的密文。

4) 猜测密钥 $R{K}_9\left[63~56,55~40,39~24,19~8,3~0\right],R{K}_8\left[63~60,51~44,35~28,19~16\right],R{K}_7\left[23~16\right]$ ，部分解密密文得到 $X_2\left[23~16\right]$ 处差分序列。

5) 检查解密所得差分序列是否存在于离线阶段建立的哈希表中。若存在，则猜测密钥作为正确密钥候选值，否则删除错误密钥。在剩余密钥基础上穷搜恢复完整主密钥。

4.3. 复杂度分析

易知构造 $\delta$ -集时猜测的状态 $Y_1^0\left[39~32,23~20,11~4\right]$ 可在密钥 $R{K}_1\left[39~32,23~20,11~4\right]$ 下经过部分加密 $M^0$ 得到，分析Boron-128的密钥关系发现， $R{K}_9\left[63~60\right]$ 可由 $R{K}_1\left[23~20\right]$ 推导而来， $R{K}_9\left[51~48\right]$ 可由 $R{K}_1\left[11~8\right]$ 推导而来， $R{K}_9\left[47~44\right]$ 可由 $R{K}_1\left[7~4\right]$ 推导而来， $R{K}_9\left[39~36\right]$ 可由 $R{K}_1\left[63~60\right]$ 推导而来， $R{K}_9\left[27~24\right]$ 可由 $R{K}_1\left[51~48\right]$ 推导而来， $R{K}_9\left[15~12\right]$ 可由 $R{K}_1\left[39~36\right]$ 推导而来， $R{K}_9\left[11~8\right]$ 可由 $R{K}_1\left[35~32\right]$ 推导而来， $R{K}_8\left[63~60\right]$ 可由 $R{K}_1\left[39~36\right],R{K}_1\left[35~32\right]$ 推导而来， $R{K}_8\left[35~32\right]$ 可由 $R{K}_1\left[11~8\right],R{K}_1\left[7~4\right]$ 推导而来， $R{K}_7\left[23~20\right]$ 可由 $R{K}_1\left[11~8\right],R{K}_1\left[7~4\right]$ 推导而来。因此在线阶段共猜测了28(RK₁) + 8(RK₇) + 24(RK₈) + 56(RK₉)-44 (可用密钥关系推导出的) = 72比特密钥。

攻击所需数据量为2²⁰选择明文，离线阶段时间复杂度为2⁴ × 2¹¹⁶次部分加密，约为2^116.84次9轮Boron-128加密，存储为2¹¹⁶个120比特差分序列，约为2^116.9个64比特块。在线阶段时间复杂度为2⁷² × 2⁴次部分加解密，约为2^72.84次9轮加密。

为了使离线和在线阶段的复杂度达到平衡，采用时间–存储权衡(TMTO)策略，这意味着在离线阶段构建表格时，并不会保存所有2¹¹⁶种可能的差分序列，而是选择按照特定的比例进行保存。假设仅存储 $2^{116-m}$ 种差分序列，则离线阶段时间复杂度为 $2^{116.84-m}$ 次9轮加密，存储为 $2^{116.9-m}$ 个64比特块．在线阶段需重复 $2^m$ 次来保证攻击的成功率，时间复杂度为 $2^{72.84+m}$ 次9轮加密，数据复杂度变为 $2^{20+m}$ 选择明文。

选择 $m=22.00$ ，则攻击总的计算复杂度为 $2^{116.84-m}+2^{72.84+m}=2^{95.84}$ 次9轮加密，存储为2^94.9个64比特块，数据复杂度为2⁴²选择明文。

5. 结论

本文研究了BORON抵抗中间相遇攻击的能力。实验表明对9轮BORON-128中间线相遇攻击所需的数据复杂度为2⁴²个选择明文，时间复杂度为2^95.84次9轮BORON加密，存储复杂度为2^94.9个64比特块。此结果是对BORON安全性分析的重要补充。

基金项目

国家自然科学基金项目(62002184)。