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

Cryptologie : Les fonctions de hachage

Dans notre article précédent, nous vous présentions l’algorithme AES. Les algorithmes de cryptographie sont gourmands en ressources et il arrive qu’on ne les utilise que sur une partie condensée du message à coder. C’est à ce niveau qu’interviennent les fonctions de hachage. Depuis, on leur a trouvé d’autres applications, telles que la signature numérique ou le contrôle de conformité des fichiers.

Principe

Les fonctions de hachage sont utilisées en informatique ainsi qu’en cryptologie. Par exemple, il est de de notoriété publique que les mots de passe ne doivent pas être stockés en clair dans une base de données : et bien c’est le résultat de l’opération de hachage qui est en fait stocké.  Ainsi, lorsque l’on procède à une identification, on hache le mot de passe rentré par l’utilisateur et on le compare au hash stocké (on parle aussi d’empreinte).

Les fonctions de hachage sont des fonctions mathématiques particulières : elles possèdent un ensemble de définition généralement infini (par exemple, l’ensemble des chaînes de caractères de toutes tailles) et un ensemble d’arrivée fini, comme une séquence de bits de taille fixe. Il se pose alors naturellement le problème des collisions, qui par construction des fonctions de hachage sont inévitables. Une collision apparaît lorsque l’on obtient la même empreinte pour deux entrées différentes (fonction non-injective).

La problématique de la sécurité des fonctions de hachage repose sur trois points :

  • Il est très difficile de remonter au message en partant de son empreinte (attaque sur la première préimage)
  • Si on dispose d’un message, de son empreinte ainsi que de l’algorithme de la fonction de hachage, il est très difficile de générer un message qui aurait la même signature (attaque sur la seconde préimage)
  • Il est très difficile de trouver deux messages aléatoires qui possèdent la même empreinte (résistance aux collisions)

Par « très difficile », on entend irréalisable avec les moyens techniques actuels et d’un futur proche. En effet, on estime qu’aujourd’hui, les problèmes de complexité supérieure à 280 opérations ne sont pas implémentables.

Pour illustrer cette notion, on peut rappeler brièvement le célèbre paradoxe des anniversaires. Ce dernier apparaît lorsque l’on cherche à déterminer combien de personnes on doit réunir pour avoir une chance sur deux que deux d’entre elles aient leur anniversaire le même jour. La réponse va contre l’intuition puisqu’il s’agit de 23. En effet, avec 23 personnes, on peut former 23 * 22 / 2 = 253 couples, soit plus que la moitié du nombre de jours dans l’année. L’application de ce paradoxe aux empreintes générées par les fonctions de hachage permet de montrer qu’il suffit de 2n/2 essais pour trouver deux empreintes identiques parmi les 2n empreintes de longueur n bits. C’est pourquoi les fonctions modernes de hachage tendent à utiliser des empreintes de 160 à 512 bits.

Un exemple : MD5

Le MD5 (acronyme de Message Digest 5) est la 5e fonction de hash de la série Message Digest, créée par le Pr. Ronald Digest, du MIT. Le MD5 est né en 1991, après que de la cryptanalyse ait suggéré que son prédécesseur, MD4, puisse être compromis au niveau sécurité.
Il est maintenant démontré que le MD5 n’est pas sécuritaire – on le sait d’ailleurs depuis un certain temps, les premières suspicions de faiblesses de l’algorithme remontent à 1993 avec une faiblesse de collision démontrée en 1996 – mais il n’en reste pas moins que le MD5 est un des algorithmes de hachage les plus répandus sur Internet et dans le monde du logiciel en général, en tant qu’algorithme de vérification de transfert de fichier (notamment pour vérifier que le transfert s’est effectué sans erreur). On le trouve notamment comme outil natif dans quasiment toutes les distributions Unix et Linux.

Le principe de fonctionnement du MD5 est fortement basé sur le MD4.
Tout d’abord, on allonge le message original pour le rendre congru à 448 modulo 512 (afin qu’il ne reste que 64 bits avant d’arriver à un multiple de 512), et ceci en y affixant un bit “1″ à la fin puis des bits “0″ jusqu’à la congruence. Ceci est réalisé même si le message original a une longueur de 448 bits.
Ensuite, on ajoute une représentation 64-bits de la longueur originale du message en little-endian. Le tout est donc de longueur multiple de 512 bits.

