0 概述

随着信息时代的快速发展, 物联网作为信息技术的重要组成部分, 其通过智能感知、识别技术与普适计算等通信感知技术广泛应用于网络融合中。由于物联网中使用的微型计算设备的计算能力有限, 因此为了保证信息安全, 轻量级分组密码算法应运而生。轻量级分组密码算法是分组密码算法中的一种, 相比普通的分组密码算法, 该算法的分组长度相对较短, 且算法结构简单, 满足低耗能、低成本的需求。目前, 轻量级分组密码算法主要有LED^[1]、LBlock^[2]、PRESENT^[3]、HIGHT^[4]、SPECK^[5]等算法, 这些算法均具有结构简单、加解密一致、容易实现等优点。

2017年, PATIL等人^[6]提出一个分组长度为64比特、密钥长度为128比特的轻量级分组密码算法——LiCi算法。该算法结构类似于MISTY结构, 在单轮加密结构中, 非线性组件S盒会影响到加密结构的两支。相较于普通Feistel结构分组密码算法, LiCi算法具有扩散性快等优势。同时, 相比于SP结构分组密码算法, LiCi算法对非线性组件输出结果进行复用, 使之结构更加简单, 具有占用面积小等特性。文献[7]对LiCi算法抵抗不可能差分攻击的能力进行了介绍。然而, 关于LiCi算法抵抗积分攻击的能力目前尚不清楚, 因此, 本文利用积分攻击方法对该算法进行分析。

积分攻击是KNUDSEN等人^[8]在总结Square攻击、Multiset攻击、Saturation攻击的基础上提出的一种密码分析方法。该攻击方法是一种选择明文攻击方法, 与差分攻击^[9]、线性攻击^[10]、代数攻击^[11]同为目前密码学界公认的最有效的几种分析方法。结合故障分析的思想, 差分故障分析^[12]、代数故障分析^[13]、积分故障分析^[14]等分析方法也受到密码学者们的广泛关注。积分分析方法提出后, 其在AES^[15]、Camellia^[16]、FOX^[17]、PRINCE^[18]等算法中进行不同程度的分析应用。文献[19-20]提出比特的可分性质后, 结合MILP搜索工具, 利用可分性质对MISTY1进行全轮攻击。同时, 文献[21]也基于比特的可分性质结合MILP搜索工具, 进一步提升LBlock^[2]、PRESENT^[3]、SIMECK^[22]等算法的积分分析结果。

本文基于比特的可分性质, 结合MILP搜索工具对LiCi算法的积分区分器进行搜索。利用搜索得到的最长轮数的12轮积分区分器对LiCi算法进行13轮积分攻击, 恢复17比特密钥信息, 同时, 为了得到更高轮数的攻击结果, 利用10轮积分区分器向后攻击6轮, 对LiCi算法进行16轮积分攻击。

1 LiCi算法介绍 1.1 LiCi算法加密过程

LiCi算法分组长度为64比特, 密钥规模为128比特, 其迭代轮数为31轮。LiCi算法的单轮加密结构如图 1所示, 基本操作包括字节替换、异或、密钥加、循环移位等步骤。字节替换是该算法中唯一的非线性组件, 由8个并列的4进4出的S盒构成。

加密过程  设第i轮输入为X_i, Y_i, i=0, 1, 2, …, 29, 30, 分别代表第i轮输入的左分支和右分支; 输出为X_i+1, Y_i+1, 分别代表输出的左分支和右分支。状态X_i, Y_i到状态X_i+1, Y_i+1的迭代过程表示如下:

$ \begin{array}{l} X_{i+1}=\left[\mathrm{S}\left[X_{i}\right] \oplus Y_{i} \oplus R K 1_{i}\right] < < <3 \\ Y_{i+1}=\left[\mathrm{S}\left[X_{i+1}\right] \oplus X_{i+1} \oplus R K 2_{i}\right]>>>7 \end{array} $

(1)

其中, RK1_i, RK2_i均为轮密钥, X_{i, (31, 30, …, 2, 1, 0)}和Y_{i, (31, 30, …, 2, 1, 0)}分别表示输入状态的64个比特的标号, 如X_{i, 31}表示第i轮左支输入的最高比特, Y_{i, 0}表示第i轮右支输入的最低比特。

1.2 LiCi算法密钥扩展方案

