对减轮Enhanced-Bivium流密码的立方攻击

doi:10.19665/j.issn1001-2400.20240401

摘要/Abstract

摘要：

Trivium流密码是最终胜选欧洲eSTREAM项目的轻量级同步流密码之一,而Enhanced-Bivium流密码是适用于RIFD系统的Trivium流密码的简化版本,该密码设计者认为在相同的初始化轮数下Enhanced-Bivium流密码算法的安全性要高于Trivium流密码算法。通过在离线预处理阶段引入代数次数评估方法和在在线计算阶段引入基于嵌套式单项式预测的立方攻击提出了一种新的立方攻击方法。使用该方法可以将初始化464轮的Enhanced-Bivium流密码的立方攻击所需时间复杂度由2⁵⁵降到2^50.3,同时利用该方法可以在时间复杂度2^77.8下将对Enhanced-Bivium流密码攻击成功的初始化轮数由464轮提升到601轮。另外,利用该方法在相同的时间复杂度下,将对Trivium流密码成功攻击的轮数由799轮提升至840轮,进而证明了Enhanced-Bivium流密码比Trivium流密码对立方攻击有更好的抵抗性。

关键词: Enhanced-Bivium, 立方攻击, 密码学, 代数次数评估, 单项式预测, 整数规划

Abstract:

The Trivium Stream cipher is one of the lightweight synchronous stream ciphers that won the eSTREAM project in Europe,which is a simplified version of the Trivium stream cipher for RIFD systems.The designers believe that the Enhanced-Bivium stream cipher algorithm is more secure than the Trivium stream cipher algorithm with the same number of initialization rounds.This article proposes a new cube attack method by introducing an algebraic degree evaluation method in the offline preprocessing stage and a cube attack based on monomial prediction in the online computing stage.With the new method,we can reduce the time complexity of the cube attack on the Enhanced-Bivium stream cipher with 464 initial rounds from 2⁵⁵ to 2^50.3.At the same time,the number of initialization rounds of successful key recovery attack can be increased from 464 to 601 with the improved cube attack method,and the time complexity is 2^77.8.Also with the same time complexity,the initial rounds number of successful cube attacks on Trivium stream ciphers can be increased from 799 to 840,which proves that Enhanced-Bivium stream ciphers have better resistance to cube attack than the Trivium stream cipher.

Key words: Enhanced-Bivium, cube attack, cryptography, degree evaluation, monomial prediction, integer programming

中图分类号:

TN918.24

杨泽琳, 董丽华, 曾勇. 对减轮Enhanced-Bivium流密码的立方攻击[J]. 西安电子科技大学学报, 2024, 51(5): 179-188.

YANG Zelin, DONG Lihua, ZENG Yong. Cube attack on round-reduced Enhanced-Bivium[J]. Journal of Xidian University, 2024, 51(5): 179-188.

图/表 2

参考文献 28

[1]	DINUR I, SHAMIR A. Cube Attacks on Tweakable Black Box Polynomials[C]// Advances in Cryptology-EUROCRYPT 2009(EUROCRYPT 2009):vol 5479.Berlin,Heidelberg:Springer, 2009:278-299.
[2]	DINUR I, SHAMIR A. Breaking Grain-128 with Dynamic Cube Attacks[C]// Fast Software Encryption(FSE 2011):vol 6733.Berlin,Heidelberg:Springer, 2011:167-187.
[3]	DINUR I, GÜNEYSU T, PAAR C, et al. An Experimentally Verified Attack on Full Grain-128 Using Dedicated Reconfigurable Hardware[C]// Advances in Cryptology-ASIACRYPT 2011(ASIACRYPT 2011):vol 7073.Berlin,Heidelberg:Springer, 2011:327-343.
[4]	TODO Y, ISOBE T, HAO Y, et al. Cube Attacks on Non-Blackbox Polynomials Based on Division Property[C]// Advances in Cryptology-CRYPTO 2017(CRYPTO 2017):vol 10403.Cham:Springer, 2017:250-279.
[5]	MORAWIECKI P, PIEPRZYK J, STRAUS M, et al. Applications of Key Recovery Cube-Attack-Like(2015)[R/OL]. [2024-06-12] https://eprint.iacr.org/2015/1009.pdf.
[6]	DONG X, LI Z, WANG X, et al. Cube-like Attack on Round-Reduced Initialization of Ketje Sr(2017)[R/OL]. [2024-06-12] https://eprint.iacr.org/2017/159.pdf.
[7]	LI Z, DONG X, WANG X. Conditional Cube Attack on Round-Reduced ASCON(2017)[R/OL]. [2024-06-12] https://eprint.iacr.org/2017/160.pdf
[8]	李璐. 具有固定格式的Keyak算法的条件立方攻击[D]. 济南: 山东大学, 2019.
[9]	KARTHIKA S K, SINGH K. Cryptanalysis of Stream Cipher LIZARD Using Division Property and MILP Based Cube Attack[J]. Discrete Applied Mathematics, 2023, 325:63-78.
[10]	穆道光, 李枫, 张文政. 改进的基于可分属性的立方攻击[J]. 通信技术, 2020, 53(06):1473-1480.
	MU Daoguang, LI Feng, ZHANG Wenzheng. Modified Cube Attack based on Separable Attribute[J]. Communications Technology, 2020, 53(06):1473-1480.