L’algorithme utilise 8 mots de 32-bits dans son état interne, dont quatre, A, B, C, et D, sont initialisés en début de process comme suivant :

        mot A: 01 23 45 67

        mot B: 89 ab cd ef

        mot C: fe dc ba 98

        mot D: 76 54 32 10

On définit ensuite 4 fonctions supplémentaires F, G, H et I, où :

De plus, on a également une table T[1 .. 64] construite à partir de la fonction sin, où

T [i] = [ | sin i | · 232 ]

Pour chaque bloc, applique 16 passes de la fonction suivante.

                    w = v + si,k(w + φi(x, y, z) + Mπi(k) + T [i · 16 + k])

où w, x, y et z représentent respectivement A, B, C et D, i représente le round en cours (i ∈ {1, 2, 3, 4}) et k le numéro de passe (k ∈ {0, . . . , 15}) de chaque round.

Enfin, φi fait référence aux fonctions F, G, H et I selon le round, et Mπi(k) est le mot πi(k) du bloc d’entrée.

La fonction si,k() est une permutation circulaire des si,k bits.

Le MD5 a réussi à être relativement sécuritaire vis à vis de la cryptanalyse jusqu’à 2004, puisque les failles qui ont été découvertes dès 1994 sont des attaques peu pratiques de collision, puis, sans aucune explication ni justification, Xiaoyun Wang publie un set de collisions pour MD4, MD5, HAVAL-128 et RIPEMD. Depuis, ces attaques ont été améliorées et recherchées, et depuis 2006, il est possible de faire des attaques de collision en moins de 30 secondes.

Même si l’attaque par collision est, en tant que telle, peu menaçante (elle consiste à calculer des hash différents pour trouver un fichier ayant le même hash qu’un autre fichier), elle permet notamment de transférer à un utilisateur peu méfiant un fichier malicieux ayant le même hash que le fichier original attendu.

Malgré cela, et le fait que les vulnérabilités du MD5 soient très bien documentées, elle n’en reste pas moins une des fonctions de hash les plus courantes. On notera que l’administration américaine a préféré le SHA-2 pour ses systèmes d’information.

Bibliographie:

[1] ”Hash functions: Theory, attacks, and applications”, par Ilya Mironov

[2] ”Hash Functions in Cryptography”, par Joseph Sterling Grah

[3] ”Cryptographic Hash Functions”, par Christian Knopf

[4] ”Les fonctions de hachage”, par SecuriteInfo.com

Antoine & Quentin

Cryptologie : A la découverte de l’AES

AES : Introduction et historique

L’AES, ou Advanced Encryption Standard (Standard de Chiffrement Avancé), provient d’une demande du bureau américain des standards, le NIST, qui cherchait en 1997 à remplacer le standard précédent, nommé le DES (Data Encryption Standard). En effet, celui-ci était en place depuis 1976 et nécessitait donc une mise à niveau. En 1998, le bureau avait reçu 15 propositions d’algorithmes, qui furent réduites à 5 finalistes après une première sélection :

  • MARS (IBM)
  • RC6 (RSA Laboratories)
  • Rijndael (J. Daemen & V. Rijmen)
  • Serpent (E. Biham et al.)
  • Twofish (B. Schneier et al.)

S’ensuivit plusieurs années de recherche sur tous ces algorithmes pour trouver des failles et des vulnérabilités, et pendant lesquels il s’est avéré que tous les cinq offraient un niveau de sécurité tout à fait acceptable. Au final, l’algorithme Rijndael fut sélectionné, sur des critères non seulement de sécurité mais aussi de performance, d’efficacité, de flexibilité et d’applicabilité.
Et ce fut donc le 26 novembre 2001, dans la publication U.S. FIPS PUB 197 (FIPS 197), que Rijndael fut officiellement adopté comme étant l’algorithme de l’AES.

