Un algorithme ne s'utilise pas n'importe comment

Avant toute chose, je vais vous demander de retourner au chapitre précédent et d’analyser attentivement le résultat produit par le chiffrement sur les deux messages échangés par nos amoureux. N’y a-t-il pas quelque chose qui vous interpelle ?

Exactement ! Le « o » est systématiquement chiffré 1858, de même que les deux « M » donnent 3852 et que les « r » deviennent tous 737. Et en chiffrant plus de messages, vous arriveriez toujours au même résultat : un caractère donné est toujours chiffré de la même manière, à condition bien sûr d’utiliser la même clé publique. En d’autres termes, bien qu’il soit extrêmement complexe de retrouver quel caractère se cache derrière chaque code, nous avons affaire à un simple chiffrement par substitution.

Très ! Combien y a-t-il de lettres dans l’alphabet français ? Vingt-six. Ou plus exactement, trente-neuf en comptant les lettres avec diacritique (cédille, accent, tréma, etc.), soit soixante-dix-huit avec les majuscules. Ajoutez-y dix chiffres, l’espace et quelques caractères de ponctuation, vous avez grosso modo une centaine de caractères qui représentent la quasi-totalité de tout ce que vous pourrez être amenés à écrire en français.

Or une clé publique, comme son nom l’indique, est publique. Ce qui signifie qu’Ébroïn n’a pas besoin de « casser » la clé de Brunehaut pour lire ses messages : il lui suffit de se faire un tableau de cette centaine de caractères et du résultat que l’on obtient en les passant à la moulinette de la clé publique de Brunehaut pour pouvoir déchiffrer tous les messages que la damoiselle pourra recevoir.

Tenez, vous allez le faire vous-mêmes ! Les minuscules non-accentuées de l’alphabet latin sont regroupées entre le code 97 (pour « a ») et le code 122 (pour « z »). À l’aide de la clé publique de Brunehaut, chiffrez chacun de ces caractères (ainsi que l’espace, de code 32) et faites-vous un tableau de correspondance caractère → code chiffré. C’est fait ? Normalement, vous aboutissez à ceci.

À présent, supposons que vous ayez intercepté le message suivant, chiffré avec cette même clé : « 2571 970 3675 4960 970 3675 244 3675 459 1640 3675 204 1858 1774 3853 3675 970 2437 3675 2814 2437 1640 2127 3675 2127 2437 4640 1774 4964 3853 3675 244 3675 3574 2437 4650 2127 4964 3675 3766 3675 375 970 2127 4650 4515 970 737 ». Essayez de déchiffrer ce que vous pouvez à l’aide de votre tableau : même si vous n’avez pas pu déchiffrer tous les caractères, cela ne vous empêche en rien de comprendre le message.

Ah ben non, je vous donnerai pas la solution, sinon ce n’est pas drôle. Soyez pas faignants, hé !

Vous voyez ! Vingt-six caractères à chiffrer par avance et vous comprenez déjà l’essentiel d’un message qui ne vous était pas destiné ! Vous pourriez même créer un programme qui fasse les maths à votre place et simplement savourer la lecture.

Autrement dit, utilisé comme au chapitre précédent, l’algorithme RSA ne résiste pas plus de quelques minutes à la cryptanalyse !

Damnation !

Pas du tout, il faut juste ne pas l’utiliser comme un amateur.

Vous vous souvenez qu’il n’est pas possible de chiffrer un nombre supérieur à la clé publique $N$ utilisée ? Cela signifie par corollaire que n’importe quel nombre inférieur peut être chiffré avec cette clé-là. Dans la pratique, cependant, ce n’est pas tout à fait vrai. Sur un ordinateur, les données sont stockées sous forme d’octets, c’est-à-dire d’un nombre constitué de 8 bits : ce nombre peut donc aller de 0 à $2^8 - 1$. Et ces 8 bits sont indissociables. Cela a pour conséquence que, pour un $N$ donné, un programme informatique ne pourra pas chiffrer de nombre supérieur à la plus grande puissance de 256 ($= 2^8$) qui soit inférieure à $N$.

Prenons un exemple : la clé que je vous ai donnée au début du chapitre précédent et qui a presque deux cents chiffres. Cette clé a une valeur $N$ comprise entre $2^{639}$ et $2^{640}$. Avec cette clé, il ne sera possible de chiffrer que 79 octets au maximum, car $(2^8)^{79} < N < (2^8)^{80}$. Pourquoi je vous raconte ça ? Nous allons y revenir.

Dans la mémoire de l’ordinateur, un texte est stocké sous forme d’octets, comme n’importe quelle donnée. Le standard le plus pratique pour les représenter est l'Unicode. Dans ce standard, les caractères les plus usuels des alphabets occidentaux sont stockés dans un seul octet, les caractères latins plus originaux, la quasi-totalité des alphabets et syllabaires du monde, ainsi que les caractères chinois, sont stockés dans deux octets, et quelques systèmes d’écriture plus originaux (essentiellement des systèmes utilisés dans l’Antiquité et qui ont depuis disparu) sont stockés dans trois octets.