密钥扩展方案:种子密钥长度为128比特, 记为K=K₁₂₇K₁₂₆…K₂K₁K₀, RK1_i, RK2_i均表示第i轮轮密钥, 其中RK1_i应用于第i轮右支加密, RK2_i应用于第i轮左支加密。轮密钥生成过程如下:

1) K=K₁₂₇K₁₂₆…K₂K₁K₀

2) RK1_i=K₃₁K₃₀K₂₉…K₂K₁K₀, RK2_i=K₆₃K₆₂…K₃₃K₃₂, i∈{0, 1, 2, …}

3) K_new=K < < < 13=K₁₁₄K₁₁₃…K₁K₀K₁₂₇K₁₂₆…K₁₁₅

4) K=K_new

5)[K₃K₂K₁K₀]_new=S[K₃K₂K₁K₀]

[K₇K₆K₅K₄]_new=S[K₇K₆K₅K₄]

[K₆₃K₆₂K₆₁K₆₀K₅₉]_new=[K₆₃K₆₂K₆₁K₆₀K₅₉] $ \oplus $ i, i∈{0, 1, 2, …}

6)[K₃K₂K₁K₀]=[K₃K₂K₁K₀]_new

[K₇K₆K₅K₄]=[K₇K₆K₅K₄]_new

[K₆₃K₆₂K₆₁K₆₀K₅₉]=[K₆₃K₆₂K₆₁K₆₀K₅₉]_new

7) 经过3)~6)得到新的K, 返回1), 经过2)得到新的轮密钥。

轮密钥分析:若已知第i轮密钥RK2_i, RK1_i(其中i≥5), 根据密钥扩展方案可以得知(RK2_i－4, RK1_i－4), …, (RK2_i, RK1_i)之间的关系。

假设已知(RK2_i, RK1_i)=(K₆₃…K₃₃K₃₂, K₃₁…K₁K₀), 则根据密钥扩展方案中轮密钥生成方案可知(RK2_i－1, RK1_i－1)和(RK2_i, RK1_i)之间的某些比特信息等价, 通过密钥生成方案中3)~6)可知, (RK2_i－1, RK1_i－1)与(RK2_i, RK1_i)相比, 新引入13比特信息。同理, 可以分析(RK2_i－2, RK1_i－2)和(RK2_i－1, RK1_i－1), …, (RK2_i－3, RK1_i－3)和(RK2_i－4, RK1_i－4)之间的关系, 5轮轮密钥总共包含116比特密钥信息, 6轮轮密钥总共包含种子密钥128比特密钥信息。通过上述轮密钥分析, 利用轮密钥之间的信息等价关系, 在猜测密钥过程中可以降低密钥猜测量。

1.3 LiCi算法的S盒性质

LiCi算法4比特S盒如表 1所示, 输入为x, 输出为S(x)。

采用文献[23]中求S盒布尔函数表达式的方法来求解LiCi算法4比特S盒代数表达式。

性质1 (S盒代数表达式)   设S盒输入为x=(x₃, x₂, x₁, x₀), 输出为y=(y₃, y₂, y₁, y₀), 则x和y之间的关系表达式如下:

$ \begin{array}{l} y_{3}=x_{0}+x_{1}+x_{3}+x_{1} x_{2}+x_{1} x_{3} \\ y_{2}=x_{0}+x_{1}+x_{3}+x_{0} x_{2}+x_{0} x_{3}+x_{2} x_{3}+x_{0} x_{1} x_{2} \\ y_{1}=1+x_{2}+x_{3}+x_{0} x_{1}+x_{0} x_{2}+x_{1} x_{3}+x_{2} x_{3}+x_{0} x_{1} x_{3} \\ y_{0}=1+x_{1}+x_{2}+x_{3}+x_{0} x_{1} \end{array} $

例如, 输入x₃x₂x₁x₀=0001, 经过S盒输出y₃y₂y₁y₀=1111。

2 基于比特的可分性质和MILP方法 2.1 基于比特的可分性质

定义1 (比特积函数π_u(x)和π_U(X)^[24])   多重集的可分性质可通过比特积函数进行评估, 比特积函数的定义如下:

令π_u(x):F₂ⁿ→F₂表示u∈F₂ⁿ的比特积函数。令x∈F₂ⁿ表示输入, π_u(x)表示满足u[i]=1的x[i]代数正规型, 定义为:

$ \pi_{u}(x):=\prod\limits_{i=1}^{n} x[i]^{u[i]} $

其中, x[i]¹=x[i], x[i]⁰=1。

