无线传感网络（wireless sensor network, WSN）与射频识别技术（radio frequency identification, RFID）在工业互联网中有着广泛应用，工业互联网的底层集成和使用了大量资源受限的终端设备，例如传感器、智能仪表、可编程控制器等，所生产的海量数据的安全传输是保障工业互联网安全运行的关键，于是，专门为WSN及RFID设计的轻量级加密算法应运而生. 轻量级密码算法的早期典型代表是PRESENT^[1]和LBlock^[2-3]，近几年新提出的算法有GIFT^[4]，WARP^[5].

WARP算法是由Banik等人^[5]在SAC 2020会议上提出来的轻量级分组密码，它具有硬件面积小、能耗低的特点，在大多数典型硬件配置下，是目前128b分组密码中硬件面积最小的. 另外，它在软件实现上也有非常好的表现：在8b微处理器上进行软件实现，在可接受的执行时间内，具有非常有竞争力的短代码长度和极低的RAM能耗；在高端处理器上使用SIMD进行软件实现时，实现效率非常高，适用于计算能力弱、存储空间小等资源受限的物联网加密环境. 多方安全性评估是新密码算法在投入市场之前必有的检验. 设计者^[5]给出了一个21轮不可能差分区分器和一个20轮积分区分器；文献[6]给出了一条19轮差分路径和21轮密钥恢复攻击；文献[7]基于21轮区分器进行了24轮矩形攻击，还给出了一个全轮的相关密钥差分攻击. 相关密钥攻击假设攻击者可以反转密码机里密钥的某些比特位，但在实际应用中攻击者不具有这个权限，该攻击对密码算法安全性不形成实际威胁. 设计者在算法描述文档中曾声明不考虑相关密钥攻击的威胁. 本文用积分分析的方法对WARP进行了单密钥情境下的有效攻击.

积分攻击是针对分组密码算法最有效的攻击方法之一，它是由Daemen等人^[8]在评估分组密码SQUARE时首次提出. 在2002年FSE会议上，Knudsen等人^[9]对此类攻击技术进行了理论上的统一，称之为积分攻击. 积分攻击的关键是寻找一个覆盖轮数尽可能多的积分区分器. 传统的积分区分器构造方法主要有2种：一是通过评估积分性质的传播进行构造的方法；二是代数次数估计方法. 在2015年欧密会上，Todo^[10]提出了可分性的概念，它是积分性质的推广，它的提出为积分区分器的构造带来突破性的进展. 可分性在构造积分区分器时考虑了更多加密原语的代数信息，更准确地描述了积分性质，从而改进了许多加密算法的积分攻击结果^[11-14]. 此外，可分性还可以与多种自动化搜索工具相结合，实现对可分性的自动化搜索^[15-18]. 但是当密码算法的分组规模较大时，对可分性的搜索会受限于计算复杂度和存储复杂度. 目前，一些研究从代数结构层面进行宏观分析和可证安全性探索^[19-20]，在某些算法的分析上取得了优于可分性的积分分析结果，例如，在文献[20]中，作者将SPN（substitution permutation network）密码算法多轮的加密变换表示成F₂^b上的多变量多项式，其中$b$为S盒的输入比特数，研究多变量多项式中出现次数较少的输入字可能带来的密码学性质得到了SKINNY的10轮积分区分器，时间复杂度低于使用可分性得到的积分区分器.

本文中总体框架采用Feistel结构，且F函数采用SP（substitution permutation）结构的分组密码称为Feistel-SP类分组密码^[21]. 本文的研究动机来源于Zhang等人^[20]的工作以及WARP算法的问世. 借鉴文献[20]方法的核心思想，本文也把输出字写成输入字的多变量多项式，基于多变量多项式中输入字的出现次数讨论分组密码基于代数结构的积分性质. 在研究过程中，发现了某种代数结构的密码算法具有积分性质，并通过分组密码S盒差分分布表（difference distribution table, DDT）的特性：|{x| x∈F₂^b∧（S（x）⊕S（x⊕u）=d）}|为偶数，证明了这一性质. 利用该性质，可以找到某些覆盖轮数更多的积分区分器，从而改进利用代数结构进行积分分析的方法. 另外，通过对几个Feistel-SP结构分组密码的结构进行分析，发现此分析方法可从分析SPN分组密码扩展到分析Feistel-SP分组密码上，并将改进的积分分析方法应用到Feistel-SP分组密码WARP算法上，构造了2个数据复杂度为2¹¹⁶的22轮积分区分器，基于该区分器给出26轮积分攻击，而WARP设计者只给出1个数据复杂度为2¹²⁴的20轮积分区分器，且认为最多可进行21轮攻击. 为了验证所给方法和理论的正确性，对用此方法所构造的18轮积分区分器做了实际实现，其复杂度为2³²，耗时7.1 h. 将本文的结果与之前所有单密钥情境下的攻击结果进行了对比，如表1所示. 结果表明，本文的积分攻击是目前对WARP可验证的最好的密钥恢复攻击结果.