Un texte complet n’est donc, pour l’ordinateur, qu’une suite d’octets, qu’on lui a dit d’interpréter comme du texte. Mais fondamentalement, un octet est un nombre, et c’est nous humains qui établissons (ou plutôt, faisons établir par l’ordinateur) une correspondance entre un nombre et le caractère qu’il est censé représenter. Et il est tout à fait possible de demander à l’ordinateur d’interpréter la suite d’octets autrement que comme du texte : on va, par exemple, lui dire qu’il faut considérer chaque groupe de quatre octets successifs comme la représentation d’un grand nombre stocké sur quatre octets (donc compris entre 0 et $(2^8)^4 - 1$). De cette manière, le texte « Papa », au lieu d’être interprété comme la suite de nombres stockés sur un seul octet 50 - 61 - 70 - 61 (en notation hexadécimale), sera interprété comme le nombre stocké sur quatre octets 50617061 (ce qui équivaut à $1348550753 = 80 \cdot (2^8)^3 + 97 \cdot (2^8)^2 + 112 \cdot (2^8)^1 + 97 \cdot (2^8)^0$ en notation décimale).

Ce nombre stocké sur quatre octets reste largement inférieur à la limite de 79 octets imposée par la clé publique dont nous parlions tantôt. Il est donc possible de le chiffrer à l’aide de cette même clé, ce qui revient à chiffrer le texte « Papa » d’un seul bloc et non plus caractère par caractère. De cette manière et avec cette clé, on peut par conséquent chiffrer d’un bloc n’importe quelle suite de caractères stockée en mémoire dans 79 octets ou moins.

L’attaque consistant à chiffrer par avance les caractères les plus courants du français et à les rechercher dans le message chiffré n’est plus envisageable. En effet, il faudrait chiffrer par avance n’importe quelle combinaison de 79 ou moins des caractères les plus courants… et prier pour qu’un caractère plus rare comme « ñ » ou « * » ne se soit pas glissé dans le lot ! Comme il y a une centaine de caractères usuels, il y a environ $100^{79} = 10^{158}$ combinaisons de 79 caractères usuels. Vous comprenez d’ores et déjà que la tâche est trop titanesque pour être sérieusement entreprise.

Qu’à cela ne tienne ! Il suffit de découper le message en tronçons de 79 octets et de chiffrer chaque tronçon. Le message chiffré sera composé de chacun de ces tronçons chiffrés mis les uns à la suite des autres. Techniquement, c’est déjà ce que nous faisions en chiffrant les caractères un par un : on découpait le message en tronçons d’un seul octet (parfois deux), que l’on chiffrait individuellement. On applique ici le même processus, mais à une plus grande échelle !

En outre, cette technique peut être appliquée à autre chose qu’à du texte. Une image aussi est stockée dans la mémoire de l’ordinateur sous forme d’une suite d’octets. Elle aussi, on peut la découper en tronçons de 79 octets pour chiffrer chaque tronçon l’un après l’autre. Vous voulez envoyer une photo coquine de vous à votre compagne(on) sans que Google ou votre fournisseur d’accès à Internet ne puisse la visionner ? Découpez-là en tronçons et chiffrez-les avec la clé publique de votre amant/maîtresse ! Cela marche bien évidemment aussi pour la musique, les films, les archives, les logiciels, ou n’importe quoi d’autre qui peut être stocké sur un ordinateur. Désolé pour ceux qui voulaient chiffrer leur grand-mère et s’apprêtaient déjà à la découper en tronçons…

Au stade où l’on en est, Ébroïn est en train d’avaler goulûment son chapeau. Mais ce faisant, il lui vient une idée lumineuse. Il prend son plus beau clavier, écrit une lettre d’insultes qu’il conclut par « Je ne veux plus jamais te revoir, grosse vache ! », la signe « Adalbéron », et l’envoie à Brunehaut en faisant bon usage de sa clé publique. Brunehaut, qui n’est pas bête, et qui rentre à nouveau dans du 36 depuis quelques semaines, se doute qu’il y a anguille sous roche à la lecture du « grosse vache ».

Si les deux amoureux restent en bons termes, cela met cependant en lumière un véritable problème : à partir du moment où la clé publique d’un destinataire est connue de tous, comment être certain que l’expéditeur est bien celui qu’il prétend ? Surtout quand le message dit « Coucou, veuillez utiliser ma carte bleue pour envoyer douze lingots d’or à une adresse au Nigéria que je n’ai encore jamais utilisée, bisoux ! » ?

La solution est relativement simple : il faut signer le message à l’aide d’une information que seul l’expéditeur connaît, mais sans la divulguer pour autant !