令π_U(X):(F₂^n₁×F₂^n₂×…×F₂^n_m)→F₂表示U∈(F₂^n₁×F₂^n₂×…×F₂^n_m)的比特积函数。令X∈(F₂^n₁×F₂^n₂×…×F₂^n_m)表示输入, π_U(X)定义为:

$ \pi_{U}(X):=\prod\limits_{i=1}^{n} \pi_{U_{i}}\left(X_{i}\right) $

定义2 (可分性^[19])  设多重集X∈(F₂^n₁×F₂^n₂×…×F₂^n_m), 若X具有可分性D_K^{n₁, n₂, …, n_m}, 其中K是一个m维向量, 其第i个元素取值为0~n_i。若存在k∈K, 使得W(u)≥k, 则$ \underset{x \in X}{\bigoplus} \pi_{u}(x)$为未知, 反之, $ \underset{x \in X}{\bigoplus} \pi_{u}(x)$为0。

定义3 (可分路径^[21])   考虑可分析性质的传播$\{ \mathit{\boldsymbol{k}}\} \buildrel \Delta \over = {K_0} \to {K_1} \to {K_2} \to \cdots \to {K_r} $, 对任意向量k_i+1∈K_i+1使得k_i能传播到k_i+1, i∈{0, 1, …, r－1}, 则(k₀→k₁→…→k_r)为一条r轮可分路径。

上述内容是关于比特积函数、可分性和可分路径的介绍, 下面对基于比特的可分性质经过复制操作、异或操作时的传播规则进行简要介绍, 更多详情可参考文献[21, 24]。

规则1 (复制操作)  令x为复制函数的输入值, y₀, y₁为复制函数的输出值, 其中(y₀, y₁)=(x, x)。令X和Y分别表示输入多重集和输出多重集, 假设多重集X有可分性D_{k}¹, 多重集Y可分析性为D_K′^1×1, 则可分性传播只有以下2种情况:

