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 Hcoefficient technique.
The second part of the thesis deals with multivariate cryptosystems. Two
schemes are studied in particular : the socalled 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 lowdegree polynomials appear during the
computation, which mostly explains the good behaviour of the Gröbner
bases algorithms. Finally for HFE, we describe a keyrecovery 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, twopoint
attacks, H coefficients, multivariate cryptology, HM scheme, HFE, Gröbner
bases, cryptanalysis.
