序列密码立方攻击研究进展综述*

田 甜, 戚文峰

信息工程大学, 郑州 450001

1 引言

2000 年前后, 相关攻击和代数攻击的发展对基于线性反馈移位寄存器(LFSR) 的序列密码算法的安全性构成严重威胁.2004–2008 年, ECRYPT 启动了序列密码征集项目eSTREAM, 出现了一批基于非线性序列源的序列密码算法.特别地, 非线性反馈移位寄存器(NFSR) 广泛用于面向硬件实现的序列密码算法, 例如eSTREAM 项目面向硬件实现的胜选算法Trivium 以及Trivium 的128 比特密钥版本Kreyvium、Grain 系列算法等都是典型的基于NFSR 的序列密码算法.采用NFSR 作为序列源, 可以有效抵抗针对基于LFSR 序列密码算法的相关攻击和代数攻击.近十年, 立方攻击是针对基于NFSR 序列密码算法的重要攻击方法, 在Trivium、Kreyvium、Grain 系列算法的安全性分析方面不断取得新的进展.目前, 在立方攻击基础上发展的攻击方法有: 实验立方攻击、基于可分性的立方攻击、动态立方攻击、相关立方攻击等.

立方攻击由Dinur 和Shamir 在2009 年欧密会上首次提出[1], 是一种高阶差分攻击和代数攻击.立方攻击的基本思想是通过对序列密码的初始化向量(IV) 进行差分, 获得关于密钥的低次方程组.在立方攻击中, 每个立方集(cube) 对应了一个关于密钥的多项式, 称为关于该立方集的超多项式(superpoly),其中立方集一般是IV 的一个仿射子空间.由于基于NFSR 的序列密码是迭代型密码算法, 经过初始化算法后, 输出密钥流比特关于密钥和IV 的代数正规型是未知的并且规模很大, 在文献[1] 中, 自然将输出密钥流比特看作密钥和IV 的黑盒布尔函数, 通过线性检测的方法搜索线性超多项式.文献[1] 具体恢复了一批672 轮和767 轮Trivium 的线性超多项式.2013 年, 文献[2] 提出利用Möbius 变换原理对一个大立方集的部分子集同时进行超多项式的线性检测或二次检测, 给出了784 轮Trivium 的42 个线性超多项式、799 轮Trivium 的12 个线性和6 个二次超多项式.文献[3] 针对Trivium-型算法, 提出线性化技术,降低检测Trivium-型算法二次超多项式的复杂度, 给出了802 轮Trivium 的6 个线性超多项式和2 个二次超多项式、776 轮Kreyvium 的8 个二次超多项式.以上立方攻击称为实验立方攻击或传统立方攻击,都是通过黑盒布尔函数检测的方法判断超多项式的代数次数和恢复代数正规型.

在实验立方攻击中, 对一个d维立方集的超多项式进行一次线性检测的复杂度是O(2d), 因此, 实际计算资源限制了立方集的维数很难超过40 维, 目前文献中最大的立方集是43 维[4].2017 年, Todo 等人将分组密码搜索积分区分器的可分性(division property) 引入到立方攻击中[5], 结合混合整数线性规划(mixed integer linear programming, MILP) 模型可以处理高维立方集的超多项式.对于给定的立方集, 文献[5] 利用基于MILP 建模的二子集可分性可以排除一部分不出现在超多项式中的密钥变元, 降低恢复超多项式的复杂度.然而, 文献[5] 的方法包括后续的改进方法[6]均不能准确恢复超多项式的代数正规型, 这也导致文献[6] 中所列833 轮到839 轮Trivium 的密钥恢复攻击均是无效的, 实际是区分攻击[7].2019 年, 文献[7] 提出基于二子集可分性的代数方法, 文献[8] 提出基于三子集可分性MILP 建模的超多项式恢复方法, 均可以准确恢复超多项式的代数正规型, 但都只适用于非常稀疏的超多项式.2020年, Hao 等人在文献[9] 中提出不含未知集的三子集可分性(3SDP/u) 的MILP 建模方法, 解决了基于MILP 建模准确恢复超多项式的问题, 并且基于MILP 建模的超多项式求解效率有了很大程度的提高.利用该模型, 文献[9] 中分别给出了841 轮和842 轮Trivium 的超多项式, 立方集的维数为78, 超多项式的次数为4 次, 项数分别为67 和53, 与之前文献中恢复的超多项式相比, 代数正规型的规模明显增大.2021年, Hu 等人在文献[10] 中提出一个更高效的超多项式恢复算法, 该算法结合了文献[9] 中的3SDP/u 的MILP 模型和文献[7] 中将输出比特表达为中间状态变元布尔函数的分治技术, 可以恢复超大规模的超多项式.在文献[10] 中, 给出845 轮Trivium、191 轮Grain-128AEAD 以及894 轮Kreyvium 的超多项式, 其中845 轮Trivium 超多项式的单项式数量均超过107.2022 年, 文献[11] 对文献[10] 的算法做了一些局部改进, 给出了848 轮Trivium、192 轮Grain-128AEAD、895 轮Kreyvium 的超多项式.当超多项式的规模增长到一千万个单项式时, 其是否平衡都是未知的, 很难评估在密钥恢复攻击阶段的贡献.针对这一问题, 文献[12] 考虑了平衡超多项式的恢复, 针对具有独立线性变元(不在非线性项中出现) 的超多项式提出立方集的筛选算法, 给出一个843 轮Trivium 的平衡超多项式.

