基于SPN结构的分组密码算法ASD

An Lightweight Block Cipher ASD Based on SPN Structure

摘要: 本文提出了一种轻量级分组密码算法ASD，该算法明文长度为64比特，密钥长度为80比特和128比特。算法整体采用SPN结构，混淆层采用16个并置的S盒运算，其中S盒为最优S盒；扩散层为PRESENT该部件的旋转。通过混合整数线性规划(MILP)寻找最小活跃S盒个数进行安全性分析，结果表明ASD具有足够的安全冗余。

Abstract: This paper proposes a lightweight block cipher algorithm ASD, which has a plaintext length of 64 bits with key length of 80 bits and 128 bits. The algorithm adopts SPN structure as a whole, and the confusion layer adopts 16 concurrent S box operations, of which the S box is the optimal S box. The diffusion layer is present for the rotation of the part. Security analysis was performed by mixed in-teger linear programming (MILP) to find the minimum number of active S boxes, and the results showed that ASD had sufficient security margins.

1. 引言

随着信息技术的飞速发展，各类安全问题引起广泛的关注，信息泄露等问题也愈演愈烈，加密成为重要的问题，分组加密算法是现代密码学的重要基础之一，在保护数据的安全和隐私方面发挥着不可替代的作用。5G时代的到来和智能设备的普及，各类应用场景中资源受限的软硬件实现平台对密码算法的实现性质和表现提出了更加严苛的要求，也催生了众多轻量级密码算法设计的新思想。

目前分组密码所采用的整体结构主要为Feistel结构和SPN结构。加解密相似是Feistel结构的一个优点，但扩散速度比较慢。与Feistel结构相比，SPN结构可以实现更快速的扩散。适合资源约束应用的密码需求越来越多，著名的轻量级分组密码算法有CLEFIA [1]，PRESENT [2]，GIFT [3]，Midori [4]。这些密码都是专门针对资源受限的环境而设计的，如RFID标签和传感器网络。而这远远不够，仍需大量可靠的轻量级密码。安全性分析方面，Biham和Shamir提出了差分密码分析 [5]，Matsui于1993年提出线性密码分析 [6]，且广泛应用于各种分组密码。针对这两种分析方法，通常有两种方法评估算法的安全性：一种是计算差分或线性活跃S盒的最小个数，以获得最大概率或绝对线性偏差的上界；另一种是寻找一条好的差分路径或线性迹来计算最大概率或绝对线性偏差。孙等 [7] 提出的基于MILP的自动化搜索算法，可以得到活跃S盒的最小个数和最大概率，目前被广泛应用于各种分组密码算法。

受PRESENT启发，本文提出了一种轻量级的分组密码算法ASD。采用SPN结构来构造ASD算法，算法版本是ASD-64-80和ASD-64-128，支持64比特长度的明文分组以及80比特和128比特的密钥。在整体结构上，ASD算法采用SPN结构设计，S盒采用与PRESENT算法等价的S盒，其各项密码学性质达到最优，为最轻的S盒之一，扩散层采用PRESENT的旋转操作，具有很好的密码学性质。在安全性方面，利用混合整数线性规划的自动化分析方法寻找最少活跃盒个数进行差分分析和线性分析。实验结果表明，ASD算法可以抵抗上述两种攻击。

本文结构安排如下：第二节给出算法的结构，第三节给出算法的设计准则，第四节进行算法分析，最后，总结全文。

2. ASD分组密码算法

ASD是一个轻量级分组密码算法，分组长度支持64比特，密钥长度支持80比特和128比特，分别记作ASD-64-80和ASD-64-128，迭代轮数为31轮。

2.1. 符号

$X$ ：n比特明文

$Y$ ：n比特密文

$R_i$ ：第i轮的轮常数

$K_i$ ：第i轮的轮密钥

$\oplus$ ：异或

$S$ ：4比特S盒

2.2. ASD算法描述

ASD算法整体采用SPN结构，轮函数包含三个步骤：ASD算法整体采用SPN结构，轮函数F包含三个步骤：轮密钥加(AddRoundKey)、S盒替换(SubNibble)、P置换(Permutation)操作。算法结构见图1，其中 $K_i$ 为轮密钥。

Figure 1. Diagram of ASD algorithm structure

图1. ASD算法结构图

2.2.1. 轮密钥加(Add Round Key)

将明文X逐比特异或轮密钥 $K_i$，获得输出状态：

