基于MILP 的轻量级密码算法ACE 的差分分析

刘帅，关杰，胡斌，马宿东

（信息工程大学密码工程学院，河南 郑州 450001）

0 引言

随着物联网的发展，如何利用有限的资源保证数据的安全成为当前的重要研究课题，轻量级密码算法（LWCA,lightweight cipher algorithm）[1]应运而生。近年来，涌现出了大量轻量级密码算法[2-5]，其设计与分析得到了研究者的广泛关注[6-8]。2016年，美国国家标准与技术研究院发起了轻量级密码算法征集活动[9]，要求提交的算法兼具认证与加密功能，这一类算法也被称为认证加密算法[10]。

认证加密算法输入密钥K、NonceN、相关数据A、明文M，输出密文C、认证码T，即(C,T) =E (K,N,A,M)；相应地，解密阶段输入密钥K、NonceN、相关数据A、密文C、认证码T，随后生成认证码T′，如果T=T′则认证通过，输出明 文M，否则认证失败输出⊥，即D(K,N,A,C,T) ∈{M,⊥}。

随着多种多样的轻量级密码算法被提出，其安全性分析也经历着不断的革新，过去的安全分析往往依赖手工推导，1994 年，Matsui[11]提出了一种强有力的自动化分析工具，利用分支定界搜索算法来搜索最优差分/线性链，从此自动化分析在诸多场景下取代了手工推导[12-15]。2014 年，Sun 等[16]给出了密码算法的混合整数线性规划（MILP,mixed-integer linear programming）差分/线性刻画方法，建立并求解了MILP 模型来搜索最优差分/线性链，拉开了利用MILP 自动化搜索技术分析密码算法的序幕[17-21]。MILP 自动化搜索的关键在于MILP 模型的刻画与快速求解，为了提高求解速度，研究者需要根据密码算法的特点，给出快速求解MILP 模型的方法，如Zhou 等[22]针对代换-置换网络（SPN）结构的分组密码算法提出了分而治之策略；刘帅等[23]针对MORUS 算法的结构特点根据 ΔI V的重量将MILP模型划分为多个子模型，根据MORUS 算法差分状态的循环等价性省略部分子模型的求解。

LWCA 第二轮的候选算法ACE 由Aagaard 等[24]提出，是基于ACE 置换设计的双工海绵结构轻量级密码算法，包括认证加密算法ACE-AE-128 和哈希算法ACE-H-256。研究者在设计报告中做出了较粗略的差分分析，利用最小活动SB-64 的数量给出了ACE 置换抗差分分析的安全边界。

2020 年，Liu 等[25]提出了ACE 置换不可能差分的自动化搜索算法，证明了ACE 置换不存在9 步以上的不可能差分，并给出了8 步不可能差分。2021 年，叶涛等[26]针对ACE 算法给出了12 步ACE 置换的积分区分器，相比于研究者给出的区分器提高了4 步，取得了较大的改进。2022 年，Chang 等[27]给出了ACE 算法的伪造攻击。对于差分分析，仍没有第三方给出较精确的分析结果。

差分分析是研究密码算法安全性强有力的分析方法，近几年，针对轻量级密码算法的差分分析得到了广泛的研究。2022 年，蒋梓龙等[28]针对Saturnin 算法给出了5.5 轮不可能差分攻击。同年，Dunkelman 等[29]给出了相关密钥下全轮TinyJUMBU-192/256 的差分伪造攻击。

本文基于自动化分析工具MILP对ACE算法的差分性质进行研究。利用MILP 搜索差分链，首先给出算法中非线性操作差分性质的MILP 刻画，给出的刻画越精确，就能更大程度地确保搜索得到的差分链的概率最大。ACE 算法中的唯一非线性操作为与门，对于ACE 置换，SB-64 轮函数中的32 个与门的输入之间存在紧密的关系，如何充分考虑与门之间的相互关系是要解决的首要问题，本文将这32 个与门转化为环形与门组合，给出了环形与门组合差分性质精确的MILP 刻画。为了提高MILP 差分模型的求解速度，本文采用了如下方法：1) 利用最小活跃SB-64 的数量给出目标函数的下界；2) 利用环形与门组合输入差分重量与差分转移概率之间的关系，增加约束条件，缩减MILP 模型的可行域与变量的取值范围。最后给出了ACE 置换的高概率差分链，为了提高差分链的概率，搜索了具有相同输入、输出差分的差分链。利用搜索到的差分链，给出了对ACE 算法的攻击方法：ACE 置换为3 步的简化版ACE-AE-128 的差分伪造攻击，以及简化版ACE-H-256 的差分碰撞攻击。

