ACE密码算法的积分分析

叶 涛 韦永壮* 李灵琛

①(桂林电子科技大学广西无线宽带通信与信号处理重点实验室 桂林 541004)

②(桂林电子科技大学广西密码学与信息安全重点实验室 桂林 541004)

1 引言

随着物联网技术和5G技术的快速发展，信息安全问题日趋突出，分组密码算法作为一种主流的加密体制，由于其安全性高、加密速度快、安全性易于评估等特点，具有非常重要的应用。对于一个安全的分组密码算法，其需要抵抗已知的各种攻击方法，比如线性密码分析[1]、差分密码分析[2]、不可能差分分析[3,4]、立方分析[5]、积分分析[6]等。目前除属性[7]以及自动化分析工具在密码分析中的广泛应用，使得积分分析成为近些年来国内外密码学者的研究热点之一。

积分分析最初是由Knudsen等人[6]为了分析Square的安全性而提出的分析方法，其基本思想是选取某些输入的明文字节为任意的固定值，其余的明文字节活跃，如果这个明文集合通过密码算法后，某些输出位的和恒为0，则攻击者构建了一个积分区分器。搜索积分区分器的典型方法一般可以分为如下3种：第1种方案是通过观察积分性质的传播轨迹来构建积分区分器[8,9]。第2种方案是通过评估密码算法输出表达式的代数次数来构建积分区分器[10,11]。第3种方法是利用除属性[7,12]构建出相应的模型，然后，利用优化工具来搜索积分区分器[13-17]。但是，这些构建积分区分器的方法受到密码结构或计算能力的限制。在2020年的国际快速软件加密会议(FSE2020)上，Zhang等人[18]给出了一种新的搜索算法。其主要思想是将内部状态的表达式用明文或密文字来表示，通过统计这些明文或密文字在内部状态中出现的次数，评估密码算法抵抗积分分析的能力。但是该方法需要手动推导出内部状态关于明文字或密文字的具体表达式形式，不能做到自动化分析。如何给出一种自动分析方法是目前的研究难点。

本文引入字传播轨迹新概念，基于混合整数线性规划技术(Mixed Integer Linear Programming, MILP)，构建了一个传播轨迹的描述模型，并给出一个新的积分区分器自动化搜索方法。利用这个自动化搜索算法，不需手动推导复杂的表达式，只需要判断模型是否有解就可以快速地得到明文(密文)字在内部状态的表达式中出现的次数，降低了密码分析者的工作量。利用这个新的自动化搜索工具，本文对国际轻量级密码算法标准化过程的第2轮候选算法之一ACE[19]的安全性进行了分析。结果表明：ACE密码算法存在12步的积分区分器，需要的数据复杂度为 2256，需要的时间复杂度为 2256次12步的ACE置换操作，存储复杂度为8 Byte。

本文后续章节的安排如下，第2节主要介绍一些基础知识；第3节主要介绍如何利用MILP结合文献[18]中的思想搜索积分区分器；第4节利用新的自动化分析方法对ACE置换的安全性进行分析；第5节是对全文的总结。文中用到的符号定义如表1所 示。

2 基础知识

2.1 ACE置换

ACE认证加密算法是由加拿大滑铁卢大学Aagaard等人[19]设计的，它是国际轻量级密码算法标准化[20]过程的第2轮候选算法之一。其中，ACE的置换包含16步，每一步都对320 bit的数据进行操作，其基本结构基于广义Feistel结构[21]，并且每一步都使用不带密钥的减轮Simeck密码算法[22]作为非线性部件。由于ACE算法每一步的操作仅包含与、异或、循环移位运算等基本操作，其具有很好的软硬件实现性能。在设计ACE的原文档中，算法的设计者给出了ACE置换的8步的积分区分器，但是，是否存在步数更高的积分区分器还有待于进一步探究。

表1 文中用到的符号

图1 ACE置换

2.2 利用置换函数性质构建积分区分器

文献[18]给出了新的积分区分器的构建方法，主要用到了置换函数的性质。

性质1如果函数 F(X):→是关于 X的置换函数，f (Y):→为任意布尔函数，则对于X,Y ∈，存在

文献[18]构建积分区分器的主要步骤如下：

(1) 利用轮函数的结构，对明文进行加密运算，并观察输出状态的表达式，直到第j 个明文字达到了全扩散，并且至少存在1个输出状态的表达式中第j 个明文字只出现1次，此时记录加密的轮数为。

(2) 利用轮函数的结构，对密文进行解密运算，观察输出状态的表达式，直到第j 个密文字达到了全扩散，记录此时对应的解密轮数为，并且，当解密-1轮后，至少存在1个输出状态的表达式中不出现第j 个密文字，记录下此时对应的。

则利用性质2，可以评估密码算法抵抗积分分析的能力。

