Abstract
The GOST hash function, defined in GOST R 34.11-2012, was selected as the new Russian standard on August 7, 2012. It is designed to replace the old Russian standard GOST R 34.11-94. The GOST hash function is an AES-based primitive and is considered as an asymmetric reply to the SHA-3. It is an iterated hash function based on the Merkle-Damgård strengthening design. In addition to the common iterated structure, it defines a checksum computed over all input message blocks. The checksum is then needed for the final hash value computation. In this paper, we show the first cryptanalytic attacks on the round-reduced GOST hash function. Using the combination of Super-Sbox technique and multi-collision, we present collision attacks on 5-round of the GOST-256 and GOST-512 hash function, respectively. The complexity of these collision attacks are both (\(2^{122},2^{64}\)) (in time and memory). Furthermore, we combine the guess-and-determine MitM attack with multi-collision to construct a preimage attack on 6-round GOST-512 hash function. The complexity of the preimage attack is about \(2^{505}\) and the memory requirements is about \(2^{64}\). As far as we know, these are the first attacks on the round-reduced GOST hash function.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
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)
Aoki, K., Sasaki, Y.: Meet-in-the-Middle Preimage Attacks Against Reduced SHA-0 and SHA-1. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 70–89. Springer, Heidelberg (2009)
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: The keccak sha-3 submission. Submission to NIST (Round 3) (2011).
Gauravaram, P., Kelsey, J., Knudsen, L.R., Thomsen, S.S.: On hash functions using checksums. Int. J. Inf. Sec. 9(2), 137–151 (2010)
Gilbert, H., Peyrin, T.: Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 365–383. Springer, Heidelberg (2010)
Grebnev, S, Dmukh, A, Dygin, D., Matyukhin, D., Rudskoy, V, Shishkin, V.: Asymmetric reply to sha-3: Russian hash function draft standard. http://www.tc26.ru/CTCrypt/2012/abstract/streebog_corr.pdf/
Joux, A.: Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004)
Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schläffer, M.: Rebound Distinguishers: Results on the Full Whirlpool Compression Function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 126–143. Springer, Heidelberg (2009)
Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schläffer, M.: The rebound attack and subspace distinguishers: application to whirlpool. IACR Cryptology ePrint Archive 2010, 198 (2010)
Matusiewicz, K., Naya-Plasencia, M., Nikolić, I., Sasaki, Y., Schläffer, M.: Rebound Attack on the Full Lane Compression Function. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 106–125. Springer, Heidelberg (2009)
Mendel, F., Peyrin, T., Rechberger, C., Schläffer, M.: Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES Block Cipher. In: Jacobson Jr., M.J., Rijmen, V., Safavi-Naini, R. (eds.) SAC 2009. LNCS, vol. 5867, pp. 16–35. Springer, Heidelberg (2009)
Mendel, F., Pramstaller, N., Rechberger, C.: A (Second) Preimage Attack on the GOST Hash Function. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 224–234. Springer, Heidelberg (2008)
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)
Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 260–276. Springer, Heidelberg (2009)
National Institute of Standards and Technology. Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family. Federal Register 27(212), 62212–62220, November 2007. http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf. 17 October 2008
Pollard, J.M.: Monte carlo methods for index computation (mod p). Math. Comput. 32(143), 918–924 (1978)
Information Protection and Special Communications of the Federal Security Service of the Russian Federation. Gost r 34.11.2012 information technology cryptographic date security hash-functions (in english). http://tk26.ru/en/GOSTR3411-2012/GOST_R_34_11-2012_eng.pdf/
Information Protection and Special Communications of the Federal Security Service of the Russian Federation. Gost r 34.11.94 information technology cryptographic date security hash-functions (in russian)
Quisquater, J.-J., Delescaille, J.-P.: How Easy Is Collision Search. New Results and Applications to DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 408–413. Springer, Heidelberg (1990)
Sasaki, Y., Wang, L., Wu, S., Wu, W.: Investigating Fundamental Security Requirements on Whirlpool: Improved Preimage and Collision Attacks. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 562–579. Springer, Heidelberg (2012)
Wang, X., Yin, Y.L., Yu, H.: Finding Collisions in the Full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
Wang, X., Yu, H., Yin, Y.L.: Efficient Collision Search Attacks on SHA-0. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 1–16. Springer, Heidelberg (2005)
Wu, S., Feng, D., Wu, W., Guo, J., Dong, L., Zou, J.: (Pseudo) Preimage attack on round-reduced Grøstl hash function and others. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 127–145. Springer, Heidelberg (2012)
Zou, J., Wu, W., Wu, S., Dong, L.: Improved (pseudo) preimage attack and second preimage attack on round-reduced grostl. IACR Cryptology ePrint Archive 686 (2012).
Acknowledgments
We would like to thank anonymous referees for their helpful comments and suggestions. This work is supported by the National Basic Research Program of China 973 Program (2013CB338002), and the National Natural Science Foundation of China (61272476, 61232009).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Zou, J., Wu, W., Wu, S. (2014). Cryptanalysis of the Round-Reduced GOST Hash Function. In: Lin, D., Xu, S., Yung, M. (eds) Information Security and Cryptology. Inscrypt 2013. Lecture Notes in Computer Science(), vol 8567. Springer, Cham. https://doi.org/10.1007/978-3-319-12087-4_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-12087-4_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12086-7
Online ISBN: 978-3-319-12087-4
eBook Packages: Computer ScienceComputer Science (R0)