Universite Paris Diderot Paris

Charles Bouillaguet

Description

Niveau: Supérieur, Doctorat, Bac+8
Universite Paris Diderot (Paris 7) Ecole Normale Superieure Equipe Crypto These de doctorat Etudes d'hypotheses algorithmiques et attaques de primitives cryptographiques Specialite : Informatique presentee et soutenue publiquement le 26 septembre 2011 par Charles Bouillaguet pour obtenir le grade de Docteur de l'universite Paris Diderot devant le jury compose de Responsable scientifique : Pierre-Alain Fouque (Ecole Normale Superieure, France) Rapporteurs : Joan Daemen (ST Microelectronics, Belgique) Henri Gilbert (ANSSI) Examinateurs : Hubert Comon-Lundh (CNRS & Ecole Normale Superieure de Cachan, France) Arnaud Durand (Universite Paris 7, France) Ludovic Perret (Universite Paris 6, France) Vincent Rijmen (Katholieke Universiteit Leuven, Belgique) Jacques Stern (CNRS & Ecole Normale Superieure, France)

• collection d'attaques


• pistes utiles


• preuve face


• moi des documents de travail utiles


• outils automatiques pour la recherche d'attaque


• compromis temps-memoire-donnees pour les attaques en seconde preimage

Sujets

• La Party
• Fouqué
• STMicroelectronics
• Angely

Informations

• Publié par: profil-feym-2012
• Publié le: 01 septembre 2011
• Nombre de lectures: 163
• Langue: Français
• Poids de l'ouvrage: 5 Mo

Extrait

