×

Efficient slide attacks. (English) Zbl 1400.94116

Summary: The slide attack, presented by A. Biryukov and D. Wagner [FSE 1999, Lect. Notes Comput. Sci. 1636, 245–259 (1999; Zbl 0942.94020) and Advanced slide attacks, Proc. Eurocrypt 2000, Lect. Notes Comput. Sci. 1807, 598–606 (2000; Zbl 1082.94506)], has already become a classical tool in cryptanalysis of block ciphers. While it was used to mount practical attacks on a few cryptosystems, its practical applicability is limited, as typically, its time complexity is lower bounded by \(2^n\) (where \(n\) is the block size). There are only a few known scenarios in which the slide attack performs better than the \(2^n\) bound. In this paper, we concentrate on efficient slide attacks, whose time complexity is less than \(2^n\). We present a number of new attacks that apply in scenarios in which previously known slide attacks are either inapplicable, or require at least \(2^n\) operations. In particular, we present the first known slide attack on a Feistel construction with a 3-round self-similarity, and an attack with practical time complexity of \(2^{40}\) on a 128-bit key variant of the GOST block cipher with unknown S-boxes. The best previously known attack on the same variant, with known S-boxes (by Courtois), has time complexity of \(2^{91}\).

MSC:

94A60 Cryptography

Software:

Square
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] W. Aerts, E. Biham, D.D. Moitie, E.D. Mulder, O. Dunkelman, S. Indesteege, N. Keller, B. Preneel, G.A.E. Vandenbosch, I. Verbauwhede, A practical attack on KeeLoq. J. Cryptol. 25(1), 136-157 (2012) · Zbl 1279.94049
[2] M.V. Anand, E.E. Targhi, G.N. Tabia, D. Unruh, Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation, in T. Takagi (ed.) Post-Quantum Cryptography—7th International Workshop, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9606 (Springer, Berlin, 2016), pp. 44-63 · Zbl 1405.81023
[3] Biham, E, New types of cryptanalytic attacks using related keys, J. Cryptol., 7, 229-246, (1994) · Zbl 0812.94012 · doi:10.1007/BF00203965
[4] E. Biham, O. Dunkelman, N. Keller, Improved slide attacks, in A. Biryukov (ed.) Fast Software Encryption, 14th International Workshop, FSE 2007, Luxembourg, Luxembourg, March 26-28, 2007, Revised Selected Papers. Lecture Notes in Computer Science, vol. 4593 (Springer, Berlin, 2007), pp. 153-166 · Zbl 1186.94425
[5] E. Biham, A. Shamir, Differential Cryptanalysis of the Data Encryption Standard (Springer, Berlin, 1993) · Zbl 0778.94005
[6] A. Biryukov, C. Bouillaguet, D. Khovratovich, Cryptographic schemes based on the ASASA structure: black-box, white-box, and public-key (extended abstract), in P. Sarkar, T. Iwata (eds.) Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I. Lecture Notes in Computer Science, vol. 8873 (Springer, Berlin, 2014), pp. 63-84 · Zbl 1306.94030
[7] A. Biryukov, D. Khovratovich, L. Perrin, Multiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs. IACR Trans. Symmetric Cryptol. 2016(2), 226-247 (2016). http://tosc.iacr.org/index.php/ToSC/article/view/572
[8] A. Biryukov, L. Perrin, On reverse-engineering S-boxes with hidden design criteria or structure, in R. Gennaro, M. Robshaw, (eds.) Advances in Cryptology—CRYPTO 2015—35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9215 (Springer, Berlin, 2015), pp. 116-140 · Zbl 1347.94019
[9] Biryukov, A; Shamir, A, Structural cryptanalysis of SASAS, J. Cryptol., 23, 505-518, (2010) · Zbl 1201.94076 · doi:10.1007/s00145-010-9062-1
[10] A. Biryukov, D. Wagner, Slide attacks. in L.R. Knudsen, (ed.) Fast Software Encryption, 6th International Workshop, FSE ’99, Rome, Italy, March 24-26, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1636 (Springer, Berlin, 1999), pp. 245-259 · Zbl 0942.94020
[11] A. Biryukov, D. Wagner, Advanced slide attacks, in B. Preneel, (ed.)Advances in Cryptology—EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding. Lecture Notes in Computer Science, vol. 1807 (Springer, Berlin, 2000), pp. 589-606 · Zbl 1082.94506
[12] N. Courtois, Algebraic complexity reduction and cryptanalysis of GOST. IACR Cryptology ePrint Archive 2011, 626 (2011). http://eprint.iacr.org/2011/626
[13] N.T. Courtois, An improved differential attack on full GOST. IACR Cryptology ePrint Archive 2012, 138 (2012). http://eprint.iacr.org/2012/138 · Zbl 1405.94054
[14] Courtois, NT, Cryptanalysis of two GOST variants with 128-bit keys, Cryptologia, 38, 348-361, (2014) · doi:10.1080/01611194.2014.915706
[15] N.T. Courtois, An improved differential attack on full GOST, in P.Y.A. Ryan, D. Naccache, J. Quisquater, (eds.) The New Codebreakers—Essays Dedicated to David Kahn on the Occasion of His 85th Birthday. Lecture Notes in Computer Science, vol. 9100 (Springer, Berlin, 2016), pp. 282-303 · Zbl 1291.94102
[16] J. Daemen, L.R. Knudsen, V. Rijmen, The block cipher square, in E. Biham, (ed.) Fast Software Encryption, 4th International Workshop, FSE ’97, Haifa, Israel, January 20-22, 1997, Proceedings. Lecture Notes in Computer Science, vol. 1267 (Springer, Berlin, 1997), pp. 149-165 · Zbl 1385.94025
[17] J. Daemen, V. Rijmen, The design of Rijndael: AES—the advanced encryption standard. Information Security and Cryptography (Springer, Berlin, 2002) · Zbl 1065.94005
[18] I. Dinur, O. Dunkelman, N. Keller, A. Shamir, Reflections on slide with a twist attacks. Des.Codes Cryptogr. 77(2-3), 633-651 (2015) · Zbl 1356.94055
[19] I. Dinur, O. Dunkelman, A. Shamir, Improved attacks on full GOST, in A. Canteaut, (ed.) Fast Software Encryption—19th International Workshop, FSE 2012, Washington, DC, USA, March 19-21, 2012. Revised Selected Papers. Lecture Notes in Computer Science, vol. 7549 (Springer, Berlin, 2012), pp. 9-28 · Zbl 1282.94040
[20] O. Dunkelman, N. Keller, Reverse Engineering the Difference Distribution Table (2016), work in progress
[21] Dunkelman, O; Keller, N; Shamir, A, Slidex attacks on the even-mansour encryption scheme, J. Cryptol., 28, 1-28, (2015) · Zbl 1356.94056 · doi:10.1007/s00145-013-9164-7
[22] Even, S; Mansour, Y, A construction of a cipher from a single pseudorandom permutation, J. Cryptol., 10, 151-162, (1997) · Zbl 1053.94552 · doi:10.1007/s001459900025
[23] P. Flajolet, R. Sedgewick, Analytic Combinatorics (Cambridge University Press, Cambridge, 2009). http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=9780521898065 · Zbl 1165.05001
[24] R.W. Floyd, Nondeterministic Algorithms. J. ACM 14(4), 636-644 (1967) · Zbl 0153.47006
[25] S. Furuya, Slide attacks with a known-plaintext cryptanalysis, in K. Kim, (ed.) Information Security and Cryptology—ICISC 2001, 4th International Conference Seoul, Korea, December 6-7, 2001, Proceedings. Lecture Notes in Computer Science, vol. 2288 (Springer, Berlin, 2001), pp. 214-225 · Zbl 0994.68594
[26] V. Goncharov, On the distribution of cycles in permutations. Doklady Akedmii Nauk SSSR 35, 299-301 (1942)
[27] V. Goncharov, Some facts from combinatorics. Izvestia Academii Nauk SSSR 8 , 3-48 (1944), ser. Mat.
[28] M. Gorski, S. Lucks, T. Peyrin, Slide attacks on a class of hash functions, in J. Pieprzyk, (ed.) Advances in Cryptology—ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7-11, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5350 (Springer, Berlin, 2008), pp. 143-160 · Zbl 1206.94067
[29] Government Committee of the USSR for Standards, Gosudarstvennei Standard 28147-89: Cryptographic Protection for Data Processing Systems. Tech. rep. (1989)
[30] E.K. Grossman, B. Tucherman, Analysis of a weakened Feistel-like Cipher, in Proceedings of International Conference on Communications (1978), pp. 46.3.1-46.3.5
[31] Isobe, T, A single-key attack on the full GOST block cipher, J. Cryptol., 26, 172-189, (2013) · Zbl 1291.94102 · doi:10.1007/s00145-012-9118-5
[32] T. Isobe, K. Shibutani, Generic key recovery attack on Feistel scheme, in K. Sako, P. Sarkar, (eds.) Advances in Cryptology—ASIACRYPT 2013—19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part I. Lecture Notes in Computer Science, vol. 8269 (Springer, Berlin, 2013), pp. 464-485 · Zbl 1327.94052
[33] J. Jean, I. Nikolic, T. Peyrin, L. Wang, S. Wu, Security analysis of PRINCE, in S. Moriai (ed.) Fast Software Encryption—20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8424 (Springer, Berlin, 2013), pp. 92-111 · Zbl 1321.94066
[34] M. Kaplan, G. Leurent, A. Leverrier, M. Naya-Plasencia, Breaking symmetric cryptosystems using quantum period finding, in M. Robshaw, J. Katz, (eds.) Advances in Cryptology—CRYPTO 2016—36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9815 (Springer, Berlin, 2016), pp. 207-237 · Zbl 1391.94766
[35] O. Kara, Reflection attacks on product ciphers. IACR Cryptology ePrint Archive 2007, 43 (2007). http://eprint.iacr.org/2007/043
[36] O. Kara, Reflection cryptanalysis of some ciphers, in D.R. Chowdhury, V. Rijmen, A. Das, (eds.) Progress in Cryptology—INDOCRYPT 2008, 9th International Conference on Cryptology in India, Kharagpur, India, December 14-17, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5365 (Springer, Berlin, 2008), pp. 294-307 · Zbl 1203.94106
[37] Y. Ko, S. Hong, W. Lee, S. Lee, J. Kang, Related key differential attacks on 27 rounds of XTEA and full-round GOST, in B.K. Roy, W. Meier, (eds.) Fast Software Encryption, 11th International Workshop, FSE 2004, Delhi, India, February 5-7, 2004, Revised Papers. Lecture Notes in Computer Science, vol. 3017 (Springer, Berlin, 2004), pp. 299-316 · Zbl 1079.68548
[38] M. Matsui, Linear cryptanalysis method for DES cipher, in T. Helleseth, (ed.) Advances in Cryptology—EUROCRYPT ’93, Workshop on the Theory and Application of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings. Lecture Notes in Computer Science, vol. 765 (Springer, Berlin, 1993), pp. 386-397
[39] B. Minaud, P. Derbez, P. Fouque, P. Karpman, Key-recovery attacks on ASASA, in T. Iwata, J.H Cheon, (eds.) Advances in Cryptology—ASIACRYPT 2015—21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29-December 3, 2015, Proceedings, Part II. Lecture Notes in Computer Science, vol. 9453 (Springer, Berlin, 2015), pp. 3-27
[40] National Bureau of Standards: Data Encryption Standard. NBS Federal Information Processing Standard (FIPS) 46 (1977)
[41] M.J Saarinen, A chosen key attack against the secret S-boxes of GOST (1998). http://citeseer.ist.psu.edu/saarinen98chosen.html
[42] B. Schneier, Applied Cryptography 2nd edn (Wiley, New York, 1996) · Zbl 0812.94012
[43] Simon, DR, On the power of quantum computation, SIAM J. Comput., 26, 1474-1483, (1997) · Zbl 0883.03024 · doi:10.1137/S0097539796298637
[44] T. Tiessen, L.R. Knudsen, S. Kölbl, M.M. Lauridsen, Security of the AES with a secret S-Box. in G. Leander, (ed.)Fast Software Encryption—22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9054 (Springer, Berlin, 2015), pp. 175-189 · Zbl 1367.94352
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.