表  1  单密钥情境下对WARP的密钥恢复攻击

Table  1.  Key-Recovery Attacks on WARP in the Single-Key Scenario

攻击方式	区分器 轮数	区分器数据 复杂度/概率	攻击 轮数	攻击数据 复杂度	来源
Diff	19				文献[5]
ID	21				文献[5]
Inte	20	2124	21	≈2128	文献[5]
Diff	19	2−132	21	2113	文献[6]
Diff	18	2−104.62	23	2106.68	文献[7]
Rect	21	2121.11	24	2125.18	文献[7]
Inte	22	2116	26	2119.5	本文第3节
注：Diff：差分攻击；ID：不可能差分攻击；Inte：积分攻击；Rect：矩形攻击.

下载: 导出CSV 

| 显示表格

1.   预备知识

本节简要介绍积分分析方法、文中用到的基本符号和定义，以及WARP算法描述.

1.1   积分分析

积分分析的主要思想是选择特定的明文集合，一般是对明文的某些比特位进行遍历（称为活跃比特），其余的明文比特位固定（称为常量比特），对选定的明文集合进行加密，对得到的所有密文值逐比特位异或求和（称为积分），若积分中的某些比特位恒为0（与密钥和常量比特无关），则称这些比特位是平衡的，即$H:{F}_{2}^{m}\to {F}_{2}^{w},\displaystyle\sum _{x\in {F}_{2}^{m}}H\left(x\right)=0$. 而对于均匀分布的随机变量而言，积分的每一比特位等于0的概率为1/2，攻击者通过积分值的非随机性将目标算法与随机置换区分，并恢复某些密钥比特位.

1.2   二元关系

定义1^[22]. 由2个元素x和y（x，y可属于不同集合）按一定顺序排列成的二元组称作一个有序对，记作〈x, y〉,其中x是第1元素，y是第2元素.

定义2^[22]. 如果一个集合满足条件之一：1） 集合非空，且它的元素都是有序对；2） 集合是空集. 则称该集合为一个二元关系.

定义3^[22]. 设U，G为二元关系，U和G的复合记作U _° G，其中U _° G={〈x, y〉|∃t使得〈x, t〉∈U∧〈t, y〉∈G}.

1.3   WARP算法描述

WARP算法的分组长度以及密钥长度都是128b，它采用32分支的Feistel-SP结构，F函数是SP结构，迭代次数为41轮. 加密时，128b明文表示成32个半字节X=（x₀, x₁, …, x₃₁）, x_i∈{0, 1}⁴，加载到128b的初始状态Q⁰中，把r轮加密后的中间状态记作Q^r，将它也表示成32个半字节：Q^r=（q₀^r, q₁^r, …, q₃₁^r），q_i^r∈{0, 1}⁴. 128b密钥K分为2个64b子密钥K=（K⁰, K¹），K⁰，K¹∈{0, 1}⁶⁴. 在第r轮加密时，将K^{（r+1）mod2}作为轮密钥使用. Kⁱ表示成16个半字节，Kⁱ=（k₀ⁱ, k₁ⁱ, …, k₁₅ⁱ），k_jⁱ∈{0, 1}⁴. 每一轮，每2个分支按顺序异或1个k_jⁱ. F函数包括16个4比特S盒、加轮密钥、加轮常数（只加到1，3分支上）以及以字为单位的32个元素的置换操作π. WARP算法最后一轮轮函数不包括置换操作π. 轮函数流程如图1所示. 置换操作π及逆置换π⁻¹如表2所示.

图  1  WARP算法的轮函数

Figure  1.  The round function of WARP

下载: 全尺寸图片 幻灯片

表  2  WARP算法中面向32个半字节的置换π和π⁻¹

Table  2.  Shuffle π and π⁻¹ of WARP on 32 Nibbles

x	π（x）	π−1（x）		x	π（x）	π−1（x）
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	31 6 29 14 1 12 21 8 27 2 3 0 25 4 23 10	11 4 9 10 13 22 1 30 7 28 15 24 5 18 3 16		16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31	15 22 13 30 17 28 5 24 11 18 19 16 9 20 7 26	27 20 25 26 29 6 17 14 23 12 31 8 21 2 19 0

下载: 导出CSV 

| 显示表格

因为在本文中S盒细节以及轮常数取值不影响对算法的分析，所以忽略S盒细节及轮常数描述. 解密过程与加密过程类似，只是将置换π换成π⁻¹，轮常数逆序使用. 具体加密过程为：

首先，将128 b明文X加载到128 b的初始状态Q⁰中，然后迭代运行41轮. 当轮数r=1, 2, …, 40时，轮函数包含4个步骤.

1） $t_{2i}^r=q_{2i}^{r-1}，0\leqslant i \leqslant 15$；

