Salle Jacques-Louis Lions, INRIA Paris, 2 rue Simone Iff, Paris 12ème, Métro Dugommier (ligne 6)

• 10h00, François Morain, LIX, INRIA Saclay-Ile de France : Factorisation d’entiers — hier, aujourd’hui, demain
  Résumé : de tous temps, il y a eu des passionnés des nombres pour factoriser des entiers. De nos jours, c’est devenu un enjeu de sécurité. Les techniques ont évolué avec le temps, le matériel également. Après un bref survol du passé et du présent, nous présenterons l’algorithme de factorisation de Shor, qui fonctionne dans le modèle quantique, et qui sert de motivation à une grande partie des recherches sur les ordinateurs quantiques. Nous montrerons que l’arithmétique classique peut apporter son aide à certaines parties des implantations physiques de cet algorithme.
  Travail conjoint avec F. Grosshans, T. Lawson, B. Smith.
• 11h15, Pierre Karpman,  LIX, INRIA Saclay-Ile de France et NTU :  Collisions explicites pour la fonction de compression de SHA-1
  Résumé : Il y a dix ans, Wang et al. publièrent la première attaque théorique sur la fonction de hachage SHA-1 en montrant comment obtenir des collisions pour un coût d’environ 2^69 appels à  la fonction au lieu des 2^80 requis par une attaque générique (W2005). Ces travaux ont eu un impact considérable sur la recherche sur SHA-1 en particulier et sur les fonctions de hachage en général. Cependant, malgré plusieurs améliorations qui ont fait baisser le coût estimé de la meilleure attaque à  2^61 (Stevens, 2013), aucune collision n’a encore été publiquement calculée et beaucoup de travaux se sont concentrés sur l’attaque de versions réduites.Dans cet exposé nous présenterons des améliorations récentes de l’état de l’art sur trois points : 1) nous montrons comment monter des attaques sur la fonction de compression de SHA-1 plutôt que sur la fonction de hachage complète ; 2) nous avons explicitement calculé une collision pour la fonction de compression complète de SHA-1, pour un coût moyen estimé de 2^57 (ainsi que pour une version réduite à  76/80 tours pour un coût moyen de 2^50) ; 3) la recherche de collision a été implémentée sur cartes graphiques et a permis de démontrer l’intérêt de ce type de plateforme pour le calcul d’attaques de cryptographie symétrique (Karpman et al., 2015), (Stevens et al., 2016).

Travaux communs avec Marc Stevens et Thomas Peyrin.

• 14h15, Gwezheneg Robert, IRMAR, Université de Rennes 1 : Décodage des codes de Gabidulin généralisés
  Résumé : Les codes de Gabidulin sont l’analogue en métrique rang des codes de Reed-Solomon. Parmi leurs propriétés notables, ils sont optimaux et disposent d’algorithmes de décodage efficaces. Cela explique leur utilisation dans diverses applications, comme par exemple le codage espace-temps. Concevoir un tel code consiste à décrire une famille finie de matrices complexes, éloignées les unes des autres en métrique rang. C’est dans ce but que nous avons généralisé les codes de Gabidulin à des corps de nombres. Dans cet exposé, nous allons nous intéresser à leur décodage, et plus précisément à deux aspects de ce décodage.Nous commencerons par définir les codes de Gabidulin généralisés. Pour cela, nous présenterons les $\theta$-polynômes et la métrique rang. Nous établirons que ce sont des codes MRD (ils atteignent la borne de Singleton pour la métrique rang).La première partie est consacrée au décodage d’erreurs et d’effacements. Cela concerne aussi bien les codes originaux sur les corps finis que leur généralisation. Dans le modèle d’erreur seule, décoder un code de Gabidulin revient à résoudre un problème appelé reconstruction linéaire. Nous verrons un algorithme quadratique résolvant ce problème. Nous présenterons ensuite deux modèles d’effacements, et expliquerons que corriger des effacements revient à décoder un autre code de Gabidulin, avec des paramètres différents.Dans la seconde partie, nous allons considérer des codes dont les coefficients sont dans un anneau d’entiers. Nous serons alors confrontés à un problème spécifique aux corps infinis : la croissance des coefficients. Bien que le nombre d’opérations soit quadratique, la taille des nombres sur lesquels elles portent augmente exponentiellement, rendant l’algorithme inutilisable en pratique. Nous allons donc nous intéresser à la réduction des codes de Gabidulin généralisés, modulo certains idéaux de l’anneau des entiers. Nous montrerons que notre algorithme de décodage calcule le mot du code modulo cet idéal.
