Résumé du séminaire CCA du 28 novembre 2014

  • Aurore Guillevic, Equipe Grace, INRIA Saclay- Île de France et LIX – Polynomial selection for NFS-DL in non-prime finite fields

This talk is about the asymptotic and practical hardness of discrete logarithms in non-prime finite fields. This is needed to evaluate the security of e.g. pairing-based cryptosystems. The Number Field Sieve (NFS) algorithm is known to be the most efficient to compute discrete logarithms in prime finite fields and large characteristic finite fields. We are interested in adapting NFS for DL in GF(p^k), starting with k=2. NFS algorithm requires two number fields that can be embedded into GF(p^k). We introduce two new methods for polynomial selection, i.e. the choice of the two polynomials defining the two number fields involved in NFS. These methods provide an important practical speed-up for DL in GF(p^2) compared to DL in prime fields of the same size, as showed the recent record of DL computation in GF(p^2) (announcement at https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1406&L=NMBRTHRY&F=&S=&P=5520). Our methods have an asymptotic complexity of L(1/3,(64/9)^(1/3)). Moreover they can be applied in medium-sized characteristic and have in this case a better asymptotic complexity of L(1/3, (96/9)^(1/3)) instead of L(1/3, (128/9)^(1/3)).

This is a joint work with Razvan Barbulescu, Pierrick Gaudry and François Morain from the CATREL team.

  • Hoeteck Wee, LIENS, ENS, – Functional Encryption and its Impact on Cryptography

Functional encryption is a novel paradigm for public-key encryption that enables both fine-grained access control and selective computation on encrypted data, as is necessary to protect big, complex data in the cloud. In this talk, we provide a brief introduction to functional encryption, and an overview of its overarching impact on the field of cryptography.

  • Ayoub Otmani, LITIS, Université de Rouen – Key-Recovery Techniques in Code-Based Cryptography

An important step in the design of secure cryptographic primitives consists in identifying hard algorithmic problems. Despite the fact that several problems have been proposed as a foundation for public-key primitives, those effectively used are essentially classical problems coming from integer factorisation and discrete logarithm. On the other hand, coding theory appeared with the goal to solve the challenging problem of decoding a random linear code. It is widely admitted as a hard problem that has led McEliece in 1978 to propose the first code-based public-key encryption scheme. The key concept is to focus on codes that come up with an efficient decoding algorithm. McEliece recommended the use of binary Goppa codes which proved to be, up to now, a secure choice.

This talk will explore the important notion underlying code-based cryptography in order to understand its strengths and weaknesses. We then look at different extensions that lead to a wide range of variants of the McEliece scheme. This will give the opportunity to describe efficient and practical key-recovery cryptanalysis on these schemes, and to show the large diversity in the design of these attacks

  • 15h30 : Frédéric de Portzamparc, Gemalto – Polsys (Inria/UPMC/CNRS) – Algebraic Attack against Wild McEliece & Incognito

In this talk, we present a new algebraic attack against Wild McEliece & Wild McEliece Incognito, which are generalizations of the original McEliece cryptosystem introduced by Bernstein, Lange and Peters (BLP).

We prove that, thanks to the multiple factors in the Goppa polynomial, recovering the secret key for such schemes is equivalent to solving a system of polynomial equations whose solutions have the structure of a usual vector space. Consequently, to recover a basis of this vector space, we can greatly reduce the number of variables in the corresponding algebraic system. From these solutions, we can then deduce the basis of a GRS code. Finally, the last step of the cryptanalysis of those schemes corresponds to attacking a McEliece scheme instantiated with particular GRS codes (with a polynomial relation between the support and the multipliers) which can be done in polynomial-time thanks to a variant of the Sidelnikov-Shestakov attack. For Wild McEliece & Incognito, we also show that solving the corresponding algebraic system is notably easier in the case of a non-prime base field Fq.

