Séminaire de Cryptologie

Algebraic cryptanalysis can be described as a general framework that permits to asses the security of a wide range of cryptographic schemes. The recent proposal and development of algebraic cryptanalysis is now widely considered an important breakthrough in the analysis of cryptographic primitives. It is a powerful technique that applies potentially to a wide range of cryptosystems.

The basic principle of such cryptanalysis is to model a cryptographic primitive by a set of algebraic equations. The system of equations is constructed in such a way as to have a correspondence between the solutions of this system, and a secret information of the cryptographic primitive (for instance, the secret key of a block cipher).

The most efficient method for solving algebraic equations over a finite field is to compute a Gröbner basis. In the first part of this talk, we will give the definition/properties of such bases, and briefly recall the principle of efficient algorithms, i.e. F4/F4, for computing these bases.

In the second part of the talk, we will present two applications of algebraic cryptanalysis. The first application is an attack of MinRank (MR) which is an important problem in multivariate cryptography (joint work with F. Levy-dit-Vehel and J.-C. Faugère). The starting point is the Kipnis-Shamir attack. The second application is the algebraic cryptanalysis of the Flurry and Curry block ciphers (joint work with J.-C. Faugère). We will present a new approach which is based on the use of several well chosen correlated message/ciphertext pairs. This has permitted to establish an interesting connection between algebraic attacks and high order differential cryptanalysis.

In this talk we will present symbolic (in the sense of Dolev and Yao) models and techniques for proving whether a password-based protocol resists against (offline) guessing attacks.

We model protocols using a language close to the applied pi calculus. Resistance against guessing attacks is modeled using static equivalence, a formal indistinguishability relation on sequences of terms. We will present compositionality results: if two password protocols do separately resist against guessing attacks, does their parallel composition resist against guessing attacks (even when the same password is used)? If time permits we will also shortly present methods for automatically deciding resistance against guessing attacks.

Les schémas de Feistel ont été conçus pour construire des permutations de [1,2^(2n)], à partir d'applications (fonctions internes) de [1,2^n]. On s'intéresse ici aux attaques génériques sur les schémas de Feistel, dans le cas où les fonctions internes sont des permutations, au lieu de fonctions. Les attaques sont génériques dans le sens où les permutations internes sont supposées aléatoires. Malgré l'utilisation de tels schémas dans la conception d'algorithmes à clé secrète (ex : Twofish, Camelia, DEAL), ils n'ont pas été le sujet de nombreuses études. Nous allons voir que leur comportement est souvent différent de celui des schémas de Feistel classiques (avec fonctions internes). Plus précisément, nous allons voir que les attaques sont souvent moins efficaces, par exemple sur 3, 6 ou 9 tours de schémas de Feistel. Pour une taille d'entrée de 2n bits, les attaques trouvées nécessitent strictement moins de 2^(2n) messages quand le nombre de tours est inférieur ou égal à 5. Pour un nombre de tours plus grand, des attaques permettant de distinguer un générateur de permutations de Feistel (avec permutations internes) d'un générateur de permutations aléatoires seront également exposées.

Les fonctions éponges sont un nouveau type de primitives cryptographiques introduites par Bertoni et al. et utilisées pour la construction de fonctions de hachage. Elles représentent une solution de remplacement intéressante à l'algorithme d'extension de domaine classique de Merkle-Damgard et leur sécurité fut récemment prouvée dans le modèle de l'indifférentiabilité en supposant la fonction interne comme idéale.

Nous étudierons dans cet exposé la cryptanalyse d'une généralisation des fonctions éponges, tout d'abord d'un point de vue assez général avec les attaques par glissement. Ensuite, nous traiterons deux cas particuliers avec l'analyse de sécurité de Grindahl et de RadioGatun, deux fonctions de hachage récemment publiées et appartenant à la famille des fonctions éponges généralisées.

Travail commun avec David Naccache et Jean-Jacques Quisquater

Multiset hash functions are functions that map multisets (or sets) of arbitrary finite size to strings of fixed length. In this talk, I will introduce a new multiset hash function based on RSA. Its collision resistance is proven under the assumption that deterministic-padding RSA signatures cannot be forged.

Identity-based encryption (IBE) is a very attractive concept that allows a user to encrypt a message just using the identity of the recipient as a public key. IBE is thus very convenient to avoid key management. Recipient-privacy is also a major concern nowadays. To combine both, anonymous identity-based encryption has been proposed. A drawback of the above scenario is the presence of an authority which has the ability to decrypt any ciphertext. In this talk, we will consider the notion of anonymity with respect to the authority in the context of IBKEM, a primitive related to IBE and KEM. We discuss this new notion, together with a new kind of non-malleability with respect to the identity, for several existing schemes. Interestingly enough, such a new anonymity property has an independent application to password-authenticated key exchange. We thus come up with a new generic framework for password-authenticated key exchange, and a concrete construction based on pairings.

Les cryptosystèmes classiques utilisant des codes correcteurs sont pénalisés par la taille importante de leur clé publique. Les codes géométriques semblaient résoudre ce problème. Cependant, on est en mesure de conduire des attaques structurelles efficaces contre de tels codes. Les mécanismes de ces attaques seront exposés ici.

En cryptographie symétrique, de nombreuses attaques sur les chiffrements par bloc peuvent être regroupées au sein d'une même famille : les attaques statistiques. Citons par exemple les cryptanalyses linéaires et différentielles pour les plus connues.

Le cryptanalyste a possibilité de chiffrer (voire déchiffrer) un certains nombre de messages (de façon adaptative ou non) avec une boîte noire. Celle-ci est un chiffrement donné utilisant une certaine clef que le cryptanalyste souhaite retrouver. De l'observation de certains phénomènes dans les échantillons disponibles (messages), on peut tirer de l'information sur la clef afin de restreindre l'espace de recherche.

Le but de cet exposé est de montrer l'importance de la quantification de ces informations pour l'estimation de la complexité d'une attaque ainsi que de donner un aperçu des méthodes utilisées pour estimer cette information après avoir, dans un premier temps, expliqué le fonctionnement des cryptanalyses statistiques.

We describe the use of explicit isogenies to translate instances of the Discrete Logarithm Problem from Jacobians of hyperelliptic genus 3 curves to non-hyperelliptic Jacobians, where they are vulnerable to faster index calculus algorithms. We give explicit formulae for $(2,2,2)$-isogenies for any hyperelliptic curve defined over a finite field of characteristic $p > 3$. Subject to reasonable assumptions, we show that we can construct such an isogeny over the ground field for at least 18.57\% of all hyperelliptic genus 3 curves over a given finite field.