流密码分析方法研究综述

doi:10.11959/j.issn.1000-436x.2022186

摘要/Abstract

摘要：

研究密码分析方法对设计密码算法至关重要。鉴于此，回顾了目前主要的流密码分析方法，研究了流密码分析方法的分类与联系，从主要技术特点的角度将其分为基于相关性质、差分性质、代数方程组和时间存储数据折中这4种类型，分别阐述了各分析方法的基本原理、主要技术及相关研究进展，并概括了其主要特点。此外，对流密码分析方法未来的发展方向进行了展望。

关键词: 流密码, 线性区分分析, 相关分析, 碰撞分析, 立方分析, 代数分析, 猜测确定分析, 时间存储数据折中分析

Abstract:

Cryptanalysis plays an essential role in the design of ciphers algorithm.Based on this, the common approaches were reviewed and investigated to clarify their relations.These approaches were categorized into four classes according to their main techniques, i.e., the correlation-based approaches, the differentials-based approaches, the algebraic-equations-based approaches and the time-memory data trade-off (TMDTO) approaches.And their principles, basic technical ideas and developments were presented, and their main features were summarized.Moreover, the future of stream cipher cryptanalysis approach was prospected at last.

Key words: stream cipher, linear distinguishing cryptanalysis, correlation cryptanalysis, collision cryptanalysis, cube cryptanalysis, algebraic cryptanalysis, guess-and-determine cryptanalysis, TMDTO cryptanalysis

中图分类号:

TN918.1

周照存, 冯登国. 流密码分析方法研究综述[J]. 通信学报, 2022, 43(11): 183-198.

Zhaocun ZHOU, Dengguo FENG. Survey on approaches of stream cipher cryptanalysis[J]. Journal on Communications, 2022, 43(11): 183-198.

图/表 9

图1

表1

表2

表3

表4

表5

表6

表7

表8

参考文献 95

[1]	冯秀涛 . 3GPP LTE国际加密标准ZUC算法[J]. 信息安全与通信保密, 2011,9(12): 45-46.
	FENG X T . ZUC algorithm:3GPP LTE international encryption standard[J]. Information Security and Communications Privacy, 2011,9(12): 45-46.
[2]	TEAM D . ZUC-256流密码算法[J]. 密码学报, 2018,5(2): 167-179.
	TEAM D . ZUC-256 stream cipher[J]. Journal of Cryptologic Research, 2018,5(2): 167-179.
[3]	ETSI/SAGE. Specification of the 3GPP confidentiality and integrity algorithms UEA2 ＆ UIA2.Document 2:SNOW 3G Specification[S]. 2006.
[4]	EKDAHL P , JOHANSSON T . A new version of the stream cipher SNOW[C]// Selected Areas in Cryptography. Berlin:Springer, 2002: 47-61.
[5]	EKDAHL P , JOHANSSON T , MAXIMOV A ,et al. A new SNOW stream cipher called SNOW-V[J]. IACR Transactions on Symmetric Cryptology, 2019(3): 1-42.
[6]	HELL M , JOHANSSON T , MEIER W . Grain:a stream cipher for constrained environments[J]. International Journal of Wireless and Mobile Computing, 2006,2(1): 86-93.
[7]	AGREN M , HELL M , JOHANSSON T ,et al. Grain-128a:a new version of Grain-128 with optional authentication[J]. International Journal of Wireless and Mobile Computing, 2011,5(1): 48-59.
[8]	HELL M , JOHANSSON T , MEIER W ,et al. An AEAD variant of the grain stream cipher[C]// Codes,Cryptology and Information Security. Berlin:Springer, 2019: 55-71.
[9]	ARMKNECHT F , MIKHALEV V . On lightweight stream ciphers with shorter internal states[C]// Fast Software Encryption 2015. Berlin:Springer, 2015: 451-470.
[10]	MIKHALEV V , ARMKNECHT F , MULLER C . On ciphers that continuously access the non-volatile key[J]. IACR Transactions on Symmetric Cryptology, 2016(2): 52-79.
[11]	CANNIERE C , PRENEEL B . Trivium[C]// New Stream Cipher Designs. Berlin:Springer, 2008: 244-266.
[12]	JIAO L , HAO Y L , FENG D G . Stream cipher designs:a review[J]. Science China Information Sciences, 2020,63(3): 1-25.
[13]	赵石磊, 刘玲, 黄海 ,等. 流密码算法、架构与硬件实现研究[J]. 密码学报, 2021,8(6): 1039-1057.
	ZHAO S L , LIU L , HUANG H ,et al. Algorithm,architecture and hardware implementation of stream cipher[J]. Journal of Cryptologic Research, 2021,8(6): 1039-1057.
