Survey on approaches of stream cipher cryptanalysis

Zhaocun ZHOU; Dengguo FENG

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

您当前的位置：

首页 >

文章列表页 >

Survey on approaches of stream cipher cryptanalysis

Comprehensive Reviews | 更新时间：2024-06-05

- Survey on approaches of stream cipher cryptanalysis
- Journal on Communications Vol. 43, Issue 11, Pages: 183-198(2022)
- 作者机构：
  
  1. 中国科学院软件研究所可信计算与信息保障实验室，北京 100190
  2. 中国科学院大学，北京 100049
- 作者简介：
- 基金信息：
  
  The National Natural Science of China(U1636216)
- DOI：10.11959/j.issn.1000-436x.2022186
  CLC： TN918.1
- Online First：2022-11，
  
  Published：25 November 2022
- 稿件说明：
移动端阅览
Zhaocun ZHOU, Dengguo FENG. Survey on approaches of stream cipher cryptanalysis[J]. Journal on Communications, 2022, 43(11): 183-198.
DOI：

Zhaocun ZHOU, Dengguo FENG. Survey on approaches of stream cipher cryptanalysis[J]. Journal on Communications, 2022, 43(11): 183-198. DOI： 10.11959/j.issn.1000-436x.2022186.

摘要

研究密码分析方法对设计密码算法至关重要。鉴于此，回顾了目前主要的流密码分析方法，研究了流密码分析方法的分类与联系，从主要技术特点的角度将其分为基于相关性质、差分性质、代数方程组和时间存储数据折中这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.

关键词

Keywords

references

冯秀涛 . 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 .

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 .

ETSI/SAGE . Specification of the 3GPP confidentiality and integrity algorithms UEA2 ＆ UIA2.Document 2:SNOW 3G Specification [S ] . 2006 .

EKDAHL P , JOHANSSON T . A new version of the stream cipher SNOW [C ] // Selected Areas in Cryptography . Berlin:Springer , 2002 : 47 - 61 .

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 .

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 .

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 .

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 .

ARMKNECHT F , MIKHALEV V . On lightweight stream ciphers with shorter internal states [C ] // Fast Software Encryption 2015 . Berlin:Springer , 2015 : 451 - 470 .

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 .

CANNIERE C , PRENEEL B . Trivium [C ] // New Stream Cipher Designs . Berlin:Springer , 2008 : 244 - 266 .

JIAO L , HAO Y L , FENG D G . Stream cipher designs:a review [J ] . Science China Information Sciences , 2020 , 63 ( 3 ): 1 - 25 .