C’est pourtant simple ! Il suffit de chiffrer tout d’abord le message à l’aide de votre clé privée, comme si vous étiez en train de le déchiffrer, puis de la clé publique de votre correspondant. De cette manière, lorsque votre correspondant reçoit le message chiffré, il commence par le déchiffrer avec sa clé privée, puis vérifie que vous êtes bien l’envoyeur en utilisant dessus votre clé publique, comme s’il voulait le chiffrer pour vous l’envoyer. Si le message en clair apparaît, il ne fait alors aucun doute que vous avez bien envoyé ce message : vous seul connaissez votre clé privée, vous seul pouvez l’avoir utilisée pour authentifier le message.

Accessoirement, cette authentification vous engage : à moins de déclarer que l’on vous a volé votre clé privée, et d’annuler ainsi tout ce que vous avez pu faire avec depuis le vol supposé, vous ne pouvez pas nier être l’expéditeur d’un message utilisant ce type de signature.

Cependant, le gros défaut de la cryptographie asymétrique, c’est que les fonctions mathématiques utilisées consomment énormément d’énergie car elles demandent beaucoup de calculs : le chiffrement et le déchiffrement sont longs, parfois très longs. C’est pourquoi, dans la vraie vie, on signe rarement un message en le chiffrant en entier avec sa clé privée.

On va plutôt signer un « résumé » du message. Mais ce résumé doit avoir un certain nombre de caractéristiques pour être valide.

1. Il doit être plus petit que le message d’origine, sinon, cela n’a pas grand intérêt.
2. Il doit être absolument impossible de retrouver le message d’origine à partir du résumé. En effet, le résumé est chiffré à l’aide de la clé privée de l’expéditeur, et déchiffré à l’aide de sa clé publique, qui est largement diffusée. Cela signifie que n’importe qui peut déchiffrer la signature et donc lire le résumé. S’il existait un moyen de remonter jusqu’au message à partir du résumé, toutes les mesures de chiffrement appliquées au message seraient vaines, un attaquant n’ayant qu’à le reconstituer à partir du résumé facile à obtenir.
3. Deux messages même similaires doivent avoir des résumés différents. De cette manière, il est possible de savoir qu’un message a été altéré lors de son transfert si le résumé réalisé au départ et signé est différent d’un résumé réalisé à la réception. Il est important de garantir l’intégrité du message lors de son transfert : quand vous payez 100€ par carte bancaire, vous ne tenez pas à ce que, du fait des aléas de l’Internet ou de l’action malveillante de quelqu’un, votre banque reçoive un message lui demandant de payer 10000€.

La tâche semble ardue, n’est-ce pas ? Il existe pourtant un type de fonction qui remplit exactement ces objectifs : on les appelle des fonctions de hachage. Les plus célèbres sont SHA-1, MD5 ou Tiger. On ne rentrera pas dans le détail de leur fonctionnement, cela mériterait un tuto à part entière. Il faut seulement retenir que ces fonctions ont trois caractéristiques essentielles.

1. À partir d’une entrée de n’importe quelle taille, elles produisent un résultat de taille fixe, souvent 128, 160 ou 256 bits.
2. Il est strictement impossible de savoir quelle entrée a produit un résultat donné : contrairement à RSA, il n’y a pas de porte dérobée, la fonction est vraiment à sens unique.
3. Deux entrées extrêmement similaires, même si elles ne diffèrent que d’un bit, donneront des résultats radicalement différents. Par corollaire, il est très difficile de produire volontairement un message qui donnera le même résultat qu’un autre message donné, ce que l’on appelle une collision.

Il n’existe pas de moyen plus simple de définir ce qu’est une fonction de hachage : si une fonction respecte ces trois impératifs, alors c’est une fonction de hachage, point final. Le « résumé » d’un message produit par une fonction de hachage est appelé un condensat.

Le principe de la signature par clé privée ou signature numérique est de réaliser un condensat du message que l’on veut envoyer, de le chiffrer à l’aide de sa clé privée, et de joindre cette signature au message afin de l’authentifier. Quand Brunehaut reçoit un message ainsi signé, elle déchiffre le condensat avec la clé publique d’Adalbéron, déchiffre le message avec sa clé privée, réalise un condensat du message déchiffré (à l’aide de la même fonction de hachage, bien entendu) et compare les deux condensats : ils doivent être identiques, sans quoi le message peut être un faux ou avoir été corrompu.

Seul le condensat étant chiffré par la clé privée, l’ensemble du processus est beaucoup plus rapide que si l’on chiffrait le message entier avec la clé privée de l’expéditeur puis la clé publique du destinataire.

À présent, voyons un exemple concret. Pour pouvoir manipuler des messages faisant un peu plus qu’un seul caractère, sans pour autant utiliser des nombres à 120 chiffres, nous allons utiliser la clé $(N = 8889895013, E = 23)$, avec $P = 72421$ et $Q = 122753$. L’exposant de déchiffrement est $D = 3865086887$, comme vous pouvez le calculer vous-mêmes. Quant à Adalbéron, sa clé sera $N = 8042009699$, $E = 4001$, $D = 110547521$. Ces deux clés sont légèrement supérieures à $2^{32}$ : comme nous l’avons vu dans la section précédente, elles nous permettront de chiffrer au maximum quatre octets (soit 32 bits) à la fois. Il faudra donc découper tout message plus long en tronçons de quatre octets.