[14]	张斌, 徐超, 冯登国 . 流密码的设计与分析:回顾、现状与展望[J]. 密码学报, 2016,3(6): 527-545.
	ZHANG B , XU C , FENG D G . Design and analysis of stream ciphers:past,present and future directions[J]. Journal of Cryptologic Research, 2016,3(6): 527-545.
[15]	冯登国 . 序列密码分析方法[M]. 北京: 清华大学出版社, 2021.
	FENG D G . Stream cipher cryptanalysis approaches[M]. Beijing: Tsin ghua University Press, 2021.
[16]	BAIGENERES T , JUNOD P , VAUDENAY S . How far can we go beyond linear cryptanalysis[C]// Advances in Cryptology - ASIACRYPT 2004. Berlin:Springer, 2004: 432-450.
[17]	TODO Y , . Structural evaluation by generalized integral property[C]// EUROCRYPT 2015. Berlin:Springer, 2015: 287-314.
[18]	COPPERSMITH D , HALEVI S , JUTLA C . Cryptanalysis of stream ciphers with linear masking[C]// Annual International Cryptology Conference. Berlin:Springer, 2002: 515-532.
[19]	NIKOLIC I , SASAKI Y . Refinements of the k-tree algorithm for generalized birthday problem[C]// Advances in Cryptology-ASIA CRYPT 2015. Berlin:Springer, 2015: 683-703.
[20]	WAGNER D , . A generalized birthday problem[C]// Advance in Cryptology - CRYPTO 2002. Berlin:Springer, 2002: 18-22.
[21]	MINDER L , SINCLAIR A . The extended k-tree algorithm[J]. Journal of Cryptology, 2012,25(2): 349-382.
[22]	YANG J , JOHANSSON T , MAXIMOV A . Vectorized linear approximations for attacks on SNOW 3G[J]. IACR Transactions on Symmetric Cryptology, 2020(4): 249-271.
[23]	YANG J , JOHANSSON T , MAXIMOV A . Spectral analysis of ZUC-256[J]. IACR Transactions on Symmetric Cryptology, 2020(1): 266-288.
[24]	SIEGENTHALER T . Decrypting a class of stream ciphers using ciphertext only[J]. IEEE Transactions on Computers, 1985,34(1): 81-85.
[25]	LEE S , CHEE S , PARK S ,et al. Conditional correlation attack on nonlinear filter generators[C]// Advances in Cryptology-ASIACRYPT’96. Berlin:Springer, 1996: 360-367.
[26]	ANDERSON R , . Searching for the optimum correlation attack[C]// Fast Software Encryption 1995. Berlin:Springer, 1995: 137-143.
[27]	L?HLEIN B . Attacks based on conditional correlations against the nonlinear filter generator[J]. IACR Cryptology ePrint Archive,2003, 2003:20.
[28]	LU Y , MEIER W , VAUDENAY S . The conditional correlation attack:a practical attack on bluetooth encryption[C]// Advances in Cryptology CRYPTO 2005. Berlin:Springer, 2005: 97-117.
[29]	ZHANG B , XU C , FENG D G . Real time cryptanalysis of bluetooth encryption with condition masking[C]// Advances in Cryptology-CRYPTO 2013. Berlin:Springer, 2013: 165-182.
[30]	MEIER W , STAFFELBACH O . Fast correlation attacks on certain stream ciphers[J]. Journal of Cryptology, 1989,1(3): 159-176.
[31]	JOHANSSON T , J?SSON F ,, . Improved fast correlation attacks on stream ciphers via convolutional codes[C]// International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 1999: 347-362.
[32]	JOHANSSON T , J?NSSON F ,, . Fast correlation attacks based on turbo code techniques[C]// Advances in Cryptology-CRYPTO’99. Berlin:Springer, 1999: 181-197.
[33]	CANTEAUT A , TRABBIA M . Improved fast correlation attacks using parity-check equations of weight 4 and 5[C]// International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2000: 573-588.
[34]	GOLIC J D . Iterative optimum symbol-by-symbol decoding and fast correlation attacks[J]. IEEE Transactions on Information Theory, 2001,47(7): 3040-3049.
[35]	ZHOU Z C , FENG D , ZHANG B . Vectorial decoding algorithm for fast correlation attack and its applications to stream cipher grain-128a[J]. IACR Transactions on Symmetric Cryptology, 2022(2): 322-350.
[36]	CHEPYZHOV V , JOHANSSON T , SMEETS B . A simple algorithm for fast correlation attacks on stream ciphers[C]// Fast Software Encryption 2000. Berlin:Springer, 2000: 181-195.
[37]	JOHANSSON T , J?SSON F . Fast correlation attacks through reconstruction of linear polynomials[C]// Annual International Cryptology Conference. Berlin:Springer, 2000: 300-315.
[38]	MIHALJEVI M J , FOSSORIER M P C , IMAI H . Fast correlation attack algorithm with list decoding and an application[C]// Fast Software Encryption 2002. Berlin:Springer, 2002: 196-210.
[39]	CHOSE P , JOUX A , MITTON M . Fast correlation attacks:an algorithmic point of view[C]// International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2002: 209-221.
[40]	ZHANG B , XU C , MEIER W . Fast correlation attacks over extension fields,large-unit linear approximation and cryptanalysis of SNOW 2.0[C]// Advances in Cryptology-CRYPTO 2015. Berlin:Springer, 2015: 643-662.
[41]	SHI Z , JIN C , ZHANG J , CUI T ,et al. A correlation attack on full SNOW-V and SNOW-Vi[C]// Advances in Cryptology-EUROCRYPT 2022. Berlin:Springer, 2022: 1-6.
[42]	TODO Y , ISOBE T , MEIER W ,et al. Fast correlation attack revisited[C]// Advances in Cryptology-CRYPTO 2018. Berlin:Springer, 2018: 129-159.
[43]	WANG S C , LIU M C , LIN D D ,et al. Fast correlation attacks on grain-like small state stream ciphers and cryptanalysis of plantlet Fruit-v2 and Fruit-80[R]. 2019.
[44]	WATANABE D , BIRYUKOV A , CANNIèRE C , . A distinguishing attack of SNOW 2.0 with linear masking method[C]// Selected Areas in Cryptography. Berlin:Springer, 2004: 222-233.
[45]	BIHAM E , et al . Differential cryptanalysis in stream ciphers[R]. 2007.
[46]	ENGLUND H , JOHANSSON T , S?NMEZ TURAN M , . A framework for chosen IV statistical analysis of stream ciphers[C]// Lecture Notes in Computer Science. Berlin:Springer, 2007: 268-281.
[47]	FISCHER S , KHAZAEI S , MEIER W . Chosen IV statistical analysis for key recovery attacks on stream ciphers[C]// Progress in Cryptology AFRICACRYPT 2008. Berlin:Springer, 2008: 236-245.
[48]	VIELHABER M . Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack[R]. 2007.
[49]	BIRYUKOV A , WAGNER D . Slide attacks[C]// Fast Software Encryption 1999. Berlin:Springer, 1999: 245-259.
[50]	ZHANG B , LI Z Q , FENG D G ,et al. Near collision attack on the grain v1 stream cipher[C]// Fast Software Encryption 2013. Berlin:Springer, 2014: 518-538.
[51]	ZHANG B , XU C , MEIER W . Fast near collision attack on the grain v1 stream cipher[C]// EUROCRYPT 2018. Berlin:Springer, 2018: 771-802.
[52]	DINUR I , SHAMIR A . Cube attacks on tweakable black box polynomials[C]// Advances in Cryptology - EUROCRYPT 2009. Berlin:Springer, 2009: 278-299.
[53]	AUMASSON J , DINUR I , MEIER W ,et al. Cube testers and key recovery attacks on reduced-round MD6 and trivium[C]// Fast Software Encryption 2009. Berlin:Springer, 2009: 1-22.
[54]	AUMASSON P , DINUR I , HENZEN L ,et al. Efficient FPGA implementations of high-dimensional cube testers on the stream cipher Grain-128[R]. 2009.
[55]	DINUR I , SHAMIR A . Breaking Grain-128 with dynamic cube attacks[C]// Fast Software Encryption 2011. Berlin:Springer, 2011: 167-187.
[56]	TODO Y , MORII M . Bit-based division property and application to Simon family[C]// Fast Software Encryption 2016. Berlin:Springer, 2016: 357-377.
[57]	TODO Y , ISOBE T , HAO Y L ,et al. Cube attacks on non-blackbox polynomials based on division property[C]// Advances in Cryptology CRYPTO 2017. Berlin:Springer, 2017: 250-279.
[58]	XIANG Z J , ZHANG W T , BAO Z Z ,et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers[C]// Advances in Cryptology-ASIACRYPT 2016. Berlin:Springer, 2016: 648-678.
[59]	WANG Q J , HAO Y L , TODO Y ,et al. Improved division property based cube attacks exploiting algebraic properties of superpoly[C]// Advances in Cryptology-CRYPTO 2018. Berlin:Springer, 2018: 275-305.
[60]	WANG S P , HU B , GUAN J ,et al. MILP-aided method of searching division property using three subsets and applications[C]// Advances in Cryptology -ASIACRYPT 2019. Berlin:Springer, 2019: 398-427.
[61]	HAO Y L , LEANDER G , MEIER W ,et al. Modeling for three-subset division property without unknown subset improved cube attacks against trivium and grain - 128AEAD[C]// EUEROCRYPT 2020. Berlin:Springer, 2020: 466-495.
[62]	SUN Y . Automatic search of cubes for attacking stream ciphers[J]. IACR Transactions on Symmetric Cryptology, 2021(4): 100-123.
[63]	HUANG S Y , WANG X Y , XU G W ,et al. Conditional cube attacks on reduced-round Keccak sponge function[C]// EUROCRYPT 2017. Berlin:Springer, 2017: 259-288.
[64]	WANG X Y , YU H B . How to break MD5 and other hash functions[C]// EUROCRYPT 2005. Berlin:Springer, 2005: 19-35.
[65]	KNELLWOLF S , MEIER W , NAYA-PLASENCIA M , . Conditional differential cryptanalysis of NLFSR-based cryptosystems[C]// Advances in Cryptology - ASIACRYPT 2010. Berlin:Springer, 2010: 130-145.
[66]	LI Z , DONG X Y , WANG X Y . Conditional cube attack on round-reduced ASCON[J]. IACR Transactions on Symmetric Cryptology, 2017(1): 175-202.
[67]	MULLER F , . Differenctial attacks against the helix stream cipher[C]// Fast Software Encryption 2004. Berlin:Springer, 2004: 94-108.
[68]	Kü?üK ? . Slide resynchronization attack on the initialization of grain 1.0[R]. 2006.
[69]	HAO Y L , JIAO L , LI C Y ,et al. Links between division property and other cube attack variants[J]. IACR Transactions on Symmetric Cryptology, 2020(1): 363-395.
[70]	KNUDSEN L , MEIER W , PRENEEL B ,et al. Analysis methods for (alleged) RC4[C]// ASIACRYPT’98. Berlin:Springer, 1998: 327-341.
[71]	PASALIC E . On guess and determine cryptanalysis of LFSR-based stream ciphers[J]. IEEE Transactions on Information Theory, 2009,55(7): 3398-3406.
[72]	FENG X T , LIU J , ZHOU Z C ,et al. A byte-based guess and determine attack on SOSEMANUK[C]// ASIACRYPT 2010. Berlin:Springer, 2010: 146-157.
[73]	YANG J , JOHANSSON T , MAXIMOV A . Improved guess-anddetermine and distinguishing attacks on SNOW-V[J]. IACR Transactions on Symmetric Cryptology, 2021(3): 54-83.
[74]	COURTOIS N T , MEIER W . Algebraic attacks on stream ciphers with linear feedback[C]// Eurocrypt 2003. Berlin:Springer, 2003: 345-359.
[75]	ARS G , FAUGèRE J C , IMAI H ,et al. Comparison between XL and Gr?bner basis algorithms[C]// Advances in Cryptology - ASIACRYPT 2004. Berlin:Springer, 2004: 338-353.
[76]	COURTOIS N , KLIMOV A , PATARIN J ,et al. Efficient algorithms for solving overdefined systems of multivariate polynomial equations[C]// Advances in Cryptology EUROCRYPT 2000. Berlin:Springer, 2000: 392-407.
[77]	COURTOIS N , PIEPRZYK J . Cryptanalysis of block ciphers with overdefined systems of equations[C]// Advances in Cryptology ASIACRYPT 2002. Berlin:Springer, 2002: 267-287.
[78]	MEIER W , PASALIC E , CARLET C . Algebraic attacks and decomposition of Boolean functions[C]// Advances in Cryptology - EUROCRYPT 2004. Berlin:Springer, 2004: 474-491.
[79]	ARMKNECHT F , . Improving fast algebraic attacks[C]// Fast Software Encryption 2004. Berlin:Springer, 2004: 65-82.
[80]	BRAEKEN A , PRENEEL B . Probabilistic algebraic attacks[C]// Cryp tography and Coding 2005. Berlin:Springer, 2005: 290-303.
[81]	HAWKES P , ROSE G G . Rewriting variables:the complexity of fast correlation attacks on stream ciphers[C]// Advances in Cryptology-CRYPTO 2004. Berlin:Springer, 2004: 390-406.
[82]	HELLMAN M . A cryptanalytic time-memory trade-off[J]. IEEE Transactions on Information Theory, 1980,26(4): 401-406.
[83]	BIRYUKOV A , SHAMIR A . Cryptanalytic time/memory/data tradeoffs for stream ciphers[C]// Advances in Cryptology-ASIACRYPT 2000. Berlin:Springer, 2000: 1-13.
[84]	BIRYUKOV A , SHAMIR A , WAGNER D . Real time cryptanalysis of A5/1 in a PC[C]// Fast Software Encryption 2000. Berlin:Springer, 2000: 1-18.
[85]	MAITRA S , SINHA N , SIDDHANTI A ,et al. A TMDTO attack against lizard[J]. IEEE Transactions on Computers, 2018,67(5): 733-739.
[86]	ESGIN M F , KARA O . Practical cryptanalysis of full sprout with TMD tradeoff attacks[C]// Selected Areas in Cryptography-SAC 2015. Berlin:Springer, 2015: 67-85.
[87]	FUNABIKI Y , TODO Y , ISOBE T ,et al. Several MILP-aided attacks against SNOW 2.0[C]// Cryptology and Network Security. Berlin:Springer, 2018: 394-413.
[88]	CEN Z , FENG X T , WANG Z Y ,et al. Minimizing deduction system and its application[J]. arXiv Preprint,arXiv:2006.05833, 2020.
[89]	BOURA C , COGGIA D . Efficient MILP modelings for sboxes and linear layers of SPN ciphers[J]. IACR Transactions on Symmetric Cryptology, 2020(3): 327-361.
[90]	BEIERLE C , DERBEZ P , LEANDER G ,et al. Cryptanalysis of the GPRS encryption algorithms GEA-1 and GEA-2[C]// Advances in Cryptology- EUROCRYPT 2021. Berlin:Springer, 2021: 155-183.
[91]	SZMIDT J , . The cube attack on courtois toy cipher[C]// Proceedings of International Conference on Number-Theoretic Methods in Cryptology. Berlin:Springer, 2017: 241-253.
[92]	BEYNE T , . A geometric approach to linear cryptanalysis[C]// ASIA CRYPT 2021. Berlin:Springer, 2021: 36-66.
[93]	关杰, 丁林, 张凯 . 序列密码的分析与设计[M]. 北京: 科学出版社, 2019.
	GUAN J , DING L , ZHANG K . The cryptanalysis and design of stream ciphers[M]. Beijing: Science Press, 2019.
