On the computational complexity of finding a minimal basis for the guess and determine attack

Khazaei, Sh.; Moazami, F.

doi:10.22042/isecure.2017.79681.373

On the computational complexity of finding a minimal basis for the guess and determine attack

Document Type : Research Article

Authors

Sh. Khazaei ¹

F. Moazami ²

¹ Sharif University of Technology, Department of Mathematical Sciences, Iran, Tehran

² Shahid Beheshti University, Cyberspace Research Institute, Iran, Tehran

https://doi.org/10.22042/isecure.2017.79681.373

Abstract

Guess-and-determine attack is one of the general attacks on stream ciphers. It is a common cryptanalysis tool for evaluating security of stream ciphers. The effectiveness of this attack is based on the number of unknown bits which will be guessed by the attacker to break the cryptosystem. In this work, we present a relation between the minimum numbers of the guessed bits and uniquely restricted matching of a graph. This leads us to see that finding the minimum number of the guessed bits is NP-complete. Although fixed parameter tractability of the problem in term of minimum number of the guessed bits remains an open question, we provide some related results. Moreover, we introduce some closely related graph concepts and problems including alternating cycle free matching, jump number and forcing number of a perfect matching.

Keywords

Guess-and-determine Attack

Computational Complexity

NP-complete

Fixed Parameter Tractable

Uniquely Restricted Matching

Alternating Cycle Free Matching

perfect matching

Jump Number

Forcing Number

