SSTIC 2003 (Eric Filiol)

[le début a été coupe - NDLR]
pour doter le monde libre d'un systeme de chiffrement gratuit, et dont on
connaitrait le code, à ce concours n'a repondu qu'une seule société : IBM
et c'est devenu, apres transformation pendant 9 mois quand même dans les officines de la NSA, le DES. Or entre la version qui a été soumise au
concours, qui était Lucifer, et la version finale qui est le DES, il y a
eu quand même des modifications drastiques qui n'ont d'ailleurs jamais
été expliquées :
- réduction de la clé de 128 a 56 bits.
- modification en particulier, de ces fameuses boites S qui sont le coeur
du coeur du système, sans autre forme de procès, surtout sans explication, et c'est vrai que pendant des années, la question d'ailleurs se pose toujours, c'est un problème ouvert, le probleme est de savoir s'il y a des fonctions cachées dedans.
Si on sait éventuellement libeller le problème d'un point de vue
scientifique, on ne sait toujours pas le résoudre.
Et puis il y a le problème de son utilisation aux USA, c'est que le DES qui
était distribué gratuitement au monde libre, est quand même, comme son successeur AES, interdit d'emploi aux USA pour le chiffrement des données sensibles, alors que par ailleurs, il est precisé dans des documents fédéraux officiels, qu'il ne doit pas etre utilisé pour des données sensibles. Tout cela mis bout a bout on peut se poser des questions.

or justement ce que je veux vous montrer c'est que le fait de réutiliser
cette clé en utilisant une certaine famille de codes, permet au contraire de retrouver des informations sur cette dernière.

Alors je vais suivre le plan suivant, quelques définitions et rappel, en
particulier j'expliquerais ce que sont ces codes correcteurs d'erreur que j'utilise, à savoir les codes a répétition.

Ce sont les codes les plus basiques qu'il soit.
Et puis je parlerais un peu de chiffrement par bloc et de la cryptanalyse
linéaire qui est actuellement la meilleure ,entre guillement, technique de
cryptanalyse connue pour ces systèmes qui est du au Japonais Matsui, qui a été raffinée à travers un certain nombre de variantes mais le coeur est quand même du a Matsui.

Et ensuite je vous présenterais justement cette fameuse technique P.D.R.C qui utilise des codes à répétitions.
On verra justement comment on peut lier chiffrement à bloc et code à
répétition.
Ensuite je vous décrirais l'attaque, vous verrez qu'elle est d'une
complexité tout a fait rudimentaire.
Et je ferais la liste d'un certain nombre de problèmes ouverts qui n'ont pas encore été résolus.
Et puis surtout je vous présenterais ces résultats éxpérimentaux à travers 200 cryptanalyses qui ont été faites, parce que ces résultats etaient contestés, de manière d'ailleurs on va dire pas tout a fait fair play, c'est pour ca qu'on a du regénérer pendant 3 mois de calcul tous les résultats en générant notament toutes les valeurs intermédiaires pour justement faire taire les critiques.

Alors qu'est ce qu'un code a répétition ?
Quand vous transmettez de l'information, imaginez que ca passe à travers un tuyaux, le long du tuyaux il y a des gens qui peuvent taper dessus, ce qui sort a l'autre bout du tuyaux quand vous collez votre oreille n'est pas forcément ce que vous avez envoyé a l'entrée
autrement dit il y a du bruit, et ce bruit intervient avec une certaine
probabilité P.
Donc on dit qu'on a un canal binaire symétrique, pourquoi binaire parce
qu'il travaille sur des zéros et des uns, et symétrique parce que la probabilité P de modifier un zero ou un un est la même.
Alors ce que l'on fait quand on veut transmettre de l'information dans un
tel canal, on peut utiliser un code a répétition, on peut décrire ca comme un code linéaire de longueur n et de dimension 1, c'est l'aspect mathématique des choses, tout ce que l'on sait c'est que pour transmettre un symbole je le répète n fois, à ce moment la je peux corriger (n-1)/2 erreurs, prenons un exemple :
imaginons que je veuille transmettre ce message : 01100
j'utilise un code 3 répétitions, certes c'est couteux en terme de bande
passante mais là n'est pas le problème, pour nous ca n'est pas handicapant. Chaque bit est envoyé 3 fois : donc la
j'envoie 000111111000000. Et imaginons que l'on recoive ce message, en
particulier on remarque que le premier triplet est bruité, quelle est la règle de décodage ? on prend
un maximum de vraissemblance : autrement dit dans un triplet, et c'est la
raison pour laquelle on prend toujours n impair, je compte le nombre maximum de symboles et je retient celui qui
est le plus prêt, donc autrement dit 010, le nombre de zéros étant supérieur au nombre de 1 je décide que c'est une zéro qui a été transmit. ici 111 ont été recus, donc je décide qu'un 1 a
été transmis, et ainsi de suite, tout simplement c'est celui qui a été
représente le plus frequement qui est supposé avoir été transmit. Donc apres décodage on s'apercoit qu'en fin
de compte j'ai pratiquement tout decodé, sauf un bit, j'ai donc un bit
d'erreur résiduelle, or cette erreur résiduelle on sait parfaitement la modéliser. J'ai donné l'équation ici, ou
n représente la longueur du code, S est égal a (n-1)/2, tout simplement on sait calculer après transmission et après décodage le nombre moyen de bits qui malgré tout auront été mal decodés.

