Strength Assessment of Modern Cryptosystems Using Methods of the Analysis Based on the Solutions of Combined Equations

Abstract

Encryption algorithm GOST 28147-89 (hereinafter GOST) is Russian national standard of symmetric encryption. Many systems of information security are based on computation complexity of algorithm GOST. Our research is about possibility of methods of the analysis based on the solutions of combined equations. The general idea of algebraic analysis is based on the representation of initial encryption algorithm as a system of multivariate quadratic equations, which define relations between a secret key and a plain/cipher text. Extended linearization (XL) method is evaluated as a method for solving the nonlinear system of equations. We observe attack to three rounds of GOST using XL methods. The research has shown that for 32-round GOST system is consist of 5376 quadratic equations, which characterize dependencies between inputs and outputs of S-blocks. The total number of variables is 2048 and the system contains 9472 monomials. Algebraic attacks (and many others like linear, differential methods) are needed to know substitution tables of encryption algorithms. However S-boxes of GOST are additional secret element of encryption, therefore this work presents software implementation and complexity evaluation of computing secret S-boxes. Also the part of the work devoted to finding the influence of S-Boxes to resistance of GOST algorithm against linear cryptanalysis. The universal algorithm for searching particular layouts of S-Boxes, which are vulnerable to linear cryptanalysis is presented. The possibility of building of efficient linear statistical expressions for simplified GOST with weak S-Boxes has been shown. This research is aimed to ensuring that certain arbitrary S-Box layouts are not weak when they are not fixed. Applicability of the presented method was tested by analyzing S-Boxes used in GOST. Application of the designed method made it possible to discover a number of weak S-Boxes, which make the overall cryptographic strength of GOST much lower.
Copyright © 2015 Praise Worthy Prize - All rights reserved.