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.

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.

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.

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.

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.

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.

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.

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).

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.

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.

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 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.

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é.

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.

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.