Donc ce sont des codes très très simples, bon certes encore une
fois en terme de bande passante c'est pas optimal, mais dans ce qui va nous préocuper au contraire c'est assez intérressant.
il faut savoir qu'actuellement ce sont les meilleurs codes connus quand vous avez a traiter des paramètres de bruits elevés, or en cryptologie c'est particulierement interréssant parce que si en théorie des codes, c'est a dire quand je veux transmettre des informations en clair
a travers un canal, dès que le bruit est trop élevé on perd le clair, on est
donc obligé de le retransmettre. en cryptant c'est une problématique différente, on cherche au contraire a bruiter le plus possible le clair avec un parametre p le plus proche de 1/2 possible, pour
que précisement un attaquant ne puisse pas le retrouver.

La problématique théorie des codes et cryptologie sont a l'opposées l'une de l'autre. Ce qui est intérressant c'est qu'en cryptant on va justement essayer de travailler avec un bruit qui lui est aussi proche que possible d'un demie. Quand on va se placer justement avec des codes correcteurs d'erreurs utilisés pour faire de l'attaque cryptologique, nous ca nous gène pas puisqu'il suffit d'augmenter le paramètre S
c'est à dire augmenter n, sachant que le nombre de fois que je répète est
égal à 2*s+1, tout simplement je suis capable de dire quand S augmente, meme si il faut que je l'augmente beaucoup, ma probabilité d'erreur résiduelle tend vers zero, donc dans une optique d'attaque
cryptologique, si j'arrive a travailler avec des codes correcteurs d'erreurs
à base de code à répétition, il suffit tout simplement que je considère des codes de plus en plus longs en finale j'arriverais a une probabilité d'erreur qui tend vers zero.
Ca veux dire que je retrouverais l'information cachée, du point de vue de la
cryptanalyse l'information cachée qui était extrêmement bruitée.
Ce sont aussi des codes parfaits, ce sont les codes les plus faciles a
décoder, vous avez vu, il suffit de compter, un simple comptage, et quand vous recevez un mot vous pouvez toujours le décoder alors qu'il y a des codes qui n'ont pas cette propriété.
Il faut savoir que l'article le plus complet sur le sujet, qui date quand
même de 1988, est l'article de Matt Falken, ou il a justement generalisé tout ces classes de codes pour des alphabets quelconques, nous on se cantonnera bien evidemment aux alphabets binaires.

Bien sur je pars ici du principe que je considere l'ensemble générique de
toutes les clés. Donc quand on veux chiffrer on va choisir une clé secrete particuliere, ce qui fait qu'on va considérer une restriction de cet ensemble, autrement dit pour chaque clé fixée on a bien une
permutation qui va de l'ensemble des chaines de n bits a l'ensemble des
chaines de n bits, autrement dit de l'ensemble espace clair a l'espace cryptogramme.
Et des clés il y en a 2expn, dans le cas d'AES par exemple on a environ
2exp128 clés, ce qui est quand même une quantité extrêmement importante. Sachant que les systèmes actuels sont
vendus pour accepter des clés de 128, 192 et 256 bits, juste pour info il
faut savoir qu'actuellement la recherche exhaustive qui consiste à essayer toutes les clés qui etait possible avec des clés de 40 ou 56 bits, n'est plus du tout possible. On a fait un petit calcul
si vous prenez une machine hypothétique qui est capable de casser le DES en 1 seconde, il faut savoir que pour une clé de 128 bits on parle en milliers d'années encore, a raison de 2exp56
clés par seconde, actuellement c'est plutot 22 heures, mais admettont même qu'on ait cette machine, la recherche exhaustive n'est plus du tout possible, a moins de trouver une faiblesse mathématique ou de disposer d'une trappe, on est en face de systèmes virtuellement inviolables.
Alors ce qui fait l'intérèt de ces systèmes, c'est que je peux réutiliser la
clé non seulement pour tous les blocs d'un même message, mais aussi pour tous les messages, d'ailleurs pour toutes les cryptanalyses qui ont ete publiées, que ce soit la cryptanalyse linéaire ou la cryptanalyse
différentielle, c'est sous entendu : quand les gens disent "pour casser il
me faut par exemple 2exp 47 couples clair/crypto a moins d'avoir un message qui fait cette taille ca veux bien dire que cette clé est réutilisée pour un très grand nombre de messages, donc implicitement, et c'est
vrai que la théorie le permet, on peut réutiliser cette clé pour un tres
grand nombre de messages, et ca c'est la superiorité par rapport au système par flot.