1 背景知识

1.1 轻量级密码算法ACE

ACE 是由Aagaard 等[24]提出的轻量级密码算法，包括认证加密算法ACE-AE-128 与哈希算法ACE-H-256。ACE 算法的设计采用基于ACE置换的双工海绵结构，ACE 置换是ACE 算法的主体部分，其规模为320 bit，第i步状态表示为5 个64 bit(Ai,B i,C i,D i,E i)(i= 0,1,2,…,16)，ACE置换由ACE-step 迭代16 次，图1 展示了ACE-step。其中，第i步ACE-step中使用了6 个8 bit 的轮常数。

图1 ACE-step

ACE置换的非线性环节SB-64是一个减轮的不带密钥的分组密码Simeck[2]，其分组规模为64 bit，轮数为8，采用Feistel 结构，轮函数如图2 所示。

图2 SB-64 轮函数

对于认证加密算法ACE-AE-128 与哈希算法ACE-H-256，其状态大小均为320 bit，状态S中有r=64 bit 进行数据的输入与输出，称为比率部分，记为Sr。比率部分由320 bit 状态S=A||B||C||D||E中的8 个字节组成，分别为A[ 7]、A[ 6]、A[ 5]、A[ 4]、C[ 7]、C[6]、C[ 5]、C[ 4]，其中，A[j]、C[j]分别表示A、C的第j个字节。对于算法ACE-AE-128 与ACE-H-256 的具体结构，这里不再赘述，可参照其设计报告[24]。

1.2 差分伪造攻击与差分碰撞攻击

对于认证加密算法，伪造攻击的基本思想是如果攻击者能够构造出未经询问的合法消息密文对则伪造成功，按照构造认证码的方式不同，将其分为差分伪造攻击和直接伪造攻击。差分伪造攻击是指攻击者在已掌握消息密文对的情况下，利用差分分析方法，构造出另一对消息密文对且能够通过验证。

哈希算法要求对于不同的消息，必定得到不同的哈希值。差分碰撞攻击的思想是利用高概率差分对应找到一对不同的消息，其对应的哈希值相同，这样哈希算法便是不安全的。

令SΔ表示320 bit 状态差分，其比率部分差分为Δ ≠ 0，其余比特差分为0，寻找ACE 置换一条高概率的差分链，其差分转移概率为P，根据该差分链，可以构造认证加密算法ACE-AE-128 的差分伪造攻击以及哈希算法ACE-H-256 的差分碰撞攻击。

1) 认证加密算法ACE-AE-128 的差分伪造攻击

已知 Nonce、相关数据、明文组(N,A0⊕Δ1||A1⊕Δ2,M)，询问ACE-AE-128 加密机得到认证码T，则认证码T对 (N,A0||A1,M)以概率P有效。同样地，也可以在明文处理阶段加入差分构造攻击。图3 给出了ACE-AE-128 的差分伪造攻击示意。

图3 ACE-AE-128 的差分伪造攻击示意

2) 哈希算法ACE-H-256 的差分碰撞攻击

已知初始变量、明文对 (IV,M0⊕Δ1||M1⊕Δ2)，询问ACE-H-256 加密机得到哈希值H，则初始变量、明文对 (IV,M0||M1)的哈希值与H以概率P产生碰撞。图4 给出了ACE-H-256 的差分碰撞攻击示意。

图4 ACE-H-256 的差分碰撞攻击示意

2 ACE 的MILP 差分模型

本节给出了ACE 的MILP 差分模型，主要研究了其非线性环节差分特性的MILP 刻画。由于ACE的状态较大，每一步迭代多轮Simeck 轮函数，MILP模型很难求解，本文利用ACE 算法中非线性环节差分转移概率与输入差分重量之间的关系给出了MILP 差分模型的快速求解方法。

2.1 环形与门组合及其MILP 差分刻画

