- 21 mai 2014 – Chrysanthi Mavromati (Sogeti, UVSQ) : Attacks in the multi-users setting : applications to Even-Mansour and PRINCE
| Abstract : The multi-user setting is a very interesting practical scenario, which is sometimes overlooked in cryptography. Indeed, cryptosystems are designed to be used by many users, and usually cryptographers prove the security of their schemes in a single-user model (except in some cases such as key exchange, public-key encryption and signatures). In this setting, the adversary tries to recover keys of many users in parallel more efficiently than with classical attacks, i.e., the number of recovered keys multiplied by the time complexity to find a single key, by amortizing the cost among several users. In this presentation, we will first show that in the multi-user Even-Mansour scheme, all keys of L=N1/3 users can be found with N1/3+ε queries for each user (where N is the domain size). We will also consider the PRINCE block cipher (with 128-bit keys and 64-bit blocks) and we will present an attack which finds the keys of 2 users among a set of 232 in time 265. Finally, we will also describe a new generic attack in the classical model for PRINCE. Joint work with Pierre-Alain Fouque and Antoine Joux. |
- 30 avril 2014 – Frédéric de Portzamparc (Gemalto, UPMC) : Algebraic Cryptanalysis of McEliece-like cryptosystems with compact keys.
| Abstract : Introduced in 1978, the McEliece cryptosystem is the first code-based cryptosystem and one of the oldest public-key cryptosystem. One of its drawbacks is the tremendous size of its public key. To overcome this difficulty, a trend in code-based cryptography was to find Goppa and alternant codes whose generator matrix admits symmetries so as to reduce the storage cost for the associated McEliece cryptosystems. Faugère, Otmani, Perret and Tillich showed at Eurocrypt’10 that the private key is the solution of an algebraic system. When the public matrix has symmetries, they proved that the corresponding algebraic system can be drastically simplified, so that its resolution may become feasible by computing Gröbner bases. For many instances of symmetric schemes, the system could be solved with the algorithm F5 in up to a few hours. However, none of the systems derived from binary codes could be solved in practice. We extend this work to all the symmetric parameters proposed so far. To do so, we introduce a completely new way of exploiting the symmetries in the algebraic attack. The idea is roughly to reverse the symmetrization process. It reduces the key-recovery to attacking a code of much smaller parameters. We also improve the algebraic modelization of the private key and the elimination technique used in the resolution. We show results of practical attacks for encryption schemes and signature schemes, both over binary and non-binary fields. For almost all parameters, the private key could be recovered in times between a few seconds and a few hours by using the Magma software. For instance, we were able to recover the private key of a signature scheme using a binary public code of length 215 and Goppa degree equal to 12 in only 5.4 seconds. For an encryption scheme defined over F7, with length 1813 and Goppa degree 49, the key recovery took 60 seconds. By this work, we challenge the very idea of using Goppa codes with symmetry for cryptographic use. Joint work with J.-C. Faugère, A. Otmani, L. Perret and J.-P. Tillich. |
- 22 janvier 2013 – Francisco Vial-Prado (UVSQ) : Gentry’s blueprint for fully homomorphic encryption schemes.
| Abstract : We review Gentry’s ideas that led to the first fully homomorphic encryption scheme in 2009. First, we describe this scheme based on ideal lattices, and its implementation. We propose new chosen ciphertext attacks that may be adapted to other primitives using lattices. Finally, we describe the state of art of FHE and the latest improvements. |
- 15 janvier 2013 – Jérôme Plût (ANSSI) : New Insight into the Isomorphism of Polynomial Problem IP1S and its Use in Cryptography.
| Résumé : Le problème d’isomorphisme de polynômes IP1S est le suivant : étant données deux familles de polynômes (a_1,…,a_m) et (b_1,…,b_m) en n variables, calculer (s’il existe) un changement de variables linéaire transformant une famille en l’autre. Des instances difficiles de ce problème permettraient notamment de construire un schéma d’identification efficace. Dans ce travail, nous étudions la structure mathématique sous-jacente au cas de familles de deux polynômes homogènes de degré 2 et nous en déduisons un algorithme polynomial de résolution de la plupart des instances de IP1S. Nous utilisons pour cela des techniques légèrement différentes selon que le corps sous-jacent est de caractéristique impaire ou binaire. Travail commun avec Gilles Macario-Rat (Orange) et Henri Gilbert (ANSSI). |
- 8 janvier 2013 – Rodolphe Lampe (UVSQ) : Indifférentiabilité du schéma d’Even-Mansour Itéré.
| Résumé : Le schéma d’Even-Mansour Itéré est un blockcipher qui alterne des XOR de clés aléatoires et l’application de permutations aléatoires publiques. Par exemple, pour 1 tour: E(x)k1P1(xk0) avec k0, k1 aléatoires et P1 aléatoire publique. Ce schéma reprend la structure de la majorité des blockciphers actuels (par exemple l’AES), il est donc intéressant d’étudier sa sécurité structurelle. Depuis quelques mois, de nombreux résultats sur son indistinguabilité (i.e. le caractère aléatoire des sorties) ont été découverts, ainsi que récemment un résultat d’indifférentiabilité (le caractère aléatoire des sorties en autorisant l’attaquant à choisir les clés) pour certains key-schedules. Dans cet exposé, je présenterai une preuve d’indifférentiabilité pour 12 tours avec des conditions plus acceptables sur le key-schedule. |
- 18 décembre 2013 – Benoît Cogliati (UVSQ) : L’indistinguabilité du XOR de plusieurs bijections
| Résumé : Étant donné k bijections pseudoaléatoires f1, …, fk sur 0,1n, il est naturel de définir une fonction pseudoaléatoire en les XORant. S. Lucks a étudié la sécurité de cette fonction pseudoaléatoire. Nous améliorons les bornes de sécurité de son article en utilisant deux techniques de preuve : celle des coefficients H classique et la technique des coefficients Hsigma. |
- 11 décembre 2013 – Luca De Feo (UVSQ) : Algorithms for F_p-bar
| Abstract : Realizing in software the algebraic closure of a finite field $F_p$ is equivalent to construct so called « compatible lattices of finite fields », i.e. a collection of finite extensions of $F_p$ together with embeddings $F_p^m ⊂ F_p^n$ whenever $m | n$.
There are known algorithms to construct compatible lattices in deterministic polynomial time, but the status of the most practically efficient algorithms is still unclear. This talk will review the classical tools available, then present some new ideas towards the efficient construction of compatible lattices, possibly in quasi-optimal time. |
- 27 novembre 2013 – Jérémy Jean (ENS) : Structural Evaluation of AES and Chosen-Key Distinguisher of 9-round AES-128.
| Abstract : While the symmetric-key cryptography community has now a good experience on how to build a secure and efficient fixed permutation, it remains an open problem how to design a key-schedule for block ciphers, as shown by the numerous candidates broken in the related-key model or in a hash function setting. Provable security against differential and linear cryptanalysis in the related-key scenario is an important step towards a better understanding of its construction. Using a structural analysis, we show that the full AES-128 cannot be proven secure unless the exact coefficients of the MDS matrix and the S-Box differential properties are taken into account since its structure is vulnerable to a related-key differential attack. We then exhibit a chosen-key distinguisher for AES-128 reduced to 9 rounds, which solves an open problem of the symmetric community. We obtain these results by revisiting algorithmic theory and graph-based ideas to compute all the best differential characteristics in SPN ciphers, with a special focus on AES-like ciphers subject to related-keys. We use a variant of Dijkstra’s algorithm to efficiently find the most efficient related-key attacks on SPN ciphers with an algorithm linear in the number of rounds. The content of this talk is a joint work with Pierre-Alain Fouque and Thomas Peyrin, and appeared in a CRYPTO 2013 paper. |
- 23 octobre 2013 – Virginie Lallemand (INRIA) : Amélioration des attaques différentielles sur KLEIN.
| Résumé : L’apparition récente du besoin de sécuriser des supports de plus en plus miniaturisés tels que les cartes à puces et les puces RFID a amené la communauté cryptographique à concevoir des algorithmes spécifiques à bas coût. Ces nouveaux algorithmes doivent répondre à des contraintes spécifiques en matière de consommation d’énergie, de taille et de rapidité. KLEIN est une famille d’algorithmes proposée en 2011 par Gong, Nikova et Law pour répondre à ces besoins. La procédures de chiffrement est de type SPN et est basée sur 4 opérations de tour assez similaires à celles de l’AES, la grande différence résidant dans la taille des états et des boîtes S. Nous verrons dans cet exposé comment cette spécificité induit des faiblesses permettant de construire une cryptanalyse différentielle efficace et ainsi de casser KLEIN-64, la version à 64 bits de clef de KLEIN. |
- 16 octobre 2013 – Cécile Pierrot (UPMC) : Crible spécial de corps de nombres dans les corps finis et application aux courbes elliptiques bien couplées.
| Réasumé : Cet exposé porte sur un des deux problèmes de théorie des nombres sur lesquels reposent un grand nombre de protocoles cryptographiques actuels : le problème du logarithme discret. Nous nous intéressons ici à la résolution de ce problème dans les corps finis. L’objet de cet exposé est d’apporter un rapide aperçu des algorithmes actuels puis d’étendre le crible spécial de corps de nombres (SNFS), qui ne portait, jusqu’ici, que sur des corps de cardinal premier. Notre SNFS s’étend sur tout le domaine d’exécution du crible de corps de nombres général (NFS), et en améliore la complexité asymptotique. Il permet le calcul de logarithmes discrets dans des corps finis dont la caractéristique admet une représentation creuse adéquate, ce qui autorise son application sur des corps finis issus de procédés de couplage. |
- 9 octobre 2013 – Christina Boura (UVSQ) : Revisiting Impossible Differential Attacks.
| Abstract : Impossible differential attacks are among the most powerful forms of cryptanalysis against block ciphers. These attacks have been extensively applied, however, due to the fact that they are highly technical, many points still remain unclear. The aim of this work is to formalize the complexity evaluation of such attacks, and propose improvements for many of the most crucial steps. We concentrate in particular on certain points of the complexity analysis that seem to be not so well understood and propose a general framework to clarify and improve them. In parallel, we develop and implement a tool for mounting impossible differential attacks on Feistel constructions. We describe this tool and present applications on two recent lightweight ciphers, LBlock and Simon. By applying our methods, we obtain the best current attacks on both of these ciphers. This is a joint-work Marine Minier, María Naya-Plasencia and Valentin Suder. |
Séminaires CRYPTO 2013-2014