[11]	WANG Q, HAO Y, TODO Y, et al. Improved Division Property Based Cube Attacks Exploiting Algebraic Properties ofSuperpoly[C]// Advances in Cryptology-CRYPTO 2018(CRYPTO 2018):vol 10991.Cham:Springer, 2018:275-305.
[12]	HU K, SUN S, WANG M, et al. An Algebraic Formulation of the Division Property:Revisiting Degree Evaluations,Cube Attacks,and Key-Independent Sums[C]// Advances in Cryptology-ASIACRYPT 2020(ASIACRYPT 2020):vol 12491.Cham:Springer, 2020:446-476.
[13]	HAO Y, LEANDER G, MEIER W, et al. Modeling for Three-Subset Division Property Without Unknown Subset Improved Cube Attacks Against Trivium and Grain-128AEAD[C]// Advances in Cryptology-EUROCRYPT 2020(EUROCRYPT 2020):vol 12105.Cham:Springer, 2020:466-495.
[14]	穆道光, 胡建勇, 苗旭东. Trivium 算法的立方攻击[J]. 信息安全与通信保密, 2022(5):2-9.
	MU Daoguang, HU Jianyong, MIAO Xudong. Cube Attacks on Trivium Cipher[J]. Information Security and Communications Privacy, 2022(5):2-9.
[15]	DELAUNE S, DERBEZ P, GONTIER A, et al. A Simpler Model for Recovering Superpoly on Trivium[C]// Selected Areas in Cryptography(SAC 2021):vol 13203.Cham:Springer, 2021:266-285.
[16]	LIU C, TIAN T, QI W F. A New Method for Searching Cubes and Its Application to 815-Round Trivium[J]. Journal of Systems Science & Complexity, 2023, 36(5):2234-2254.
[17]	DECANNIÈRE C. TRIVIUM:A Stream Cipher Construction Inspired by Block Cipher Design Principles.Information Security(ISC 2006):vol 4176.Berlin,Heidelberg:Springer,2006:171-186.
[18]	KNELLWOLF S, MEIER W, NAYA-PLASENCIA M. Conditional Differential Cryptanalysis of Trivium and KATAN[C]// Selected Areas in Cryptography(SAC 2011):vol 7118.Berlin,Heidelberg:Springer, 2012:200-212.
[19]	LI B, ZHANG H, LIN D. Higher-Order Masking Scheme for Trivium Hardware Implementation[C]// Information Security and Cryptology(Inscrypt 2022):vol 13837.Cham:Springer, 2023:337-356.
[20]	ZHANG S Y, CHEN G L, ZHOU Y K, et al. Enhanced-Bivium Algorithm for RFID System[J]. Mathematical Problems in Engineering, 2015, 2015(1):1-6.
[21]	BORGHOFF J, KNUDSEN L R, STOLPE M. Bivium as a Mixed-Integer Linear Programming Problem[C]// Cryptography and Coding(IMACC 2009):vol 5921.Berlin,Heidelberg:Springer, 2009:133-152.
[22]	MAXIMOV A, BIRYUKOV A. Two Trivial Attacks on Trivium[C]// Selected Areas in Cryptography(SAC 2007):vol 4876.Berlin,Heidelberg:Springer, 2007:36-55.
[23]	YE C D, TIAN T. A New Framework for Finding Nonlinear Superpolies in Cube Attacks Against Trivium-Like Ciphers[C]// Information Security and Privacy(ACISP 2018):vol 10946.Cham:Springer, 2018:172-187.
[24]	YE C D, TIAN T, ZENG F Y. The MILP-aided Conditional Differential Attack and Its Application to Trivium[J]. Designs,Codes and Cryptography, 2020(89):317-339.
[25]	HU K, SUN S, TODO Y, et al. MassiveSuperpoly Recovery with Nested Monomial Predictions[C]// Advances in Cryptology-ASIACRYPT 2021(ASIACRYPT 2021),vol 13090.Cham:Springer, 2021:392-421
[26]	ZHANG S Y, CHEN G L, LI J H. Cube Attack on Reduced-round Enhanced-Bivium[C]//2016 International Conference on Security of Smart Cities,Industrial Control System and Communications(SSIC). Piscataway:IEEE, 2016:1-4.
[27]	何煜. 对轻量级密码算法MORUS、Enhanced-Bivium和Quartet的立方攻击[D]. 上海: 华东师范大学, 2022.
[28]	TODO Y. Structural Evaluation by Generalized Integral Property[C]// Advances in Cryptology-EUROCRYPT 2015(EUROCRYPT 2015),vol 9056.Berlin,Heidelberg:Springer, 2015:287-314.