To support our theoretical results, we have been able to practically break several parameters defined over a non-prime base field $q \in \{9,16,25,27, 32\}$, $t\leq 6$, extension degrees $m \in \{2,3\}$, and security level up to $2^{129}$ against information set decoding in few minutes or hours. Amongst others, we broke the hardest challenges proposed for q=27 by BLP (on the website http://pqcrypto.org/wild-challenges.html), which were out of the reach of the attack of Couvreur, Otmani and Tillich.

Joint work with Jean-Charles Faugère and Ludovic Perret.

Résumé du CCA du 06 juin 2014

  • 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

Résumé du séminaire du 10 janvier 2014

  • 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.

Résumé du séminaire du 18 octobre 2013

  • 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.

Résumé du séminaire du 28 juin 2013

  • Julia Wolf, Ecole Polytechnique – A quadratic Goldreich-Levin theorem

We present a local self-correction procedure for Reed-Muller codes of order 2 for functions at distance 1/2-epsilon from a codeword. This is an algorithmic analogue of Samorodnitsky’s tester for this problem, and to our knowledge, the first instance of a correction procedure beyond the list-decoding radius for any class of codes. It also forms the key ingredient of a « quadratic Goldreich-Levin theorem », which computes with high probability the large quadratic Fourier coefficients of a function in polynomial time.

This is joint work with Madhur Tulsiani.

  • Julia Pieltant, INRIA Saclay Île-de-France – Tours de corps de fonctions algébriques et algorithme de type Chudnovsky pour la détermination de bornes sur la complexité bilinéaire de la multiplication dans les corps finis.

On s’intéresse ici aux algorithmes de multiplication dans les corps finis, et plus précisément à la détermination de bornes sur la complexité bilinéaire de la multiplication dans une extension de degré n de F_q. On distingue en effet deux types d’opérations élémentaires : les opérations scalaires (additions, multiplications par des constantes) comptabilisées par la complexité scalaire et les opérations bilinéaires (multiplications de deux éléments de F_q dépendants directement des éléments de F_{q^n} dont on effectue le produit) comptabilisées par la complexité bilinéaire. Ce dernier type de complexité est indépendant de la base de F_{q^n} sur F_q choisie et correspond au rang du tenseur de la multiplication dans F_{q^n}.

L’algorithme de type évaluation-interpolation introduit en 1987 par D.V. et G.V. Chudnovsky est actuellement le meilleur algorithme de multiplication connu en terme de complexité bilinéaire : il a permis d’établir que le rang de tenseur de la multiplication dans F_{q^n} est linéaire en le degré n de l’extension considérée, et en fournit désormais les meilleures bornes connues dans le cas d’extensions de degré grand relativement au cardinal du corps de base.

Au cours de cet exposé, on présentera la dernière version de l’algorithme de type Chudnovsky, ainsi qu’une méthode d’obtention de bornes uniformes en n pour la complexité bilinéaire de la multiplication dans F_{q^n} sur F_q à partir de tours de corps de fonctions algébriques ayant de bonnes propriétés. En particulier, l’étude des tours de Garcia-Stichtenoth d’extensions d’Artin-Schreier et de Kummer qui atteignent la borne de Drinfeld-Vladut permet d’obtenir les meilleures bornes actuellement connues pour la complexité bilinéaire de la multiplication dans F_{q^n} sur F_q, pour tout q premier ou puissance d’un premier.

Julia.Pieltant-28-06-2013 (format pdf)

  • Antoine Joux, DGA et Université de Versailles – Logarithmes discrets dans les corps finis. Application en caractéristiques petite et moyenne

Cet exposé commencera par une introduction aux algorithmes génériques de calcul de logarithmes discrets. Ensuite, nous nous intéresserons aux algorithmes de calcul d’index dans le cas le plus simple: celui de la petite ou moyenne caractéristique. Après une présentation des algorithmes précédemment connus, nous montrerons comment une transformation simple de ces algorithmes permet un amélioration importante de la complexité asymptotique et conduit à de nouveaux records de calcul de logarithmes discrets.

  • Gaëtan Leurent, Université catholique de Louvain -« Differential Attacks against ARX Designs »

In this talk, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger; we introduce new multi-bit constraints to describe differential characteristics in ARX designs more accurately, and quartet constraints to analyze boomerang attacks. We describe an efficient way to propagate multi-bit constraints, that allows us to use the complete set of 2^32 2.5-bit constraints.

We have developed a set of tools for this analysis of ARX primitives based on this set of constraints. We show that the new constraints are more precise than what was used in previous works, and n detect several cases of incompatibility. In particular, we show that several published attacks are in fact fact invalid because the differential characteristics cannot be satisfied. This highlights the importance of verifying differential attacks more thoroughly.

Moreover, we are able to build automatically complex non-linear differential characteristics for reduced versions of the hash function Skein. We describe several characteristics for use in various ttack scenarios; this results in attacks with a relatively low complexity, in relatively strong settings. In particular, we show practical free-start and semi-free-start collision attacks for 20 rounds and 12 rounds of Skein-256, respectively. These are some of the first examples of complex differential trails built for pure ARX designs.

Gaetan.Leurent-28-6-2013 (format pdf)

Résumé du séminaire du 11 janvier 2013

  • Gilles Van Assche, – Keccak and permutation-based symmetric cryptography

In the last decades, mainstream symmetric cryptography has been dominated by block ciphers: block cipher modes of use have been employed to perform encryption, MAC computation, authenticated encryption and even internally in hash functions. One could therefore argue that the « swiss army knife » title usually attributed to the hash function belongs to the block cipher. In the last 5 years, Guido Bertoni, Joan Daemen, Michaël Peeters and I have proposed hashing (keyed or non-keyed), encryption (authenticated or plain) and other modes of use based on a fixed-length permutation rather than a block cipher. Such a permutation can be seen as a block cipher without a dedicated key input and can be constructed in the same way: by iterating a simple round function. Our modes, built on top of the sponge and duplex constructions, are simpler than the traditional block cipher modes and offer at the same time more flexibility. When designing a permutation suitable for this purpose, an obvious advantage is the absence of a key schedule. Moreover, thanks to the fact that the modes do not require the inverse permutation, there is also more freedom in the round function design than in the case of a block cipher.

This will be illustrated by the design of Keccak, which was submitted to the NIST SHA-3 competition and selected on October 2, 2012, to become the future SHA-3 standard.

Gilles.van.Asche-11-01-2012 (format pdf) Voir aussi keccak.noekeon.org, et sponge.noekeon.org

  • Anja Becker, – How to improve information set decoding exploiting that 1+1=0.

At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of n elements and density close to 1 in time O(2^{0.337n}0 and memory O(2^{0.256n}). This improved a 30-year old algorithm by Shamir and Schroeppel of running time O(2^{0.5n}) and memory requirement O(2^{0.25n}). In this talk we will present the following: Using the simple observation that the solution to the knapsack problem, a binary vector, can be represented by two overlapping vectors with coefficients in {-1,0,1} , we can obtain a better algorithm of running time O(2^{0.291n}). Furthermore, this technique can be applied to improve information set decoding attacking linear codes such as used in McEliece public key encryption. We can improve recent results on half-distance decoding such as Ball-collision decoding and May-Meurer-Thomae–ISD of asymptotic time complexity O({2^{0.056n}}) and O(2^{0.054n}), respectively. Previous attempts split the solution vector in disjoint parts. We search the solution as decomposition of two overlapping vectors which permits to reduce the running time to O(2^{0.049n}) in the asymptotic case. The talk is based on the publications: http://eprint.iacr.org/2011/474 http://eprint.iacr.org/2012/026\\ a joint work with Jean-Sébastien Coron, Antoine Joux, Alexander Meurer and Alexander May.

Anja.Becker-11-01-2012 (format pdf)

  • Emmanuel Prouff, – Partage de Secret et Preuves de Sécurité En présence de Fuites d’Information

L’implantation des algorithmes cryptographiques est particulièrement sensible aux attaques dites par canaux auxiliaires. Ces dernières sont capables d’extraire de l’information sensible grâce à l’observation du comportement du matériel sur lequel se déroule les calculs. Depuis leur introduction dans le milieu des années 90, la protection des implantations contre ce type d’attaques a servi de base à une nouveau domaine de recherche, soutenu à la fois par les milieux de la recherche industrielle et académique. Parmi les nombreuses approches proposées, un technique appelée masquage des données s’est imposée comme étant celle offrant les meilleures garanties de sécurité. Les méthodes utilisées pour masquer un algorithme se sont révélées être très proches des schémas roposés en théorie du calcul multipartie sécurisé (SMC en anglais). Au cours de mon exposé, je propose de dresser une état de l’art des techniques de masquage et d’identifier précisément les ressemblances et différences avec les problématiques étudiées en SMC. J’en profiterai pour montrer comment il est possible d’exhiber des bornes de sécurité pour les implantations protégées grâce au masquage.

  • Matthieu Legeay, -« Utilisation du groupe de permutations des codes correcteurs pour améliorer l’efficacité du décodage »

Résumé du séminaire du 29 juin 2012

  • Rafael Fourquet, Université Paris 8 Saint-Denis, – Décodage par liste des codes de Reed-Muller binaires

Nous présenterons un algorithme déterministe de décodage par liste des codes de Reed-Muller. Jusqu’à la borne de Johnson, sa complexité est linéaire en la longueur du code (complexité optimale pour un algorithme déterministe). Il s’agit d’une généralisation à tous les ordres de l’algorithme « sums » pour l’ordre un de Kabatianski-Tavernier (qui peut être vu comme le déroulement non-exhaustif d’une transformée de Fourier rapide). A titre d’exemple, nous appliquerons l’algorithme au calcul du profil de non-linéarité d’une fonction booléenne.

  • Nicolas Delfosse, Institut de mathématiques de Bordeaux, – Construction et performances des codes quantiques topologiques

Les codes topologiques sont des codes quantiques construits à partir de pavages de surfaces. Ces codes ont été introduits par Kitaev, qui a défini un code quantique en utilisant un pavage carré du tore. Après avoir rappelé la construction de Kitaev, nous verrons comment les paramètres du code quantique s’expriment géométriquement en fonction du pavage. Nous nous intéresserons aux codes de surfaces hyperboliques de Zémor, qui forment l’une des rares familles de codes LDPC quantiques de rendement constant dont la distance minimale est croissante. En utilisant des pavages hyperboliques 3-coloriés nous obtenons une nouvelle famille de codes topologiques. Nous verrons que ces codes couleur hyperboliques possèdent aussi un rendement constant et une distance croissante.

Nous nous intéresserons ensuite aux performances de ces codes sur le canal à effacement. Nous verrons que les codes construits à partir de pavages réguliers n’atteignent pas la capacité du canal. Ce résultat nous permet de mieux comprendre les propriétés nécessaires pour approcher la capacité du canal.

Enfin, nous appliquerons ce résultat à un problème combinatoire. En utilisant la ressemblance entre effacements quantiques pour les codes hyperboliques et phénomène de percolation, nous déterminons une borne sur le seuil de percolation d’une famille de graphes hyperboliques auto-duaux. Nous obtenons ainsi une borne en théorie de la percolation provenant de la théorie de l’information quantique.

Travail en commun avec Gilles Zémor.

  • Charles Bouillaguet, Université de Versailles-Saint-Quentin-en-Yvelines, – Symbolic Methods for the Automatic Search of Attacks Against Some Block Ciphers

Résumé. The block cipher cryptanalyst usually faces the following problem: she may interact with a black box containing the block cipher instantiated with a secret random key, and her goal is, in most cases, to retrieve this secret key using less time than exhaustive search and asking less encryptions/decryptions to the black box than the whole codebook. Several researchers had previously observed that the Advanced Encryption Standard (AES), the most widespread block cipher, had a relatively simple algebraic description over the field with 256 elements, because of its byte-oriented design. However, this property has not been harnessed by cryptanalysts to this day. In particular the (tempting) approach consisting in writing down the equations describing the AES, and trying to solve them directly using off-the-shelf tools such as SAT-solvers, has systematically failed to provide any result. In this talk, I will present the results we obtained using a slightly different method. We have designed tools that take as input a system of AES-like equations, and that search for an efficient ad hoc solving procedure. The result of these tools is the source code of a solver that can only solve the input system, but which can in some cases be efficient (its complexity can be predicted accurately). This solver can then be compiled and run to find the actual solutions. Our tools, which « reason » from the equations describing the AES (or similar looking symmetric primitives) are intrinsically symbolic, and they are inspired by standard tools from the field of automated deduction, such as the DPLL algorithm for SAT, the Knuth-Bendix completion algorithm, or the resolution algorithm for first-order logic. These tools found, nearly automatically, the best known Low-Data-Complexity attacks on reduced versions of the AES, and the best known attack on the full versions of AES-derived primitives, such as the Message Authentication code Pelican-MAC, and the stream cipher LEX.

Résumé à venir

  • Patrick Derbez, École normale supérieure, –Généralisation des attaques de Demirci et Selçuk

Résumé: En 2008, Demirci et Selçuk présentent de nouvelles attaques sur 7 tours d’AES-192 et d’AES-256 reposant pour l’essentiel sur la technique du meet-in-the-middle. Dans cet exposé nous montrerons que ces attaques appartiennent en fait à une classe plus générale d’attaques et que celles trouvées par Demirci et Selçuk n’étaient pas optimales. Nous discuterons également de la méthode utilisée pour exhauster cette nouvelle classe ainsi que des résultats obtenus.

Résumé du séminaire du 06 avril 2012

  • Carlos Aguilar, Université de Limoges, – De l’utilisation du produit tensoriel pour le chiffrement complètement homomorphe

Résumé : Très récemment d’importantes avancées ont été réalisées en cryptographie au niveau des systèmes de chiffrement homomorphe, outils permettant de réaliser des calculs sur des données chiffrées sans passer par les données en clair. L’obtention de ces outils, souvent décrits comme le Graal de la cryptographie, a été un des problèmes ouverts les plus importants de la cryptographie depuis trente ans.

Dans cet exposé nous montrons comment l’utilisation de primitives cryptographiques basées sur des problèmes autres que ceux de la théorie des nombres a permis de débloquer ce problème en présentant rapidement les grandes constructions et en se focalisant ensuite sur l’utilisation du produit tensoriel.

  • Sylvain Duquesne, Université de Rennes 1,- Représentation RNS des nombres et calcul de couplages

Résumé : Dans cet exposé, Je présenterai rapidement le système de représentation des nombres basé sur le théorème des restes chinois (RNS) et je montrerai comment et pourquoi il est bien adapté au calcul de couplages, en particulier pour les grands degrés d’extension comme pour les courbes BN et pour les implémentations matérielles (FPGA dans notre cas).

  • Elodie Leducq, Université Paris 7, – Rayon de recouvrement des codes de Reed-Muller généralisés

Résumé : Le rayon de recouvrement des codes de Reed-Muller a surtout été étudié pour les codes de Reed-Muller binaires. Dans cet exposé, nous nous proposons d’étendre certains résultats aux codes de Reed-Muller généralisés. Plus, précisément nous en donnerons un encadrement qui permet de le calculer pour un nombre pair de variables. Dans le cas d’un nombre impair de variable, nous améliorerons cet encadrement pour un corps à trois éléments.

  • Christophe Petit, Université Catholique de Louvain, –On polynomial systems arising from a Weil descent

Résumé : Polynomial systems of equations appearing in cryptography tend to have special structures that simplify their resolution. In this talk, we discuss a class of polynomial systems arising after deploying a ultivariate polynomial equation over an extension field into a system of polynomial equations over the ground prime field (a technique commonly called Weil descent). We provide theoretical and perimental evidence that the degrees of regularity of these systems are very low, in fact only slightly larger than the maximal degrees of the equations. We then discuss cryptographic applications of particular instances of) these systems to the hidden field equation (HFE) cryptosystem, to the factorization problem in SL(2,2^n) and to the elliptic curve discrete logarithm over binary fields. In particular, e show (under a classical heuristic assumption in algebraic cryptanalysis) that an elliptic curve index calculus algorithm due to Claus Diem has subexponential time complexity (2^{c\,n^{2/3}\log n})\) over the binary field GF(2^n), where c is a constant smaller than 7/3.

