PRISM NSA : La riposte technologique

près avoir dans un précédent billet la solution de navigation Tor, pour surfer plus ou moins anonymement sur le web, aujourd’hui nous allons nous pencher sur les solutions technologiques qui sont apparues au lendemain du scandale américain.

Le chiffrement intégral des données :

Au lendemain donc du scandale, certains géants du Web (qui ont été plus ou moins impliqués dans l’affaire) ont réagi en proposant ou en planifiant un chiffrement intégral de leurs données face à la NSA.

Microsoft :

Chez Microsoft, le chiffrement des données existait déjà avant les révélations sur le programme de surveillance, mais il n’était pas intégral.
En effet, chez Microsoft les connexions entre les services et les clients sont pour la plupart déjà chiffrés, mais on se limite à ça. Les échanges de données à l’échelle de l’entreprise ne sont pas encore cryptés, ainsi que les échanges entre les serveurs au sein des centres de données.

Selon cet article du Washington Post, Microsoft suspecte l’agence gouvernementale d’avoir pénétré ses  échanges de données interne. Ces suspicions seraient d’autant plus fondées que la NSA aurait selon cet autre article intercepté les communications internes d’entreprises rivales (à savoir Google et Yahoo) et utilisant les mêmes architectures pour leurs infrastructures.

Par ailleurs les documents révélés par Snowden suggèrent que des services de Microsoft sont bien concernés, des références existent envers des services du géant sont présentes (les services Hotmail et Windows Live Messenger Services).
Le caractère personnel des données, ainsi que l’avènement le cloud, ne fait qu’augmenter le problème pour les entreprises: c’est moins à l’utilisateur qu’à l’entreprise de veiller à la protection des données, et le chiffrement seul de la connexion avec le client n’est plus suffisant.

Face à ces révélations, les officiels de Microsoft ont nié être au courant de cette opération de la NSA, voici une déclaration de Brad Smith, vice-président de Microsoft et responsable juridique de la firme, se montre inquiet : « Ces allégations sont réellement troublantes. Si elles sont vraies, ces actions sont équivalentes au piratage et à la capture de données personnelles, et de notre point de vue, sont une faille dans la protection garantie par le Quatrième Amendement de la Constitution »
Les officiels se seraient donc déjà rencontrés pour évoquer le chiffrement intégral des données, comment ils allaient le déployer, le budget ainsi que la vitesse à laquelle ça sera fait. On devrait donc voir prochainement des efforts faits dans ce sens par la firme américaine.

 

Yahoo :

 

Dans les éléments publiés par le lanceur d’alertes, Yahoo est une entreprise qui revient de manière récurrente. Avant ce scandale, les données de la firme n’étaient pas chiffrées, et ce même  (ce qui explique peut-être la forte parution du nom de l’entreprise dans ce scandale, ses données n’étaient peut-être pas suffisamment protégées).

Après les révélations, la PDG du groupe Marissa Meyer a publié une annonce sur le chiffrement des données sur son blog (voir sur le lien donné). Dans cette annonce elle annonce le fort engagement de la firme à ne pas exposer les données de ses utilisateurs. Elle explique ne jamais avoir donné accès à la NSA à ses serveurs.
La firme annonce les mesures suivantes suite à ces annonces :

  • Crypter les échanges de données entre les datacenter
  • Offrir aux utilisateurs de crypter leurs échanges avec Yahoo
  • Travailler avec leurs partenaires au niveau Mail pour que tous les sites soient sous https

En outre, ils ont doté leur client Mail d’un chiffrement https (ssl) avec des clés de 2048 bits.

Le chiffrement intégral des données a donc été une des mesures techniques prises par les géants du Web suite à ce scandale. On va voir d’autres mesures adoptées au lendemain des révélations.

 

Le chiffrement des messages :

Un article du journal allemand Der spiegel (voir dans les sources) rapporte que la NSA surveillerait également le contenu des smartphones.
Les téléphones concernés seraient ceux tournant sous Android, iOs et les BlackBerry.

Parmi les informations récupérées par le NSA figureraient les SMS, les mails, les listes de contact, les informations de localisation.
La NSA procèderait cependant par des moyens détournés pour accéder au contenu des smartphones, en allant jusqu’à utiliser l’aide d’autres services alliés.
Dans le cas de BlackBerry par exemple,  l’agence gouvernementale aurait utilisé l’aide de son équivalente britannique, la GCHQ, sigle pour Government Communications Headquarters. En 2009, la NSA aurait ainsi percé les défenses de BlackBerry pour accéder au stockage des SMS. Mais la même année, BlackBerry change sa méthode de compression des données, modifiant du même coup le chiffrement. L’année suivante, en mars, le GCHQ informe dans une communication à la NSA qu’elle est parvenue à percer cette nouvelle défense.

Face à ces nouvelles déclarations, des solutions sont apparues pour permettre le chiffrement des messages, que ce soit sur les smartphones ou même sur les ordinateurs. On va en présenter quelques-unes.

TextSecure :

Les développeurs de Cyanogen, célèbres pour la création de Rom (personnalisations des versions du système d’exploitation Android) pour les smartphones sous Android, ont dévoilé leur nouvel outil TextSecure. C’est une application qui permet le chiffrement des SMS en utilisant les clés des deux protagonistes de la communication.
Les messages à d’autres utilisateurs de TextSecure sont chiffrés à la volée, et tous les messages sont stockés dans une base de données chiffrée sur l’appareil. Si le téléphone est perdu ou volé, les messages seront en sécurité, et les communications avec d’autres utilisateurs de TextSecure ne peuvent pas être espionnées à la volée.

De plus son code est open source et est disponible sur Github, la communauté entière travaille donc dessus et il est difficile d’y introduire des portes dérobées ou autres sans qu’on ne s’en rende compte. L’intégration de TextSecure est profonde que l’on ne pourrait le penser et l’outil pourra au final s’interfacer avec n’importe quelle autre application de gestion des SMS. Si vous envoyez un message à un autre utilisateur de CyanogenMod ou TextSecure, le chiffrement sera automatique. Sinon, il sera envoyé en clair. Pour l’utilisateur tout sera fait de manière transparente. Des indicateurs vont néanmoins être rajoutés à terme afin d’indiquer si le chiffrement sera activé ou non en fonction du destinataire.
Un client iOs est aussi en cours de développement par les équipes.

Cryptocat :

La dernière solution présentée est différente de la précédente, dans le sens où elle ne concerne pas que les messages et les smartphones. C’est un client de chat sécurisé, disponible comme extension pour les navigateurs Firefox, Chrome, Safari, Opera. Des clients sont aussi prévus sur les smartphones.
Cryptocat chiffre les chat côté client ; la confiance au serveur se limite à des données déjà chiffrées.

Elle utilise AES-256 pour le chiffrement, un échange basé sur les courbes elliptiques pour l’accord de clef, SHA-512 pour le hachage (servant pour l’authentification) et une signature HMAC pour vérifier l’intégrité des messages. Elle permet aussi des salons de discussion, en utilisant un protocole de chiffrement inspiré de celui d’OTR. Les conversations privées (entre deux personnes) en revanche sont sécurisées par une implémentation fidèle du protocole OTR.

C’est une autre solution pour permettre d’éviter l’interception des messages des utilisateurs pour toutes les agences gouvernementales. De plus, le code étant open source il est maintenu à jour des avancées en matière de sécurité et rend difficile l’introduction de portes dérobées ou de code suspect par quiconque souhaite espionner des conversations.

On a donc vu quelques solutions ou mesures technologiques qui ont émergé après le scandale  déclenché par Mr Snowden.
On est encore loin de pouvoir sécuriser complètement nos données et contrer toutes les tentatives d’espionnage, mais c’est encourageant de voir que des solutions sont en train d’être proposées. C’est aussi rassurant de voir que les géants du Web se penchent de plus en plus sur cette question, et la prennent au sérieux. Ce scandale aura eu pour mérite de nous ouvrir enfin les yeux sur la question de notre vie privée et de notre anonymat sur le Web. Surtout à l’heure où on voit l’émergence du Cloud, qui nous offrira encore moins de contrôle sur nos données (en les envoyant sur le nuage).

Sources :

http://www.pcinpact.com/news/84840-textsecure-va-gerer-chiffrement-sms-dans-cyanogenmod.htm

http://www.washingtonpost.com/business/technology/microsoft-suspecting-nsa-spying-to-ramp-up-efforts-to-encrypt-its-internet-traffic/2013/11/26/44236b48-56a9-11e3-8304-caf30787c0a9_story_1.html

http://apps.washingtonpost.com/g/page/world/hints-of-microsofts-vulnerability/621/

http://www.pcinpact.com/news/84628-face-a-nsa-microsoft-prevoit-aussi-sur-chiffrement-integral-donnees.htm

http://www.pcinpact.com/news/84485-face-a-nsa-yahoo-promet-chiffrement-integral-donnees.htm

http://yahoo.tumblr.com/post/67373852814/our-commitment-to-protecting-your-information

https://threatpost.com/textsecure-encrypted-text-messaging-integrated-into-cyanogenmod-for-android/103141

http://fr.wikipedia.org/wiki/Cryptocat

 

 

Licence Creative Commons
PRISM NSA : La riposte technologique est mis à disposition selon les termes de la licence Creative Commons Attribution 4.0 International.

Courbes elliptiques et cryptographie multivariable

Durant cet article, nous allons vous parler de courbes elliptiques et de cryptographie multivariable, deux méthodes de cryptographie moderne.

Utilisation des courbes elliptiques dans la cryptographie

Comme nous l’avons vu dans notre précédent article, la cryptographie moderne fait appel à des procédés mathématiques toujours plus complexes afin de rendre les systèmes inviolables, mais également plus efficaces en assurant une meilleure protection avec des clés de poids plus faible.
Parmi les nouveaux procédés cryptographiques à clé publique, est apparue la cryptographie à base de courbes elliptiques.
La cryptographie à base de courbes elliptiques est très adaptée pour les nouveaux systèmes, notamment les systèmes embarqués, ou encore les cartes à puce, où les coûts et l’efficacité sont des contraintes importantes.
Pour vous donner un aperçu, la cryptographie à base de courbes elliptiques permet de réduire considérablement la taille des clés, notamment si on compare avec l’algorithme RSA, où quand celui-ci utilise des clés de 1024 bits, la cryptographie elliptique utilise des clés de 200 bits avec une sécurité plus élevée.

Petit rappel sur les courbes elliptiques

On appelle courbe elliptique, toute courbe d’équation :

y2 = x3 +ax + b

Et où le discriminant du membre de droite est non nul.
Une courbe elliptique est définie sur un corps K et se note E(K).

Considérons la figure suivant :

Courbe elliptique

On considère 3 points P(x1,y1), Q(x2,y2) et R(x3,y3) trois points de la courbe (E) et un point O situé à l’infini, tel que R = P + Q.
L’opération mathématique “+” définit une loi de groupe sur la courbe, on peut alors définir :
Opération

Nous avons ici fait un bref rappel sur les courbes elliptiques et défini ce dont nous allons avoir besoin afin de mieux comprendre son utilisation dans la cryptographie.

La mise en oeuvre dans la cryptographie

Les courbes elliptiques pour l’échange de clés

