×

A single-key attack on the full GOST block cipher. (English) Zbl 1307.94059

Joux, Antoine (ed.), Fast software encryption. 18th international workshop, FSE 2011, Lyngby, Denmark, February 13–16, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-21701-2/pbk). Lecture Notes in Computer Science 6733, 290-305 (2011).
Summary: The GOST block cipher is the Russian encryption standard published in 1989. In spite of considerable cryptanalytic efforts over the past 20 years, a key recovery attack on the full GOST block cipher without any key conditions (e.g., weak keys and related keys) has not been published yet. In this paper, we show a first single-key attack, which works for all key classes, on the full GOST block cipher. To construct the attack, we develop a new attack framework called reflection-meet-in-the-middle attack. This approach combines techniques of the reflection attack and the meet-in-the-middle attack. We apply it to the GOST block cipher with further novel techniques which are the effective MITM techniques using equivalent keys on short rounds. As a result, a key can be recovered with \(2^{225}\) computations and \(2^{32}\) known plaintexts.
For the entire collection see [Zbl 1217.68011].

MSC:

94A60 Cryptography
Full Text: DOI

References:

[1] Aoki, K., Sasaki, Y.: Preimage Attacks on One-Block MD4, 63-Step MD5 and More. In: Avanzi, R.M., Keliher, L., Sica, F. (eds.) SAC 2008. LNCS, vol. 5381, pp. 103–119. Springer, Heidelberg (2009) · Zbl 1256.94040 · doi:10.1007/978-3-642-04159-4_7
[2] Biham, E., Dunkelman, O., Keller, N.: Improved Slide Attacks. In: Biryukov, A. (ed.) [3], pp. 153–166 · Zbl 1186.94425 · doi:10.1007/978-3-540-74619-5_10
[3] Biryukov, A. (ed.): FSE 2007. LNCS, vol. 4593. Springer, Heidelberg (2007) · Zbl 1143.68002
[4] Biryukov, A., Wagner, D.: Slide attacks. In: Knudsen, L.R. (ed.) FSE 1999. LNCS, vol. 1636, pp. 245–259. Springer, Heidelberg (1999) · Zbl 0942.94020 · doi:10.1007/3-540-48519-8_18
[5] Biryukov, A., Wagner, D.: Advanced Slide Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 589–606. Springer, Heidelberg (2000) · Zbl 1082.94506 · doi:10.1007/3-540-45539-6_41
[6] Bogdanov, A.A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: An Ultra-Lightweight Block Cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007) · Zbl 1142.94334 · doi:10.1007/978-3-540-74735-2_31
[7] Bogdanov, A., Rechberger, C.: A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) SAC 2010. LNCS, vol. 6544, pp. 229–240. Springer, Heidelberg (2011) · Zbl 1292.94032 · doi:10.1007/978-3-642-19574-7_16
[8] De Cannière, C., Dunkelman, O., Knežević, M.: KATAN and KTANTAN – A Family of Small and Efficient Hardware-Oriented Block Ciphers. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol. 5747, pp. 272–288. Springer, Heidelberg (2009) · Zbl 1290.94060 · doi:10.1007/978-3-642-04138-9_20
[9] Chaum, D., Evertse, J.-H.: Cryptanalysis of DES with a Reduced Number of Rounds Sequences of Linear Factors in Block Cipher. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 192–211. Springer, Heidelberg (1986) · Zbl 0592.94009 · doi:10.1007/3-540-39799-X_16
[10] Demirci, H., Selçuk, A.A.: A Meet-in-the-Middle Attack on 8-Round AES. In: Nyberg, K. (ed.) [23], pp. 116–126 · Zbl 1154.68391 · doi:10.1007/978-3-540-71039-4_7
[11] Demirci, H., Taşkın, \.I., Çoban, M., Baysal, A.: Improved Meet-in-the-Middle Attacks on AES. In: Roy, B.K., Sendrier, N. (eds.) INDOCRYPT 2009. LNCS, vol. 5922, pp. 144–156. Springer, Heidelberg (2009) · Zbl 1273.94345 · doi:10.1007/978-3-642-10628-6_10
[12] Diffie, W., Hellman, M.E.: Exhaustive Cryptanalysis of the NBS Data Encryption Standard. Computer 10, 74–84 (1977) · doi:10.1109/C-M.1977.217750
[13] Dunkelman, O., Keller, N., Shamir, A.: Improved Single-Key Attacks on 8-Round AES-192 and AES-256. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 158–176. Springer, Heidelberg (2010) · Zbl 1253.94045 · doi:10.1007/978-3-642-17373-8_10
[14] Dunkelman, O., Sekar, G., Preneel, B.: Improved Meet-in-the-Middle Attacks on Reduced-Round DES. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol. 4859, pp. 86–100. Springer, Heidelberg (2007) · Zbl 1153.94371 · doi:10.1007/978-3-540-77026-8_8
[15] Fleischmann, E., Gorski, M., Hüehne, J., Lucks, S.: Key Recovery Attack on full GOST. Block Cipher with Negligible Time and Memory. In: Western European Workshop on Research in Cryptology (WEWoRC). LNCS, vol. 6429. Springer, Heidelberg (2009)
[16] Indesteege, S., Keller, N., Dunkelman, O., Biham, E., Preneel, B.: A Practical Attack on KeeLoq. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 1–18. Springer, Heidelberg (2008) · Zbl 1149.94322 · doi:10.1007/978-3-540-78967-3_1
[17] Kara, O.: Reflection Cryptanalysis of Some Ciphers. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 294–307. Springer, Heidelberg (2008) · Zbl 1203.94106 · doi:10.1007/978-3-540-89754-5_23
[18] Kara, O., Manap, C.: A New Class of Weak Keys for Blowfish. In: Biryukov, A. (ed.) [3], pp. 167–180 · Zbl 1186.94452 · doi:10.1007/978-3-540-74619-5_11
[19] Ko, Y., Hong, S.H., Lee, W.I., Lee, S.-J., Kang, J.-S.: Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST. In: Roy, B.K., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 299–316. Springer, Heidelberg (2004) · Zbl 1079.68548 · doi:10.1007/978-3-540-25937-4_19
[20] Mendel, F., Pramstaller, N., Rechberger, C.: A (Second) Preimage Attack on the GOST Hash Function. In: Nyberg, K. (ed.) [23], pp. 224–234. · Zbl 1154.68406 · doi:10.1007/978-3-540-71039-4_14
[21] Mendel, F., Pramstaller, N., Rechberger, C., Kontak, M., Szmidt, J.: Cryptanalysis of the GOST Hash Function. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 162–178. Springer, Heidelberg (2008) · Zbl 1183.94042 · doi:10.1007/978-3-540-85174-5_10
[22] National Soviet Bureau of Standards. Information Processing System - Cryptographic Protection - Cryptographic Algorithm GOST 28147-89 (1989)
[23] Nyberg, K. (ed.): FSE 2008. LNCS, vol. 5086. Springer, Heidelberg (2008) · Zbl 1144.68007
[24] Poschmann, A., Ling, S., Wang, H.: 256 Bit Standardized Crypto for 650 GE – GOST Revisited. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 219–233. Springer, Heidelberg (2010) · Zbl 1297.94098 · doi:10.1007/978-3-642-15031-9_15
[25] Sasaki, Y., Aoki, K.: Finding Preimages in Full MD5 Faster Than Exhaustive Search. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 134–152. Springer, Heidelberg (2009) · Zbl 1239.94064 · doi:10.1007/978-3-642-01001-9_8
[26] Schneier, B.: Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish). In: Anderson, R.J. (ed.) FSE 1993. LNCS, vol. 809, pp. 191–204. Springer, Heidelberg (1994) · Zbl 0943.94523 · doi:10.1007/3-540-58108-1_24
[27] Schneier, B.: Applied Cryptography, 2nd edn. Protocols, Algorithms, and Source Code in C. John Wiley & Sons, Inc., New York (1995) · Zbl 0789.94001
[28] Seki, H., Kaneko, T.: Differential Cryptanalysis of Reduced Rounds of GOST. In: Stinson, D.R., Tavares, S.E. (eds.) SAC 2000. LNCS, vol. 2012, pp. 315–323. Springer, Heidelberg (2001) · Zbl 0981.94503 · doi:10.1007/3-540-44983-3_23
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.