$V=X\oplus K_i$ (1)

其中 $X=\left(x_{63},x_{62},\cdots ,x_0\right)$ 表示64比特明文， $V=\left(v_{63},v_{62},\cdots ,v_0\right)$ 表示轮密钥加以后的状态。

2.2.2. S盒替换(Sub Nibble)

替换是基于半字节的非线性替换，将64比特状态V划分为16个4比特块，进行S盒操作，获得输出状态：

$W=S\left(V\right)$ (2)

其中 $W\triangleq \left(w_{63},w_{62},\cdots ,w_0\right)$ 表示S盒替换完成后的状态，具体见表1。

2.2.3. 扩散层P (Permutation)

将64的状态进行P置换，ASD算法的P置换。输入的第i比特对应输出的第P(i)比特，例如，输入的第0比特对应输出的第63比特，输入的第15比特对应输出的第12比特，具体见表2。

Table 1. S box truth table of ASD algorithm

表1. ASD算法的S盒真值表

Table 2. P Permutation of ASD algorithm

表2. ASD算法的P置换

2.2.4. 密钥扩展

将80比特种子密钥 $K=k_{79}{k}_{78}\cdots k_1{k}_0$ 放置在寄存器中，每轮提取左边64比特作为轮密钥 $K_i=k_{63}{k}_{62}\cdots k_1{k}_0=k_{79}{k}_{78}\cdots k_{17}{k}_{16}$。对K做如下更新：

1) $\left[k_{79}{k}_{78}\cdots k_1{k}_0\right]=\left[k_{18}{k}_{17}\cdots k_{20}{k}_{19}\right]$ ；

2) $\left[k_{79}{k}_{78}{k}_{77}{k}_{76}\right]=S\left[k_{79}{k}_{78}{k}_{77}{k}_{76}\right]$ ；

3) $\left[k_{19}{k}_{18}{k}_{17}{k}_{16}{k}_{15}\right]=\left[k_{19}{k}_{18}{k}_{17}{k}_{16}{k}_{15}\right]\oplus R_i,i=1,2,\cdots ,32$。

首先，将种子密钥K循环右移19比特；然后，将种子密钥最左端的4比特进行S盒操作，为了提高运行效率，密钥扩展算法的S盒采用加密算法中的S盒；最后，将 $k_{19}{k}_{18}{k}_{17}{k}_{16}{k}_{15}$ 这5比特与 $R_i$ 进行异或操作， $R_i$ 取轮密钥最右边的5比特 $k_4{k}_3{k}_2{k}_1{k}_0$。K更新完成。

将128比特种子密钥 $K=k_{127}{k}_{126}\cdots k_1{k}_0$ 放置在寄存器中，每轮提取左边64比特作为轮密钥 $K_i=k_{63}{k}_{62}\cdots k_1{k}_0=k_{127}{k}_{126}\cdots k_{65}{k}_{64}$。对K做如下更新：

1) $\left[k_{79}{k}_{78}\cdots k_1{k}_0\right]=\left[k_{62}{k}_{61}\cdots k_{64}{k}_{63}\right]$ ；

2) $\left[k_{119}{k}_{118}{k}_{117}{k}_{116}\right]=S\left[k_{119}{k}_{118}{k}_{117}{k}_{116}\right]$ ；

3) $\left[k_{99}{k}_{98}{k}_{97}{k}_{96}\right]=S\left[k_{99}{k}_{98}{k}_{97}{k}_{96}\right]$ ；

4) $\left[k_{79}{k}_{78}{k}_{77}{k}_{76}\right]=S\left[k_{79}{k}_{78}{k}_{77}{k}_{76}\right]$ ；

5) $\left[k_{57}{k}_{56}{k}_{55}{k}_{54}{k}_{53}\right]=\left[k_{57}{k}_{56}{k}_{55}{k}_{54}{k}_{53}\right]\oplus R_i,i=1,2,\cdots ,32$。

首先，将种子密钥K循环右移63比特；然后，将种子密钥中间的12比特进行S盒操作，为了提高运行效率，密钥扩展算法的S盒采用加密算法中的S盒；最后，将 $k_{57}{k}_{56}{k}_{55}{k}_{54}{k}_{53}$ 这5比特与 $R_i$ 进行异或操作， $R_i$ 取为轮密钥的中间5比特 $k_{75}{k}_{74}{k}_{73}{k}_{72}{k}_{71}$。K更新完成。