2）$t_{2 i+1}^r=S\left(q_{2 i}^{r-1}\right) {\text{⊕}} k_i^{(r+1) \bmod 2} {\text{⊕}} q_{2 i+1}^{r-1} {\text{⊕}} R C_i^{{{r}}}，0\le i\le 1$；

3）$t_{2 i+1}^r=S\left(q_{2 i}^{r-1}\right) {\text{⊕}} k_i^{(r+1) \bmod 2} {\text{⊕}} q_{2 i+1}^{r-1}， 2\le i\le 15$；

4） $q_{i}^{{{r}}}$=$t_\lambda^{{r}} ,\lambda=\pi^{-1}({{i}}) , 0\leqslant {{i}}\leqslant31$.

当r=41时，轮函数只包含1）~3）步骤. 41轮结束后，密文${\boldsymbol{Y}}=\left(t_0^{41}, t_1^{41}, … , t_{31}^{41}\right)$.

解密过程略. 关于WARP算法的详细描述，请参见文献[5].

2.   利用代数结构构造积分区分器的框架

首先简要回顾文献[20]中利用代数结构构造SPN分组密码积分区分器的主要思想：把明文字（密文字）用中间状态字的多变量多项式表示出来，通过统计中间状态字在多变量多项式中出现的次数来构造积分区分器. 给定的分组密码的代数结构通过多变量多项式体现出来，用以评估抵抗攻击的安全性. 我们发现该思想同样适用于Feistel-SP结构分组密码，并且攻击效果更佳. 该文献指出可用S盒的置换性质构造积分区分器，定理1描述了该性质.

定理1. 设S_i（x），i=0,1,…,n−1，是F₂^b上的n个置换，c_i为常数，则S_n−1（…S₁（S₀（x⊕c₀）⊕c₁）…⊕c_n−1）也是F₂^b上的一个置换，从而

本文将用$（x）表示置换S_n−1（…S₁（S₀（x⊕c₀）⊕c₁）…⊕c_n−1）. 定理1表明，若中间状态字在密文字的表达式里只出现1次，则当中间状态字遍历时，密文字是平衡的. 在研究过程中，发现了某种代数结构的密码算法具有积分性质，可以用中间状态字的多变量多项式进行判别，并将某些积分区分器扩展至更多轮数，见定理2.

定理2. 设S（x）是F₂^b上的置换，并且u和v是常数，则

证明. 在S盒的DDT中，任意一个元素都是偶数，即对∀ u，d∈F₂^b，都有|{x| x∈F₂^b∧（S（x）⊕S（x⊕u）=d）}|是偶数. 所以当x取遍F₂^b时，S（x）⊕S（x⊕u）的每个值都会出现偶数次. 从而u和v是常数时，$\displaystyle\sum _{x\in {F}_{2}^{b}}S\left(S\left(x\right){\text{⊕}} S\left(x {\text{⊕}} u\right){\text{⊕}} v\right)=0$. 证毕.

定理2表明，虽然中间状态字在密文字里出现2次，但是若以S（S（x）⊕S（x⊕u）⊕v）的形式出现，则当中间状态字遍历时，密文字也是平衡的. 借鉴文献[20]给出的构造积分区分器的思想，辅助运用定理1和定理2，给出了一个构造SPN结构和Feistel-SP结构分组密码积分区分器的通用框架. 在介绍通用框架之前，本节先给出构造过程中用到的一些概念.

令Trail_e^r=〈q_j, Γ〉表示一个有序对，q_j表示某个中间状态字，Γ表示一个包含某些密文字的集合. 这些密文字是从中间状态Q开始经过r轮加密而得. Trail_e^r=〈q_j, Γ〉表示当q_j取遍F₂^b时，Γ中的每一个密文字都平衡. 我们把对应r轮的所有有序对Trail_e^r构成的集合记作二元关系T_e^r.

令Trail_d^r=〈Ф, q_j〉表示一个有序对，Ф表示一个包含某些明文字的集合，这些明文字是从中间状态Q开始经过r轮解密而得，q_j表示某个中间状态字. Trail_d^r=〈Ф, q_j〉表示当Ф中的明文字活跃而其余的明文字固定为常数时，经过r轮加密后，得到若干个中间状态的结构，在每个结构中，q_j是活跃的而其他中间状态字为常数. 我们把对应r轮的所有Trail_d^r构成的集合记作二元关系T_d^r.

当一个Trail_e^α中的第1元素和一个Trail_d^β中的第2元素相同时，一个α+β轮的积分区分器就可以通过连接Trail_e^α和Trail_d^β得到. 例如，连接Trail_e⁵=〈q₇, {y₃, y₁₅}〉和Trail_d¹⁰=〈{x₃, x₉, x₂₃}, q₇〉可以得到一个5+10=15轮的积分区分器{x₃, x₉, x₂₃}→{y₃, y₁₅}，即令x₃, x₉, x₂₃活跃，其他明文字为常数，加密15轮后密文字y₃, y₁₅平衡. 求T_d^β_° T_e^α可以得到所有α+β轮积分区分器. 当轮数并不具体时，本文分别用Trail_e, Trail_d, T_e, T_d来表示Trail_e^r, Trail_d^r, T_e^r, T_d^r.

