Année scolaire 2010-11

La sécurité des hyperviseurs

Le 05 octobre 2010 à 14:00 - Salle 106 à Jidé
Orateur : Amaury Gauthier (doctorant XLIM) et Clément Mazin (CDD Ingénieur XLIM)
Thème : Sécurité et cartes à puce - Public : Plutôt informatique

Après avoir été étudié dans les années 1970 et utilisé dans les mainframes, les hyperviseurs ont pratiquement disparu avec le développement des ordinateurs personnels. Depuis les années 2000, cette technologie a été remise au goût du jour pour être non plus utilisée sur des mainframes, mais sur de simples serveurs ou ordinateurs personnels x86.

Nous détaillerons dans un premier temps les techniques de virtualisation actuelles, ainsi qu'un exemple de faille. Dans un deuxième temps nous présenterons nos travaux sur la sécurité des hyperviseurs pour systèmes embarqués.

Présentation des thématiques de recherche en codes cryptographie et sécurité

Le 12 octobre 2010 à 14:00 - Salle 106 à Jidé
Orateur : à déterminer
Thème : Codes, Crypto et Sécurité - Public : Tout public

Dans ce séminaire, une série de présentations rapides introduiront aux élèves les thématiques de recherche présentes dans les équipes de recherche associées au master Cryptis.

Protocole d'identification zero-knwoledge basé sur les codes correcteurs avec cout de communication réduit

Le 19 octobre 2010 à 14:00 - Salle 106 à Jidé
Orateur : Julien Schrek (doctorant XLIM)
Thème : Codes et cryptographie - Public : Plutôt mathématique

Il va etre présenté un nouveau protocole d'identification en 5 passes avec une probabilité asymptotique de tricher de 1/2 et basé sur le problème de syndrome decoding. Ce protocole reprend le potocole d'identification de Stern présenté en 1996 mais avec 40% en moins de communications (18000b) et avec une clé publique bien plus petite. On peut aussi en déduire une signature en 90000b. Il sera fait une comparaison avec tous les protocoles qui ont successivement amélioré Stern ainsi qu'une présentation des performances du protocole sur processeur 8 bits.

Attaque par faute sur RSA par perturbation de la valeur du module