• 15h30, Marc Kaplan, TelecomParisTech : attaquer les cryptosystèmes symétriques en utilisant l’algorithme quantique de recherche de période
  Résumé : au milieu des années 90, la découverte par Peter Shor de l’algorithme qui porte son nom a révélé au monde que les ordinateurs quantiques, quand ils seront disponibles, seront une grande menace pour la cryptographie à clé publique telle qu’on la pratique aujourd’hui. Au coeur de cet algorithme se trouve une procédure de recherche de période dans un groupe. Dans notre exposé, nous montrerons que le plus simple algorithme quantique de recherche de période, connu sous le nom d’algorithme de Simon, peut également être utilisé pour attaquer la cryptographie symétrique.Pour certains groupes assez simples, l’algorithme de Simon permet de trouver la période d’un fonction avec O(n) requêtes quantiques à la fonction alors qu’il faut O(2^n) requêtes classiques. Cela permet de construire des attaques simples en faisant des requêtes en superposition à l’oracle cryptographique. Nous appliquons cette idée à plusieurs cryptosystèmes, incluant certains modes d’operation utilisés pour l’authentification ou le chiffrement authentifié, ainsi que des candidats à la compétition CEASAR. Enfin, nous montrons que les slide attacks reposent sur une structure similaire et peuvent être exponentiellement plus efficaces pour un adversaire quantique que pour un adversaire classique.

Amphi émeraude, Télecom Paris Tech, 46 rue Barrault

• 10:00. Pierre Loidreau « Codes cellulaires et applications cryptographiques »

Dans le domaine de la cryptographie à clé publique reposant sur les codes correcteurs d’erreurs, un problème essentiel pour les concepteurs de systèmes est de parvenir à gérer la très grande taille de clé publique nécessaire pour assurer une sécurité convenable. Un moyen consiste à utiliser des codes structurés tels les codes quasi-cycliques qui permettent des représentations compactes de la clé publique. Cependant, même si en théorie la sécurité des systèmes n’en est pas affectée, dans la pratique la structure algébrique sous-jacente est assez peu considérée dans la mise au point d’attaques par décodage. Dans cet exposé on étudiera une famille de codes généralisant la notion de codes quasi-cycliques. La matrice génératrice est formée de « cellules » qui sont des matrices carrées prises dans une algèbre de matrices engendrée par un polynôme. On montrera qu’un diviseur de ce polynôme permet d’engendrer des codes de paramètres plus petits. On décrira les effets de cette projection sur le décodage et la recherche de mots de petit poids dans des codes quasi-cycliques tant en métrique de Hamming qu’en métrique rang. On montrera comment cette approche peut réduire la complexité des attaques déjà connues, en fonction du poids du polynôme considéré ou bien de l’espace de ses coefficients. Les résultats soulèvent des questions sur l’existence  de polynômes particuliers qui divisent des polyômes de type $X^n-1$ dans des corps finis.
Bien que le sujet ne soit pas lié à la cryptographie à base de réseaux, on  montrera, si le temps le permet comment ces idées ont été appliquées ou pourraient être appliqués à des problèmes de décodage de type Ring-LWE.

• 11:15. Léo Ducas,  « Fast Fourier Orthogonalization »