构造积分区分器的框架包括3个步骤：1）构造T_e；2）构造T_d；3）求T_{d °} T_e.

假设所讨论的分组密码为E：F₂^b×n→F₂^b×n，明文X、密文Y和中间状态Q分别划分成n个字X=（x₀, x₁, …, x_n−1），Y=（y₀, y₁, …,y_n−1），Q=（q₀，q₁, …, q_n−1），其中x_i，y_i，q_i∈F₂^b，b是字长.

步骤1. 构造T_e.

本步骤关注从中间状态Q开始，经过r轮加密得到Y的加密过程. 把每个密文字y_i用中间状态字q₀, q₁, …, q_n−1表示出来，然后统计每个中间状态字q_j在每个密文字y_i表达式中出现的次数. 当加密轮数超过某个数值r_e时，每个中间状态字q_j在每个密文字y_i表达式中至少出现1次，小于数值r_e时，有些中间状态字在某些密文字表达式中出现次数为0，r_e即加密方向全扩散的轮数. 假设q_a在加密r_e轮后的密文字y_b的表达式中只出现1次，根据定理1，当q_a活跃，其他中间状态字固定为常数时，加密r_e轮后，密文字y_b是平衡的，这样可以得到一个${T rail}_{\mathrm{{{e}}}}^{{r}_{\mathrm{e}}}$= 〈q_a,{y_b}〉.

接下来本节继续探究是否存在加密轮数超过r_e的Trail_e^r. 借助于实验寻找加密更多轮后积分为0的密文字，依次穷举单个q_j，即每次令一个中间状态字q_j活跃，其他中间状态字为常数，求出r_e+u（u$\ge$0）轮加密后每个密文字的积分，筛选出积分为0的密文字. 但是实验是在选定密钥下进行，更换密钥后，这些密文字积分未必仍为0. 通过分析实验筛选出的密文字的多变量多项式结构，根据定理1和定理2确定它们是否是平衡的. 找到存在平衡字的最大加密轮数r_e+u，获得一个对应轮数最长的${T rail}_{\mathrm{e}}^{{r}_{\mathrm{e}}+u}= 〈 {q}_{j},\{{y}_{{i}_{0}}, {y}_{{i}_{1}},… , {y}_{{i}_{k-1}}\} 〉$. 有时候，尽管没有平衡的密文字，但是密文字的（非）线性组合是平衡的，就将组合设置为${T rail}_{\mathrm{e}}^{{r}_{\mathrm{e}}+u}$的第2元素. 得到的有序对${T rail}_{\mathrm{e}}^{{r}_{\mathrm{e}}+u}$不一定唯一，所有${T rail}_{\mathrm{e}}^{{r}_{\mathrm{e}}+u}$构成二元关系${T}_{\mathrm{e}}^{{r}_{\mathrm{e}}+u}$.

步骤2. 构造T_d.

本步骤关注从中间状态Q开始，经过r轮解密得到明文X的解密过程. 把每个明文字x_i用中间状态字q₀, q₁, …, q_n−1表示出来，然后统计q_j在x_i中出现的次数. 将解密方向全扩散的轮数记作r_d，则解密r_d−1轮时，至少存在1个q_j在某些明文字的多变量多项式表达式中出现的次数为0. 设q_j在其表达式中出现次数不为0的明文字为${x}_{{l}_{0}}, {x}_{{l}_{1}}, … , {x}_{{l}_{v-1}}$，出现次数为0的明文字为${x}_{{l}_{v}}, {x}_{{l}_{v+1}}, … , {x}_{{l}_{n-1}}$. 令${x}_{{l}_{0}}, {x}_{{l}_{1}}, … , {x}_{{l}_{v-1}}$活跃，${x}_{{l}_{v}}, {x}_{{l}_{v+1}}, … , {x}_{{l}_{n-1}}$为常数，得到一个明文集M，对其加密r_d−1轮后得到中间状态值的集合J，|M|=|J|=2^v×b. 把J做如下划分：{q₀, q₁, …, q_n−1}\ {q_j}相等的元素属于同一个子集. 这样所得每个子集中元素的{q₀, q₁, …, q_n−1}\{q_j}为常数，q_j必活跃；否则，若存在中间状态值$\rho$，$\rho$的{q₀, q₁, …, q_n−1}\{q_j}与一子集中元素的{q₀, q₁, …, q_n−1}\{q_j}相等，但不属于J. 将$\rho$解密r_d−1轮，因为q_j不影响$\left\{{x}_{{l}_{v}}, {x}_{{l}_{v+1}}, … , {x}_{{l}_{n-1}}\right\}$，$\rho$对应明文的$\left\{{x}_{{l}_{v}}, {x}_{{l}_{v+1}}, … , {x}_{{l}_{n-1}}\right\}$与该子集中元素对应明文的$\left\{{x}_{{l}_{v}}, {x}_{{l}_{v+1}}, … , {x}_{{l}_{n-1}}\right\}$相等，所以$\rho$对应明文属于M，这与$\rho$不属于J矛盾. 因此每个子集必包含2^b个元素. 所以J可以划分成2^{（v−1）×b}个结构，每个结构中q_j是活跃的，其他中间状态字为常数. 据此得到${T rail}_{\mathrm{d}}^{{r}_{\mathrm{d}}-1}= 〈 \left\{{x}_{{l}_{0}}, {x}_{{l}_{1}}, … , {x}_{{l}_{v-1}}\right\}, {q}_{j} 〉$，${T rail}_{\mathrm{d}}^{{r}_{\mathrm{d}}-1}$不一定唯一，所有${T rail}_{\mathrm{d}}^{{r}_{\mathrm{d}}-1}$构成二元关系${T}_{\mathrm{d}}^{{r}_{\mathrm{d}}-1}$.