Quand les systèmes par blocs sont sortis, le premier rappelons nous c'est au milieu des années 1970, très vite sont apparues un certain nombre de cryptanalyses, j'ai bien sur retenu la plus efficace, il y a bien sur la cryptanalyse différentielle de Adil et Shamir de 1992, mais la plus efficace c'est la cryptanalyse dite linéaire, c'est une attaque qui suppose de connaitre le clair, donc au niveau opérationnel c'est un peu embettant, quand on vous demande de connaitre des milliards et des milliards
de bits clairs connaissant le chiffré pour pouvoir retrouver la clé, il est
facile de comprendre que c'est pas opérationnel. Parce que si vous êtes capables de connaitre le clair sur des milliard et des milliards de bits, on se pose pas la question de retrouver la clé, mais c'est quand même interréssant.
En fait Matsui s'est dit "si j'arrive a établir une relation probabiliste,
c'est a dire vraie avec une certaine probabilité p, entre d'une part certains bits du clair, p étant utilisé pour son acronyme
anglo-saxon "plain text" avec certains bits du cryptogrammes "cypher text", et si ces 2 quantités peuvent être liées, autrement dit si l'entrée et la sortie du système peuvent etre liées de facon probabilistes avec certains bits de la clé k, j'ai à ce moment là une information qui est
vraie dans plus d'un cas sur deux ou moins d'un cas sur deux. Si par exemple vous jouez a pile ou face et que pile sort plus souvent
que face, vous allez miser sur face, vous allez pouvoir jouer à un jeux
d'argent, si vous savez que p = 1/2 à la limite vous avez autant de chances de perdre que de gagner, a ce moment là on ne joue pas.
Trouver une équation de ce type là ca va permettre de tricher. C'est avoir
une relation qui va permettre de retrouver une information sur la clé k. Alors comment on fait: la cryptanalyse consiste à soumettre
un grand nombre de couples clair/crypto c'est pour ca qu'on a besoin de
connaitre à la fois le clair et le chiffré parce tous les deux interviennent dans le membre de gauche de l'équation.
Et le plus souvent je sais que c'est egal à une certaine
clé, par un décodage de maximum de vraissemblance, je retrouve tout simplement une information sur la clé, en vertu d'un biais théorique
qui a été constaté sur le systeme de chiffrement, alors bien évidemment la probabilité de succes est élevée
dès que le nombre n de couples clair/crypto dont je dispose est plus grand que le biais observé.
C'est simple si vous savez qu'une piece est plombée du coté face avec une
probabilité de 2 sur 3, au bout d'un grand nombre d'essais vous saurez de quel coté la piece est plombée, autrement dit dès que vous avez
suffisament de tirages vous êtes en mesure de déterminer le biais et surtout de l'utiliser, là c'est exactement la meme chose, il faut suffisament de matériaux clair/crypto pour être capable d'exploiter ce biais. L'exemple du DES qui est la meilleure attaque connue, pour une probabilité qui fait 1/2 -1.19exp -21, on est très très proche de 1/2, il faut quand même connaitre le clair de 2exp43 couples ce qui veux dire que en gros il faut 2exp49 bits de clairs connu, donc ca fait quelques dizaines de milliards, alors on pourrais penser que cette attaque ne sert a rien, car si la cryptanalyse linéaire s'est révélée inefficace contre le DES, à la meme époque, certains systemes, en particulier le système FEAL des Japonais, s'est complètement effondré, c'est donc une technique qui est loin d'être ininterréssante.
Bien évidemment le gros inconvenient est qu'elle nécéssite de connaitre le clair en grande quantitée.