对于实验立方攻击和基于可分性的立方攻击, 如何构造立方集或确定一个立方集的选择范围使得以较大概率可搜索到低次超多项式一直是一个困难问题.以实验立方攻击为例, 采用随机搜索立方集的方法,很难找到800 轮以上Trivium 算法的线性超多项式.2021 年, Ye 等人在文献[4] 中, 从实际密钥恢复攻击的角度考虑, 针对Trivium 的线性超多项式搜索给出一个立方集的启发式构造方法, 结合Möbius 变换和线性检测, 对于805 轮Trivium 恢复了1000 多个线性超多项式(含线性相关).随后, 文献[13] 将文献[4] 中构造方法与平衡多项式的筛选以及MILP 建模的超多项式恢复方法相结合, 对于恢复820 轮以下低次超多项式非常有效.

在立方攻击的基础上, 2011 年FSE 会议上, Dinur 和Shamir 进一步提出动态立方攻击[14].在动态立方攻击中, 通过设置动态IV 变元, 可以零化某些中间状态变元, 达到简化输出函数代数正规型的目的,从而一批立方集的超多项式能够形成区分器, 例如零和区分器.利用动态立方攻击, 文献[14] 分析了全轮Grain-128 算法, 给出了一个弱密钥下的攻击结果, 其弱密钥空间为2118.随后, 2011 年亚密会上, Dinur等人改进了这一结果, 利用更低的计算复杂度攻击了全轮Grain-128 算法, 并对该攻击在正确密钥下进行了实验验证, 其中对于7.5% 的正确密钥输出具有明显偏差[15].2020 年, Hao 等人在文献[16] 中指出一个成功的攻击不仅要评估正确密钥的非随机性, 还需要评估错误密钥的随机性.基于这一想法, Hao 等人基于MILP 技术给出评估动态立方攻击成功概率的理论方法, 并对全轮Grain-128 给出一个新的动态立方攻击, 理论上成功概率为99.83%.

针对Trivium 算法的密钥恢复攻击, Liu 等人在文献[17] 中提出了相关立方攻击.相关立方攻击利用超多项式与一组特定的低次多项式(称之为基) 之间的条件相关概率建立关于密钥变元的概率方程.利用该方法, 对于835 轮Trivium 算法, 以244的计算复杂度平均可以恢复5 比特密钥信息.进一步, 2023 年,Che 等人给出了一种新的相关立方攻击框架, 能够以245的计算复杂度恢复844 轮Trivium 算法的4 比特密钥信息[18].

总的来说, 立方攻击方法和技术不断发展, 已成为评估基于NFSR 序列密码算法安全性的重要方法.利用立方攻击, 既可以对密码算法进行密钥恢复攻击, 也可以对密码算法的代数性质进行检测, 具有较好的实用性和通用性.

本文内容安排如下: 第2 节介绍立方攻击基本原理; 第3 节介绍实验立方攻击方法; 第4 节介绍基于可分性立方攻击的研究进展; 第5 节介绍立方集构造研究进展; 第6 节介绍动态立方攻击研究进展; 第7 节介绍相关立方攻击研究进展; 第8 节对全文进行总结.

2 立方攻击基本原理

序列密码算法的每个输出密钥流比特可以自然视为关于密钥Key 和公开初始化向量IV 的布尔函数.以下均以序列密码第一个输出密钥流比特为例进行描述.设f(x,v) 表示第一个密钥流比特关于密钥变元x=(x0,x1,···,xn−1) 和IV 变元v=(v0,v1,···,vm−1) 的函数.选择若干IV 变元, 并记这些IV 变元的下标集合为I ⊆{0,1,···,m −1}, 那么函数f可以唯一地表示成f=t·pI ⊕q, 其中t=∏i∈I vi, 并且q的代数正规型中没有t的倍式.记CI是IV 变元的一组取值, 满足下标在I中的变元独立取遍0/1而下标不在I中的变元固定为常值(通常固定为0).那么,f(x,v) 关于CI求和有

集合CI称为一个立方集(cube),{vi|i ∈I}称为立方变元集,I称为立方变元的下标集, 集合I的基数|I| 称为CI的维数, 多项式pI(x) 称为I的超多项式(superpoly) 或CI的超多项式.

立方攻击由离线阶段和在线阶段两部分组成.离线阶段的主要工作是搜索立方集和恢复超多项式的代数正规型; 在线阶段的主要工作是获得当前密钥条件下超多项式的函数值, 从而得到关于密钥变元的方程组, 求解方程组获得密钥信息.由于序列密码算法在输出第一个密钥流比特以前, 内部状态经过了高轮非线性迭代更新(例如Trivium 是1152 轮初始化), 所以函数f(x,v) 代数正规型的规模非常大, 在攻击中是未知的.因此, 如何恢复超多项式一直是立方攻击的关键问题.