步骤3. 求T_{d °} T_e.

求${T}_{\mathrm{d}}^{{r}_{\mathrm{d}}-1}$_°${T}_{\mathrm{e}}^{{r}_{\mathrm{e}}+u}$，得到的二元关系复合中的每个有序对由1对具有相同q_j的${T rail}_{\mathrm{d}}^{{r}_{\mathrm{d}}-1}$和${T rail}_{\mathrm{e}}^{{r}_{\mathrm{e}}+u}$生成，对应一个r_d−1+r_e+u轮积分区分器$\left\{{x}_{{l}_{0}},{x}_{{l}_{1}},… ,{x}_{{l}_{v-1}}\right\}\to \{{y}_{{i}_{0}},{y}_{{i}_{1}},… ,{y}_{{i}_{k-1}}\}$. 这个积分区分器意味着当明文字${x}_{{l}_{0}},{x}_{{l}_{1}},… ,{x}_{{l}_{v-1}}$活跃，其他明文字固定为常数时，经过r_d−1+r_e+u轮加密后得到的密文${y}_{{i}_{0}},{y}_{{i}_{1}},… ,{y}_{{i}_{k-1}}$是平衡的. 如果${T}_{\mathrm{d}}^{{r}_{\mathrm{d}}-1}$_°${T}_{\mathrm{e}}^{{r}_{\mathrm{e}}+u} =\varnothing$，则寻找减轮的T_d或T_e，直到T_{d °} T_e≠$\varnothing$，从而得到积分区分器.

3.   对WARP算法的积分分析

设计者利用MILP和可分性，给出了一个需要2¹²⁴个选择明文（令31个明文字活跃）的20轮积分区分器，设计者认为利用该积分区分器最多只能实现21轮密钥恢复攻击. 本节中利用多变量多项式的代数结构分析方法给出了2个只需要2¹¹⁶个选择明文（令29个明文字活跃）的22轮积分区分器，并且利用该积分区分器，至少可以实现26轮密钥恢复攻击. 为方便实验验证，本文特地给出了一个时间复杂度为2³²的18轮可实现积分区分器.

3.1   构造20轮积分区分器

根据第2节给出的框架，分3步来构造WARP的积分区分器.

步骤1. 构造T_e.

假设从中间状态Q=（q₀, q₁, …, q₃₁）加密r轮后得到密文Y=（y₀, y₁, …, y₃₁），将每个密文字y_i用q₀, q₁, …, q₃₁表示出来，然后统计中间状态字q_j在y_i中出现的次数. 具体做法如下所示.

当r=1时，用中间状态字q₀, q₁, …, q₃₁把1轮加密后的密文字y₀, y₁, …, y₃₁表示出来，请见附录A中式（A1）.

迭代1轮加密的表达式，得到r=2, 3, …, 10轮后每个密文字y_i的多变量多项式表达式. 由1轮加密表达式可以看出，中间状态字q_j在r轮密文字y_i中出现次数等于q_j在某些r−1轮密文字中出现次数之和，编程迭代计算可以得到每个中间状态字在每个r轮密文字中出现的次数. 我们发现10轮时达到了全扩散，即每个q_j在每个y_i的表达式中至少出现1次，如图2所示. 图2中的（i, j）元素表示第j个中间状态字在第i个密文字中出现的次数. 假设q_u在y_v的表达式中恰好出现1次，则令q_u活跃，其他中间状态字固定为常数，加密10轮之后的密文字y_v是平衡的.

图  2  加密10轮后q_j在y_i的表达式中出现的次数

Figure  2.  The number of times q_j appears in y_i after 10-round encryption

下载: 全尺寸图片 幻灯片