Le 02 novembre 2010 à 14:00 - Salle 106 à Jidé
Orateur : Christophe Clavier (professeur à l'Université de Limoges)
Thème : Attaques physiques et cryptographie - Public : Plutôt mathématique

Des attaques par analyse de faute sur RSA sont connues depuis plus de 10 ans. Eviter, ou au moins savoir détecter, des altérations des calculs de déchiffrement ou signature, ou des modifications des éléments privés de clé a rapidement été considéré comme de nécessaires contre-mesures. Toutefois, il a fallu attendre de nombreuses années avant qu'il apparaisse nécessaire également de protéger l'intégrité des éléments publics de la clé. Dans cet exposé, nous présenterons une des toutes premières attaques par fautes sur le RSA qui exploitent une perturbation volontaire de la valeur du module.

Algorithmes quasi-optimaux : aussitôt dit, aussitôt fait

Le 09 novembre 2010 à 14:00 - Salle 106 à Jidé
Orateur : Jean-Marc Couveignes (Professeur à l'université de Toulouse)
Thème : Algorithmes fondamentaux pour la crypto - Public : Plutôt mathématique

On apprend à l'école comment ajouter ou multiplier deux entiers. La division euclidienne et son application au calcul du PGCD viennent ensuite, et, plus tard, la multiplication des polynômes, puis des matrices. Pour chacun de ces problèmes, la méthode apprise à l'école est la plus facile à expliquer et la plus commode lorsque l'on traite des données de petite taille. Mais, d'un point de vue asymptotique, la méthode naïve n'est pas la meilleure, sauf pour l'addition. Pour multiplier deux nombres entiers, par exemple, il existe des algorithmes quasi-optimaux, c'est-à-dire des méthodes de calcul qui ne demandent pas (beaucoup) plus de temps qu'il n'en faut pour écrire le résultat. On ne peut donc espérer de meilleurs algorithmes. Ces méthodes de multiplication rapide utilisent la transformée de Fourier discrète. Inventées dans les années 1970, elles se sont répandues grâce à la micro-informatique et aux logiciels de calcul formel. Quant à la multiplication des matrices, Strassen et d'autres ont proposé depuis 1969 des méthodes théoriquement plus rapides que la méthode standard; mais on ignore s'il existe des algorithmes optimaux: multiplier deux matrices est aujourd'hui bien plus lent que de recopier le résultat. Majorer le rang du tenseur de multiplication des matrices est une question importante et difficile. Cohn et Umans on récemment reformulé cette question en termes de combinatoire et de représentations de groupes finis.

Dans la première partie de mon exposé je présenterai quelques uns de ces problèmes importants de complexité algébrique.

Je présenterai ensuite un travail commun avec Reynald Lercier, qui donne un algorithme quasi-optimal pour produire des polynômes irréductibles sur un corps fini, à l'aide de la théorie de Kummer des courbes elliptiques. La même question pour les entiers premiers reste ouverte.

Fuzzing sur cartes à puce

Le 16 novembre 2010 à 14:00 - Salle 106 à Jidé
Orateur : Matthieu Barreaud (ingénieur en CDD à XLIM)
Thème : Sécurité et cartes à puce - Public : Plutôt informatique

Les travaux sur le fuzzing ont montré que de nombreuses failles de sécurité peuvent être découvertes par des techniques d'injection de données invalides pour l'application testée. Aujourd'hui le fuzzing est devenue une méthode très largement utilisée pour tester une application ou rechercher des vulnérabilités. Nous verrons dans ce séminaire une application du fuzzing sur des cartes à puce afin de tester et vérifier l'implémentation d'un protocole.

Faiblesse du Key schedule de l'AES sous des attaques SPA

Le 23 novembre 2010 à 14:00 - Salle 106 à Jidé
Orateur : Antoine Wurcker (stagiaire XLIM)
Thème : Sécurité et cartes à puce - Public : Plutôt informatique

Les cartes à puce sont faites pour conserver des informations secrètes. Un des problème les concernant est qu'il est facile de calculer leur consommation électrique. Or les techniques de SPA (Simple power analysis) peuvent permettre de faire le lien entre consommation et informations traitées. Ici nous récupérons des informations sur l'étape de préparation de clef (key schedule) de l'AES-128 par SPA, pour ensuite mettre en corrélation ces informations pour parvenir à la clef cachée par la carte. Ce thème ayant déjà été aborde par Stefan Mangard dans un article de 2002, nous verrons en quoi nos hypothèses différent.

Virtdbg: un débogueur noyau utilisant la virtualisation matérielle

Le 30 novembre 2010 à 14:00 - Salle 106 à Jidé
Orateur : Damien Aumaître (Ingénieur R&D chez SOGETI)
Thème : Sécurité - Public : Plutôt informatique

L'observateur perturbe la mesure : cette règle s'applique aussi dans le monde de l'analyse dynamique de programmes, où le fait d'attacher un débogueur peut entraîner des effets de bords modifiant le comportement du système étudié. Ainsi, plusieurs codes malveillants tentent de détecter la présence d'un débogueur ou d'un environnement de virtualisation pour altérer leurs actions en conséquence.

Le projet virtdbg a objectif but de créer un débogueur fondé sur un hyperviseur minimaliste. Il est injecté directement dans la mémoire du système cible en utilisant un transfert DMA et offre un ensemble de primitives simples permettant de contrôler la cible (pose de points d'arrêt, lecture et écriture de la mémoire, gestion des exceptions, etc.) Ces primitives s'appuient sur les fonctions de virtualisation matérielle des processeurs Intel et AMD récents. Le système est très peu altéré et le contrôle est total.

Les communications entre l'hyperviseur et le débogueur reposent sur le protocole gdbserver, implémenté au-dessus d'un médium physique choisi pour minimiser l'impact sur le système à étudier (USB ou Ethernet). Ce protocole a par ailleurs comme avantage d'être compatible avec différents débogueurs comme gdb, IDA Pro, GenDbg, etc.

Cryptanalyse de cryptosystèmes basés sur des polynômes non commutatifs

Le 25 janvier 2011 à 14:00 - Salle 106 à Jidé
Orateur : Jean-Gabriel Kammerer (doctorant à l'université de Rennes 1)
Thème : Codes et Cryptographie - Public : Plutôt mathématique

Ten years ago, Ko et al. described a Diffie-Hellman like protocol based on decomposition with respect to a non-commutative semigroup law. Instantiation with braid groups had first been considered, however intense research on braid groups revealed vulnerabilities of the group structure and of the braid based DH problem itself.

Recently, Boucher et al. proposed a similar scheme based on a particular non-commutative multiplication of polynomials over a finite field. These so called skew polynomials have a well-studied theory and have many applications in mathematics and coding theory, however they are quite unknown in a cryptographic application.

In this talk, we will show that the Diffie-Hellman problem based on skew polynomials is susceptible to a very efficient attack. This attack is actually general in nature, it uses the availability of a one-sided notion of gcd and exact division. Given such tools, one can reduce the Diffie-Hellman problem to a linear algebra type problem.

Bases normales auto-duales

Le 08 février 2011 à 14:00 - Salle 106 à Jidé
Orateur : Stéphane Vinatier (MCF XLIM)
Thème : Théorie des nombres et Cryptographie - Public : Mathématique

Soient $p$ un nombre premier et $q$ une puissance de $p$. Les éléments du corps à $p$ éléments ${\mathbb F}_p$ sont les classes des entiers modulo $p$. Comment représenter les éléments du corps à $q$ éléments ${\mathbb F}_q$ ? Bien souvent en utilisant la structure d'espace vectoriel de ${\mathbb F}_q$ sur ${\mathbb F}_p$, c'est-à-dire en choisissant une base de ${\mathbb F}_q$ sur ${\mathbb F}_p$, dans laquelle chaque élément sera représenté par ses coordonnées. Différents types de bases ont été étudiés, ici on se concentre sur les bases \textit{normales auto-duales} : définition, propriétés, construction, ..., ainsi que des résultats numériques concernant leur \textit{complexité}, qui mesure la difficulté de calculer des produits dans une telle base.

Dans une deuxième partie, on s'intéressera à une famille particulière de bases normales auto-duales, dans le cadre des extensions cycliques de degré premier du corps des rationnels, et on donnera des pistes pour tenter de déterminer leur complexité (travail en cours).

Tous les travaux présentés sont le fruit d'une collaboration avec François Arnault (Limoges) et Erik Pickett (Lausanne).

Stéganographie et codes correcteurs d'erreurs

Le 22 février 2011 à 14:00 - Salle 106 à Jidé
Orateur : Mohamed Bouye Ould Medeni (invité XLIM)
Thème : Codes et Cryptographie - Public : Plutôt mathématique

L’idée du codage matriciel (en anglais : ”Matrix encoding”) a été introduite en stéganographie par Crandall en 1998[1]. L’implémentation a ensuite été proposée par Westfeld avec l’algorithme de stéganographie F5[2]. L’objectif est de transmettre un message dans une image en modifiant celle-ci, mais avec la contrainte de minimiser le nombre de pixels de l’image modifiés. Depuis 2001, des codes plus performants ont été utilisés pour réaliser le codage matriciel : algorithme Modified Matrix Encoding : MME[3], algorithme FastBCH[4], algorithme basé Reed-Solomon (RS)[5]. L’insertion est toujours baée sur le calcul de syndrome, mais les codes utilisés possèdent une efficacité d’insertion (e=nombre de bits du message/nombre de coefficients modifiés) meilleure que celle du code de Hamming utilisée dans F5. Une autre évolutiondes codes matriciels été également proposée à travers les ”codes à papier mouillé”[6], et consiste à sélectionner les sites d’insertion du côté codeur, mais avec un décodeur ignorant les sites sélectionnés. Cet algorithme insère les données dans des média numérique (par exemple, les pixels d’une image, ou les coefficients DCT,...etc). La contrubtion pour ce papier est de diminuer la complexité, pour qu’il soit linéaire et non pas exponentiel.

Mots-clé : Steganography, Error-correcting code, average distortion, matrix encoding, embeding, efficient, sécurité, image, Majority Logic Decoder.

Références

[1] R. Crandall Some notes on steganography, available at http ://os.inf.tu-dresden.de/ westfeld/crandall.pdf, 1998.
[2] A. Westfeld (eds.), F5 steganographic algorithm, In I.S Moskowitz diteur : proc Information Hiding 4th International Workshop, IHW 2001.
[3] Y. Kim, Z. Duric, D. Richards : Modified matrix encoding technique for minimal distortion steganography. In : Camenisch, J.L., Collberg, C.S., Johnson, N.F., Sallee, P. (eds.) IH 2006. LNCS, vol. 4437, pp. 314-327 (2007).
[4] R. Zhang, V. Sanchev, H. J. Kim : Fast BCH Syndrome Coding for Steganography. In : Katzenbeisser, S. and Sadeghi, A.-R (Ed.) Information Hiding 2009, IH’2009, LNCS 5806, pp. 48- 58, 2009, Springer-Verlag Berlin Heidelberg 2009.

Lattice-Based Digital Signatures from Low-Density Compact Knapsacks

Le 08 mars 2011 à 14:00 - Salle 106 à Jidé
Orateur : Vadim Lyubashevsky (CR1 INRIA à l'ENS)
Thème : Cryptographie et réseaux euclidiens - Public : Plutôt mathématique

I will describe a new lattice-based signature scheme which is based (in the random oracle model) on the conjectured hardness of a natural average-case problem which can be seen as a hybrid between the Ring-LWE and the NTRU assumptions. Our assumption roughly states that if we pick a polynomial r uniformly at random from a particular polynomial ring R, and polynomials s_1,s_2 at random from a small subset of R, then the pair (r,rs_1+s_2) is computationally indistinguishable from a uniformly random element in R x R.

I will explain why, given the current state-of-the-art of lattice algorithms and techniques for lattice protocol construction, this new assumption is more natural to use for building efficient signature schemes than the SIS and Ring-SIS assumptions upon which all current provably-secure lattice-based signatures are based. In our scheme, signing and verification require just a few polynomial multiplications and random oracle queries, and the resulting signature length is under 9000 bits, which is a factor of six shorter than any previous lattice-based scheme of comparable security that also possesses a security reduction.

AREMES, Methode automatisée de rétro-ingénierie par exploitation des cannaux cachés.

Le 15 mars 2011 à 14:00 - Salle 106 à Jidé
Orateur : Francois-Xavier Aranda (doctorant Thales-XLIM)
Thème : Sécurité et Cartes à puce - Public : Plutôt informatique

Le principe de notre méthode est de retrouver, à partir de la consommation en courant d'un système d'information (microcontrôleur, cartes à puces…), les instructions exécutées par ce dernier.

Pour se faire nous étudions le système pour en tirer une empreinte caractéristique susceptible d'expliquer le comportement de la consommation en fonction des instructions. Cette empreinte sera basée sur  différentes variables inhérentes au code exécuté et suivant un modèle de consommation basée sur le poids de hamming des données manipulées par le système. Ces variables pourront être, par exemple, le poids de hamming d'une instruction, la distance de hamming entre deux instructions successives ou encore le poids de hamming des données manipulées par une instruction.

Durant cette phase d'étude, nous disposons d'une plateforme ouverte sur laquelle nous pouvons exécuter nos propres code sample. Nous utilisons la régression multilinéaire pour estimer la consommation en fonction des variables citées plus haut. Puis, nous comparons l'estimée obtenue avec la courbe originale pour trouver la combinaison de variable fournissant l'estimation la plus fidèle à la consommation.

Pour retrouver les instructions correspondant à une consommation donnée, nous évaluerons le score d'accointance avec cette dernière pour une séquence d'instructions données. Ce score sera directement dépendant des variables misent en exergue à l'étape précédente. Ainsi, en effectuant une recherche non exhaustive des séquence d'instructions possibles grâce à un algorithme d'intelligence artificielle (algorithme génétique, min-max…), nous espérons pouvoir retrouver la séquence d'instructions possédant le meilleur score et pouvant être proposée comme solution.

Scalar multiplication on smart cards and side-channel analysis

Le 03 mai 2011 à 14:00 - Salle XR203 au bâtiment XLIM
Orateur : Vincent Verneuil (doctorant à l'IMB)
Thème : Attaques par canaux cachés - Public : Plutôt mathématique

Scalar multiplication is the main operation of Elliptic Curve Cryptography. Its implementation on smart cards in an industrial context requires much effort in order to satisfy performance and security goals. Indeed short timing execution are required in many applications and must be achieved given the power and memory constraints of the smart cards. On the other hand the well known side- channel analysis can threaten the secrets manipulated by the card, such as secret scalars. Therefore numerous studies have proposed solutions for speeding-up the elliptic curve scalar multiplication and counterfeiting side-channel attacks. Not all of these solutions fit to the industrial smart card context however.

Génération de tests de vulnérabilité pour vérifieur du typage de Java Card

Le 17 mai 2011 à 11:00 - Salle 106 à Jidé
Orateur : Aymerick Savary (étudiant en master à Sherbrook)
Thème : Sécurité et cartes à puce - Public : Informatique

Le vérifieur de byte code est un élément essentiel dans la sécurité de la plate-forme Java Card. La génération de tests pour vérifier son implémentation est impérative. Cependant, la complexité d’un plan de test ne peut se faire à la main tout en assurant une bonne couverture. Il devient intéressant d’automatiser leur génération. Dans notre approche, l’utilisation de méthodes formelles pour cette génération est un atout considérable, tant pour trouver un préambule, un postambule ou l’ensemble des cas de test de chaque instruction. Nos tests s’appliquent uniquement à des tests de vulnérabilité. Ainsi, on s’assure qu’un comportement rejeté par le modèle l’est aussi par son implémentation. Nos résultats montrent que les techniques mises en place permettent d’atteindre un tel objectif sur un langage simplifié.

 

Utilisation du groupe de permutations d'un code-correcteur pour améliorer les algorithmes génériques de décodage

Le 31 mai 2011 à 14:00 - Salle XR203 au bâtiment XLIM
Orateur : Matthieu Legeay (Doctorant à l'IRMAR)
Thème : Codes correcteurs - Public : Plutôt mathématique

Le décodage par maximum de vraisemblance d'un code-correcteur linéaire binaire est un des grands problèmes en théorie des codes-correcteurs. Il a été montré NP-difficile. Cependant, aucun des algorithmes de décodage génériques des codes-correcteurs d'erreurs ne prennent en compte le groupe de permutation des codes. On verra deux façons distinctes d'utiliser cette information sur le code pour améliorer les algorithmes existant.
La première idée fut lancée par MacWilliams en 1964 concernant les codes cycliques. Elle présentait un algorithme basée sur les ensembles d'information. Nous montrerons une évaluation théorique avec un cas particulier de permutation (travail réalisé en commun avec Christophe Chabot).
La seconde idée est basée sur l'utilisation d'un sous-code (\sigma-code) du sous-code idempotent d'un code. Nous montrerons des bornes sur la dimension du \sigma-code pour une permutation particulière \sigma et nous expliquerons comment utiliser cette information pour le décodage.

Test de Sécurité à Partir de Modèle par Analyse des Partitions et Classification

Le 21 juin 2011 à 14:00 - Salle 106 à Jidé
Orateur : Mohammed Bennatou (université de Kenitra)
Thème : Sécurité et cartes à puce - Public : Plutôt informatique

La génération de données de test à partir d’une spécification formelle utilise soit des méthodes de génération de données aléatoire pour tester la conformité d’une classe d’objet par rapport à sa spécification, soit des méthodes de résolutions de contraintes pour réduire le domaine de valeurs des données générées. Les oracles de test proposés dans l’industrie se contentent de tester la conformité d’une méthode en générant seulement des données valides respectant la pré-condition. Cependant une pré-condition fausse peut induire une post-condition et un invariant valides. Une méthode proprement implémentée devrait écarter les cas des données non valides qui impliquent des résultats valides. Ces travaux proposent un modèle formel généralisé permettant de tester la conformité de l’implémentation d’une méthode par rapport à sa spécification et intégrant le test de sécurité pour les données invalides. L’idée principale de notre approche est basée sur une classification par analyse de partition des domaines de conformité et de non-conformité pour chaque type de méthode dans le cadre du test objet.

> Témoignage

vignette témoignage

Béatrice, promo 2006

Certificateur Critères Communs à l'ANSSI.

Lire la suite >

> Séminaires

> À noter

Cryptis sur le réseau LinkedIn !

Diplômés en sécurité de l'information et cryptogaphie de Limoges, rejoignez le groupe Master Cryptis Alumni...

Lire la suite >