Trivium 算法的立方攻击*

穆道光，胡建勇，苗旭东

（1.中国电子科技集团公司第三十研究所，四川 成都 610041；2.保密通信重点实验室，四川 成都 610041）

0 引 言

立方分析是2009 年欧密会上以色列密码学者Dinur 和Shamir 提出的一种密码算法分析方法[1]，目前已成为对称密码算法中一种常见的分析方法，针对流密码算法[1-7]、哈希算法[1-2,4-5]、认证加密算法[8]等许多典型算法，采用立方分析能得到很好的分析效果。

2017 年美密会上，日本密码学者Todo 等人[4]提出了基于可分性的立方分析方法。该方法借助于混合整数线性规划（Mixed Integer Linear Programming，MILP）求解工具，可以判断出较大规模立方变量集（如大于或等于70）对应的超级多项式中包含的密钥比特变量。2018 年美密会上，王庆菊等人[5]对Todo 等人提出的基于可分性的立方分析方法作了改进，提出了标记技术（Flag Technique）、单项式枚举（Term Enumeration）、代数次数评估（Degree Evaluation）等方法，能够进一步判断出立方变量集对应的超级多项式的代数式次数、可能包含的单项式及数量。2020 年亚密会上，胡凯等人[6]提出了基于单项式预估（Monomial Prediction）的立方攻击方法；同年欧密会上，郝咏霖等人[7]提出了基于不带未知集的三子集可分性的立方攻击方法，以上两种方法都能够准确地判断超级多项式的代数表达式，虽然研究的角度不同，但本质上是等价的，且均需要运用Gurobi、Cplex 等工具求解出MILP 模型的所有可行解。当MILP 模型规模庞大、可行解数量过多时，求解模型所有可行解往往需要耗费大量的时间和内存，例如，上述两种方法都只恢复出初始化842 轮的Trivium 算法的立方变量集对应的超级多项式表达式，当初始化轮数提升至843 轮时，持续数月求解相应的MILP 模型，均无法得到最终结果。针对上述问题，2021 年亚密会上，胡凯等人[2]提出了嵌套单项式预测方法（Nested Monomial Predictions），其思想是将大轮数对应的MILP 模型反复分解为若干小轮数对应的MILP 模型，同时，设置轮数步长以控制分解后的模型数量，设置模型求解时间戳以限制每个分解后的模型求解时间。通过该方法，能够恢复出初始化843、844、845 轮的Trivium 算法的立方变量集对应的超级多项式表达式，其中恢复出初始化845 轮的Trivium 算法的立方变量集对应的超级多项式表达式的时间约21 天。

2021 年，Delaune 等人[3]根据序列密码算法中的状态转移关系式，提出了一种基于有向图的建模方法。与基于可分性的建模方法相比，该方法建立的MILP 模型更加简单，求解MILP模型的时间消耗更少，Delaune 等人恢复出初始化842 轮的Trivium 算法的立方变量集对应的超级多项式表达式的时间约3 小时，但没有给出初始化更高轮数Trivium 算法的立方攻击结果。

本文结合Delaune 等人的有向图建模方法以及胡凯等人的模型分解方法，提出一种Trivium算法的攻击算法。

1 基本知识

本文介绍了立方攻击基本原理、胡凯等人提出的嵌套单项式预测方法以及Delaune 等人提出的基于有向图建模方法等相关的基本知识。

1.1 立方攻击

1.2 嵌套单项式预测方法

（3）若Gurobi 求解器在时间戳0t 内没有反馈出MILP 模型有无解或者没有解出所有解，则设置新的轮数步长，计算出所有的的路径数量，设置新的时间戳1t ，运用Gurobi 求解器在时间1t 内判断每个集合的奇偶性；以此反 复直到Gurobi 求解器的反馈结果中不包含没有解出的MILP 模型。

1.3 基于有向图的建模方法

2021 年，Delaune 等人根据序列密码算法中的状态转移关系式，提出了一种基于有向图的建模方法。与基于可分性的建模方法相比，该方法建立的MILP 模型包含的变量或约束条件更少。

