Chapitre 4 FAQ de sci.crypt Chapitre 6 Retour à la case départ

Chiffres produits

Ceci est le cinquième des dix chapitres de la FAQ de sci.crypt. Nous n'avons pas le temps d'envoyer ce qui manque par courrier électronique, donc ne demandez rien.
Des notes comme "[KAH67]" renvoient à la liste de références au dernier chapitre.

Les chapitres de cette FAQ sont disponibles par FTP anonyme sur ftp://rtfm.mit.edu/pub/usenet/news.answers/cryptography-faq/part[xx]
La FAQ de cryptographie est postée sur les groupes de discussions sci.crypt, talk.politics.crypto, sci.answers, et news.answer tous les 21 jours.

Table des matières

5.1. Qu'est-ce qu'un "chiffre produit"?

[NdT: j'ai traduit product cipher littéralement par chiffre produit. Je ne connais pas le terme exact en français]
Un produit est un chiffrement par bloc qui répète plusieurs opérations faibles comme des substitutions, des transpositions, des additions ou des multiplications modulo N, et des transformations linéaires (un chiffrement par bloc signifie que l'on chiffre un bloc de données à la fois (par exemple 8 octets), puis on passe au bloc suivant). La notion de chiffre produit est due à Shannon [SHA49]. Des exemples de chiffres produits modernes sont LUCIFER [SOR84], le DES [NBS77], les réseaux SP [KAM78], LOKI [BRO90], FEAL [SHI84], PES [LAI90], Khufu et Khafre [ME91a]. Les chiffres de Feistel sont une classe de chiffres produits qui opèrent sur une moitié du cryptogramme à chaque ronde et échangent les deux moitiés après chaque ronde. LUCIFER, le DES, LOKI, et FEAL sont des exemples de chiffres de Feistel.

Voici un comparatif des principaux paramètres de divers chiffres produits:

Chiffre Taille de bloc Bits de clé Nombre de rondes
LUCIFER12812816
DES645616
LOKI646416
FEAL641282^5, x >= 5
PES641288

5.2. Qu'est-ce qui rend un chiffre produit sûr?

Personne ne sait prouver mathématiquement qu'un chiffre produit est sûr. Aussi en pratique on commence en démontrant que le chiffre a l'air hautement aléatoire. Par exemple, le chiffre doit être non linéaire et il doit produire des cryptogrammes qui dépendent de tous les bits du texte clair et de la clé. Meyer [MEY78] a montré qu'au moins 5 rondes du DES sont nécessaires pour garantir cette dépendance. Dans ce sens un produit est un "mélange" de fonctions qui combinent le texte clair, la clé et le cryptogramme de manière compliquée et non linéaire.

Les substitutions à chaque ronde du produit sont appelées les boîtes S. Par exemple, LUCIFER a 2 boîtes S, et le DES en a 8. La non linéarité du produit dépend d'une conception soigneuse de ces boîtes S. Une liste partielle des critères de conceptions des boîtes S du DES, qui s'appliquent aux boîtes S en général, se trouve dans Brown [BRO89] et Brickell et al. [BRI86].

5.3. Quelles sont les propriétés de la théorie des groupes qui s'appliquent aux produits?

Soit E un chiffre produit qui transforme un bloc de N bits en bloc de N bits.
Soit EK(X) le chiffrement de X avec une clé K.
Alors, pour tout K fixé, la fonction X -> EK(X) est une permutation de l'ensemble des blocs de N bits.
Soit PK cette permutation. L'ensemble de toutes les permutations de N bits est appelé le groupe symétrique et est noté S{2^N}
L'ensemble de toutes les permutations PK, où K varie parmi toutes les clés possibles est appelé E(S{2^N}). Si E était une fonction aléatoire des libellés vers les cryptogrammes alors on s'attendrait à ce que E(S{2^N}) génère un gros sous-ensemble de S{2^N}.

Coppersmith et Grossman [COP74] ont montré qu'un chiffre produit très simple peut générer le groupe A{2^N} avec un nombre suffisant de rondes
(A{2^N} est la moitié du groupe symétrique: il est composé de toutes les permutations "paires", c'est-à-dire toutes les permutations qui peuvent s'écrire comme un nombre pair d'échanges)
Even et Goldreich [EVE83] ont été capables d'étendre ces résultats pour montrer que les chiffres de Feistel peuvent générer A{2^N} avec un nombre suffisant de rondes.

La sécurité des surchiffrements dépend aussi des propriétés "de groupe" d'un chiffre. Les chiffrements multiples sont une amélioration par rapport au chiffrement simple si pour les clés K1 et K2 il n'existe pas de clé K3 telle que
EK2(EK1(X)) == EK3(X) (**)
ce qui voudrait dire que le double chiffrement avec deux clés indépendantes K1 et K2 serait équivalent au chiffrement simple avec une troisième clé K3. Si pour tout K1 et K2 il existe K3 telle que (**) est vraie alors on dit que E est un groupe.

Cette question de savoir si le DES est un groupe selon cette définition a été largement étudiée par Sherman, Kaliski, et Rivest [SHE88]. Dans leur papier ils ont une forte présomption que le DES ne soit pas un groupe. En fait, le DES n'est pas un groupe [CAM93].

5.4. Qu'est-ce qui peut être prouvé sur la sécurité d'un "produit"?

D'après ce qu'on a dit plus haut, PK est une permutation produite par E en fonction d'une clé K. Le but du concepteur de E est de s'assurer que PK apparaisse comme un élément au hasard du groupe symétrique S{2^N}. Soit R un élément de S{2^N} pris au hasard. Nous dirons que PK et R sont indiscernables si un observateur à qui on a donné PK et R ne peut pas les différencier en temps polynomial. C'est-à-dire qu'en un temps limité, l'observateur ne peut pas distinguer les permutations produites par E: la décision optimale n'est pas meilleure qu'une simple devinette.

Luby et Rackoff [LUB88] ont montré qu'une classe de chiffres de Feistel est sûre selon cette définition quand la fonction appliquée à chaque ronde est remplacée par des fonctions booléennes aléatoires.

5.5. Comment les algorithmes de chiffrement par bloc peuvent-ils chiffrer des données plus longues qu'un bloc?

Il y a quatre mode opératoires standards (et beaucoup d'autres non standards). Les modes standards sont définis dans U.S. Department of Commerce Federal Information Processing Standard (FIPS) 81, publié en 1980. Voir la question sur l'ECB ci-dessous pour plus de détails.

Bien qu'ils soient définis pour le DES, ces modes peuvent être utilisés avec n'importe quel algorithme de chiffrement par blocs.

5.6. Les algorithmes de chiffrement par blocs symétriques peuvent-ils être utilisés pour l'authentification de messages?

Vous pouvez utiliser un cryptosystème symétrique pour vous prouver que vous avez généré un message et que le message n'a pas été altéré après sa création. Mais vous ne pouvez pas prouver cela à quelqu'un d'autre sans révéler votre clé. Ensuite vous ne pourrez rien prouver à propos des messages authentifiés avec cette clé.

Voir ANSI X3.106-1983 et FIPS 113 (1985) pour une méthode d'authentification de messages standard basée sur le DES.

5.7. Qu'est-ce que le DES exactement?

Le DES est le Standard de Chiffrement de Données (Data Encryption Standard) du gouvernement américain, un chiffre produit qui opère sur des blocs de 64 bits en utilisant une clé de 56 bits.

Il est défini dans FIPS 46-1 (1988) [qui remplace FIPS 46 (1977)]. FIPS signifie Federal Information Processing Standards; ces standards sont publiés par NIST.
Le DES est identique à l' ANSI standard Data Encryption Algorithm (DEA) défini dans ANSI X3.92-1981.

5.8. Qu'est-ce que le triple DES?

Le Triple DES est un chiffre produit qui, comme le DES, travaille sur des blocs de données de 64 bits. Il en existe plusieurs formes qui utilisent toutes le DES trois fois. Certaines utilisent deux clés de 56 bits, d'autres trois. Les modes opératoires du DES peuvent être aussi utilisés avec le Triple DES.

Certains appellent "Triple DES " l'opération E(K1,D(K2,E(K1,x))).

Cette méthode est définie au chapitre 7.2 du standard ANSI X9.17-1985 Financial Institution Key Management et est prévue pour chiffrer les clés et vecteurs d'initialisation DES pour la distribution automatique de clés. Son nom officiel est Chiffrement et déchiffrement d'une clé simple à l'aide d'une paire de clés mais est appelée EDE dans d'autres standards.

Ce standard dit (paragraphe 7.2.1): "Les clés de chiffrement de clés peuvent être une clé DEA simple ou une paire de clés DES. Les paires de clés doivent être utilisées où l'on a besoin d'une sécurité accrue (par exemple si les données protégées par la (les) clé(s) ont une longue vie). Une paire de clés ne doit pas être chiffrée ou déchiffrée à l'aide d'une clé simple".

D'autres appellent "triple DES" l'opération E(K1,D(K2,E(K3,x))) ou bien E(K1,E(K2,E(K3,x))).

Toutes ces méthodes sont définies seulement pour le mode ECB. La sécurité des diverses méthodes dans les autres modes (comme le CBC) est à l'étude en ce moment. Pour le moment, on doit supposer que les autres modes seront définis comme ils le sont actuellement mais avec E(K1,D(K2,E(K1,x))) comme algorithme de chiffrement par bloc à la place du DES simple dans le mécanisme de rétroaction.

L'un d'entre nous (Ellison) a longtemps plaidé pour le triple DES sous la forme

E(K1, Tran( E(K2, Tran( E(K3, Compress( x )))))),

où chaque exemplaire du DES a sa propre clé et son propre vecteur d'initialisation (en mode CBC) et où Tran est un programme de transposition de gros blocs. Tran est disponible dans [FTPTR]. Ceci augmenterait la sécurité en diffusant les changements de bits sur un bloc beaucoup plus gros (la taille de bloc de Tran). D'autres compositions de chiffres faibles avec le DES sont possibles. Par exemple on pourrait définir :

E(K1, Prngxor(K4, Tran( E(K2, Tran( Prngxor(K5, E(K3, Compress( x )))))))),

où Prngxor() [FTPPX] est un algorithme de chiffrement de flux simple basé sur un générateur pseudo aléatoire à longue période, pour être sûr que tous les motifs du texte clair ou du cryptogramme seront cachés même quand on utilise le mode ECB du DES -- l'utilisation de boucles intérieures en mode CBC présente en effet des faiblesses face à certaines attaques, et on ignore encore si elles sont toujours présentes lors de la composition avec Tran().

[NdT:
Pourquoi le DES triple avec deux clés seulement ? Éh bien ! parce qu'un DES double serait vulnérable à une attaque meet in the middle qui réduirait la recherche à l'espace de clé d'un DES simple, au prix d'un précalcul et d'un stockage assez monstrueux.
Pourquoi déchiffrer au milieu ? Ceci permet aux chips qui font du 3DES de faire aussi du DES simple en chargeant 3 fois la même clé.

5.9. Qu'est-ce que la cryptanalyse différentielle?

La cryptanalyse différentielle est une méthode d'attaque statistique qui peut être appliquée à tout processus itératif (c'est-à-dire un processus basé sur l'application répétée d'une fonction). La méthode a été popularisée récemment par Biham et Shamir [NIH91], mais Coppersmith a remarqué que les boîtes S du DES ont été optimisées contre cette attaque il y a 20 ans. Cette méthode est efficace contre plusieurs chiffres produits, notamment FEAL [BI91a].

La cryptanalyse différentielle se base sur l'observation d'un grand nombre de textes chiffrés Y, Y' correspondant à des textes clairs X, X' ayant une différence connue D=X+X' où + est le OU exclusif. Dans l'attaque de base de Biham-Shamir, 2^47 paires de tels textes clairs sont nécessaires pour déterminer la clé du DES. Si le DES est tronqué à 6 ou 8 rondes, il faut significativement moins de paires. Dans ces cas, la clé peut être retrouvée en quelques minutes en utilisant quelques milliers de paires.
Pour le DES complet, cette attaque est irréalisable car elle demande trop de textes clairs connus.

Le travail de Biham et Shamir sur le DES a révélé plusieurs observations étonnantes sur l'algorithme. La plus importante est que si la génération des clés [NdT: key schedule] était supprimée du DES et si l'on utilisait une clé de 16*48 = 768 bits, on pourrait retrouver la clé en moins de 2^64 étapes. Ainsi des sous-clés indépendantes n'améliorent pas énormément la sécurité du DES.
De plus les boîtes S du DES sont extrèmement sensibles: le changement d'une seule entrée dans ces tables "améliore" grandement l'efficacité de l'attaque différentielle.

Adi Shamir a dit (NYTimes 31 Oct 1991): "je voudrais dire que, contrairement à ce que certains croient, il n'y a pas de preuve que la conception de base du DES a été affaiblie".

5.10. Comment la NSA a t-elle été impliquée dans la conception du DES ?

D'après Kinnucan [KIN78], Tuchman, un membre de l'éauipe d'IBM qui a développé le DES aurait dit:
Nous avons entièrement développé le DES chez IBM avec des gens d'IBM. La NSA n'a pas dicté une seule ligne!
Tuchman et Meyer (un autre développeur du DES) a passé un an à casser des chiffres et a fini par trouver des faiblesses dans Lucifer.
Leur approche était de chercher des substitutions, des permutations et des mises en place de clés fortes... IBM a classifié les notes contenant les critères de sélection à la demande de la NSA... La NSA nous a dit que nous avions réinventé par inadvertance certains des secrets profonds qu'ils utilisent dans leurs propres algorithmes
explique Techman.

D'un autre côté, un document intitulé Involvement of the NSA in the development of DES: unclassified summary of the United States Select Committee on Intelligence publié dans IEEE Communications Magazine, p53-55, 1978, dit:
Dans le développement du DES, la NSA a convaincu IBM qu'une taille de clé réduite était suffisante; a indirectement aidé au développement de la structure des boîtes S; et a certifié que l'algorithme DES final était, à leur connaissance, dépourvu de faiblesses mathématiques ou statistiques.


Il est clair que la NSA a insisté pour réduire la taille de clé. L'article dit de plus que la NSA n'a pas touché à l'algorithme lui-même, seulement ses paramètres, ce qui dans un certain sens résout le conflit apparent avec les remarques de Meyer et Tuchman.

5.11. Le DES est-il disponible en logiciel?

Plusieurs personnes a écrit des codes DES disponibles par FTP (voir le chapitre 10 pour les chemins d'accès): Stig Ostholm [FTPSO]; BSD [FTPBK]; Eric Young [FTPEY]; Dennis Furguson [FTPDF]; Mark Riordan [FTPMR]; Phil Karn [FTPPK].
Un source Pascal du DES est aussi fourni chez Patterson [PAT87]. Antti Louko <alo@kampi.hut.fi> a écrit une version du DES avec les packages BigNum dans [FTPAL].

FIPS 46-1 dit "L'algorithme spécifié dans ce standard doit être réalisé ... en technologie matérielle (pas logicielle). ... Les mises en oeuvres logicielles dans des ordinateurs d'usage général ne sont pas conformes à ce standard." En dépit de ceci, il existe beaucoup de réalisations logicielles, et des agences gouvernementales les utilisent.

5.12. Le DES est-il disponible en matériel?

Les paragraphes suivants sont tirés de messages envoyés aux auteurs. Nous ne nous engageons pas sur la qualité ou même l'existence de ces produits.

Christian Franke, franke@informatik.rwth-aachen.de, dit:
1. Cryptech CRY12C102: 22.5Mbit/s d'après la fiche technique, avec une interface 32 bits. Nous utilisons celui-là, car c'est le seul qui était disponible quand nous avons lancé le projet. Aucun problème!
2. Pijnenburg PCC100: 20Mbit/s d'après la fiche technique. Adresse: PIJNENBURG B.V., Boxtelswweg 26, NL-5261 NE Vught, Pays-Bas.
3. INFOSYS DES Chip (Allemagne): Les boîtes S doivent être chargées par logiciel. Donc vous pouvez modifier l'algorithme. Désolé, je n'ai pas la fiche technique sous la main. S'il vous plait envoyez-moi un courrier si vous avez besoin d'autres renseignements.
Marcus J Ranum, mjr@tis.com, dit:
"SuperCrypt" 100Mbits/s et plus.
DES and Proprietary Storage for 16 56-bit keys Key stream generator Integrated hardware DES3 procedure Extended mode with 112 bit keys; Computer Elektronik Infosys; 512-A Herndon Parkway,; Herndon, VA 22070; 800-322-3464. [NdT: qqn comprend qqch à ce charabia télégraphique ?]
Tim Hember, thember@gandalf.ca, dit:
Newbridge Microsystems vend une puce DES AM9568 qui travaille à 25 MHz, effectue un chiffrement en 18 cycles d'horloge, a un pipeline à 3 étages, supporte les modes ECB, CBC, CFB-8 et "CFB-1". De plus le prix est très raisonable si on le compare à d'autres puces DES haut de gamme. Appelez Newbridge Microsystems, Ottawa, 613-592-0714. (... il n'y a pas de problème d'import/export entre les Etats-Unis et le Canada). Si vous avez besoin de circuits intégrés maison, DES ou à clé publique, alors Timestep Encryption a développé les puces cryptographiques de Newbridge et d'autres circuits intégrés pour des établissements scolaires ou commerciaux. On peut les joindre au 613-820-0024.

5.13. Peut-on utiliser le DES pour chiffrer des données classifiées?

Le DES n'a pas été conçu pour protéger des données classifiées. Le standard FIPS 46-1 dit:
Ce standard sera utilisé par tous les départements et agences fédéraux pour la protection cryptographique des données informatiques quand les conditions suivantes s'appliquent:
1. ... une protection cryptographique est requise; et 2. Les données ne sont pas classifiées selon le National Security Act de 1947, amendé, ou le Atomic Energy Act de 1954, amendé.

5.14. Qu'est-ce que le chiffrement ECB, CBC, CFB, et OFB?

Ce sont les façons d'utiliser des chiffrements par bloc, comme le DES, pour chiffrer des messages, des fichiers et des blocs de données, connus sous le nom de modes opératoires.
Quatre modes opératoires sont définis dans FIPS 81 (2 Décembre 1980) et aussi dans ANSI X3.106-1983.

FIPS 81 spécifie que quand des données ASCII sur 7 bits sont envoyées par octets, le bit le plus significatif inutilisé doit être mis à 1.

FIPS 81 spécifie aussi le bourrage pour les blocs courts.

Les quatre modes opératoires du DES dans les standards FIPS/ANSI sont: Les quatre modes ANSI/FIPS ont très peu de "propagation d'erreurs". Si un bit seul est en erreur dans le flux, la longueur de la chaîne erreur sera au plus de 128 bits.
Un cinquième mode opératoire, utilisé dans Kerberos et ailleurs mais défini dans aucun stanard, est le error-Propagating Cipher Block Chaining [Chiffrement par chainage de blocs avec propagation d'erreurs] (PCBC). Contrairement aux quatre modes standard, le PCBC étend l'effet d'une simple erreur de bit dans tout le flux restant après l'erreur.
[NdT: ce mode était utilisé dans Kerberos 4 mais a été abandonné dans Kerberos 5 : on y a découvert des faiblesses]

Ces cinq méthodes sont expliquées ci-dessous dans une notation similaire au langage C.

Quelques définitions:
P[n]
Le n-ième bloc du texte clair, l'entrée du chiffrement, la sortie du déchiffrement. La taille du bloc est déterminée par le mode.
C[n]
Le n-ième bloc du texte chiffré, la sortie du chiffrement, l'entrée du déchiffrement. La taille du bloc est déterminée par le mode.
E(m)
La fonction de chiffrement du DES, sur un bloc m de 64 bits, en utilisant les sous-clés générées à partir d'une clé de 56 bits.
D(m)
La fonction de chiffrement du DES, sur un bloc de 64 bits, en utilisant les mêmes sous-clés que E(m), si ce n'est qu'elles sont en ordre inverse.
IV
Un vecteur d'initialisation de 64 bits, une valeur secrète qui, avec la clé est partagée par le chiffreur et le déchiffreur.
I[n]
La n-ième valeur d'une variable de 64 bits, utilisée dans certains modes.
R[n]
La n-ième valeur d'une variable de 64 bits, utilisée dans certains modes.
LSB(m,k)
Les k bits les moins significatifs (de droite) de m.
Par exemple: m & ((1 << k) - 1)
MSB(m,k)
Les k bits les plus significatifs (de gauche) de m.
Par exemple: (m >> (64-k)) & ((1 << k) - 1)

Les opérateurs = ^ << >> & sont définis comme dans le langage C.

Livre de codage électronique (ECB)
P[n] et C[n] font chacun 64 bits de long.
ChiffrementDéchiffrement
C[n] = E(P[n])P[n] = D(C[n])

Chiffrement par chainage de blocs (CBC)
P[n] et C[n] font chacun 64 bits de long.
ChiffrementDéchiffrement
C[0] = E(P[0]^IV)P[0] = D(C[0])^IV
n>0C[n] = E(P[n]^C[n-1]) P[n] = D(C[n])^C[n-1]

Chiffrement par chainage de blocs avec propagation (PCBC)
P[n] et C[n] font chacun 64 bits de long.
ChiffrementDéchiffrement
C[0] = E(P[0]^IV)P[0] = D(C[0])^IV
n>0C[n] = E(P[n]^P[n-1]^C[n-1]) P[n] = D(C[n])^P[n-1]^C[n-1]

Chiffrement par rétroaction sur k bits (CFB)
P[n]et C[n] font chacun k bits de long, 1 <= k <= 64.
ChiffrementDéchiffrement
I[0] = IVI[0] = IV
n > 0 I[n] = I[n-1]<<k | C[n-1] I[n] = I[n-1]<<k | C[n-1]
Pour tout n R[n] = MSB(E(I[n]),k) R[n] = MSB(E(I[n]),k)
Pour tout n C[n] = P[n]^R[n] P[n] = C[n]^R[n]

Notez que si k==64, ceci se simplifie en:
I[0] = IVI[0] = IV
n > 0I[n] = C[n-1]I[n] = C[n-1]
Pour tout nR[n] = E(I[n])R[n] = E(I[n])
Pour tout nC[n] = P[n]^R[n] P[n] = C[n]^R[n]

Notes sur le CFB: Comme I[n] dépend seulement du texte clair ou chiffré de l'opération précédente, la fonction E() peut être calculée en parallèle avec la réception du texte avec lequel elle va être utilisée.

Rétroaction en sortie sur k bits (OFB)
P[n] et C[n] font chacun k bits de long, 1 >= k >= 64.
ChiffrementDéchiffrement
I[0] = IVI[0] = IV
n > 0I[n] = I[n-1]<<k | R[n-1] I[n] = I[n-1]<<k | R[n-1]
Pour tout nR[n] = MSB(E(I[n]),k) R[n] = MSB(E(I[n]),k)
Pour tout nC[n] = P[n]^R[n]P[n] = C[n]^R[n]

Notez que si k==64, ceci se simplifie en:
I[0] = IVI[0] = IV
n > 0I[n] = R[n-1]I[n] = R[n-1]
Pour tout nR[n] = E(I[n])R[n] = E(I[n])
Pour tout nC[n] = P[n]^R[n]P[n] = C[n]^R[n]

Notes sur l'OFB: le chiffrement et le déchiffrement sont identiques. Comme I[n] est indépendant de P et C, la fonction E() peut être calculée en avance sur la réception du texte clair/chiffré avec lequel elle va être utilisée.

Notes supplémentaires sur les modes opératoires du DES:
L'ECB et le CBC utilisent E() pour chiffrer et D() pour déchiffrer, mais les modes par rétroaction utilisent E() pour chiffrer et déchiffrer. Ceci invalide cet argument erroné:
Les mises en oeuvre du DES qui proposent E() mais pas D() ne peuvent pas être utilisées pour la confidentialité des données.

Chapitre 4 FAQ de sci.crypt Chapitre 6 Retour à la case départ
Michel Arboi
Last modified: Sun Mar 25 16:20:53 CEST 2007