In this talk we present a very practical ciphertext-only cryptanalysis of GSM encrypted communication, and various active attacks on the GSM protocols. These attacks can even break into GSM networks that use ``unbreakable'' ciphers. We describe a ciphertext-only attack on A5/2 that requires a few dozen milliseconds of encrypted off-the-air cellular conversation and finds the correct key in less than a second on a personal computer. We then extend this attack to a (more complex) ciphertext-only attack on A5/1. We describe new attacks on the protocols of networks that use A5/1, A5/3, or even GPRS. These attacks are based on security flaws of the GSM protocols, and work whenever the mobile phone supports A5/2. We emphasize that these attacks are on the protocols, and are thus applicable whenever the cellular phone supports a weak cipher, for instance they are also applicable using the cryptanalysis of A5/1. Unlike previous attacks on GSM that require unrealistic information, like long known plaintext periods, our attacks are very practical and do not require any knowledge of the content of the conversation. These attacks allow attackers to tap conversations and decrypt them either in real-time, or at any later time. We also show active attacks, such as call hijacking, altering of data messages and call theft.

Joint work with Elad Barkan and Nathan Keller

Dans cet exposé, nous nous intéresserons à l'attaque de deux schémas de cryptographie asymétrique, à l'aide de techniques basées sur la réduction de réseaux. Dans un premier temps, nous montrerons comment, à partir d'un certain nombre d'entiers s dans Z_N tels que s mod p est "petit", il est possible de factoriser le module N = pq. On appliquera ensuite cette technique à l'attaque de deux schémas de signatures.