The classical Fast Fourier Transform (FFT) allows to compute in quasi-linear time the product of two polynomials, in the circular convolution ring $\mathbb R[x]/(x^d -1)$ — a task that naively requires quadratic time. Equivalently, it allows to accelerate matrix-vector products when the matrix is circulant. In this work, we discover that the ideas of the FFT can be applied to speed up the orthogonalization process of a circulant matrix. We show that, when $n$ is composite, it is possible to proceed to the orthogonalization in an inductive way, leading to a structured Gram-Schmidt decomposition. In turn, this structured Gram-Schmidt decomposition accelerates a cornerstone lattice algorithm: the Nearest Plane algorithm. The results easily extend to cyclotomic rings, and can be adapted to Gaussian Samplers. This finds applications in lattice-based cryptography, improving the performances of trapdoor functions.

• 14:15. Philippe Langevin, Institut mathématique de Toulon, « propriété d’extension de la métrique de Lee »

Le théorème d’extension de MacWilliams affirme qu’une isométrie définie sur un code linéaire se prolonge  en une transformation monomiale, c’est-à-dire,  une isométrie de l’espace de Hamming tout entier. La question du  prolongement d’une isométrie à l’espace ambiant se pose pour toutes les métriques dans mon exposé je ferai le point sur des travaux récents concernant la propriété d’extension de la métrique de
Lee dans le cas des codes linéaires définis sur un corps premier.

• 15:30. Renaud Sirdey, CEA List, « Mise en œuvre pratique du chiffrement homomorphe »

Nous présentons des travaux d’implémentation du chiffrement (fully) homomorphe et de développement d’outils logiciels supports (compilateurs) permettant de faire le lien entre des algorithmes applicatifs et ce formalisme bas-niveau, de manière aussi performante que possible. L’exposé portera également sur les problématiques d’intégration du chiffrement homomorphe dans des cas d’applications concrets, en particulier pour ce qui est de son interfaçage avec du chiffrement symétrique. Enfin, nous essaierons de faire un point sur les performances actuelles et présenterons quelques scénarios applicatifs qui semblent aujourd’hui être à la portée du FHE.

Le prochain sémininaire CCA se déroulera le vendredi 12 juin à TélécomParisTech (46, rue Barrault) en amphithéâtre Emeraude.

• 10h00 : Johan Nielsen, LIX, INRIA Saclay-Ile de France, and somehow UVSQ – Power Decoding Reed-Solomon Codes Up to the Johnson Radius

Résumé : Power decoding, also known as « decoding using virtual interleaving » is a simple technique for decoding Reed-Solomon codes up to the Sudan radius. It is based on the classical approach of solving a « key equation » involving a special polynomial whose roots reveal the error positions. Since the inception of Power decoding, it has been an open question if it is possible to incorporate « multiplicities »: the parameter allowing the Guruswami-Sudan algorithm (G-S) to decode up to the Johnson radius.

In this talk I will describe how this can be done, and show how one can solve the resulting equations in an efficient manner using lattice basis reduction. This gives a new, simple decoding algorithm with the same decoding radius and speed as the G-S algorithm, but which does not need the additional root-finding step of the G-S. It has the drawback that it is a partial bounded-distance decoding algorithm, as it will fail for a few received words.

• 11h15 : Gilles Zémor, IMB, Université de Bordeaux – Combinatoire additive et théorie des codes

Résumé: un des objectifs de la combinatoire additive est de caractériser les parties S d’éléments d’un groupe telles que S+S soit de petite cardinalité. Le théorème de Vosper affirme en particulier que les ensembles d’entiers modulo p de plus petites sommes de parties ne peuvent qu’être des progressions arithmétiques, quelques cas dégénérés mis à part. Nous nous intéressons à la transposition de ces résultats dans des algèbres, notamment à la caractérisation d’espaces vectoriels S dont le carré S^2 engendre un espace vectoriel de petite dimension. Des transpositions du théorème de Vosper nous permettront d’affirmer que de tels espaces doivent admettre des bases d’éléments en progression géométrique. Des bornes de codage dans des espaces de formes quadratiques jouent un rôle crucial dans l’obtention d’une variante du théorème de Vosper dans les extensions de corps. Nous obtiendront également que sous quelques conditions, les codes de Reed-Solomon sont les seuls codes qui minimisent la dimension du produit de Schur de deux codes.