Delaune 等人将序列密码的中间状态变量和多项式关系用有向图G 表示。其中，有向图G 中的节点为序列密码的中间状态变量，有向图G 中的边x y→ 为变量y 在变量x 的代数表达式之中。

例如，变量1x ,2x ,3x ,1y ,2y ,1z ,2z 及它们之间的多项式关系为：

对应的有向图 G = (V , E)如图1 所示，有向 图G 中表示的节点，

用T 表示由根节点的代数表达式中的单项式对应的一条传播路径，边之间存在的逻辑关系为：

以边E 中的元素为模型变量，得到的模型包含8 个变量、6 个约束关系，相较于基于可分性建立的模型，变量和约束关系均较少。

针对Trivium 算法，Delaune 等人给出了其模型建立方法。Trivium 算法的状态转移关系为3 个二次非线性关系式，每个关系式包含了5个变量，特别地，二次关系对应的边用双线边（Double Edges）表示，线性关系对应的边用单线边表示，因此，每个节点（除叶子节点外）均有5 条边，其中2 条为双线边。

设 ( )Pred i 为节点i 的父节点， ( )Succ i 为节点i 的单线边对应的子节点及双线边对应的其中1 个子节点， brother1( i )和 brother2(i )分别为节点i 的双线边对应的2 个子节点。在模型中，用布尔变量 ,i jX 验证边i j→ 是否存在于路径T 之中，若(i, j ) ∈ T，则 Xi,j= 1；若(i , j ) ∉ T，则Xi,j= 0。 Xi,j满足以下的约束关系：

类似地，通过运用Gurobi 求解上述变量及约束关系建立的模型的所有可行解，当密钥变量的叶子节点组成的向量v 对应的可行解数量为奇数时，对应的 kv为超级多项式 p ( x′ , k )中包含的单项式。

为了提高模型求解效率，Delaune 等人还提出了一些优化方法，包括增加约束以尽可能多地排除可行解数量为偶数的向量v、设置模型中变量的BranchPriority 权值和VarHintVal 值以加速Gurobi 求解速度等。

2 Trivium 算法的立方攻击

本节首先介绍Trivium 算法，其次给出对Trivium 算法的攻击算法。

2.1 Trivium 算法简介

Trivium 算法采用非线性反馈移位寄存器设计，内部状态共为288 比特，记为 s1, s2, …,s288，分为3 个寄存器A，B，C，其中，寄存器A 包含93 比特状态，寄存器B 包含84 比特状态，寄存器C 包含111 比特状态。

Trivium 算法使用80 比特密钥变量 k1, k2, …,k80和80 比特初始值IV 变量 v1, v2, … , v80，初始填充过程如下：

填充完成后进行1 152 轮迭代，每轮迭代中，首先计算中间变量t1, t2, t3：

其次更新寄存器A , B , C：

迭代完成后，输出密钥流比特z 为：

2.2 攻击算法

本文结合了有向图建模方法以及模型分解方法，提出一种针对Trivium 算法的快速立方攻击方法，攻击过程中需要使用的一些算法如下文所述。

算法1 用于得到有向图中的节点变量下标。

算法1：节点变量下标算法getvar

输入：整数a 为节点变量x 的下标

输出：整数b 为节点变量x 之前与其相等的节点变量的下标

1 若 288a ＜ ，返回b a= ；否则，转到步骤2

2 令 c = a%288，若 c= 0或 c= 93或 c= 177， 返回b a= ；否则，转到步骤3

3 返回 getvar ( a- 288 -1)

算法2 用于得到根节点向量为s 的r 轮Trivium 算法的有向图G。

算法2：有向图算法getG

输入：轮数r，根节点向量s

输出：字典g，其中，键表示有向图G 中的节点的变量下标，键值表示键节点对应的子节点的变量下标

5 返回g

算法3 用于根据节点向量为s 的r 轮Trivium算法的有向图G，得到其另一种等价表示。

算法3：有向图等价表示算法getG′

输入：字典g，其中，键表示有向图G 中节点的变量下标，键值表示键节点对应的子节点的变量下标