从图5 可以看出，ACE 中的非线性操作实际是一个32 维环形与门组合，上述转换本质上是将SB-64同一轮的32 个与门利用线性变换进行移位，更直观地展示了32 个与门之间的相互关系，使2 个相邻的与门具有一个共同的输入，便于利用数学化的推导进行下一步分析。此外，将ACE 中的非线性操作归纳为n维环形与门组合，对环形与门组合进行研究，使研究结果可以应用于更多的场景，比如SIMON 算法轮函数中的与门同样可以转化为多维环形与门组合，其维数取决于分组的规模。本节将给出n维环形与门组合的MILP 差分刻画，值得一提的是，Saha 等[21]在分析认证加密算法TinyJUMBU 时，给出了函数f(x0,x1,…,xn-1)=(x0x1,x1x2,…,x n-2xn-1)的MILP 差分刻画，称其为链形与门组合。与链形与门组合不同的是，n维环形与门组合在链形与门组合的基础上增加了一个与门，即最后一个输入xn-1与第一个输入x0经过一个与门输出yn-1，这使n个与门之间的相互关系更加复杂，下面给出具体的分析及刻画。

图5 环形与门组合的示意

其中，|表示逻辑或，对应的目标函数为

式(1)并没有考虑n个与门之间的相关性，实际上，不同与门的输入之间是相互关联的，所以这种简单的刻画显然不准确，为了给出精确的刻画，需要分析环形与门组合中n个与门之间的相关性。参考文献[21]，观察 2 个相邻与门xi xi+1,xi+1xi+2的情况，上述刻画认为这2 个与门相互独立，其差分特性满足

但实际上，式(2)并不一直成立。表2 给出了输入差取遍所有值时式(2)的成立情况。

由表2 可知，只有当相邻2 个与门的输入差为(1,0,1)时，2 个与门的差分传递概率之间存在相关性，这容易从单个与门的差分特性进行解释，当输入差为(1,0,1)，根据表1，输出差为 Δxi xi+1=Δxi+1xi+2=xi+1，据此，在g(x0,x1,…,xn-1)的MILP 差分刻画中增加如下限制条件，其中，i=0,1,2,…,n-1。

表1 单个与门的差分特性

表2 输入差取遍所有值时式(2)的成立情况

最后，还需要考虑一种特殊情况，即输入差为全1 的情况。定理1 给出了这种情况下不同输出差对应的差分转移概率。

对于n维环形与门组合g(x0,x1,…,xn-1)，当输入差为全1 时，输出差中1 的个数与n具有相同的奇偶性，为此加入如下限制条件

其中，dummy 是一个辅助变量。当且仅当所有i∈ { 0,1,…,n- 1}，满足idi=1时，λ=1（即输入差为全1），此时，第二个等式使输出差中1 的个数与n具有相同的奇偶性；其他情况下，第二个等式不起任何作用。在输入差为全1 的情况下，最后一个与门与前n-1个与门具有相关性，因此目标函数应该减去λ。λ= id0id1…i dn-1与线性表达式等价。

综上，式(1)、式(3)和式(4)给出了n维环形与门组合g(x0,x1,…,xn-1)完全精确的MILP 差分刻画，目标函数为。

式(1)、式(3)和式(4)共包含5n+2个线性表达式、一个二次表达式以及n个逻辑或表达式。如果单纯把n维环形与门组合g当作一个大规模的S 盒处理，由于规模过大，利用之前关于S盒的MILP刻画技术[30]很难对函数g进行有效刻画，本文仅利用O(n) 个表达式精确刻画了n维环形与门组合g的差分特性，并验证了以上刻画是完全精确的。

2.2 MILP 差分模型的快速求解

为了提高搜索差分/线性链的速度，Zhou 等[22]针对SPN 结构与Feistel 结构的分组密码给出了MILP 模型的分而治之求解策略，其基本思想是缩减MILP 模型的可行域，这部分可行域由于活跃S盒的数量较多，不包含较好的差分/线性链。Zhou等[22]的方法并不适用于ACE 算法，由于ACE 算法的非线性环节（环形与门组合）规模较大，把环形与门组合当作S 盒处理仅考虑其活跃性，会忽略很多细节。由于ACE 的状态规模较大，且轮函数较为复杂，其MILP 差分模型很难求解，本节结合Gurobi 求解器及ACE 的特点，给出了提高MILP差分模型求解速度的方法。