[94]	冯登国 . 频谱理论及其在密码学中的应用[M]. 北京: 科学出版社, 2000.
	FENG D G . The spectral theory and its applications in cryptology[M]. Beijing: Science Press, 2000.
[95]	冯登国 . 密码分析学[M]. 北京: 清华大学出版社, 2000.
	FENG D G . Cryptanalysis[M]. Beijing: Tsinghua University Press, 2000.

分析方法	分析对象	密钥长度/bit	分析效果（时间复杂度，数据复杂度，存储复杂度）
线性区分分析	SNOW 1.0	128	2 ^101.6,2^101.6,—
条件相关分析	E0	128	2 ³⁹,2³⁹,—
快速相关分析	SNOW-V	256	2 ^246.53,2^237.5,2^238.77
	Grain-128a	128	2 ^115.4,2^113.8,—
	Grain-v1	80	2 ^76.7,2^75.1,—

分析方法	主要技术	特点
线性区分分析	构造密钥流之间的线性相关性质	①适用于基于LFSR的流密码
		②受生成校验式和相关性的限制
Lee的条件相关分析	输出条件下输入变量的相关性	①条件相关性强于一般相关性
		②适用于分析滤波函数型流密码
Lu的条件相关分析	部分输入未知且均匀随机的条件下输出条件的相关性	①条件相关性强于一般相关性
		②特殊性质下FWHT加速
		③目前仅见于分析E0算法
