侯铖安,刘美成
(1. 中国科学院信息工程研究所 信息安全国家重点实验室,北京 100093;2. 中国科学院大学 网络空间安全学院,北京 100093)
现代密码学发展至今，已经衍生出对称密码学和非对称密码学(公钥密码学)两大方向。它们的主要区别是在对称密码算法中，发送者和接收者共享同一个秘密密钥；
而在非对称密码中，双方需要分别使用不同而又紧密相关的2个密钥。对称密码算法在效率方面具有显著的优势，而非对称密码算法则可以提供丰富的安全功能。只有将对称密码算法与非对称算法结合起来，才能满足人们对安全和效率的需求。
传输层安全(Transport Layer Security，TLS)协议综合应用了对称密码和非对称密码算法，常用于安全超文本传输协议(Hyper Text Transfer Protocol Secure，HTTPS)，在计算机网络通信安全中起着至关重要的作用。然而，TLS协议中使用的密码算法在设计和实现上存在漏洞，近年来有许多对TLS协议的攻击被提出[1-2]。这些攻击表明现有的密码算法还远远不能满足人们的安全需求。同时也带给密码算法设计者一个重要的设计原则，就是在密码算法中必须同时考虑数据的机密性和完整性，也就是认证加密(Authenticated Encryption，AE)。目前，密码学界已经在研究和标准化认证加密算法方面做出了许多努力。例如，经过 CAESAR竞赛，ASCON算法在安全和效率方面展现出了强大的实力[3]。
在医疗、分布式控制系统、物联网等新兴领域，常常需要将一些资源非常有限的设备进行连接，并协同工作。但目前广泛应用的密码算法大都是为个人电脑或服务器环境而设计，因此，不适用于资源受限的设备。在这样的背景下，轻量级密码算法应运而生。美国标准与技术研究所(National Institute of Standards and Technology，NIST)也开始公开征集、评估和标准化轻量级密码算法(Lightweight Cryptography，LWC)，以用于其他NIST 密码标准无法工作的资源受限场景。2021年3月，经过3轮筛选，NIST公布了包括 ASCON和Elephant 在内的10个算法进入最终的候选列表，并将在接下来一段时间中对这10个算法进行更全面而深入地评估。
Elephant算法是由Beyne等提交到 NIST 的 LWC 竞赛的轻量级认证加密算法[4]，并于 2020年发表在IACRTransactionsonSymmetricCryptology(ToSC)。Elephant 算法具有状态小、并行度高等特性，其底层使用了较为成熟的 Spongent结构和Keccak-f[200]置换，这些优点使得Elephant从LWC竞赛的候选算法中脱颖而出，进入到最终列表的评估。因此，分析Elephant算法的安全性具有十分重要的理论价值和现实意义。目前，除了设计者在理想置换模型下的安全分析之外，Zhou等[5]使用优化插值攻击以298.3的复杂度实现了对8轮 Elephant-Delirium实例的密钥恢复攻击，该结果于2021年4月正式发表在TheComputerJournal上，也是目前为止唯一的第三方分析。本文利用立方攻击的思想改进了这一攻击结果，将时间复杂度降到295.2。除了理论分析，本文还首次实现了对6轮Elephant-Delirium 实例的实际密钥恢复攻击。
1.1 布尔函数与莫比乌斯变换
(1)
使用莫比乌斯变换可以将一个布尔函数f从它的真值表形式转换为ANF，也可以反过来从ANF转换为真值表。对于一个n元布尔函数，莫比乌斯变换需要n2n-1次异或运算。
1.2 高阶差分攻击与立方攻击
对布尔函数的每一次求导都会降低导数的代数次数[6]。因此，对于任何维数大于该函数的代数次数的子空间，其对应的导数为
(2)
对于一个特定轮数的密码算法，如果能够找到某个输入子空间，使得这个子空间的维数超过输出函数的代数次数，那么对这个输入子空间对应的输出子空间进行求和将恒等于0，也就是得到了一个零和区分器，然后可以利用这个零和区分器来实现密钥恢复攻击。不难看出，输出函数的代数次数对高阶差分攻击至关重要。但一般而言，需要很高的复杂度才能得到输出函数的准确次数。因此，在实际中人们常常只是估计输出函数代数次数的上界。对于一个轮函数的代数次数为d的密码算法，由于第二轮输入的代数次数为d，第二轮的输出函数关于第二轮输入的代数次数也为d，因此，第二轮输出函数关于第一轮输入的代数次数不超过d2，由归纳法可知，经过r轮迭代后的输出函数的代数次数不会超过dr。例如，Keccak-f[200]的代数次数为2，那么经过4轮后输出函数的代数次数不会超过16。因此，根据高阶差分性质，任意超过16维的子空间都对应一个4轮的零和区分器。
立方攻击是高阶差分攻击的一种变体，由Dinur等[7]在2009年的欧密会上提出。立方攻击作为一种用来分析对称密码算法的通用方法，已经成功用于攻击许多密码体制。立方攻击将输出比特的ANF看作是关于n个秘密变量x=(x1,x2,…,xn)和m个公开变量v=(v1,v2,…,vm)的多项式，记为f(x,v)。对于任何一个集合I={i1,i2,…,i|I|}⊂{1,…,m}，f(x,v)可以写作
f(x,v)=tIp(x,v)⨁q(x,v)，
其中，tI=vi1vi2…vi|I|称为极大项，极大项中的变量vi1,vi2,…,vi|I|称为立方变量。p(x,v)不含有立方变量，称为tI对应的超级多项式，且q(x,v)至少比tI少一个变量。
(3)
恰当地选择立方变量将使得超级多项式在变量和次数方面都比原多项式简单得多，因此，更有利于分析函数的性质。
1.3 优化插值攻击
优化插值攻击[8]是对插值攻击[9]的改进，利用莫比乌斯变换降低了攻击的复杂度。
插值攻击考虑一个目标比特a，其ANF可以用密文C和密钥K表示，即
Elephant算法是由Beyne等[4]提交到 NIST 的 LWC 竞赛的轻量级认证加密算法，是LWC竞赛最终列表中的10个算法之一。Elephant算法的结构是基于nonce的先加密后认证的构造，根据底层所用置换的不同，Elephant算法共有Dumbo、Jumbo和Delirium 3个实例，分别使用的是Spongent-π[160]、Spongent-π[176]和Keccak-f[200]置换。每一个实例都使用一个置换和一个线性反馈移位寄存器来将密钥扩展为掩码。这个过程是可逆的，如果可以恢复出秘密掩码，那么就可以直接逆推得到密钥。本文关注的是使用Keccak-f[200]置换的Delirium实例，此后所说的Elephant算法都特指Delirium实例。
Elephant算法的内部状态有200比特，初始时用96比特随机数和104比特的0进行填充。然后，将密钥扩展后的200比特掩码异或到初始状态上。经过18轮Keccak-f[200]置换后，再将掩码异或到所有状态上，得到输出状态。对于一个200比特的明文分组，异或输出状态后得到相应的密文。本文只使用一个明文分组进行选择明文攻击，所以略去了Elephant算法关于分组的处理和认证阶段。
Keccak-f[200]置换有200比特内部状态，总共18轮。这200比特的状态X∈{0,1}200被表示为一个5×5×8的数组a∈{0,1}5×5×8。对于数组a中下标为(x,y,z)∈5×5×8的元素ax,y,z，对应的是X的第8·(5y+x)+z比特，即ax,y,z=X[8·(5y+x)+z]。Keccak-f[200]的每一轮置换都对所有200比特状态依次进行5个操作θ,ρ,π,,ι，其中，是唯一的非线性操作，它们的定义如下：
ρ:ax,y,z←ax,y,z+tx,y，
π:ax,y,z←ax+3y,x,z，
ι:ax,y,z←ax,y,z+RCi,x,y,z，
注意到Keccak-f[200]中的非线性操作的代数次数只有2次，这一性质被许多攻击所利用。
由于Elephant算法的非线性操作可以看作40个并行的5比特S盒，输出时异或的秘密掩码可以看作是轮密钥，因此，本文采用了分组密码分析中常见的区分器-解密的攻击方式进行密钥恢复攻击。具体来说，如果有一个r轮的区分器，那么首先猜测轮密钥，然后将r+1轮的输出进行解密。如果猜测的轮密钥恰好是正确的轮密钥，那么解密出来的结果恰好是r轮的输出，因此，满足区分器的性质。另外，如果猜测的轮密钥是错误的，则解密出来的结果近似于均匀分布，因此，不能观察到区分器的性质。由于40个S盒是相互独立的，因此，可以利用分治法来恢复每个S盒对应的轮密钥，也就是Elephant算法中的秘密掩码。
3.1 5轮零和区分器的构造
基于Keccak-f[200]置换的代数次数为2的特点，本文利用高阶差分性质来构造零和区分器。Elephant算法加密时的初始状态是用96比特的随机数(nonce)和104比特的0进行填充的，然后该初始状态异或200比特的秘密掩码。其中，nonce是可以控制的，即可以选择的子空间的最大维数是96维。根据高阶差分性质，任何65维的子空间都可以构造一个6轮的零和区分器，因为65>26。由于这个零和区分器的复杂度远远超过了人们的计算能力，所以只能降低攻击的轮数。一个直接的想法就是用33维的子空间构造5轮的零和区分器，或者用17维的子空间构造4轮的零和区分器。事实上，可以利用CP-kernel性质(CP-kernel性质是Keccak的设计者提出的θ操作的一个性质),将使用17维子空间的4轮零和区分器推进到5轮。
要将4 轮的零和区分器推进1轮，则17 维的子空间必须满足一定的条件。可以从代数次数的角度来看这个问题：之所以可以用17维的子空间得到4轮的零和区分器，是因为4轮输出函数的代数次数至多为16，而17维的子空间对应的极大项是一个17次项，因此，其系数必然为0。如果选择17维子空间对应的立方变量，在经过1轮置换后没有乘出二次项，则再经过4轮置换，其输出函数中不可能出现17 个变量的乘积项，所以子空间的求和仍然是 0。从另一个角度说，在遍历 17 维输入子空间的时候，恰好遍历了1 轮置换的某个17 维输出子空间。而这个1 轮置换的17维输出子空间，又可以看作是4 轮零和区分器的输入子空间，也就必然满足零和的性质。综上所述，本研究的问题转化为寻找满足条件的 17 维子空间。
这个问题可以使用混合整数线性规划模型进行建模。首先，用(x0,…,x95),xi∈2来表示可以控制的96比特随机数(nonce)。当xi=1时，表示将其选为立方变量，否则表示不选为立方变量。其次，本研究的目标是最大化子空间的维数，也就是最大化立方变量的个数，即约束条件是经过1轮置换后，立方变量之间不会相互乘出二次项，这需要借助1轮 Keccak-f[200]的ANF来给出。将所有的随机数比特都用一个布尔变量来表示，其他比特赋值为0。然后，使用 SageMath 软件进行符号计算，得到1轮Keccak-f[200]关于nonce的 ANF。所得的 ANF 中包含一些二次项，每一个二次项，不妨设为xixj，给出一个约束条件xi+xj≤1，即这2个变量不能同时选为立方变量。最后，使用 Gurobi 软件求解这个 MILP 模型，即可得到满足条件的子空间的最大维数，给出所选的立方变量。
在选择立方变量时，必须考虑Keccak-f[200]的CP-kernel性质，因为不考虑CP-kernel性质时，以上模型给出的子空间的最大维数只有8维，不能满足5轮零和区分器所要求的17维子空间。观察θ操作的表达式不难发现，如果将ax,y,z和ax,y′,z,y′≠y同时选为相等的立方变量。则在它们的和中，立方变量将被消掉。这一性质是异或的直接结果，称为CP-kernel性质。θ操作的目的是提供扩散，而CP-kernel性质阻止了扩散。因为ρ和π操作都只是比特位置的移动而不存在扩散，所以CP-kernel性质使得Keccak-f[200]的θ，ρ，π操作退化为比特置换。这样一来，就有可能找到更大维数的子空间。实验的结果也验证了这一点，在考虑了CP-kernel性质后，子空间的最大维数达到28维，因此，可以从中选取17维的子空间来构造零和区分器。
3.2 攻击过程
本研究的攻击是一个选择明文攻击，只使用一个明文块。不妨固定M=0200，则加密得到的密文C=P(N‖0104⨁maskK)⨁maskK。其中，P是约简轮数的Keccak-f[200]置换，maskK=P(K‖072)是由密钥导出的秘密掩码。
因为θ,ρ,π操作都是线性操作，不会破坏零和的性质，所以5轮的零和区分器可以直接推进到第6轮的操作之前。那么，距离6轮的输出，还有,ι和异或秘密掩码3个操作。其中，ι操作只是异或了第6轮的轮常数，可以等效到异或秘密掩码的操作中。因此，需要考虑和异或等效掩码2个操作。
(4)
反之，如果猜测错误，则得到的结果近似于均匀分布，那么5个比特同时满足零和的概率近似于2-5。在实验中发现，对于每一个S盒，除了正确的掩码，还可能有至多3个错误的掩码也满足零和的性质。为了降低错误的概率，使用3个17维的子空间。假设错误的结果为均匀分布，则错误的掩码同时在3个子空间都满足零和的概率为2-15。实验结果表明，使用3个不同的零和区分器，只有正确的掩码才能同时满足零和的性质。
对所有40个S盒都进行以上过程，就可以恢复出200比特的掩码，进而恢复出密钥。
整个攻击的过程如算法1所示。
算法1：对6轮Elephant算法的密钥恢复攻击
输入:MILP模型给出的任意18个立方变量I={x0,…,x17}
输出：200比特秘密掩码maskK
遍历18个立方变量的取值，任意给定nonce其他比特的取值，构建集合NI
对NI中的每一个nonce，设置明文M=0200，访问加密函数得到对应的密文，并异或轮常数，得到集合CI
fors←0 to 39 do
fori←0 to 25do
ifsum0⨁sum1=0 andsum0⨁sum2=0 andsum2⨁sum3=0 then
end if
end for
end for
3.3 攻击复杂度分析
总共需要对3个17维子空间，这可以从18维子空间中选取。而且，这3个17维子空间可以共享同一个16维子空间，这样一来，3个子空间的并集大小为218，而不是3×217。我们需要218的数据复杂度，同时存储这些数据需要218的空间复杂度。
然后，对40个S盒分别进行猜测，每个S盒的输出有5比特，共25种可能性。对于每一种可能的取值，需要在218的数据上进行求和，然后根据是否满足零和性质来筛选出正确的掩码。因此，攻击的时间复杂度为40×25×218≈229。
3.4 攻击的实现
为了验证以上理论，使用C++编程实现了攻击。随机生成了超过100个密钥，然后调用Elephant的参考代码进行加密，最终以100%的成功率恢复出所有的秘密掩码。实验在装有Ubuntu Server 21.04操作系统的台式机上运行，使用单核CPU(AMD Ryzen7-3700X，3.6 GHz)。本文所实现的串行版本，计算1个17维的子空间对应的密文空间，需要大约1.2 s。在准备好所需的nonce-密文对后，平均一次密钥恢复攻击需要大约2.8 s时间。同时，使用并行计算还可以进一步减少运行时间，既可以对40个S盒并行执行，也可以在每次判断零和时并行执行。
4.1 攻击过程
本文同样考虑第6轮的输出比特。一方面，可以逆向计算2轮Keccak-f[200]得到关于第8轮输出的密文表达式;另一方面，可以计算立方和得到关于输入明文的超级多项式。本文的改进主要针对6轮的零和区分器。通过立方攻击放宽了零和的限制，从而可以使用更小维数的子空间。一个子空间的超级多项式可以给出一个方程：
其中，GK(VP)是VP对应的超级多项式，VC是VP加密后得到的密文空间。
此时，等式左右两边都是非线性的多项式，因此，都必须进行线性化。对于等式的左边，使用与Zhou等[5]相同的方法来进行线性化，即需要引入223.1个新变量来线性化。因此，只需要考虑等式右边的超级多项式的线性化。
在线阶段，攻击的步骤与Zhou等[5]类似。首先，对67维子空间的所有nonce和固定的明文M=0200加密得到对应的密文,用这些密文计算出Mu，得到一个比特向量；
然后对这个比特向量做莫比乌斯变换，从所得的结果中去除子空间对应的系数，即是一个等效密钥的系数。在遍历了223.11个子空间后，即可求解方程组得到所有等效密钥的值，进而恢复出密钥比特。
4.2 攻击复杂度分析
与Zhou等[5]的攻击相比，本研究的攻击使用了维数更小的子空间和更多的变量。在离线阶段，需要恢复223.11个超级多项式，每个超级多项式需要求解213.3个变量的线性方程组。在线阶段时，需要遍历67维子空间，并存储所得的密文。因此，数据复杂度和空间复杂度都是267。计算一次莫比乌斯变换需要266×log267次异或操作，总共需计算223.11次莫比乌斯变换。因此，总的攻击复杂度约为223.11×266×log267≈295.2。
本文对 Elephant-Delirium 算法的安全性进行分析，提出了6轮的实际密钥恢复攻击并改进了8轮的密钥恢复攻击。
对于6轮的实际密钥恢复攻击，采用了区分器-解密的攻击方式。首先，利用底层的Keccak-f[200]置换代数次数为2的特点，使用17维子空间构造出4轮零和区分器；
然后,利用MILP模型并借助 Keccak-f[200]置换中θ操作的CP-kernel性质阻止立方变量的扩散，使得子空间对应的 17个立方变量在经过1轮Keccak-f[200]置换后仍然是1次，从而得到5轮零和区分器。利用构造出的5轮零和区分器对猜测的秘密掩码的正确性进行区分，最终恢复出所有的秘密掩码。
另外，利用立方攻击的思想改进了 8 轮密钥恢复攻击的结果。在优化插值攻击中使用超级多项式来建立方程，扩展了现有的使用零和区分器的方法。将攻击的时间复杂度从298.3降低到295.2，空间复杂度和数据复杂度也都有降低。值得注意的是，本研究的方法依然可能存在改进空间。例如本文对超级多项式的项数上界只是粗略的估计，如果可以更加精确地估计这个上界，攻击的复杂度也会随之降低。
猜你喜欢掩码区分代数基于RISC-V的防御侧信道攻击AES软件实现方案微处理机(2021年5期)2021-11-02两个有趣的无穷长代数不等式链河北理科教学研究(2021年4期)2021-04-19Hopf代数的二重Ore扩张数学年刊A辑(中文版)(2021年4期)2021-02-12什么是代数几何科学(2020年1期)2020-08-24低面积复杂度AES低熵掩码方案的研究通信学报(2019年5期)2019-06-11怎么区分天空中的“彩虹”奥秘(创新大赛)(2019年3期)2019-03-13基于布尔异或掩码转算术加法掩码的安全设计*通信技术(2018年3期)2018-03-21教你区分功和功率中学生数理化·八年级物理人教版(2017年6期)2017-11-09怎祥区分天空中的“彩虹”(一)百科探秘·航空航天(2016年5期)2016-11-07一个非平凡的Calabi-Yau DG代数应用数学与计算数学学报(2015年1期)2015-07-20