本文如果没有特殊说明, 设f(x,v) 表示支持n比特密钥且m比特IV 的某个序列密码算法的第一个输出密钥流比特, 其中x=(x0,x1,···,xn−1),v=(v0,v1,···,vm−1).

3 实验立方攻击

2009 年, Dinur 和Shamir 提出立方攻击的同时, 也提出超多项式的线性检测方法, 称为实验立方攻击.实验立方攻击将序列密码的输出密钥流比特看作黑盒布尔函数, 通过对黑盒布尔函数的输出进行查询,从而判断超多项式是否是线性函数, 如果是线性函数, 则同样通过查询黑盒布尔函数恢复其代数正规型.

3.1 线性检测和二次检测

将f(x,v) 看作黑盒布尔函数.设I是一个立方变元的下标集,pI是f(x,v) 关于I的超多项式.设a,b ∈Fn2, 通过查询函数f(x,v) 的输出, 可以计算出pI在变元x分别为a,b,a ⊕b,0 时的函数值, 验证下式是否成立

若pI是关于x的线性函数或常值函数, 则式(1)总是成立; 否则,pI是关于x的非线性函数, 则式(1)以一定概率成立.在实验立方攻击中, 对于给定的I, 随机选择a,b ∈Fn2, 重复多次对式(1)进行检测, 若pI通过了所有检测, 则认为pI是线性超多项式1实际中, pI 有可能不是线性函数, 但非常接近线性函数..一般地, 检测的次数越多, 检测结果的正确性越高, 也即pI是线性函数或常值函数的可能性越大.

若pI通过了线性检测, 则仍然通过访问黑盒布尔函数f(x,v) 可以进一步得到pI的代数正规型.设

其中c,c0,···,cn−1是待定的系数.对0≤i ≤n −1,ei ∈Fn2表示第i+1 个分量等于1 且其余分量等于0 的F2上n维向量, 那么

类似线性检测, 也可以对超多项式pI(x) 进行二次检测并恢复函数的代数正规型.设a,b,c ∈Fn2, 若deg(pI(x))≤2, 则

成立; 若deg(pI(x))> 2, 则式(2)以一定概率成立.值得注意的是, 对于相同维数的立方集, 进行1 次二次检测的复杂度是进行1 次线性检测复杂度的两倍.虽然二次检测相较于线性检测, 计算复杂度仅是2 倍增长关系, 实际攻击中很少采用二次检测.主要原因有以下两点:

• 恢复二次超多项式并不能显著降低立方集的维数;

• 随着立方集维数的增长, 例如40 维, 对超多项式进行一次线性检测的计算复杂度超过240, 而判断一个超多项式是否为线性函数需要上百次测试, 这对于普通PC 机已需要耗费大量时间, 2 倍复杂度的增长往往超过了实际能够承受的计算时间.

3.2 Möbius 变换

在立方攻击中, 利用Möbius 变换可以同时对立方变元集I的所有子立方变元集进行线性检测, 这有效提高了检测的效率, 从而增加了攻击成功的可能性.

令h(x0,x1,···,xk−1) 是F2上k元布尔函数, 其代数正规型可以表示为:

已知h真值表 (h(0),h(1),···,h(2k −1)), 利用 Möbius 变换可以计算出h的代数正规型, 即(α0,α1,···,α2k−1), 参见算法1[19].对于一个k元布尔函数, 算法1 的存储复杂度为2k, 计算复杂度为k·2k.

下面介绍Möbius 变换在立方攻击中的应用.注意到在做线性检测时, 关键是求得超多项式在给定密钥下的函数值, 因此, 这里仅需讨论如何同时获得一个立方集全体子立方集的超多项式在给定密钥下的函数值.设I={i1,i2,···,id}是一个立方变元下标集.给定密钥x=a, 并且下标不在I中的IV 变元固定为常值0.那么, 在此条件下,f是关于立方变元的一个函数, 其代数正规型可以表示为

其中J取遍I的所有子集,pJ(a) 是立方变元集{vj|j ∈J}所对应的超多项式在x=a的函数值.当IV 取遍d维立方集CI中的元素时, 记录函数f(a,v) 的2d个函数值, 也即f(a,0,{vi|i ∈I}) 关于变元{vi|i ∈I}的真值表S, 利用算法1, 可得函数f(a,0,{vi|i ∈I}) 代数正规型中全体单项式系数, 由式(3)知, 也即每个单项式∏j∈J vj前面的系数pJ(a).这样就获得了I的全体子集所对应的超多项式在x=a的函数值.

一般地, 在实际攻击中, 对于一个d维立方集, 只需要检测维数较大的子立方集, 不需要检测其所有子立方集, 这是因为随着维数的降低, 找到线性或二次超多项式的可能性越来越小.在文献[4] 中, 针对只考虑大维数立方子集的情形, 作者提出了一种改进的Möbius 变换, 可以降低存储复杂度.