Alors justement cette dépendance vis a vis du clair est un peu embettante, parce que d'un cote operationel ca ne permet pas de réellement casser. Donc ce qu'on a imaginé c'est de prendre le meilleur des deux mondes c'est a dire prendre les codes a répétition d'un cote, et la cryptanalyse linéaire de Matsui de l'autre, et d'éssayer de conjuguer les deux. Et ca a donné la technique PDRC, autrement dit faire dépendre la cryptanalyse d'un sous-ensemble de clair et d'utiliser les codes a
répétition, alors en gros on reprend une équation probabiliste de Matsui, et on éssaie de s'affranchir avec du clair, autrement dit dans le chiffrement par bloc je transmet un bloc de clair que je cherche à bruiter avec la clé, la on a renversé les choses, on s'est dit, je prend une clé, je la bruite avec du clair, autrement dit le clair est vu comme
un facteur de bruit, autrement dit ce que je transmet c'est une information bruitée sur la clé, on peut très bien renverser le mécanisme, seulement comme cette clé est réutilisee de bloc en bloc, le clair certes lui
change, mais en gros vous transmettez toujours la même information bruitée, puisque la clé est réutilisee de bloc en bloc, autrement dit transmettre une même information un grand nombre de fois mais de manière bruitée c'est un code a répétition, donc on s'est dit si on arrive à trouver une relation de ce type là qui ne fait intervenir que le cryptograme et la clé, on a notre relation, donc on inverse le role respectif
de la clé et du clair, et on considère tout simplement qu'on a un code à
répétition par transmission d'une information sur la clé de bloc en bloc, le probleme c'est de trouver ce genre de relation, c'est pas evident.
Le problème d'abord c'est que je ne peux pas considérer tout le clair, parce que d'un point de vue mathématique cette relation considérée sur l'ensemble tout les cryptogramme c'est p = 1/2, ca c'est la théorie vous avez une équation linéaire, sur un espace complet c'est p = 1/2, donc on ne peut pas décider, c'est pour cela qu'il faut considérer un sous ensemble de clair, et on a pu construire de manière opérationnelle des exemples
non triviaux ou globalement la probabilité était de 1/2 sur tout l'espace,
mais sur certaines permutations et sur certains sous ensemble de clair et de chiffre correspondant on avait p différent de 1/2, donc on avait bien
ce biais, donc ca confortait l'idée qu'on pouvait chercher l'information
concernée.
Il y a des problèmes de variabilité du paramètre de bruit, en fait si on
était vraiment rigoureux on aurait un bruit non stationaire, parce qu'en fin de compte les blocs de clairs qui bruitent la clé ne sont pas forcément
les mêmes d'un bloc à un autre donc ca peut poser des problèmes, c'est pour ca qu'on s'est dit qu'on allait considérer un sous ensemble de clair a partir duquel aura été produit avec une même clé secrête les cryptogrammes qui vont servir de base a notre étude, l'avantage c'est que ca permet de considérer de facon [coupure-NDLR] éspérer des valeurs beaucoup plus importantes de p.
Les clairs qu'on a etudié correspondent a du langage de type anglais, mais c'est transposable à d'autres langues, codé en majuscule et en caractères ASCII, donc d'un point de vue operationel ca correspond quand même à beaucoup de choses envoyées sur les réseaux ou dans les communications, par exemple le telex chiffrant rentre tout a fait
dans ce modèle. Alors on applique les masques, on génère aléatoirement des clair et on applique ce masque, ca oblige un bit a être a zéro ici ou ici, la position dépend du type de codage que l'on considère, autrement dit
la seule supposition que je fais c'est que celui que j'attaque a envoyé du
langage clair de type anglais code en ascii, un presupposé qui n'est pas trop handicapant, on peut éventuellement savoir, par une analyse de traffic ce qui a été réellement envoyé.