对于一条差分链，假设其差分转移概率为P≠ 0，称 -lbP为差分转移概率的重量。求解差分链的最大差分转移概率即求解差分转移概率重量的最小值，这与2.1 节中给出的目标函数一致。按照2.1 节的刻画方法给出R步ACE-step 的MILP差分模型，记该模型为 M1，并利用Gurobi 求解器求解该MILP 差分模型，Gurobi 求解器实时返回当前的最优解CB 以及最优解的下界LB，当CB=LB 时，Gurobi 确定CB 为该模型最优解B并返回该解，据此可以将Gurobi 求解过程分为2 个主要部分：1) 求解当前最优解CB，直到得到全局最优解B；2) 计算更紧致的下界LB，直到LB=B。

根据经验，在Gurobi 的求解过程中，往往能够较快地给出全局最优解B，而绝大部分时间都被用来收紧下界LB，使LB 的数值逐渐增加，逼近数值B。根据Gurobi求解过程的特点，给出2种方式来提高MILP差分模型 M1的求解速度：1) 建立一个粗略的MILP差分模型 M2，给出模型 M1目标函数的紧致下界，以提高求解过程第二部分的速度；2) 通过分析环形与门组合的差分转移概率与输入差之间的关系，加入一些限制条件缩减MILP 差分模型 M1的可行域或者缩小变量的取值范围，从而提高求解过程第一部分的速度。

2.2.1 MILP 差分模型下界的确定

本节建立了一个MILP差分模型 M2，对于R步ACE-step，ACi,j∈{ 0,1}表示第i(i=0,1,…,R-1)步ACE-step 中第j(j= 0,1,2)个SB-64 的活跃性，当且仅当该SB-64 的输入差不为0 时，ACi,j=1，否则ACi,j=0，目标函数为。

2 种模型的区别仅在于模型 M1的目标函数是使差分链的差分转移概率重量达到最小，而模型M2的目标函数是使差分链中活跃SB-64 的数量达到最小。由于目标函数更加简单，后者的求解变得非常容易。对于一个活跃的SB-64，其差分转移概率的重量最小值为18[31]，由此容易得到定理2。

定理 2对于R步 ACE-step，假设其活跃SB-64 的最小数量为v，则其差分转移概率的重量下界为18v。

证明对于R步ACE-step 的任意一条概率为P= 2-p≠ 0的差分链，其活跃SB-64 的数量为w，设第i(i= 0,1,…,w- 1)个活跃SB-64 的差分转移概率重量为pi，则，所以差分转移概率的重量下界为18v。证毕。

定理2 给出了一种确定MILP 差分模型 M1目标函数下界的方法，由于Gurobi 求解过程第二步花费的时间远大于第一步，这种方法大大提升了模型M1的求解速度。表3 给出了不同步数ACE 置换活跃SB-64 的最小数量及其搜索时间。

表3 不同步数ACE置换活跃SB-64的最小数量及其搜索时间

2.2.2 增加MILP 差分模型的限制条件

ACE 中唯一的非线性操作是环形与门组合，根据2.1 节的分析直观地得出一个结论：环形与门组合的输入差分重量越小，差分转移概率越大。定理3具体分析了环形与门组合的差分转移概率与输入差分重量之间的关系。

定理3假设n维环形与门组合的输入差分为id= (id0,id1,…,idn-1)，id 的重量为，对于任意输出差分，满足差分转移概率P≠ 0，则概率P具有P= 2-p的形式，其中p为非负整数，且有

证毕。

本文的MILP 差分模型刻画了R步ACE-step（R是一个正整数），每一步ACE-step 包含24 个环形与门组合，则R步共包含24R个环形与门组合，假设这些环形与门组合之间是相互独立的，对于R步ACE-step 的一条差分链，根据定理3 容易得到差分链的差分转移概率与环形与门组合的输入差分重量之间的关系，即推论1。

根据前面的分析，Gurobi 求解器会实时返回当前最优解CB，且利用2.2.1 节中的方法可以确定最优解的下界LB，令SUM 表示MILP 模型中所有24R个环形与门组合的输入差分变量的和，设定当Gurobi 求解器长时间没有返回更优的解时，根据当前的最优解CB 以及最优解的下界LB 加入以下限制条件。

根据推论1，条件1 删除了MILP 模型的部分解，这部分解对应的目标函数不小于CB，所以必然不包括更优的解；条件2 删除了MILP 模型中变量的部分取值，这部分取值必然不构成一个有效解，假设其构成一个有效解，那么该解对应的目标函数小于LB，产生了矛盾。条件1 缩减了MILP模型的可行域，条件2 缩减了MILP 模型中变量的取值范围，这些限制条件使MILP 模型的求解速度大幅提升。