Comme nous l’avons dit en introduction, la cryptographie sur les courbes elliptiques est basée sur un échange de clés à la manière de Diffie et Hellman, c’est-à-dire sans se les communiquer directement.

Afin de communiquer, nos deux interlocuteurs vont devoir définir ensemble quelques paramètres.
Le premier paramètre, à définir publiquement, est un corps fini K, puis la courbe elliptique qui va servir.
Enfin le dernier paramètre à choisir publiquement est un point P.
La seconde étape pour nos deux interlocuteurs va être de choisir, cette fois-ci secrètement, un entier chacun (par exemple l’émetteur choisit un entier a et le récepteur un entier b).
Pendant la troisième étape, l’émetteur envoie au récepteur le point aP et le récepteur envoie le point bP.
Enfin, la dernière étape consiste à calculer, chacun de leur côté, a(bP) = b(aP) = (ab)P, qui est la clé voulue.

Lors de l’échange de clés par les courbes elliptiques, on peut remarquer qu’il y a beaucoup de dialogue entre émetteur et récepteur, se pose alors la question de la sécurité du procédé.
En effet, bien que beaucoup d’informations soient échangées, le secret reste intacte, et cela grâce à la notion mathématique de logarithme discret.
En effet, si une personne a écoutée l’échange entre nos deux interlocuteurs, elle va connaître la courbe, le corps fini, le point P, et les points aP et bP.
Cependant, pour pouvoir calculer la clé, ‘l’espion” va avoir besoin des entier a ou b.
Connaissant aP, bP et P, cela revient à résoudre le problème du logarithme discret, mais ce problème est extrêmement difficile à résoudre sur des courbes elliptiques.

Les courbes elliptiques pour la transmission de messages

Nous allons maintenant nous intéresser à l’envoi d’un message en utilisant la cryptographie à base de courbes elliptiques.
La première étape concerne le récepteur qui va fabriquer une clé publique à l’aide d’une clé privée b, d’une courbe elliptique E(A,B,K) et d’un point P de cette courbe.
La seconde étape concerne cette fois l’émetteur qui reçoit la clé publique constituée de la courbe, du point P et de bP.
Lors de la troisième étape, l’émetteur va choisir un entier n, calculer nP et M + nbP (M étant le message), et envoyer ces deux nouveaux points au récepteur.
Grâce à sa clé secrète b, le récepteur peut calculer nbP à partir de nP puis il lui suffit de calculer (M + nbP) – nbP pour trouver le message souhaité.

Nous avons donc vu la mise en oeuvre des courbes elliptiques dans la cryptographie pour l’envoi de messages et l’échange de clés.
Nous allons maintenant présenter les avantages et inconvénients de cette méthode.

Avantages et inconvénients de la cryptographie par courbes elliptiques

Comme nous l’avons vu, le principe de cryptographie par courbes elliptiques fait appel au procédé mathématique du logarithme discret.
C’est cet algorithme sur les logarithmes discrets qui fait la force d’un tel chiffrement car le problème mathématique à résoudre n’est plus sur de simples entiers, mais sur tout le groupe d’une courbe elliptique.
Le principal avantage de cela est que l’on va pouvoir générer des clés plus petites mais avec un niveau de sécurité plus élevé par rapport aux algorithmes plus classique de chiffrement.
Le second avantage d’un telle méthode est que les calculs sur les courbes elliptiques sont assez faciles à réaliser, ce qui est particulièrement intéressant pour des systèmes comme les cartes à puces, où la taille des clé est un facteur déterminant sur les performances, car leur puissance est limité.

Les principaux inconvénients du procédé subsistent du fait que la théorie des courbes elliptiques est complexe et encore assez récente, ce qui ne nous met pas à l’abri de solutions permettant de contourner le problème du logarithme discret.
Aussi, lors d’un échange de texte, il faut pouvoir transformer celui-ci en une suite de point d’une courbe elliptique ce qui est loin d’être facile !
Enfin, malgré son jeune âge, la cryptographie par courbes elliptiques a déjà fait l’objet de beaucoup de brevets, ce qui rend son utilisation assez chère.

Sources :
http://fr.scribd.com/doc/16760820/Exemple-de-cryptographie-elliptique

http://tel.archives-ouvertes.fr/docs/00/73/30/04/PDF/vverneuil_these.pdf

Cryptographie multivariable: une nouvelle “branche”

Présentation

De nos jours, la cryptographie à clef publique la plus utilisée peut être qualifiée de univariable (parfois bivariable). En effet, les équations qu’elle utilise sont le plus souvent univariables dans les anneaux ou corps finis. Quant aux cryptosystèmes basés sur les courbes elliptiques (EC), ils utilisent une équation bivariable. Cependant, dans la cryptographie multivariable, on utilise plusieurs équations avec plusieurs variables sur un corps ou anneau fini d’où le nom multivariable.

Prenons un exemple simple constitué de trois variables et de trois équations du second degré quadratiques:

y1 = x1 x1 + x1 x3 + x2 x3 + x3 x3
y2 = x1 x2 + x2 x2 + x3 x3
y3 = x1 x1 + x1 x2 + x2 x3 + x3 x3

Ici, le message à chiffrer est symbolisé par les xi. On peut donc facilement calculer les yi, mais il est nettement plus difficile de retrouver les xi en connaissant uniquement les yi. Il s’agit ici d’un exemple simple à valeur explicative mais en pratique, on utilise des centaines d’équations souvent quadratiques et des centaines de variables.

Par ailleurs, cette théorie repose sur les problème dits NP-complet. En d’autres termes, il s’agit de problèmes réputés les plus coriaces parmi un groupe de problèmes. Mais pour être plus précis, on définit les problèmes NP-complets comme suit:

  • c’est un problème pour lequel il est possible de vérifier une solution efficacement (en temps polynomial); cela correspond à la notation NP.
  • le problème est au moins aussi difficile que tous les autres problèmes de la classe NP puisque tout problème de la classe NP peut se ramener à ce problème par réduction polynomiale.

Cette branche de la cryptographie possède également une spécificité particulière qui est que les ensembles considérés ne possèdent plus de structure de groupe, ni aucune autre structure algébrique apparente. De fait on peut concevoir des cryptosystèmes que l’on ne pourra pas casser même en disposant d’une puissance de calcul exponentielle.

Pour situer un peu mieux la place des schémas multivariables parmi tous les autres, on peut faire une petite classification.

Classification des schémas multivariables et principe directeur

La cryptographie multivariable est une branche de la cryptographie à clef publique mais elle est basée sur des systèmes d’équations polynomiales sur des petits corps ou anneaux finis. On peut même aller jusqu’à distinguer trois styles:

  • Des cryptosystèmes multivariable linéaires sur des petits corps finis
  • Des schémas multivariables quadratique sur des petits corps finis
  • Les variantes combinatoires des schémas précédents

La dernière variante permet de modifier les schémas précédents en retirant un certain nombre d’équations par exemple. De cette manière, il est possible d’obtenir des schémas pour lesquels on ne connaît aucune attaque même théorique.

Pour élaborer le design des schémas multivariables, on cherche d’abord à trouver des schémas algébriques basiques liés voire même directement basés sur des problèmes algébriques difficiles à résoudre. Et pour compliquer un peu les choses, on rajoute une voire plusieurs couches combinatoires afin d’introduire des perturbations pour mettre à mal les attaques qui existent.

Solution classiques contre multivariables

Continuons à comparer les schémas multivariables comme le schéma HFE aux autres schémas bien connus – les schémas à clef publique tels que RSA, McEliece ou Courbes Elliptiques.

Pour commencer, pourquoi ces “nouveaux” schémas multivariables? Pour une raison simple et alarmante: le RSA arrive à son terme. En effet, on se rappelle tous du problème posé par le pirate Français Serge Humpich. Il avait désassemblé un terminal de paiement pour trouver la clef publique RSA utilisée par les banques pour signer les cartes bancaires. Et grâce à ça, il a pu fabriquer de fausses cartes capables de se faire passer pour des vraies dans certains terminaux simplifiés. Pour se faire, il a cassé RSA en réussissant à factoriser un entier de 320 bits qui avait été jugé largement suffisant dans les années 80. Petit échec auquel vient s’ajouter un autre en août 1999. Cette “attaque” résultait d’un effort conjoint de chercheurs issus de nombreux pays et de l’équipe de l’école Polytechnique et avait permis de casser le RSA avec une clé de 512 bits. De fait, à cause de ces quelques problèmes, le désir de trouver un successeur à RSA est devenu une priorité. Mais en attendant, on utilise des tailles de paramètres plus importantes – 1024 bits par exemple – pour assurer la sécurité de RSA. Mais de telles tailles commencent à être assez encombrantes.

Évidemment, d’autre solutions ont été proposées pour remplacer RSA, il n’y a pas eu que les schémas multivariables. On peut citer les schémas HFE (Hidden Field Equations) et les courbes elliptiques qui ont été proposées pour remplacer RSA. En fait, ces deux idées sont des voies de généralisation de l’idée RSA:

  • Les courbes elliptiques (EC) reposent sur des groupes mathématiques plus complexes
  • HFE reposent sur des polynômes plus complexes

Ce qui a justifié l’évolution aussi rapide de la cryptanalyse de RSA fut la structure algébrique Z/NZ qui est trop riche. De fait, le problème d’extraction des racines dans cette anneau, qui constitue le problème RSA n’est pas un problème exponentiel. Donc, pourquoi ne pas remplacer RSA par des cryptosystèmes exponentiels?

On peut citer les deux cryptosystèmes exponentiels bien établis qui permettent d’effectuer à la fois une signature et du chiffrement:

  • McEl, il s’agit du système de McEliece connu depuis 1978
  • Courbes elliptiques, connues depuis 1985 pour leur application cryptographique

Mais même dans ces deux cas, il existe des attaques de complexité égale à la racine carrée de la complexité d’une recherche en force brute. Ainsi, même si de nombreuses alternatives existent, aucun successeur ne semble se détacher du lot au vu des problèmes sur lesquels ils sont basés. Mais qu’en est-il de la sécurité de ces schémas?

Sécurité théorique et pratique

Commençons par quelques rappels sur les cryptosystèmes considérés:

RSA:

  • cryptosystème basé sur un problème algébrique, à savoir la factorisation.
  • problème RSA = problème d’inversion (ce problème semble aussi dur que la factorisation).

McEl:

  • ces systèmes reposent sur l’observation suivante, à savoir que les codes de Goppa sont assez nombreux et assez optimaux pour ne pas pouvoir les distinguer d’un code aléatoire.
  • le problème de Syndrome Decoding pour un code aléatoire est supposé être pleinement exponentiel à résoudre.

Pour en savoir plus sur le Syndrome Decoding et les codes de Goppa, vous pouvez vous référez aux liens suivants:
http://fr.wikipedia.org/wiki/D%C3%A9codage_par_syndrome
http://fr.wikipedia.org/wiki/Code_de_Goppa

EC:

  • il s’agit d’une généralisation des problèmes tels que RSA sur quelque chose de très compliqué. Ces cryptosystèmes sont uniquement basés sur l’opacité de la représentation du code sous-jacent.

