- Itai Dinur, LIENS, ENS, – Improved Generic Attacks Against Hash-Based MACs Used in Practice
Résumé : HMAC is a specific MAC construction based on a hash function and secret key. It was designed in 1996 by Bellare, Canetti and Krawczyk, and is one of the most widely used MAC algorithms in practice today. The security of HMAC has been formally proven up to the birthday bound of $2^{\ell/2}$ (where $\ell$ is the internal state size), and this bound is tight, as there exist very simple attacks with this complexity against the construction. On the other hand, HMAC was believed to provide security of $2^{\ell}$ against more advanced and devastating attacks, such as state-recovery and universal forgery attacks. This situation changed very recently, following results of Leurent et al. and Peyrin et al., which presented advanced attacks against HMAC with complexity much lower than $2^{\ell}$.
In this talk, I will extend the recent results, and present improved attacks under various constraints imposed by underlying hash functions used by HMAC in practice. These attacks include the first state-recovery attacks that are applicable to HMAC using hash functions based on the HAIFA mode (such as BLAKE and Skein), which inputs a block counter to every compression function call. Moreover, I will present the first universal forgery attacks that are applicable to HMAC using SHA-1 and SHA-2, which limit the length of the hashed message.
Based on joint work with Gaëtan Leurent.
- Matthieu Finiasz, CryptoExperts – Construction de couches de diffusions récursives MDS à partir de codes BCH raccourcis
Résumé : Lors de la conception de schémas de chiffrement symétriques un dilemme se présente souvent : est-il préférable de superposer de nombreuses couches simples et rapides, ou quelques couches plus complexes mais de meilleure qualité ? Pour les couches de diffusion linéaires, les matrices MDS offrent la meilleure diffusion possible, en revanche elles sont souvent assez coûteuses à évaluer et ont une description peu compacte. Une idée est donc apparue très récemment : construire des matrices MDS à partir de matrices compagnons, donc simples à évaluer et ayant une description compacte. C’est ce que les cryptographes ont appelé des matrices récursives.
Jusqu’à présent, aucune construction directe de telles matrices n’était connue et seule une recherche plus ou moins exhaustive permettait d’en trouver pour des paramètres donnés. Le but de cet exposé est de présenter une construction directe de telles matrices à partir de codes BCH raccourcis. Cela permet, entre autres, de construire des matrices récursives pour des paramètres bien plus grand que ce qui était possible avant.
- Louise Huot, UPMC, LIP6, Équipe PolSyS – Résolution de systèmes polynomiaux et cryptologie sur les courbes elliptiques.
Résumé : Depuis ces dix dernières années, les attaques sur le logarithme discret sur les courbes elliptiques (ECDLP) mettant en jeu la résolution de systèmes polynomiaux connaissent un large succès. Dans cet exposé je présenterai les résultats obtenus pendant ma thèse sur cette thématique.
En particulier, j’introduirai de nouveaux outils de résolution de systèmes polynomiaux par bases de Gröbner. Plus précisément, nous nous intéressons à l’étape bloquante de la résolution de systèmes : le changement d’ordre pour bases de Gröbner. Depuis 20 ans, la complexité de cette étape est cubique en le nombre de solutions et domine la complexité totale de la résolution. Nous proposons de nouveaux algorithmes de changement d’ordre de complexité sous-cubique levant le caractère dominant de cette étape.
Cette nouvelle borne de complexité a un impact direct sur la complexité de l’attaque du logarithme discret sur les courbes elliptiques par calcul d’indice proposée par Gaudry.
Par ailleurs, nous mettons en évidence des familles de courbes elliptiques possédant des symétries particulières. Ces symétries impliquent un gain exponentiel sur la complexité de la résolution du ECDLP. Nous obtenons ainsi de nouveaux paramètres de sécurité pour certaines instances du ECDLP. En caractéristique deux, l’utilisation de ces symétries ainsi que du caractère creux des polynômes de sommation de Semaev nous permet d’établir un nouveau record de calcul de ces polynômes à la base de l’attaque de Gaudry.
Les travaux présentés sont extraits de travaux en collaboration avec Jean-Charles Faugère, Pierrick Gaudry, Antoine Joux, Guénaël Renault et Vanessa Vitse.
- Irene Marquez-Corbella, INRIA Saclay-île-de-France, LIX, Equipe Grace –Une attaque polynomiale du schéma de McEliece basé sur les codes géométriques
Résumé : L’idée d’utiliser la difficulté du décodage d’un code aléatoire comme primitive de cryptographie à clé publique à été introduite par McEliece en 1978. Le schéma de McEliece présente l’intérêt de résister aux attaques d’un hypothétique ordinateur quantique. De plus, ses vitesses de chiffrement et de déchiffrement sont bien meilleures que celles de schémas basés sur les problèmes de factorisation ou du logarithme discret. En contrepartie il présente l’inconvénient de nécessiter de très grandes tailles de clés.
La proposition originelle de McEliece repose sur l’utilisation des codes de Goppa binaires. Par la suite, d’autres familles de codes ont été proposées pour ce schéma de chiffrement dans le but de réduire la taille des clés. La principale exigence est d’avoir un algorithme de décodage rapide et corrigeant beaucoup d’erreurs. Par exemple (et cette liste est loin d’être exhaustive), les codes de Reed-Solomon généralisés, leur sous-codes et les codes Reed-Muller binaires. Tous ces systèmes sont soumis à des attaques en temps polynomial ou sous-exponentiel.
Les codes géométriques sont des codes d’évaluation de fonctions rationnelles sur des courbes algébriques. Leur bonne distance minimale ainsi que l’existence d’algorithmes de décodage efficace en fait d’intéressants candidats pour le schéma de McEliece, ce qui a motivé Janwa et Moreno à les proposer à des fins cryptographiques. Faure et Minder ont proposé une attaque structurelle de ce système lorsque les codes proposés sont construits à partir de courbes de genre g