Travaux communs avec Christine Bachoc, Oriol Serra, et avec Diego Mirandola.

• 14h15 : Cédric Lauradoux, – Projet Privatics, INRIA Rhône-Alpes, Exploitations concrètes des mauvaises utilisations des fonctions de hachage

Résumé : L’avènement de SHA-3 pourrait laisser penser que tous les problèmes opérationnels liés aux fonctions de hachage sont résolus. Ce n’est malheureusement pas la cas car les propriétés des fonctions de hachage cryptographiques sont mal comprises. Les impacts de cette mauvaise compréhension vont de la re-identification (Gravatar,Navizon) au déni de service algorithmique. Pour illustrer les erreurs que l’on peut rencontrer, je présenterais 2 exemples: les problèmes de secondes pré-images et de saturation des filtres de Bloom et pour conclure l’utilisation de SHA-256 dans Google Safe Browsing.

• 15h30 : Christina Boura, Prism, Université de Versailles-Saint Quentin en Yvelines – Improving impossible differential cryptanalysis

Résumé : Impossible differential cryptanalysis is a powerful attack against block ciphers introduced independently by Knudsen and Biham et al. The idea of these attacks is to exploit differentials that have zero probability to occur in order to eliminate some key candidates. These attacks, even if extensively used, remain not fully understood because of their high technicality. We show in this talk how to derive general formulas for evaluating the data, time and memory complexity of this kind of cryptanalysis and we propose then several new techniques for optimizing these attacks. Finally, we show applications of these techniques for numerous block ciphers, such as the AES, CRYPTON, ARIA, CLEFIA, Camellia, LBlock and the SIMON family of ciphers. These attacks improve all previous impossible differential attacks and lead in some cases to the best known cryptanalysis against these ciphers.

This is a joint work with Virginie Lallemand, Maria Naya-Plasencia and Valentin Suder.

• Charles Bouillaguet, Laboratoire Cristal, université de Lille 1 – Systèmes de chiffrement par bloc minimalistes, obfuscation et implémentations en boite blanche

La plupart du temps, la sécurité des systèmes de chiffrement est évaluée en supposant que les adversaires interagissent avec le dispositif à travers une « interface », mais qu’ils n’ont pas le système de chiffrement sous la main pour étudier les détails de son fonctionnement interne. En effet, le fonctionnement de tels systèmes repose largement sur le fait qu’ils contiennent des informations secrètes (comme des clefs de chiffrement). Cette hypothèse est réaliste dans certains cas, par exemple si on communique avec un serveur web qui contient un mécanisme de chiffrement.

Cependant, dans bon nombre de situations, on a sous la main une implémentation soit matérielle soit logicielle du dispositif cryptographique, dont on peut donc observer le fonctionnement… et tenter d’extraire les secrets. On s’intéresse ici à cette deuxième situation. Est-il possible de concevoir des mécanismes cryptographiques contenant des secrets, mais dont le code source serait publiquement distribuable ? C’est en principe l’objet de la cryptographie à clef publique, mais on s’intéresse ici plus particulièrement à des constructions à clef secrète.

Le problème qui consiste à dissimuler des secrets cryptographiques dans du code source est un cas particulier du problème de l’obfuscation de programme, qui consiste à rendre incompréhensible et impossible à analyser le code de programmes arbitraires. Nous survolerons cette problématique dans l’exposé. Nous présenterons ensuite plusieurs systèmes de chiffrement par blocs, susceptibles de telles implémentations en boite-blanche. Ce sont pour certains des héritiers du système « 2R » conçu par J. Patarin en 1997.