通过以上加速方法，经过实验验证，3 步ACE 置换MILP 差分模型求解时间由3 700 s 降低到1 900 s，4 步ACE 置换MILP 差分模型求解时间由24 200 s降低到10 600 s，而对于5 步ACE 置换，加速前的模型无法在有限时间内完成求解过程，而加速后的模型求解大约花费了2 天时间。

3 ACE 的差分分析

ACE 算法中的ACE 置换包含16 步ACE-step，本文主要分析了R步ACE-step 的ACE 置换的差分特征，在本文的分析中，限制ACE 置换输入差与输出差中64 bit 比率部分非0，其余比特为0。本节首先给出了文献[24]的差分分析结果，然后给出了本文的分析结果。

3.1 文献[24]的差分分析结果

文献[24]中给出了ACE的差分分析结果，目前，对于ACE 算法，尚没有进一步的差分分析结果，文献[24]利用MILP 自动搜索技术，求解出16 步ACE-step 中活跃SB-64 数量的最小值为21，其中SB-64 的差分转移概率上界为 2-15.8，由此得到了16步 ACE-step 的最大差分转移概率的上界2-15.8×21= 2-331.8＜ 2-320，这样16 步ACE-step 保证了ACE 置换达到差分安全边界 2-320，使ACE 状态与随机320 bit 状态不可区分。

3.2 本文的差分分析结果

本文对ACE 置换建立MILP 差分模型，从而搜索其高概率差分链，ACE 置换中的线性操作包括异或、移位，其中，移位操作只需要改变差分值的位置，不需要进行额外的刻画。

对于比特异或a⊕b=c，可以用等式Δa+Δb+Δc= 2dummy 刻画其差分性质，这里需要引入一个整数变量dummy。

2.1 节将ACE 置换中的非线性操作转化为32 维环形与门组合，并给出了其差分性质精确的MILP刻画，综上，可对ACE 置换的差分性质利用MILP进行全面的刻画，并通过Gurobi 求解器进行求解。

本文搜索了ACE 置换的步数为1～6 时的差分链，表4 给出了最优搜索结果，当步数为1、2 时，没有满足条件的差分链。

表4 ACE 置换差分链最优搜索结果

对于表4 给出的差分链，搜索具有相同输入差、输出差的多条差分链，从而得到更大、更精确的差分传递概率。例如，当步数为3 时，找到一条概率为 2-98的差分链，表5 给出了这条差分链，固定其输入差 ΔS0以及输出差 ΔS3，搜索得到多条大概率的 差 分 链，计 算其概率之和为 2-98× 6+2-99× 13+2-100× 183+2-101× 627+2-102× 671 ≈ 2-90.52。

表5 3 步ACE 置换概率为 2-98的差分链

对表4 中3～6 步的差分链均做此处理，表6 给出了多条差分链的概率之和。

表6 多条差分链的概率之和

根据以上搜索结果，本文给出了减轮认证加密算法ACE-AE-128 的差分伪造攻击和减轮哈希函数ACE-H-256 的差分碰撞攻击，当ACE 置换的步数为3 时，差分伪造攻击的成功概率为 2-90.52，差分碰撞攻击的成功概率为 2-90.52。文献[24]指出，ACE-AE-128 的认证安全目标为 128 bit，ACE-H-256 的碰撞安全目标为128 bit。从表6 可以看出，4 步 ACE 置换可以保证认证加密算法ACE-AE-128 抗差分伪造攻击，哈希算法ACE-H-256 抗差分碰撞攻击。

4 结束语

轻量级密码算法ACE 是LWCA 征集活动中第二轮的候选算法，文献[24]给出了较粗略的差分分析结果，为了给出进一步的结果，本文利用自动化分析工具MILP 对ACE 算法的差分性质进行研究，首先给出了ACE 算法非线性操作差分性质精确的MILP 刻画，实际上，该部分工作可以直接应用到SIMON、Simeck 等密码算法的分析中；然后给出了ACE 置换的高概率差分链，并利用多差分技术提高差分链的概率，分别给出了ACE-AE-128 的差分伪造攻击与哈希函数ACE-H-256 的差分碰撞攻击。

本文的工作为利用自动化分析工具研究基于与门设计的密码算法的差分性质提供了理论参考与技术基础，下一步考虑将环形与门组合的MILP差分刻画进行扩展并应用到更多相关算法的差分分析中，尝试给出改进的差分分析结果。