算法1 Möbius 变换Input: h(x0,x1,··· ,xk−1) 的真值表S Output: h 的单项式系数S 1 for i from 0 to k −1 do 5 for j from 0 to Sz −1 do 2 Sz ←2i;3 Pos ←0;4 while Pos < 2k do 6 S[Pos+Sz +j] ←S[Pos+j]⊕S[Pos+Sz +j];7 end Pos ←Pos+2·Sz;9 end 10 end 8

3.3 应用

实验立方攻击主要应用于Trivium 算法.2009 年, 文献[1] 中给出35 个767–774 轮的线性超多项式.2012 年, 文献[20] 中给出38 个709–712 轮的二次超多项式.2013 年, 文献[2] 给出12 个799 轮线性超多项式和6 个799 轮二次超多项式.2018 年, 文献[3] 中给出8 个802 轮线性超多项式和2 个802轮二次超多项式.2021 年, 文献[4] 在结合立方集构造方法条件下, 利用线性检测恢复了大量805 轮线性超多项式以及2 个810 轮线性超多项式, 这是线性检测方法恢复的最高轮数超多项式.

4 基于可分性和MILP 的立方攻击

在实验立方攻击中,对一个d维立方集的超多项式进行线性检测的计算复杂度和存储复杂度是O(2d).所以, 一般情况下, 攻击者至多只能对40 维左右的立方集进行检测, 这在很大程度上限制了立方攻击的效果和基于立方攻击的安全性评估能力.2017 年, Todo 等人将分组密码搜索积分区分器的二子集可分性引入到立方攻击中[5], 结合混合整数线性规划MILP 模型可以有效分析高维立方集对应超多项式的代数性质.基于可分性和MILP 的立方攻击是目前针对序列密码算法最有效且应用最广泛的一类密码分析方法.

4.1 混合整数线性规划

混合整数线性规划(mixed integer linear programming, MILP) 是一类数学优化问题, 由变元、线性限制条件、目标函数组成, 其中部分或全部取值限制在整数范围, 其标准形式可以表示如下:

其中x ∈Zk×Rn−k,A ∈Rm,n,b ∈Rm,c ∈Rn, 且x,b,c是列向量.在一个MILP 模型M中, 用M.var 表示变元,M.con 表示限制条件,M.obj 表示目标函数.常用的MILP 模型求解器有Gurobi[21]等.如果模型有解, 则求解器根据参数设置返回一个解或全部解; 如果模型没有解, 则求解器返回无解.若模型没有目标函数, 则求解器仅返回是否可解.实际上, 在序列密码的立方攻击中, MILP 模型的变元都是取整数0 或1.

4.2 基于比特的可分性

可分性由Todo 在2015 年欧密会上首次提出[22], 是针对分组密码算法的一种广义积分性质, 可用来搜索分组密码的积分区分器.同年, Todo 在文献[23] 中利用可分性得到了MISTY1 算法6 轮积分区分器, 进而给出了MISTY1 算法首个全轮的理论攻击.在2016 年FSE 会议上, Todo 等人针对基于比特运算设计的SIMON 类密码算法进一步提出了基于比特的可分性(bit-based division property), 包括传统的基于比特的可分性(conventional bit-based division property, CBDP) 和基于比特的三子集可分性(bit-based division property using three subsets, BDPT), 以及它们的传播规则[24].在序列密码算法分析中, 主要采用基于比特的可分性.传统的基于比特的可分性与基于比特的三子集可分性的定义如下.

虽然基于比特的可分性能够用来搜索更准确的积分特征, 但是计算其传播所需要的时间和存储复杂度通常比较大.为了解决该问题, Xiang 等人在文献[25] 中引入了基于MILP 建模的搜索方法.文献[25]首次给出了可分路径的概念, 用来描述可分性在分组密码算法中的传播; 同时, 给出了传统的基于比特的可分性关于AND (与运算)、XOR (异或运算) 以及COPY (复制运算) 传播规则的MILP 建模方法.利用自动化工具求解对应的MILP 模型, 显著提高了搜索积分区分器的效率.

是E的一条r轮可分路径.

需要注意的是给定一个输入可分性质k0和一个输出可分性质kr, 可能存在很多条从k0到kr的可分路径.下面给出可分性关于AND、XOR 以及COPY 传播规律的MILP 模型.由于基于比特的分组密码算法和序列密码算法的轮函数都是由这些基本运算构成的, 在此基础上可以建立针对任意加密轮数的可分路径传播模型.特别地, 对于给定输入可分性质k0和输出可分性质kr, 建立的MILP 模型可以覆盖所有从k0到kr的可分路径.

AND 运算的MILP 模型[25].令(a1,a2,···,am)是经过AND 的一条可分性路径, 则下面的不等式描述了AND 运算可分性的传播规律:

4.3 基于二子集可分性的立方攻击