HFE:

  • pour ce système, la sécurité se décline en deux niveaux emboîtés, la sécurité issue des problèmes algébriques et celle provenant de l’opacité de la représentation.

Maintenant que ces quelques rappels sur la sécurité théorique ont été faits, voyons ce qu’ils ont donné en pratique:

RSA:

  • ce système avec un bloc (ou clé) de taille 512 bits fut cassé en août 1999 et l’attaque avait même été exposées au Eurocrypt de la même année. Cette attaque nécessitait environ 258 opérations CPU

McEl:

  • ce système avec les paramètre d’origine qui étaient 1025, 524 et 101 a été cassé en 1998 à l’aide d’environ 260 opérations CPU

EC:

  • ce système avec un bloc de taille 97 bits fut cassé en septembre 1999 au cours d’un challenge posé par Certicom et l’attaque nécessitait environ 259 opérations CPU

HFE:

  • ce système avec un bloc de taille 80 bits a été cassé avec une attaque en 262 opérations CPU

La constatation est donc la suivante: à difficulté comparable, les cryptosystèmes multivariables semblent atteindre des tailles de blocs plus courts.

La cryptographie multivariable et son importance

Cette nouvelle cryptographie apporte de nouvelles choses à la cryptographie à clé publique de manière générale et ce sur plusieurs plans.

Pour commencer, elle utilise des schémas qui sont souvent beaucoup plus rapides, plus intuitifs et qui donnent des signatures beaucoup plus courtes que d’autres schémas. De fait, elle est plus efficace. De plus les coûts sont également plus faibles puisqu’à complexité égale, les tailles des blocs sont plus petites comme nous l’avons vu juste avant.

Ensuite, en sécurité, tout baser sur le même problème difficile comme la factorisation n’est pas forcément la meilleur stratégie à adopter. On a besoin de varier les types de problèmes, il s’agit de biodiversité, un terme créé par François Morain. Et c’est ce que fait la cryptographie multivariable car elle repose sur les problèmes dits NP-complets qui sont plus coriaces (complexité exponentielle) et plus variés que le “simple” problème de factorisation.

De plus, la cryptographie multivariable possède des propriétés uniques permettant des choses que les autres branches de la cryptographie ne peuvent pas faire. On peut citer par exemple la possibilité de créer des signatures très courtes, un attrait non négligeable. On rappelle d’ailleurs qu’une signature a pour but de permettre au destinataire de vérifier que tel message provient bien de l’émetteur indiqué. Et cet attrait est très recherché puisque pour les télévisions cryptées, les transmissions militaires, les cartes à puce, la sécurisation des transactions sur Internet, la protection des mots de passe sur un disque dur et bien d’autres applications, il est nécessaire d’avoir des clés compactes, ou des temps de calcul infimes, voire même les deux.

Quid de son histoire?

D’après les propriétés et avantages vus plus haut, on a constaté que la cryptographie multivariable était adaptée aux situations où la puissance de calcul était limitée (en raison de la faible taille des blocs), elle sert aussi pour le chiffrement et la vérification de signature en particulier. Mais parlons quand même de son histoire pour voir ce qu’elle est devenue.

En 1988, lors du congrès européen de cryptographie Eurocrypt, deux Japonais, Tsutomu Matsumoto et Hideki Imai ont proposé un premier schéma connu sous le nom “Matsumoto-Imai”, MI ou encore C* mettant à profit le principe de cryptographie multivariable. Dans ce schéma, les équations étaient de degré deux, comme dans notre exemple, limité à deux d’où le terme cryptographie multivariable quadratique MQ.

Ce schéma va rester invaincu pendant sept ans jusqu’à ce qu’une équipe française décide de s’attaquer à ce schéma. Elle finit par le casser en 1995 avec l’aide de Jacques Patarin. Première déconvenue pour cette branche de la cryptographie. Mais juste après cette cryptanalyse, Jacques Patarin propose de nouveaux schémas. C’est en 1996 à Eurocrypt qu’il va présenter un algorithme s’éloignant de la proposition de Matsumoto et d’Imai : HFE (Hidden Field Equations) basé sur des polynômes au lieu de monômes. Son approche est de plus très économe en temps de calcul. Il va poursuivre ses travaux en proposant un algorithme de signature en 1997nommé Oil and Vinegar (OV) assez similaire au MI. Le nom vient du fait que les variables du système d’équation sont séparées en deux catégories: les hi pour huile et les vi pour vinaigre. Les équations de ce système comportent tous les produits à l’exception du produit hi-hi.

Mais ce système OV va être démonté durant le congrès Crypto en 1998 par deux Israéliens. J. Patarin va donc le réparer donnant naissance au schéma Unbalanced Oil and Vinegar qui comportent beaucoup plus de variables  vi que hi publié en 1999 avec l’aide d’un des israéliens qui avaient démonté son schéma précédent.

Deux ans plus tard, J. Patarin publie SFLASH en se basant sur HFE, avec l’aide de Nicolas Courtois et Louis Goubin, deux membres de l’université de Versailles. Cet algorithme de signature numérique va s’avérer très convaincant du fait de son économie en puissance de calcul à la fois pour calculer et pour vérifier la signature. Cet algorithme va même finir par être homologué en 2003.

Donc, malgré quelques déboires la cryptographie multivariable a fini par s’imposer dans le milieu de la signature spartiate.

Mais c’était sans compter l’attaque proposée par Henri Gilbert lors de l’Eurocrypt de 2002. Car même si celle-ci n’a pas remis en question les fondements du schéma, elle a fini par engendrer des corrections au niveau des paramètres – au niveau de la taille des clés en fait. Suite à ce manque de sécurité, deux nouvelles versions de SFLASH vont voir le jour (avec des tailles de clé plus grandes même si la taille finale commençait à être un peu lourde pour les cartes à puce de 2008).

Il y a même eu des attaques sur HFE avec celle du congrès Crypto de 2003 menée par deux Français: Jean-Charles Faugère et Antoine Joux.

Puis, l’équipe constituée de Vivien Dubois, P.-A. Fouque et J. Stern de l’ENS va s’attaquer à une version dégradée de SFLASH et va réussir à casser cette version. Ainsi, SFLASH commence à être mis à mal. Puis c’est l’ensemble des versions normales de SFLASH (même la v3) qui va être détruit avec une petit coup de main d’un des fondateurs du RSA.

Somme toute, seul HFE semble encore tenir la route. La cryptographie multivariable a donc connu son heure de gloire avec SFLASH mais à l’heure actuelle, avec les nombreuses attaques subies, son âge d’or semble bel et bien fini.

Sources :
http://www.larecherche.fr/savoirs/dossier/gloire-deboires-cryptographie-multivariable-01-06-2008-74888
La sécurité des primitives cryptographiques basées sur des problèmes algébriques multivariables: MQ, IP, MinRank, HFE (thèse)

“Nouveaux” types de cryptographie

Introduction

Comme chacun sait, il y a eu une augmentation considérable des débits des télécommunications de ces dernières années que ce soit dans les transmissions numériques ou analogiques. Augmentation qui va naturellement de paire avec la montée en puissance des calculateurs ce qui conduit à se demander pendant combien de temps les algorithmes de calcul seront encore sûrs. Ces craintes sont d’autant plus importantes que les promesses faites sur les capacités de calcul de l’ordinateur quantique sont très prometteuses et surtout colossales.

C’est ainsi que deux alternatives ou plutôt deux nouvelles techniques ont fait leur apparition durant les dernières années : la cryptographie quantique et la cryptographie chaotique. Deux alternatives que nous allons expliciter un peu plus au cours de cet article.

La cryptographie quantique

Un des procédés cryptographiques qui a révolutionné la fin du XXe siècle est la cryptographie quantique se basant sur des propriétés de la physique quantique. Longtemps considérée comme une méthode quasiment invulnérable, nous verrons que des expériences lui ont démontrées quelques limites.

La cryptographie quantique est donc un moyen cryptographique qui utilise des propriétés de la physique quantique afin d’atteindre des niveaux de sécurité qu’un procédé classique ne pourrait pas atteindre. Ce procédé est surtout utilisé pour chiffrer les clés lors d’une communication entre deux personnes distantes. La sécurité de ce procédé se base essentiellement sur les lois de la physique quantique et la théorie de l’information. Jusqu’à maintenant le moyen de transmettre des clés secrètes entre deux personnes distantes afin que celles-ci puissent communiquer, était la valise diplomatique. Nous allons voir en quoi la cryptographie quantique a sonnée au coup de tonnerre en terme de sécurité.

Afin de vous faire comprendre comment marche ce procédé, il est temps de vous mettre en situation. Pour cela nous vous présentons 3 personnages : Alice et Bob qui communiquent entre eux, et Eve qui les espionne. Ces 3 prénoms sont couramment utilisés pour expliquer les procédés cryptographiques, notamment Eve signifie “eavesdropper”, oreille indiscrète en anglais. Voici ce dont disposent nos deux interlocuteurs :

  • des objets quantiques, comme des impulsions lumineuses : des photons.
  • un canal quantiques qui va permettre au objets quantiques de se déplacer d’un point à un autre, comme la fibre optique.
  • un canal classique de communication, comme Internet.
Chacun des photons peuvent être polarisés sur des angles qui vont varier de 0° à 180°. Les protocoles de cryptographie quantique les plus connus sont le BB84 et le E90 mis au point par les canadiens CH.Bennett et G.Brassard. Dans ces protocoles les champs magnétiques des photons prennent des directions de 0°, 45°, 90° et 135° soit 4 positions possibles.

Champs magnétiques

Pour les polarisations de 0 et 90° on parle de polarisation rectiligne et pour 45 et 135°, de polarisation diagonale.

Afin de détecter l’orientation du photon, le receveur va utiliser un filtre, qui comme les photons peut être orienté. Dans le cas d’un filtre orienté à 0°, si un photon orienté à 0° est transmis, il va traverser le filtre et donc être enregistré par le receveur qui dispose d’un détecteur. Maintenant si l’émetteur transmet un photon orienté à 45 ou 135°, le photon va traverser le filtre une fois sur deux. Il est donc possible de distinguer une polarisation de 0° contre une polarisation de 90° mais les polarisations 45 et 135° sont in-différentiables. C’est le protocole de sécurité qui nous allons expliquer par la suite qui va permettre de les différencier. Il faut noter que dans le cas d’un filtre orienté à 45°, il laissera passer les photons orientés à 45°, stoppera ceux à 135° et reviendra le même problème pour les photons à 0 et 90°.

Après ces explications, nos deux personnages Alice et Bob peuvent commencer à s’échanger la clé secrète via le canal quantique. Alice va émettre une série de photons où les 0° et 45° représentent 0, et 90° et 135° vont représenter 1. De l’autre côté, Bob va recevoir les photons et mesurer leur polarité avec un filtre rectiligne ou diagonal, et considérera 0 si le photon traverse le filtre, 1 sinon.

Lors de la mesure avec par exemple un filtre rectiligne, si un photon est orienté diagonalement, il passera une fois sur deux et donc la mesure de Bob pourra être fausse. C’est là qu’intervient le canal classique de communication entre les deux interlocuteur. Bob va pouvoir indiquer à Alice le filtre qu’il a utilisé et Alice va alors pouvoir confirmer ou non la mesure de Bob. Les bits qui seront connus d’Alice et Bob constitueront la clé secrète.