$ \left\{\begin{array}{l} \boldsymbol{K}^{\prime}=\{(0, 0)\}, k=0 \\ \boldsymbol{K}^{\prime}=\{(0, 1), (1, 0)\}, k=1 \end{array}\right. $

规则2 (异或操作)  令y₀, y₁为异或函数的输入值, x为异或函数的输出值, 其中x=y₀$ \oplus $y₁。令X和Y分别表示输入多重集和输出多重集, 假设多重集X有可分性D_K′^1×1, 多重集Y可分析性为D_{k}¹, 则可分性传播有以下4种情况:

$ \left\{\begin{array}{l} \boldsymbol{K}^{\prime}=\{(0)\}, \boldsymbol{k}=(0, 0) \\ \boldsymbol{K}^{\prime}=\{(1)\}, \boldsymbol{k}=(0, 1) \\ \boldsymbol{K}^{\prime}=\{(1)\}, \boldsymbol{k}=(1, 0) \\ \boldsymbol{K}^{\prime}=\varnothing, \boldsymbol{k}=(1, 1) \end{array}\right. $

2.2 基本操作的MILP模型

基于比特的复制模型:假设输入可分性为a, 经过基于比特的复制操作输出可分性为(a₀, a₁), 记作a→(a₀, a₁), 其中a, a₀, a₁∈{0, 1}。a, a₀, a₁之间的关系如下:

$ a-a_{0}-a_{1} \geqslant 0, 0 \leqslant a_{0} \leqslant 1, 0 \leqslant a_{1} \leqslant 1 $

例如:1→(0, 1)或1→(1, 0), 0→(0, 0)。

基于比特的异或模型:假设输入可分性为(a₀, a₁), 经过基于比特的异或操作输出可分性为a, 记作(a₀, a₁)→a, 其中a, a₀, a₁∈{0, 1}。a, a₀, a₁之间的关系如下:

$ a-a_{0}-a_{1} \geqslant 0, 0 \leqslant a_{0} \leqslant 1, 0 \leqslant a_{1} \leqslant 1 $

例如:(0, 1)→1, (1, 0)→1, (0, 0)→1, 但是输入可分性为(1, 1), 经过异或操作可分性传播会中断。

S盒模型:利用文献[20]中的算法2可以得到LiCi算法S盒的可分性(详见开放科学(资源服务)标志码中附

录部分), 通过得到的S盒的可分性结合SageMath软件可得到S盒的线性不等式组。再利用文献[20]中的算法1对上述S盒线性不等式组进行简化, 最终得到LiCi算法S盒的15个线性不等式(详见开放科学(资源服务)标志码中附录部分)。

基于比特的循环移位模型:假设输入n比特可分性为k_n－1, …, k₂, k₁, k₀, 其中k_i∈{0, 1}。循环左移j位, 输出为k_{(i+n－j)modn}, i∈{n－1, …, 2, 1, 0};循环右移j位, 输出为k_(i+j)modn, i∈{n－1, …, 2, 1, 0}。

基于比特可分性的初始条件和终止条件:由可分轨迹的定义$ \{\boldsymbol{k}\} \triangleq K_{0} \rightarrow K_{1} \rightarrow K_{2} \rightarrow \cdots \rightarrow K_{r}, \boldsymbol{a}^{0}=\left(a_{n-1}^{0}, \cdots, a_{1}^{0}, a_{0}^{0}\right) \rightarrow\left(a_{n-1}^{r}, \cdots, a_{1}^{r}, a_{0}^{r}\right)=\boldsymbol{a}^{r}$表示一条r轮基于比特的可分轨迹, L表示变量为$ a_{i}^{j}, i=0, 1, \cdots, n-1, j=0, 1, \cdots, r$的线性不等式组。

令$D_k^{1, n} $表示初始输入可分性, 其中k=(k_n－1, …, k₁, k₀), L求解得到的所有可行解——可分轨迹始于可分性k。由于可分性(0, 0, …, 0, 0, 0)经过复制操作、异或操作、S盒、循环移位等基本操作后, 输出可分性仍为0, 因此可分性初始输入不能为(0, 0, …, 0, 0, 0)。

命题1^[20]  假设X是具有可分性$ D_\mathit{\boldsymbol{K}}^{1, n}$的多重集, 当K包含n个单位向量时, 多重集X不存在积分。

令目标函数为Obj: $\operatorname{Min}\left\{a_{0}^{r}+a_{1}^{r}+\cdots+a_{n-1}^{r}\right\} $, MILP问题转化为限制条件为L、目标函数为Obj的求解问题。最后一轮求解得到可分性$ D_{{K^r}}^{1, n}$, 当K^r包含n个单位向量时终止求解。

3 MILP方法在LiCi算法中的应用 3.1 LiCi算法MILP模型建立

对LiCi算法的基本操作建立MILP模型, 在模型建立过程中, 基于比特的复制模型、异或模型和S盒模型与已有文献[20]给出的模型构造基本相同, 根据LiCi算法左支循环右移7位后直接得到输出值的结构特性, 在最后一轮利用逆向思维构造LiCi算法MILP模型。

LiCi算法单轮可分性传播示意图如图 2所示。

第i(i∈{1, 2, …, R－1})轮LiCi算法单轮MILP模型建立过程如下所示:

1) 令可分性$ D_{\mathit{\boldsymbol{X}}, i}^{1, 32}$经过S盒模型, 输出可分性为$ D_{\mathit{\boldsymbol{u}}, i}^{1, 32}$。

2) 令可分性$ D_{\mathit{\boldsymbol{u}}, i}^{1, 32}$经过“复制操作1”输出可分性分别为$ D_{\mathit{\boldsymbol{u}}{\rm{1}}, i}^{1, 32}$、$ D_{\mathit{\boldsymbol{u}}{\rm{2}}, i}^{1, 32}$。

3) 令可分性$ D_{\mathit{\boldsymbol{u}}{\rm{1}}, i}^{1, 32}$和$D_{\mathit{\boldsymbol{Y}}, i}^{1, 32} $经过异或操作, 输出可分性为$D_{\mathit{\boldsymbol{v}}, i}^{1, 32} $。

4) 令可分性$D_{\mathit{\boldsymbol{v}}, i}^{1, 32} $经过循环左移3位后输出可分性为$D_{v{\rm{new}}, i}^{1, 32} $。

5) 令可分性$D_{\mathit{\boldsymbol{v}}, i}^{1, 32} $= $ D_{v{\rm{new}}, i}^{1, 32}$经过“复制操作2”后, 输出可分性分别为$ D_{\mathit{\boldsymbol{v}}{\rm{1}}, i}^{1, 32}$、$ D_{\mathit{\boldsymbol{X}}, i + 1}^{1, 32}$。

6) 令可分性$ D_{\mathit{\boldsymbol{u}}{\rm{2}}, i}^{1, 32}$和$ D_{\mathit{\boldsymbol{v}}{\rm{1}}, i}^{1, 32}$经过异或操作后, 输出可分性为$ D_{\mathit{\boldsymbol{Y}}, i + 1}^{1, 32}$。