Meier的快速相关分析	基于贝叶斯迭代过程软判定噪声分布	①缺乏可靠的复杂度评估
		②受特殊校验式和相关性的限制
基于信息集译码的快速相关分析	基于噪声折叠技术多步状态恢复分析	①适用于基于LFSR的流密码
		②可FWHT加速计算
		③受生成校验式和相关性的限制
Todo的快速相关分析	基于有限域上线性掩码的交换性先恢复中间状态	①可用多个线性逼近降低复杂度
		②可FWHT加速计算
		③受相关性和LFSR规模的限制

分析方法	分析对象	密钥长度/bit	分析效果（T 为时间复杂度，D为数据复杂度）
差分分析	Helix	256	T =2⁸⁸,D=2^12[67]
滑动分析	Grain v0	80	2^{- 2}概率滑动碰撞^[68]
近似碰撞分析	Grain-v1	80	T =2^86.1,D=2^19[51]
传统立方分析	767轮Trivium	128	T=2^36[52]
动态立方分析	全轮Grain-128	128	弱密钥集上快于穷举^[55]
	全轮Grain-128	128	选择IV假设T =2⁸⁴,D=2^62.4
划分性质立方分析	855轮Trivium	80	T=2^77[62]
	190轮Grain-128AEAD	128	T =2^123[61]
	763轮Acorn	128	T=2 ^125.54[69]