Cet exposé est dérivé de l’article « Cryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key », disponible à l’adresse : http://eprint.iacr.org/2014/474.pdf

• Yannick Seurin, ANSSI – Analyse des algorithmes de chiffrement par bloc à clés alternées dans le modèle d’Even-Mansour

Les algorithmes de chiffrement par bloc dits « à clés alternées » (key-alternating ciphers) généralisent la classe des chiffrements SPN (Substitution-Permutation Network). Leur structure très simple consiste à appliquer répétitivement à l’état courant l’addition d’une clé de tour secrète et une permutation publique.

L’absence d’attaques génériques (i.e., indépendantes des permutations publiques utilisées) contre cette classe de chiffrements par bloc peut être analysée en modélisant les permutations publiques internes comme des permutations parfaitement aléatoires auxquelles l’attaquant n’a accès qu’en boîte noire. Ce modèle a été introduit par Even et Mansour (ASIACRYPT ’91) qui ont montré que pour un seul tour, le chiffrement par bloc résultant est sûr (plus précisément, pseudo-aléatoire) jusqu’à 2^{n/2} requêtes de l’adversaire à l’oracle de chiffrement et à la permutation interne, n étant la taille de bloc. Il a depuis été remis au goût du jour par un article de Bogdanov et al. (EUROCRYPT 2012) qui ont montré que pour deux tours, la borne de sécurité est repoussée à 2^{2n/3} requêtes de l’adversaire.

Dans cet exposé, nous présenterons un aperçu de travaux récents dans ce modèle qui ont permis non seulement d’améliorer la borne de sécurité en fonction du nombre de tours, mais également de montrer que la classe des chiffrements à clés alternées possède (pour un nombre suffisant de tours) de nombreuses propriétés plus fortes que le simple caractère pseudo-aléatoire, notamment la résistance aux attaques à clés reliées, à clés choisies, et l’indifférentiabilité par rapport à un chiffrement idéal.

• Olivier Blazy, XLIM, Université de Limoges – Protocoles d’échanges de clés

Les protocoles d’échanges de clés sont des primitives cryptographiques qui permettent à plusieurs utilisateurs de communiquer sur un canal non sécurisé via une clé de session sûre. Ce qui permet ainsi de créer des canaux virtuels sécurisés sur des réseaux non sécurisés. Un modèle général a été proposé par Bellare et Rogaway , mais dans le cas de l’authentification par mot de passe le problème s’avère plus ardu. (Du fait de leur petite taille, les méthodes d’attaque de type brute force se révèlent efficaces à cause du manque d’entropie).

Dans ce talk, nous nous intéresserons aux nouvelles techniques d’authentification par mot de passe, poignées de mains secrêtes, … et ceci au travers d’une méthodologie de preuves implicites. Pour celà, nous reviendrons sur des techniques existantes et montrerons leurs limitations, puis nous verrons des résultats récents permettant d’améliorer ces constructions pour les rendre plus sûres et plus efficaces.

• Florian Caullery, Université d’Aix-Marseille – Polynômes sur les corps finis pour la cryptographie

Les fonctions de F_q dans lui-même sont des objets étudiés dans de divers domaines tels que la cryptographie, la théorie des codes correcteurs d’erreurs, la géométrie finie ainsi que la géométrie algébrique. Les polynômes qui représentent ces fonctions peuvent présenter une multitude de propriétés ayant des applications intéressantes en mathématiques pures ou appliquées. Nous étudierons trois classes de polynômes particulières: les polynômes Presque Parfaitement Non linéaires (Almost Perfect Nonlinear (APN)), les polynômes planaires ou parfaitement non linéaire (PN) et les o-polynômes.

