Résumé.

Le schéma du cryptosystème de Boneh-Franklin est basé sur les couplages, et utilise directement le secret comme argument de ceux-ci lors du déchiffrement.

Nous allons d'abord voir comment fonctionne les pairings, ainsi que l'algorithme utilisé pour les calculer, puis comment une attaque par fautes pourra nous permettre de récupérer le secret utilisé.

Résumé.

In this talk, we will give several results on the complex multiplication (CM) method for genus 2 curves and several results on orders in primitive quartic CM number fields. The main result is a generalisation of the complex analytic CM method to orbitrary orders. The algorithm computes class polynomials whose root system are invariants of genus 2 curves with prescribed endomorphism ring. In the literature, the maximal order is mainly considered. In primitive quartic CM fields, we will propose the beginning of a complete description of orders, stable by complex conjugation. Those orders are "strong" candidates for endomorphism rings of genus 2 curves. We will recall how to build models for those curves.

Résumé.

En 2014, Shresta et Kim ont proposé d'utiliser les codes polaires dans le cryptosystème de McEliece. Dans ce contexte, la clé publique est un code polaire permuté, tandis que la clé privée est un code polaire connu (à paramètres fixés, il n'existe qu'un seul code polaire).

La sécurité de ce cryptosystème repose donc sur la difficulté de retrouver la permutation utilisée. Une nouvelle approche de ces codes, et notamment la définition d'une nouvelle famille de code, les codes monomiaux décroissants, permet de déduire des propriétés algébriques (notamment leur groupe d'automorphisme) et de retrouver la permutation secrète.

Résumé.

La sécurité des protocoles cryptographiques à base de courbes repose sur la difficulté du problème du logarithme discret. Pour étudier ce problème, on considère le graphe suivant : les noeuds sont des courbes de genre 3 et les arêtes sont des isogénies entres les jacobiennes de ces courbes. Dans ce graphe, qu'on appele graphe d'isogénies, il y a deux types de noeuds : des noeuds hyperelliptiques forts, car le log discret est difficile, et des noeuds non-hyperelliptiques faibles, pour lesquels on dispose d'attaques efficaces. Dans cet exposé, on donne une méthode pour construire des courbes hyperelliptiques de genre 3 pour la cryptographie et on présente une approche pour étudier le log discret en genre 3, via le graphe d'isogénies.

Travail joint avec J. Balakhrishnan, K. Lauter et C. Vincent

Résumé.

The Rényi divergence is a measure of closeness of two probability distributions. We show that it can often be used as an alternative to the statistical distance in security proofs for lattice-based cryptography. Using the Rényi divergence is particularly suited for security proofs of primitives in which the attacker is required to solve a search problem (e.g., forging a signature). We show that it may also be used in the case of distinguishing problems (e.g., semantic security of encryption schemes), when they enjoy a public sampleability property. The techniques lead to security proofs for schemes with smaller parameters, and sometimes to simpler security proofs than the existing ones.

Résumé.

In this presentation, we prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. with the goal to resist to Overbeck’s structural attack are actually still vulnerable to that attack. We show that by applying the Frobenius operator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code but with a lower length. In particular, the code obtained by this way correct less errors than the secret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometric transformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existing techniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed.

A joint work with Ayoub OTMANI and Selestin NDJEYA.

Résumé.

La conception de chiffrements symétriques est aujourd'hui assez bien maîtrisée et dispose notamment d'un ensemble de critères permettant de s'assurer de la résistance aux principales cryptanalyses. Cependant, l'apparition récente de nouvelles applications aux exigences particulières impose de créer de nouveaux chiffrements qui doivent vérifier des contraintes si strictes qu'il faut parfois s'éloigner de ces critères. On peut par exemple évoquer l’avènement des petits objets connectés type puces RFID qui imposent de créer des algorithmes consommant peu d'énergie et occupant peu d'espace. Un autre domaine émergent est la cryptographie symétrique adaptée aux schémas de chiffrements homomorphes pour laquelle le degré multiplicatif doit être le plus faible possible.

