Algebraic Cryptanalysis of Block Ciphers Using Groebner Bases

This thesis investigates the application of Groebner bases to cryptanalysis of block ciphers. The basic for the application is an algorithm for solving systems of polynomial equations via Groebner basis computation. In our case, polynomial equations describe the key recovery problem for block ciphers, i.e., the solution of these systems corresponds to the value of the secret key. First we demonstrate that Groebner basis technique can be successfully used to break block ciphers, if the algebraic structure of these ciphers is relatively simple. To show this, we construct two families of block ciphers that satisfy this condition. However, our ciphers are not trivial, they have a reasonable block and key size as well as an acceptable number of rounds. Moreover, using suitable parameters we achieve good resistance of these ciphers against differential and linear cryptanalysis. At the same time, we design our ciphers so that the key recovery problem for each of them can be described by a system of simple polynomial equations. In addition, parameters of the ciphers can be varied independently. This makes the constructed families suitable for analysis of algebraic attacks. To study the vulnerable of such ciphers against Groebner basis attack, we have performed experiments using the computer algebra system Magma. Results of these experiments are given and analyzed. Also, for a subset of these ciphers we present an efficient method to construct zero-dimensional Groebner bases w.r.t. a degree-reverse lexicographical term order without a polynomial reduction. This reduces the key recovery problem to the problem of Groebner basis conversion. Using known complexity bounds for the last problem, we estimate the maximum resistance of these ciphers against Groebner basis attacks. We show that our method can be also applied to the AES block cipher. In the thesis we describe the AES key recovery problem in the form of a total-degree Groebner basis, explain how this Groebner basis can be obtained, and study the cryptanalytic significance of this result. Next, we investigate the semi-regularity of several polynomial representations for iterated block ciphers. We demonstrate that the constructed Groebner basis for the AES is semi-regular. Then we prove that polynomial systems that are similar to the BES quadratic equations are not semi-regular as well as the AES systems of quadratic equations over GF(2) are not semi-regular over GF(2). Finally, we propose a new method of side-channel cryptanalysis - algebraic collision attacks - and explain it by the example of the AES. The method is based on the standard power analysis technique, which is applied to derive an additional information from an implementation of a cryptosystem. In our case, this information is about generalized internal collisions occurring between S-boxes of the block cipher. However, we use a new approach to recover the secret key from the obtained information. Taking into account a specific structure of the attacked cryptographic algorithm, we express the detected collisions as a system of polynomial equations and use Groebner bases to solve this system. This approach provides significant advantages both in terms of measurements and post-processing complexity. Also, we use non-collisions to optimize our method. For the AES block cipher, we demonstrate several efficient algebraic collision attacks. The first of them works in the known-plaintext scenario and requires 5 measurements to derive the full secret key within several hours on a PC with success probability 0.93. This attack with 4 measurements recovers key in about 40% of all cases. The second attack works in the known plaintext/ciphertext pair scenario but leads to more efficient results: the key can be obtained in several seconds of offline computations with success probability of 0.82 for 4 measurements, and with probability close to 1 for 5 measurements. We also propose a successful algebraic collision attack on the AES with 3 measurements. The attack has a probability of 0.42 and needs 4.24 PC hours post-processing