Les fonctions APN sont principalement étudiées pour leurs applications en cryptographie. En effet, ces fonctions sont celles qui offrent la meilleure résistance contre la cryptanalyse différentielle. Elles sont aussi particulièrement intéressantes en théorie des codes correcteurs d’erreurs car elles permettent de construire des codes 2-correcteurs.

Les polynômes PN et les o-polynômes sont eux liés à des problèmes de géométrie finie. Les premiers décrivent des plans projectifs et les seconds sont en correspondance directe avec les ovales et hyperovales de P^2(\F_q). Néanmoins, leur champ d’application a été récemment étendu à la cryptographie symétrique et à la théorie des codes correcteurs d’erreurs.

La classification complète des polynômes APN ou PN et des o-polynômes est un problème ouvert qui a attiré une multitude de mathématiciens depuis les années 50.

L’un des moyens utilisé pour compléter la classification est de considérer les polynômes présentant l’une des propriétés recherchées sur une infinité d’extensions de F_q. Ces fonctions sont appelées fonction APN (respectivement PN ou o-polynômes) exceptionnelles.

Nous étendrons la classification des polynômes APN et PN exceptionnels et nous donneront une description complète des o-polynômes exceptionnels. Les techniques employées sont basées principalement sur la borne de Lang-Weil et sur des méthodes élémentaires.

• 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

• Razvan Barbulescu, LIX, INRIA Saclay – Un algorithme quasi-polynomial pour le calcul du logarithme discret dans les corps finis de petite caractéristique.

Résumé : La sécurité des couplages en petite caractéristique repose sur la difficulté du calcul du logarithme discret dans les corps finis de petite caractéristique. L’algorithme le plus efficace jusque récemment était le crible de corps de fonctions (FFS), avec ses variantes. Ce dernier a une complexité sous-exponentielle, très proche de celle de la factorisation. Les records récents utilisant FFS ont montré que les couplages en petite caractéristique offrent une sécurité plus faible que celle estimée initialement. Mais ce sont les avancées de l’année 2013 qui ont amené une perte de sécurité très importante, rendant lesdits crypto-systèmes inutilisables.

Dans cet exposé, on s’inspire des avancés récentes de Joux et Göloglu et al., mais on n’utilise pas d’outils avancés comme les corps de fonctions et les bases de Gröbner.

L’algorithme consiste à exprimer le logarithme discret recherché comme une somme de logarithmes discrets d’éléments plus petits, pour une notion de taille qu’on va préciser. Ainsi on met en place un arbre dont les feuilles sont des éléments pour lesquels on connaît le logarithme discret. Étant donné que le temps passé à chaque nœud est polynomial et que le nombre de nœuds est quasi-polynomial, on obtient un algorithme quasi-polynomial.

Razvan.Barbulescu-10-01-2014 (format pdf)

• Philippe Gaborit, XLIM, Université de Limoges – Nouveaux résultats pour la cryptographie en métrique rang

Résumé: La cryptographie en métrique rang s’est développée à partir de 1991 et du cryposystème GPT qui est une adaptation du cryptosystème de McEliece en métrique rang.

L’intérêt principal de la métrique rang est que les meilleures attaques connues ont une complexité qui grandit très vite, permettant d’avoir des tailles de clés relativement petites de quelques milliers de bits. Cependant le système GPT étant basé sur des codes très structurés (les codes de Gabidulin qui sont en équivalent des codes de Reed-Solomon en métrique rang), il a fait l’objet d’attaques structurelles fortes et de réparations successives.

Dans cet exposé nous présenterons une nouvelle approche pour la cryptographie en métrique rang à partir d’une nouvelle famille de codes peu structurés décodables: les codes LRPC (Low Rank Parity Check codes), qui permettent d’avoir des tailles de clés de chiffrement de l’ordre de 1500b, tout en étant très rapides. On présentera aussi une nouvelle approche générale pour la signature basée sur les codes, qui à partir des codes LRPC permet d’obtenir un algorithme de signature très efficace avec des tailles de clé et de signature de seulement quelques milliers de bits. Enfin on présentera un nouvel algoritme générique d’attaque en métrique rang qui adapte efficacement les idées traditionnelles de l’approche Information Set Decoding.