L'attaque en elle même est tres simple, c'est juste compter, tout simplement je considere un code a répétition de n, avec n impair pour les raisons qu'on a vu tout a l'heure, je considère donc ce nombre de bloc de
cryptogrammes, la je ne vais utiliser que les textes chiffrés, la je me suis
affranchis de toute autre considération sur le clair, je ne travaille qu'avec des cryptogrammes, il suffit de mettre une antenne dans l'air ou de sniffer
un réseau, c'est des choses qu'on intercepte facilement.
Et aussi je dispose d'une équation probabiliste qui me permet de lier sur un tel sous ensemble le cryptogramme a la clé, donc en sortie je vais produire tout simplement un ou plusieurs bit d'information, du moins un bit par équation probabiliste, c'est a dire une information vraie a 100%, du moins on l'espère, sur la clé, et quand j'aurais suffisament de bits d'information, il suffit d'avoir n bits d'information sur une clé de n bits, je pourrais retrouver la clé. L'algorithme en pseudo code est très simple, j'initialise un compteur à zéro, pour chaque bloc chiffre je calcule le membre de gauche de mon équation probabiliste, autrement dit
c'est simplement des ET et des OU en terme d'informatique, donc ca ne consomme presque rien, si le resultat de mon produit scalaire vaut 1, j'incrémente mon compteur, terminé, donc en fin de compte c'est juste n comptage, soit n évaluations de produits scalaires, mais ca coute vraiment rien, et à la fin je décide, tout simplement si c'est supérieur au seuil, je décide que le bit d'information que je cherche c'est 1, sinon c'est 0.
Vous voyez qu'en terme de complexité on ne peut pas faire plus simple, je n'ai meme pas a soumettre au chiffrement un certain nombre de clair, donc je gagne également sur cette phase, je n'ai juste que des comptages a faire.

Alors on s'est dit aussi ce qu'on pourrais faire c'est une attaque en deux
temps, autrement dit on pourrait utiliser ce qu'on appelle des codes concaténés, autrement dit je considère 2 codes a répétition, c'est a dire que j'ai mon système de chiffrement, mon clair et mon crypto, et je fais une premiere attaque par code à répétition, vous savez que le résultat donnera une information avec une certaine probabilité d'erreur résiduelle, je resoumet ca a une deuxieme phase de cryptanalyse par code a répétition en considerant cette fois ci un code a répétition different, dont le parametre de bruit sera justement la probabilité d'erreur résiduelle obtenue lors du premier décodage, on s'est dit intuitivement que ca pourrait peut etre etre interréssant, parce qu'on sait qu'en general
les codes concaténés sont des codes plus puissants que leurs homologues simples, sauf dans le cas des codes a répétition, on a pu le démontrer mathématiquement.
Donc cette idée était moins efficace, il faut mieux prendre un seul code a
répétition plutot que d'en prendre deux, la bonne nouvelle c'est que la complexité de l'attaque reste basse parce que sinon il aurait fallu répéter l'attaque 2 fois.

Alors avant de passer aux résultats concernant l'AES, on s'est posé 4
problèmes qui sont des problèmes ouverts, et qui ont quand même ont leur importance, vous allez voir pourquoi.
tout d'abord est ce qu'il est possible de concevoir un système
cryptographique S capable de résister a cette attaque,
le problème c'est que dans l'absolu ca n'est pas possible, pourquoi ? parce que les mathématiques montrent qu'au niveau des fonctions booléennes modélisant les sorties d'un système de chiffrement par bloc, comme d'ailleurs dans n'importe quel système de chiffrement, il existe toujours des corrélations exploitables, autrement dit il existe toujours des biais,
vous pouvez toujours essayer de les gommer à la base, vous ne ferrez que les concentrer ailleurs, et ca c'est du au théorème de Parseval, donc ces corrélations existent toujours, alors le problème c'est de les trouver, rappelez vous qu'on travaille sur des ensembles monstrueusement grands, et ca c'est en particulier le travail qu'effectue le logiciel Vauban qui a été concu pour travailler sur de très très gros ensembles.
Alors après il y a 2 problèmes: le problème de trappes faibles, autrement
dit je dispose d'un sous ensemble de cryptogrammes produits a partir d'un sous-ensemble de texte clair, est ce que je peux concevoir un système S qui pour une équation probabiliste E que je connais, est ce qu'il est possible de fabriquer un tel système autorisant l'attaque, le principe
du systeme c'est que j'ai une équation, je connais le secret, la personne
utilise mon systeme sans le connaitre, moi je veux attaquer ce système, on travaille dessus, on a disont de bons espoirs d'y arriver, on voit bien les enjeux qu'il y a derriere.
Puis le problème de trappe forte, la j'augmente un peu les contraintes,
autrement dit j'ai une équation probabiliste, cette fois ci je veux que quel que soit le sous-ensemble de cryptogramme ca fonctionne, autrement dit que je puisse attaquer le systeme, vous voyez que par rapport au problème de trappe faible on augmente le niveau de difficulté.
Et puis un autre problème ouvert, qui est de moins en moins ouvert avec le système Vauban, c'est justement est ce que je peux trouver des équations probabilistes et des sous-ensembles qui vont bien permettant de lier uniquement le cryptogramme avec la clé.

