Previous Articles     Next Articles

Straightforward Guess and Determine Analysis Based on Genetic Algorithm

CAO Chunping1, CEN Zhe1, FENG Xiutao2, WANG Zhangyi3, ZHU Yamin4   

  1. 1. Department of Computer Science and Technology, University of Shanghai for Science and Technology, Shanghai 200093, China;
    2. Department of Computer Science and Technology, University of Shanghai for Science and Technology, Shanghai 200093, China;
    3. School of Cyber Science and Engineering, Wuhan University, Wuhan 430072, China;
    4. School of Science, Xi'an Technological University, Xi'an 710021, China
  • Received:2021-02-11 Online:2022-10-25 Published:2022-10-12
  • Supported by:
    This research was supported by the National Key Research and Development Project under Grant No.2018YFA0704705,2016YFB0800401 and the National Natural Science Foundation under Grant No.61972297.

CAO Chunping, CEN Zhe, FENG Xiutao, WANG Zhangyi, ZHU Yamin. Straightforward Guess and Determine Analysis Based on Genetic Algorithm[J]. Journal of Systems Science and Complexity, 2022, 35(5): 1988-2003.

With the development of artificial intelligence,the genetic algorithm has been widely used in many fields.In cryptography,the authors find it is natural to code an individual and design its fitness in a genetic algorithm for a straightforward guess and determine analysis (SGDA,in short).Based on this observation,the authors propose an SGDA based on genetic algorithm.Comparing it with the other three SGDAs based on exhaustive search,MILP method and CPP method respectively,the authors illustrate its effectiveness by three stream ciphers:Small scale SNOW 2.0,medium scale Enocoro-128v2 and large scale Trivium.The results show our method is significantly superior to them,especially for Trivium,the method can find a solution of 165 variables in less than one hour,while the other three methods are not applicable due to its enormous search space of size 2619.37.As far as we know,it is a best solution in an SGDA for Trivium so far.
[1] Jong D and Alan K, Analysis of the behavior of a class of genetic adaptive systems, Department of Computer and Communication Sciences, University of Michigan, Ann Arbor, USA, 1975.
[2] Dorigo M, Maniezzo V, and Colorni A, Ant system:Optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 1996, 26(1):29-41.
[3] Michael S, Guido M, and Alfons K, Heuristic and randomized optimization for the join ordering problem, The VLDB Journal, 1997, 6(3):191-208.
[4] Spillman R, Cryptanalysis of knapsack ciphers using genetic algorithms, Cryptologia, 1993, 17(4):367-377.
[5] Feng T L and Cheng Y K, A genetic algorithm for ciphertext-only attack in cryptanalysis, IEEE International Conference on Systems, Man and Cybernetics, 1995, 1:650-654.
[6] Jong D and Alan K, Optimization heuristics for cryptology, Queensland University of Technology, Queensland, 1998.
[7] Glover F and Laguna M, Tabu Search, Kluwer Academic Publishers, Boston, 1997.
[8] Castro J C H, Sierra J M, Isasi O, et al., Genetic cryptoanalysis of two rounds TEA, International Conference on Computational Science, 2002, 1024-1031.
[9] Yang F, Song J, and Zhang H G, Quantitative cryptanalysis of six-round DES using evolutionary algorithms, International Symposium on Intelligence Computation and Applications, 2008, 134-141.
[10] Piyush M, Rajesh P, Rajesh S, et al., Application of genetic algorithm in cryptanalysis of monoalphabetic substitution cipher, International Conference on Computing, Communication and Automation, 2017, 400-405.
[11] Zhang H G, Feng X T, Qin Z Q, et al., Evolutionary cryptosystems and evolutionary design for DES, Journal of China Institute Communication, 2002, 23:57-64.
[12] Yang M, Meng Q S, and Zhang H G, The evolutionary design of trace form bent functions in cryptography, International Journal of Information and Computer Security, 2009, 3:47-59.
[13] Wang Y H, Wang H Y, Guan A H, et al., Evolutionary design of random number generator, First IITA International Joint Conference on Artificial Intelligence, 2009, 256-259.
[14] Siegenthaler T, Decrypting a class of stream ciphers using ciphertext only, IEEE Transactions on Computers, 1985, 34(1):81-85.
[15] Golić J D, Cryptanalysis of alleged A5 stream cipher, International Conference on the Theory and Applications of Cryptographic Techniques, 1997, 239-255.
[16] Knudsen L R, Meier W, Preneel B, et al., Analysis methods for (alleged) RC4, International Conference on the Theory and Application of Cryptology and Information Security, 1998, 18-22.
[17] Hawkes P and Rose G G, Analysis methods for (alleged) RC4, Exploiting Multiples of the Connection Polynomial in Word-Oriented Stream Ciphers, 2000, 303-316.
[18] Ahmadi H and Eghlidos T, Heuristic guess-and-determine attacks on stream ciphers, IET Information Security, 2009, 3(2):66-73.
[19] Bouillaguet C, Derbez P, and Fouque P A, Automatic search of attacks on round-reduced AES and applications, CRYPTO 2011, 2011, 169-187.
[20] Huang Z Y and Lin D D, Attacking bivium and trivium with the characteristic set method, Africacrypt 2011, 2011, 77-91.
[21] Feng X T, Liu J, Zhou Z C, et al., A Byte-based guess and determine attack on SOSEMANUK, ASIACRYPT 2010, 2010, 146-157.
[22] Feng X T, Shi Z Q, Wu C K, et al., on guess and determine analysis of rabbit, International Journal of Foundations of Computer Science, 2011, 22(6):1283-1296.
[23] Shi Z Q, Feng X T, Feng D G, et al., A real-time key recovery attack on the lightweight stream cipher A2U2, International Conference on Cryptology and Network Security, 2012, 12-22.
[24] Feng X T and Zhang F, A realtime key recovery attack on the authenticated cipher FASER128,IACR Cryptology ePrint Archive, 2014, https://eprint.iacr.org/2014/258.
[25] Feng X T and Zhang F, Cryptanalysis on the authenticated cipher Sablier, International Conference on Network and System Security, 2015, 198-208.
[26] Feng X T, Zhang F, and Wang H, A practical forgery and state recovery attack on the authenticated cipher PANDA-s, IACR Cryptology ePrint Archive, 2014, https://eprint. iacr.org/2014/325.
[27] Jiao L, Li Y Q, and Hao Y L, A guess-and-determine attack on SNOW-V stream cipher, The Computer Journal, 2020, 63(12):1789-1812.
[28] Pavlenko A, Buzdalov M, and Ulyantsev V, Fitness comparison by statistical testing in construction of SAT-based guess-and-determine cryptographic attacks, GECCO 2019, 2019, 312-320.
[29] Cen Z, Feng X T, Wang Z Y, et al., Minimizing deduction system and its application, arxiv, 2020, https://arxiv.org/abs/2006.05833.
[30] Ekdahl P and Johansson T, A new version of the stream cipher SNOW, International Workshop on Selected Areas in Cryptography, 2002, 47-61.
[31] Watanabe D, Okamoto K, and Kaneko T, A hardware-oriented light weight pseudo-random number generator Enocoro-128v2, SCIS 2010, 2010, 3D1-3.
[32] Canniére H D, Trivium:A stream cipher construction inspired by block cipher design principles, International Conference on Information Security, 2006, 171-186.
[33] Canniére C D and Preneel B, New Stream Cipher Design, Springer, Berlin, Heidelberg, 2008.
[34] Eén N and Sörensson N, An extensible sat-solver, International Conference on Theory and Applications of Satisfiability Testing, Springer, 2003, 502-518.
[35] Clegg M, Edmonds J, Impagliazzo R, Using the Groebner basis algorithm to find proofs of unsatisfiability, Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996, 174-183.
[36] Chai F J, Gao X S, and Yuan C M, A characteristic set method for solving boolean equations and applications in cryptanalysis of stream ciphers, Journal of Systems Science&Complexity, 2008, 21(2):191-208.
[37] International Standard Organization, ISO/IEC 180334:Information technology-Security techniques-Encryption algorithms-Part 4:Stream ciphers, 2011.
[38] International Standard Organization, ISO/IEC 291923:Information technology-Security techniques-Encryption algorithms-Part 3:Stream ciphers, 2012.
[1] Xin Chao ZHAO. A GREEDY GENETIC ALGORITHM FOR UNCONSTRAINED GLOBAL OPTIMIZATION [J]. Journal of Systems Science and Complexity, 2005, 18(1): 102-110.
[2] S.Suganuma;V.N.Huynh;Y.Nakamori;S.Y.Wang;K.K.Lai. A FRAMEWORK OF FUZZY LANDSCAOE THEORY WITH AN APPLICATION TO ALLIANCE ANALYSIS [J]. Journal of Systems Science and Complexity, 2003, 16(1): 1-012.
Viewed
Full text


Abstract