Dans ce contexte il est primordial de réaliser une analyse minutieuse des nouvelles propositions pour déterminer quelles primitives peuvent être utilisées et lesquelles doivent être écartées.

Résumé.

Un des outils les plus puissants de la cryptographie sur les réseaux est le Gaussian sampling. À très haut niveau, il permet de prouver qu’on connaît une base courte d’un réseau, et ce sans dévoiler la moindre information sur cette base. Une grande variété de cryptosystèmes repose dessus.

Lors de cet exposé, je présenterai d'abord des outils statistiques et algorithmiques permettant d'améliorer le Gaussian sampling, que ce soit au niveau de sa vitesse ou de la sécurité qu'il offre.

Puis je présenterai deux cas d'utilisation, un schéma de signature et un schéma de chiffrement basé sur l’identité. Le premier fournit les signatures les plus compactes actuellement obtenues avec les réseaux, et le deuxième est près de mille fois plus rapide que ses homologues à base de couplages sur les courbes elliptiques.

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 (Wang et al., 2005). 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., 2015).

(Travaux communs avec Marc Stevens et Thomas Peyrin.)

Résumé.

In this presentation, we will in a first part develop a new software attack to retrieve a keys in a smart card. This is based on several assumptions and we will evaluate the coverage of this hypotheses. Then, in a second part we will develop the instanciation of an attack tree on a recent product (2013) and show how vulnerable an implementation can be.

Résumé.

DECT (Digital Enhanced Cordless Telephone) est un standard ETSI utilisé dans les systèmes de téléphonie sans-fil largement déployé dans les environnements domestiques et d'entreprise. On compte environ 800 millions de dispositifs DECT dans le monde. L'un des objectifs de ce standard est de protéger la confidentialité des communications à l'aide de mécanismes d'authentification et chiffrement des communications. Malheureusement, la sécurité de ces systèmes n'est pas infaillible et nous avons mis à jour plusieurs failles de sécurité permettant d'intercepter et de déchiffrer les communications sous certaines hypothèses. Je présenterai au cours de cet exposé quatre attaques, chacune basée sur des hypothèses différentes. Bien que testées et validées en laboratoire, ces attaques ne sont pas (encore) envisageables en pratique de par les conditions requises pour les mettre en oeuvre (e.g. accès physique au téléphone ou encore Known-Plaintext-Attack). Toutefois, nous proposons des contres-mesures afin de mitiger les risques liés à ces attaques et accroître la sécurité des communications.

Résumé.

L'utilisation d'aléas est un élément clé en cryptographie; des bits aléatoires sont nécessaires non seulement pour générer des clés, mais ils sont également souvent nécessaires dans l'exécution d'algorithmes cryptographiques. Dans la pratique, les bits aléatoires utilisés dans les protocoles cryptographiques sont générés par un processus de génération pseudo-aléatoire. Dans ce cas, la sécurité du système dépend bien sûr de manière cruciale de la qualité des bits produits par le générateur. Nous analysons les propriétés mathématiques de suites finies générées par des fonctions pseudo-aléatoires parmi lesquelles, la distribution, le degré et le poids des polynômes multivariés interpolant ces suites. Dans cet exposé, nous analyserons notamment ces notions de complexités pour la fonction pseudo-aléatoire de Naor-Reingold définie sur le groupe multiplicatif d'un corps fini et sur le groupe de points rationnels d'une courbe elliptique définie sur corps fini.

Résumé.

Dans le cadre de la mise en place du chiffrement systématique des données du laboratoire, nous avons cherché une solution logicielle permettant un démarrage autonome des systèmes (sans intervention humaine) et lié à notre infrastructure (les systèmes ne démarrent pas en dehors de notre réseau). Notre solution s'applique aussi bien aux serveurs qu'aux machines des usagers.