在2017 年美密会上, Todo 首次将传统的基于比特的可分性及其MILP 建模方法引入到序列密码分析中, 提出了基于可分性的立方攻击[5].在文献[5] 中, 利用CBDP 和MILP 建模可以判断哪些密钥变元不出现在给定立方集的超多项式中.下面的命题给出了CBDP 可分路径与超多项式代数正规型的一种联系.

命题1[5]设I是一个立方变元集的下标集,kI ∈Fm2满足vkI=∏i∈I vi.若不存在形如(ej,kI)f−→1 的可分路径, 则xj不出现在pI(x) 的代数正规型中.

基于命题1, 对于给定的一组立方变元集I, 可以建立描述从(ej,kI) 到1 经过函数f的可分性传播模型M, 若模型M无解, 则我们知道密钥xj不出现在I的超多项式pI(x) 中.需要注意的是, 即使MILP 模型M有解, 变元xj也有可能不出现在pI(x) 中.主要原因有以下两点:

• 在CBDP 的MILP 建模中,常值视为常值变元,这意味着只要单项式xjvkI的倍式出现在f(x,v)中, 模型M一定有解, 而实际中非立方变元的取值会影响pI(x) 的具体代数正规型;

• 在CBDP 的MILP 建模中, 没有处理异或运算消项的问题.

基于CBDP 和MILP 建模的立方攻击步骤如下:

离线阶段.选择一个以I为下标集的立方变元集, 利用MILP 模型得到一组不出现在pI中的密钥变元, 剩余的密钥变元记为集合J.随机设定一组非立方变元的取值C, 计算超多项式pI({xj|j ∈J},C)的真值表, 计算复杂度为2|I|+|J|.若pI({xj|j ∈J},C) 是常值函数, 则通过改变非立方变元的取值, 直到对应的超多项式为非常值函数.

在线阶段.对于离线阶段记录的立方变元集I, 设置非立方变元的取值, 使得超多项式pI(x) 是非常值函数.在当前密钥下计算pI(x) 的函数值a, 建立关于密钥的方程pI(x)=a.利用多个立方集, 可以建立关于密钥的一组方程.

穷举搜索阶段.穷尽满足方程解的剩余密钥, 并逐个验证.

在上述攻击中, 当2|I|+|J|超过计算能力时, 实际无法判断超多项式pI({xj|j ∈J},C) 在给定非立方变元取值为C时是否为常值多项式, 因此, 在文献[5] 中提出如下两个假设:

假设1 (强假设) 对于给定的立方变元下标集I,存在很多非立方变元的赋值使得I的超多项式pI(x)是平衡函数.

假设2 (弱假设) 对于给定的立方变元下标集I,存在很多非立方变元的赋值使得I的超多项式pI(x)不是常值函数.

由于MILP 模型对于比较大维数的立方集, 例如70 维, 也可以快速求解集合J, 所以基于假设1 和假设2, 对于维数较大的立方集, 也可以给出密钥恢复攻击的理论分析.据此, 文献[5] 中给出832 轮Trivium、183 轮Grain128a、872 轮Kreyvium 的理论攻击, 立方集的维数分别是72、92 和64.随后, 在2018 年美密会上, Wang 等人对传统的基于比特可分性的MILP 建模方法进行了一些技术上的改进[6],同样基于假设1 和假设2, 给出了839 轮Trivium、891 轮Kreyvium 和184 轮Grain-128a 的理论攻击,立方集维数分别为78、113 和95.

值得注意的是, 上述假设对于Trivium 常常不成立, 例如当集合J非空时, 超多项式仍然可能是零常值, 这意味着任意非立方变元的取值, 超多项式都是零常值.文献[7] 中通过对超多项式的准确计算, 说明了文献[6] 中所给的833 轮–839 轮的5 个超多项式实际都是零常值, 从而与此相关的密钥恢复攻击均不成立, 应是区分攻击.此外, Wang 等人在文献[8] 中也指出文献[6] 的一些立方集的超多项式是零常值.

自2017 年Todo 等人将可分性和MILP 引入立方攻击后, 如何基于可分性理论和MILP 建模恢复准确的超多项式成为序列密码立方攻击的一个重要问题.

2019 年, Ye 等人在文献[7] 中提出一种基于CBDP 恢复超多项式的代数方法, 能够恢复准确的超多项式, 该技术思想在后续文献[10] 的大规模超多项式恢复算法中也有应用.文献[7] 恢复超多项式的基本框架如下.首先, 选择一个立方变元集I.然后, 将输出密钥流比特表达成中间状态变元的函数:

其中U ⊆{0,1}b,αi(x,v) 表示更新过程中某个内部状态比特变元(可以是不同时刻).那么,I在f(x,v)中的超多项式满足

4.4 基于无未知子集的三子集可分性的立方攻击

2020 年欧密会上, Hao 等人在文献[9] 中提出无未知子集的三子集可分性(three-subset division property without unknown subset, 3SDP/u), 从而较好解决了基于MILP 建模的超多项式恢复问题.下面给出3SDP/u 的定义及其对应的MILP 建模规则.