接下来，本文借助于实验寻找加密更多轮后积分为0的密文字. 依次令单个中间状态字q_j活跃，其余的31个中间状态字固定，观察加密多于10轮后是否仍存在积分为0的密文字. 实验发现加密11轮和12轮后依然存在积分为0的密文字，但这些密文字是否真正平衡需要根据定理1和定理2对该密文字表达式的代数结构进行判断. 例如，令q₃活跃，其他中间状态字固定，加密12轮之后的密文字y₁₅的积分为0. q₃在y₁₅表达式中出现4次，写出y₁₅的代数表达式（详见附录B），发现该表达式结构为：y₁₅=S（S（x⊕α）⊕S（x）⊕β）⊕$（q₃）⊕$′（q₃）⊕γ，其中x=S（q₂）⊕$k_0^1$⊕q₃⊕$RC_1^0$，α，β，γ是不包含q₃的项，$（q₃）和$′（q₃）是定理1中所示S盒的复合，q₃在其中各出现1次. 当q₃活跃，其他中间状态字为常数时，根据定理1和定理2，y₁₅平衡. 从而可以得到一个Trail_e¹²=〈q₃,{y₁₅}〉. 同样的方法，可以得到另一个Trail_e¹²=〈q₁₉,{y₃₁}〉. 另外还有若干个11轮的Trail_e.

T_e¹²={〈q₃,{y₁₅}〉, 〈q₁₉,{y₃₁}〉}.

T_e¹¹={〈q₁₄,{y₁₅}〉,〈q₃₀,{y₃₁}〉,…}.

步骤2. 构造T_d.

假设从中间状态Q开始解密r轮得到明文X=（x₀, x₁, …, x₃₁），用q₀, q₁, …, q₃₁把每个明文字x_i表示出来，并统计q_j在每个x_i的表达式中出现的次数.

当r=1时，用中间状态字q₀, q₁, …, q₃₁把一轮解密后的明文字x₀, x₁, …, x₃₁表示出来，请见附录A中式（A2）.

迭代一轮解密的表达式，得到r=2, 3, …, 10轮解密后的每个明文字x_i的表达式，并统计每个中间状态字q_j在其中出现的次数，发现与加密相同，解密10轮时达到了全扩散. 解密9轮时，存在q_j在某些x_i的表达式中出现次数为0，例如，q₀在x₁₆，x₂₆，x₂₈的表达式中出现次数为0，从而可以得到一个Trail_d⁹=〈A\{x₁₆, x₂₆, x₂₈}, q₀〉，本文中令A={x₀, x₁, …, x₃₁}，x_i∈{0,1}⁴. 通过解密9轮后q_j在x_i的表达式中出现的次数，如图3所示，可以找到所有Trail_d⁹，从而得到二元关系T_d⁹. 图3中的（i, j）元素表示第j个中间状态字在第i个明文字中出现的次数.

图  3  解密9轮后q_j在x_i的表达式中出现的次数

Figure  3.  The number of times q_j appears in x_i after 9-round decryption

下载: 全尺寸图片 幻灯片

T_d⁹={〈 A\{x₁₆, x₂₆, x₂₈}, q₀〉，〈A\{x₆, x₂₂, x₂₄}, q₂〉，〈A\{x₂₈}, q₄〉, 〈A\{x₁₆}, q₆〉, 〈A\{x₁₆, x₂₂}, q₈〉, 〈A\{ x₃₀}, q₁₀〉, 〈A\{x₂₀, x₃₀}, q₁₂〉, 〈A\{x₈, x₁₄, x₁₈}, q₁₄〉, 〈A\{x₀, x₁₀, x₁₂}, q₁₆〉, 〈A\{x₆, x₈, x₂₂}, q₁₈〉, 〈A\{x₁₂}, q₂₀〉, 〈A\{x₀}, q₂₂〉, 〈A\{x₀, x₆}, q₂₄〉, 〈A\{x₁₄}, q₂₆〉, 〈A\{x₄, x₁₄}, q₂₈〉, 〈A\{x₂, x₂₄, x₃₀}, q₃₀〉}.

用同样的方法得到二元关系T_d⁸.

步骤3. 求T_d°T_e.

T_d⁹_° T_e¹²=$\varnothing$，T_d⁹_° T_e¹¹= T_d⁸_° T_e¹²={〈A\{x₈, x₁₄, x₁₈}, {y₁₅}〉, 〈A\{x₂, x₂₄, x₃₀}, {y₃₁}〉}，从而得到了2个20轮积分区分器.

20轮积分区分器Ⅰ: 令集合{x_i|i∈{0, 1, …, 31}\ {8, 14, 18}}中的每个明文字活跃，x₈，x₁₄，x₁₈为常数，经过20轮加密后，y₁₅是平衡的.

20轮积分区分器Ⅱ：令集合{x_i|i∈{0, 1, …, 31}\ {2, 24, 30}}中的每个明文字活跃，x₂，x₂₄，x₃₀为常数，经过20轮加密后，y₃₁是平衡的.

2个积分区分器的数据复杂度都是2^29×4=2¹¹⁶个选择明文，低于设计者给出的积分区分器的复杂度2^31×4=2¹²⁴个选择明文.

3.2   扩展为22轮积分区分器

