Le bit est l'unité fondamentale de l'information. C'est un 0 ou un 1. Les ordinateurs des quarante dernières années travaillent tous en binaire, c'est-àdire en alignant des bits (et non des chifres entre 0 et 9, comme font les humains ; en quelque sorte, les ordinateurs n'ont que deux doigts). Une suite de bits permet de coder un nombre entier, des caractères, etc... Toute information qui est passée par un ordinateur a été transformée en bits.
8 bits forment un octet ; ceci donne 256 combinaisons, ce qui permet de coder un nombre entre 0 et 255, ou un caractère (en incluant les différences entre les majuscules et les minuscules, les caractères accentués, et divers autres caractères).
1024 octets font un kilo-octet (Ko). On utilise 1024 plutôt que 1000 car 1024 est une puissance de 2, c'est-à-dire un nombre "rond" quand on travaille en base 2. 1024 Ko font un méga-octet (Mo), soit 1048576 octets. 1024 Mo font un giga-octet (Go), soit 1073741824 octets. 1024 Go font un tera-octet (To). Les multiples au-delà sont peu usités car trop chers de toutes façons. Les ordinateurs grand public vendus actuellement peuvent typiquement stocker une dizaine de giga-octets de données sur leurs disques durs. Un réseau un peu évolué peut faire passer une dizaine de méga-octets par seconde entre deux machines.
La cryptographie concerne des opérations telles que le chiffrement ou la signature, qui ne doivent être possibles que pour certaines personnes, disposant d'un certain secret. Dans les siècles passés, ce secret était la méthode même de transformation des données. Il est apparu qu'il était plus rationnel, et plus efficace, de concentrer le secret sous la forme d'une suite de bits, et de rendre l'algorithme lui-même public.
En effet, il est difficile de conserver un algorithme secret, et, par ailleurs, il est appréciable de pouvoir quantifier mathématiquement la sécurité. Par ailleurs, le fait de rendre un algorithme public permet d'obtenir "gratuitement" l'avis de la communauté cryptographique sur la solidité de cet algorithme.
La clé est donc ce secret concentré, cette suite de bits qui est l'essence même de la confidentialité.
Casser un système cryptographique, c'est pouvoir réaliser certaines opérations nécessitant en théorie la connaissance du secret, mais sans avoir été informé préalablement de ce dernier. Le cassage le plus complet est celui où on obtient la connaissance de la clé elle-même, ce qui donne ensuite les mêmes pouvoirs que le légitime possesseur de cette dernière.
La recherche exhaustive est la méthode la plus simple de ce point de vue : elle consiste à essayer toutes les clés l'une après l'autre jusqu'à trouver la bonne. Cette méthode a l'avantage d'être générique et parallélisable (on peut distribuer le calcul sur de nombreuses machines). Par ailleurs, elle est réaliste : si on envisage le cas d'un système de chiffrement symétrique (qui associe à un bloc constitué de quelques octets un autre bloc de même taille, mais illisible, la correspondance dépendant de la clé), il suffit d'intercepter un couple clair/chiffré, c'est-à-dire un bloc de quelques octets et le chiffré correspondant. Par exemple, si c'est une image de type JPG qui est transférée, le début du message est l'entête JPG standard, parfaitement connue de tout un chacun.
Statistiquement, il faudra essayer la moitié des clés avant de trouver la bonne, Si on chiffre avec des clés de 56 bits, celà signifie qu'il faudra 2^55 essais, soit 36028797018963968 (en moyenne).
Non. Mais les autres méthodes dépendent fortement de l'algorithme lui-même. Certaines, telles que la cryptanalyse linéaire ou la cryptanalyse différentielle, peuvent nécessiter un nombre impressionnant de couples clair/chiffré, rendant l'attaque purement théorique.
Par ailleurs, il existe des systèmes de chiffrement (notamment les systèmes asymétriques, dits "à clé publique") pour lesquels toutes les suites de bits ne forment pas des clés valide. L'exemple typique est RSA, où la clé représente un grand nombre, produit de deux grands nombres premiers. L'ensemble des suites de 1024 bits qui représentent en base 2 de tels nombres est beaucoup plus petit que 2^1024. La recherche exhaustive est absurde dans ce cas.
NON ! C'est une erreur courante. Chaque bit supplémentaire double le nombre de clés possibles, donc le coût de la recherche exhaustive. Une clé de 128 bits est 18446744073709551616 fois plus dure à casser exhaustivement qu'une clé de 64 bits (qui déjà n'est pas facile du tout).
Stop ! Halte au sketch ! Les "1024 bits" de PGP sont ceux d'une clé de type RSA ou DSS, c'est-à-dire une clé structurée servant à un algorithme asymétrique. La recherche exhaustive n'est pas du tout la meilleure attaque connue dans ce cas-là.
Par ailleurs, les algorithmes asymétriques étant relativement lents, PGP utilise en interne un algorithme symétrique (historiquement IDEA, puis CAST) dont la clé a une taille de 128 bits.
Publiquement parlant, deux clés de 56 bits ont été cassées par recherche exhaustive sur des ordinateurs génériques tels que des PC. Une machine spécialisée (construite par l'EFF) a aidé pour la deuxième clé, à hauteur d'environ un tiers de l'effort total.
Les deux clés mettaient en jeu l'algorithme DES. Un PC haut de gamme ou une station de travail peuvent essayer au maximum quelques millions de clés par seconde. Si on considère une moyenne de un million de clés par seconde et par machine, on peut calculer que 10000 machines viennent à bout de la clé en un temps moyen de 42 jours.
Une recherche exhaustive d'une clé de 64 bits pour RC5 (pour lequel le coût de la recherche exhaustive est légèrement plus élevé que pour DES) est en cours. Et durera encore quelques années au moins. Rappelons que casser une clé de 64 bits est 256 fois plus dur que casser une clé de 56 bits.
Un groupe de pression américain, l'EFF, a investi 250000$ dans une machine spécialisée, nommée "Deep crack", qui essaye toutes les clés de l'algorithme DES en environ 3 jours. Ceci utilise des processeurs spécialisés, construits pour l'occasion et absolument inutile pour quoi que ce soit d'autre que casser du DES (notamment, RC5, ils ne connaissent pas du tout).
Toute autre machine du même genre est du domaine de la rumeur. DES est en usage depuis plus de 20 ans et il est généralement considéré comme probable que la machine de l'EFF a été précédée par d'autres prototypes construits par divers services secrets. En tous cas, cela fait bientôt 15 ans que le principe d'une telle machine est périodiquement évoqué.
Il existe principalement deux problèmes mathématiques utilisés pour le chiffrement asymétrique : la factorisation et le logarithme discret. RSA utilise le premier, DSS le second. D'autres problèmes ont été évoqués (variations des deux précédents utilisant des courbes elliptiques, sac à dos, réduction de réseau, perceptron permuté) mais sont encore peu utilisés pour le moment.
Le record de factorisation date du 22 août 1999 : un nombre de 155 chiffres décimaux (512 bits) a été factorisé en six mois de calcul sur un parc d'environ 600 machines, dont certaines peuvent être qualifiées de "bovines" (notamment un Cray avec 2 Go de mémoire). Les algorithmes mis en jeu sont nettement plus complexes qu'une recherche exhaustive et nécessitent beaucoup de mémoire vive, et rapide.
Le logarithme discret est moins médiatique, et il a été moins investi sur son cassage que sur la factorisation. Le record est de l'ordre de 95 chiffres décimaux.
Présentée à Eurocrypt'99 à Prague (début mai 1999), c'est un appareil qui accélère par des moyens physiques la recherche de nombres lisses (c'est-à-dire produits uniquement de petits nombres premiers), qu'on obtient habituellement par des méthodes de crible. Ces nombres sont le fondement de plusieurs algorithmes de factorisation et de résolution du logarithme discret.
L'appareil lui-même n'a pas encore été construit, seul son principe a été décrit. Des problèmes techniques subsistent encore pour la construction d'un prototype en vraie grandeur (Arjen Lenstra a soulevé un certain nombre d'objections, avec lesquelles Adi Shamir est d'accord).
Le sentiment général est que cette méthode permettrait de factoriser des nombres d'environ 600 bits, avec les moyens qui ont permis de prendre le record à 465 bits (en février 1999), si tous les problèmes d'implémentation peuvent être résolus. On notera que le crible a occupé environ 60% du temps pour le record à 512 bits.
Toujours est-il que le show était très ludique. Phil Zimmerman, l'auteur de PGP, m'a confié qu'il était très content que les chercheurs s'intéressent tant que ça à ces problèmes, car cela augmente la confiance qu'on peut avoir dans de tels systèmes.
La loi de Moore est une estimation à l'emporte-pièce du progrès des micro-processeurs au cours du temps. D'un point de vue basique, elle stipule que pour un coût donné (au sens large, incluant la consommation électrique, la production du matériel, son usure, le coût du stockage, etc...) la puissance de calcul disponible est multipliée par 8 tous les 3 ans. Plus précisément, on peut dire qu'en trois ans, le progrès technologique permet de placer 4 fois plus de portes logiques sur une puce pour un coût donné, en cadençant le tout 2 fois plus vite.
Cette loi est remarquablement vérifiée sur les 15 dernières années. On notera que les micro-processeurs centraux des ordinateurs génériques ne suivent pas complètement cette loi, parce qu'ils ne peuvent pas augmenter la taille des bus de données aussi vite que ça (pour des raisons de compatibilité ascendante du code, et aussi parce que les calculs que ces processeurs doivent effectuer ont d'habitude des contraintes supplémentaires rendant inutile l'usage de registres trop grands).
Ceci concerne donc les systèmes s'exprimant en termes de portes logiques, spécialisés dans un algorithme particulier. Donc essentiellement les ASIC et les FPGA (Field Programmable Gate Arrays ; ce sont des circuits reprogrammables, qui remplissent les mêmes rôles que les ASIC, en étant deux fois plus chers pour une puissance donnée, mais aussi polyvalents).
Si la loi de Moore continue à se vérifier (et il n'y a pas vraiment de raison que ça s'arrête, car elle inclut les progrès qualitatifs et pas seulement l'augmentation de la finesse de grave dans le silicium), on peut partir de la machine de l'EFF (un quart de million de dollars, pour du 56 bits en 3 jours) et rajouter 3 bits tous les 3 ans (3 bits = 2^3 = 8 fois plus de clés possibles).
On notera que pour maintenir la loi de Moore, il faudra faire des progrès qualitatifs assez rapidement, car il y a des limites à la finesse de gravure dans le silicium (quand les électrons changent de fil par effet tunnel, ça marche beaucoup moins bien). Au rang des techniques prototypales, on citera le remplacement du silicium par l'arsiénure de gallium, qui permet de graver nettement plus fin, le remplacement de l'alluminium par du cuivre, qui permet de cadencer beaucoup plus vite, la construction de logique optique (une porte optique bascule environ 100 fois plus vite qu'une porte électronique, mais elle coûte encore plus de 100 fois plus cher).
Donc on peut considérer que la recherche exhaustive sur 128 bits aura la difficulté de celle sur 56 bits maintenant, dans 72 ans. C'est une borne "au mieux", car certains chercheurs plutôt bien documentés sur le sujet estiment que la loi de Moore ne pourra pas être maintenue plus de quelques années, pour cause de pénurie d'idées nouvelles (en effet, toutes les améliorations qualitatives apportées sur ces 15 dernières années étaient déjà latentes, voire explicitées dès 1975, et ce stock est à peu près épuisé maintenant).
Les ordinateurs quantiques implémentent, via la superpositions d'états sur une même particule, un modèle de calcul plus puissant que la machine de Turing, qui permet d'effectuer certaines opérations (dont la recherche exhaustive de clés pour un algorithme "branchless" tel que DES) en un temps sub-exponentiel.
Les ordinateurs quantiques sont très séduisants mais ils n'existent pas. Il a été construit un registre quantique de deux bits, mais il y a des objections assez fortes contre une machine à casser du DES (essentiellement, l'initialisation du bouzin, qui elle ne se paralléliserait pas, et prendrait donc 2^n opérations pour une clé de n bits).
Ceci n'a pas grand'chose à voir avec l'autre type de cryptographie quantique, qui sert à la transmission non espionnable de données sur une fibre optique (en utilisant le principe d'incertitude d'Heisenberg).
Il y a des objections très fortes contre ce genre d'assertion. Parmi les classiques, on peut citer celle qui suppose des processeurs spécialisés consommant 10 fois moins de courant qu'un processeur classique issu de la recherche publique (ce sont des services secrets, ils ont droit à une petite avance). La consommation énergétique d'une recherche sur 128 bits serait alors telle que tout cassage en moins d'un an ferait disparaître les Pays-Bas sous les eaux (toute cette énergie est, in fine, dissipée sous forme thermique, provoquant la fonte des glaces polaires).
Pour ce qui est du 256 bits, on peut faire plus universel : si on suppose que chaque essai d'une clé nécessite le changement de niveau d'énergie d'un électron autour d'un atome, alors l'énergie fournie généreusement par le soleil est trop limitée pour faire une recherche exhaustive en un temps concevable.
Certains manipulent les nombres de bits allègrement, accordant généreusement 20 bits grâce à l'usage de supraconducteurs ou de portes optiques, 20 autres pour les algorithmes secrets hyper-efficaces, et les 30 derniers parce que "ce n'est pas loin" (juste un facteur 1 milliard, c'est vrai que c'est n'est pas loin).
Rappelons que les nombres de bits sont exponentiels, ce qui veut dire que le coût d'une recherche exhaustive sur n bits est en 2^n. Pour frapper l'imagination, disons seulement que :
Hautement improbable. Si c'est vraiment le cas, alors leur avance technologique dépasse de très loin les 10 ans qu'on leur attribue généreusement. En d'autres termes, ils maîtriseraient alors une technologie si avancée que l'idée même de les combattre serait une absurdité.
Certains ont évoqué la possibilité d'un don par les extraterrestres, soit par l'intermédiaires des Hommes en Noir, soit directement via Phil Zimmerman, leur ambassadeur sur cette planète. Selon d'autres sources, l'ordinateur quantique serait un vestige de la civilisation Atlante (certainement engloutie sous les eaux à la suite d'un essai de recherche exhaustive par des moyens "classiques", cf ci-dessus).
Le pire côtoyant l'absurde et le médiocre dans ce domaine, il est généralement admis que le seul moyen de penser correctement sans passer pour un guignol est de s'abstenir de telles spéculations. Si on veut estimer ce que la NSA sait faire, on leur donnera 3 ans de loi de Moore d'avance, et un budget important. Cela les met en position de faire du 64 bits quotidiennement. Le 80 bits reste inatteignable.
Il est vrai que la NSA a expliqué (par l'intermédiaire de Don Coppersmith) en 1987 qu'il connaissaient déjà en 1977 la cryptanalyse différentielle, découverte dans le public par E. Biham et A. Shamir en cette année 1987, justement. L'algorithme DES, conçu en 1977, est spécialement protégé contre cette attaque.
Néanmoins, précisons que cette attaque nécessite un grand nombre de couples clair/chiffré, et est de toutes façons irréaliste. Par ailleurs, DES n'a pas été protégé contre la cryptanalyse linéaire, découverte en 1993 par Matsui, ce qui donne une borne de 15 ans sur l'avance scientifique de la NSA. Enfin, cette dernière cryptanalyse est irréaliste quand même (il faut 64 To de texte clair connu, plusieurs dizaines de millions de fois la Bible).
De semblables rumeurs ont été évoquées pour la factorisation, le logarithme discret et le remède contre les furoncles. On reconnaît assez facilement ces rumeurs aux références omniprésentes à un complot international de méchants pas beaux qui veulent tout savoir sur tout le monde.
De toutes façons, au-delà d'un certain point, il devient infiniment moins cher de placer une caméra dans votre bureau que de faire mouliner un ordinateur quantique. Savez-vous qu'on peut reconstruire ce qui s'affiche sur votre écran à 100 mètres de distance ? Et pareil pour ce que vous tapez au clavier. Il faut une cage de Faraday bien conçue pour se protéger contre ça. Le chiffrement permet juste de construire un canal sûr entre deux points, il ne protège pas ces points en particulier.
Niark niark niark. Je suis fourbe, n'est-ce pas ?