Alors pour l'AES, les résultats avaient été trouvés l'année derniere, on a
trouvé apres 4 mois de calcul, sur 2 PC quand même retaillés mais ne nécéssitant pas une grande quantité de mémoire, juste beaucoup de temps, on a donc trouvé avec le logiciel Vauban, qui est un logiciel qui n'est pas publié pour le moment, 2 equations de facon déterministe,
on en a en fait trouvé plus, environ 300 a 400, mais pour l'instant on en a
étalonné que 2.
Ce que l'on sait c'est que l'on peut exhiber une équation dont on connait le biais et le signe du biais, autrement dit on sait si c'est 1/2+epsilon ou 1/2-epsilon, ce que l'on ne sait pas encore déterminer, tout simplement parce qu'on a pas encore assez avance dans le domaine, c'est le biais lui même, est ce que c'est 1/2+0.1, ou 1/2+0.01, on sait plutot
que ca sera 1/2+10e-5 ou 10-6, mais on est pas capable a l'heure actuelle de donner la valeur exacte du biais, on sait qu'il y a un biais et on connait son signe, c'est déja une information importante.
Alors ce qu'on a fait c'est 200 cryptanalyses sur l'AES, le code source
complet a été publié, ce qui a nécéssité 3 mois de calculs, le plus dur a été de produire les blocs chiffrés, l'AES a beau etre bien programmé plus de 80% du temps de calcul est passé dans la génération de ce que dans un autre cas on intercepterait simplement.

Le cout dans l'éxpérience menée
est donc essentiellement passé dans la génération de ce qu'on intercepterait autrement.
et on utilise que 2exp31 blocs de chiffres, autrement dit c'est ce que l'on
stocke actuellement sur un disque dur moyen ca fait environ 4 giga-blocs, on suppose tout simplement que le clair a été produit a partir de l'ASCII.
Alors bien sur on a définit un protocole éxpérimental rigoureux parce qu'il
faut savoir qu'en Janvier quand on a publié ca alors qu'on avait publié le code source, il y a eu un certain nombre de critiques, qui s'expliquent plus ou moins, ce qui s'est passé c'est que personne n'a voulu reproduire l'éxpérience, donc on a été obligé de refaire l'éxpérience,
(ces 200 cryptanalyse), mais cette fois ci de générer depuis le code source, de montrer que l'aléas était de bonne qualitée puisque ca aussi a été suspecté mauvais, bref on a définit un protocole éxpérimental extrêmement rigoureux, tout a été publié, code source et également toutes les valeurs intermédiaires des cryptanalyses, pour permettre justement la reproductibilite des résultats sans avoir a refaire la cryptanalyse, et les résultats sont confirmés, on peut effectivement retrouver 3 bits d'information (en fait 2 et demie) sur la clé de maniere opérationnelle.
Alors il faut savoir que lors des critiques de février 2002, deux Americains
ont prétendu avoir obtenu les mêmes résultats en 27 heures ce que nous on avait fait en 3 mois, le problème c'est que les informations qu'ils donnent sont inexploitables car non reproductibles. il n'est pas possible qu'ils aient obtenu ces résultats, c'est en particulier ce qui a incité a
refaire l'éxpérience en regénérant tout les résultats intermédiaires.
Alors juste pour le fun voila les deux équations, elle sont disponibles sur
un lien que je vous donnerais, ne les recopiez pas. ici vous avez le bits de cryptogrammes, alors il y a des raisons particulieres qui font qu'on considère les bits de cryptogrammes un par un plutot que par plusieurs, comme dans le cas de la cryptanalyse linéaire, et ici tous les bits de
clé que l'on considère, pareil pour la deuxieme équation.
Maintenant qu'on est sur que cette technique marche on va pouvoir valider les quelques 300 autres équations, le problème c'est qu'il faut beaucoup de puissance de calcul, et je suis a la recherche de gros ordinateurs.
L'éxpérience numero un consiste a laisser tourner un PC pendant 3 mois, on lui a donne une graine, et on l'a laisse générer ses 300 cryptanalyses, autrement dit avec l'équation 1 je retrouve le premier bit avec une probabilité de succès de 60%, alors bien évidemment si j'augmentait la taille de mon code a répétition, passer de 2exp31 a 2exp36 par exemple,
c'est pas grave on travaille que sur du chiffré, je pense qu'on doit augmenter
la probabilite de succès. sur l'equation numéro 2 on obtient 63%, et ce qui est intérressant c'est de remarquer que ces équations sont très fortement différentes, or si l'AES était un bon modèle on pourrait se dire que ces équations sont indépendantes, donc additionner les équations devrait donner a priori 1/2, or on s'apercoit qu'il y a un lien entre ces deux
équations, ce qui conforte d'ailleurs l'approche, donc ces equations ne sont pas indépendantes.
On a obtenu les mêmes types de résultats sur un deuxieme PC qui a lui aussi tourné 3 mois. donc il est clair que, contrairement a ce qu'a dit une des critiques, que ca n'est pas une question de chance. car obtenir ce genre de résultats c'est plus dur que de gagner au loto, un simple calcul le montre, donc c'est pas une question de chance.