Based on joint work with Jean-Charles Faugère, Ludovic Perret, Jean-Jacques Quisquater and Guénaël Renault.

Résumé du séminaire du 03 février

  • 10h00-11h00 : Clément Pernet, Université Joseph Fourier,- Adaptive decoding for evaluation/interpolation codes

Résumé : We will present recent work on CRT (Chinese Remainder Theorem) and more generally codes based on an evaluation-interpolation scheme that include the better known Reed-Solomon codes. It was motivated in the study of algorithm based fault tolerance (ABFT) applied to parallel exact linear algebra.In this area, Chinese Remainder Theorem is used to split computations over integers or rational numbers into several computations over finite rings, allowing a simple parallelization. CRT codes enable the use of Chinese Remainder reconstruction with errors in some of the residues, provided that some amount of redundant information has been computed. We will first introduce a more general error model allowing to derive tighter bounds on the error correction capacities of such codes. Then we will describe two adaptations of the usual unique decoding algorithm (based on the extended euclidean algorithm), making the correction capacity adaptive. Several termination criteria allow to efficiently use these codes without knowing their parameters, and use the maximal amount of redundancy available for correction. Furthermore they make it possible to adapt fault tolerance in algorithms with early termination. We will lastly present some recent insights on the application of these adaptive decoding to a problem in computer algebra: interpolation of sparse polynomials with errors.