对于传统基于CBDP 的MILP 建模, 目标是找到一条传播路径或判断没有可分路径[5,17].特别地,一个MILP 模型无解时, 攻击者可以知道某个项在超多项式中的系数为0; 而MILP 模型有解时, 攻击者不能确定该项在超多项式中的系数.在3SDP/u 模型中, 给定初始可分性和常值, 一个可行解描述一条可分路径, 可行解与可分路径一一对应, 通过可分路径的奇偶性可以准确知道某个项在超多项式代数正规型中的系数, 从而准确恢复超多项式.具体地, 可行解为偶数的项在超多项式的代数正规型中系数为0, 即因为异或运算而消项, 可行解为奇数的项在超多项式的代数正规型中系数为1, 即真正出现在超多项式代数正规型中的项.因此, 所有奇数路径的可行解即为超多项式的所有项.利用新的建模技术, Hao 等人给出了841 轮Trivium 和190 轮Grain-128AEAD 的密钥恢复攻击[9].

随后, 在3SDP/u 模型基础上, 为了能够给出更高轮数的立方攻击, 一系列针对大规模超多项式的恢复方法被提出.2021 年亚密会上, Hu 等人提出了嵌套单项式预测的恢复超多项式技术[10], 其也采用了和文献[7] 类似的分治技术, 即根据算法内部更新函数的代数表达式, 将输出比特表示为关于中间状态比特的多项式, 通过恢复每个单项式的超多项式进而恢复完整的超多项式.文献[10] 与文献[7] 存在两点不同.第一, 文献[10] 采用3SDP/u 的MILP 模型求每个中间状态比特乘积αc11αc22···αcbb的超多项式, 而文献[7] 采用CBDP 的MILP 模型判断每个αc11αc22···αcbb的超多项式是否为零常值.第二, 通过设置时间阈值,文献[10]提前结束很难求解的模型,即如果在给定时间内关于某个中间状态比特乘积αc11αc22···αcbb的MILP 模型未能求解, 则将该单项式进一步展开, 表示为关于更早时刻中间状态比特的多项式, 再建模计算每个单项式的超多项式.文献[10] 恢复了超过一千万项的845 轮Trivium 超多项式.2021 年亚密会上, 在文献[10] 方法基础上, Hu 等人引入有效项(valuable terms) 的概念, 并提出了两种筛选有效项的新技术,非零比特可分性(non-zero bit-based division property,NBDP)和核心单项式预测(core monomial prediction, CMP)[11].两种新技术在嵌套单项式预测技术中的应用, 能够避免在对超多项式没有任何贡献的中间项上浪费计算资源, 进而恢复了848 轮Trivium、895 轮Kreyvium 和192 轮Grain-128AEAD的准确超多项式, 这是目前这些算法能够恢复的最高轮数超多项式.

5 立方集的构造

随着恢复超多项式的方法越来越有效, 立方攻击的另一个问题, 即如何选择立方集也越来越受关注.可分性的提出使得在立方集的构造上有了新的突破, 一系列基于可分性的构造立方集的方法被提出.2021年, Ye 等人将贪心比特集算法与基于可分性的代数次数估计方法相结合, 给出了用于恢复线性超多项式的立方集构造算法[4].在构造过程中, Ye 等人先启发式地给出一个小维数的初始立方集, 再对其分两阶段添加IV 变元, 从而成功构造了包含线性超多项式的立方集.为方便描述扩展的两个阶段, 首先给出以下两个定义.

定义5[4]令I={vi1,vi2,···,vil}是一个有l个IV 变元的立方变元集.如果一个IV 变元b满足

则称b是一个快速下降IV 变元, 其中B={v0,v1,···,vm−1}I且ds(I) 是立方变元集I在输出中的超多项式的次数.

定义6[4]令I={vi1,vi2,···,vil}是一个有l个IV 变元的立方变元集.如果一个IV 变元b满足

则称b是一个缓慢下降IV 变元, 其中B={v0,v1,···,vm−1}I且ds(I) 是立方变元集I在输出中的超多项式的次数.

基于定义5 和定义6, Ye 等人提出了一个针对线性超多项式的立方集构造方法.给定一个初始立方集I, 在第一阶段中, 对于每次迭代选择快速下降变元对集合I进行扩充, 使得超多项式的代数次数尽可能快地下降.然而, 仅通过添加快速下降变元无法构造具有线性超多项式的立方集.因此, 第二阶段的目标是确保超多项式的次数可以接近1, 而不是突然下降到0.在第二阶段, 通过逐步添加缓慢下降IV 变元,能以更高的概率构造具有线性超多项式的立方变元集.成功构造出候选立方集之后, Ye 等人再利用基于Möbius 的实验检测, 搜索线性超多项式.应用于805 轮Trivium, 得到大量线性超多项式, 给出一个实际密钥恢复攻击.随后, 在文献[13] 中, Che 等人仍利用该方法构造大立方集, 并提出了从大立方集中搜索有价值子立方集的方法.利用3SDP/u 对搜索得到的立方集逐个恢复超多项式, Che 等人给出了815 轮和820 轮Trivium 的实际密钥恢复攻击.