性质2对于一个SPN结构的分组密码算法，令renc和 rdec分别为加密和解密方向达到全扩散的最小轮数，则这个密码算法存在renc+rdec轮的积分区分 器[18]。

3 新的积分区分器自动化搜索算法

3.1 分组密码算法字传播轨迹

为了观察每一个输入字在内部状态中出现的次数，攻击者需要利用轮函数的具体形式来推导出多轮后输出状态关于输入字的表达式形式，然后再观察每一个输入字在输出状态中出现的次数。以ACE密码算法的第0个字 A0为例，本文定义数组[4]] 为第i步的输出状态的表达式 Ai,Bi,Ci,Di,Ei中包含第0个字 A0的次数。首先，在不考虑步常数的条件下，可以得到ACE置换第i步的输入与输出之间的关系为

利用式(2)，当只有 A0为活跃块时，在加密方向上，可以得到 A0的传播轨迹为

由于x90[j]＞1(0 ≤j ＜5) ，则A9,B9,C9,D9,E9都不是关于输入字 A0的置换；由于x80[1]=1，所以， B8是 输入块 A0的置换，则=8( A为步函数输入的第0个字)。

由上面的实例可以发现，对于一个字，经过轮函数后，在每一轮的输出状态中出现的次数是固定的。根据这个特点，本文定义字传播轨迹如下。

3.2 构建分组密码算法字传播模型

如果直接手动推导字传播轨迹，需要的时间较长，并且容易发生错误。为了提高密码分析者的效率，本文给出了字传播轨迹的混合整数规划模型(MILP)，利用这个模型结合优化工具(Gurobi8.0)给出了一个自动化搜索积分区分器的方法。

本文的方法主要是在不考虑S盒内部结构的前提下，根据密码算法线性部件的特点来构建字传播模型。在密码算法的线性部件中，基本的操作包括置换运算、异或运算，下面分别讨论如何构建这两个运算的字传播轨迹。

性质3置换运算的字传播轨迹模型：由于置换运算只是对某些字进行位置上的置换，不影响输入字在输出状态中出现的次数。如果轮函数中存在置换操作 si[k]→si[k1]，则可以构建出如下的模型来描述第j 个字的传播轨迹

性质4异或运算的字传播轨迹模型：由于在分组密码算法的轮函数中，线性操作之前一般都会经过非线性层，所以，进行异或操作的变量都是非线性部件的输出，则经过异或操作后的输出中某一个字出现的次数为异或操作前这个变量在对应的字中出现的次数之和。如果轮函数的线性层中包含异或操作 si[k1]⊕si[k2]⊕si[k3]⊕···⊕si[kl]=si+1[k]，则可以构建如式(5)的模型来描述第 j个字的传播轨迹

通过将密码算法的线性层拆分为异或和置换操作，可以构建出这个密码算法每一轮的字传播模型 ，将其迭代r 轮后可以得到r 轮字传播模型M 。

3.3 新积分区分器自动化搜索算法

基于文献[18]中的积分区分器构建方法，结合本文构建的MILP模型，同时利用优化求解工具，本文设计了积分区分器自动化搜索算法。

首先，给出如何设置模型的初始的输入。如果想得到输入的第 k个字的传播轨迹，由于s0[k]只在s0[k]中出现1次，在其余的位置没有出现，则初始输入对应的模型变量为

所以，利用字传播轨迹，如果向量 Xkr中至少存在1个元素等于1，则存在r 轮的关于第k 个字的积分区分器。则有如下的性质。

为了向解密方向继续扩展积分区分器的轮数，需要判断出第 k个字解密方向上没有达到全扩散的最大轮数，即解密+1 轮后第k 个输入字第1次达到了全扩散，但是解密轮后第k 个字没有达到全扩散。根据这个关系，有如下的性质。

表2 算法1：利用字传播模型确定

表2 算法1：利用字传播模型确定

fr ∈(Fn2 )m R k 输入：分组密码轮函数 ，加密轮数 ，活跃字的下标rke rke k ωk 输出： ，以及加密 轮后，当第 个字活跃时，输出状态中的平衡字的下标集合rh =R rl =0 rke =0r =0 (1) , , , , flag= 0 xik[0]xik[1]···xik[m-1] i (2) , , , 为 轮加密后，输出状态对应的MILP模型变量，每一个MILP变量的值范围是大于等于0的整数rh-rl ＞1 (3) While do r =⎿(rh+rl)/2」 (4) r Me (5) 利用性质3和性质4构建出 轮的字传播模型 (6) Me.con ←x0k[k]=1,M.con ←x0k[j]=0,j ∈[0,m),j /=k Me.con ←min′{(xrk[0],xrk[1],··· ,xrk[m-1])}=1 (7) Me (8) 利用求解器对模型 进行求解 (9) If Me 有解rl =r,flag=1 (10) (11) else rh =r,flag=0 (12) (13) End If (14) End While flag==1 (15) If rke =r (16) (17) else rke =r-1 (18) (19)End If(1,ωk)=min{(xrke k [0],xrkek [1],··· ,xrkek [m-1])} (20)rke ωk (21) return 和