Les resultats présentés sont issus de collaborations avec: O. Ruatta, J. Schrek et G. Murat (Univ. Limoges) et G. Zémor (Univ. Bordeaux).

• Christophe Clavier, XLIM, Université de Limoges – Rétro-conception de paramètres secrets d’AES par analyse de canaux auxiliaires et analyse de fautes

Résumé : Dans certains types d’applications des cartes à puce (notamment la téléphonie mobile ou la télévision à péage), les algorithmes de chiffrements ou fonctions d’authentification utilisés sont souvent ‘propriétaires’ c’est à dire que leurs spécifications sont tenues secrètes et connues seulement des opérateurs et fabricants des cartes. Pour des raisons économiques (éviter une étape de conception spécifique) ces fonctions sont parfois des variantes d’algorithmes publiques connus (DES, AES,…) dans lesquelles tout ou partie des paramètres les définissant ont été modifiés (par exemple en choisissant une boite de substitution différente). Dans ce cas, le secret de la fonction ne réside que dans un jeu de paramètres non divulgués. Dans cet exposé nous nous intéressons à la révélation des paramètres secrets des algorithmes propriétaires basés sur l’AES en considérant que tous les paramètres de l’AES ont pu être simultanément modifiés. Sous différents modèles, nous montrons comment un adversaire peut exploiter des fuites d’information apportées par l’observation de la consommation de courant (attaque de type SCARE) ou l’injection de fautes (attaque de type FIRE) pour retrouver les valeurs de ces paramètres. Certaines des attaques présentées révèlent les paramètres secrets y compris lorsque l’implémentation de la fonction cryptographique est protégée contre ces types d’attaques physiques par la présence simultanée de plusieurs contre-mesures.

• Nicolas Estibals, IRISA, Université de Rennes 1, Un algorithme pour trouver toutes les formules calculant une application bilinéaire.

Résumé : La multiplication est une opération arithmétique coûteuse comparativement à l’addition. Aussi il est intéressant, étant donné une application, de minimiser le nombre de produits à effectuer pour la calculer. Dans cette étude, nous nous restreignons au cas des applications bilinéaires.

En effet, parmi les applications bilinéaires, nous étions intéressés en premier lieu par la multiplication polynomiale. Ce problème ancien a déjà été très étudié. La première découverte fut celle de Karatsuba (1962) qui montra que l’on peut effectuer le produit de deux polynômes de degré 2 en n’utilisant que 3 produits au lieu de 4 avec l’algorithme quadratique. Puis Toom & Cook (1963) montrèrent que 5 multiplications suffisent à calculer le produit de polynômes de degré 3. En généralisant le problème aux polynômes de degré n fixé, on définit alors M(n) le nombre minimal de produits à effectuer pour une telle multiplication. Le calcul de M(n) est difficile et on ne dispose bien souvent que de bornes supérieures, de formules sans preuve de leur optimalité. En 2005, Montgomery effectua une recherche exhaustive de formules pour la multiplication de polynômes de degré 5 et trouva de nouvelles formules pour le degré 6 et 7.

Nous avons alors cherché à généraliser son approche et réduire son coût grâce à une formalisation en terme d’espace vectoriel. Nous présentons ainsi un algorithme permettant d’énumérer toutes les formules contenant exactement k produits calculant une application bilinéaire. Cet algorithme permet de calculer le nombre minimal de produits à calculer pour certaines applications bilinéaires.

Enfin, notre algorithme ne se restreignant pas au produit de polynômes, nous avons pu appliquer cet algorithme à d’autres problèmes tels que : le produit court, la multiplication dans une extension de corps ou encore de matrices.

• Daniel Augot, LIX, INRIA Saclay – Décodage des codes de Reed-Solomon et logarithme discret dans les corps finis.