En guise de fonction de hachage, nous allons utiliser Adler-32. Ce n’est pas une très bonne fonction de hachage, parce qu’il est facile d’obtenir des collisions, mais elle produit des condensats de 32 bits, ce qui reste facilement manipulable et peut être chiffré en une seul fois à l’aide des clés fournies ci-dessus.

Adalbéron désire envoyer le message « Douce amie ! ». Il commence par le découper en tronçon de quatre octets, ce qui nous donne 1148155235, 1696620909 et 1768235041. Chacun de ces tronçons est chiffré à l’aide de la clé publique ci-dessus : 1338172656, 923473543 et 8857666592. Ensuite, Adalbéron génère le condensat de son message par Adler-32, ce qui donne 1bb103ee (en hexadécimal), c’est-à-dire 464585710 (en décimal). Il applique alors sa propre fonction de déchiffrement sur ce condensat : $464585710^{110547521} \ [8042009699] = 2226882204$. Il ne lui reste plus qu’à envoyer le message « 1338172656 923473543 8857666592 2226882204 » à Brunehaut.

À la réception du message, celle-ci procède en plusieurs étapes. D’abord, elle déchiffre les trois premiers nombres avec sa clé privée, ce qui lui permet de retrouver le message : je ne vous montre pas, vous savez comment faire. Ensuite, elle applique la fonction de chiffrement d’Adalbéron au dernier nombre (la signature) : $2226882204^{4001} \ [8042009699] = 464585710$. Enfin, elle génère le condensat par Adler-32 du message tel qu’elle l’a déchiffré, ce qui est censé donner 464585710 (en décimal) aussi. Elle a alors la preuve que le message a bien été envoyé par Adalbéron. S’il s’avérait que les deux condensats ne correspondent pas, cela signifierait que, soit le message n’a pas été envoyé par Adalbéron, soit le message a été altéré en chemin. Dans les deux cas, elle peut le mettre à la poubelle.

Mais il y a mieux encore ! Appliquer la fonction de chiffrement de votre destinataire à l’ensemble du message est également une opération très énergivore : il faudrait pouvoir en chiffrer le moins possible. Vous pensez sans doute à une fonction de compression pour réduire la taille du message, mais cela ne suffirait pas. La solution ultime s’appelle la cryptographie hybride.

Celle-ci fut inventée en 1991 par un dénommé Phil Zimmerman lorsqu’il créa et mit à disposition du public sur Internet le logiciel PGP, dont vous avez peut-être entendu parler. Le principe est vraiment simple, mais il fallait y penser.

Un système cryptographique symétrique, quel qu’il soit, peut être extrêmement solide, presque autant qu’un système asymétrique. Sa seule réelle faiblesse réside dans le moment où il faut faire parvenir la clé à son destinataire. Le principe de la cryptographie hybride, c’est de chiffrer le message à l’aide d’un algorithme symétrique le plus solide possible (de nos jours, on utiliserait AES), parce que c’est beaucoup plus rapide qu’avec un système asymétrique, puis de chiffrer la clé et seulement la clé à l’aide du système asymétrique. Il ne reste plus qu’à envoyer le message chiffré, la clé chiffrée aussi et la signature réalisée comme on l’a vu plus haut.

De cette manière, le système est tout aussi sécurisé, mais on réduit comme peau de chagrin la quantité de données à chiffrer de manière asymétrique : les clés de systèmes symétriques dépassent rarement 256 bits de longueur, et les fonctions de hachage actuellement sur le marché ne produisent pas d’empreinte de plus de 512 bits. Au maximum, les fonctions symétriques n’auront à travailler que sur un millier de bits.

À quelques détails près, vous avez là le système cryptographique le plus robuste possible avec les connaissances actuelles. Quelques années après sa sortie, il a été dit de PGP que c’était ce qui s’approchait le plus d’une protection de niveau militaire donnée aux particuliers. Ce n’est pas pour rien que ce logiciel, ou son équivalent libre GnuPG, est le plus utilisé au monde pour protéger ses mails.

Bon, je vous entends demander à cor et à cri un exemple. D’accord, d’accord. Adalbéron doit envoyer le message « RDV au moulin ce soir » à Brunehaut. Pour cet exemple, nous utiliserons les dernières clés en date qui, je le rappelle, ne permettent pas de chiffrer plus de quatre octets donc 32 bits.