Le canal classique va être primordial pour la sécurité du système. En effet, si Eve était en train d’écouter la transmission d’Alice vers Bob, elle effectuait en fait le même travail que Bob. Eve intercepte donc le photon, et afin que son action reste invisible, il renvoie immédiatement un photon vers Bob en essayant de transmettre le même qu’Alice. Cependant elle a une chance sur deux de renvoyer le même photon, donc Bob a maintenant une chance sur quatre d’avoir une mesure fausse. Alice est Bob vont donc sacrifier quelques uns des bits communs afin de vérifier la sécurité :

  1. Alice émet un photon à 45° de valeur en bit 0
  2. Eve intercepte avec un filtre rectiligne, lit 1 et transmet un photon à 90°
  3. Bob reçoit le photon avec un filtre diagonal, le photon passe, Bob note 1
  4. Alice et Bob sacrifient la mesure, Bob annonce un filtre diagonal

Alice et Bob peuvent donc en conclurent qu’Eve les a espionnée

La cryptographie quantique commence t-elle à montrer ses limites ?

Grâce à ce procédé, la cryptographie quantique demeure très sûre, bien que quelques expériences commencent à démontrer le contraire, notamment des travaux au sein de l’université des sciences et technologies de Norvège, ou des chercheurs sont parvenus à trouver un moyen d’écouter une communication sans utiliser le canal direct de communication afin de le pas laisser de trace. Les chercheurs sont allés directement aveugler la machine émettrice grâce à des flashs laser. Grâce à ce procédé, les chercheurs ont intercepté 4% des communications sécurisées.

Comme tout procédé élaboré par l’Homme, la cryptographie quantique commence peut-être à montrer ses limites, ce qui devrait qui continuer dans le futur avec l’apparition des ordinateurs quantiques. Comme toujours l’Homme va devoir encore rechercher une méthode plus performante afin de répondre à l’évolution des technologies et l’évolution des travaux de chercheurs mal intentionnés ou non.

La cryptographie chaotique

Avant toute chose, il faut savoir que la cryptographie par chaos a déjà donné la preuve de sa faisabilité et de sa puissance de chiffrage qui excède 1 Gbits/s.

Principe du cryptage par chaos

Dans certain cas, en cryptanalyse, il est possible d’utiliser la répétabilité du signal transmis. En effet, les algorithmes “actuels” de cryptage sont des suites de nombres pseudo aléatoires. De fait, on peut, à l’aide du signal crypté si celui-ci est suffisamment long, retrouver la clé. On peut résoudre ce type de faille en choisissant un clé d’une dimension relativement importante et suffisamment complexe afin d’éviter que, même sur le long terme, on ne puisse pas remonter à la clé à l’aide du texte crypté. Une bonne idée pourrait donc reposer sur l’utilisation d’un bruit aléatoire, fonction du temps, comme clé.

Pour en revenir au chiffrement d’un message par le chaos, la méthode est la suivante. Ce chiffrement est basé sur la superposition d’un signal chaotique à l’information initiale que l’on veut chiffrer. C’est cette superposition que l’on va envoyer à un récepteur connaissant les caractéristiques du générateur de chaos. Le destinataire n’a plus qu’à soustraire la superposition chaotique du message qu’il a reçu afin de récupérer le message clair. Tout cela semble parfait à l’exception du fait que le décryptage est une étape pour le moins critique notamment en ce qui concerne la recréation de la composante chaotique à soustraire.

Petit rappel succinct sur le chaos

Comment savoir qu’un phénomène peut être qualifié de chaotique ? C’est le cas lorsque le phénomène présente un comportement désordonné et ceci peut se constater sans recherche particulièrement poussée. C’est le cas du jeu de billard puisque l’on peut aisément concevoir que l’on ne pourra pas renvoyer une boule exactement d’où elle vient, sauf en utilisant exactement la même force et le même angle. Et même en remplissant ces conditions, le comportement des bandes du billard ne sera pas forcément le même non plus. Ainsi, on comprend aisément l’importance des conditions initiales pour un tel système. Cette sensibilité aux conditions initiales est la caractéristique propre de tout système chaotique.

Et pour plus d’informations sur la théorie du chaos et ses principes fondamentaux comme le déterminisme :
http://just.loic.free.fr/

La synchronisation des signaux chaotiques

Comme nous l’avons fait remarquer juste avant, le vrai problème que pose un système de cryptographie chaotique provient du phénomène présenté avec l’exemple de la boule de billard : un joueur de billard est incapable de renvoyer sa boule d’où elle vient du moins volontairement. Ainsi, faire le chemin inverse – consistant à reproduire exactement un signal chaotique dans notre cas – va devenir une opération très complexe voir irréalisable. Et donc décrypter un message risque d’être assez difficile. De fait, même si cette méthode semble sure, s’il est impossible de déchiffrer le message transmis, l’intérêt d’un tel chiffrement diminue significativement.

C’est en 1996 que Thomas Caroll et Louis Pecora vont faire une découverte surprenante dans ce domaine en parvenant à reproduire à l’identique un signal électrique chaotique et à le mettre en phase avec le signal original, phénomène connu sous le nom de synchronisation des signaux chaotiques. Un phénomène indispensable sans lequel cette méthode de cryptographie ne serait pas valide.

Générateur optique de chaos

Pour ne citer q’un exemple de générateur de chaos, on peut parler des générateurs optiques de chaos utilisant des dynamiques engendrées par des oscillateurs non linéaires à retard. L’une des principales études réalisées dans ce domaine l’a été par par le physicien japonais Kensuke Ikeda qui a choisi d’analysé les variations de la puissance optique en sortie d’une cavité optique non linéaire en forme d’anneau aussi appelée boucle à retard ou encore anneau d’Ikeda. On injecte un faisceau laser dont la puissance est constante dans cet anneau optique en matériau non linéaire (ce qui signifie, entre autres choses, que son indice de réfraction varie avec l’intensité optique). Après un tour dans ladite cavité, le faisceau va interférer avec lui-même créant ainsi une interférence induisant une variation de l’intensité lumineuse dans la cavité qui va elle-même provoquer une modification de l’indice de réfraction de la boucle. Cet enchaînement va entraîner un chaos d’intensité lumineuse au fur et à mesure que le rayon tournera dans l’anneau.

Ce comportement est décrit par des équations différentielles à retard ou équations d’Ikeda qui sont de la forme :
équation différentielle à retardDans ces équations, T correspond au retard du faisceau dû aux interférences, entraînant un chaos de plus en plus complexe à mesure que T grandira.

Composantes d’un système de chiffrement par chaos

Un système de cryptage par chaos comme bien d’autres systèmes de chiffrement se compose de deux parties : le brouilleur et le décrypteur. Dans notre cas, ces deux éléments sont strictement identiques compte tenu de la sensibilité d’un système chaotique aux conditions initiales : pour obtenir le même résultat (signal chaotique) les conditions initiales doivent être scrupuleusement identiques. Pour mettre en place La synchronisation des dispositifs, on amorce le chaos dans le système récepteur en injectant dans sa boucle à retard l’ensemble “information + dynamique chaotique superposée” puis on attend que les générateurs de chaos soient synchronisés via un signal de synchronisation provenant du générateur de chaos de l’émetteur. On remarque que cette méthode nécessite généralement deux canaux de transmission : l’un pour le signal crypté et l’autre pour la synchronisation. Comme mentionné plus haut, c’est cette étape qui constitue la phase critique de l’opération de déchiffrement. En effet, le moindre écart lors du processus de chiffrement va entraîner un parasite sur l’information aussi appelé bruit de déchiffrement, ce qui rendra illisible l’information.

Limite de complexité

Pour limiter les bruits de déchiffrement on peut choisir un chaos moins complexe au détriment de la qualité du chiffrement. Ainsi, tous les phénomènes chaotiques ne peuvent pas servir à chiffrer un message car même si le degré de complexité assure la sûreté du message, si le phénomène chaotique n’est pas reproductible, on ne pourra pas obtenir une restitution suffisamment claire de l’information.

C’est ainsi que s’achève notre article sur ces deux nouvelle méthodes de chiffrement toutes deux prometteuses. Mais soyez rassurés, si vous avez apprécier ce survol, vous allez pouvoir approfondir le sujet en consultant les liens suivants :

http://www.google.com/patents/EP0963064B1?cl=fr
http://blog.4j4x.net/?p=27

http://www.bibmath.net/crypto/index.php?action=affiche&quoi=moderne/quantique

http://www.lemonde.fr/technologies/article/2009/06/19/le-secret-etait-presque-parfait-la-cryptographie-quantique-n-est-pas-invulnerable_1209092_651865.html

http://fr.wikipedia.org/wiki/Cryptographie_quantique

http://www.femto-st.fr/~laurent.larger/Homepage_ll_fichiers/pdf_files/HDR_ll.pdf (mémoire assez complet et complexe)

Cryptographie symétrique et asymétrique

Après le précédent article où nous avons abordé la cryptographie à travers l’histoire avec quelques exemples connus ou à connaître, nous allons maintenant voir ce que la cryptographie est devenue en parlant de deux axes majeurs de ce domaine. Commençons d’abord par la cryptographie symétrique.

Cryptographie symétrique

En cryptographie, on peut trouver deux approches différentes pour protéger les données. On trouve la cryptographie symétrique aussi nommée à clé secrète et la cryptographie asymétrique ou à clé publique. Dans les deux cas, les objectifs fonctionnels visés sont similaires. De fait, le choix de la méthode est plus une affaire de contexte d’utilisation.

Parlons maintenant de la cryptographie symétrique. Elle regroupe tous les mécanismes cryptographiques qui font appel à des opérations de protection et de recouvrement qui peuvent facilement se déduire l’une de l’autre. Ainsi, ces opérations doivent rester secrètes. C’est pour cette raison que l’usage des mécanismes reposant sur la cryptographie symétrique implique l’établissement d’un secret préalablement partagé entre toutes les entités voulant communiquer de manière sécurisée naturellement.

Les premiers mécanismes de cryptographie symétrique

Ces premiers mécanismes étaient utilisé dans le domaine militaire (encore une avancée grâce à la guerre). Ils servaient à protéger la confidentialité des messages entre leurs émetteurs et leurs destinataires. Dans un premier temps, la transformation d’un message clair en un message crypté (message incompréhensible toute personne autre que le ou les destinataires)  passait par des procédures secrètes. C’est donc cette opération que l’on partageait entre les différents participants.

Un des premiers exemples de cette cryptographie symétrique est le chiffrement de César dont nous avons déjà parlé dans notre précédent article.

Le principe de Kerckhoffs