Feistel结构轮函数具有如下特点，有一半状态没有变化，直接赋值给下一轮的状态比特，同时这半数状态经过轮函数后和剩下的另一半状态异或后赋值给下一轮的另一半状态. 通过观察WARP轮函数的加解密代数表达式发现，每个中间状态字都可以被它的前一轮或者后一轮的2个状态字、密钥字和轮常数表示出来. 特别是，轮密钥的异或发生在S盒之后. 利用这一特性，可以将3.1节所得20轮积分区分器向解密方向和加密方向各扩展1轮，得到22轮积分区分器.

以20轮积分区分器Ⅰ为例，该区分器由T_d⁹中的有序对〈A\{x₈, x₁₄, x₁₈}, q₁₄〉与T_e¹¹中的有序对〈q₁₄, {y₁₅}〉连接而成. 我们将其置于22轮积分区分器的第1~21轮的位置，q₁₄为第10轮的中间状态字$q^{10}_{14}$，如图4所示.

图  4  22轮积分区分器

Figure  4.  A 22-round integral distinguisher

下载: 全尺寸图片 幻灯片

有序对〈A\{x₈,x₁₄,x₁₈},q₁₄〉表示当解密9轮时，$q^{10}_{14}$在第1轮的x₈，x₁₄，x₁₈中没有出现，如果继续再解密1轮，在第0轮的每个明文字中就都出现了. 但用第0轮的明文字把第1轮的x₈，x₁₄，x₁₈表示出来后发现，第0轮的明文字的如下组合不包含$q^{10}_{14}$：

其中$x^{i}_{j}$表示第i轮的第j个字. 所以22轮积分区分器需要{x_i|i∈{0, 1, …, 31}\{3, 7, 25}}集合中的明文字活跃，S（x₂）⊕x₃，S（x₆）⊕x₇，S（x₂₄）⊕x₂₅为常数.

在20轮区分器Ⅰ中$y_{15} ^{21}$是平衡的，而$y_{15} ^{21}$可以表示成2个22轮密文字的组合：$y_{15} ^{21}$= S（$y_{23} ^{22}$）⊕$y_{10} ^{22}$⊕$k_{j'} ^{i'}$，其中$y^{i}_{j}$表示第i轮的第j个字，如图5所示. $y_{15} ^{21}$平衡当且仅当S（$y_{23} ^{22}$）⊕$y_{10} ^{22}$平衡，所以区分器在加密方向也扩展1轮，从而得到22轮积分区分器Ⅰ.

图  5  平衡的密文字组合

Figure  5.  The balanced combinations of ciphertext

下载: 全尺寸图片 幻灯片

22轮积分区分器Ⅰ：令{x_i|i∈{0, 1, …, 31}\{3, 7, 25}}中的明文字活跃，S（x₂）⊕x₃，S（x₆）⊕x₇，S（x₂₄）⊕x₂₅为常数，加密22轮后S（$y_{23}^{22}$）⊕$y_{10}^{22}$是平衡的.

该区分器各轮状态与$q^{10}_{14}$的依赖关系如图6所示. 可用同样的方法将20轮积分区分器Ⅱ扩展为22轮积分区分器Ⅱ.

图  6  22轮区分器中对$q^{10}_{14}$的依赖关系迹

Figure  6.  The trail of the dependence on $q^{10}_{14}$ in the 22-round distinguisher

下载: 全尺寸图片 幻灯片

22轮积分区分器Ⅱ：令{x_i|i∈{0, 1, …, 31}\{9, 23, 19}}中的明文字活跃，S（x₈）⊕x₉，S（x₂₂）⊕x₂₃，S（x₁₈）⊕x₁₉为常数，加密22轮后S（$y_{7}^{22}$）⊕$y_{26}^{22}$是平衡的.

2个22轮积分区分器的数据复杂度仍然是 2¹¹⁶个选择明文.

3.3   构造18轮可实验验证的积分区分器

当减少构造区分器的Trail_d的轮数时，区分器所需的活跃明文字个数也会减少. 用一个Trail_d⁵和一个Trail_e¹¹通过q₁₄连接，构造了一个16轮积分区分器：令{x₀, x₁, …, x₃₁}中的{x₅, x₁₄, x₁₅, x₁₈, x₁₉, x₂₀, x₂₁, x₂₇}明文字活跃，其余的明文字为常数，加密16轮后，y₁₅平衡. 然后将此区分器分别在解密方向和加密方向各扩展1轮，得到一个18轮积分区分器，即：令明文字x₃, x₆, x₈, x₁₆, x₂₂, x₂₅, x₂₆, x₂₉活跃，令x₇⊕S（x₆）, x₉⊕S（x₈）, x₁₇⊕S（x₁₆）, x₂₃⊕S（x₂₂）, x₂₇⊕S（x₂₆）, x₀, x₁, x₂, x₄, x₅, x₁₀, x₁₁, x₁₂, x₁₃, x₁₄, x₁₅, x₁₈, x₁₉, x₂₀, x₂₁, x₂₄, x₂₈, x₃₀, x₃₁为常数，加密18轮后，S（y₂₃）⊕y₁₀平衡. 该区分器的数据复杂度为2^8×4=2³²个选择明文，随后在配置为Intel Xeon E5-2670 v2 @2.5 GHz, 2.49 GHz，16.00 GB RAM的服务器上进行了实验，运行时间为7.1 h，证实了结论的正确性.