Clement.Pernet-03-02-2012 (format pdf)

  • 11h15-12h15 : Christophe Guyeux, Université de Franche-Comté,-Quelques avancées pour une approche topologique en sécurité informatique

Résumé : Nous nous intéressons à la possibilité de concevoir des machines de Turing au comportement imprévisible et désordonné. Le cadre théorique de cette étude est la topologie mathématique, avec de possibles ramifications dans les domaines de la complexité et de la théorie de la mesure. Les applications visées ont trait à la sécurité informatique et aux simulations numériques de phénomènes chaotiques. Cette conception et cette étude sont possibles en tenant compte des points suivants : de telles machines sont des processus itératifs, diverses distances naturelles sont envisageables, on peut donc étudier topologiquement le comportement de ces systèmes dynamiques. Nous nous focalisons en particulier sur les propriétés suivantes : régularité, transitivité, expansivité, sensibilité, mélange topologique, instabilité, entropies topologique et métrique, exposant de Lyapounov, etc.

Cette approche théorique prouve rigoureusement qu’il est possible d’obtenir du chaos sur machine, et ce de manière exacte et mathématiquement correcte. D’autre part, ce modèle nous donne la marche à suivre concrètement pour préserver intégralement toutes ces propriétés lors d’implémentations : l’espace sur lequel itérer est le produit cartésien entre les états finis de la machine et l’ensemble infini des rubans possibles. Ainsi, on doit itérer sur des vecteurs de bits, et prendre à chaque itérée une nouvelle entrée, si l’on veut se prémunir des cas dégénérés, et notamment éviter de boucler systématiquement. La situation idéale correspond aux traitements de flux audio ou vidéo.