Nous souhaitions respecter quelques contraintes lors de la mise en place du chiffrement de nos données :

• chaque système doit avoir une passphrase différente.
• ne pas avoir à apprendre autant de passphrases que de systèmes chiffrés.
• pouvoir faire des interventions de maintenance en l'absence des usagers des machines.

Pour les serveurs, l'intérêt de notre solution réside principalement dans le fait que le démarrage ne nécessite pas la présence d'un opérateur pour saisir la passphrase. Pour les machines des usagers, la saisie d'une passphrase à chaque démarrage du poste est souvent vue comme une contrainte. De plus, pour les machines fixes qui ne sont pas redémarrées souvent, il y a un fort risque d'oubli de la passphrase par l'usager.

Par conception, notre solution procure une pseudo clef de séquestre pour chaque matériel enregistré dans le service. Actuellement, le client de déchiffrement (écrit en python) s'intègre au fonctionnement du système de déchiffrement des distributions Debian et Ubuntu. Notre solution est en place sur plus de 300 machines.

Résumé.

Thanks to the variants of pairings which decrease the length of the Miller loop, the final exponentiation has become a significant component of the global computation. I exploit the structure of BN curves to improve this computation. I will first present the most famous methods in the literature that ensure the computing of the hard part of the final exponentiation. I 'm particularly interested in the memory resources necessary for the implementation of these methods. Indeed, this is an important constraint in restricted environments. More precisely, I'm studying Devegili et al. method, Scott et al. addition chain method and Fuentes et al. method. After recalling these methods and their complexities, I determine the number of required registers to compute the final result, because this is not always given in the literature. Then, I will present new versions of these methods which require less memory resources (up to 37%). Moreover, some of these variants are providing algorithms which are also more efficient than the original ones.

Résumé.

Les nouvelles technologies ont profondément modifié nos usages mais ne sont pas que synonymes d’avantages pour leurs utilisateurs. Elles ont en effet de lourdes conséquences sur notre vie privée, ce qui est bien souvent sous-estimé. Les utilisateurs de moyens de paiement électronique ne réalisent par exemple pas toujours que leurs transactions peuvent révéler des informations particulièrement intimes à leur sujet, telles que leur localisation, leur état de santé ou mêmes leurs croyances.

Nous nous intéressons dans ce mémoire aux techniques cryptographiques permettant de concilier les exigences de sécurité traditionnelles et le respect de la vie privée. Dans une première partie nous étudions deux cas particuliers, celui du paiement anonyme et celui de l’authentification anonyme. Nous proposons de nouvelles constructions qui offrent une meilleure efficacité que les solutions existantes, ouvrant ainsi la voie à de réelles applications pratiques. Chacun de ces systèmes fait l’objet d’une étude de sécurité montrant qu’ils offrent de solides garanties sous des hypothèses raisonnables.

Cependant, afin de satisfaire des contraintes techniques souvent très fortes dans ces contextes, il peut être nécessaire d’optimiser ces constructions qui nécessitent souvent un nombre significatif de calculs. Dans une deuxième partie nous proposons donc des moyens pour améliorer l’efficacité des opérations et algorithmes les plus fréquemment utilisés. Chacune de ces contributions peut présenter un intérêt au-delà du contexte de l’anonymat.

Résumé.

We study the problem of factoring an RSA modulus N=pq in polynomial time, when p is a weak prime, that is, p can be expressed as ap=u_0+M_1u_1+...+M_ku_k for some k integers M_1,..., M_k and k+2 suitably small parameters a, u_0,... u_k. We further compute a lower bound for the set of weak moduli, that is, moduli made of at least one weak prime, in the interval [2^{2n},2^{2(n+1)}] and show that this number is much larger than the set of RSA prime factors satisfying Coppersmith's conditions, effectively extending the likelihood for factoring RSA moduli. We also prolong our findings to moduli composed of two weak primes.