输出：字典g′ ，其中，键表示有向图G 中节点的变量下标，键值表示键节点对应的父节点的变量下标

1 g′ =∅

2 对g 中任意的键x，记其键值为 [ ]y g x= ， 对任意的z y∈ ，若g′ 中不含键z，则将键z 及键值x 放入g′ 中；若g′ 中已包含键z，则将x加入键z 的键值， [ ]g′ z x←

3 返回g′

算法4 用于得到根节点向量为s、叶子节点向量为l 的r 轮Trivium 算法的MILP 模型M。其中，叶子节点向量l 由立方变量集和非立方变量集决定，设cube 为立方变量集，ncube 为非

立方变量集，则0 ≤ j≤288，l 中的元素赋值为（其中*表示未知或待定值）：

算法4：建模算法getM

输入：轮数r ，根节点向量s，叶子节点向量l

输出：MILP 模型M

5 返回M

算法5：Trivium 算法的攻击算法

输入：攻击轮数r，立方变量集cube，非立方变量集ncube

输出：可行路径数量sol

1 初始化起始根节点集合S、轮数步长0r 和时间戳0t

起始根节点集合S 由密钥流输出函数得到，因输出密钥流比特由6 个状态比特异或得到，故S 包含6 个元素。设 S = { s0: 1, s1:1, s2:1, s3:1, s4:1, s5:1}，其中 s0， s1， s2， s3， s4， s5均为288 维、权重为1 的二进制向量，s0[ 6 5 ] = 1 ，s1[92] = 1，s2[ 1 6 1 ] = 1 ，s3[ 1 7 6 ] = 1 ，s4[ 2 4 2 ] = 1 ，s5[ 2 8 7 ] = 1

设起始轮数步长0r 为100，起始时间戳0t 为50 秒

2*S =∅，对任意的根节点向量 S∈s ，建立 MILP 模型 M= getM ( r0, s, ∅)，运用Cplex 等求解工具求解出模型M 的所有解

记 s*为一个288 维布尔向量，令 0 ≤ x ≤ 287，如果x 是模型M 中的叶子节点下标，若则 s*[ x ] =1，若则 s*[ x ] =0；如果x 不是模型M 中的叶子节点下标，对应的模型M 的可行解数量为 ns*，添加到*S 中

3 若 S**=∅，对任意的根节点向量 s*∈S*， 建立模型，运用Cplex 等求解工具在时间戳0t 内求解模型*M 的所有解。若模型*M 无解，说明没有从向量l 到*s 的传播路径；若模型*M 有解，则求解出所有解，记l对应的模型*M 的可行解数量为nl，则统计l 及其对应的可行解数量为。若时间戳0t 内无法得出模型*M 有无解或者没有解出所有解，将添加到 S**中

4 若S**=∅，则终止；否则，转到步骤5

5 令 S = S**， r = r - r0，重新设置轮数步长0r 和时间戳0t ，转到步骤2

3 实验结果

攻击实验采用的MILP 求解工具为IBM 的Cplex 软件，版本号12.7.1。实验中采用5 台联想SR850 服务器并行求解模型，每台服务器含两个处理器，每台处理器CPU 均为Inter Xeon Gold 5117（2.00 GHz），核 心 数28，内 存256 GB。攻击轮数0r 为845，攻击中选取的立方变量集cube 和非立方变量集ncube 如表1 所示。

表1 选取的立方变量集和非立方变量集

轮数步长0r 和时间戳0t 可以按照表2 进行设置。

表2 轮数步长和时间戳的设置

攻击效果对比如表3 所示，可以看出，本文通过使用有向图建模方法以及模型分解方法，恢复845 轮Trivium 算法的超级多项式的时间明显减少。

表3 845 轮Trivium 算法立方攻击效果对比

4 结 语

为提高Trivium 算法立方攻击中恢复超级多项式的攻击效率，本文提出了一种快速方法，结合了有向图建模方法和模型分解方法，恢复845 轮Trivium 算法的超级多项式的时间明显减少。后续将继续研究这种立方攻击方法的改进及其在其他序列密码算法上的应用。