1. Il chiffre son message à l’aide de l’algorithme symétrique AES et de la clé « 4891e674ff312b9519df3245b7d1c3ff ». Pour la petite histoire, il s’agit du condensat MD5 de « Brunehaut, je te kiffe ! ». Le résultat (découpé en tronçons de 32 bits et en notation hexadécimale, pour plus de clarté) est le suivant : « 7bd19a87 3c0f39a5 d7656446 d1d5007a 21757f1d 3a36fd25 97c527cf 5f03f75d ».
2. Il réalise un condensat par Adler-32 de son message (4d23075c), qu’il signe à l’aide de sa fonction de déchiffrement : « c8c43b7e » (en hexadécimal, encore).
3. Il découpe la clé qu’il a utilisée pour AES en tronçons de 32 bits et les chiffre à l’aide de la clé publique de Brunehaut : « 1bc83cd40 1bcb41456 1c1936f3f fa66823f » (en hexadécimal, toujours).
4. Il envoie à Brunehaut le message suivant.

À la réception, Brunehaut réalise un déchiffrement en 6 étapes.

1. Elle déchiffre la clé AES à l’aide de sa propre clé privée.
2. Elle déchiffre le message à l’aide de la clé AES qu’elle vient de trouver.
3. Elle génère par Adler-32 un condensat de ce message fraîchement déchiffré.
4. Elle déchiffre la signature à l’aide de la clé publique d’Adalbéron.
5. Elle compare les deux condensats ainsi obtenus.
6. S’ils sont identiques, elle se plonge goulûment dans la lecture du message qu’elle a déchiffré.

Parce que ce sympathique M. Zimmerman a eu des déboires importants avec diverses instances de son pays. Comme un certain Edward S. dont nous ne parlerons plus.

En premier lieu, il faut savoir que la loi américaine permet de breveter le logiciel, contrairement à la loi française. En second lieu, il faut savoir que nos amis Rivest, Shamir et Adleman, pas fous, avaient breveté le RSA et même créé une société privée pour l’exploiter. Ce sont eux qui ont attiré le regard de la justice sur Zimmerman, au motif qu’il était un vilain pirate qui mettait à disposition de n’importe qui des moyens de protéger sa vie privée, certes, mais gratuitement, ce qui est bien plus grave.

Là où ça devient rigolo, c’est que lorsque les autorités américaines s’emparent du dossier en 1993 et ouvrent une enquête criminelle au sujet de ce brave homme, ce n’est pas au sujet d’une éventuelle contrefaçon. Non. C’est sous des accusations de complicité de terrorisme. Oui, déjà.

Car il faut savoir, en troisième lieu, que jusqu’à la fin des années 1990, la loi américaine considérait qu’exporter hors du territoire national un outil cryptographique utilisant des clés de plus de 40 bits (le terme technique pour des clés de moins de 40 bits est « une protection de merde ») équivalait à exporter des munitions d’armes de guerre. À des terroristes, puisque c’est à l’étranger. Et puisque le logiciel était trouvable sur Internet, il y avait bien exportation hors du territoire. Pour contourner cela, Zimmerman a été obligé d’imprimer le code de PGP sur des livres et d’exporter les livres, qui sont eux protégés par le premier amendement de la constitution américaine.

L’enquête a duré trois ans, avant d’être abandonnée sans raison officielle en 1996. La raison officieuse est que Zimmerman a reçu de très nombreux mails et lettres de soutien venues du monde entier, ce qui aurait fait plier les services d’espionnage américains. Il y a peut-être une autre raison, encore plus spéculative, que nous verrons dans la section suivante.

Il reste une grosse faille dans notre système cryptographique. La seule qui soit à l’heure actuelle encore réellement exploitable, au moyen de ce que l’on appelle l’attaque de l’homme du milieu.

Revenons à Ébroïn. Faute de meilleure solution, il décide de placer une troupe de ses fidèles sur la route qui mène de chez Adalbéron à chez Brunehaut, pour intercepter tout messager qui irait de l’un à l’autre. Lorsqu’Adalbéron demande à Brunehaut de lui envoyer sa clé publique, Ébroïn lui envoie en vérité sa propre clé publique et demande à Brunehaut la sienne. Il fait de même dans l’autre sens. À ce stade, chacun des amoureux a la clé publique d’Ébroïn en pensant que c’est celle de l’autre, et Ébroïn possède la clé publique des deux. De cette manière, lorsque l’un d’entre eux envoie un message, il l’intercepte, le déchiffre avec sa clé privée, éventuellement le modifie, et le chiffre à nouveau avec la vraie clé du destinataire, avant de faire suivre.

Une personne malveillante s’est glissée au milieu de la communication au moment de la transmission des clés publiques et met tout le système en l’air. Patatras ! On en revient au même point qu’avec les chiffrements symétriques : comment transmettre la clé de chiffrement, certes publique, à son destinataire sans que quelqu’un l’intercepte à des fins douteuses ?

Petite parenthèse avant l’explication. Vous vous dites peut-être qu’une telle attaque a peu de chance d’arriver, qu’elle nécessite quand même de gros moyens. Elle est beaucoup plus facile à mettre en œuvre que vous pourriez le penser. Quand vous vous connectez à un WiFi public, qui vous garantit que votre connexion va directement au routeur et ne transite pas par l’ordinateur d’un autre des clients affairés ? Si vous allez voir vos comptes bancaires au boulot, comment être certains que le responsable du service informatique ne détourne pas ce genre de requêtes avant qu’elles ne sortent du bâtiment ? Quand vous achetez en ligne à l’aide de votre numéro de carte bleue, qui vous dit que votre fournisseur d’accès à Internet ne le note pas dans un coin en profitant de sa position obligatoire d’homme du milieu ?

