ROTATIONAL CRYPTANALYSIS OF GOST WITH IDENTICAL S-BOXES

Zajac, Pavol; Ondroš, Michal

doi:10.2478/tmmp-2013-0032

Abstract

Rotational cryptanalysis was introduced by Khovratovich and Nikoli ´c as a tool to analyse ARX-type cipher designs. GOST 28147-89 is a former Soviet Union cipher standard based on a Feistel construction with 32 rounds. Each round function adds the round key modulo 2³², transforms the result with 4-to-4 bit S-boxes, and rotates the output. We apply the rotational cryptanalysis to a version of GOST using eight identical S-boxes, such as GOST-PS. We show the existence of (practical) rotational distinguisher in related key model for full GOST. Furthermore, there is a set of weak keys (rotationally symmetric keys) that enables rotational attacks in single-key model as well. Finally, we show a simple attack on the last round that uses the rotational distinguisher to reduce the complexity of the full GOST to 208 bits.

References

[1] COURTOIS, N. T: Security evaluation of GOST 28147-89 in view of international standardisation, Cryptologia 36 (2012) 2-13.
Search in Google Scholar
[2] COURTOIS, N. T.-MISZTAL, M.: Differential cryptanalysis of GOST, Cryptology ePrint Archive, Report 2011/312, 2011, http://eprint.iacr.org/.
Search in Google Scholar
[3] COURTOIS, N. T.: Algebraic Complexity reduction and cryptanalysis of GOST, Cryptology ePrint Archive, Report 2011/626, 2011, http://eprint.iacr.org/2011/626.
Search in Google Scholar
[4] DINUR, I.-DUNKELMAN, O.-SHAMIR, A.: Improved attacks on full GOST, in: Fast Software Encryption (A. Canteaut, ed.), LNCS Vol. 7549, Springer, Heidelberg, 2012, pp. 9-28.
Search in Google Scholar
[5] DOLMATOV, V.: GOST 28147-89: Encryption, decryption, and message authenticationcode (MAC) algorithms, RFC 5830 (Informational), March 2010.10.17487/rfc5830
Search in Google Scholar
[6] ISOBE, T.: A single-key attack on the full GOST block cipher, in: Fast Software Encryption (A. Joux, ed.), LNCS Vol. 6733, Springer, Heidelberg, 2011, pp. 290-305.
Search in Google Scholar
[7] KHOVRATOVICH, D.-NIKOLI´C, I.: Rotational cryptanalysis of ARX, in: Fast Software Encryption 2010 (S. Hong, T. Iwata, eds.) LNCS Vol. 6147, Springer, Heidelberg, 2010, pp. 333-346.
Search in Google Scholar
[8] KHOVRATOVICH, D.-NIKOLI´C, I.-RECHBERGER, C.: Rotational rebound attackson reduced skein, in: Adv. in Cryptology-ASIACRYPT 2010 (M. Abe, ed.), LNCS 6477 Springer, Heidelberg 2010, pp. 1-19.10.1007/978-3-642-17373-8_1
Search in Google Scholar
[9] ONDROˇS, M.: ARX Ciphers, in: Master’s Thesis, Slovak University of Technology in Bratislava, 2013. (In Slovak)
Search in Google Scholar
[10] POPOV, V.-KUREPKIN, I. -LEONTIEV, S.: Additional Cryptographic Algorithmsfor Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, andGOST R 34.11-94 Algorithms, RFC 4357 (Informational), January 2006.10.17487/rfc4357
Search in Google Scholar
[11] POSCHMANN, A.-LING, S.-WANG, H.: 256 bit standardized crypto for 650 ge-gostrevisited, Cryptographic Hardware and Embedded Systems, CHES 2010 (S. Mangard, F.-X. Standaert, eds.) LNCS 6225, Springer, Heidelberg, 2010, pp. 219-233.10.1007/978-3-642-15031-9_15
Search in Google Scholar
[12] GOSUDARSTVENNYI STANDART SOJUZA SSR: Sistemy obrabotki informacii. Zashchita kryptograficheskaya, Algoritm kriptograficheskogo preobrazovaniya. GosudarstvennyiStandart Soyuza SSR, GOST: 28147-89, IPK Izdatelstvo standartov, Moskva, 1989.
Search in Google Scholar
[13] ZAJAC, P.-ˇCAGALA, R.: Local reduction and the algebraic cryptanalysis of the blockcipher GOST, Periodica Mathematica Hungarica 65 (2012), 239-255.10.1007/s10998-012-6376-9
Search in Google Scholar
[14] ZANECHAL, M.: An algebraic approach to fix points of GOST-algorithm, Mathematica Slovaca 51 (2001), 583-591.
Search in Google Scholar

ROTATIONAL CRYPTANALYSIS OF GOST WITH IDENTICAL S-BOXES

Abstract

Paradigm

My account