Donc en guise de conclusion, d'abord il faut savoir que d'autres équations
sur AES ont été obtenues, et sont en cours de tests, mais ce qu'on voulait c'etait quand même que ces deux équations soient validées, ce qu'on voudrait c'est quand même déterminer plus precisement le biais, on y travaille, parce que je vous rappelle que l'on sait qu'il y a un biais et quel est son signe. Il faut quand meme savoir une chose, l'AES a été selectionné a l'issu d'un concours lancé par le gouvernement Americain, encore une fois, et il imposait obligatoirement que ca soit des systèmes par blocs, il ne veulent pas du tout entendre parler de systèmes par flot. 18 candidats avaient été soumis, il y en a 3 qui ont été tout de suite virés ce sont les candidats Russes, les Americains ont peut être peur des Mathématiciens Russes, et on a eu 15 candidats sélectionnés pour la première phase, a l'issu de la première phase 5 candidats ont étés
retenus, 3 Americains, 1 Anglais/israelien/norvegien, 1 candidat belge, un
seul candidat a été retenu c'est le système Belge aussi appelé Rinjdael. On a appliqué les techniques Vauban sur ces systèmes.
Seuls 3 systèmes pour l'instant résistent, c'est le système E2 Japonais, le
système Allemand "Magenta", et le système Mars, mais c'est vrai que les gens de Mars sont les mêmes qui ont concu le système DES, certains louvoient entre IBM et la NSA et ils ont donc peut etre des connaissances beaucoup plus étendues que les autres personnes ayant composées les candidats, en tout cas pour l'instant ces 3 la résistent, autrement dit le système Vauban ne retrouve pas d'équations pour ces systèmes, ca ne veux pas dire qu'elles n'existent pas, mais le système est tellement bien fait que Vauban n'arrive pas a les retrouver.
Alors en tout cas on peut d'un point de vue théorique, mais aussi d'un point de vue pratique, a la lumiere des éxpériences sur l'AES considérer qu'une certaine remise en cause des systèmes de chiffrement par bloc est possible, le simple fait de réutiliser la clé on voit bien par cette modélisation par des codes a répétition, que c'est une information qu'on transmet plusieurs fois, on peut d'une manière ou d'une autre essayer de la retrouver, en tout cas pour l'AES c'est ce qu'on est parvenu a faire dans nettement plus d'un cas sur deux. on a essayé avec pour l'instant des prémisses de succès, de transposer ces technique Vauban pour les systèmes sur les systèmes par flot utilisant la rétroaction linéaire,
c'est a dire les systèmes les plus fréquents, a priori ca marche sans
problème, et pour le moment les seuls qui résistent sont les systèmes par flots utilisant la rétroaction non lineaire, autrement dit l'évolution du système interne pour générer la suite aléatoire qui est combinée au texte clair se fait selon des processus non linéaires contrairement aux systèmes utilisant la rétroaction linéaire, c'est implicite, on voit bien que quand il y a une relation interne entre les états de la machine qui sont de nature linéaire, c'est moins difficile et plus prédictible que pour quelque chose qui se rapproche du chaos. Donc pour l'instant Vauban ne marche pas sur les systèmes non lineaire.