La seule solution connue est de faire certifier la clé publique par un intermédiaire de confiance. Par exemple, au lieu de s’envoyer mutuellement leur clé publique par la poste, Adalbéron et Brunehaut la confient chacun à leur ami Warnachaire en qui ils ont toute confiance et qu’ils peuvent rencontrer physiquement. Et c’est lui et lui seul qui distribue les clés publiques quand on les lui demande, et en main propre.

L’idée n’est vraiment pas mauvaise. Warnachaire étant ami un peu avec tout le monde, bien vite, les clés de Chimnechilde, de Drogon de Frédégonde et de Genséric viennent rejoindre son trousseau. Il est devenu une autorité de certification ou AC pour les intimes. Seulement, quand il ne peut pas se déplacer en personne, Warnachaire est obligé d’envoyer la clé voulue authentifiée par sa propre clé privée. Comment certifier que la clé publique qui va avec est bien la sienne et pas celle d’Ébroïn ?

Eh bien sa clé publique est elle-même confiée à une AC de niveau supérieur, qui confie sa propre clé à une autorité supérieure, et ainsi de suite, créant ainsi une pyramide de certifications.

Ce système de certificats distribués par des autorités hiérarchisées est celui qu’utilise le système TLS, plus connu sous le nom de SSL. Oui, oui, celui-là même qui se cache derrière les adresses en HTTPS de votre navigateur.

Tout à fait ! C’est encore l’utilisation de RSA la plus courante. Et si nous vivions dans un monde parfait, elle serait excellente. Mais il y a un hic. Les autorités de certification étant organisées de manière pyramidale, tout en haut ne se trouvent que quelques dizaines d’autorités « ultimes ». Or on sait de source sûre depuis 2010 que la NSA fait pression sur les AC américaines de plus haut niveau pour obtenir des certificats « de complaisance » et sans doute sur les AC des autres pays aussi. Et nul doute que les services d’espionnage des autres pays font de même avec leurs AC nationales.

Si, on peut faire autrement. Des logiciels comme GnuPG utilisent le système du réseau de confiance, ou web of trust en anglais. Dans les infrastructures à clés publiques comme le réseau de certification de SSL, une seule des deux parties certifie l’autre, ce qui génère la hiérarchisation dont on a parlé. Au contraire, dans un réseau de confiance, les deux parties se certifient mutuellement, créant ainsi un système décentralisé. Voyez plutôt.

À l’occasion d’une rencontre en personne, Brunehaut et Adalbéron s’échangent leurs clés publiques respectives. Quelques temps plus tard, Brunehaut rend visite à sa meilleure amie Chimnechilde, et elles échangent leurs clés. Lorsque Chimnechilde veut obtenir la clé publique d’Adalbéron, elle la demande à Brunehaut, qui la lui donne en la certifiant avec sa propre clef privée. Comme Chimnechilde a une confiance totale en Brunehaut, elle accepte la clé sans problème. Dans son message à Adalbéron, elle lui donne sa clé publique, et comme c’est la meilleure amie de Brunehaut, Adalbéron la range dans ses contacts de confiance. De cette manière, si Brunehaut change de clé d’une manière ou d’une autre, elle n’a qu’à la donner à Chimnechilde en mains propres et celle-ci pourra la transmettre à Adalbéron, qui a toute confiance en elle.

On peut y ajouter encore une subtilité. Brunehaut est également amie avec Haremburgis et lui accorde toute sa confiance. Mais Adalbéron trouve que c’est une oie blanche, qui se laisse facilement berner, alors quand il obtient sa clé par l’intermédiaire de Brunehaut, il la range dans ses contacts de confiance limitée. Warnachaire subit le même sort : depuis que le comte Leudegisèle a menacé de massacrer toute sa famille s’il ne « coopérait pas avec la justice », tout le monde sait que ses informations sont sujettes à caution ; mais comme c’est un vieil ami, on ne va pas le rejeter totalement. Quand Adalbéron a besoin de la clé de quelqu’un, il demande à tous ses contacts. Si un de ses contacts de confiance lui donne une réponse, il l’accepte. Pour ses contacts de confiance limitée, en revanche, il faut qu’un nombre suffisant d’entre eux (généralement trois) lui donnent la même réponse pour qu’il l’accepte.

De cette manière, un réseau de confiance totalement décentralisé se constitue peu à peu et il est beaucoup plus difficile, voire impossible, à une agence gouvernementale de falsifier les informations.

Avant de terminer cette section, je voudrais revenir sur la remarque que j’ai faite en fin de section précédente. Vous vous souvenez que les poursuites contre Zimmerman ont cessé en 1996 sans raison apparente ? En 1995, le navigateur Netscape implémente la première version publique de SSL. Pour rappel, cette année-là, il était utilisé par environ 70 % des internautes. Ce n’est peut-être pas une coïncidence.

