Comment DES a été cassé

DES possède 2^56 clés possibles, soit environ 72 billiards de clés (72 057 594 037 927 936). Bien que ce nombre semble immense, il s’agit d’un espace fini qui peut être parcouru systématiquement avec une puissance de calcul suffisante.

L’épuisement de l’espace de clés (force brute) exige en moyenne de mettre à l’épreuve la moitié de cet espace avant de trouver la clé correcte. Pour DES, cela représente environ 2^55 déchiffrements d’essai, chacun ne nécessitant que quelques opérations sur le matériel moderne.

En 1997, RSA Data Security a offert une récompense de 10 000 $ pour casser un message chiffré avec DES. Rocke Verser a coordonné un effort de calcul distribué mobilisant des dizaines de milliers d’ordinateurs connectés à Internet.

Après 96 jours de recherche, la clé a été trouvée. Le texte en clair était : « Une cryptographie forte rend le monde plus sûr. » Cet effort a démontré que DES pouvait être cassé, même si cela nécessitait des mois et une coordination considérable.

La Fondation pour la frontière électronique a construit Deep Crack pour 250 000 $ en 1998. Il contenait 1 856 circuits intégrés spécifiques à une application, chacun capable de mettre à l’épreuve 2,5 millions de clés DES par seconde, ce qui lui donnait un débit cumulé de plus de 90 milliards de clés par seconde.

Deep Crack pouvait parcourir l’intégralité de l’espace de clés de DES en environ 9 jours en moyenne. Cela prouvait qu’un adversaire déterminé, disposant d’un investissement de 250 000 $, pouvait casser DES en moins de deux semaines.

Lors du Défi DES II-1 (février 1998), Deep Crack, associé au réseau de calcul bénévole distributed.net, a cassé DES en seulement 39 jours. Le Défi II-2 (juillet 1998) est tombé en 56 heures.

L’amélioration rapide, de 96 jours à 56 heures en une seule année, a démontré à quelle vitesse les progrès du matériel et une meilleure coordination pouvaient accélérer les attaques par force brute.

En janvier 1999, Deep Crack de l’EFF, associé à distributed.net, a cassé le Défi DES III en seulement 22 heures et 15 minutes, remportant une récompense de 10 000 $ offerte par RSA Security.

Cette démonstration définitive que DES pouvait être cassé en moins de 24 heures a effectivement mis fin à tout argument en faveur de la sécurité de DES. Peu après, NIST a commencé à sélectionner un remplacement pour DES, qui est devenu AES.

Distributed.net a organisé des efforts de calcul bénévole dans le cadre desquels des internautes ordinaires mettaient leurs cycles CPU à disposition pour les défis DES. À son apogée, des centaines de milliers d’ordinateurs participaient.

Chaque ordinateur mettait à l’épreuve une portion différente de l’espace de clés, sous la coordination d’un serveur central. Ce modèle de calcul distribué pour la cryptanalyse, encore utilisé aujourd’hui pour des défis comme le cassage d’anciens chiffres, a été inauguré par cette initiative.

L’épuisement de l’espace de clés fonctionne parce que chaque déchiffrement DES est rapide (quelques microsecondes sur le matériel) et indépendant. Il n’existe aucune dépendance entre la mise à l’épreuve de la clé N et celle de la clé N+1 ; la recherche peut donc être parfaitement répartie entre un nombre quelconque de machines.

Cette nature particulièrement propice au parallélisme signifie que doubler le matériel réduit exactement le temps de moitié. Ajouter des machines produit une accélération linéaire, ce qui rend l’opération économiquement avantageuse pour les adversaires.

Eli Biham et Adi Shamir ont publié la cryptanalyse différentielle en 1990, une technique qui exploite la manière dont les différences entre des paires d’entrées se propagent à travers les tours d’un chiffre. Pour DES, elle nécessite théoriquement 2^47 textes en clair choisis.

On a découvert rétrospectivement que les boîtes S de DES avaient été conçues en tenant compte de leur résistance à la cryptanalyse différentielle, ce qui laisse penser que la NSA connaissait cette technique dans les années 1970. Cette attaque est impressionnante sur le plan théorique, mais elle est en pratique dépassée par la force brute matérielle.

Mitsuru Matsui a publié la cryptanalyse linéaire en 1993 ; celle-ci nécessite 2^43 textes en clair connus pour attaquer DES. Il a mis l’attaque en œuvre et a cassé DES expérimentalement en 1994, confirmant l’analyse théorique.

La cryptanalyse linéaire trouve des approximations linéaires du comportement des boîtes S et les utilise pour retrouver des bits de clé grâce à un biais statistique. En théorie, elle nécessite beaucoup moins de données que la force brute, mais elle était irréalisable avant les attaques matérielles.

La cryptanalyse différentielle a été publiée en 1990, mais elle nécessite des textes en clair choisis, ce qui est irréalisable dans la plupart des situations réelles. La cryptanalyse linéaire a été publiée en 1993 et fonctionne avec des textes en clair connus, mais elle en exige 2^43.

La force brute matérielle, avec Deep Crack, a cassé DES en 22 heures en 1999. En pratique, l’attaque matérielle a été plus dévastatrice que les avancées cryptanalytiques théoriques, car elle ne nécessitait aucune paire particulière de textes en clair et de textes chiffrés.

Le cassage public et documenté de DES a eu des conséquences politiques immédiates. NIST a lancé le processus de compétition d’AES en 1997, l’année même où le Défi DES I a été remporté. La compétition a été explicitement conçue pour éviter les faiblesses du processus de normalisation de DES.

Les banques et les organismes gouvernementaux ont commencé à passer à 3DES comme mesure provisoire pendant le développement d’AES. La chronologie du cassage de DES a directement déterminé l’urgence et le calendrier de l’adoption d’AES.

Vérifiez votre compréhension de l’histoire du cassage de DES.

DES a été cassé de plus en plus rapidement : en 96 jours en 1997, en 56 heures en 1998, puis en 22 heures en 1999. Le Deep Crack de l’EFF, d’un coût de 250 000 $, utilisait des circuits intégrés spécifiques pour mettre à l’épreuve 90 milliards de clés par seconde.

La cryptanalyse différentielle (2^47 textes en clair choisis) et la cryptanalyse linéaire (2^43 textes en clair connus) permettent également, en théorie, de casser DES, mais la force brute matérielle a été le véritable facteur décisif. Le cassage en 22 heures a mis fin à l’utilisation viable de DES comme chiffre.