7) 令可分性$ D_{\mathit{\boldsymbol{Y}}, i + 1}^{1, 32}$经过循环右移7位后输出可分性为$D_{Y{\rm{new}}, i}^{1, 32} $, 令$ D_{\mathit{\boldsymbol{Y}}, i + 1}^{1, 32}$= $D_{Y{\rm{new}}, i}^{1, 32} $。

性质1 (基于比特循环移位)   在单轮函数加密结构中, 若输入可分性经过循环移位操作后, 存在复制操作、异或操作或S盒, 则直接对输入可分性建立基于比特的循环移位模型, 反之, 则最后一轮输入可分性经过循环移位操作时利用逆向思维建立基于比特的循环移位模型。以LiCi算法为例, 最后一轮(第R轮)MILP模型建立过程如下:第R轮MILP模型建立过程1)~5)和第1轮至第R－1轮模型建立过程相同, 6)和7)过程如下:

6) 令可分性$ D_{\mathit{\boldsymbol{Y}}, r}^{1, 32}$经过循环左移7位后输出可分性为$ D_{Y{\rm{new}}, r - 1}^{1, 32}$, 令$ D_{\mathit{\boldsymbol{Y}}, r}^{1, 32}$= $ D_{Y{\rm{new}}, r - 1}^{1, 32}$。

7) 令可分性$D_{Y{\rm{new}}, r - 1}^{1, 32} $和$经过异或操作后, 输出可分性为$ D_{\mathit{\boldsymbol{Y}}, r}^{1, 32}$。

3.2 LiCi算法基于比特积分区分器搜索结果

目前搜索得到的LiCi算法平衡比特数最多, 轮数最长的积分区分器为输入63比特活跃, 输出43比特平衡的12轮积分区分器。

假设a表示活跃, b表示平衡, c表示常数, ?表示未知, 输入两支的单支为32比特, 令标号31表示最高位, 标号0表示最低位, 输入两支标号表示如下:

$ \left\{\begin{array}{l} X_{0}: X_{31}, X_{30}, X_{29}, \cdots, X_{2}, X_{1}, X_{0} \\ Y_{0}: Y_{31}, Y_{30}, Y_{29}, \cdots, Y_{2}, Y_{1}, Y_{0} \end{array}\right. $

10轮积分区分器:基于MILP搜索得到的平衡比特数最多, 轮数最长的积分区分器为输入62比特活跃, 输出64比特平衡的10轮积分区分器, 输入记为(X₀, Y₀), 输出记为(X₁₀, Y₁₀), 输入输出状态表示如下:

$ \begin{array}{l} {X_0}:aaaa, aaaa, aaaa, aaaa, aaaa, aaaa, aaaa, aaaa\\ {Y_0}:aaaa, aaaa, aaaa, aaaa, aaaa, aaca, aaaa, aacaa\\ {X_{10}}:bbbb, bbbb, bbbb, bbbb, bbbb, bbbb, bbbb, bbbb\\ {Y_{10}}:bbbb, bbbb, bbbb, bbbb, bbbb, bbbb, bbbb, bbbb \end{array} $

12轮积分区分器:目前搜索得到的最长轮数积分区分器为12轮积分区分器, 共有两个积分区分器, 积分区分器1是输入63比特活跃, 输出43比特平衡; 积分区分器2是输入63比特活跃, 输出6比特平衡。输入记为(X₀, Y₀), 输出记为(X₁₂, Y₁₂), 输入输出状态表示如下:

1) 12轮积分区分器1

$ \begin{aligned} X_{0}: {aaaa, aaaa }, {aaaa}, {aaaa}, {aaaa}, {aaaa}, {aaaa}, {aaaa}\\ Y_{0}: {aaaa }, {aaaa }, {aaaa}, {aaaa} {, aaaa }, {aaaa}, {aaaa}, {aaac}\\ X_{12}: b b b b, b b b b, b b b b, b b b b, b b b b, b b ? ?, b b ? ?, b b b b\\ Y_{12}: ? ? ? b, ? ? b b, b b b b, b b b b, b b b b, b b b b, b b b b, b ? ? b \end{aligned} $

2) 12轮积分区分器2