定义密码算法的线性层可以使用矩阵A=(ai,j)⊂来表示，非线性层使用S表 示第i轮中的第j 个密码S盒，则在不考虑轮常数和轮密钥的条件下，可得第 i轮的输出状态与输入状态的关系为

表3 算法2：利用字传播模型确定

表3 算法2：利用字传播模型确定

fr-1 ∈(Fn2 )m R k 输入：分组密码解密轮函数 ，解密轮数 ，活跃字的下标rkd rkd k φk 输出： ，以及解密 轮后，输出状态中的不包含第 个字的下标集合rh =R rl =0 rkd =0r =0flag=0 (1) , , , , yik[0] yik[1]···yik[m-1] i (2) , , , 为第 轮解密输出状态对应的MILP模型变量，每一个MILP变量的值范围是大于等于0的整数rh-rl ＞1 (3) While do r =⎿(rh+rl)/2」 (4) r Md (5) 利用性质3和性质4构建出 轮的字解密传播模型 (6) Md.con ←y0k[k]=1,M.con ←y0k[j]=0,j ∈[0,m),j /=k Md.con ←min′{(yrk[0],yrk[1],···,yrk[m-1])}=0 (7) Md (8) 利用求解器对模型 进行求解 (9) If Md 有解rl =r,flag=1 (10) (11) else rh =r,flag=0 (12) (13) End If (14) End While flag==1 (15) If rkd =r (16) (17) else rkd =r-1 (18) (19) End If(0,φk)=min{(yrkd (20) rkd φk (21) return 和k [0],yrkdk [1],···,yrkdk [m-1])}

4 ACE密码算法新积分分析

对于一个给定的迭代分组密码算法，本文给出了如下的积分区分器搜索步骤：

(1)先构建出密码算法轮函数的加密和解密方向的字传播模型；

(4)根据算法结构，观察 red轮的积分区分器能否继续向加密方向扩展1轮。

利用上面的步骤对ACE置换进行积分分析。首先，在加密方向上，定义初始输入(A0,B0,C0,D0,E0) 对应的模型变量为k ∈[0,5)， 其中，k 表示在初始输入中第k 个字是活跃的，ACE置换加密方向第i步的输出对应的模型变量为， 例如，x30[0]表示加密3步后，字 A0在字 A3的表达式中出现的次数，其他的变量代表的含义同理。则根据ACE置换的步函数的结构，可以得到加密方向第i步的步函数对应的字传播模型为

定义ACE置换解密方向第 i 步的输出对应的模型变量为 ([0],[1],··· ,[4])， 则第i步解密方向的步函数对应的字传播模型为

利用式(9)和式(10)， r 次迭代后就可以得到r 步的字传播模型。然后，将模型输入到算法1和算法2中，使用求解器对模型进行求解(求解器：Gur o b i 8.0，编程语言：P y t h o n 2.7)，并遍历k ∈[0,5)，得到的结果如表4和表5所示。

由 表4 和 表5 可 得 red=12 , φ =[0,2,3]，则ACE置换存在1个12步的积分区分器，对应的区分器的具体形式如表6所示。

images/BZ_38_811_2277_845_2322.pngωk表 4 ACE置换对应的 和k rke ωk 0 8[1][3]2 7[1]1 8 3[1]4 7[3]9

rkd φk表 5 ACE置换对应的 和k rkd φk 0 4[0]1[4]2 5[0]3[0]4 4[4]3 3

表6 ACE置换12步的积分区分器

由于13步加密后，仅有字 E13的表达式中包含了字 B12， 同时E13中还包含了C12，则12步的积分区分器不能继续向下扩展1步，所以，本文得到的ACE置换的积分区分器的步数为12步。相比于ACE设计文档中给出的结果[19]，本文给出的积分区分器步数更高，需要的数据量更少。结果对比如表7。

表7 ACE置换积分分析结果对比

5 结束语

本文给出了字传播轨迹的概念，构建了相应的MILP模型来描述字传播轨迹，并在此基础上设计了一种新的积分区分器自动化搜索方法，同时利用二分法减少了需要求解模型的次数。利用这个自动化分析工具，对ACE置换抵抗积分分析的能力进行了评估，发现了12步的积分区分器，在ACE的设计文档中，设计者利用可分性搜索到了8步的积分区分器，所以，相比ACE设计文档中的区分器，本文的区分器提高了4步。虽然，本文的区分器没有对ACE认证加密算法的安全性造成威胁(ACE认证加密算法中ACE置换的总步数为16步)，但是本文给出了一种自动化搜索分组密码算法积分区分器的新方法，提高了密码分析的效率，为以后的分组密码算法的设计与分析提供了强有力的工具。