Orateurs invités
- Gilles Barthe Software Institute IMdea
- Conception, optimisation et vérification formelle de constructions cryptographiques
EasyCrypt est un outil formel pour raisonner sur la sécurité des constructions cryptographiques dans le monde calculatoire. Dans cet exposé, je présenterai les principes d'EasyCrypt, ainsi que certains développements récents: la vérification d'implémentations C, la synthèse de nouveaux schémas de chiffrement, et la vérification automatique d'hypothèses calculatoires dans le modèle générique.
- Alain Couvreur INRIA Saclay-Île de France, LIX
- Une attaque polynomiale du schéma de McEliece basée sur les codes de Goppa "sauvages"
Le schéma de McEliece est un schéma de chiffrement basé sur les codes correcteurs d'erreurs dont la sécurité repose sur la difficulté à décoder un code aléatoire. Parmi les différentes familles de codes algébriques proposées pour ce schéma, les codes de Goppa classiques sont les seuls à résister à toutes les attaques algébriques, et ce, depuis près de 35 ans. Dans cet exposé, je présenterai une attaque d'un genre nouveau, dite "par filtration" qui permet de retrouver la structure d'un code de Goppa "sauvage" (Wild Goppa code) construit à partir d'une extension de corps quadratique. Cette attaque consiste à utiliser des propriétés multiplicatives du code pour en calculer une filtration (i.e. une famille de sous-codes emboités) dont chaque élément est un code de Goppa classique. Les propriétés algébriques de cette filtration permettent ensuite de retrouver entièrement la structure du code utilisé comme clé publique. Cette attaque a été implémentée en Magma et permet de casser en moins d'une heure des clés proposées par Bernstein, Lange et Peters dont la sécurité était estimée supérieure à 128 bits (Wild McEliece, SAC 2010). Depuis l'introduction du schéma de McEliece, c'est la première attaque polynomiale sur des codes de Goppa classiques n'ayant aucune symétrie apparente.
- Caroline Fontaine CNRS Lab-STICC et Telecom Bretagne
- Calcul sur données chiffrées : de la théorie à la pratique
Les systèmes de chiffrement dits homomorphes permettent d'effectuer des calculs sur des données chiffrées, donc sans en connaître le sens ni la portée, le déchiffrement du résultat étant égal à ce qu'on aurait obtenu en effectuant le calcul directement sur les données en clair. Ces systèmes permettent ainsi de déléguer des calculs ou des traitements à des entités auxquelles on ne veut pas dévoiler les données. C'est donc une primitive essentielle pour assurer la confidentialité des données dans des applications de type Cloud Storage ou Cloud Computing. Parmi les traitements que l'on souhaite pouvoir réaliser sur des données chiffrées, on trouve des tests d'égalité ou de relation d'ordre sur des chaînes de caractères, mais aussi des traitements bien plus complexes, notamment pour le traitement de données multimédia, comme des techniques calculs de descripteurs SIFT, des techniques de compression, ou même des techniques de tatouage. Une grande partie de ces traitements n'était mathématiquement pas envisageables avec les schémas de la première génération, dits partiellement homomorphes, qui ne permettaient que les traitements très simples (ne faisant intervenir qu'un seul type d'opération, + ou ×), et le deviennent du moins en théorie avec les nouveaux schémas, dits complètement ou presque complètement homomorphes (qui supportent des traitements faisant intervenir un nombre arbitraire de + et un nombre éventuellement borné de ×) apparus depuis 2009. Néanmoins, la gestion de grands flux de données ainsi que l'exécution de traitements coûteux imposent des contraintes très fortes en termes de complexité si l'on souhaite que le système global soit opérationnel. Malheureusement, on ne disposait en 2012 que d'estimations de complexités asymptotiques de ces schémas, et très peu de résultats avaient été publiés quant à leur implémentation, si bien que l'on manquait de repères pour cerner à quel point on était proches ou non de leur déploiement effectif. Cet exposé présentera les résultats actuels en termes d'implémentation et de tests, montrant que si certaines applications sont encores uniquement d'ordre théorique (pour l'instant), d'autres sont aujourd'hui palpables.
- Antoine Joux CryptoExperts et UPMC
- Revisiting discrete logarithms in small/medium characteristic finite fields
In this talk, we present a new algorithm for the computation of discrete logarithms in finite fields of small characteristic. This algorithm combines several previously existing techniques with a few additional ingredients. Among those, the most notable is a new method for generating multiplicative relations with a "systematic side" by composing the polynomial (Xq-X) with homographies. This results in an algorithm of quasi-polynomial complexity for discrete logs in GF(qk) where k is close to q.
- Pierre-Jean Spaenlehauer INRIA Nancy, équipe CARAMEL
- Bases de Gröbner de systèmes structurés et applications en Cryptologie
De nombreux problèmes en cryptologie peuvent &ecrice;tre modélisés par des systèmes polynomiaux à coefficients dans un corps fini. Le développement de la cryptanalyse algébrique durant les dernières décennies a montré l'importance pour la cryptologie des algorithmes efficaces de résolution de ces systèmes, à la fois d'un point de vue théorique et pratique (par exemple les résultats récents de complexité et les records sur le logarithme discret dans les corps finis de petite caractéristique). Les systèmes polynomiaux qui apparaissent en Cryptologie possèdent souvent des structures algébriques héritées des propriétés des cryptosystèmes qu'ils modélisent. Nous exposerons des progrès récents sur la complexité des bases de Gröbner pour les structures déterminantielles (HFE, MinRank), multi-homogènes (McEliece, logarithme discret), et pour les systèmes booléens (QUAD). Ces résultats ont conduit à de nouvelles bornes de complexité pour la résolution de ces systèmes, et nous présenterons leur impact sur la sécurité de certaines primitives cryptographiques. Travaux communs avec Magali Bardet, Jean-Charles Faugère, Mohab Safey El Din et Bruno Salvy.
- François Xavier Standaert UCL Crypto Group
- How to Certify the Leakage of a Chip
Evaluating side-channel attacks and countermeasures requires determining the amount of information leaked by a target device. For this purpose, information extraction procedures published so far essentially combine a "leakage model" with a "distinguisher". Fair evaluations ideally require exploiting a perfect leakage model (i.e. exactly corresponding to the true leakage distribution) with a Bayesian distinguisher. But since such perfect models are generally unknown, density estimation techniques have to be used to approximate the leakage distribution. This raises the fundamental problem that all security evaluations are potentially biased by both estimation and assumption errors. Hence, the best that we can hope is to be aware of these errors. In this talk, we provide and implement methodological tools to solve this issue. Namely, we show how sound statistical techniques allow both quantifying the leakage of a chip, and certifying that the amount of information extracted is close to the maximum value that would be obtained with a perfect model.