$ \begin{aligned} X_{0}: {aaaa}, {aaaa} {, aaaa }, {aaaa}, {aaaa}, {aaaa}, {aaaa}, {aaac}\\ Y_{0}: {aaaa}, {aaaa}, {aaaa}, {aaaa}, {aaaa}, {aaaa}, {aaaa}, {aaaa}\\ X_{12}: ? ? ? ?, ? ? b ?, b b ? ?, b ? ? ?, ? ? ? ?, ? ? ? ?, ? ? ? ?, ? ? ? ?\\ Y_{12}: ? ? ? ?, ? ? ? ?, ? ? ? ?, ? ? ? b, ? ? ? b, ? ? ? ?, ? ? ? ?, ? ? ? ? \end{aligned} $

4 LiCi算法的密钥恢复攻击 4.1 13轮密钥恢复攻击

由于目前基于MILP搜索得到的最优12轮积分区分器输入活跃比特数为63比特, 输出平衡比特数为43比特, 利用12轮积分区分器时只能利用1组明文, 通过猜测41比特密钥信息, 对第13轮RK2₁₂的17比特密钥信息进行密钥恢复攻击。具体攻击过程和攻击结果如下:

1) 对构造12轮积分区分器中2⁶³个明文进行加密, 得到2⁶³个密文C₀, C₁, …, C_2⁶³－1。

2) 猜测第13轮41比特轮密钥RK2_{12, (31, …, 13, 12, 3, 2, 1, 0)}, RK1_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}解密第13轮, 得到第12轮41比特输出X_{12, (31, …, 13, 12, 3, 2, 1, 0)}和Y_{12, (23, …, 13, 12, 3, 1)}。如下表示:

$ \begin{array}{l} X_{12, (31, \cdots, 13, 12, 3, 2, 1 \cdots, 0)}= \\ S^{-1}\left(\left(Y_{13} <<<7\right) \oplus X_{13} \oplus R K 2\right)_{12, (31, \cdots, 13, 3, \cdots, 0)} \end{array} $

$ \begin{array}{l} Y_{12, (28, 25, 24, 23, \cdots, 13, 12, 3, 1)}= \\ \left(\left(Y_{13}<<<7\right) \oplus X_{13} \oplus R K 2_{12}\right)_{(28, 25, 24, 23, \cdots, 13, 12, 3, 1)} \\ \left(X_{13}>>>3\right)_{(28, 25, 24, 23, \cdots, 13, 12, 3, 1)} \oplus \\ R K 1_{12, (28, 25, 24, 23, \cdots, 13, 12, 3, 1)} \end{array} $

(2)

验证X_{12, (31, …, 13, 12, 3, 2, 1, 0)}和Y_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}是否为平衡比特, 若为平衡比特, 则猜测密钥为正确密钥, 否则为错误密钥。密钥恢复攻击分为两步, 第一步对轮密钥RK2_{12, (31, …, 13, 12, 3, 2, 1, 0)}进行密钥恢复攻击, 错误轮密钥使X_{12, (31, …, 13, 12, 3, 2, 1, 0)}为平衡比特的概率为2^－24, 经过1组明文后剩余错误密钥数目为(2²⁴－1)×2^－24≈1。第二步对轮密钥RK2_{12, (31, …, 13, 12, 3, 2, 1, 0)}和RK1_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}进行密钥恢复攻击, 错误密钥使Y_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}为平衡比特的概率为2^－17。由于第一步已经对RK2_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}进行筛选, 经过1组明文后RK2_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}剩余错误密钥数目为1, 经过第二步筛选后RK2_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}剩余错误密钥数目为2^－17 < < 1, 可以恢复RK2_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}共17比特密钥信息。由于经过第二步筛选, RK1_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}错误密钥量为1, 因此无法对RK1_{12, (23, …, 13, 12)}进行正确恢复。从而攻击数据复杂度为2⁶³个明文, 时间复杂度为2⁶³×2⁴¹=2¹⁰⁴次查32比特S盒大表, 相当于2¹⁰⁴/16=2¹⁰⁰次16轮加密。为猜测密钥, 攻击需要对猜测密钥进行存储, 存储复杂度为2⁴¹。

针对式(2)的计算, 可以通过“部分和”^[25]技术对其进行改进, 具体方式如下:

