1、第 21 卷第 4 期2022 年12 月广州大学学报(自然科学版)Journal of Guangzhou University(Natural Science Edition)Vol 21No 4Dec2022收稿日期:2022-10-08;修回日期:2022-10-15基金项目:国家自然科学基金资助项目(62122085，12231015);中国科学院青年创新促进会资助项目作者简介:侯铖安(1999)，男，硕士研究生 E-mail:houchengan iie ac cn*通信作者 E-mail:liumeicheng iie ac cn引文格式:侯铖安，刘美成 Elephant-Del
2、irium 算法安全性分析J 广州大学学报(自然科学版)，2022，21(4):46-52，86文章编号:1671-4229(2022)04-0046-07Elephant-Delirium 算法安全性分析侯铖安1，2，刘美成1，2(1 中国科学院信息工程研究所 信息安全国家重点实验室，北京100093;2 中国科学院大学 网络空间安全学院，北京100093)摘要:文章主要关注 Elephant-Delirium 算法的安全性分析。Elephant 算法是美国国家标准与技术研究所主导的轻量级密码算法标准最终轮候选算法之一。Elephant 加密算法的内部将密钥通过一个可逆变换扩展为秘密掩码，然
3、后对内部状态使用置换达到混淆和扩散的目的。Elephant-Delirium 是 Elephant 的加密算法实例，采用 Keccak-f 200 置换作为底层置换。文章利用 Keccak-f 200 置换中非线性操作的代数次数为 2 的性质，构造出 5 轮 Keccak-f 200 置换的零和区分器。在此区分器的基础上，文章使用分治法猜测 Elephant-Delirium 算法第 6 轮输出中的秘密掩码，并利用所构造的零和区分器筛选出正确的秘密掩码。在不重用随机数(nonce)的条件下，文章以 100%的准确率和100%的成功率实现了6 轮 Elephant-Delirium 的密钥恢复攻
4、击，在单核 CPU 上的实际运行时间约为 2.8 s。这是对 Elephant-Delirium 算法的第一个实际密钥恢复攻击。同时，文章利用立方攻击的思想扩展了优化插值攻击，从而将 8 轮 Elephant-Delirium 算法密钥恢复攻击的复杂度从 298 3降到了 295 2。关键词:Elephant 算法;立方攻击;优化插值攻击;密钥恢复中图分类号:TN 918.1文献标志码:AOn the security analysis of Elephant-Delirium algorithmHOU Cheng-an1，2，LIU Mei-cheng1，2(1 State Key Labo
5、ratory of Information Security，Institute of Information Engineering，Chinese Academy of Sciences，Beijing 100093，China;2 School of Cyber Security，University of Chinese Academy of Sciences，Beijing 100093，China)Abstract:This paper focuses on the security analysis of Elephant-Delirium algorithm Elephant
6、is oneof the candidate algorithms in the finalist of National Institute of Standards and Technology(NIST)lightweight cryptographic(LWC)project Its encryption algorithm extends the key to the secret masksthrough an invertible map，and then uses a permutation on the internal states to achieve confusion
7、 anddiffusion The Elephant-Delirium algorithm is an instance of Elephant encryption algorithm which usesKeccak-f 200as its underlying permutation This paper constructs a 5-round zero-sum distinguisherusing the property that the algebraic degree of nonlinear operation in Keccak-f 200permutation is 2B
8、ased on this distinguisher，we use the divide and conquer method to guess the secret mask in theoutput of 6-round Elephant-Delirium algorithm and filter out the right secret mask by checking the ze-ro-sum property As a result，the secret mask can be recovered with 100%accuracy and 100%suc-cess rate Th
9、is attack is under the nonce-respecting setting and costs about 2 8 seconds to recover allkey bits using a single CPU core This work is the first practical attack on the Elephant-Delirium algo-第 4 期侯铖安等:Elephant-Delirium 算法安全性分析rithm Also，we improve the result of optimized interpolation attack on 8-
10、round Elephant-Delirium algo-rithm with the help of the cube attack This improvement reduces the complexity from 2983to 2952Key words:Elephant algorithm;cube attack;optimized interpolation attack;key recovery现代密码学发展至今，已经衍生出对称密码学和非对称密码学(公钥密码学)两大方向。它们的主要区别是在对称密码算法中，发送者和接收者共享同一个秘密密钥;而在非对称密码中，双方需要分别使用不同
11、而又紧密相关的 2 个密钥。对称密码算法在效率方面具有显著的优势，而非对称密码算法则可以提供丰富的安全功能。只有将对称密码算法与非对称算法结合起来，才能满足人们对安全和效率的需求。传输层安全(Transport Layer Security，TLS)协议综合应用了对称密码和非对称密码算法，常用于安全超文本传输协议(Hyper Text Transfer Proto-col Secure，HTTPS)，在计算机网络通信安全中起着至关重要的作用。然而，TLS 协议中使用的密码算法在设计和实现上存在漏洞，近年来有许多对TLS 协议的攻击被提出1 2。这些攻击表明现有的密码算法还远远不能满足人们的安全
12、需求。同时也带给密码算法设计者一个重要的设计原则，就是在密码算法中必须同时考虑数据的机密性和完整性，也就是认证加密(Authenticated Encryp-tion，AE)。目前，密码学界已经在研究和标准化认证加密算法方面做出了许多努力。例如，经过CAESA 竞赛，ASCON 算法在安全和效率方面展现出了强大的实力3。在医疗、分布式控制系统、物联网等新兴领域，常常需要将一些资源非常有限的设备进行连接，并协同工作。但目前广泛应用的密码算法大都是为个人电脑或服务器环境而设计，因此，不适用于资源受限的设备。在这样的背景下，轻量级密码算法应运而生。美国标准与技术研究所(Na-tional Insti
13、tute of Standards and Technology，NIST)也开始公开征集、评估和标准化轻量级密码算法(Lightweight Cryptography，LWC)，以 用 于 其 他NIST 密码标准无法工作的资源受限场景。2021年 3 月，经过 3 轮筛选，NIST 公布了包括 ASCON和 Elephant 在内的 10 个算法进入最终的候选列表，并将在接下来一段时间中对这 10 个算法进行更全面而深入地评估。Elephant 算法是由 Beyne 等提交到 NIST 的LWC 竞赛的轻量级认证加密算法4，并于 2020年发表在 IAC Transactions on S
14、ymmetric Cryptolo-gy(ToSC)。Elephant 算法具有状态小、并行度高等特性，其底层使用了较为成熟的 Spongent 结构和Keccak-f 200置换，这些优点使得 Elephant 从LWC 竞赛的候选算法中脱颖而出，进入到最终列表的评估。因此，分析 Elephant 算法的安全性具有十分重要的理论价值和现实意义。目前，除了设计者在理想置换模型下的安全分析之外，Zhou等5 使用优化插值攻击以 298 3的复杂度实现了对8 轮 Elephant-Delirium 实例的密钥恢复攻击，该结果于 2021 年4 月正式发表在 The Computer Journal
15、上，也是目前为止唯一的第三方分析。本文利用立方攻击的思想改进了这一攻击结果，将时间复杂度降到 295 2。除了理论分析，本文还首次实现了对 6 轮 Elephant-Delirium 实例的实际密钥恢复攻击。1预备知识1 1布尔函数与莫比乌斯变换布尔函数即从二元域F2上的 n 维向量空间Fn2映射到F2的函数。布尔函数既可以用它的真值表表示，也可以用它的代数标准型(Algebraic Nor-mal Form，ANF)表示。令 f:Fn2F2是一个 n 元布尔函数，则其 ANF 是F x0，xn 1/(x20 x0，x2n 1xn 1)中的多项式，即f(x)=uFn2auxu(1)其中，x=(
16、x0，xn1)，u=(u0，un1)，auF2，xu=n1i=0 xuii。使用莫比乌斯变换可以将一个布尔函数 f 从它的真值表形式转换为 ANF，也可以反过来从ANF 转换为真值表。对于一个 n 元布尔函数，莫比乌斯变换需要 n2n 1次异或运算。1 2高阶差分攻击与立方攻击高阶差分攻击是差分攻击的推广，其理论基74广州大学学报(自然科学版)第 21 卷础是布尔函数的高阶导数6。令 F:Fn2Fm2为一个向量布尔函数。对vFn2，F 关于 v 的导数定义为 DvF(x)=F(xv)F(x)。进一步地，对Fn2中的任意 k 维子空间 V 和 V 的任意一组基 v0，vk 1，F 关于 V 的 k 阶导数定义为DVF(x)=Dv0Dv1Dvk 1F(x)=uVF(xu)。对布尔函数的每一次求导都会降低导数的代数次数6。因此，对于任何维数大于该函数的代数次数的子空间，其对应的导数为DVF(x)=uVF(xu)=0(2)对xFn2都成立。对于一个特定轮数的密码算法，如果能够找到某个输入子空间，使得这个子空间的维数超过输出函数的代数次数，那么对这个输入子空间对应的输出子空间进行求和将恒等于 0