Abordons à présent certaines attaques plus fourbes à l’encontre de RSA.

La première d’entre elles a été démontrée par Johan Håstad en 1986 et utilise le théorème des restes chinois. Celui-ci sert à résoudre le difficile problème d’un système de $n$ équations de la forme $x \equiv a_i \ [N_i]$. Or, si le même message est envoyé à plusieurs personnes ayant des $N$ différents mais des $E$ identiques, chaque fonction de chiffrement vaut $x^E \equiv y_i \ [N_i]$, où $y_i$ est le texte chiffré envoyé à chaque destinataire : il suffit de $E$ destinataires différents pour que le théorème fonctionne et qu’on puisse récupérer $x^E$, donc en un temps très réduit le message en clair.

Cela signifie qu’il est dangereux d’utiliser un $E$ de petite taille. Premièrement, parce qu’il sera plus facile de réunir $E$ messages identiques. Deuxièmement, parce que la probabilité que vous ayez le même $E$ que d’autres gens est beaucoup plus forte avec $E = 3$ qu’avec $E = {2}^{2^{42}}-1$. Troisièmement, parce qu’avec un $E$ suffisamment grand, même si l’attaque reste théoriquement possible, le temps nécessaire à la résolution du système d’équations devient trop important pour être rentable.

En outre, Håstad a montré que rajouter du « bruit » aux différents messages pour qu’ils soient légèrement différents ne fonctionne pas si la fonction utilisée est déterministe. En 1997, Don Coppersmith a étendu l’attaque en démontrant que même un « bruit » aléatoire ne suffit pas à protéger le message si ce « bruit » est trop court, mais si je vous explique comment fonctionne l’attaque, on y est encore après-demain.

Dans un tout autre genre, RSA est sensible aux attaques par texte chiffré choisi. En effet, si un attaquant cherche à déchiffrer un message $y$ donné, il peut demander au destinataire du message de lui déchiffrer le message $y \cdot r^E \ [N]$ où $r$ est un entier pris au hasard : le résultat du déchiffrement sera $x \cdot r \ [N]$, à partir duquel il est très simple de retrouver $x$. Cette attaque a toujours été théorique : pourquoi quelqu’un accepterait-il de déchiffrer pour vous l’intégralité d’un message chiffré d’une manière qui indique qu’il est destiné à lui seul ? Il faudrait vraiment que la victime soit idiote.

Mais un beau jour de 1998, Daniel Bleichenbacher a montré que cette attaque pouvait être beaucoup plus pernicieuse qu’on ne le pensait alors. Supposez un système informatique qui attend des messages formatés d’une certaine manière (donc à peu près tous les serveurs, HTTP, IRC, FTP ou n’importe quoi) mais chiffrés avec sa clé publique. Si un seul bit, ou mieux quelques octets, du texte clair sont strictement identiques dans tous les messages en clair qu’attend ce système — par exemple, le magic number qui identifie le format — et si le système renvoie un message d’erreur lorsque le message déchiffré ne correspond pas au format qu’il attendait, alors il existe un algorithme qui permet dans un temps très raisonnable de déchiffrer n’importe quel message chiffré adressé à ce système que l’on aurait intercepté.

Ces recommandations sont d’autant plus importantes quand le texte en clair est court, par exemple une clé de cryptographie symétrique ou un condensat à signer.

C’est là l’objet de l'Optimal Asymmetric Encryption Padding (OAEP). Il s’agit d’un schéma de bourrage qui nécessite pour fonctionner un générateur de données aléatoires efficace et deux fonctions de hachage $G(x)$ et $H(x)$ donnant un résultat de taille fixe, respectivement $k_1$ et $k_2$. Les étapes de l’algorithme de bourrage sont alors les suivantes.

1. Le message est complété avec des 0 jusqu’à atteindre une taille de $k_1$ bits. On l’appelle $m_0$.
2. Le générateur de données aléatoires génère $k_2$ bits de données, appelées $r$.
3. On calcule $X = m_0 \oplus G(r)$ où $\oplus$ est la fonction « ou exclusif » ou XOR.
4. On calcule $Y = H(X) \oplus r$.
5. On concatène $X$ et $Y$ dans cet ordre, et c’est ce message seulement que l’on chiffre à l’aide de RSA.

La fonction « ou exclusif » étant son propre inverse, il est très simple de répéter l’opération en sens inverse. Ce schéma de bourrage a aussi comme intérêt qu’il n’est pas possible de reconstituer le message en clair bourré complet à partir d’un fragment de celui-ci.

Les attaques présentées dans la section précédente cherchaient à déchiffrer le message sans pour autant obtenir la clé privée du destinataire. Celles que nous allons voir ici sont beaucoup plus dangereuses, car elle permettent de casser une clé privée et donc d’usurper totalement l’identité de quelqu’un.

