Contradiction Immunity and Guess-Then-Determine Attacks on Gost

Courtois, Nicolas T.; Gawinecki, Jerzy A.; Song, Guangyan

doi:10.2478/v10127-012-0039-3

Abstract

GOST is a well-known government standard cipher. Since 2011 several academic attacks on GOST have been found. Most of these attacks start by a so called “Complexity Reduction” step [Courtois Cryptologia 2012] the purpose of which is to reduce the problem of breaking the full 32-round GOST to a low-data complexity attack on a reduced-round GOST. These reductions can be viewed as optimisation problems which seek to maximize the number of values inside the cipher determined at given “cost” in terms of guessing other values. In this paper we look at similar combinatorial optimisation questions BUT at the lower level, inside reduced round versions of GOST.

We introduce a key fundamental notion of Contradiction Immunity of a block cipher. A low value translates to working software attacks on GOST with a SAT solver. A high value will be mandatory for any block cipher to be secure. We provide some upper bounds for the Contradiction Immunity of GOST.

References

[1] BIRYUKOV, A.-WAGNER, D.: Advanced Slide Attacks, in: Advances in Cryptology- -EUROCRYPT ’00, 19th Internat. Conf. on the Theory and Appl. of Cryptographic Tech., Bruges, Belgium, 2000 (B. Preneel, ed.), Lecture Notes in Comput. Sci., Vol. 1807, Springer, Berlin, 2000, pp. 598-606.
Search in Google Scholar
[2] BARD, G. V.-COURTOIS, N. T.-JEFFERSON, CH.: Efficient methods for conversion and solution of sparse systems of low-degree multivariate polynomials over GF(2) via SAT-solvers, http://eprint.iacr.org/2007/024/. A working windows distribution with source code is available at: http://www.nicolascourtois.com/software/CourtoisBardJefferson_public_distribution.zip
Search in Google Scholar
[3] COURTOIS, N.-BARD, G. V.: Algebraic cryptanalysis of the data encryption standard, in: Cryptography and Coding, 11th IMA Internat. Conf. (S. Galbraith, ed.), Cirencester, UK, 2007, Lecture Notes in Comput. Sci., Vol. 4887, Springer, Berlin, 2007, pp. 152-169; eprint.iacr.org/2006/402/.10.1007/978-3-540-77272-9_10
Search in Google Scholar
[4] COURTOIS, N.-BARD, G. V.-WAGNER, D.: Algebraic and slide attacks on KeeLoq, in: Fast Software Encryption, 15th Internat. Workshop-FSE ’08 (K. Nyberg, ed.), Lausanne, Switzerland, 2008, Lecture Notes in Comput. Sci., Vol. 5086, Springer, Berlin, 2008, pp. 97-115.
Search in Google Scholar
[5] COURTOIS, N.-BARD, G. V.-BOGDANOV, A.: Periodic ciphers with small blocks and aryptanalysis of KeeLoq, Tatra Mt. Math. Publ. 41 (2008), 167-188.
Search in Google Scholar
[6] COURTOIS, N.-DEBRAIZE, B.: Algebraic description and simultaneous linear approximations of addition in Snow 2.0., in: 10th Internat. Conf. on Information and Commun. Security-ICICS ’08 (L. Chen et al., eds.), Birmingham, UK, 2008, Lecture Notes in Comput. Sci., Vol. 5308, Springer, Berlin, 2008, pp. 328-344.
Search in Google Scholar
[7] COURTOIS, N. T.-SEPHERDAD, P.-SUSIL, P.-VAUDENAY, S.: ElimLin algorithm revisited, in: Fast Software Encryption-FSE ’12, 19th Internat. Workshop (A. Can-teaut, ed.), Washington, 2012, Lecture Notes in Comput. Sci., Vol. 7549, Springer, Berlin, pp. 306-325.
Search in Google Scholar
[8] COURTOIS, N.: Security evaluation of GOST 28147-89 in view of international standardisation, Cryptologia 36 (2012) 2-13.
Search in Google Scholar
[9] COURTOIS, N.: Low complexity key recovery attacks on GOST block cipher, Cryptologia 37 (2013) (to apear).10.1080/01611194.2012.739587
Search in Google Scholar
[10] COURTOIS, N.: Algebraic complexity reduction and cryptanalysis of GOST, Preprint, 9 December 2012, http://eprint.iacr.org/2011/626.
Search in Google Scholar
[11] COURTOIS, N.-MISZTAL, M.: Aggregated differentials and cryptanalysis of PP-1 and GOST, in: 11th Central European. Conference on Cryptology-CECC ’11, Debrecen, Hungary, 2012, Period. Math. Hungar. 65 (2012), 11-26.10.1007/s10998-012-2983-8
Search in Google Scholar
[12] COURTOIS, N.-MISZTAL, M.: First differential attack on full 32-round GOST, in: 13th Internat. Conf.-ICICS ’11 (S. Qing et al., eds.), Beijing, China, 2011, Lecture Notes in Comput. Sci., Vol. 7043, pp. 216-227.10.1007/978-3-642-25243-3_18
Search in Google Scholar
[13] COURTOIS, N.-MISZTAL, M.: Differential cryptanalysis of GOST, Cryptology ePrint Archive, Report 2011/312, 14 June 2011, http://eprint.iacr.org/2011/312.
Search in Google Scholar
[14] COURTOIS, N.: An improved differential attack on full GOST, in: Cryptology ePrint Archive, Report 2012/138, 15 March 2012, http://eprint.iacr.org/2012/138.
Search in Google Scholar
[15] COURTOIS, N. T.-HULME, D.-MOUROUZIS, TH.: Solving circuit optimisation problems in cryptography and cryptanalysis, in: (informal) proceedings of SHARCS ’12, Workshop, Washington, USA, pp. 179-191, http://2012.sharcs.org/record.pdf. Earlier preprint is available at, http://eprint.iacr.org/2011/475, and an abridged version appears in the electronic proceedings of the 2nd IMA conference Mathematics in Defence 2011, UK.
Search in Google Scholar
[16] DINUR, I.-DUNKELMAN, O.-SHAMIR, A.: Improved attacks on full GOST, in: Fast Software Encryption-FSE ’12, 19th Internat. Workshop, Washington, USA, 2012, Lecture Notes in Comput. Sci., Vol. 7549, Springer, Berlin, 2012, pp. 9-28; early version available at http://eprint.iacr.org/2011/558/.10.1007/978-3-642-34047-5_2
Search in Google Scholar
[17] FAUGÉRE, J.-CH.: A new efficient algorithm for computing Gr¨obner bases withoutreduction to zero (F5), in: Proc. of the Internat. Symp. on Symbolic and Algebraic Computation-ISSAC ’02, New York, NY, 2002, ACM Press, New York, pp. 75-83.10.1145/780506.780516
Search in Google Scholar
[18] SHORIN, V. V.-JELEZNIAKOV, V. V.-GABIDULIN, E. M.: Linear and differential cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 April 2001.10.1016/S1571-0653(04)00206-9
Search in Google Scholar
[19] ZABOTIN, I. A.-GLAZKOV, G. P.-ISAEVA, V. B.: Cryptographic protection for information processing systems, Government Standard of the USSR, GOST 28147-89, Government Committee of the USSR for Standards, 1989. ed States DES can be used ONLY for unclassified documents.
Search in Google Scholar
[20] A Russian reference implementation of GOST implementing Russian algorithms as an extension of TLS v1.0. is available as a part of OpenSSL library. The file gost89.c contains eight different sets of S-boxes and is found in OpenSSL 0.9.8 and later at http://www.openssl.org/source/
Search in Google Scholar
[21] ISOBE, T.: A single-key attack on the full GOST block cipher, in: Fast Software Encryption-FSE ’11, 18th Internat. Workshop (A. Joux, ed.), Lyngby, Denmark, 2011, Lecture Notes in Comput. Sci., Vol. 6733, Springer, Berlin, 2011, pp. 290-305.
Search in Google Scholar
[22] KARA, O.: Reflection cryptanalysis of some ciphers, in: Progress in Cryptology- -INDOCRYPT ’08, 9th Internat. Conf. on Cryptology in India (R. Chowdhury et al., eds.), Kharagpur, India, 2008, Lecture Notes in Comput. Sci., Vol. 5365, Springer, Berlin, 2008, pp. 294-307.
Search in Google Scholar
[23] POSCHMANN, A.-LING, S.-WANG, H.: 256 bit standardized crypto for 650 GE GOST revisited, in: Workshop on Cryptographic Hardware and Embedded Systems- CHES ’10 Santa Barbara, California, 2010, Lecture Notes in Comput. Sci., Vol. 6225, Springer, Berlin, 2010, pp. 219-233.
Search in Google Scholar
[24] CHARNES, C.-O’CONNOR, L.-PIEPRZYK, J.-SAVAFI-NAINI, R.-ZHENG, Y.: Comments on Soviet encryption algorithm, in: Advances in Cryptology- -EUROCRYPT ’94 (A. De Santis, ed.), Lecture Notes in Comput. Sci., Vol. 950, Springer, Berlin, 1995, pp. 433-438.10.1007/BFb0053459
Search in Google Scholar
[25] SEMAEV, I.: Sparse algebraic equations over finite fields, SIAM J. Comput. 39 (2009), 388-409.10.1137/070700371
Search in Google Scholar
[26] SÖRENSSON, N.-EEN, N.-SOOS, M.: CryptoMiniSat 2.92, an open-source SAT solver package based on earlier MiniSat software, http://www.msoos.org/cryptominisat2/.
Search in Google Scholar
[27] SCHNEIER, B.: Section 14.1 GOST (2nd ed.), in: Applied Cryptography, John Wiley and Sons, New York, 1996.
Search in Google Scholar

Contradiction Immunity and Guess-Then-Determine Attacks on Gost

Abstract

Paradigm

My account