Local reduction and the algebraic cryptanalysis of the block cipher GOST

DOI10.1007/S10998-012-6376-9MaRDI QIDQ2392058zbMATH OpenOpenAlexWikidataFDO

Authors Pavol Zajac, Radoslav Čagala

Publication date 6 August 2013

Published in Periodica Mathematica Hungarica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10998-012-6376-9

zbMATH Keywords

algebraic cryptanalysislocal reductionmethod of syllogisms

Mathematics Subject Classification ID

Applications to coding theory and cryptography of arithmetic geometry (14G50) Cryptography (94A60)

Review text

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.

Recommendations

• Linear and differential cryptanalysis of Russian GOST
• scientific article; zbMATH DE number 1689015
• Cryptanalysis of GOST in the multiple-key scenario
• scientific article; zbMATH DE number 1823207
• Contradiction immunity and guess-then-determine attacks on GOST

Cites work

• A new efficient algorithm for computing Gröbner bases (F₄)
• Algebraic Cryptanalysis of the Data Encryption Standard
• scientific article; zbMATH DE number 2151220 (Why is no real title available?)
• Methods to solve algebraic equations in cryptanalysis
• MRHS Equation Systems
• On solving sparse algebraic equations over finite fields
• On the complexity of k-SAT
• On the use of the lattice sieve in the 3D NFS
• Solving equation systems by agreeing and learning
• Solving multiple right hand sides linear equations
• Solving Trivium-based Boolean equations using the method of syllogisms
• Sparse algebraic equations over finite fields

Cited in

(3)

• Linear and differential cryptanalysis of Russian GOST
• Contradiction immunity and guess-then-determine attacks on GOST
• Solving sparse MRHS systems with genetic algorithms

This page was built for publication: Local reduction and the algebraic cryptanalysis of the block cipher GOST

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392058)