- on a un certain nombre de candidats mais dans ce domaine là dans la mesure ou ce sont des ensembles tellement gros il faudra refaire l'éxpérience un grand nombre de fois, j'espère que ca donnera l'idée a des chercheurs de se mettre dessus, alors on a réussi a expliquer pourquoi ces biais existent, ca c'est important, en mettant bout a bout Parseval
et les aspects combinatoire, on peut l'expliquer, le probleme c'est qu'il
manque quand même une inconnue pour avoir une idée précise de la quantité de chiffrés qu'il faut, ce serait bien d'avoir une valeur relativement exacte du moins avec un bon ordre de grandeur, du biais, pourquoi c'est intérressant, parce qu'une fois que j'aurais le biais relativement précis, je pourrais déterminer une longueur suffisante de mon code a répétition pour pouvoir avoir une probabilité de succès plus importante. Quand j'aurais des probabilités suffisament importantes avoisinant les 90%, je pourrais varier plusieurs équations, et la je pense qu'on pourra retrouver une partie significative de la clé. Mais il y a encore
beaucoup de travail a faire avant de dire que l'AES est cassé, on a de bons espoirs d'y arriver avec beaucoup de temps et d'ordinateurs, en tout cas on sait comment faire.

- il faut savoir qu'il existera toujours des biais, et ca meme les
concepteurs de l'AES l'ont reconnu, c'est du au theoreme de Parseval, on ne peut pas y couper,ce qu'on peut s'arranger c'est de répartir l'énergie de chaque fonction le mieux possible pour etre inexploitable pour l'attaquant, a l'inverse, on peut s'arranger pour la répartir d'une
maniere optimale pour l'attaquant, le probleme c'est que ce sont des
ensembles tellement gros que, a moins de connaitre la trappe on ne peut pas repondre a la question, alors maintenant à la lumiere d'un certain nombre d'éxpérience, et d'un certain nombre d'autres éléments, et connaissant surtout les Américains, je serais ammené a penser que oui, il y a une trappe, mais cette fois ci c'est un sentiment personnel, etayé certes par un certain nombre d'éléments de réflexion et un certain nombre d'éléments techniques, mais il est bien evident que tant que l'on exhibera pas la trappe, on ne pourra pas le prouver à 100%. Maintenant ca dépend de ce qu'on appelle trappe, on peut très bien ne pas mettre tous les oeufs dans le même pannier, peut etre que c'est une trappe qui permet de réduire la complexité de 2exp128 a 2exp60 ou 2exp70, ce qui n'est accessible qu'a des pays richement dotes en matière de compétences informatiques, donc à la limite on ne met pas tous les oeufs dans le même panier, ce qui est déja intérressant, mais ma conviction est que oui il y en a une.

- pour avoir été a la conférence AES 3, au départ les Américains avaient
envie de privilégier le système Mars, les universitaires n'avaient pas du tout envie, il y a eu des votes, de facon feinte ou réelle je ne sais pas,
la communauté Européenne, en particulier le NIST, a semblé ou a affecté
d'agir sous la pression, moi mon sentiment, c'est que les 15 systèmes ils les maitrisent. pour l'instant il existe une grosse incertitude sur le chiffrement par bloc. Sur un systeme de chiffrement par flot il
y a un état de l'art tel que l'on sait si on a un niveau de securité ou pas,
c'est peut etre la raison pour laquelle la plupart des systèmes de chiffrement par flot sont reconnus, il y a un état de l'art.
les systèmes par bloc pour l'instant c'est une grosse pagaille combinatoire, et c'est vrai qu'il y a des tas d'idées, on est en train d'en developper certaines, qui permettent de cacher des tas de choses dedans, J'ai parlé de la cryptanalyse différentielle tout a l'heure, quand elle a ete révélee par Shamir en 92, beaucoup de systèmes sont tombés, le systeme FEAL des japonais, et d'autres, et on s'est dit que c'était quand meme bizarre que le DES résiste, c'est pas naturel qu'un systeme résiste aussi bien à une cryptanalyse qui il faut bien le reconnaitre,
était puissante, et la NSA a reconnu que cette cryptanalyse il la connaissaient 20 ans avant, donc ca vous donne une idée du differentiel en terme de connaissances entre la communaute ouverte, pourtant nombreuse, et certains services comme la NSA. Il faut voir l'énergie qu'ils y consacrent, de plus ce differentiel s'est a mon avis aggravé en ce qui
nous concerne.
Mais bon la pour beaucoup de choses se sont des suppositions, certes etayés par un certain nombre d'éléments de réflexion, encore une fois tant qu'on exhibera pas la trappe, ca reste une conjecture.
Bon, si il n'y a pas d'autres questions je vous propose d'aller prendre un
café.