Cependant, avec la croissance du besoin de transmettre des messages protégés en confidentialité, les limites des premières méthodes de cryptage ont vite été atteintes. Et pour cause, devoir créer de nouvelles opérations pour chaque couple émetteur-destinataire est vite devenue compliqué voire irréaliste en raison du très grand nombre de couples. Par ailleurs, quantifier la notion de secret utilisée dans un algorithme n’est pas aisée et même si une méthode est inventée par un cryptologue cela ne signifie pas pour autant qu’un attaquant ne peut pas imaginer le fonctionnement d’une telle opération. Et enfin, conserver ces procédés secrets peut s’avérer difficile. C’est alors que les cryptographes ont mis en place le concept de clé. Il s’agit en fait d’un paramètre qui est choisi aléatoirement. Ce paramètre est utilisé dans la fonction de chiffrement évitant ainsi de devoir créer un nouvel algorithme à chaque fois que l’on veut le réutiliser pour un nouveau couple émetteur-destinataire. Il suffit de modifier la clé. Une clé possible pour le chiffre de César pourrait être le nombre de positions par lequel on décale chaque lettre dans l’alphabet.

Ce concept, même si assez « simple », fut une véritable révolution qui a permis une large réutilisation d’un même algorithme. Mais cela a contribué à rendre publiques les algorithmes très réutilisés conduisant ainsi Auguste Kerckhoffs, un cryptologue néerlandais du XIXe siècle, à énoncer un principe fondamental :

« La sécurité d’un cryptosystème doit résider dans le secret de la clé. Les algorithmes utilisés doivent pouvoir être rendus publics »

Ainsi, même si un algorithme de chiffrement est publié, si le constat précédent est vérifié, l’impact d’une telle publication s’en trouvera réduit.

Description sommaire d’une fonction de chiffrement symétrique

Pour résumer tout ce qui a été dit précédemment : la confidentialité des données, en cryptographie symétrique, repose sur l’utilisation d’une fonction avec un paramètre correspondant à la clé secrète qui sera partagée entre l’émetteur et le destinataire d’un message.

Figure illustrant le fonctionnement du chiffrement symétriqueLe chiffre de Vernam : fonctionnement et limites

C’est en 1926 que le chiffre de Vernam, un cryptosystème, a été inventé. Sa sécurité est inconditionnelle. En d’autres termes, même en interceptant le message chiffré via ce système, la seule chose que l’on pourra apprendre à propos du message clair sera sa longueur quelle que soit la puissance de calcul utilisée par l’attaquant.

De plus, suivant la façon dont est représenté le texte clair (suite de 0 et de 1 en informatique par exemple), on peut trouver plusieurs versions de ce cryptosystème. On va prendre ici le cas d’une représentation « normale » c’est-à-dire utilisant les 26 lettres de l’alphabet latin.

Pour cette méthode, la clé est une suite de nombres de même taille que le message. Par ailleurs, il vaut mieux choisir ces nombres (modulo 26) de manière aléatoire pour qu’ils soient deux à deux indépendants. On a donc pour chaque lettre du message clair un nombre correspondant et on décale la lettre de ce message dans l’alphabet conformément au nombre de la clé. Pour déchiffrer le message, on applique le décalage dans l’autre sens.

En théorie, le chiffrement de Vernam pourrait être une méthode idéale mais on peut pointer deux gros inconvénients :

  • La clé doit être de même longueur que le message à transmettre.
  • Les clés ne peuvent pas être réutilisées

En effet, supposons que l’on utilise deux fois la même clé et qu’un pirate intercepte deux messages chiffrés avec cette clé. Il serait alors en mesure d’en extraire des informations. Il pourrait même déchiffrer partiellement ou totalement les messages interceptés. Et pour cause, le décalage serait le même pour chaque lettre des deux messages interceptés. La preuve de l’efficacité d’une telle attaque a été démontrée par les services secrets américains et britanniques qui ont, de cette façon, réussi à déchiffrer des messages soviétiques, durant la guerre froide.

De fait, l’organisation nécessaire à la bonne mise en place et à l’utilisation d’un tel système serait bien trop lourde voire impossible à assurer en pratique. Par ailleurs, en 1949, Shannon a démontré que l’on pouvait obtenir une sécurité inconditionnelle à condition d’avoir un coût au moins égal à celui du chiffrement de Vernam. Encore une fois, la réalité est différente. Ainsi, les systèmes actuellement utilisés n’atteignent pas ce niveau de sécurité. On se contente d’assurer une sécurité calculatoire même si celle-ci est fortement dépendante de la puissance des ordinateurs qui est multipliée par deux tous les 18 mois.

Le chiffrement par flot

Les inconvénients du chiffrement de Vernam qui ont été mis en évidence ont toutefois conduit à l’élaboration de nouveaux algorithmes de chiffrement par pallier ces problèmes. C’est ainsi qu’est né le chiffrement par flot qui utilise des clés courtes et réutilisables. Il fonctionne de la façon suivante :

  • On choisit une clé secrète K partagée entre un émetteur (Emil) et le récepteur (Remi) du message
  • Emil choisit une valeur aléatoire IV. Et à l’aide de ces deux valeurs (IV et K) et d’un algorithme public (appelé générateur de pseudo-aléa cryptographique), il va créer une suite S de nombres de longueur prédéfinie. Les nombres de cette suite sont ainsi générés de manière pseudo-aléatoire : ils doivent donner l’illusion d’être choisis totalement au hasard et sans la clé, on ne doit pas pouvoir retrouver cette suite même si une personne en possède une partie.
  • Emil utilise cette suite de nombres comme clé pour le chiffrement de Vernam.
  • Il envoie ensuite IV et le message chiffré.
  • Remi reçoit le tout et en déduit S pour faire le processus dans le sens inverse.

Le chiffrement par blocs

Les primitives (« combinaison d’algorithmes ou pratiques ») de chiffrement par flot permettent d’effectuer un chiffrement rapide  en traitant les données bit par bit mais cela n’a conduit à aucun cryptosystème avec des garanties suffisantes en termes de sécurité à ce jour. A la place, c’est le principe de chiffrement par blocs qui a permis l’élaboration de la plupart des primitives utilisées de nos jours.

Le principe est simple : Emil découpe le message à traiter en blocs de longueur fixe, et on traite ces blocs de manière successive. On va donc transformer les messages clairs de taille fixe N en des messages chiffrés de taille N via une clé de longueur K. De plus, cette opération doit être inversible.

Il existe de nos jours quatre modes de chiffrement par blocs. Le cryptage par blocs (block-cipher) est beaucoup plus utilisé et assure une meilleure sécurité. De plus, plusieurs normes existent : le DES datant de 1977, le triple-DES qui en découle directement, et pour finir l’AES datant de 2001. Pour plus d’informations sur ce domaine, vous pouvez suivre les deux liens suivant :

http://www.securiteinfo.com/cryptographie/symetrique.shtml
http://iml.univ-mrs.fr/~rodier/Cours/Blocs.pdf

Parlons maintenant de quelques notions importantes à respecter pour la cryptographie de la façon dont cela est assuré dans le cas de la cryptographie symétrique.

Confidentialité, intégrité et authentification

En cryptographie, la protection en confidentialité d’un message a pour but de restreindre la lecture de son contenu à un petit nombre d’entités en transformant ce message pour qu’il soit incompréhensible. Etant donné qu’en cryptographie symétrique, tout repose sur la connaissance de d’une clé privée comme nous allons le voir après, il faut donc avoir partagé de manière sécurisée autant de clés secrètes différentes que d’interlocuteurs potentiels ce qui est avantageux dans le cas où il y en a peu (communications point à point, chiffrement d’archives, architectures en étoile…) Dans l’autre cas (de nombreux interlocuteur potentiels), cela nécessite une couche de gestion des clés souvent réalisée à l’aide de la cryptographie asymétrique.

Il existe également le mécanisme d’authentification qui est doit permettre à une entité de s’assurer de l’identité de l’origine des messages reçus.

Enfin, on peut parler de la protection en intégrité d’une donnée. Il s’agit de prouver au destinataire du message que celui-ci n’a pas été modifié depuis qu’il a été envoyé. Dans le cas de la cryptographie symétrique, ceci est assuré par la transmission d’un MAC ou Message Authentication Code qui est spécifique à un message donné. Le MAC fonctionne grâce à la clé secrète partagée. De plus, si la clé partagée est symétrique, la validité du MAC implique l’authenticité de son origine puisque les seuls détenteurs de la clé secrète sont l’émetteur et le récepteur.

Point essentiel à retenir

Rappelons donc le point le plus important de la cryptographie symétrique qui se trouve dans le principe de Kerckhoffs :

« la sécurité d’un système cryptographique doit résider dans le secret de la clé ».

Toutes ces méthodes reposaient sur la connaissance préalable d’une clé partagée entre les personnes voulant communiquer, chose assez contraignante, ce qui va conduire à l’élaboration de la cryptographie asymétrique dont nous allons maintenant parler.

Cryptographie Asymétrique

Comme nous avons pu le voir, la notion de cryptographie symétrique repose sur la connaissance d’un secret par plusieurs entités. Nous allons donc maintenant pouvoir introduire le concept de cryptographie asymétrique ou également appelée cryptographie à clé publique.

La cryptographie asymétrique est basée sur le même principe mathématique d’asymétrie. En effet, certaines fonctions mathématiques peuvent être calculées facilement par ordinateur, mais l’opération inverse reste difficile à réaliser. Grâce à cette notion mathématique, on peut alors définir des couples d’opérations inverses l’une de l’autre, l’une étant publique et l’autre reposant alors sur la connaissance d’un secret. En se basant sur ces notions mathématiques, on peut alors donner une définition de la cryptographie asymétrique :

« Ensemble de mécanismes reposant sur des fonctions mathématiques asymétriques, qui sont faciles à calculer mais dont l’inverse est difficile à calculer pour quiconque sauf celui qui connaît la clé privée. »

Naissance de la cryptographie asymétrique

La notion d’asymétrie dans la cryptographie est apparue en 1976 lorsque deux cryptologues américains Whitfield Diffie et Martin Hellman ont publié un article mettant en œuvre le principe d’asymétrie en cryptologie.

Leur principe repose sur le fait qu’il n’y pas nécessité, pour que tout se passe bien, que la clé de chiffrement soit la même que pour le déchiffrement.

De plus, les deux cryptologues ont constaté que, pour la protection de données en confidentialité par exemple, le chiffrement d’un message pourrait être effectué par tous alors que le déchiffrement devrait être effectué seulement par le destinataire du message.

L’intérêt de l’asymétrie serait alors que la clé de chiffrement pourrait être rendue publique, donc utilisable par tous ceux qui voudraient chiffrer un message, on parle alors de clé publique, alors que la clé de déchiffrement serait propre au destinataire, on parle de clé privée.

L’idée de Diffie et Hellman est alors apparue comme une petite révolution dans le monde de la cryptographie et il restait maintenant à trouver les outils mathématiques adéquats, des problèmes mathématiques dont la solution serait extrêmement difficile à trouver, et ce, par les ordinateurs les plus puissants au monde.

Nous allons exposer le problème de la factorisation des grands nombres entiers, c’est un problème utilisé aujourd’hui dans la cryptographie asymétrique.

Petits rappels d’arithmétique :

  • Si a et b sont deux nombre entiers, a est dit divisible par b si le reste de la division de a par b et 0. b est alors un diviseur de a.
  • Un nombre entier a est dit premier s’il admet exactement deux diviseurs distincts : 1 et a.

Petits exemples :

  • 7 = 7 * 1 donc 7 est premier.
  • 6 = 1 * 6 = 2 * 3 donc 6 n’est pas premier.

Définition : Factorisation.