3.4   对WARP算法的26轮积分攻击

基于22轮积分区分器，利用部分和技巧^[2,23]在区分器尾部加4轮，对26轮WARP进行了密钥恢复攻击.

以22轮积分区分器Ⅰ为例，判断准则为S（$y_{23}^{22}$）⊕ $y_{10}^{22}$平衡，利用解密方向的表达式，将$y_{10}^{22}$和$y_{23}^{22}$分别用26轮的密文字和23~26轮所用的轮密钥字表示为:

2个表达式中包含13个26轮密文字和10个轮密钥字.

攻击步骤有3步：

1） 构造一个包含2¹¹⁶个明文的明文集. 根据22轮积分区分器Ⅰ，该明文集的结构为：令集合{x_i|i∈{0, 1, …, 31}\{3, 7, 25}}中的明文字活跃，S（x₂）⊕x₃, S（x₆）⊕x₇, S（x₂₄）⊕x₂₅为常数. 设置一个52b的变量d，对应在式（6）（7）中出现的13个26轮密文字d= $y_{2}^{26}$||$y_{5}^{26}$||$y_{7}^{26}$||$y_{11}^{26}$||$y_{14}^{26}$||$y_{17}^{26}$||$y_{18}^{26}$||$y_{21}^{26}$||$y_{24}^{26}$||$y_{26}^{26}$||$y_{27}^{26}$||$y_{29}^{26}$||$y_{31}^{26}$. 对这个明文集加密26轮，统计d的每个值出现次数. 然后根据统计值筛选d的值，将出现偶数次的值丢弃，留下出现奇数次的值，构成集合D. 至多留下2⁵²个不同的d的值，即|D|≤2⁵².

2） 猜测式（6）（7）中出现的10个密钥字$k_{1}^{0}, k_{2}^{0}, k_{4}^{0}, k_{11}^{0}, k_{12}^{0}, k_{15}^{0} , k_{0}^{1} , k_{5}^{1} , k_{11}^{1}, k_{14}^{1}$的值，然后将猜测值和D中每个值所对应的$y_{2}^{26}$, $y_{5}^{26}$, $y_{7}^{26}$, $y_{11}^{26}$, $y_{14}^{26}$, $y_{17}^{26}$, $y_{18}^{26}$, $y_{21}^{26}$, $y_{24}^{26}$, $y_{26}^{26}$, $y_{27}^{26}$, $y_{29}^{26}$, $y_{31}^{26}$代入2个表达式中，求S（$y_{23}^{22}$）⊕$y_{10}^{22}$的值. 当$\mathop {\text{⊕}} \limits_{\forall d \in D}$（S（$y_{23}^{22}$）⊕$y_{10}^{22}$）=0时，此时10个密钥字的猜测值为正确值的候选值. 本步骤最多需要做2^4×10+52=2⁹²次多项式计算，多项式计算指利用式（6）（7）计算S（$y_{23}^{22}$）⊕$y_{10}^{22}$.

3） 每个错误的密钥猜测值通过步骤2）的概率为2⁻⁴，共有2⁴⁰−1个错误的密钥猜测值，所以需要构造11个相同结构的明文集，重复步骤1）到步骤2）的操作，筛掉所有的错误密钥猜测值，最后得到正确的 $k_{1}^{0}, k_{2}^{0}, k_{4}^{0}, k_{11}^{0}, k_{12}^{0}, k_{15}^{0} , k_{0}^{1} , k_{5}^{1} , k_{11}^{1}, k_{14}^{1}$的值. 对26轮WARP进行积分攻击的总过程大约需要11×2¹¹⁶≈2^119.5次加密.

在3.3节给出的18轮区分器尾部加1轮，对19轮WARP进行可实现的密钥恢复攻击，可以恢复4b密钥$k_{11}^0$，本文在同一个服务器上进行了实验，运行时间约为7.6 h，验证了该攻击方法的正确性.

4.   总　　结

本文将明密文字用中间状态字的多变量多项式来表示，通过对多变量多项式进行分析，发现了一类代数结构具有的积分特性，用该性质改进了SPN和Feistel-SP分组密码积分分析的结果. 将该方法应用于WARP算法，分析轮数由原来设计者给出的21轮提高到26轮. 据我们所知，该区分器和密钥恢复攻击是迄今为止单密钥情境下最好的结果.

作者贡献声明：邢朝辉负责分析方法的理论分析、实验设计及实现、论文撰写；张文英提出分析思路、指导写作并修改论文；曹梅春负责图表整理及论文校对.