3. 设计准则

3.1. S盒的设计

3.1.1. 相关定义及定理

定义1 (差分均匀度)令S表示一个4 × 4的S盒。对任意非零输入差分和输出差分 $\alpha ,\beta \in F_2^n$，定义集合 $D_S\left(\alpha \to \beta \right)=\left\{x\in F_2^n|S\left(x\oplus \alpha \right)\oplus S\left(x\right)=\beta \right\}$，集合 $D_S\left(\alpha \to \beta \right)$ 中元素的个数为 ${\delta }_S\left(\alpha ,\beta \right)$，则函数S的

差分均匀度为 $\delta \left(S\right)=\underset{\alpha \ne 0,\beta }{\max }{\delta }_S\left(\alpha ,\beta \right)$。

定义2 (线性度)令S表示一个4 × 4的S盒。对任意非零输入掩码和输出掩码 $\alpha ,\beta \in F_2^n$，令 $Im{b}_S\left(\alpha ,\beta \right)=\left|\#\left\{x\in F_2^n|\alpha \cdot x=\beta \cdot S\left(x\right)\right\}-8\right|$，其中，“∙”为内积运算，则函数S的线性度为

$\lambda \left(S\right)=\underset{\alpha ,\beta \in F_2^n,\beta \ne 0}{\max }2Im{b}_S\left(\alpha ,\beta \right)$。

对于任意4 × 4的双射S盒，均有 $\delta \left(S\right)\ge 4$， $\lambda \left(S\right)\ge 8$，使得这两个值都达到最小值的S盒被称为最优S盒。

定义3 (最优S盒 [8])令S表示一个4 × 4的S盒，若满足1) S是双射；2) $\delta \left(S\right)=4$ ；3) $\lambda \left(S\right)=8$ 这三个条件，称其为最优S盒。

Eslice选取最优S盒的规则如下 ：

1) S是双射，即对任意 $x\ne x^{*}$，有 $S\left(x\right)\ne S\left(x^{*}\right)$。

2) 由差分分布表(表3)可知，对任意非零输入差分和输出差分 $\alpha ,\beta \in F_2^n$，有 ${\delta }_S\left(\alpha ,\beta \right)\le 4$，由定义1知， $\delta \left(S\right)=4$。

3) 由线性逼近表(表4)可知，对任意非零输入掩码和输出掩码 $\alpha ,\beta \in F_2^n$，有 $Im{b}_S\left(\alpha ,\beta \right)\le 4$，由定义2知， $\lambda \left(S\right)=8$。

4) S没有不动点，即对任意的 $x\in F_2^4$，有 $S\left(x\right)\ne x$。

定义4 (差分活跃S盒 [9])在一条i轮差分特征 $\Omega =\left({\beta }_0,{\beta }_1,\cdots ,{\beta }_i\right)$ 中，若第j轮( $j\le i$ )的输入差分 ${\beta }_{i-1}$，导致该轮某个S盒的输入差分非零，则称这条差分特征导致该S盒活跃，简称该S盒是差分活跃S盒。

定义5 (线性活跃S盒 [9])在一条i轮线性特征 $\Omega =\left({\beta }_0,{\beta }_1,\cdots ,{\beta }_i\right)$ 中，若第j轮( $j\le i$ )的输出掩码 ${\beta }_{i-1}$，导致该轮某个S盒的输出掩码非零，则称这条线性特征导致该S盒活跃，简称该S盒是线性活跃S盒。

3.1.2. S盒的选取

ASD算法S盒在设计时主要遵循下列准则：

1) 单比特输入差分能引起单比特输出差分的差分特征个数为0；

2) S盒是最优S盒；

3) S盒没有不动点，即对于任意 $v\in F_2^4$，有 $S\left(v\right)\ne v$ ；

4) 单比特输入掩码能引起单比特输出掩码对应偏差非零的线性特征个数为4。

基于上述准则选择了ASD算法的S盒，S盒的选择对于SPN结构算法的安全性具有极大的影响。相较于8比特S盒，之所以选择4比特S盒，是因为8比特S盒不适合轻量级环境。对于选择４比特S盒作为扩散层的分组密码算法，以 Leander等人 [8] 的仿射等价类研究为基础，选择了一个与PRESENT算法的S盒仿射等价的S盒作为ASD算法的S盒。该S盒具有PRESENT算法的S盒所有的优点。

