Local reduction and the algebraic cryptanalysis of the block cipher GOST (Q2392058)

The paper applies some techniques of algebraic cryptanalysis to evaluate the security of GOST, a private-key Feistel cryptosystem with 32 rounds, see [RFC 5830, GOST 28147-89 encryption, decryption and MAC algorithms, \url{http://www.faqs.org/rfc/rfc5830.txt} (2010)]. In fact, combining strategies of local reduction, the method of syllogisms and generic guessing strategies, the paper deduces lower bounds in the number of rounds required to assure the security, against known-plaintext attacks, of GOST with 64, 128 and 256 bit keys. Section 2 summarizes the strategies to solve sparse Boolean equation systems by local reduction and Section 3 specifies the methodology and the three guessing strategies (RANDOM, GUESS and IMPACT) to be used in the following. Section 4 describes the GOST cryptosystem and constructs the corresponding equation system in the symbol representation. Section 5 shows experimental results for the three selected guessing strategies and computes the dependence of the complexity of the algorithm to solve the equation system on the number of rounds. The paper concludes that \` \` the RANDOM guessing strategy is successful up to 9 rounds of GOST-64, up to 11 rounds of GOST-128, and up to 18 rounds of GOST-256, respectively. The GUESS strategy improves these results to 11, 14, and 20 rounds, respectively. The IMPACT strategy with rebalancing improves the results for GOST-128 and GOST-256 by one round.