New Fixed Point Attacks on GOST2 Block Cipher

Document Type: ORIGINAL RESEARCH PAPER

Authors

1 Department of Electrical Engineering Sharif University of Technology

2 Department of Electrical Engineering Sharif University of Technology

Abstract

GOST block cipher designed in the 1970s and published in 1989 as the Soviet and Russian standard GOST 28147-89. In order to enhance the security of GOST block cipher after proposing various attacks on it, designers published a modified version of GOST, namely GOST2, in 2015 which has a new key schedule and explicit choice for S-boxes. In this paper, by using three exactly identical portions of GOST2 and fixed point idea, more enhanced fixed point attacks for filtration of wrong keys are presented. More precisely, the focus of the new attacks is on reducing memory complexity while keeping other complexities unchanged as well. The results show a significant reduction in the memory complexity of the attacks, while the time complexity slightly increased in comparison to the previous fixed point attacks. To the best of our knowledge, the lowest memory complexity for an attack on full-round GOST2 block cipher is provided here.

Keywords


[1] Matsui, M.: Linear Cryptoanalysis Method for DES Cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386397. Springer (1994)

[2] Bogdanov, A., Rijmen, V.: Zero-correlation linear cryptanalysis of block ciphers. Accepted to Designs, Codes and Cryptography, 2012

[3] E. Biham, A. Shamir, Differential Cryptanalysis ofDESlikeCryptosystems,JournalofCryptology, Vols.4, no.1, pp. 3-72 (1991)

[4] E. Biham, A. Biryukov, A. Shamir, Cryptanalysis of Skipjack Reduced to 31 Rounds using ImpossibleDifferentials,”inAdvancesinCryptology:EUROCRYPT’99 LNCS 1592, pp. 12-23, Springer Verlag (1999)

[5] W. Diffie and M. Hellman. Exhaustive cryptanalysis of the NBS data encryption standard. Computer, 10(6):7484, (1977)

[6] Canteaut, A., Naya-Plasencia, M., and Vayssire, B. Sieve-in-the-middle: Improved MITM attacks. In CRYPTO (2013), R. Canetti and J. Garay, Eds., vol. 8042 of Lecture Notes in Computer Science, Springer, pp. 222240.

[7] Bogdanov, A., Khovratovich, D., Rechberger, C.: Biclique Cryptanalysis of the Full AES. ASIACRYPT 2011, LNCS, vol. 7073, pp. 344-371.
Springer, Heidelberg (2011)

[8] Ahmadi, Siavash, et al. Low-data complexity biclique cryptanalysis of block ciphers with application to piccolo and hight. IEEE Transactions on Information Forensics and Security 9.10 (2014): 1641-1652 (2014)

[9] Dunkelman, O., Keller, N., and Shamir, A. Improved single-key attacks on 8-round AES-192 and AES-256. In ASIACRYPT (2010), M. Abe, Ed., vol. 6477 of Lecture Notes in Computer Science, Springer, pp. 158176.

[10] Derbez, P., Fouque, P.-A., and Jean, J. Improved key recovery attacks on reduced-round AES in the single-key setting. In EUROCRYPT (2013), T. Johansson and P. Nguyen, Eds., vol. 7881 of Lecture Notes in Computer Science, Springer, pp. 371387.

[11] Russian National Bureau of Standards. Federal Information Processing Standard-Cryptographic Protection - Cryptographic Algorithm. GOST 28147-89, 1989

[12] Dolmatov, Vasily. ”GOST R 34.12-2015: Block Cipher Kuznyechik. Transformation 50 (2016): 10.

[13] Youngdai Ko, Seokhie Hong, Wonil Lee, Sangjin Lee, and Ju-Sung Kang. Related Key Differential Attacks on 27 Rounds of XTEA and FullRound GOST. In Bimal K. Roy and Willi Meier, editors, Fast Software Encryption, 11th International Workshop, FSE 2004, Delhi, India, February5-7,2004,RevisedPapers,volume3017ofLecture Notes in Computer Science, pages 299316. Springer, 2004.

[14] Takanori Isobe: A Single-Key Attack on the Full GOST Block Cipher, In FSE 2011, pp. 290-305, Springer LNCS 6733, 2011

[15] Nicolas Courtois: On Multiple Symmetric Fixed Points in GOST, In Cryptologia, Volume 39, Issue 4, 2015, pp. 322-334.

[16] Haruki Seki and Toshinobu Kaneko: Differential Cryptanalysis of Reduced Rounds of GOST. In SAC 2000, LNCS 2012, pp. 315-323, Springer, 2000

[17] Nicolas Courtois, Micha Misztal: First DifferentialAttackOnFull32-RoundGOST,inICICS’11, pp. 216-227, Springer LNCS 7043, 2011.

[18] Nicolas Courtois, Micha Misztal: Aggregated Differentials and Cryptanalysis of PP-1 and GOST, In CECC 2011, 11th Central European Conference on Cryptology. In Periodica Mathematica Hungarica Vol. 65 (2), 2012, pp. 1126, Springer.

[19] Nicolas T. Courtois, Theodosis Mourouzis, Micha Misztal, Jean-Jacques Quisquater, Guangyan Song: Can GOST Be Made Secure Against Differential Cryptanalysis? In Cryptolo gia, vol. 39, Iss. 2, 2015, pp. 145-156.

[20] Nicolas Courtois, Theodosis Mourouzis, Advanced Truncated Differential Attacks Against GOST Block Cipher and Its Variants, In Computation, Cryptography, and Network Security, Springer, pp. 351-380, 2015.

[21] Nicolas Courtois: Security Evaluation of GOST 28147-89 In View Of International Standardisation, in Cryptologia, Volume 36, Issue 1, pp. 2-13, 2012.

[22] Nicolas T. Courtois: Cryptanalysis of GOST in the Multiple Key Scenario, In postproceedings of CECC 2013, Tatra Mountains Mathematical Publications. Vol. 57, no. 4 (2013), p. 45-63.

[23] Nicolas Courtois: On Multiple Symmetric Fixed Points in GOST, In Cryptologia, Volume 39, Issue 4, 2015, pp. 322-334

[24] Takanori Isobe: A Single-Key Attack on the Full GOST Block Cipher, In FSE 2011, pp. 290-305, Springer LNCS 6733, 2011

[25] Itai Dinur, Orr Dunkelman and Adi Shamir: Improved Attacks on Full GOST, FSE 2012, LNCS 7549, pp. 9-28, 2012

[26] Nicolas Courtois: Algebraic Complexity Reduction and Cryptanalysis of GOST, Monograph study on GOST cipher, 2010-2014, 224 pages

[27] Alekseychuk, A. N., and L. V. Kovalchuk. Towards a Theory of Security Evaluation for GOSTlike Ciphers against Differential and Linear Cryptanalysis. IACR Cryptology ePrint Archive 2011 (2011): 489.

[28] Ashur, Tomer, Achiya Bar-On, and Orr Dunkelman. Cryptanalysis of GOST2. IACR Transactions on Symmetric Cryptology 2017.1 (2017): 203-214.

[29] Ahmadi, Siavash, and Mohammad Reza Aref. Improved Fixed Point Attack on Gost2. 2017 14th International ISC (Iranian Society of Cryptology) Conference on Information Security and Cryptology (ISCISC). IEEE, 2017.

[30] Comer, Douglas. Ubiquitous B-tree. ACM Computing Surveys (CSUR) 11.2 (1979): 121-137.