Il deviendra le standard de chiffrement de l’administration fédérale américaine le 26 mai 2002, et de manière plus significative, le premier algorithme de chiffrement ouvert à tous approuvé par la National Security Agency (NSA) pour le chiffrement des informations top secret.
À ce jour, il n’existe pas de manière de cracker l’AES – une attaque par brute force prendrait plusieurs fois la durée d’existence de l’Univers. Des vulnérabilités permettent de réduire ce temps, mais pas suffisamment pour rendre une méthode de crackage viable ; la cryptoanalyse de l’AES est détaillée plus bas.

AES : Description de l’algorithme

Le procédé mathématique est très complet et dépasse le cadre de cet article ; je vous enjoins donc à lire la bibliographie à la fin de l’article si vous souhaitez comprendre l’algorithme en détail.
Ici, nous en détaillerons les bases.

L’algorithme de Rijndael consiste en la succession plusieurs étapes, ou rounds, comme détaillé dans la Figure 1. On notera qu’il suffit de 4 opérations et d’une clé pour chiffrer des informations. Chacune de ces opérations sera détaillée plus loin.

Comme prévu dans les spécifications du NIST, l’algorithme de Rijndael propose des longueurs de clés de 128, 192 ou 256 bits ; en revanche, si la spécification de l’AES ne propose que des blocs d’entrée de 128 bits de longueurs, Rijndael permet des longueurs de 128, 192 ou 256 bits en entrée.

Le nombre d’étapes, noté Nr, est dépendant de la longueur du bloc d’entrée, comme en témoigne le tableau suivant :

Longueur d’entrée en mots

Nr

AES-128

4

10

AES-192

6

12

AES-256

8

14

Note : un mot correspond à 32 bits.

On appelle l’état intermédiaire de la phrase en chiffrement comme étant tout simplement l’État. On peut le représenter par une matrice, de manière à ce que cette matrice possède toujours 4 lignes et dont le nombre de colonnes dépende du nombre de bits en entrée et en sortie. Une clé de 192 bits sera représenté par une matrice (4,6), alors qu’un bloc de 128 bits sera représenté par une matrice (4,4).

Bloc en entrée: 32 43 F6 A8 88 5A 30 8D 31 31 98 A2 E0 37 07 34

Clé:                    2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C

Enfin, il est nécessaire de comprendre la notion mathématique de corps fini, puisque tous les calculs et opérateurs mathématiques sont définis sur le corps fini GF(28).

a)      SubBytes

Ici, chaque octet sij de l’État est transformé de la manière suivante :

-          On interprète chaque sij comme étant un élément de GF(28), et on calcule son inverse sij-1. La convention veut que l’inverse de 0 soit 0.

-          On décompose chaque sij en huit bits b7b6b5b4b3b2b1b0 et on pose :

On calcule ensuite :

Le résultat :

est interprété comme étant un octet b’7b’6b’5b’4b’3b’2b’1b’0. C’est le résultat de la transformation SubBytes.

b)      ShiftRows

L’opération ShiftRows, la plus simple des quatre, effectue une permutation des éléments dans la matrice d’État selon la taille NB du bloc d’entrée :

Permutation Ligne 0 Ligne 1 Ligne 2 Ligne 3
NB = 4 Aucune 1 élément 2 éléments 3 éléments
NB = 6 Aucune 1 élément 2 éléments 3 éléments
NB = 8 Aucune 1 élément 2 éléments 3 éléments

Exemple : effectuer un ShiftRows sur l’État s donne :

c)       MixColumns 

MixColumns est une transformation où les colonnes de la matrice de l’État sont considérées comme étant des polynômes du corps GF(28).

Ainsi, chaque colonne (polynôme) est multipliée modulo (1 + z4) par le polynôme fixe :

On peut également représenter ceci sous forme matricielle :

d)      AddRoundKey

Cette opération constitue simplement à ajouter octet par octet le round key à l’État.

où s est l’État, s’ est l’État suivant et w est le round key.

Le round key est tiré de la clé de cryptage comme décrit dans la section suivante.

 e)      Organisation des clés

Les différentes round keys sont dérivées de la clé de cryptage en utilisant un procédé bien défini de key schedule.

