Le mystère de la S-box et la sécurité DES 

la NSA (National Security
Agency) américaine à  partir de l’algorithme de cryptage original nommé Lucifer
et conçu par IBM en 1976 (la S-box est l’ensemble des nombres commençant en A
sur la figure 5).
D’aucuns pensaient que la NSA avait implanté une propriété mathématique secrète
ou “invisible” dans ces nombres pour permettre l’espionnage. Les raisons de la
NSA en modifiant la S-box étaient restées mystérieuses jusqu’à  il y a peu. Entre-temps,
de nombreux spécialistes du chiffrement avaient cédé aux chant des sirènes à  la
recherche d’une propriété invisible, cachée dans la S-box. Même le Senat Select
Committee on Intelligence américain avait enquêté sur le sujet en 1978.

Le mystère a été levé en mai 1994, lorsque le Journal of Research and Development
d’IBM publia les critères de conception de la S-box version NSA. En l’occurrence,
les concepteurs du DES avaient optimisé la S-box pour résister à  une puissante
méthode d’attaque cryptographique baptisée analyse cryptographique différentielle.

Cette méthode compare des paires de textes crypté dont l’équivalent en
clair présente des différences particulières. Etant donné que la méthode d’attaque
n’était pas connue dans la littérature publiée dans les années 1970, IBM et la
NSA en avaient conclu que la reconnaissance de l’existence de la méthode affaiblirait
les autres systèmes cryptographiques et réduirait de ce fait l’avantage compétitif
dont bénéficiaient les Etats-Unis sur les autres pays dans le domaine de la cryptographie.

Cependant, l’expérience a montré que le meilleur moyen de développer des algorithmes
de cryptographie puissants n’est pas le secret mais la déclaration publique et
l’étude critique par des experts indépendants. Le gouvernement américain a appris
cette leçon à  ses dépens lorsqu’il a gardé secret l’algorithme de cryptage de
l’important dépôt fiduciaire Clipper. Les spécialistes de la cryptographie triés
sur le volet avec soin par le gouvernement (les seuls scientifiques non gouvernementaux
autorisés à  analyser le fonctionnement interne de Clipper) ont sous-estimé un
défaut fatal de l’algorithme qui en a rendu l’usage projeté par mise en application
de la loi inefficace. Matt Blaze, chercheur chez AT&T découvrit par la suite le
défaut (fort heureusement avant que l’algorithme ne soit largement déployé). Le
gouvernement renonça rapidement au projet Clipper.

Une fois les renseignements sur l’analyse cryptographique différentielle tombés
dans le domaine public (grâce en partie au volumineux ouvrage Applied Cryptography:
Protocols, Algorithms and Source Code in C de Bruce Schneier:, John Wiley
& Sons, 1994), le gouvernement a autorisé la publication des critères de conception
de la S-box. Il est clair désormais qu’il n’y avait pas de porte secrète, mais
entre-temps, une autre menace pointait en direction du DES : celui-ci était susceptible
d’être attaqué en essayant chaque clé possible.

Le problème de la longueur de clé

Dès la première parution du standard DES, les chercheurs en cryptographie
se sont plaints qu’une clé de 56 bits était trop courte. La NSA a imposé la limitation
d’une clé de petite taille pour le DES, invoquant des raisons de sécurité nationale
et assurant au public que le décryptage empirique ne serait pas possible dans
un futur proche. Cependant, fin 1997, un groupe de chercheurs en Internet utilisant
des systèmes fonctionnant en réseau mais pas couplés et la méthode de recherche
empirique ont décodé un DES de 40 bits en cinq mois. En 1998, la même méthode
a été utilisée pour décoder une clé de 56 bits en 39 jours. à€ peu près au même
moment, l’EFF (Electronique Frontier Foundation) apportait les dernières touches
à  un ordinateur parallèle spécialisé capable de décoder un DES de 56 bits en seulement
une semaine et démontrait qu’une machine semblable d’une valeur de un million
de dollars pouvait effectuer le même travail en 16 heures (le système est entièrement
documenté, le code source complet et les schémas de câblage étant fournis dans
l’ouvrage Cracking DES: Secrets of Encryption Research, Wiretap Politics, and
Chip Design, EFF, O’Reilly & Associates, 1998).

à€ la lumière de ce progrès du secteur privé, beaucoup de membres de la communauté
cryptographique pensent que la NSA décodait les messages DES depuis le début,
en utilisant des systèmes secrets et ultrarapides du gouvernement. Il ne semble
pas exister d’autre explication pour justifier son insistance à  utiliser des clés
de 56 bits.

Si un DES peut être décodé, quel est alors l’intérêt de l’utiliser ? Primo, bien
qu’il soit en principe “décodable”, le cryptage d’un message représente encore
un coût fort élevé. Le standard DES continue à  représenter un obstacle considérable
pour la vaste majorité des pirates informatiques. Secundo, la faiblesse du DES
face à  une attaque empirique peut être compensée en utilisant une variante du
DES baptisée 3DES (Three-key Triple DES). Dans ce cas de figure, il s’agit d’utiliser
trois clés différentes et d’exécuter l’algorithme DES dans une séquence EDE (Encrypt-Decrypt-Encrypt)
sur chaque bloc de message, comme ceci :

Etape1 : Encryptage(TexteClairA, Clé1) -> TexteCryptéB

Etape2 : Decryptage(TexteCryptéB, Clé2) -> TexteClairC

Etape3 : Encryptage(TexteClairC, Clé3) -> TexteCryptéD

Pour décrypter 3DES, on inverse le processus, comme ceci :

Etape1 : Decryptage(TexteCryptéD, Clé3) -> TexteClairC

Etape2 : Encryptage(TexteClairC, Clé2) -> TexteCryptéB

Etape3 : Decryptage(TexteCryptéB, Clé1) -> TexteClairA

GG