Master Thesis no. 2004-07

Cryptanalysis of secret-key cryptosystems

Charlotte Heinstrup Vikkelsø

August 2004

Abstract

Throughout the past decades block ciphers iterating over round functions composed by applications of small S-boxes and linear transformations have been proposed and applied widely. The security of these is based on the fact that for the most well known attacks on block ciphers, namely the linear and the differential attacks, the complexity grows exponentially in the number of rounds.

Algebraic attacks follows a different approach than the above named probabilistic attacks. As opposed to these the algebraic approaches seeks to determine the key uniquely from just one, or very few, known text pairs. The algebraic attacks presented in this thesis are based on the fact that for S-boxes of many of the most acknowledged block cipher, such as the AES, Serpent, Noekeon etc., a great number of multivariate quadratic equations over GF(2) exist. The general problem of solving systems of multivariate equations over a finite fields is known to be NP-complete. Perhaps for this reason the potential for such equations to exist has not previously been considered in the design of the S-boxes.

Within the past couple of years new algorithms, which provides methods for solving these systems of equations, have been developed. At first the method of Relinearization was published, then the eXtended Linearization algorithm and finally the eXtended Sparse Linearization algorithm. The latter is claimed to exploit the special property, that the equations describing the AES are overdefined and sparse, in a so efficient way that it will have a big impact on the AES.

In this thesis the algebraic attacks and their application to practical block cipher (especially the AES) are studied. Moreover a preliminary version of a new approach to the algebraic attacks is suggested. We have analysed and simulated both the XL attack and our approach on small block ciphers and it seems that this new approach has got potential for being practical on larger ciphers.

Pages: 102