Universite Paris Diderot Ecole Normale Superieure
(Paris 7) Equipe Crypto
These de doctorat
Etudes d’hypotheses algorithmiques et attaques
de primitives cryptographiques
Specialite : Informatique
presentee et soutenue publiquement le 26 septembre 2011 par
Charles Bouillaguet
pour obtenir le grade de
Docteur de l’universite Paris Diderot
devant le jury compose de
Responsable scienti que : Pierre-Alain Fouque (Ecole Normale Superieure, France)
Rapporteurs : Joan Daemen (ST Microelectronics, Belgique)
Henri Gilbert (ANSSI)
Examinateurs : Hubert Comon-Lundh (CNRS & Ecole Normale Superieure de Cachan, France)
Arnaud Durand (Universite Paris 7, France)
Ludovic Perret (Universite Paris 6, France)
Vincent Rijmen (Katholieke Universiteit Leuven, Belgique)
Jacques Stern (CNRS & Ecole Normale Superieure, France)Remerciements
Je souhaite remercier tous ceux qui, par leur soutien, ont contribue a la reussite de cette these. Je remercie
tout d’abord les membres du Jury d’avoir accepte d’^etreal aujourd’hui, en particulier ceux qui viennent de
l’etranger. Je remercie chaleureusement Joan Daemen et Henri Gilbert, qui ont du^ relire un manuscrit plut^ot
imposant en peu de temps, mais qui l’ont fait avec le sourire.
Cette these n’aurait pas ete possible sans le soutien nancier de la fondation EADS, envers qui je suis
evidement tres reconnaissant.
Materialiste convaincu, je mesure le pro t que j’ai pu tirer de l’environnement exceptionnel dont Pierre-
Alain Fouque m’a fait bene cier en me faisant entrer dans l’equipe de cryptographie du LIENS. Merci
donc aux autres chercheurs de l’equipe qui ont toujours ete a l’ecoute, c’est-a-d ire par ordre alphabetique
Michel Abdalla (fournisseur o ciel de cafe) Bruno Blanchet, Vadim Lyubashevsky, David Naccache et les
Men-in-Black, Phong NGuyen, David Pointcheval (pour avoir en plus supporte les inconvenients d’^etre mon
directeur de these o ciel) et Damien Vergnaud (pour avoir pr^ete son appartement et son frigo). L’ambiance
de cette equipe ne serait pas ce qu’elle est sans ses thesards et post-docs, et pour cela je remercie sans ordre
particulier Leo Ducas pour nombre de seances de brainstorming souvent peu frucueuses, Qiang Tang, Georg
Fuchsbauer et Steven Gay pour le ping-pong de l’apres-midi en 2007, Malika Izabachene, Celine Chevalier
et Yuan-Mi Chen pour ^etre sympas, Aurore Guillevic (made in Bretagne) pour les mangas, Aurelie Bauer
pour ^etre la Gentille Organisatrice et pour avoir cree un seminaire qui a porte brievement son nom en signe
de reconnaissance eternelle, Olivier Blazy pour les produits derives Portal, Jeremie Jean parce qu’il a pirate
\Questions pour un champion" ou autre un jeu du m^eme style, Dario Fiore et Mario Stre er parce que ce
sont de beaux gosses, David Cade parce que je n’avais jamais vu quelqu’un jouer a une sorte de Guitar-Hero
en entrant en transe au cours de la partie, et en n Miriam Paiola parce qu’elle est souriante et que comme
elle est assise juste en face de moi c’est elle que je regarde tout le temps.
Je remercie plus particulierement les thesards avec qui j’ai eu l’occasion de collaborer. Merci donc a
Gaetan Leurent, mon sempai qui pla cait de facto la barre assez haut, a Sebastien Zimmer pour ses petites
siestes qui justiaient les miennes et pour son aide tranquille mais e cace lors de mes debuts, a Elena
Andreeva pour avoir initie une collaboration internationale fructueuse et amicale, a Mehdi Tibouchi qui a
ete mon oracle pour les problemes de math qui me depassaient, a Patrick Derbez pour sa creativite et sa
souplesse d’esprit (aussi avec les horaires et la rigueur mathematique), et en n a Joana Treger-Marim pour
sa determination a l’epreuve des balles, sa rigueur et sa jovialite.
Dans l’ensemble, je n’ai lu en detail que les theses de Vivien Dubois, de Sebastien Kunz-Jacques, de
Magali Turrel-Bardet et de Gilles Macario-Rat. Elles ont ete pour moi des documents de travail utiles, sur
le serieux desquels je pouvais compter. J’espere juste que la mienne sera aussi bien.
Je remercie Bo-Yin Yang ainsi que Ludovic Perret et Jean-Charles Faugere, qui ont tous les trois instan-
tanement accepte de participer et de s’investir dans les projets que je leur proposais. Antoine Joux, Vincent
Rijmen et Adi Shamir et m’ont tous les trois fait le plaisir et l’honneur de travailler avec moi, et je les
remercie de la facilite avec laquelle ils partagent leur experience et en font pro ter leur entourage. Au gre
des rencontres, j’ai pu en bene cier a plusieurs reprises.
Cette these n’aurait pas non plus ete possible sans le soutien indefectible de l’equipe administrative et
technique de l’ENS. Je remercie chaleureusement Jacques Beigbeder, Nasser Bacha et Ludovic Ricardou pour
le devouement, le serieux et l’e cacite dont ils ont toujours fait preuve face a mes demandes ou a mes appels
au secours. Ils ne seront jamais assez remercies. Merci aussi a Michelle Angely, Lise-Marie Bivard, Isabelle
Delais, Joelle Isnard et Valerie Mongiat, sans lesquelles je n’aurais jamais rien fait. Elles ne seront jamais
assez remerciees non plus.
3Je remercie aussi Orr Dunkelman, qui en plus de m’avoir fait bene cier de son talent et de son sens de
l’humour sur une base quotidienne lors de son sejour a l’ENS et m^eme au-dela, est aussi un ami personnel.
Finalement, je remercie Pierre-Alain Fouque, tres certainement la personne qui a joue le rol^ e le plus impor-
tant pour moi dans ces annees de these. Il a supporte de m’avoir dans les jambes tous les jours pendant
pratiquement trois ans avec un calme olympien. Il m’a guide, m’a propose des pistes utiles qui ont pu de-
boucher sur des resultats, s’est preoccupe de l’avancement et de l’aboutissement de mes travaux sans ^etre
ni laxiste ni autoritaire. Le spectre large de ses domaines de competence m’a permit de travailler des sujets
(multi)varies, et n’ayant m^eme rien a voir entre eux. En gros, il est responsable des resultats que j’ai pu
obtenir.
J’en vient a la partie la plus di cile, celle ou il faut que je remercie mon amoureuse. Pour les polemiques
de mauvaise foi sur \est-ce que la cryptologie est plus ou moins importante que l’in uence du changement
climatique sur le regime de la Loire moyenne", je ne sais pas si je dois te remercier. Neanmoins, tu as
toujours supporte que je me passionne pour des trucs bizarres, et tu as toujours recolle les morceaux quand
la deception succedait a l’enthousiasme premature. J’ai commence cette these avant de te rencontrer, mais
maintenant la these est nie et toi, tu es toujours la. Bref, la science c’est bien, mais toi c’est mieux.
4Sommaire
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Presentation de mes Travaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
I Modes operatoires de fonctions de hachage 21
3 Modes operatoires et attaques generiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4 Nouvelles attaques en seconde preimage generiques . . . . . . . . . . . . . . . . . . . . . . . . 49
5 Autres attaques generiques contre d’autres constructions . . . . . . . . . . . . . . . . . . . . . 61
6 Compromis temps-memoire-donnees pour les attaques en seconde preimage . . . . . . . . . . . 69
7 Securite prouvee des modes operatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
II Cryptanalyse assistee par ordinateur de primitives orientees octet 93
8 Outils automatiques pour la recherche d’attaque a faible complexite en donnees . . . . . . . . 99
9 Une collection d’attaques a faible complexite en donnees . . . . . . . . . . . . . . . . . . . . . 111
III Etude d’hypotheses algorithmiques en cryptographie multivariee 139
10 Une boite a outil pour la cryptanalyse multivariee . . . . . . . . . . . . . . . . . . . . . . . . . 145
11 Recherche exhaustive pour la resolution d’equations booleennes . . . . . . . . . . . . . . . . . 169
12 Problemes \d’Isomorphisme de Polyn^ omes" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
13 Etat de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
14 Une methode generale : les pinceaux de matrice . . . . . . . . . . . . . . . . . . . . . . . . . . 213
15 Equivalence simultanee de formes quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . 219
16 Equivalence de formes cubiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
17 Equivalence lineaire de fonctions quadratiques inhomogenes . . . . . . . . . . . . . . . . . . . 233
18 Equivalence lineaire de fonctions quadratiques homogenes . . . . . . . . . . . . . . . . . . . . 241
19 Une classe de clefs faibles dans HFE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
5Table des Matieres
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Presentation de mes Travaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1 Etude de modes operatoires pour les fonctions de hachage . . . . . . . . . . . . . . . . . . 12
2.2 Recherche automatiques d’attaques sur des versions reduites de l’AES . . . . . . . . . . . 14
2.3 Etude de problemes di ciles en cryptographie multivariee . . . . . . . . . . . . . . . . . . 16
2.4 Me