步骤1  猜测RK2_{12, (31, …, 13, 12, 3, 2, 1, 0)}的一种可能值, 并计算72比特三元组(Z_{12, (31, …, 12, 3, …, 0)}, (Y₁₃ < < < 7)_{(31, …, 13, 3, …, 0)}, X_{13, (31, …, 13, 3, …, 0)}), 其中Z_{12, (31, …, 13, 12, 3, …, 0)}=((Y₁₃ < < < 7)$ \oplus $X₁₃$ \oplus $RK2₁₂)_{(31, …, 13, 3, …, 0)}, 用表T记录出现奇数次的三元组(Z_{12, (31, …, 12, 3, …, 0)}, (Y₁₃ < < < 7)_{(31, …, 13, 3, …, 0)}, X_{13, (31, …, 13, 3, …, 0)}), 求得最终结果$ \oplus $Z_{12, (31, …, 12, 3, …, 0)}。

步骤2  猜测(RK2, RK1)_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}的一种可能值, 对表T中标记的每一个三元组, 计算W_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}, 其中W_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}=Z_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}$ \oplus $(_X13$ \oplus $RK1_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}, 求得最终结果$ \oplus $W_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}。

若步骤1中求得的值$ \oplus $Z_{12, (31, …, 12, 3, …, 0)}=0, 则此次猜测的RK2_{12, (31, …, 13, 12, 3, 2, 1, 0)}有可能是正确密钥, 否则一定是错误密钥。一个错误密钥满足$ \oplus $Z_{12, (31, …, 12, 3, …, 0)}=0的概率为2^－24。若步骤2中求得的值$ \oplus $W_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}=0, 则此次猜测的RK2_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}, RK1_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}有可能是正确密钥, 否则一定是错误密钥。一个错误密钥满足$ \oplus $W_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}=0的概率为2^－17, 因此, 1个包含2⁶³个明文的明文组可以唯一确定17比特轮密钥RK2_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}。

求解RK2_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}的时间复杂度步骤如下:

步骤1  对于2²⁴种RK2_{12, (31, …, 13, 12, 3, 2, 1, 0)}的可能值, 需要处理的密文有2⁶³个, 因此需要进行2^87次32比特S盒查表操作。

步骤2  由于一共猜测了34比特密钥信息RK2_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}, RK1_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}, 对于三元组中的每个(Z₁₂, Y₁₃ < < < 7, X₁₃)_{28, 25, 24, 23, …, 13, 12, 3, 1}计算W_{12, (28, 25, 24, 23, …, 13, 12, 3, 1)}, 且(Z₁₂, Y₁₃ < < < 7, X₁₃)_{(28, 25, 24, 23, …, 13, 12, 3, 1)}至多有2⁵¹种可能, 需要大约进行2⁸⁵次32比特S盒查表操作。综上, 攻击时间复杂度为(2⁸⁷+2⁸⁵)≈2⁸⁷次查32比特S盒查表, 相当于约2⁸³次16轮加密, 相比于2¹⁰⁰次16轮加密结果有了较大改进。

4.2 16轮密钥恢复攻击

为了得到更长轮数的攻击结果, 结合密钥扩展方案的特性, 本文选择利用10轮积分区分器向后攻击6轮, 对16轮LiCi算法进行密钥恢复攻击。攻击过程至少需要猜测119比特密钥信息。第11轮攻击过程如图 3所示。

具体攻击过程如下:

步骤1  对构造10轮积分区分器中2⁶²个明文进行加密, 得到2⁶²个密文C₀, C₁, …, C_2⁶²－1。

步骤2  猜测第16轮64比特轮密钥(RK2₁₅, RK1₁₅), 解密第16轮, 得到第15轮64比特输出X_{15, (31, 30, …, 2, 1, 0)}和Y_{15, (31, 30, …, 2, 1, 0)}。

步骤3  根据步骤2的结果, 猜测第15轮64比特轮密钥(RK2₁₄, RK1₁₄), 结合密钥扩展方案和轮密钥的关系可以得知, 这一步只需要猜测13比特信息。解密第15轮, 得到第14轮64比特输出。

步骤4  根据步骤3的结果, 猜测第14轮64比特轮密钥(RK2₁₃, RK1₁₃), 结合密钥扩展方案和轮密钥的关系可以得知, 这一步只需要猜测13比特信息。解密第14轮, 得到第13轮64比特输出。

步骤5  根据步骤4的结果, 猜测第13轮64比特轮密钥(RK2₁₂, RK1₁₂), 结合密钥扩展方案和轮密钥的关系可以得知, 这一步只需要猜测13比特信息。解密第13轮, 得到第12轮64比特输出。