2021 年, Sun 基于实验观察和分治技术, 针对具有独立线性变元的平衡超多项式(该变元不出现在非线性项中), 提出了从大立方集中排除无效立方集的启发式算法, 用来构造具有平衡超多项式的立方集[12],给出了808 轮Trivium 的实际密钥恢复攻击, 并成功恢复了843 轮Trivium 的一个平衡超多项式.这是目前已知的最高轮数平衡超多项式, 大于843 轮的已知超多项式由于规模大, 无法准确判断其平衡性.

6 动态立方攻击

在立方攻击的基础上, 2011 年, Dinur 等人提出动态立方攻击[14].动态立方攻击是针对Grain 系列算法的重要攻击方法.相比立方攻击通过求解密钥方程组来获取密钥信息, 动态立方攻击则是通过区分器来识别正确密钥.在动态立方攻击中, 通过设置Key/IV 变元的表达式条件, 达到简化输出函数f(x,v) 代数正规型的目的; 若动态条件中同时含有密钥变元和IV 变元, 则可以恢复密钥信息.

动态立方攻击将IV 变元分为三类: 立方变元、常值、动态变元, 其中每个动态变元由一个关于立方变元和密钥变元的表达式确定.通过设置动态变元, 可以零化某些中间状态, 使得超多项式有可能呈现出不随机性.在非常理想的情况下, 若密钥猜测正确, 则超多项式可以检测出不随机性, 例如0 常值多项式;若密钥猜测错误, 则超多项式检测为一个随机多项式, 排除错误密钥.2011 年, Dinur 等人利用动态立方攻击, 分析了全轮Grain-128 算法, 并对攻击进行了实验验证[15].然而, 在实际情况中, 由于超多项式未知, 排除错误密钥的效果并不好.在文献[15] 中, 对107 个正确密钥进行检测, 8 个正确密钥的超多项式观察到明显0/1 偏差, 对正确密钥攻击成功的概率约为7.5%.由此可见, 文献[15] 的动态立方攻击中超多项式的性质对于正确密钥和错误密钥的区分不大.因此, 动态立方攻击的研究中存在的突出问题是: 排除错误密钥的概率建立在随机假设之上, 随机假设与实际情况是否相符不清楚.

对于上述问题, Hao 等人在文献[16] 中指出一个成功的攻击不仅要评估正确密钥的非随机性, 还要评估错误密钥的随机性.基于这一想法, Hao 等人考虑如何分析一个超多项式pI(x) 的偏差.他们将整个空间分成弱密钥空间W和补集 ¯W.在弱密钥空间W中, 超多项式恒为0; 在补集 ¯W中, 假设超多项式0/1 平衡.那么, 对于超多项式pI(x), 给定一个弱密钥空间W, 则有

满足对所有x ∈WΛ, 都有pI(x)=0, 则称Λ 是一个分裂集.

分裂集Λ 定义了一类大小为2n−|Λ|的弱密钥空间, 并且在假设条件下超多项式在该弱密钥空间中的偏差为2−(|Λ|+1).在攻击中, 对于正确密钥条件, 超多项式等于0; 对于错误密钥条件, 通过MILP 模型构造最小分裂集, 根据分裂集大小给出超多项式偏差的一个理论估计.文献[16] 对全轮Grain-128 给出一个新的动态立方攻击, 并评估成功概率为99.83%.

7 相关立方攻击

2018 年, Liu 等人提出相关立方攻击[17], 其思想是利用超多项式和密钥表达式之间的相关性建立密钥方程, 主要应用到Trivium 算法.2023 年, Che 等人提出新的相关立方攻击模型[18], 提高了对Trivium算法的攻击效果.

7.1 数值映射

数值映射是文献[17] 中实现相关立方攻击的基本技术, 也是Trivium 型序列密码算法判断代数次数上界的重要方法.

数值映射最早由Liu 在2017 年美密会上提出[26].设

是一个m元布尔函数,D=(d0,d1,···,dm−1)∈Zm, 则函数h的数值映射DEG(h,D) 定义为

利用数值映射, 文献[26] 中进一步定义了合成函数的数值次数.设g0,g1,···,gm−1是m个n元布尔函数,h1=h(g0,g1,···,gm−1) 是一个合成函数, 则h1的数值次数定义为DEG(h1,deg(G)), 其中G=(g0,g1,···,gm−1) 且deg(G)=(deg(g0),deg(g1),···,deg(gm−1)).显然, 合成函数的代数次数总是小于等于其数值次数, 即deg(h1)≤DEG(h,deg(G)).进一步, 若已知deg(G)≤D=(d0,d1,···,dm−1),则也有deg(h1)≤DEG(h,D).利用这个不等式, 容易估计非线性迭代密码的代数次数.文献[26] 中对Trivium-型序列密码算法的代数次数进行了一系列评估.2021 年, 针对数值映射中变量可能被重复计数的问题, Ye 等人在文献[27] 中给出了一种改进的数值映射方法, 可以代替Liu 提出的数值映射, 得到更紧的代数次数上界.

