Trivium流密码的基于自动推导的差分分析

doi:10.3969/j.issn.0372-2112.2014.08.030

电子学报 ›› 2014, Vol. 42 ›› Issue (8): 1647-1652.DOI: 10.3969/j.issn.0372-2112.2014.08.030

Trivium流密码的基于自动推导的差分分析

丁林, 关杰

解放军信息工程大学, 河南郑州 450000

收稿日期:2012-11-28 修回日期:2013-06-14 出版日期:2014-08-25
- 作者简介:
- 丁林男，1987年生于河南信阳.解放军信息工程大学博士生.研究方向为流密码分析.E-mail：dinglin_cipher@163.com；关杰女，1974年生于河南郑州.解放军信息工程大学教授、硕士生导师，研究方向为密码学与信息安全.E-mail：guanjie007@163.com
- 基金资助:
- 国家自然科学基金 (No.61202491，No.61272041，No.61272488）; 全军军事学研究生课题 (No.2010JY0263-149）; 信息保障技术重点实验室开放基金 (No.KJ-13-007）; 保密通信重点实验室基金 (No.9140C110303140C11003）

Differential Cryptanalysis of Trivium Stream Cipher Based on Automatic Deduction

DING Lin, GUAN Jie

The PLA Information Engineering University, Zhengzhou, Henan 450000, China

Received:2012-11-28 Revised:2013-06-14 Online:2014-08-25 Published:2014-08-25
- Supported by:
- National Natural Science Foundation of China (No.61202491, No.61272041, No.61272488); PLA Military Science Postgraduate Project (No.2010JY0263-149); Open Fund of Key Laboratory of Information Assurance Technology (No.KJ-13-007); Fund of Key Laboratory of Secure Communication (No.9140C110303140C11003)

摘要/Abstract

摘要：

Trivium是欧洲eSTREAM工程评选出的7个最终胜出的流密码算法之一.本文提出了针对Trivium的基于自动推导的差分分析技术，利用该技术可以得到任意轮Trivium算法的差分传递链.将该技术应用于轮数为288的简化版Trivium算法，提出了一个有效的区分攻击，仅需2²⁶个选择IV，区分优势为0.999665，攻击结果远优于已有的线性密码分析和多线性密码分析.将该技术应用于更多轮的Trivium算法和由Turan和Kara提出的修改Trivium算法，结果表明，初始化轮数低于359的Trivium算法不能抵抗差分分析，修改Trivium算法在抵抗差分分析方面优于原Trivium算法.

关键词: 密码分析, 差分分析, Trivium, 流密码

Abstract:

Trivium is a stream cipher and has successfully been chosen as one of seven finalists by European eSTREAM project.In this paper,a differential cryptanalysis of Trivium based on automatic deduction is presented.This new technique enables the attacker to obtain differential characteristics on arbitrary-round Trivium.The technique is applied to 288-round Trivium,which results in an efficient distinguishing attack.Our attack only requires 2²⁶ chosen IVs with a distinguishing advantage of 0.999665.The result is much better than the existing single linear cryptanalysis and Linear Cryptanalysis with Multiple Approximations on 288-round Trivium.We also apply the technique to more-round Trivium and the modified Trivium proposed by Turan and Kara.The results show that Trivium reduced to no more than 359(out of 1152)initialization rounds is weak against differential cryptanalysis,and the modified Trivium is better against differential cryptanalysis than the original Trivium.

Key words: cryptanalysis, differential cryptanalysis, Trivium, stream cipher

中图分类号:

TN918.1

丁林, 关杰. Trivium流密码的基于自动推导的差分分析[J]. 电子学报, 2014, 42(8): 1647-1652.

DING Lin, GUAN Jie . Differential Cryptanalysis of Trivium Stream Cipher Based on Automatic Deduction[J]. Acta Electronica Sinica, 2014, 42(8): 1647-1652.

参考文献

[1] ECRYPT.eSTREAM:ECRYPT Stream Cipher Project,IST-2002-507932[EB/OL].http://www.ecrypt.eu.org/stream,2005-04-12.
[2] Cannière C D,Preneel B.Trivium[A].New Stream Cipher Designs[C].Germany:Springer-Verlag,2008.244-246.
[3] Turan M S,Kara O.Linear Approximations for 2-round Trivium[EB/OL].http://www.ecrypt.eu.org/stream/papersdir/2007/008.pdf,2007-12-28.
[4] 贾艳艳,胡予濮,杨文峰,高军涛.2 轮Trivium 的多线性密码分析[J].电子与信息学报,2011,33(1):223-227. Jia Y Y,Hu Y P,Yang W F,Gao J T.Linear cryptanalysis of 2-round trivium with multiple approximations[J].Journal of Electronics & Information Technology,2011,33(1):223-227.(in Chinese)
[5] 孙文龙,关杰,刘建东.针对简化版Trivium算法的线性分析[J].计算机学报,2012,35(9):1890-1896. Sun W L,Guan J,Liu J D.Linearcryptanalysis of simplified trivium[J].Chinese Journal of Computers,2012,35(9):1890-1896.(in Chinese)
[6] Maximov A,Biryukov A.Two trivial attacks on trivium[A].Selected Areas in Cryptography[C].Germany:Springer-Verlag,2007.36-55.
[7] Wong K K,Gregory V B.Improved algebraic cryptanalysis of QUAD,Bivium and Trivium via graph partitioning on equation systems[A].The 15th Australasian Conference on Information Security and Privacy[C].Germany:Springer-Verlag,2010.19-36.
[8] 李昕,林东岱.对Bivium流密码的变元猜测代数攻击[J].电子学报,2011,39(8):1727-1732. Li X,Lin D D.Guessingspecific variables in algebraic attacks on Bivium[J].Acta Electronica Sinica,2011,39(8):1727-1732.(in Chinese)
[9] Huang Z Y,Lin D D.Attacking Bivium and Trivium with the characteristic set method[A].Progress in Cryptology-AFRICACRYPT 2011[C].Germany:Springer-Verlag,2011.77-91.
[10] Schilling T E,Raddum H.Analysis of Trivium using compressed right hand side equations[A].The 14th International Conference on Information Security and Cryptology[C].Germany:Springer-Verlag,2011.18-32.
[11] Priemuth-Schmid D,Biryukov A.slid pairs insalsa 20 and Trivium[A].INDOCRYPT 2008[C].Germany:Springer-Verlag,2008.1-14.
[12] 关杰,丁林.修改Trivium流密码算法的滑动攻击[J].上海交通大学学报(自然版),2012,46(6):926-930. Guan J,Ding L.Slide attack on modified Trivium stream cipher[J].Journal of Shanghai Jiaotong University(Science),2012,46(6):926-930.(in Chinese)
[13] Zeng W,Qi W F.Finding slid pairs in Trivium with minisat[J].Science China Information Sciences,2012,55(9):1-8.
[14] Dinur I,Shamir A.cube attacks on tweakable black box polynomials[A].EUROCRYPT 2009[C].Germany:Springer-Verlag,2009.278-299.
[15] Mroczkowski P,Szmidt J.The cube attack on stream cipher Trivium and quadraticity tests[J].Fundamenta Informaticae,2012,114(3-4):309-318.
[16] Stankovski P.Greedy distinguishers and nonrandomness detectors[A].INDOCRYPT 2010[C].Germany:Springer-Verlag,2010.210-226.
[17] Pierre-Alain F,Thomas V.Improving key recovery to 784 and 799 rounds of Trivium using optimized cube attacks[EB/OL].http://www.di.ens.fr/～fouque/pub/fse13a.pdf,2013-6-14.
[18] Baignères T,Junod P,Vaudenay S.How far can we go beyond linear cryptanalysis?[A].ASIACRYPT 2004[C].Germany:Springer-Verlag,2004.432-450.

Trivium流密码的基于自动推导的差分分析

Differential Cryptanalysis of Trivium Stream Cipher Based on Automatic Deduction

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	杨继林, 王念平. 类CLEFIA动态密码结构抵抗差分密码分析能力评估[J]. 电子学报, 2021, 49(11): 2279-2283.
[2]	王念平. 一类分组密码变换簇抵抗线性密码分析的安全性评估[J]. 电子学报, 2020, 48(1): 137-142.
[3]	陈智雄, 刘华宁, 杨阳. 基于RSA模数的一类新型广义割圆序列的迹表示[J]. 电子学报, 2019, 47(7): 1512-1517.
[4]	李俊志, 关杰. 非线性反馈移存器型序列密码的完全性通用算法[J]. 电子学报, 2018, 46(9): 2075-2080.
[5]	董丽华, 曾勇, 王春红, 胡予濮. LFCSR:基于FCSR的新密码学部件[J]. 电子学报, 2018, 46(8): 1924-1930.
[6]	付立仕, 崔霆, 金晨辉. 嵌套SP网络的New-Structure系列结构的零相关线性逼近与不可能差分性质研究[J]. 电子学报, 2017, 45(6): 1367-1374.
[7]	魏长河, 李俊志, 张少武. 对288轮Trivium算法的线性分析[J]. 电子学报, 2017, 45(6): 1456-1461.
[8]	贾平, 徐洪, 来学嘉. LBlock-s算法的不可能差分分析[J]. 电子学报, 2017, 45(4): 966-973.
[9]	王念平. 四分组类CLEFIA变换簇抵抗差分密码分析的安全性评估[J]. 电子学报, 2017, 45(10): 2528-2532.
[10]	郭建胜, 崔竞一, 罗伟, 刘翼鹏. CIKS-128分组算法的相关密钥-差分攻击[J]. 电子学报, 2016, 44(8): 1837-1844.
[11]	黄永洪, 郭建胜, 罗伟. LBlock算法的相关密钥-不可能差分攻击[J]. 电子学报, 2015, 43(10): 1948-1953.
[12]	高海英, 金晨辉, 张军琪. 基于卡方统计量的多差分攻击方法[J]. 电子学报, 2014, 42(9): 1775-1780.
[13]	罗伟, 郭建胜. Cobra-H64/128算法的相关密钥-差分攻击[J]. 电子学报, 2013, 41(8): 1569-1573.
[14]	李昕;林东岱. 对Bivium流密码的变元猜测代数攻击[J]. 电子学报, 2011, 39(8): 1727-1732.
[15]	王慧娟;王锦玲. GF(q)上广义自缩序列的线性复杂度[J]. 电子学报, 2011, 39(2): 414-418.