步骤6  根据步骤5的结果, 猜测第12轮64比特轮密钥(RK2₁₁, RK1₁₁), 结合密钥扩展方案和轮密钥的关系可以得知, 这一步只需要猜测13比特信息。解密第12轮, 得到第11轮64比特输出。

步骤7  根据步骤6的结果, 猜测第11轮44比特轮密钥(RK2_{10, (21, 20, …, 2, 1, 0)}, RK1_{10, (21, 20, …, 2, 1, 0)}), 结合密钥扩展方案和轮密钥的关系可以得知, 这一步只需要猜测3比特信息。解密第11轮, 得到第10轮42比特输出(X_{10, (19, …, 2, 1, 0)}, Y_{10, (21, 20, …, 2, 1, 0)}), 具体表示如下:

$ \begin{aligned} X_{10, (19, \cdots, 2, 1, 0)}=& \mathrm{S}^{-1}\left(\left(Y_{11}<< <7\right) \oplus X_{11} \oplus R K 2_{10}\right)_{(19, \cdots, 2, 1, 0)} \\ Y_{10, (21, 2), \cdots, 2, 1, 0)}=&\left(\left(Y_{11}<<<7\right) \oplus X_{11} \oplus R K 2_{10}\right)_{(21, 0, \ldots, 2, 1, 0)} \oplus \\ &\left(X_{11}>>>3\right)_{(21, 20, \cdots, 2, 1, 0)} \oplus \\ & R K 1_{10, (21, 20, \cdots, 2, 1, 0)} \end{aligned} $

(3)

验证X_{10, (19, 18, …, 2, 1, 0)}和Y_{10, (21, 20, …, 2, 1, 0)}是否为平衡比特, 若为平衡比特, 则猜测密钥为正确密钥, 否则为错误密钥。

步骤8  重新选择一组构造10轮积分区分器的明文, 重复步骤1~步骤7直至密钥唯一确定。

结合密钥扩展方案和轮密钥的分析, 上述攻击共需要猜测119比特密钥信息。对于正确密钥可以保证X_{10, (27, 26, …, 1, 0)}和Y_{10, (27, 26, …, 1, 0)}为平衡比特, 错误密钥使X_{10, (27, 26, …, 1, 0)}和Y_{10, (27, 26, …, 1, 0)}为平衡比特的概率为2^－42, 经过1组明文后剩余错误密钥数目为(2¹¹⁹－1)×2^－42≈2⁷⁷, 为确定唯一密钥需要3组明文, 剩余错误密钥数量为(2¹¹⁹－1)×2^－42×3≈2^－7。从而攻击数据复杂度为2⁶²×3=2^63.6个明文, 时间复杂度为2⁶²×(2¹¹⁹+2⁷⁷+2³⁵)≈2¹⁷⁷次查32比特S盒大表, 相当于2¹⁷⁷/16=2¹⁷³次16轮加密。为猜测密钥, 攻击需要对猜测密钥进行存储, 存储复杂度为2¹¹⁹。由于利用10轮积分区分器向后扩展6轮对LiCi算法进行16轮积分攻击, 第10轮输出和第16轮密文信息以及第12~第16轮的轮密钥的每一比特信息均几乎相关, 因此未能利用“部分和”技术降低时间复杂度。

根据攻击步骤1~步骤8结合LiCi算法密钥扩展算法可知, 利用10轮积分区分器向后扩展2轮~6轮时, 攻击时间复杂度均大于2¹²⁸。

5 结束语

本文将基于比特的积分性质和MILP搜索工具相结合, 得到平衡比特数目最多、轮数最长的积分区分器为12轮积分区分器, 利用12轮积分区分器对LiCi算法进行13轮积分攻击, 攻击数据复杂度约为2⁶³, 时间复杂度约为2¹⁰⁰次16轮加密, 存储复杂度约为2⁴¹。利用“部分和”技术可以将时间复杂度降为2⁸³次16轮加密。为得到更长轮数的攻击结果, 利用构造的10轮积分区分器向后攻击6轮, 对16轮算法实施密钥恢复攻击, 攻击数据复杂度约为2^63.6, 时间复杂度约为2¹⁷³次16轮加密, 存储复杂度约为2¹¹⁹。本文在积分攻击层面对LiCi算法进行分析, 结果表明, 13轮LiCi算法不能抵抗积分攻击。下一步将基于比特的可分性, 在搜索积分区分器时对输入可分性的初始值和积分区分器的轮数与平衡比特数目之间的关系进行研究。