Le nombre de round keys nécessaires pour chiffrer des informations dépend de la taille du bloc en entrée : par exemple, pour un bloc de 128 bits, il faudra 11 round keys : 1 pour l’étape initiale, 1 pour l’étape finale, et 9 pour les étapes standard (en effet, Nr = 10).

Ce qui suit est pris dans le cas de 128 bits. Les calculs dans le cas de plus de 6 colonnes dans la matrice de la clé de cryptage (donc 256 bits) sont légèrement différents, mais ne sont pas traités ici.

La clé de chiffrage est notée :

et on appelle Wi la i-ème colonne de K.

Le procédé de key schedule est alors le suivant :

Le calcul pour le cas de W4, W8, etc… est un peu différent :

où SubByte correspond à la transformation de chaque élément (octet) de la colonne, RotByte correspond à une permutation circulaire des éléments d’une colonne verticalement vers le haut. De plusdans le corps GF(28).

AES : Cryptanalyse 

Il existe de nombreux types d’attaques contre l’AES. On peut citer par exemple les attaques “boomerang” qui utilisent des collisions crées localement lors du chiffrement, ou les attaques utilisant les bicliques de la théorie des graphes. Nous avons choisi de présenter rapidement un type d’attaque contre AES qui consiste à résoudre d’énormes systèmes d’équations quadratiques à plusieurs variables.

Ce type de problème, appelé « MQ problem » pour « multivariate quadratic equations », fait intervenir deux méthodes : la « relinéarisation » et les algorithmes XL (ainsi que sa version évoluée, XSL) qui permettent de linéariser ces équations quadratiques, et en même temps d’augmenter le nombre d’équations linéairement indépendantes afin de faciliter la résolution du système. Cette modélisation se fait dans un contexte mathématique particulier, celui des corps finis, aussi appelés corps de Galois en hommage au mathématicien français Evariste Galois. On modélise en particulier les bits de valeur 0 ou 1 dans GF(2) (GF pour Galois Field). La théorie donne une complexité de 2330 opérations pour la résolution de ce problème (sur AES-128), ce qui ne constitue pas un progrès par rapport à une méthode exhaustive de type « brute-force » dont la complexité est 2128.

Une idée pour améliorer la méthode consiste à imbriquer AES dans un autre code appelé BES (Big Encryption System) et de modéliser le système dans GF(28) au lieu de GF(2). Pour cela, on manipule directement les octets (constitués de 8 bits) dont la valeur est comprise entre 0 et 255. En utilisant l’algorithme XSL, on obtient une complexité de 2100 ce qui constitue un progrès remarquable, mais qui reste toujours inexploitable par la puissance actuelle des processeurs. A titre de comparaison, on estime qu’avec un milliard de processeurs, cela prendrait plus de 30 000 ans. Par ailleurs, les estimations fournies par les auteurs de XSL, notamment sur le nombre d’équations générées par l’algorithme, font l’objet d’une polémique au sein de la communauté scientifique. Cependant, personne n’a pu jusqu’alors, fournir une preuve de l’efficacité, ou de l’inefficacité, des algorithmes de type XL contre AES.

Ce qui est sûr, c’est que nous vivons à une époque où les attaques ne peuvent pas être implémentées. La bonne nouvelle, c’est que fondées ou pas, nous sommes à l’abri de ces attaques pour le moment. La mauvaise, c’est que si elles devaient se révéler exactes, nous ne le découvririons que trop tard.

Bibliographie:

[1] ”The Advanced Encryption Standard: Rijndael”, par K. Cartrysse et J.C.A. van der Lubbe

[2] ”Mathematical Cryptology”, par Keijo Ruohonen

[3] ”Specification for the Advanced Encryption Standard (AES)”, par National Institute of Standards and Technology

[4] ”Related-key Cryptanalysis of the Full AES-192 and AES-256″, par Alex Biryukov et Dmitry Khovratovich

[5] ”Algebraic Cryptanalysis of AES – An overview”, par Harris Nover

[6] ”Biclique Cryptanalysis of the Full AES”, par Andrey Bogdanov, Dmitry Khovratovich, et Christian Rechberger