7.2 利用基多项式分解的相关立方攻击

在数值映射基础上, Liu 等人于2018 年欧密会上提出相关立方攻击[17].该攻击利用数值映射给出超多项式的低次基多项式分解, 在基多项式中搜索与超多项式具有相关性的密钥表达式.一个布尔函数的基多项式分解定义如下.

定义8 给定一个布尔函数h, 称h=⊕ui=1hi·gi是h的一个分解, 并且G={g1,g2,···,gu}是h的一组基.

攻击分为两个阶段: 预处理阶段和在线阶段.预处理阶段, 对每个给定的立方集, 试图找到超多项式的一组基并计算基多项式与超多项式的条件相关概率.因为基于NFSR 的序列密码是非线性迭代型密码,所以文献[17] 中提出前N0轮状态比特中关于立方变元的最大次数项的系数, 很可能是一组基.在搜索基多项式时, 选定N0, 计算前N0轮更新状态中立方变元最大次数项的系数.将这些关于密钥变元的系数表达式设置为0 后(除常值以外), 利用数值映射判断第r轮超多项式是否为0.若超多项式等于0, 则这些系数表达式构成超多项式的一组基.设I是一个具有低次分解基G的立方变元集.对于g ∈G, 估计在固定密钥下的条件概率Pr(g= 0|pI(key,·)≡0) 和Pr(g= 1|pI(key,·)̸≡0).在线攻击阶段, 通过超多项式的具体值, 选择大于一定概率阈值的方程建立密钥方程组.对于835 轮Trivium, 文献[17] 平均可以恢复5 个密钥比特, 在线攻击复杂度244.文献[27] 利用改进的数值映射方法, 给出更多可用于对835 轮Trivium 进行相关立方攻击的立方集.

7.3 相关立方攻击的新框架

给定立方集, 文献[17] 的方法是先确定一组基多项式, 而后分析这些多项式和超多项式之间的条件相关性.然而, 基多项式是不唯一的, 可能一些具有较好相关性的低次多项式没有被选到, 导致攻击不成功.为了避免基的局限性以及更好地选择一组相关性高的多项式, Che 等人在文献[18] 中丢掉了基的概念, 提出了新的相关立方攻击框架, 从更一般更直接的角度刻画了在什么情形下密钥表达式f(x,v) 和超多项式pI(x) 会具有好的相关性.

在立方攻击中, 选定立方变元集I后, 超多项式pI也可以视为关于密钥和非立方变元的布尔函数.若超多项式pI形如λ(x)g(x,v), 则在固定密钥下, 可将pI看成关于IV 的黑盒多项式, 通过查询pI的值来猜测λ(x) 的值.具体地, 若对于某组IV 有pI= 1, 则λ(x) = 1, 从而得到以概率1 成立的密钥方程;若对于多组IV,pI始终等于0, 则λ(x) 以一定概率等于0.考虑到出现形如pI=λ(x)g(x,v) 的概率很小, 在文献[18] 中, 作者将pI=λ(x)g(x,v) 扩展为pI=λ(x)g(x,v)⊕h(x,v), 其中h是有明显偏差的函数.例如, 当h以很大概率为0 时,pI也可近似看成λ(x)g(x,v) 的形式, 仍可利用pI和λ(x) 之间的条件相关性来获取密钥信息.文献[18] 搜索密钥表达式的模型比文献[17] 更全面, 搜索更细致, 并且搜索到的密钥表达式完全包含了原模型中的密钥表达式.在攻击时, 作者将可分性引入相关立方攻击中, 借助MILP 建模技术对相关立方攻击中可利用的立方集进行搜索.对于844 轮Trivium, 平均能以245的计算复杂度恢复4 比特的密钥信息, 通过实验可以充分验证.这是迄今为止对844 轮Trivium 密钥恢复攻击的最好结果.

8 总结

本文对立方攻击的提出和发展进行了系统的梳理和总结.立方攻击是序列密码的一种重要攻击方法.立方攻击首次针对基于NFSR 序列密码算法给出了建立低次密钥方程的方法.搜索分组密码积分区分器的可分性和MILP 建模方法引入立方攻击后, 可用于攻击的立方集的维数大大提高, 使得立方攻击成为评估基于NFSR 序列密码算法安全性的重要工具.三子集不含未知子集的MILP 建模方法首次较好解决了基于可分性立方攻击中精确恢复超多项式的建模方法, 很大程度上增强了攻击者恢复超多项式的能力.动态立方攻击和相关立方攻击在已知超多项式局部信息时也可以攻击密钥, 攻击思想对于处理大规模超多项式有一定价值.

目前, 超多项式的恢复技术已比较成熟, 随着轮数的增长, 超多项式的规模太大是导致超多项式无法恢复的主要原因, 并且庞大的代数正规型对于密钥恢复意义也不大.一般地, 代数次数越低, 超多项式的规模越小.因此, 如何选取低次超多项式的立方集是有待解决的关键问题.同时, 超多项式的次数与立方集维数之间的代数关系也是一个有意义的理论问题.