3.2. 扩散层设计

扩散层作为分组密码的核心部分，其目的是提高扩散和混淆程度来实现雪崩效应，这有助于抵抗差分分析、线性分析以及一些未知分析方法的攻击。它的设计不仅影响算法的安全性，还影响分组密码在软硬件中的实现效率,在实际应用中迫切需求具有轻量级的扩散层，采用按比特进行拉线操作的扩散层极大地减少硬件面积以及更好地防御侧信道攻击，因此本文采用比特级拉线操作构造扩散层，且该扩散层具有较高的扩散性能。

3.3. ASD的密钥扩展算法设计

密钥扩展算法设计准则如下：

1) 密钥扩展算法采用与加密算法相同的S盒，以此减少实现代价；

2) 使用轮常数消除对称性；

3) 采用简单的逻辑运算，易于实现。

4. 安全性分析

实验平台的硬件环境为处理器：AMD Ryzen 5 5600U，内存16GB，操作系统：Windows 10。采用MILP搜索算法进行安全性分析。

4.1. 差分分析

差分和线性密码分析是分组密码最强大的技术之一。要使用差分密码分析(DC)攻击n比特分组密码，需要找到一条概率大于 $2^{1-n}$ 的差分传播，差分传播由一组微分特征组成，其概率是具有指定输入差分特征和输出差分特征的概率之和。应用MILP搜索模型，搜索差分活跃S盒个数的方法评估算法抵抗攻击的能力，得到了16轮活跃S盒个数。差分活跃S盒个数的结果见表3：

Table 3. The minimum number of active S box of ASD algorithm

表3. ASD算法活跃S盒的最小个数

通过差分活跃S盒个数的下界评估最大差分概率的上界。本文通过MILP模型搜索了ASD-64的结果，16轮最小差分活跃S盒的个数为32，由S盒的差分分布表(见表4)可知该算法S盒的最大差分概率为2⁻²，因此，估算16轮差分特征的概率约为： $D{P}_{\max }<2^{-2\times 32}=2^{-64}\le 2^{-64}$，根据安全性分析，ASD-64的绝对安全冗余为16轮。实验结果也表明，16轮差分特征概率为 $2^{-70}\le 2^{-64}$，因此，认为该算法能够抵抗差分攻击。

4.2. 线性分析

运用类似差分分析的方法，进一步评估算法抵抗线性攻击的能力。通过估算线性特征中活跃S盒个数的下界，评估线性特征最大偏差概率的上界。采用MILP自动化搜索算法搜索ASD-64的结果，线性活跃S盒个数的结果同差分结果一致，由S盒的线性分布表(见表5)可知该算法S盒的最大线性概率为2⁻²，估算16轮的线性偏差为： $L{P}_{\max }\le 2^{32-1}\cdot 2^{-2\times 32}=2^{-33}$ ；考虑到迭代轮数为31，因此，我们认为该算法能够抵抗线性攻击。

Table 4. Differential Distribution Table of S-box

表4. S盒差分分布表

Table 5. Linear Approximation Table of S-box

表5. S盒线性逼近表

4.3. SPN结构分析

SPN结构中的S是指替换(Substitution)，P是指置换或更广泛的线性变换(Permutation)。SPN结构是目前广泛使用的一种分组密码整体结构，PRESENT，GIFT 和Midori等分组密码都采用该结构。SPN结构的原理是在这种密码结构的每一轮中，首先每一轮的输入经过一个可逆函数S作用，其中可逆函数S由子密钥控制，然后再作用到一个置换P。SPN结构清晰，S层一般被称为混淆层，主要起混淆作用。P一般被称为扩散层，主要起扩散的作用。直观来看，先经过混淆层，再经过扩散层，就很接近Shannon所提出的混淆原则和扩散原则，而现代分组密码将混淆层和扩散层通过整体结构迭代多次，将会增强密码的混淆性和扩散性，使得密码的输入和输出之间的依赖关系更为复杂。和Feistel结构相比，SPN结构优势在于可以得到更快的扩散。综上所述，该结构具有足够的安全性。

5. 总结

本算法采用分组密码算法常用的SPN结构，该结构优点在于适用于资源受限的环境，通过MILP估计了活跃S盒的个数进行计算，以此计算差分特征的概率和线性偏差，实验表明该算法该可以抵抗差分分析和线性分析等安全密码分析，具有绝对安全冗余16轮。