<abstract xmlns="http://www.w3.org/1999/xhtml"><p> 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.</p><p>We introduce a key fundamental notion of <bold>Contradiction Immunity</bold> 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.</p></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.

Contradiction Immunity and Guess-Then-Determine Attacks on Gost

University College London, Gower street, London, UNITED KINGDOM

Military University of Technology, Warsaw, POLAND

University College London, Gower street, London, UNITED KINGDOM, CISCO Systems, London, UNITED KINGDOM

Tatra Mountains Mathematical Publications

{"article-title":"Contradiction Immunity and Guess-Then-Determine Attacks on Gost"}

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...

Contradiction Immunity and Guess-Then-Determine Attacks on Gost

Published Online: Feb 01, 2013

Page range: 65 - 79

DOI: https://doi.org/10.2478/v10127-012-0039-3

Keywords
block ciphers, cryptanalysis, GOST, DES, low-data complexity, guess-then- -determine, meet in the middle, combinatorial optimization, SAT Solvers

This content is open access.

Contradiction Immunity and Guess-Then-Determine Attacks on Gost

Published Online: Feb 01, 2013

Page range: 65 - 79

DOI: https://doi.org/10.2478/v10127-012-0039-3

Keywordsblock ciphers, cryptanalysis, GOST, DES, low-data complexity, guess-then- -determine, meet in the middle, combinatorial optimization, SAT Solvers

This content is open access.

Keywords
block ciphers, cryptanalysis, GOST, DES, low-data complexity, guess-then- -determine, meet in the middle, combinatorial optimization, SAT Solvers