L.С. Babenko, E.A. Maro

This paper is devoted to the research of applicability of algebraic cryptanalysis methods to block ciphers. The aim of this work is to analyze features of eXtended Linearization (XL) and eXtended Sparse Linearization (XSL) methods when they are applied to GOST 28147-89 and AES algorithms. The essence of algebraic attack methods is finding secret data by solving nonlinear systems of equations, which describe the encryption algorithm. In general, algebraic attacks can be presented as two stages: - creation of a nonlinear system of equations, - solving the system (finding a secret key). Nonlinear systems of equations for block ciphers are built according to their substitution blocks (S-box). In this paper we present an algorithm of nonlinear system creation for an arbitrary S-box, as well as a sample nonlinear system obtained for a 4-4-bit S-box. Three methods of solving a nonlinear system are presented in the paper: linearization, eXtended Linearization and eXtended Sparse Linearization. The algorithms of solving are presented for each method; applicability conditions and method selection criteria are also described. As soon as S-blocks are considered a part of the secret key in GOST, we have to provide an additional stage to get GOST S-blocks. The algorithm for S-boxes computation is also presented in the paper