Trouver deux grands nombres premiers p et q et calculer leur produit N = p*q et assez simple, en revanche, le problème consistant à retrouver p et q connaissant N est difficile quand p et q sont grands. C’est ce problème que l’on appelle factorisation.

On peut illustrer le problème de cette façon :

Illustration du problème de factorisation

La première primitive de chiffrement asymétrique est publiée en 1978 par Rivest, Shamir et Adleman.

Elle est alors basée sur le problème de factorisation ci-dessus, c’est la primitive RSA.

Le principe de fonctionnement est le suivant :

  1. Génération de la clé publique.
    Le destinataire choisit deux grands nombres premiers p et q et calcule leur produit N. Il choisit également un exposant e qui ne doit avoir aucun diviseur premier commun avec (p – 1)(q – 1). Il publie ensuite N et e.
  2. Calcul de la clé privée.
    Seule la connaissance de p, q et e permet de calculer l’exposant privé d.
  3. Chiffrement.
    Pour chiffrer un message m, l’émetteur calcule c = me [N].
  4. Déchiffrement.
    Le déchiffrement s’obtient en calculant m = cd [N].

Ce qu’il faut retenir pour la primitive RSA :

La primitive RSA repose sur le principe de la factorisation. La clé publique contient un entier N, produit de deux grands nombres premiers p et q. La connaissance de p et q permet d’effectuer des opérations de déchiffrement.

Application de la cryptographie asymétrique

Notion de chiffrement hybride

Comme on l’a vu, lors d’un chiffrement asymétrique, chaque utilisateur génère une clé privée, et sa clé publique est diffusée. Cela permet de résoudre les problèmes de gestion des clés dans les réseaux de taille importante. Le principal problème de l’asymétrie par rapport à la symétrie va être le problème du débit, en effet les mécanismes mis en œuvre sont moins performants. C’est donc à partir de ce constat qu’est né le chiffrement hybride. Le principe fait appel à de la cryptographie symétrique et à de la cryptographie asymétrique.

Définition : Chiffrement hybride.

Le chiffrement d’un message M se déroule en deux étapes. Dans un premier temps, l’émetteur choisit une clé symétrique K aléatoire. Il utilise ensuite cette clé K pour chiffrer de manière symétrique le message M. Ensuite il chiffre de manière asymétrique cette fois, la clé K avec la clé publique du destinataire. Il envoie à son destinataire les chiffrés de M et de K. Le destinataire déchiffre d’abord la clé K, puis l’utilise pour retrouver M.

Le chiffrement asymétrique possède donc un grand avantage lorsque le nombre d’interlocuteurs est grand.

Le chiffrement hybride étant composé des chiffrements symétrique et asymétrique, il possède les avantages des deux procédés.

Autres applications : signature électronique et certificat

La signature électronique est l’équivalent de la signature manuscrite. Cette donnée doit garantir l’intégrité du message et authentifier celui qui l’envoie. Ici, l’opération privée va correspondre à la signature du message qui sera effectuée par l’envoyeur à l’aide de la clé privée. La vérification de la signature repose uniquement sur l’utilisation de la clé publique et peut être effectuée par tous.

Nous avons ainsi passé en revue les deux axes majeurs autour desquels la cryptographie d’aujourd’hui s’est développée. C’est donc tout pour cette fois.

Aperçu des méthodes de cryptographie du passé

Fidèles à notre poste, nous allons cette semaine vous parler de quelques méthodes de cryptographie du passé. Nous parlerons de la cryptographie par substitution mono-alphabétique avec le célèbre chiffre de César, entre autres et nous parlerons pour finir d’une méthode qui a fait loi pendant près de 3 siècles.

Principe de la cryptographie par substitution mono-alphabétique

Le cryptage par substitution mono-alphabétique est un des codages les plus anciens, et également certainement le codage le plus simple à réaliser. Cette méthode va simplement consister à remplacer une lettre donnée par une autre lettre de l’alphabet ou un signe quelconque. On parle de substitution mono-alphabétique car une même lettre n’est remplacée que par une seule et même lettre.
Voici un premier exemple :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
W X E H Y Z T K C P J I U A D G L Q M N R S F V B O

Le message « Un petit roseau » va alors donner « MT JCGLG UZVCNM ». Le déchiffrement du message s’obtient simplement avec la même clé de chiffrement. L’un des problèmes de ce chiffrement est qu’il faut se souvenir de la clé utilisée, c’est-à-dire de la permutation de l’alphabet utilisée.

Pour cela il existe plusieurs techniques dont la première est de se baser sur un mot-clé et ensuite de compléter la clé par la suite alphabétique du mot. Par exemple, choisissons comme mot-clé : SRETI, la clé de chiffrement sera :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
S R E T I J K L M N O P Q U V W X Y Z A B C D F G H

Deux autres techniques sont, ou ont été, utilisées pour se souvenir de la clé, le chiffrement AtBash qui consiste à simplement inverser l’alphabet, ou encore le code de César fondé sur un simple décalage de lettres.

Principe du Code de César

Le chiffrement par substitution mono-alphabétique remonte maintenant à de nombreux siècles. En effet, les premières traces d’un tel codage remontent à l’époque de Jules César. On sait que, pour transmettre des messages secrets, César s’est essayé à des méthodes toutes plus originales les unes que les autres.

Par exemple, une méthode consistait à raser la tête d’un esclave sur laquelle on inscrivait ensuite le message puis, une fois que les cheveux avaient repoussé, on envoyait l’esclave délivrer le message. Cependant à cause de l’attente que cette méthode engendrait, César a dû recourir à des moyens plus ingénieux dont le plus célèbre reste le Code de César qui constitue la méthode de cryptographie la plus ancienne connue à ce jour.

Il va consister à décaler les lettres de l’alphabet d’un ou plusieurs rangs. Il faut noter que César lui ne décalait les lettres que de 3 rangs, c’est pour cela qu’officiellement, le chiffre de César ne correspond qu’au chiffrement par un décalage de 3 lettres.

Par exemple, pour un décalage de 3 lettres :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Ainsi la phrase « Je levai les yeux » devint « MH OHYDL OHV BHXA ».

La sécurité d’un tel chiffrement est assez limitée puisqu’il n’existe que 26 façons différentes de crypter un message avec ce code. Cependant on trouve encore quelques traces d’utilisation des siècles plus tard, par exemple l’armée russe l’aurait utilisée en 1915, ainsi que des sudistes pendant la guerre de Sécession.

Le carré de Polybe

Voici une méthode de chiffrement qui remonte également à l’antiquité. Polybe, un historien grec est capturé par les Romains parmi 1000 otages à la suite de la bataille de Pydna en Macédoine et à la victoire de Paul-Émile sur les Grecs.

Le carré de Polybe est un carré comportant 25 cases (pour notre alphabet), ce qui signifie que l’on place le I et le J dans la même case et donc ils auront le même codage. Chaque lettre va alors être codée par ses coordonnées dans le tableau, en commençant par la ligne puis la colonne. Par exemple, on va coder A par 11 et B par 12.

Le carré de PolybeProcédons à un exemple : le mot SRETI va ici être codé par : 4342154424.

Plusieurs variantes du carré de Polybe consistent notamment à remplir le tableau de manière différente et en commençant, pourquoi pas, par un mot-clé et la suite de l’alphabet.

Une des dernières grandes utilisations connues de l’utilisation du carré de Polybe remonte aux XIXème et XXème siècle. En effet, il fut utilisé par les nihilistes russes (terroristes russes souhaitant la chute du Tsar) enfermés dans des prisons du Tsars. Afin de faire parvenir les messages entre les cellules, ils tapaient sur les murs ou la tuyauterie afin de pratiquer une transmission de message très proche du morse, la différence est qu’ici, on peut modifier la clé. S’ils avaient voulus transférer le mot SRETI, les prisonniers auraient tapés comme suit : 4.3 – 4.2 – 1.5 – 4.4 – 2.4, les . désignant des silences brefs et les – des silences prolongés.

Le chiffre des templiers

On a vu que dans les codes précédents, pour crypter un message, on se contentait de remplacer une lettre par une autre selon une clé bien définie. Et si, au lieu de ça, on décidait de remplacer chaque lettre par des symboles… C’est là ce que certains ont préféré. En fait, ce sont surtout les membres de société plus ou moins secrète qui ont utilisé ce procédé comme les francs-maçons au XIXè s. avec le chiffre de PigPen.

Mais pourquoi les templiers ont-ils eu besoin de coder les lettres qu’ils s’échangeaient ? Pour le savoir faisons un rapide rappel d’histoire : le Temple, un ordre de moines fondé au XIIème siècle, avait pour mission d’assurer la sécurité des pèlerins en Terre Sainte. Mais assez rapidement, les templiers se sont détournés du droit chemin pour chercher richesse et pouvoir. Et ils se sont tellement enrichis qu’ils ont fini par devenir les trésoriers du roi et du Pape. Et de fait, par souci de sécurité, ils ont dû coder les lettres de crédit qu’ils s’échangeaient. Cet alphabet de substitution provient de la croix « des huit béatitudes » qui étaient l’emblème de leur ordre.

Emblème des templierscode des templiers

Si on fait abstraction de la petite difficulté provenant de l’utilisation de symboles peu courants ce système de chiffrement n’est pas plus sûr que n’importe quel autre système de substitution.

Les faiblesses de la méthode de substitution mono-alphabétique

Pour toutes les méthodes de cryptographie par substitution mono-alphabétique que nous avons vues, les clés possibles sont au nombre de 26! soit un peu plus de 4×1026, ce qui en soi est assez énorme. Pas de souci donc, les méchants ne trouveront jamais la clé… Eh bien, en fait, il y a un très gros bémol : ce nombre de clés ne tient pas compte de la faiblesse structurelle de la cryptographie par substitution. En effet, dans les différentes langues, les lettres n’apparaissent pas toutes à la même fréquence. Dans le cas de la langue française, il y a presque toujours beaucoup plus de E que de Y dans un texte, enfin presque… dans le cas de la Disparition de Georges Pérec, où la lettre E a totalement disparu, ce postulat n’est plus vrai. Mais sinon, comme le E est toujours remplacé par la même lettre et le Y aussi on peut en déduire que la lettre qui apparait le plus dans un texte français correspond sûrement à un E crypté. Et inversement, s’il n’y a presque aucun F par exemple, il s’agit sûrement d’un Y crypté.

