UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Contradiction Immunity and Guess-Then-Determine Attacks On GOST

Courtois, N; Gawinecki, J; Song, G; (2013) Contradiction Immunity and Guess-Then-Determine Attacks On GOST. In Tatra Mountains Mathematic Publications , 53 (1) 65 - 79. 10.2478/v10127-012-0039-3. Green open access

[img] PDF
0114113604CuGaSo.pdf
Access restricted to UNSPECIFIED

Download (286kB)

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.

Type: Article
Title: Contradiction Immunity and Guess-Then-Determine Attacks On GOST
Location: Slovakia
Open access status: An open access version is available from UCL Discovery
DOI: 10.2478/v10127-012-0039-3
Publisher version: http://dx.doi.org/10.2478/v10127-012-0039-3
Language: English
Additional information: This is an Open Access article distributed under Degruyter licence agreement, which permits use, distribution, and reproduction in any medium, provided that that reuse is restricted to non-commercial purposes, i.e. research or educational use, and the original work is properly cited.
Keywords: Block ciphers, cryptanalysis, GOST, DES, low-data complexity attacks, guess-then-determine, meet in the middle, combinatorial optimization, SAT Solvers
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/1395015
Downloads since deposit
1Download
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item