En commun avec François Morain.

Alors que le problème associé au décodage des Reed-Solomon est connu pour être NP-complet, on se fait pas bien quelles sont les instances difficiles, ni si les codes de Reed-Solomon standard font partie de ce ces instances.

Dans le but d’analyser les codes standard, Cheng et Wan étudient depuis 2004 comment le logarithme discret sur les corps non premiers se réduit à un certain problème de décodage des codes de Reed-Solomon. Leur objectif est de prouver la difficulté du décodage des codes de Reed-Solomon, en présence d’un grand nombre d’erreurs, sous l’hypothèse que le logarithme discret est difficile.

Nous nous sommes proposés d’étudier la réduction dans le sens inverse: utilisation d’algorithmes de décodage connus pour construire un algorithme de calcul de logarithmes discrets sur les corps finis. La méthode est une méthode de calcul d’index, où la découverte de relations repose sur le décodage (des codes de Reed-Solomon). Nous avons utilisé des algorithmes de décodage unique, comme celui de Gao, par opposition au décodage en liste. Ces méthodes ont été implantées en Magma et NTL. Bien que cette méthode ne semble pas aussi performante que les méthodes classiques à la Adleman, il y a toutefois de nombreuses thématiques originales qui émergent.

• Franck Landelle, DGA MI – Cryptanalysis of Full RIPEMD-128

Travail commun avec Thomas Peyrin

Nous proposons une nouvelle méthode de cryptanalyse pour les fonctions de hachage double-branche qui nous permet sur le standard RIPEMD-128 d’améliorer grandement les résultats connus. Précisement, nous sommes capable de construire un très bon chemin différentiel en plaçant un chemin avec une partie non linéaire dans chacune des branches de la fonction de compression de RIPEMD-128. Ces parties non linéaires ne sont pas nécessairement sur les toutes premières étapes. Pour gérer les parties non linéaires des chemins différentiels, nous proposons une nouvelle méthode pour l’utilisation des degrées de liberté se déroulant 2 deux phases principales : la vérification des parties non linéaires et le merge des chemins des 2 branches via l’état initial. Nous obtenons la première collision sur la fonction de compression complète de RIPEMD-128 ainsi qu’un distingueur sur cette fonction de hachage. Les étapes de l’attaque ont été programmées et les expériences confirment nos raisonnements et complexités de l’attaque. Nos résultats montrent que l’une des dernières primitives de hachage de conception comptemporaine de SHA-1 non cassée n’était pas aussi sûre que prévue.

• Gaël Thomas, Université de Limoges – Diffusion dans les schémas de Feistel généralisés

Avec les réseaux substitution-permutation, les schémas de Feistel consti- tuent l’une des deux grandes familles de chiffrement par bloc. Popularisé par le DES, le schéma de Feistel a depuis subi de nombreuses généralisations visant à augmenter le nombre de blocs en lesquels est subdivisé le message. Ceci amène alors à se poser la question du nombre minimum d’itérations à effectuer pour « bien mélanger » ces blocs. Plus précisément, on s’intéresse ici à la notion de (délai de) diffusion qui est le nombre minimum de tours au bout desquels chaque bloc en sortie dépend de tous les blocs en entrée. Dans cet exposé, on se propose d’abord de faire un tour d’horizon des différentes familles de schémas de Feistel généralisés existantes puis d’en ex- hiber une représentation matricielle unifiée en lien avec la notion de diffusion. Finalement cette représentation permettra de définir une nouvelle classe de tels schémas bien adaptés pour des applications cryptographique

• Adeline Langlois, LIP, ENS Lyon – Classical Hardness of Learning With Errors

This work has been done with Z. Brakerski, C. Peikert, O. Regev and D. Stehlé.

The decision Learning With Errors (LWE) problem, introduced by Regev in 2005 has proven an invaluable tool for designing provably secure cryptographic protocols. We show that LWE is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.