Etudes d'hypothèses algorithmiques et attaques de primitives cryptographiques
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Cryptanalysis consists in finding flaws of all kinds in cryptographic constructions. This thesis is made of three parts, devoted to the study of different families of cryptographic primitives. Hash functions are iterated constructions, where a building block is used in a repeated way, as specified by a mode of operation. The discovery of new generic attacks, targeting the standard mode of operation, prompted the design of alternative modes of operations. These attacks exploit internal collisions in the hash functions. Our results tend to show that this problem is difficult to avoid: we describe generic second preimage attacks against proposals precisely designed to avoid these attacks. We next focus on the cryptanalysis of the AES in a restrictive attack model where the attacker only has access to a small quantity of data. We have built software tools to assist us in finding guess-and-determine as well as meet-in-the-middle attacks. These tools found surprising attacks, and for instance, we find the best known attacks against Pelican-MAC, and against the LEX. The last part of this thesis is devoted to the cryptanalysis of multivariate schemes (whose security explicitly relies on the hardness of solving Systems of polynomial equations in several unknowns). Some multivariate scheme also rely on another hardness assumption, namely the hardness of the Polynomial Linear Equivalence (PLE) problem. We build new algorithms to solve PLE, and we show that a multivariate scheme relying on the hardness of PLE cannot exhibit an optimal security level. These algorithms also allow to break in practice the "subfield" variant of HFE.
Abstract FR:
La cryptanalyse est la science qui consiste à trouver des défauts dans des constructions cryptographiques. Dans cette thèse, nous étudions trois familles de primitives cryptographiques. Les fonctions de hachage sont des constructions itérées, où un mode opératoire précise l'usage d'une brique de base. De nouveaux modes opératoires ont été proposés suite à la découverte d'attaques contre la construction usuelle. Ces attaques exploitent des collisions internes dans la fonction de hachage. Nos résultats tendent à montrer qu'elles sont quasiment impossibles à éviter, car nous parvenons à monter des attaques en seconde préimage contre certains de ces nouveaux modes. Nous nous intéressons ensuite à la cryptanalyse de l'AES dans un modèle restrictif où la quantité de paires clair/chiffré est très faible. Nous avons construit des outils automatiques pour nous assister dans la recherche d'attaques par test d'hypothèses partielles ou par le milieu. Ces outils ont découverts des attaques surprenantes, et notamment la meilleure attaque connue contre Pelican-MAC et contre LEX. La dernière partie est consacrée à la cryptanalyse de schémas multivariés, c'est-à-dire reposant explicitement sur la difficulté de résoudre des systèmes polynomiaux en plusieurs variables. Certains de ces schémas reposent aussi sur une autre hypothèse algorithmique, la difficulté problème de l'Equivalence Linéaire de Polynômes (PLE). Nous proposons de nouveaux algorithmes pour PLE. Ceci montre qu'un schéma dont la sécurité reposerait sur PLE ne peut pas exhiber un niveau de sécurité optimal, et que la variante "sous- corps" de HFE est cassée en pratique