Nous avons commencé par appliquer nos réflexions à des situations concrètes. Notre approche consiste à utiliser des algorithmes prouvés sûrs par la communauté, et à réaliser un traitement dessus de sorte que le nouvel objet a ses propriétés de sécurité préservées, et possède en sus de nouvelles propriétés de désordre topologique. Ainsi, nous avons détaillé comment réaliser un post-traitement sur une fonction de hachage de sorte que ses propriétés de résistance aux collisions et à la première préimage soient préservées tout en possédant de nouvelles propriétés reliées au caractère imprédictible de la valeur hachée 1,2. Dans le même esprit, nous avons proposé une approche pour mixer deux générateurs de nombres pseudo-aléatoires avec une fonction dont la suite récurrente est chaotique, de sorte que le nouveau générateur reste rapide, devienne parallélisable, possède une kyrielle de propriétés de désordre topologique tout en préservant des propriétés telles que l’uniforme distribution 3. De telles preuves s’appuient notamment sur la théorie des graphes et les chaînes de Markov. Ce générateur passe avec succès les tests DieHARD, NIST et TestU01, même quand les PRNGs fournis en entrée n’en sont pas capables. Enfin, dans le domaine de la dissimulation d’informations, nous avons proposé des schéma de tatouage et de stéganographie prouvés stégo-sûrs, et ayant de bonnes propriétés topologiques. Nous avons relié ces propriétés à des classes d’attaques jusqu’alors impossibles à étudier 4,5.