赵石磊 , 刘玲 , 黄海 , 等 . 流密码算法、架构与硬件实现研究 [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 .

张斌 , 徐超 , 冯登国 . 流密码的设计与分析:回顾、现状与展望 [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 .

冯登国 . 序列密码分析方法 [M ] . 北京 : 清华大学出版社 , 2021 .

FENG D G . Stream cipher cryptanalysis approaches [M ] . Beijing : Tsin ghua University Press , 2021 .

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 .

TODO Y , . Structural evaluation by generalized integral property [C ] // EUROCRYPT 2015 . Berlin:Springer , 2015 : 287 - 314 .

COPPERSMITH D , HALEVI S , JUTLA C . Cryptanalysis of stream ciphers with linear masking [C ] // Annual International Cryptology Conference . Berlin:Springer , 2002 : 515 - 532 .

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 .

WAGNER D , . A generalized birthday problem [C ] // Advance in Cryptology - CRYPTO 2002 . Berlin:Springer , 2002 : 18 - 22 .

MINDER L , SINCLAIR A . The extended k-tree algorithm [J ] . Journal of Cryptology , 2012 , 25 ( 2 ): 349 - 382 .

YANG J , JOHANSSON T , MAXIMOV A . Vectorized linear approximations for attacks on SNOW 3G [J ] . IACR Transactions on Symmetric Cryptology , 2020 ( 4 ): 249 - 271 .

YANG J , JOHANSSON T , MAXIMOV A . Spectral analysis of ZUC-256 [J ] . IACR Transactions on Symmetric Cryptology , 2020 ( 1 ): 266 - 288 .

SIEGENTHALER T . Decrypting a class of stream ciphers using ciphertext only [J ] . IEEE Transactions on Computers , 1985 , 34 ( 1 ): 81 - 85 .

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 .

ANDERSON R , . Searching for the optimum correlation attack [C ] // Fast Software Encryption 1995 . Berlin:Springer , 1995 : 137 - 143 .

LÖHLEIN B . Attacks based on conditional correlations against the nonlinear filter generator [J ] . IACR Cryptology ePrint Archive,2003 , 2003 :20.

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 .

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 .

MEIER W , STAFFELBACH O . Fast correlation attacks on certain stream ciphers [J ] . Journal of Cryptology , 1989 , 1 ( 3 ): 159 - 176 .

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 .

JOHANSSON T , JÖNSSON F ,, . Fast correlation attacks based on turbo code techniques [C ] // Advances in Cryptology-CRYPTO’99 . Berlin:Springer , 1999 : 181 - 197 .

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 .

GOLIC J D . Iterative optimum symbol-by-symbol decoding and fast correlation attacks [J ] . IEEE Transactions on Information Theory , 2001 , 47 ( 7 ): 3040 - 3049 .

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 .

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 .

JOHANSSON T , JÖSSON F . Fast correlation attacks through reconstruction of linear polynomials [C ] // Annual International Cryptology Conference . Berlin:Springer , 2000 : 300 - 315 .

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 .

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 .

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 .

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 .

TODO Y , ISOBE T , MEIER W , et al . Fast correlation attack revisited [C ] // Advances in Cryptology-CRYPTO 2018 . Berlin:Springer , 2018 : 129 - 159 .

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 .

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 .

BIHAM E , et al . Differential cryptanalysis in stream ciphers [R ] . 2007 .

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 .

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 .

VIELHABER M . Breaking ONE.FIVIUM by AIDA an algebraic IV differential attack [R ] . 2007 .

BIRYUKOV A , WAGNER D . Slide attacks [C ] // Fast Software Encryption 1999 . Berlin:Springer , 1999 : 245 - 259 .

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 .

ZHANG B , XU C , MEIER W . Fast near collision attack on the grain v1 stream cipher [C ] // EUROCRYPT 2018 . Berlin:Springer , 2018 : 771 - 802 .

DINUR I , SHAMIR A . Cube attacks on tweakable black box polynomials [C ] // Advances in Cryptology - EUROCRYPT 2009 . Berlin:Springer , 2009 : 278 - 299 .

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 .

AUMASSON P , DINUR I , HENZEN L , et al . Efficient FPGA implementations of high-dimensional cube testers on the stream cipher Grain-128 [R ] . 2009 .

DINUR I , SHAMIR A . Breaking Grain-128 with dynamic cube attacks [C ] // Fast Software Encryption 2011 . Berlin:Springer , 2011 : 167 - 187 .

TODO Y , MORII M . Bit-based division property and application to Simon family [C ] // Fast Software Encryption 2016 . Berlin:Springer , 2016 : 357 - 377 .

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 .

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 .

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 .

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 .

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 .

SUN Y . Automatic search of cubes for attacking stream ciphers [J ] . IACR Transactions on Symmetric Cryptology , 2021 ( 4 ): 100 - 123 .

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 .

WANG X Y , YU H B . How to break MD5 and other hash functions [C ] // EUROCRYPT 2005 . Berlin:Springer , 2005 : 19 - 35 .

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 .

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 .

MULLER F , . Differenctial attacks against the helix stream cipher [C ] // Fast Software Encryption 2004 . Berlin:Springer , 2004 : 94 - 108 .

KÜÇÜK Ö . Slide resynchronization attack on the initialization of grain 1.0 [R ] . 2006 .

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 .

KNUDSEN L , MEIER W , PRENEEL B , et al . Analysis methods for (alleged) RC4 [C ] // ASIACRYPT’98 . Berlin:Springer , 1998 : 327 - 341 .

PASALIC E . On guess and determine cryptanalysis of LFSR-based stream ciphers [J ] . IEEE Transactions on Information Theory , 2009 , 55 ( 7 ): 3398 - 3406 .

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 .

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 .

COURTOIS N T , MEIER W . Algebraic attacks on stream ciphers with linear feedback [C ] // Eurocrypt 2003 . Berlin:Springer , 2003 : 345 - 359 .

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 .

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 .

COURTOIS N , PIEPRZYK J . Cryptanalysis of block ciphers with overdefined systems of equations [C ] // Advances in Cryptology ASIACRYPT 2002 . Berlin:Springer , 2002 : 267 - 287 .

MEIER W , PASALIC E , CARLET C . Algebraic attacks and decomposition of Boolean functions [C ] // Advances in Cryptology - EUROCRYPT 2004 . Berlin:Springer , 2004 : 474 - 491 .

ARMKNECHT F , . Improving fast algebraic attacks [C ] // Fast Software Encryption 2004 . Berlin:Springer , 2004 : 65 - 82 .

BRAEKEN A , PRENEEL B . Probabilistic algebraic attacks [C ] // Cryp tography and Coding 2005 . Berlin:Springer , 2005 : 290 - 303 .

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 .

HELLMAN M . A cryptanalytic time-memory trade-off [J ] . IEEE Transactions on Information Theory , 1980 , 26 ( 4 ): 401 - 406 .

BIRYUKOV A , SHAMIR A . Cryptanalytic time/memory/data tradeoffs for stream ciphers [C ] // Advances in Cryptology-ASIACRYPT 2000 . Berlin:Springer , 2000 : 1 - 13 .

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 .

MAITRA S , SINHA N , SIDDHANTI A , et al . A TMDTO attack against lizard [J ] . IEEE Transactions on Computers , 2018 , 67 ( 5 ): 733 - 739 .

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 .

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 .

CEN Z , FENG X T , WANG Z Y , et al . Minimizing deduction system and its application [J ] . arXiv Preprint,arXiv:2006.05833 , 2020 .

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 .

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 .

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 .

BEYNE T , . A geometric approach to linear cryptanalysis [C ] // ASIA CRYPT 2021 . Berlin:Springer , 2021 : 36 - 66 .

关杰 , 丁林 , 张凯 . 序列密码的分析与设计 [M ] . 北京 : 科学出版社 , 2019 .

GUAN J , DING L , ZHANG K . The cryptanalysis and design of stream ciphers [M ] . Beijing : Science Press , 2019 .

冯登国 . 频谱理论及其在密码学中的应用 [M ] . 北京 : 科学出版社 , 2000 .

FENG D G . The spectral theory and its applications in cryptology [M ] . Beijing : Science Press , 2000 .

冯登国 . 密码分析学 [M ] . 北京 : 清华大学出版社 , 2000 .

FENG D G . Cryptanalysis [M ] . Beijing : Tsinghua University Press , 2000 .

Views

1210

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Collision analysis of the GMR-2 cipher used in the satellite phone

On the linear complexity of a new generalized cyclotomic sequence with length mover GF(h)

Improvement and evaluation for algebraic fault attacks on PRESENT

Computing on the joint quadratic complexity of multiple periodic sequences

Review of algebraic attacks on stream ciphers

Related Author

Chaojing TANG

Jiao HU

Ruilin LI

Long-fei LIU

Kai YANG

Xiao-yuan YANG

Jing HUANG

Xin-jie ZHAO

Related Institution

College of Electronic Science, National University of Defense Technology

Key Laboratory of Network ＆Information Security of Armed Police Force,Engineering University of Armed Police Force

Key Laboratory of Computer Network ＆Information Security of the Ministry of Education,Xidian University

Third Department of No.61541 Unit

The Institute of North Electronic Equipment

AI问答

⁰