Tout d’abord, sans surprise, il faut que $N$ soit suffisamment grand pour ne pas être factorisable dans un délai raisonnable, même en faisant travailler des milliers d’ordinateurs en parallèle dessus. À l’heure actuelle, on est capable de factoriser des $N$ de 768 bits de long en deux ans. Le $N$ de 640 bits de long que je vous ai donné comme exemple de clé réelle a été factorisé en 2005 en seulement cinq mois à l’aide de tout juste 80 ordinateurs. Au vu des prédictions sur les capacités futures des ordinateurs, un $N$ de 1024 bits peut être utilisé pour une information qui sera périmée sous un délai d’un an ou deux, un de 2048 bits est pleinement acceptable pour une utilisation longue, et un de 4096 bits garantit une inviolabilité à peu près définitive.

On a vu dans la section précédente qu’un $E$ de petite taille était dangereux, mais il existe également des attaques efficaces contre les $D$ de petite taille. Michael Wiener a exposé dans un article de 1990 que le développement en fractions continues de $\frac E {N}$ permettait de découvrir très vite $D$ si celui-ci est inférieur à $N^{0,25}$ environ. Les gens ont tendance à choisir de petits $D$ parce qu’ils rendent le déchiffrement ou la signature de messages beaucoup plus rapides, mais c’est une erreur : il existe une technique pour maintenir un bon niveau de performances même avec un $D$ de grande taille, que nous exposerons dans le chapitre suivant.

En outre, la factorisation de Fermat est d’autant plus efficace que l’un des facteurs est proche de $\sqrt N$, c’est-à-dire, dans notre cas où il n’y a que deux facteurs, que $P$ et $Q$ ne doivent pas être trop proches, sans quoi la factorisation se voit grandement facilitée. Dans un autre ordre d’idée, si $P - 1$ ou $Q - 1$ se décompose en facteurs premiers exclusivement de petite taille, l'algorithme p-1 de Pollard est capable de factoriser $N$ en peu de temps. Il faut donc prêter attention à ces deux faiblesses lorsque l’on génère une clé privée.

Il est enfin une « faiblesse » contre laquelle on ne peut pas grand chose. Si deux personnes utilisent deux $N$ différents mais que par hasard ces deux $N$ aient un facteur en commun, un simple calcul de PGCD permet de retrouver ce facteur commun et donc le deuxième facteur des deux $N$ par division. Là où ça devient plus gênant, c’est qu’en collectant un grand nombre de clés publiques, la probabilité que l’une d’entre elles au moins ait un facteur commun avec la clé que l’on veut attaquer augmente. Et pour accélérer encore le processus, on peut multiplier entre elles toutes les clés publiques connues, donnant un nombre colossal mais encore manipulable, et procéder au test de PGCD avec ce nombre-là : seul le premier calcul sera vraiment long. Le seul moyen de se prémunir contre cette recherche semi-exhaustive est de disposer d’un bon générateur de nombres aléatoires lors de la création des clés privées.

Il ne reste que trois attaques connues à mentionner.

Premièrement, à cause de la combine visant à améliorer les performances de déchiffrement dont on a parlé il y a peu, il est possible, en étudiant le temps que mettent plusieurs messages donnés à être déchiffrés, de déterminer rapidement la valeur de $D$. Le seul moyen de contrer cette méthode est de s’assurer que le temps de déchiffrement ne soit plus dépendant uniquement de $D$. Pour ce faire, on génère un nombre aléatoire $r$, et on déchiffre non pas $y$ mais $r^E \cdot y \ [N]$ : le résultat sera $r \cdot x \ [N]$, qui permet très simplement de retrouver $x$. Un même message mettra à chaque fois un temps différent à être déchiffré, rendant impuissante l’attaque par chronométrage.

Deuxièmement, la plupart des processeurs modernes utilisent un système de prédiction de branchement pour accélérer le traitement des programmes. Dans deux articles parus en 2006, il a été présenté une utilisation possible des erreurs de prédiction de ces systèmes, qui permettrait à un programme de l’espace utilisateur sans permissions particulières de découvrir extrêmement rapidement la clé privée $D$ utilisée par un déchiffrement de RSA ayant lieu en parallèle. Toutes les méthodes de protection connues actuellement seraient inefficaces face à ce genre d’attaques. Cela étant, à ma connaissance, cette attaque a été peu étudiée, donc on ne connaît pas encore bien son impact réel, mais on ne sait pas non plus comment s’en protéger.

Troisièmement, il est connu depuis bien longtemps que, si l’on parvient un jour à construire un ordinateur quantique, factoriser les clés publiques utilisées par RSA deviendra un jeu d’enfant. Cependant, ne vous inquiétez pas outre mesure : de tels ordinateurs sont à l’heure actuelle pure spéculation, et s’ils venaient à exister un jour, ils ouvriraient la porte à la cryptographie quantique (déjà théorisée depuis longtemps) à côté de laquelle RSA est aussi sécurisé que du morse.