Elephant-Delirium算法安全性分析  

On the security analysis of Elephant-Delirium algorithm

作　　者：侯铖安 刘美成 HOU Cheng-an;LIU Mei-cheng(State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100093,China)

机构地区：[1]中国科学院信息工程研究所信息安全国家重点实验室,北京100093 [2]中国科学院大学网络空间安全学院,北京100093

出　　处：《广州大学学报（自然科学版）》2022年第4期46-52,86,共8页Journal of Guangzhou University:Natural Science Edition

基　　金：国家自然科学基金资助项目(62122085,12231015);中国科学院青年创新促进会资助项目。

摘　　要：文章主要关注Elephant-Delirium算法的安全性分析。Elephant算法是美国国家标准与技术研究所主导的轻量级密码算法标准最终轮候选算法之一。Elephant加密算法的内部将密钥通过一个可逆变换扩展为秘密掩码,然后对内部状态使用置换达到混淆和扩散的目的。Elephant-Delirium是Elephant的加密算法实例,采用Keccak-f[200]置换作为底层置换。文章利用Keccak-f[200]置换中非线性操作的代数次数为2的性质,构造出5轮Keccak-f[200]置换的零和区分器。在此区分器的基础上,文章使用分治法猜测Elephant-Delirium算法第6轮输出中的秘密掩码,并利用所构造的零和区分器筛选出正确的秘密掩码。在不重用随机数(nonce)的条件下,文章以100%的准确率和100%的成功率实现了6轮Elephant-Delirium的密钥恢复攻击,在单核CPU上的实际运行时间约为2.8 s。这是对Elephant-Delirium算法的第一个实际密钥恢复攻击。同时,文章利用立方攻击的思想扩展了优化插值攻击,从而将8轮Elephant-Delirium算法密钥恢复攻击的复杂度从2^(98.3)降到了2^(95.2)。This paper focuses on the security analysis of Elephant-Delirium algorithm. Elephant is one of 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 masks through an invertible map, and then uses a permutation on the internal states to achieve confusion and diffusion. The Elephant-Delirium algorithm is an instance of Elephant encryption algorithm which uses Keccak-f[200] as its underlying permutation. This paper constructs a 5-round zero-sum distinguisher using the property that the algebraic degree of nonlinear operation in Keccak-f[200] permutation is 2. Based on this distinguisher, we use the divide and conquer method to guess the secret mask in the output of 6-round Elephant-Delirium algorithm and filter out the right secret mask by checking the zero-sum property. As a result, the secret mask can be recovered with 100% accuracy and 100% success rate. This attack is under the nonce-respecting setting and costs about 2.8 seconds to recover all key bits using a single CPU core. This work is the first practical attack on the Elephant-Delirium algorithm. Also, we improve the result of optimized interpolation attack on 8-round Elephant-Delirium algorithm with the help of the cube attack. This improvement reduces the complexity from 2^(98.3)to 2^(95.2).

关 键 词：Elephant算法 立方攻击 优化插值攻击 密钥恢复 

分 类 号：TN918.1[电子电信—通信与信息系统]