Nous verrons que les signatures à base de RSA (quel que soit l'encodage) et utilisant l'algorithme de Garner lors du calcul de l'exponantiation modulaire peuvent être attaquées avec cette méthode. L'attaque exploite l'information qui peut être obtenue par mesure de consommation de temps ou de courant indiquant si s mod p est inférieur à s mod q (ou s est une signature pour un message quelconque). Nous montrerons que dans le cas de modules légèrement déséquilibrés, il est possible de retrouver la clé secrète en quelques minutes.

Puis, nous nous intéresserons au schéma de signature Esign. Nous verrons que s'il est possible de connaître les bits de poids fort ou de poids faible des valeurs aléatoires utilisées lors de chaque signature, alors le module Esign N=p^2q se factorise à partir de la connaissance d'une cinquantaine de signatures seulement.

Les signatures numériques, alternatives électroniques aux signatures manuscriptes, subissent régulièrement des modifications pour satisfaire des applications particulières. Ces modifications, parfois contradictoires avec les traditionnelles propriétés d'intégrité, d'authentification et de non-répudiation, permettent d'enrichir la sécurité des schémas. En particulier, on cherche souvent à protéger le signataire, en lui assurant son anonymat.

Dans cet exposé, nous présenterons un certain nombre de ces schémas préservant l'anonymat du signataire, en se focalisant en particulier sur les signatures à vérificateur désigné, introduites en 1996 indépendamment par Chaum, et par Jakobsson, Sako et Impagliazzo. Nous définirons formellement ces signatures, en précisant une propriété d'anonymat pour le signataire, suggérée dès l'article de Jakobsson, Sako et Impagliazzo. Nous proposerons un schéma basé sur les couplages, qui est une variante de celui introduit à Asiacrypt'03 par Steinfeld, Bull, Wang et Pieprzyk.Puis nous proposerons une généralisation esquissée par Desmedt à la rump session de Crypto'03.

Travail en commun avec Damien Vergnaud (LMNO)

Nous montrons que le schéma d'encodage à plusieurs étages proposé par J.C. Carlach et C. Vervoux peut être utilisé pour construire des treillis cycliques. Cette propriété est exploitée sur plusieurs alphabets pour obtenir des treillis cycliques de faible complexité représentant des codes auto-duaux extrémaux. Les alphabets sur lesquels nous restreignons sont $GF(2)$, $GF(3)$, $Z_4$, GF(4) (cas euclidien et hermitien) et GF(5). Nous montrons que dans le cas binaire, il est possible d'obtenir des treillis cycliques à 16 états pour le code de Golay et deux codes auto-duaux extrémaux de paramètres $[32,16,8]$ et $[40,20,8]$, en partant du code de Hamming étendu de paramètres [8,4,4]. Dans le cas où l'alphabet est $Z_4$, cette construction donne des treillis cycliques à 256 états pour des codes de paramètres $(24,4^12,12)$ et $(32,4^16,12)$ (pour la distance de Lee) en se servant de l'octacode. Dans le cas ternaire, un treillis cyclique minimal à 9 états représentant le code de Golay ternaire est obtenu en utilisant un code auto-dual de paramètres $[4,2,3]$.

Travail commun avec Grégory OLOCCO, Université d'Orsay

Dans cet exposé, nous introduirons dans un premier temps la notion de métrique rang, en mettant en perspective ses similitudes et ses différences avec la métrique de Hamming. Nous présenterons ensuite la famille des codes de Gabidulin qui sont les analogues des codes de Reed-Solomon, à savoir que ce sont des codes d'évaluation de polynômes particuliers. De cette propriété, nous déduirons une approche nouvelle du décodage des codes de Gabidulin que l'on peut extraire des travaux de Öre de 1933 et 1934 sur la classe des polynômes linéaires. Cette approche repose sur une nouvelle approche du décodage en métrique rang du point de vue de la reconstruction de ces polynômes.

Dans un dernier temps nous présenterons des applications de la métrique rang notamment dans la conception de cryptosystèmes à clé publique de type McEliece, mais avec des tailles de clé plus petites. Ces systèmes furent développés à partir de l'article fondateur de Gabidulin, Paramonov et Tretjakov de 1991.

We present a new, efficient, tree-based signature scheme that is provably secure against adaptive chosen message attacks under the assumption that factoring large composites is computationally infeasible.

The scheme uses a tree with a large branching factor $l$, thus yielding a factor of $O(\log l)$ improvement in signatures length, computation and verification time compared to the only other known provably secure signature scheme equivalent to factoring (the classical result by Goldwasser, Micali and Rivest). Although flat-trees had been used before to construct provably secure signature schemes, the security was based on the possibly stronger RSA assumption.

joint work with Rosario Gennaro IBM T.J.Watson Research Center.

L'un des principaux outils utilisés en cryptographie est l'échange de clé, mécanisme qui consiste pour une ou plusieurs entités à se mettre d'accord sur une valeur secrète, dans le but de pouvoir utiliser d'autres outils cryptographiques (comme le chiffrement par exemple). La formalisaton de ce type de protocole, pour en étudier la sécurité, a connu beaucoup d'intéret ces dernières années.

Pour se protéger des intrus (personnes non autorisées à connaitre la clé), l'authentification des participants est nécessaire. Cette authentification peut se faire grace à d'autres clés déjà établies, ou par le biais d'un mot de passe. Nous étudierons dans cet exposé ce deuxième scénario, en explicitant les définition et le modele de sécurité spécifiques à ce contexte, puis en décrivant les protocoles, à deux joueurs et à n joueurs, qui sont prouves surs dans ce modele.

Apres avoir rappele quelques proprietes de la moyenne arithmetico-geometrique (AGM) et ses liens avec certaines formes et fonctions modulaires, je presenterai un nouvel algorithme permettant l'evaluation d'une large classe de formes et fonctions modulaires (dont la fonction modulaire elliptique j) avec une complexite quasi-optimale, et le comparerai a d'autres algorithmes existants.

L'application directe est le calcul de polynomes de classes (etape necessaire dans la construction de courbes elliptiques par multiplication complexe).

J'esquisserai eventuellement (selon le temps disponible) la generalisation de cet algorithme au genre superieur.

Nous introduisons un nouveau token sécurisé appellé Microprocesseur Externalisé (XmP) qui, à la différence d'une carte à puce classique ne contient pas de mémoire programme (ROM).

Le programme du XmP (OS, applications, ...) est totalement exporté vers un terminal sans confiance, et lui est envoyé dynamiquement pour être éxécuté. Bien que ce concept pose des problèmes de sécurité extrêmes, les avantages d'une carte à puce sans ROM sont innombrables: le masquage disparaît, la correction de bugs se réduit à une simple mise à jour au niveau du terminal, et bien sûr, la taille du programme cesse d'être un facteur limitant!

Nous proposons plusieurs techniques d'éxécution sécurisée de programmes. Le premier repose sur un nouveau schéma de vérification combinée de signatures RSA (RSA screening), et permet d'éxécuter des ecto-programmes sans traitement préalable au prix d'une certaine charge de calcul en cours d'éxécution. Le second, basé sur de simples MACs, est beaucoup plus rapide mais requiert une phase de précalcul.

La sécurité des deux techniques est formalisée dans un modèle d'attaque adapté et prouvée sous des hypothèses adéquates.

Nous présenterons l'algorithme d'Ajtai, Kumar et Sivakumar pour résoudre le problème du plus court vecteur d'un réseau Euclidien. Ce problème a été prouve NP-dur sous des réductions randomisées par Ajtai en 1996. Cet algorithme, présenté à STOC 2001, a une complexité probabiliste 2^O(n) en temps et en espace. Il bat donc la précédente borne de complexité (n^O(n)), qui correspond à l'algorithme de Kannan (1983).

En utilisant l'algorithme BKZ de Schnorr, cela permet d'améliorer la taille des vecteurs que l'on peut obtenir en temps polynomial. Il existe une controverse quant à la practicabilité de ce dernier résultat, du fait de la constante du O(.) de 2^O(n). Schnorr estime la complexité à O(poly(n).2³⁰ⁿ). Nous argumenterons pourquoi il s'agirait plutôt de O(poly(n).3ⁿ).

En-dehors de ces ameliorations de bornes de complexité, l'algorithme d'Ajtai, Kumar et Sivakumar apporte surtout un nouvel éclairage sur l'algorithmique des réseaux Euclidiens, en donnant une vision beaucoup plus géométrique que LLL.

Travail commun avec D. Lubicz.

Nous décrivons un algorithme de complexité $O(n^{2+o(1)})$ pour calculer la cardinalité de courbes hyperelliptiques ordinaires de petits genres définies sur $\F_{2^n}$. Cet algorithme découle d'idées dues a Jean-François Mestre. Une fois rappelée la littérature sur le sujet, et présentées les mathématiques sous-jacentes nécessaires, nous revisitons la méthode AGM pour les courbes elliptiques sous un jour nouveau. Nous proposons alors une généralisation au cas des courbes hyperelliptiques. Nous finissons par une description des outils algorithmiques nécessaires et donnons les résultats issues d'expérimentations pour le cas de courbes de genre un, deux ou trois.

Soit E une courbe elliptique définie sur un corps binaire F_{2^n}. L'opération inverse au doublement d'un point, appelée "point halving", peut être effectuée trois fois plus rapidement que le doublement. Il a été proposé (Eric W. Knudsen et Richard Schroeppel) de calculer le multiple d'un point en utilisant un algorithme de "division par 2-et-addition", qui est plus rapide que la méthode "doublement-et-addition".

Si les coefficients de la courbes sont définis sur un sous corps de F_{2^n}, il est alors possible d'utiliser l'endomorphisme de Frobenius de l'extension de corps pour remplacer le doublement. Comme le coût de l'application de l'endomorphisme à un point de la courbe est très faible, la multiplication scalaire est écrite en base d'endomorphisme et l'algorithme du calcul du multiple d'un point a alors une très bonne performance (la méthode du "point halving" n'est donc pas la plus efficace sur ces courbes dites de Koblitz).

Les deux notions précédentes ("point halving" et expansion en base d'endomorphisme) serons tout d'abord présentées. Puis, nous verrons comment combiner les deux méthodes pour calculer efficacement le multiple d'un point sur une courbe de Koblitz. Un gain de plus de 14% par rapport à la méthode d'expansion en base d'endomorphisme est ainsi obtenu. Ceci sans aucun précalcul supplémentaire.

(Travail en collaboration avec Roberto Maria Avanzi et Francesco Sica)

D.J. Bernstein a décrit une méthode pour calculer les nombres rationnels pour lesquels deux polynômes à coefficients rationnels ont simultanement des petits numérateurs et dénominateurs. Cette méthode est basée sur la réduction des réseaux par l'algorithme LLL et généralise plusieurs travaux antécédents (Hastad, Vallée, Girault, Toffin, Coppersmith, Boneh, Durfee....).

Nous présenterons cette méthode et nous intéresserons particulièrement à la résolution de certains problèmes diophantiens ayant des applications en cryptographie.

L'article de D.J. Bernstein est disponible à l'adresse http://cr.yp.to/ntheory.html#smallheight

On sait que, en moyenne, les codes linéaires aléatoires ont de très bonnes propriétés. Malheureusement, décoder dans de tels codes est un problème difficile. C'est le problème de "Syndrome Decoding" qui est NP-complet. C'est la difficulté de ce problème qui garantit en partie la sécurité de la plupart des cryptosystèmes à clef publique utilisant des codes correcteurs d'erreurs (McEliece, Niedereiter...).

Nous verrons comment, autour du Syndrome Decoding, il est possible de construire de nouvelles primitives cryptographiques. Après avoir regardé les systèmes classiques, nous explorerons deux exemples récents : un cryptosystème et une fonction de hachage.

Nous proposons un nouveau type d'attaquant à chiffrés choisis, qui complète le schéma classique (requêtes avant le challenge -CCA1-, requêtes avant et après le challenge -CCA2-), à savoir les attaques à chiffrés choisis post-challenge -CCAO2-. Ces attaquants sont contraints de ne poser des requêtes de déchiffrement qu'après avoir reçu le challenge. Ce nouveau modèle d'attaque entraine l'apparition de deux nouvelles classes de sécurité pour le chiffrement asymétrique: IND-CCAO2, les schémas sémantiquement sûrs contre ce nouveau type d'attaquant, et NM-CCAO2, les schémas non-malléables. Nous complétons alors le schéma des relations entre les différents niveaux de sécurité, en introduisant ces deux dernières notions.

Nous insisterons sur les résultats les plus surprenants, à savoir que CCA1 + CCAO2 n'implique pas nécessairement CCA2. Nous montrons en effet que toute requête, que ce soit avant ou après le challenge, a son importance (contrairement au cas du chiffrement symétrique).

• méthode de cryptanalyse "algébrique" permettant d'attaquer avec succès des systèmes à clé publique comme HFE ou à clé secrète (comme les registres filtrés).
• arithmétique efficace dans les jacobiennes de courbes superelliptiques.

• amélioration de plusieurs ordre de grandeur du calcul des bases de Gröbner dans les corps finis.
• utilisation de l'algorithme LLL polynomial pour effectuer certains calculs de base Gröbner.
• analyse asymptotique fine et résultats de complexité pour les systèmes algébriques ayant beaucoup plus d'équations que de variables.

Au cours de cet exposé, nous nous intéresserons à la monnaie électronique dite équitable. Dans ce type de paiement électronique, un utilisateur pourra effectuer des paiements de manière anonyme et une autorité habilitée pourra, en cas de fraude de la part d'un utilisateur, lever l'anonymat de ses transactions. L'un des schémas les plus efficaces a été élaboré par A. de Solages et J. Traoré et publié à la conférence Financial Cryptography 1998. Malheureusement, la sécurité de ce schéma, ainsi que celle des schémas de monnaie électronique antérieurs, repose sur des hypothèses cryptographiques non standard et n'avait pas été prouvée.

L'exposé se déroulera en deux parties. En premier lieu, nous rappellerons le concept de monnaie électronique ainsi que les différents outils cryptographiques nécessaires à leur mise en oeuvre. Ensuite, nous introduirons une variante du protocole d'A. de Solages et J. Traoré et nous prouverons sa sécurité (plus précisément, celle de l'utilisateur, l'anonymat) dans le modèle de l'oracle aléatoire, sous l'hypothèse, communément admise, de Décision Diffie-Hellman. Ces résultats, obtenus en collaboration avec J. Traoré, ont fait l'objet d'une publication à la conférence Financial Cryptography 2003.

Un réseau est un ensemble de points de R^n représentant les sommets de parallélépipèdes identiques pavant l'espace. Ce pavage peut être réalisé par translation d'un parallélépipède fondamental dont l'un des sommets est l'origine, les vecteurs définissant ce parallélépipède fondamental forment une base du réseau, ils le caractèrisent entièrement. Ayant une base d'un réseau, la recherche de points de celui-ci "assez proches" de l'origine est une question importante dans la mesure où elle apporte des solutions numériques à beaucoup de problèmes, notamment en cryptanalyse.

L'objet de cette présentation est l'étude d'algorithmes, publiés par Schnorr en 2002, qui marquent une nette amélioration théorique quant à la recherche de ces points proches de l'origine.

La cryptographie, ou science du secret, étudie depuis de nombreux siècles les notions de confidentialité, d'intégrité et d'authentification. Plus récemment, elle a aussi cherché les moyens de permettre à une entité de garder secrète son identité. Ainsi, la propriété d'anonymat permet à quelqu'un de se convaincre que l'émetteur d'un document possède certains droits sans pour autant connaître l'identité de ce dernier. Néanmoins, l'entité doit rester responsable de ce qui est écrit dans le document. L'un des outils cryptographiques utilisés pour l'anonymat est la signature de groupe.

Dans cette thèse, nous présentons dans un premier temps un état de l'art des schémas de signature de groupe et des principes de révocation de membre, puis nous donnons nos propres propositions basées sur l'hypothèse d'inviolabilité d'une carte à puce, celle-ci étant utilisée pour produire la signature. Nous abordons dans un second temps les applications des schémas de signature de groupe en introduisant un schéma efficace de vote électronique, un schéma d'enchères anonymes rapides et un schéma de monnaie électronique équitable prouvé sûr.