Histogramme illustrant l’analyse de fréquence d’apparition des lettres dans l’acte 1 du Malade Imaginaire de Molière (soit 13334 caractères utiles après conversion des caractères accentués en leurs équivalents sans accent et en supprimant les autres caractères (espaces, ponctuations, etc.).

Grâce à cet histogramme, on note l’apparition de groupes de lettres avec des fréquences assez similaires :

  • le E est de loin le plus fréquent
  • Puis, on trouve les S et U
  • Ensuite, les A,I,N,O,T
  • Et on continue…

En plus des fréquences d’apparition, on peut également utiliser la position des lettres dans le texte pour en identifier d’autres. On trouve par exemple les S en fin de mots quand ils sont au pluriel. Le A est, quant à lui, fait souvent parti des lettres qui apparaissent isolées. Puis on continue avec la fréquence d’apparition des groupes de 2 lettres voire de 3.

Cette démarche comporte tout de même quelques failles. Tout d’abord, le texte doit être relativement long pour réaliser des statistiques correctes et fiables et il vaut mieux qu’il soit écrit en français standard pas comme la Disparition de Georges Pérec.

Le chiffre de Vigenère

Malgré quelques faiblesses, aucune amélioration n’est survenue entre César et le XVIème siècle en matière de procédé cryptographique, à la fois sûr et facile à utiliser ! C’est alors que naquit en 1523 Blaise de Vigenère qui allait devenir l’inventeur d’une « nouvelle » façon de crypter les messages, une méthode mettant en scène une substitution polyalphabétique. Et cette méthode va dominer 3 siècles durant. Elle est expliquée dans son Traicté des chiffres ou Secrètes manières d’écrire publié en 1586.

Son idée, que l’on peut qualifier de révolutionnaire pour l’époque, à propos de cette nouvelle substitution consistait à utiliser un chiffre de César différent pour chaque lettre. On modifie donc le décalage pour chaque lettre. Pour ce faire, on utilise la table suivante :

La méthodologie pour coder un message est la suivante : on commence par choisir une clé, i.e. un mot de longueur arbitraire. On reproduit ensuite ce mot sous la totalité du texte à coder autant que nécessaire de façon à ce que toutes les lettres du texte soit associée à une lettre de la clé. Enfin, on regarde dans le tableau la lettre qui se trouve à l’intersection de la lettre du texte et de celle de la clé.

Un petit exemple pour rendre tout ça plus compréhensible. On va coder le texte « Vous aurez une surprise lors du prochain cours de SRETI » avec la clé « SRETI ». On commence donc par écrire la clé sous le texte à coder :

V

O

U

S

A

U

R

E

Z

U

N

E

S

U

R

P

R

I

S

E

S

R

E

T

I

S

R

E

T

I

S

R

E

T

I

S

R

E

T

I

Pour coder la lettre V, on regarde l’intersection de la colonne issue de V avec la ligne issue de S et l’intersection donne la lettre N. Puis on continue et on obtient au final : NFYL IMIIS CFV WNZHIMLM DFVL LM GVHKZRMG KGLVL LW JVXBA.

Par rapport à tous les algorithmes précédents, celui-là possède nettement plus de points forts. Le cryptage et le décryptage en connaissant la clé sont tous deux faciles d’utilisation.

Ce code n’est certes pas infaillible mais résout l’un des problèmes qui se posait précédemment. Le E a été codé en E, R, I et X. Ainsi, une analyse statistique simple ne peut pas permettre de découvrir où se trouvent les E. Par ailleurs, on peut produire une infinité de clés qui peuvent être des mots voire des phrases. Pour toutes ces raisons, cette méthode s’est imposée durant plus de 3 siècles.

C’est donc sur cette dernière méthode que l’on va refermer le bref historique sur les méthodes de cryptographie du passé. Nous espérons que cette lecture vous aura plu et nous espérons que vous serez également là pour notre prochaine publication.

Panorama des algorithmes de cryptage de l’information

   La cryptologie est une science mathématique qui peut se décomposer en deux branches : la cryptographie et la cryptanalyse. Durant notre étude nous allons exclusivement nous concentrer sur la cryptographie.

Qu’est ce que la cryptographie ?

La cryptographie consiste en l’étude des techniques permettant de transmettre des données de façon confidentielle, afin de protéger une information, qui serait envoyée entre deux entités, dans le cas où celle-ci serait interceptée par une personne mal intentionnée.

Le cadenas informatique

Comme ça marche ?

Une brève explication de la cryptographie pourra se résumer comme ceci : lorsque l’on souhaite protéger un message, on va lui appliquer une transformation mathématique qui va le rendre illisible, cette transformation s’appelle le chiffrement.
Enfin, si on souhaite lire le message après réception et en général, c’est le cas : on va effectuer un déchiffrement, i.e. l’action inverse.

Le plan

Durant cette étude, nous commencerons par étudier et effectuer un historique des méthodes de cryptographie, un historique assez riche puisque les premières découvertes de cryptographie remontent à MXOHV FHVDU (la personne qui a inventé le code César… je vous laisse deviner).

Ensuite nous présenterons les méthodes de cryptographie modernes :
- Cryptographie symétrique
- Cryptographie asymétrique
- Cryptographie hybride

Ces méthodes pourront être illustrées par des exemples de systèmes connus.

Puis, afin de finir l’étude, nous effectuerons des recherches concernant l’évolution de ces méthodes ainsi que des recherches sur de futures méthodes.

Et pour commencer à vous mettre dans le bain, voici un petit lien intéressant au cas où vous auriez du mal à dormir le soir :
http://www.bibmath.net/crypto/index.php3

Licence Creative Commons

Licence Creative Commons
Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution – Partage dans les Mêmes Conditions 3.0 non transposé.

Cryptologie : Synthèse et plan du rapport final

Synthèse de la veille technologique en 2011-2012

La fin de cette veille technologique approchant, il semble approprié de prendre un moment pour considérer ce que nous avons réalisé.

Nous nous étions posés pour objectif d’avancer, par rapport aux années précédentes, sur l’aspect mathématique de la cryptologie et plus particulièrement sur certains algorithmes, afin de mieux comprendre comment chacun d’entre eux fonctionne et également réaliser quels sont les avantages et inconvénients de chacun.
Parmi ceux que nous avions énoncés en septembre dernier, nous avons vu l’AES, les fonctions de hachage, et NTRU. Cependant, nous n’avons pas eu l’opportunité de traiter ni ElGamal ni les signatures électroniques, ayant préféré nous concentrer sur une introduction à la cryptographie quantique – un sujet qui nous semblait absolument primordial dont il fallait parler, sinon vulgariser – et un article sur une faille de sécurité dans l’algorithme RSA, qui met potentiellement en difficulté la sécurité dans un nombre effrayant de structures les plus sensibles les unes que les autres.

En tant qu’auteurs de ces articles, nous espérons que ceux-ci vous auront aidé à comprendre la base de la sécurité informatique de nos jours, dans quels cadres la cryptologie intervient, et pourquoi la confiance à lui accorder ne doit pas être absolue, via des ajouts de cryptanalyse dans nos articles.

Afin de pouvoir rendre compte de ce travail de manière plus exhaustive, nous mettrons en ligne sur ce blog le 16 mars prochain un rapport qui contiendra :

  • Une introduction sur notre travail de veille technologique et la cryptologie
  • La cryptographie moderne : les principes fondamentaux
  • Différents algorithmes pour différentes utilisations
  • La cryptographie dans l’industrie, et son avenir

Merci à vous, lecteurs et lectrices, pour nous avoir suivis tout au long de ce semestre.

Antoine & Quentin

Cryptologie : Des failles dans le RSA

Au cours de cette veille technologique, nous vous avons présenté diverses branches de la cryptologie : certains algorithmes tels que l’AES et le NTRU, l’utilité et le principe des fonctions de hachage telles que le MD5, et enfin un domaine prometteur qui devrait se développer fortement dans l’avenir : la cryptographie quantique.

Avant de conclure notre étude, nous avons la chance aujourd’hui de vous sensibiliser à une découverte qui date de moins d’une semaine, et qui concerne l’emblématique et célèbre algorithme RSA. En effet, un groupe de chercheurs vient de mettre en évidence que cet algorithme à clé publique présentait une faiblesse importante lors de la génération de la clé.

Nous n’allons pas présenter RSA en profondeur puisque cela a déjà été fait par nos prédécesseurs (voir cet article). Il convient cependant de rappeler que l’idée centrale de cet algorithme est de former une clé n = pq, où p et q sont des entiers premiers de grande taille. La robustesse de RSA s’appuie en effet sur la difficulté que constitue la factorisation de grands nombres en facteurs premiers.

Place à la découverte : il s’avère que les clés pour lesquelles un des facteurs (p et/ou q) a déjà été utilisé pour générer une autre clé sont facilement décodables. Par ailleurs, le phénomène est loin d’être marginal, puisque sur les 7,1 millions de clés testées, 27000 se sont révélées vulnérables, soit une probabilité d’occurrence de 0,38%. Ce problème est d’autant plus inquiétant dès lors que cette probabilité d’occurrence est en augmentation, le taux était de 0,26% sur un précédent échantillon de 4,7 millions de clés.

La révélation de cette faiblesse a posé une question éthique puisque, s’il a fallu 3 ans aux chercheurs pour aboutir, ils estiment qu’il serait possible, pour un public averti, d’exploiter cette faille sous quelques semaines. C’est pourquoi ils ont pris certaines dispositions afin que la publication ne devienne pas dangereuse. Après avoir averti le maximum d’entités concernées par les questions de sécurité, ils ont testé leur lot de clés et ont vérifié si les clés utilisées pour mettre en place les certificats SSL sur le web ne présentaient pas cette faiblesse, ce qui n’était heureusement pas le cas. Par ailleurs, il apparaît que cette faiblesse ne concerne pour le moment que des matériels tels que des routeurs, et pas des serveurs web entiers, il n’y a donc pas de raison de paniquer quant à la sécurité du site de votre banque !

Enfin, la découverte semble incriminer particulièrement les générateurs de nombres premiers qui ne fonctionneraient pas de manière totalement aléatoire, puisque la faiblesse concerne à la fois des clés de 1024 et de 2048 bits. Pour donner un ordre de grandeur, une clé de 1024 bits nécessite la génération de 2200 certificats afin de tester l’ensemble des facteurs possibles. On est donc confronté à un problème actuellement insoluble, et s’il existe des solutions c’est à cause du processus de génération qui n’est pas aléatoire. On n’a cependant aucune explication concernant ce dernier point.

Notons que ces mêmes chercheurs ont précisé qu’étant donné le niveau de complexité relativement faible des méthodes qu’ils ont employées, il leur paraît difficile de croire que les résultats présentés soient révolutionnaires, surtout aux yeux d’agences ou de parties connues pour leur curiosité dans ce domaine. Dès lors, on comprend l’importance croissante et cruciale qu’occupe la cryptographie dans notre société. Il en va de la sécurité de l’ensemble de nos transactions, de nos données, de notre liberté.

Bibliographie:

[1] ”Crypto shocker: four of every 1,000 public keys provide no security”, par arstechnica.com

[2] ”Ron was wrong, Whit is right”, par Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung et Christophe Wachter

[3] ”New research: There’s no need to panic over factorable keys, just mind your Ps and Qs”, par freedom-to-tinker.com

Antoine & Quentin

Cryptologie : Cryptographie Quantique

Introduction

Nobody understands quantum theory. - Richard Feynman

Tous les algorithmes de chiffrement que nous avons présentés jusqu’à maintenant sont des méthodes de chiffrement classiques, qui reposent sur des systèmes de clés publiques ou de clés privées. Bien que ces algorithmes aient trouvé leur place dans le monde actuel, et qu’ils sont utilisés de manière efficace, il n’en reste pas moins que leur sécurité repose sur le postulat que les ordinateurs actuels ne proposent pas la puissance de calcul nécessaire pour casser cette protection. En d’autres termes, ces algorithmes ne sont pas inviolables, mais ils sont robustes sur le temps.

La cryptographie quantique, en revanche, applique les mécanismes de la mécanique quantique aux méthodes de chiffrement pour offrir un double avantage en comparaison aux méthodes classiques : elle promet une sécurité inconditionnelle, tout en ne nécessitant pas d’échange de clé en personne (chose qui était nécessaire auparavant pour garantir une sécurité « absolue » de la clé).

Tout repose sur le principe d’incertitude de Heisenberg, qui indique que certaines propriétés physiques sont liées d’une certaine manière où la mesure d’une value empêche de connaitre la valeur de l’autre. Tout particulièrement, lors de la mesure de la polarisation d’un photon, le choix de la direction à mesurer affecte toutes les mesures qui suivent. Par exemple, si l’on mesure la polarisation d’un photon en observant qu’il passe à travers un filtre vertical, le photon observé sera polarisé verticalement à la sortie du filtre, peu importe sa polarisation initiale. (Dans la théorie quantique, le passage d’un photon à travers un filtre est aléatoire.) Si l’on place ensuite un deuxième filtre, orienté selon un angle Θ de la verticale, il existe une probabilité que le photon passera également à travers ce filtre, et cette probabilité dépend de l’angle Θ.  Plus Θ augmente, et plus la probabilité décroît jusqu’à atteindre 0 si Θ = 90°. Lorsque Θ = 45°, la probabilité est d’exactement ½.
En conséquence, si les photons possèdent une polarisation initiale – sans toutefois connaître laquelle, et que l’on utilise un filtre sur la base 45° / 135° pour mesurer le photon, il est impossible de tirer une quelconque information sur la polarisation initiale de celui-ci.

Ces caractéristiques donnent le principe sur lequel s’appuie la cryptographie quantique. Imaginons maintenant que le photon est la clé de chiffrement en train d’être transmise d’une personne à une autre. Si une personne extérieure voulait écouter la transmission, il lui faudrait avoir un « filtre » aligné de la bonne manière ; autrement, cette personne ne recevrait aucune information et brouillerait la clé transmise par la même occasion, rendant sa présence connue.

Protocole de partage de clé

La cryptographie quantique est souvent réduite à tort au seul processus de QKD (Quantum Key Distribution). Ce processus que nous allons vous présenter s’appuie en effet sur les propriétés de la mécanique quantique pour assurer la production et l’échange d’une clé unique de chiffrement, qui sera connue uniquement de l’émetteur et du récepteur. La puissance de cette étape repose sur la propriété quantique qui rend détectable l’espionnage de l’échange opéré. Ainsi, une fois ce processus réalisé avec succès, on est absolument certain que la clé ait été échangée de manière parfaitement sécurisée.

La QKD s’effectue majoritairement selon le protocole BB84, qui doit son nom à ses auteurs Charles H. Bennett et Gilles Brassard, et dont la mise au point remonte à 1984. L’idée fondatrice est de se servir de l’état quantique de photons émis sur un canal quantique (fibre optique par exemple) avec une certaine polarisation, c’est-à-dire de donner une direction précise à leur champ électrique. Dans le protocole BB84, on polarise ces photons selon quatre angles : 0°, 45°, 90° ou 135°. On parle alors de polarisation rectiligne ou de polarisation diagonale.

Le récepteur, grâce à un polariseur et un détecteur de photons, mesure cette orientation à l’autre bout du canal quantique. Prenons l’exemple d’un polariseur rectiligne placé au bout du canal quantique.

Si le photon a été émis à travers un même polariseur rectiligne, le résultat est net : on récupère tout ou rien selon que la direction soit horizontale ou verticale. En revanche, si le photon a été émis à travers un polariseur diagonal, la sortie sera aléatoire (rien ou horizontale) selon le principe d’incertitude de Heisenberg.

On va se servir de ce principe pour émettre une série de photons, chacun selon une polarisation aléatoirement choisie. Le récepteur, quant à lui, va recevoir cette même série avec un polariseur dont le type (rectiligne ou diagonal) sera choisi aléatoirement pour chaque photon. Si les deux polariseurs sont les mêmes, alors le bit transmis sera correctement interprété.

Une  fois les bits transmis, le récepteur et l’émetteur échangent sur un canal public la manière dont ils ont disposé leur polariseur. Cela permet d’isoler une suite de bits correctement transmis (sur cet exemple, ce sont les bits n° 1, 3, 4 et 7). Enfin, pour s’assurer que  personne n’a intercepté leur clé, l’émetteur et le récepteur peuvent se mettre d’accord pour « sacrifier » certains bits en les comparant publiquement.

Sur l’exemple, on voit que pour le 1er bit, l’orientation du polariseur est la même pour l’émetteur et le récepteur, mais la valeur du bit a été changée à cause de l’espion. Dans ce cas, on abandonne la clé et on répète la procédure éventuellement sur un autre canal quantique. Dans le cas où l’on s’est assuré qu’il n’y a pas eu d’espionnage, la suite de bits restants constitue la fameuse clé quantique.

A titre d’exemple, et pour illustrer la robustesse de la méthode, si l’émetteur et le récepteur comparent 72 bits de leur clé, la probabilité de détecter un espion est de 99,99999%. Enfin, on remarquera que même si l’espion peut théoriquement récupérer des informations, ces informations peuvent être erronées (comme le 4ème bit dans l’exemple ci-dessus).

On notera que dans la pratique, l’émission de photons uniques est extrêmement compliquée à mettre en œuvre. L’idée originale est de parvenir à isoler un émetteur quantique fluorescent individuel (une molécule, un atome, un « ilot quantique » semi-conducteur, …) et de le porter dans son état excité par une émission laser afin qu’il émette un unique photon. De nombreuses recherches portent aujourd’hui sur les centres NV du diamant, qui sont un constituant particulier de sa maille cristalline.

Bibliographie:

[1] ”Mathematical Cryptology”, par Keijo Ruohonen

[2] ”Quantum Cryptography and Privacy Amplification”, par Sharon Goldwater

[3] ”Cryptographie Quantique”, par bibmath.net

[4] ”Photons unique et cryptographie quantique”, par Gaëtan Messin et François Treussard

[5] “Cryptographie Quantique”, par wikipedia.org

Antoine & Quentin

Cryptologie : NTRU – Number Theorists ‘R Us

Dans l’article de cette semaine, nous revenons sur un algorithme moins connu que l’AES ou que le MD5 mais qui risque de prendre de l’importance très rapidement : l’algorithme NTRU.
Celui-ci est un algorithme à clé publique, comme l’algorithme ElGamal ou RSA, qui pourrait d’ailleurs trouver en NTRU un concurrent solide puisqu’on le considère comme une alternative à RSA.

Cet algorithme possède une particularité par rapport aux algorithmes que nous avons présentés précédemment : il est très compliqué du point de vue mathématique, et sa cryptanalyse l’est encore plus. En effet, la base mathématique de l’algorithme NTRU se trouve dans les réseaux, des espaces euclidiens particuliers, et consiste à la résolution dans un réseau d’un problème du plus court vecteur. En conséquence, nous adopterons une approche plus simpliste que celle dont nous avions fait preuve avec l’AES : le but est de comprendre comment l’algorithme fonctionne pour ensuite pouvoir déboucher sur la plus grande force de NTRU, à savoir sa robustesse vis-à-vis des ordinateurs quantiques.

Principe

Génération de la clé :

On prend deux polynômes f et g de manière aléatoire.
Le polynôme  doit satisfaire deux conditions : il doit avoir un inverse modulo q et un inverse modulo p, où q est un modulo important (comme 128 ou 256) et p est un petit modulo (comme 3, par exemple).

On notera que le déchiffrage peut échouer dans certains cas très rares (gap failure). Cependant, pour des paramètres p et q bien choisis, ces probabilités sont tellement faibles qu’elles sont ignorées en pratique.

Les forces de NTRU

Comparé à d’autres algorithmes proposant une sécurité équivalente, l’algorithme NTRU trouve sa force dans sa rapidité et son efficacité en chiffrage et en déchiffrage, que ce soit au niveau hardware que software ; il peut également générer des clés très rapidement, ce qui permet d’utiliser des clés « jetables » (puisque très peu chères à produire).

Mais sa grande force réside dans sa cryptanalyse ; au contraire des algorithmes tels RSA, qui peuvent être mis à mal par des ordinateurs quantiques – puisque la factorisation du nombre chiffré en deux nombres premiers p et q, impensable sur des calculateurs communs, peut être réalisée aisément sur un calculateur quantique selon un algorithme de Peter Shor – NTRU se base sur un problème complètement différent, qui ne possède pas encore de solution par des calculateurs quantiques.

Cryptanalyse

La sécurité de NTRU est intimement liée à la difficulté de trouver le plus petit vecteur (SVP : Shortest Vector Problem) dans un réseau euclidien de grande dimension. Cette caractéristique est extrêmement intéressante puisqu’elle s’avère résistante aux attaques basées sur des ordinateurs quantiques, ce qui n’est pas le cas des algorithmes RSA ou ECC basés sur la factorisation d’entiers de grande taille.

Des recherches ont été menées jusqu’en 2005 afin d’améliorer la sécurité de NTRU, notamment en augmentant les dimensions utilisées (plusieurs centaines). Cela a pour conséquence de complexifier grandement la réduction de base à l’intérieur des réseaux, au détriment de la rapidité de l’algorithme puisque les clés publiques sont plus grandes et les étapes de chiffrement/déchiffrement ont vu leur durée croître. NTRU reste cependant toujours avantageux en termes de performance lorsqu’on le compare à RSA. En effet, lorsque la taille des clés augmente de n bits, le taux d’opérations par seconde décroît en n3 pour l’algorithme RSA alors qu’il ne décroît qu’en n² pour NTRU. Ainsi, le niveau de performance de NTRU augmente avec le niveau de sécurité, ce qui est un atout remarquable.

La cryptanalyse de NTRU s’appuie sur l’algorithme LLL (pour A. Lenstra – H. Lenstra – L. Lovasz) qui date de 1986 et permet la réduction de réseau, c’est-à-dire l’extraction d’une base presque orthogonale (LLL-réduite) à partir d’une base quelconque. En manipulant des polynômes dans Z[X]/(XN-1) et en particulier en décomposant la clé publique h sous la forme d’un produit de deux polynômes f et g, on arrive à utiliser cet algorithme pour trouver une base et obtenir le plus petit vecteur d’un réseau euclidien particulier. Cela nous permet de retrouver les polynômes f et g utilisés pour déchiffrer le message.

Cette méthode n’est implémentable que pour des paramètres de NTRU assez faibles, or les versions actuelles de NTRU sont considérées sûres pour les jeux de critères suivants :

N

p

q

Moderate Security 167 128 3
Standard Security 251 128 3
High Security 347 128 3
Highest Security 503 256 3

Bibliographie:

[1] ”Mathematical Cryptology”, par Keijo RuohonenBibliographie:

[2] ”NTRU: A Public Key Cryptosystem”, par Jeff Hoffstein, Daniel Lieman, Jill Pipher et Joseph H. Silverman

[3] ”Lattice attacks on NTRU”, par Don Coppersmith et Adi Shamir

[4] ”Cryptanalysis of NTRU with two public keys”, par Abderrahmane Nitaj

Antoine & Quentin