条件立方分析	Ascon	128	T =2^1039[66]
	容量256/512Keccak-MAC	128	T =D=2^72[63]

分析方法	主要技术	特点
差分分析	与分组密码差分分析相似	受差分传播性质制约
滑动分析	与滑动密钥分析相似	受轮对称性制约
近似碰撞分析	基于内部状态近似差分与密钥流差分的不均匀性	受算法结构影响大
传统立方分析	通过计算公开变量高阶差分来简化多项式以恢复秘密变量或者建立区分器	要求初始化更新函数简单
动态立方分析	部分公开变量设为动态以放大立方检验的非随机性	①所需立方集的规模更小
		②内部状态分析更加复杂
划分性质立方分析	基于划分性质分析代数正规型的系数来恢复超级多项式	①实现了更大的立方集
		②能够有效恢复超级多项式
条件立方分析	通过增加对IV的条件来降低立方变量多项式的次数	适用于类Keccak-MAC算法

分析方法	分析对象	密钥长度/bit密钥长度/bit	时间复杂度时间复杂度
猜测确定分析猜测确定分析	SOSEMANUKSOSEMANUK	128	2 ^176[72]
	SNOW-V	256	2 ^378[73]
代数分析	LILI-128	128	2 ^57[74]
	Toyocrypt	128	2 ^49[74]
快速代数分析	E0	128	2 ^49[80]