The use of Groebner bases in cryptanalysis of symmetric ciphers

Abstract

Algebraic attacks on symmetric ciphers often results in large systems of non-linear multivariate polynomial equations. Solving these equations is a complex task. There are many methods for doing this, but the most fundamental is by constructing Groebner bases for the system of polynomials. In an article by Jovan Dj. Golic, "Vectorial Boolean Functions and Induced Algebraic Equations" a general mathematical framework for algebraic cryptanalysis is developed. In short, the article concerns finding algebraic polynomial equations of low algebraic degree induced by vectorial Boolean functions. This thesis will investigate the framework and develop hopefully more efficient algorithms for constructing Groebner bases over Boolean polynomial rings.

Topic covered by the project

There are different ways of attacking, or cryptanalysing, a cipher algorithm. Well known methods are e.g. linear cryptanalysis, differential cryptanalysis or plain brute force. The basis of this work comes from an attack method called Algebraic Attack or Algebraic Cryptanalysis. In short, an algebraic attack on a cipher algorithm is performed by breaking the cipher algorithm down into a system of algebraic equations, with the secret key bits as unknowns, plaintext and ciphertext as knowns, and other cipher dependent variables and constants. One then tries to find a simultaneous solution to the equations. The major problem with this method lies in solving the equations within an acceptable time frame, since the resulting multivariate equations, i.e. equations in several variables, are often highly non-linear and of high degree. But there are techniques for transforming this hard problem into a more feasible one. One technique is transforming the set of polynomial equations into a more suitable set of polynomials called a Groebner base. The notion of Groebner bases allows us to make use of results from abstract algebra, like Ideal theory and the relation to Affine varieties to help solve the equations in a hopefully more efficient way. Practical construction of Groebner bases belongs to the art of computational algebra, and algorithms will be implemented in several programming languages during the different phases of this project.

Keywords

Algebraic attack, cryptanalysis, symmetric cipher, multivariate equations, linearization, Groebner, Buchberger algorithm, vectorial Boolean functions.

Problem description

Groebner bases may seem like a superb tool, but the main problem is the computation time and memory consumption in constructing the Groebner bases. The general problem of constructing Groebner bases has high complexity. Thus, a seemingly benign looking system of polynomials in three or four variables of degree three or four may fail to terminate in a reasonable time. The original algorithm for constructing Groebner bases, namely the Buchberger algorithm can be improved, tweaked and be rendered more suitable to the specific problem at hand. In the case of this work, we will examine the construction of low degree Groebner bases from induced algebraic equations of binary multivariate polynomials and try to implement efficient algorithms for it.

Justification, motivation and benefits

The construction of Groebner bases is the fundamental tool for many complex problems. Finding new- or improving old algorithms for efficiently constructing Groebner bases are of great interest to many scientific disciplines. Regarding the discipline of algebraic cryptanalysis, increased and deeper knowledge in the use and construction of Groebner bases may be highly beneficial. Direct benefits may be the construction of stronger cryptographic algorithms which are more resistant to this type of attack.