1 Jacques M. Bahi and Christophe Guyeux. Topological chaos and chaotic iterations, application to hash functions. In IJCNN’10, IEEE Int. Joint Conference on Neural Networks, pages 1–7, Barcelona, Spain, July 2010. Best paper award. (Conférence de rang A)

2 Christophe Guyeux et Jacques M. Bahi. A Topological Study of Chaotic Iterations. Application to Hash Functions. In Computational Intelligence for Privacy and Security (CIPS). Springer. Accepted paper, to appear.

3 Jacques M. Bahi, Jean-François Couchot, Christophe Guyeux, Adrien Richard. Chaotic discrete dynamical systems: why getting strongly connected iteration graph and how. In FCT’11, 18th Int. Symposium on fundamentals of computational theory. August 2011, Oslo, Norway. (rang A)

4 Jacques Bahi and Christophe Guyeux. A new chaos-based watermarking algorithm. In SECRYPT’10, Int. conf. on security and cryptography, pages 455–458, Athens, Greece, July 2010. SciTePress.

5 Nicolas Friot, Christophe Guyeux, et Jacques M. Bahi. Chaotic iterations for steganography – Stego-security and chaos-security. In SECRYPT’11, Int. conf. on security and cryptography, pages ***-***, Spain, July 2011.

  • 14h15-15h15 : Christophe Ritzenthaler, Université de MarseilleInvariants et courbes hyperelliptiques : aspects géométriques, arithmétiques et algorithmiques