20.1001.1.20082045.2017.9.2.2.9

Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmen, and Sven Verdoolaege. Analysis Methods for (Alleged) RC4. In ASIACRYPT, pages 327{341, 1998.
[2] Jovan Dj. Golic. Cryptanalysis of Alleged A5 Stream Cipher. In EUROCRYPT, pages 239{255, 1997.
[3] Christophe De Canniere. Guess and determine attack on SNOW. NESSIE Public Document, NES/DOC/KUL/WP5/011/a, 2001.
[4] Philip Hawkes and Gregory G. Rose. Guess-and-Determine Attacks on SNOW. In Selected Areas in Cryptography, pages 37{46, 2002.
[5] Azad Mohammadi-Chambolbol. Cryptanalysis of word-oriented stream ciphers. Master thesis
(in Persian), Sharif University of Technology.,2004.
[6] Hadi Ahmadi and Taraneh Eghlidos. Advanced Guess and Determine Attacks on Stream Ciphers. International Symposium on Telecommu-nications (IST), Tehran, Iran, 2005.
[7] Hadi Ahmadi and Taraneh Eghlidos. Heuristic guess-and-determine attacks on stream ciphers.IET Information Security, 3(2):66{73, 2009.
[8] Philip Hawkes. An attack on SOBER-II. Technical report, QUALCOMM Australia, Suite 410, Birkenhead Point, Drummoyne NSW 2137, Australia, 1999.
[9] S Blackburn, S Murphy, F Piper, and P Wild. A SOBERing remark. Unpublished report. Information Security Group, Royal Holloway University of London, Egham, Surrey TW20 0EX, UK,1998.
[10] Daniel Bleichenbacher, Sarvar Patel, and Willi Meier. Analysis of the SOBER stream cipher. TIA contribution TR45. AHAG/99.08, 30, 1999.
[11] Daniel Bleichenbacher and Sarvar Patel. SOBER Crytanalysis. In FSE, pages 305{316, 1999.
[12] Christophe De Canniere. Guess and determine attack on SOBER. NESSIE Public Document, NES/DOC/KUL/WP5/010/a, 2001.
[13] Steve Babbage, Christophe De Canniere, Joseph Lano, Bart Preneel, and Joos Vandewalle. Cryptanalysis of SOBER-t32. In FSE, pages 111{128,2003.
[14] Hadi Ahmadi, Taraneh Eghlidos, and Shahram Khazaei. Improved guess and determine attack on SOSEMANUK. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/085,2005. http://www.ecrypt.eu.org/stream/papersdir/085.pdf.
[15] Yukiyasu Tsunoo, Teruo Saito, Maki Shigeri, Tomoyasu Suzaki, Hadi Ahmadi, Taraneh Eghlidos,and Shahram Khazaei. Evaluation of SOSEMANUK with regard to guess-and-determine attacks. SASC (the State of the Art of Stream Ciphers), pages 25{34, 2006.
[16] Xiutao Feng, Jun Liu, Zhaocun Zhou, Chuankun Wu, and Dengguo Feng. A Byte-Based Guess and Determine Attack on SOSEMANUK. In ASIACRYPT, pages 146{157, 2010.
[17] John Mattsson. A Guess-and-Determine Attack on the Stream Cipher Polar Bear. eSTREAM, ECRYPT Stream Cipher Project, Report 2006/017, 2006. http://www.ecrypt.eu.org/stream/papersdir/2006/017.pdf.
[18] Mahdi Hasanzadeh, Elham Shakour, and Shahram Khazaei. Improved Cryptanalysis of Polar Bear. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/084, 2005. http://www.ecrypt.eu.org/stream/papersdir/084.pdf.

[19] Xiutao Feng, Zhenqing Shi, Chuankun Wu, and Dengguo Feng. On Guess and Determine Analysis of Rabbit. Int. J.Found. Comput. Sci.,22(6):1283{1296, 2011.
[20] Hans L. Bodlaender and Arie M. C. A. Koster.Treewidth computations i. upper bounds. Inf.Comput., 208(3):259{275,2010.
[21] Ton Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994.
[22] Patrik Ekdahl and Thomas Johansson. A New Version of the Stream Cipher SNOW. In Selected Areas in Cryptography, pages 47{61, 2002.
[23] Martin Charles Golumbic, Tirza Hirst, and Moshe Lewenstein. Uniquely restricted matchings. Algorithmica, 31(2):139{154, 2001.
[24] Bruno Courcelle. The monadic second-order logic of graphs: Definable sets of finite graphs. In Graph-Theoretic Concepts in Computer Science,14th International Workshop, WG '88, Amsterdam, The Netherlands, June 15-17, 1988, Proceedings, pages 30{53, 1988.
[25] Benjamin A. Burton, Thomas Lewiner, Jo~ao Paix~ao, and Jonathan Spreer. Parameterized complexity of discrete morse theory. ACM Trans.Math. Softw., 42(1):6:1{6:24, 2016.
[26] Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth.SIAM J. Comput., 25(6):1305{1317, 1996.
[27] Michel Habib. Comparability invariants. In Orders: description and roles (L'Arbresle, 1982), volume 99 of North Holland Math. Stud., pages 371{385. North-Holland, Amsterdam, 1984.
[28] Rolf H. Mohring. Algorithmic aspects of comparability graphs and interval graphs. In Graphs
and order (Banff, Alta., 1984), volume 147 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci.,pages 41{101. Reidel,Dordrecht, 1985.
[29] G. Chaty and M. Chein. Ordered matching and matchings without alternating cycles in bipartite graphs. Utilitas Math., 16:183{187, 1979.
[30] D. J. Klein and M. Randic. Innate degree of freedom of a graph. J. Comput. Chem. 8, pages 516{521, 1987.
[31] F. Harary, D. J. Klein, and T. P. Zivkovic. Graphical properties of polyhexes: perfect matching vector and forcing. J.Math. Chem. 6, pages 295{306, 1991.
[32] Z. Che and Z. Chen. Forcing on perfect matchings a survey. MATCH Commun. Math. Comput. Chem. 66, pages 93{136, 2011.
[33] Peter Adams, Mohammad Mahdian, and Ebadollah S. Mahmoodian. On the forced matching numbers of bipartite graphs. Discrete Mathematics, 281(1-3):1{12, 2004.

[34] P. Afshani, H. Hatami, and E. S. Mahmoodian.On the spectrum of the forced matching number of graphs. Australasian J. Combin., 30, pages 147{160, 2004.
[35] Diane Donovan, ES Mahmoodian, Colin Ramsay,and Anne Penfold Street. Defining sets in combinatorics: a survey. Surveys in combinatorics,pages 115{174, 2003.
[36] C^ome Berbain, Olivier Billet, Anne Canteaut,Nicolas Courtois, Henri Gilbert, Louis Goubin, Aline Gouget, Louis Granboulan, Cedric Lauradoux,Marine Minier, Thomas Pornin, and Herve Sibert. Sosemanuk, a Fast Software-Oriented Stream Cipher. In The eSTREAM Finalists, pages 98{118. 2008.
[37] Mohammad Sadegh Nemati Nia and Ali Payandeh. THE NEW HEURISTIC GUESS AND DETERMINE ATTACK ON SNOW 2.0 STREAM CIPHER. IACR Cryptology ePrint Archive,2014:619, 2014.
[38] Xiutao Feng, Jun Liu, Zhaocun Zhou, Chuankun Wu, and Dengguo Feng. A byte-based guess and determine attack on SOSEMANUK. In Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings,pages 146{157, 2010.
[39] Patrik Ekdahl and Thomas Johansson. SNOW-a new stream cipher. In Proceedings of First Open NESSIE Workshop, KU-Leuven, 2000.
[40] Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography. Springer, 2002.