7 January 2013

Security of block ciphers and multivariate schemes

Étude de la Sécurité de Schémas de Chiffrement par Bloc et de Schémas Multivariés

http://www.ssi.gouv.fr/IMG/pdf/Thesis.pdf (FR)

Security of block ciphers and multivariate schemes

24 June 2010

Abstract :

The thesis focuses on the security of block ciphers and multivariate schemes. In the first part, we study Feistel networks with internal permutations and Mistylike schemes, which are both involved in the design of many symmetric algorithms. The study is made in a generic context, which means that the internal permutations are supposed random. This allows to exhibit properties of the schemes’ structure, without taking into account eventual weaknesses of the internal permutations. This part focuses on generic attacks on these schemes, and is related to the series of works done by Patarin et al. on similar structures. We consider attacks that allow to distinguish with high probability one scheme or the other from a random permutation. Different types of attacks are studied for the first rounds (e.g. two points, three points or four points attacks), then, we extend the two points attacks for any number of rounds, thanks to Patarin’s H-coefficient technique.

The second part of the thesis deals with multivariate cryptosystems. Two schemes are studied in particular : the so-called HM scheme (“Hidden Matrix” scheme) and the HFE scheme (“Hidden Field Equations”), both designed by Patarin in 1998 and 1996 respectively. For HM, we exhibit a special property of the differential of the public key, which gives an efficient distinguisher between the system of equations forming the public key and a random system of equations. Moreover, the use of Gröbner bases (in particular, MAGMA’s implementation of Faugère’s F4 algorithm) allows to efficiently invert the public key in polynomial time, for any practical paremeters.

We also study the equations involved in such a Gröbner based attack. More precisely we show that many low-degree polynomials appear during the computation, which mostly explains the good behaviour of the Gröbner bases algorithms. Finally for HFE, we describe a key-recovery attack that affects a whole family of special instances, and whose complexity comes down to solving one instance of the IP problem. These weak instances are the polynomials with coefficients in the base field. They happen to offer a commutation property with the Frobenius map, allowing our attack to work.

Keywords : block cipher, Feistel cipher, MISTY, generic attacks, two-point attacks, H coefficients, multivariate cryptology, HM scheme, HFE, Gröbner bases, cryptanalysis.