Travail en commun avec Reynald Lercier.

Résumé : De nombreuses questions géométriques ou arithmétiques sur les courbes hyperelliptiques peuvent être étudiées grâce aux invariants des formes binaires. S’il est relativement standard de calculer un système générateur de ces derniers, il est par contre nettement plus difficile de retrouver une forme binaire d’invariants donnés. En particulier la résolution par les bases de Gröbner est hors de portée des ordinateurs actuels dans le cas générique. Nous montrerons comment palier à ce problème par l’utilisation de la notion de covariants et de la méthode de Mestre. Nous compléterons ces résultats en étudiant si la courbe peut être construite sur son corps des modules.

Christophe.Ritzenthaler-03-02-2012 (format pdf)

  • 15h30-16h30 : Gohar Kyureghyan, Université de Magdebourg, – Permutation Polynomials over Finite Fields: Proof Techniques

Résumé : Permutation polynomials describe the bijective mappings on finite fields and play an important role in both theoretical and practical aspects of finite fields. For example, mappings used for applications in Coding Theory or Cryptology are often required to be bijective in order to ensure a unique decoding/decryption or to provide a good resistance against several attacks.

There are very few known explicit families of permutation polynomials, because lack of efficient methods for proving that a given polynomial defines a permutation on infinite many finite fields.

In the talk we will present some of known classes of permutation polynomials and give the key ideas used for proving them.

Résumé des exposés du séminaire du 07 octobre

  • Matthieu Finiasz (ENSTA ParisTech) –  »Surcoût asymptotique en communication pour la protection de la vie privée dans une recherche par mots clefs »

Le chiffrement homomorphique (simplement homomorphique ou pleinement homomorphique) est un outil central des protocoles de protection de la vie privée. Il permet de chiffrer une requête qu’un serveur peut ensuite traiter (sans avoir à la déchiffrer) pour retourner une réponse que seul l’utilisateur peut déchiffrer. Ostrovsky et Skeith ont ainsi proposé en 2005 un protocole de recherche par mots clef, utilisant le cryptosystème de Paillier, permettant de masquer les mots recherchés. L’inconvénient principal de ce protocole (mis à part les calculs un peu lourds liés au chiffrement homomorphique) est le volume des communications : la taille de la requête et celle de la réponse du serveur.

Nous proposons deux variantes de ce protocole permettant d’optimiser ces communications en utilisant des codes correcteurs d’erreur : des codes de Reed-Solomon pour l’un, et des LDPC irréguliers pour l’autre. Asymptotiquement, le surcoût en communication lié à la protection de la vie privée peut devenir négligeable par rapport au volume des documents récupérés.

  • Christophe Guyeux (Université de Franche-Comté) – Annulé et reporté au 3 février
  • Maria Naya-Plasencia (Université de Versalilles-Saint Quentin)How to Improve Rebound Attacks (and New Applications)

Résumé : Rebound attacks are a state-of-the-art method for the analysis of hash functions.Such attacks are based on a well chosen differential path and have been applied to several hash functions from the SHA-3 competition, providing the best known analysis in these cases. In this talk, we will describe the main idea of rebound attacks, and we will show how can we improve most of them. This is done by identifying a common family of problems at the bottleneck of these attacks: « merging large lists with respect to a relation t ». Theses problems can be studied out of the rebound-attack context, and we provide several algorithms that efficiently solve some subcases, which are directly applicable to several practical instances.

Recently, we proposed new applications of this approach — recognizing an instance of the list-merging problem and applying the ad-hoc algorithm that solves it — which provide the best known analysis against the hash functions ECHO, JH (SHA-3 finalist) and the multipurpose primitive ARMADILLO2. We will describe the intuition behind these latest applications.