Antoine & Quentin

Cryptologie : Reprise de la veille et articles à venir

Le sujet de veille technologique de cryptographie, bien que facultatif depuis toujours dans les projets disponibles depuis sa création, a toujours trouvé preneur parmi les élèves de l’option Info. Cela fait maintenant 4 ans qu’elle existe; beaucoup de contenu et d’informations ont été traitées et centralisées par les élèves qui nous ont précédé, et il s’agit maintenant pour nous de nous approprier ces connaissances afin de pouvoir approfondir le sujet en choisissant des axes bien particuliers.

En tout premier lieu, je recommande à tous ceux que le sujet intéresse de jeter un coup d’oeil à ce que l’équipe de l’année dernière, composée d’Alice Lan et de Benoit Vandevelde, ont produit – notamment sur le blog de l’année dernière, mais également via leur rapport de fin de projet, très complet, et qui formera un tremplin pour notre étude.
En voici un court résumé:

Ce rapport, comme son nom l’indique, présente un panel assez large des algorithmes utilisés en cryptographie. Les auteurs ont décidé d’aborder la cryptographie depuis ses prémices, à l’époque où l’écriture a été inventée, jusqu’aux algorithmes actuels, infiniment plus complexes, et qui s’appuient parfois sur des domaines de pointe tels que la mécanique quantique. On découvre alors successivement les premiers principes de chiffrement (le code de César, le code de Vigenère, le chiffrement de Vernam) puis les méthodes plus récentes telles que le célèbre algorithme RSA (utilisation de grands nombres premiers), mais aussi des chiffrements basés sur l’utilisation des logarithmes discrets, ainsi que des courbes elliptiques.

On apprend par ailleurs qu’il existe deux grands types de cryptographie:

- La cryptographie symétrique : c’est la plus ancienne historiquement et elle est aussi connue sous le nom « cryptographie à clé privée ». Elle est basée sur l’utilisation d’une même clé secrète, partagée par les personnes qui s’échangent le message. Elle est extrêmement répandue à cause de ses performances remarquables.

- La cryptographie asymétrique : elle est aussi connue sous le nom « cryptographie à clé publique ». Son principe est que, contrairement au code symétrique, les deux interlocuteurs ne partagent pas la même clé. Ainsi, la personne qui veut envoyer un message utilisera la clé publique de son correspondant. Ce dernier déchiffrera le message grâce à sa clé privée que lui-seul connaît. La sécurité est ici améliorée car même en cas d’interception de la clé publique, le message ne pourra pas être déchiffré sans la connaissance de la clé privée.

Enfin, les auteurs nous présentent le concept d’efficacité d’un cryptosystème. Cette connaissance est très importante pour déterminer si le code est robuste à la cryptanalyse (science qui vise à casser les codes de chiffrement). Pour cela, on découvre la notion de théorie de l’information, introduite par Claude Shannon, et comment cette théorie est appliquée en cryptographie, notamment par le biais de l’entropie dont on étend l’usage aux variables aléatoires.

Malgré cela, il reste encore beaucoup de choses à voir sur la cryptographie. Nous pensons notamment que les bases mathématiques avancées de la cryptographie restent un sujet largement ignoré les années précédentes et nous souhaitons développer des aspects particuliers plus techniques, en allant dans le détail de comment certains algorithmes fonctionnent, comme par exemple:

  • AES
  • ElGamal
  • NTRU
  • Fonctions de hash
  • Signatures électroniques

ainsi que pourquoi pas aller plus loin dans d’autres aspects de la cryptographie, comme la cryptographie quantique, qui ont déjà été traités les années passées.
Enfin, nous pensons qu’il serait très intéressant et important de mettre en avant les applications dans le monde réel et notamment l’industrie de ces procédés de cryptage, comme notamment les produits de la société RSA, etc.

Nous espérons que vous aurez autant de plaisir à nous lire que nous en avons à faire ces recherches.

Antoine & Quentin

Bibliographie:

[1] ”Panorama des algorithmes de Cryptographie”, par Alice Lan et Benoit Vandevelde

[2] ”Mathematical Cryptology”, par Keijo Ruohonen