Description
Date depot: 1 janvier 1900
Titre: Sécurité et cryptanalyse des fonctions de hachage soumises à la compétition SHA-3
Directrice de thèse:
Anne CANTEAUT (Inria-Paris (ED-130))
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
{{Bref état de l'art}}
Une fonction de hachage doit idéalement se comporter comme un oracle aléatoire. Cette propriété ne peut être atteinte dans l'absolu, et l'on définit en pratique trois caractéristiques principales de sécurité pour les fonctions de hachage, qui consistent à résister à trois types de menaces distinctes : une attaque possible consiste par exemple à trouver deux messages $m
eq m^{prime}$ tels que $H(m) = H(m^{prime})$, situation qu'on appelle une collision; étant donné un haché $h$, une autre attaque consiste à trouver un message $m$ tel que $H(m) = h$ (attaque en préimage); enfin, étant donné un message $m$, un troisième type d'attaque est de trouver un deuxième message $m^{prime}
eq m$ tel que $H(m) = H(m^{prime})$ (attaque en seconde préimage).
L'histoire moderne de la cryptanalyse des fonctions de hachage commence en 1996, quand Hans Dobbertin a présenté ses travaux sur une cryptanalyse complète de la fonction MD4, capable de produire des collisions. Deux ans plus tard, Florent Chabaud et Antoine Joux fournissent une attaque théorique et des premières collisions sur SHA-0 en moins de $2^{80}$ opérations. En 2004, Biham et Chen introduisirent l'idée des bits neutres, qui mena plus tard au calcul de la première collision sur SHA-0 avec 4 blocs de message. 2004 s'est avérée une année clé dans l'histoire de la cryptanalyse, lorsque la communauté scientifique découvre les travaux de cinq chercheurs chinois (Wang, Lai, Feng, Cheng et Yu) qui révolutionnent la recherche de collisions et qui présentent des {chemins différentiels} et des collisions présentant une complexité très basse sur des fonctions très connues comme MD5, SHA-1 ou RIPEMD-0. Depuis ces importantes avancées, une grande quantité de nouveaux travaux publiés pendant les cinq dernières années ont permis de mieux comprendre ces attaques et d'apporter des améliorations fondamentales aux méthodes de construction des fonctions. Parmi ces articles, les travaux de Vlastimil Klima et sa technique des {tunnels} ou encore les travaux de Marc Stevens, ont pu réduire encore la complexité des attaques.
La capacité d'un attaquant à trouver des collisions sur une fonction de hachage peut aujourd'hui avoir des conséquences dangereuses sur les schémas de signature ou l'intégrité des données. En 2007, Stevens, Lenstra et de Weger ont pu construire, sous certaines conditions, deux certificats X509 qui collisionnent. De la même façon, Stevens et al. ont récemment exploité des faiblesses de la fonction MD5 pour produire à partir d'un certificat numérique donné un nouveau certificat illégitime mais parfaitement valide, et d'une manière dégagée des contraintes qui existaient dans les attaques précédentes. Les certificats ainsi construits permettent facilement de se faire passer pour un site internet certifié arbitraire, alors même que le protocole sécurisé HTTPS est utilisé.
{{Plan des travaux}}
Cette thèse sera essentiellement consacrée à l'analyse de la sécurité des fonctions de hachage, notamment à travers les nouveaux algorithmes qui ont été proposés à la compétition SHA-3. En effet, les fonctions de hachage reposent encore sur des bases qui semblent très fragiles comme en témoignent le nombre d'attaques publiées en un an contre les algorithmes soumis à SHA-3. Il semble donc primordial, si l'on veut aboutir à une fonction de hachage qui soit à la fois performante et sûre, de progresser dans l'analyse de la sécurité de ces candidats. Cette analyse pourra s'orienter dans deux grandes directions.
{{Analyse des primitives internes de certains candidats du concours SHA-3}}
Pour des raisons évidentes de performance et de coût d'implémentation (notamment sur des plates-formes très contraintes), les algorithmes cryptographiques symétriques consistent généralement à enchaîner un nombre important de fonctions relativement simples et portant sur des objets de petite taille. En règle générale, les divers composants utilisés ont une fonctionnalité bien particulière (certains propagent l'information à travers le système, d'autres introduisent de la non-linéarité...). Le choix de ces blocs élémentaires conditionnent naturellement la sécurité de l'algorithme global.
Dans d'autres domaines de la cryptographie symétrique comme celui du chiffrement par blocs, les travaux menés dans les vingt dernières années ont abouti à la définition de critères de conception très précis. On peut par exemple quantifier très exactement la résistance offerte par une fonction (boîte-S) donnée aux cryptanalyses différentielles et linéaires, et tous les algorithmes par blocs proposés reposent sur des fonctions offrant une résistance optimale ou presque optimale à ces attaques. L'exemple le plus connu est l'utilisation de la fonction inverse dans le corps fini à (2^8)~éléments dans le standard AES.
Dans le domaine des fonctions de hachage, la situation est beaucoup plus complexe. La plupart des attaques développées récemment sont encore trop p
Doctorant.e: Boura Christina