Le Data Encryption Standard (DES) est un algorithme de chiffrement symétrique par blocs, basé sur un schéma de Feistel, qui opère sur des blocs de 64 bits en utilisant une clé secrète de 56 bits (avec 8 bits de parité sur 64 bits total). Il utilise 16 tours itératifs pour transformer le texte clair en texte chiffré.

Étapes principales du fonctionnement :
1. Permutation initiale ($IP$) : Le bloc de 64 bits est réorganisé selon une permutation fixe, sans impact sur la sécurité.
2. 16 tours de Feistel : Chaque tour divise le bloc en deux parties de 32 bits : $L_0$ (gauche) et $R_0$ (droite).

• $R_1 = L_0 ⊕ f(R_0, K_1)$
• $L_1 = R_0$ où $$$f$ est une fonction de confusion utilisant la sous-clé $K_1$ (48 bits), dérivée de la clé principale.
• La fonction $f$ comprend :
  • Expansion de 32 bits vers 48 bits (E).
  • $XOR$ avec la sous-clé $K_1$.
  • Boîtes de substitution (S-Boxes) : 8 fonctions non linéaires qui remplacent 6 bits par 4 bits, ajoutant de la confusion.
  • Permutation de 32 bits (P) pour assurer la diffusion.

3. Échange final : Après les 16 tours, les deux moitiés sont échangées ($L_{16}$ devient $R_{16}$, $R_{16}$ devient $L_{16}$), mais sans transformation.
4. Permutation finale ($IP^{-1}$) : La sortie est réorganisée selon l’inverse de la permutation initiale, produisant le texte chiffré.

Déchiffrement :
Le déchiffrement suit le même schéma, mais les sous-clés sont utilisées dans l’ordre inverse ($K_{16}$ à $K_{1}$).

En cryptographie, les algorithmes de hachage (comme SHA-256) ou de chiffrement (comme DES) utilisent intensivement des opérations sur les bits.
Deux opérations fondamentales sont :

• La rotation de bits : les bits sortant à droite réapparaissent à gauche.
• Le décalage de bits : les bits sortant à droite sont perdus, des zéros sont ajoutés à gauche.

Partie 1 : Le décalage à droite

Le décalage à droite (>> en Python) déplace tous les bits d’un nombre vers la droite. Les bits qui « sortent » à droite sont perdus, et des zéros sont ajoutés à gauche.

Exemple avec un nombre 8 bits (pour simplifier) :

Nombre original : 11011010 (218 en décimal)
Décalage de 2 bits vers la droite :
Résultat : 00110110 (54 en décimal)

Les deux bits de droite (10) sont perdus, et deux zéros sont ajoutés à gauche.

>>> shr(0b1101, 1)   # 1101 (13) → 0110 (6)
6
>>> shr(0b1101, 2)   # 1101 (13) → 0011 (3)
3
>>> hex(shr(0x12345678, 8))  # Décalage de 8 bits
0x00123456

Partie 2 : La rotation à droite

La rotation est similaire au décalage, mais les bits qui sortent à droite réapparaissent à gauche.

Exemple avec un nombre 8 bits :

Nombre original : 11011010
Rotation de 2 bits vers la droite :
Étape 1 : décalage classique → 00110110 (les bits 10 sont perdus)
Étape 2 : récupération des bits perdus → les bits 10 sont placés à gauche
Résultat : 10110110

Principe mathématique pour une rotation sur 32 bits :

rotation_droite(x, n) = (x >> n) | (x << (32-n))

où | est le OU binaire. Il faut ensuite masquer le résultat pour ne garder que 32 bits (avec & 0xFFFFFFFF).def

>>> rotr(0b1101, 1)  # Sur 4 bits imaginaires, mais on travaille en 32 bits
0x80000006  # Le bit de poids faible passe en poids fort
>>> rotr(0x12345678, 4)  # Rotation de 4 bits
0x81234567  # Le dernier chiffre hexa (8) passe devant

# Compléter les fonctions ci-dessous :
def shr(x, n):
    pass
def rotr(x, n):
    pass

L’histoire de l’origine des S-Boxes du DES est l’un des épisodes les plus fascinants et controversés de la cryptographie moderne. Elle mêle secrets d’État, avancées technologiques secrètes et une résolution qui n’est intervenue que près de 20 ans après la publication du standard.

Voici l’histoire en trois actes.

1. Une origine mystérieuse et des soupçons de « backdoor » (années 1970)

Au départ, IBM développa un algorithme nommé Lucifer avec une clé de 128 bits. Lorsque le National Bureau of Standards (NBS, devenu NIST) appela à un standard de chiffrement, IBM le soumit, mais avec une clé réduite à 56 bits à la demande de la NSA (National Security Agency). La modification la plus mystérieuse, cependant, fut l’altération des S-Boxes, ces huit tables de substitution qui constituent le cœur non-linéaire de l’algorithme.
La NSA modifia les S-Boxes proposées initialement par IBM . Aucune explication publique ne fut donnée, ce qui alimenta immédiatement les soupçons : beaucoup pensèrent que la NSA avait implanté une « porte dérobée » (backdoor) , une propriété mathématique secrète leur permettant d’espionner facilement les communications chiffrées .

2. La découverte publique d’une attaque et la levée du secret (années 1990)

Le mystère a commencé à se dissiper en 1990, lorsque les chercheurs Eli Biham et Adi Shamir publièrent une méthode d’attaque révolutionnaire appelée cryptanalyse différentielle . Ils découvrirent alors une chose surprenante : le DES, avec ses S-Boxes modifiées, était extraordinairement résistant à cette nouvelle attaque . De simples modifications des S-Boxes suffisaient à rendre le DES vulnérable.
Il est apparu que la NSA et l’équipe d’IBM (notamment Don Coppersmith) connaissaient déjà la cryptanalyse différentielle dès la conception du DES dans les années 1970, bien avant sa publication publique . Leurs modifications des S-Boxes avaient pour but précis de renforcer l’algorithme contre cette attaque, et non de l’affaiblir.
Ce n’est qu’en 1994 que Don Coppersmith publia officiellement les critères de conception des S-Boxes, confirmant cette version . Le gouvernement américain autorisa cette publication une fois que la technique de cryptanalyse différentielle fut tombée dans le domaine public.

3. Des critères de conception très stricts

Loin d’être arbitraires, les S-Boxes du DES ont été choisies pour satisfaire à des critères mathématiques rigoureux afin de maximiser la sécurité :

• Non-linéarité : Aucune S-Box ne doit être une fonction linéaire ou affine de son entrée . C’est ce qui crée la confusion (selon Shannon), essentielle pour déjouer les analyses statistiques.
• Résistance à la cryptanalyse différentielle : Pour toute différence d’entrée non nulle, la différence de sortie ne doit pas être trop prévisible. Les concepteurs ont notamment veillé à ce qu’un changement d’un seul bit en entrée entraîne la modification d’au moins deux bits en sortie .
• Résistance à la cryptanalyse linéaire : Bien que cette attaque n’ait été publiée qu’en 1993, les S-Boxes ont montré par la suite une bonne résistance, même si elle n’était pas un critère de conception initial .

Les 8 S-Boxes de DES

Elles sont nommées $S_1, S_2, S_3, S_4, S_5, S_6, S_7, S_8$. Chaque S-Box convertit 6 bits en 4 bits. Toutes utilisent le même principe :
– Bits externes (positions 1 et 6) → ligne (0 à 3)
– Bits centraux (positions 2 à 5) → colonne (0 à 15)

Les 8 S-Boxes sont différentes pour maximiser la sécurité.

Exemple

Voici une S-Box ($S_5$) tirée de l’algorithme DES. La sortie de 4 bits est obtenue à partir de l’entrée de 6 bits. On divise ces 6 bits en deux parties : les deux bits aux extrémités et les quatre bits restants (au centre). Les deux bits aux extrémités indiquent la ligne et les bits centraux donnent la colonne correspondante. Par exemple, avec une entrée « 011011 », on divise en « 0 1101 1 ». Ce qui donne pour la ligne « 01 » et pour la colonne « 1101 ». La sortie de la table est alors « 1001 ».

• Sur la première ligne les 4 bits au centre de l’entrée
• Sur la première colonne les 2 bits externes

Contraintes d’implémentation matérielle

Les S-Boxes ont également été optimisées pour être implémentées avec un nombre minimum de circuits logiques (52 ou 53 minterms au lieu des $2^6 = 64$ théoriques : Dans les années 1970, moins de minterms = moins de transistors = circuit plus petit, plus rapide et moins cher.), une contrainte forte pour la technologie des années 1970. Cela prouve que les S-Boxes ne sont pas aléatoires. Des tables complètement aléatoires auraient nécessité beaucoup plus de minterms. Les concepteurs ont choisi des fonctions booléennes ayant une structure mathématique particulière, ce qui a permis cette optimisation.Shannon

En résumé

Les S-Boxes du DES ne contiennent pas de porte dérobée. Leur conception, en avance sur la recherche publique de plusieurs décennies, visait à protéger l’algorithme contre des attaques que seuls les concepteurs connaissaient. C’est un exemple parfait de la longueur d’avance des agences gouvernementales en cryptographie à cette époque.

Le tableau ci-dessous résume les meilleures attaques connues contre DES :

• La colonne « Paires connues/choisies » indique le nombre de couples (message clair, message chiffré) nécessaires à l’attaque :
  • « Connues » : l’attaquant dispose de ces paires sans pouvoir les choisir
  • « Choisies » : l’attaquant peut choisir les messages clairs à chiffrer
• La colonne « Mémoire » indique l’espace de stockage nécessaire (en nombre de blocs de 64 bits)
  • Exprimé en puissance de 2 : $2^{56} \text{blocs}\approx 72\times10^{15}\times 8 \text{octets} = 5.76×10^{17} \text{o} = 576 000 000 \text{To}$ (impossible en pratique)
• La colonne « Temps » indique le nombre d’opérations de chiffrement nécessaires
  • Une opération = un chiffrement DES complet
  • Exprimé aussi en puissance de 2

Analyse détaillée des attaques

1. Attaque par pré-calcul $(1, 2^{56}, 1)$

# Principe : calculer à l'avance tous les chiffrements possibles
def attaque_precalcul(message_clair, message_chiffre):
    # Phase de précalcul (une seule fois)
    table = {}
    for cle in range(2**56):  # Toutes les clés possibles
        table[des_chiffrement(message_clair, cle)] = cle
    # Phase d'attaque (instantanée)
    return table[message_chiffre]

• Paires : 1 seul couple suffit
• Mémoire : Énorme ($2^{56}$ entrées) → impossible en pratique
• Temps : 1 seul accès mémoire après pré-calcul

Conclusion : Théorique mais irréaliste (nécessiterait des yottabytes ($10^{24}$ bytes))

2. Recherche exhaustive (force brute) $(1, 1, 2^{55})$

def force_brute(message_clair, message_chiffre):
    for cle in range(2**56):
        if des_chiffrement(message_clair, cle) == message_chiffre:
            return cle
    return None

• Paires : 1 seul couple suffit
• Mémoire : Négligeable
• Temps : $2^{55}$ essais en moyenne (moitié de l’espace des clés)

En 2024 : $2^{55} \approx 36 000 000$ milliards d’opérations → réalisable avec du matériel dédié comme Deep Crack (2008) qui cassait DES en 6 jours.

3. Cryptanalyse linéaire $(2^{43}, 2^{43}, 2^{43})$

Découverte par Matsui en 1993, elle utilise des approximations linéaires du DES.

# Principe simplifié
def cryptanalyse_lineaire(message_clair, message_chiffre):
    # Étape 1 : Trouver une relation linéaire approchée
    # P[i1] ⊕ ... ⊕ P[ik] ⊕ C[j1] ⊕ ... ⊕ C[jl] = K[m]
    # avec probabilité ≠ 1/2
    # Étape 2 : Collecter 2^43 paires
    for paire in 2**43 paires:
        # Vérifier la relation
        # Accumuler des statistiques sur les bits de clé
    # Étape 3 : La clé qui apparaît le plus souvent est la bonne
    return cle_probable

• Principe : Trouver une approximation linéaire entre bits du clair, du chiffré et de la clé
• Données : $2^{43}$ textes clairs connus ($\approx 8 796$ milliards)
• Complexité : $2^{43}$ opérations (bien mieux que $2^{55}$)
  – Efficacité : Première attaque théoriquement plus rapide que la force brute

4. Cryptanalyse différentielle $(2^{47}, 2^{47}, 2^{47})$

Découverte par Biham et Shamir (années 1990), elle analyse la propagation de différences entre paires de textes.

# Principe simplifié
def cryptanalyse_differentielle():
    # Étape 1 : Choisir une différence ΔP pour les messages clairs
    ΔP = 0x00200000  # Exemple : différence sur un bit
    # Étape 2 : Collecter 2^47 paires (P, P⊕ΔP)
    paires = []
    for _ in range(2**47):
        P1 = random_message()
        P2 = P1 ⊕ ΔP
        C1 = des_chiffrement(P1)
        C2 = des_chiffrement(P2)
        paires.append((P1, P2, C1, C2))
    # Étape 3 : Analyser les différences ΔC = C1⊕C2
    # Certaines différences apparaissent avec des probabilités caractéristiques
    # Ces probabilités révèlent des informations sur la clé
    return cle-* 

• Principe : Observer comment une différence dans le clair se propage dans le chiffré
• Données : $2^{47}$ paires choisies (l’attaquant choisit les différences)
• Complexité : $2^{47}$ opérations

Remarque : Le DES a été spécifiquement conçu pour résister à cette attaque.

Pourquoi DES n’est plus sûr

Le tableau montre que :

• La force brute est devenue réalisable (machine à 250 000 $ en 1998)
• Les attaques cryptanalytiques réduisent théoriquement la complexité
• Mais surtout, la clé de 56 bits est trop courte :

Résultat : DES a été remplacé par AES (clés de 128-256 bits)

La machine à 250 000 $ de 1998 (la célèbre Deep Crack) mettait environ 56 heures pour trouver une clé DES.

Aujourd’hui, la donne a complètement changé, principalement grâce à l’optimisation matérielle pour le minage de Bitcoin. Le minage de Bitcoin utilise l’algorithme SHA-256, dont les opérations de base (rotations, décalages, XOR) sont très similaires à celles du chiffrement DES. Les ASICs (circuits intégrés spécifiques) conçus pour le minage sont donc extraordinairement efficaces pour ce type de calcul.

Le calcul pour aujourd’hui

L’espace des clés DES est de $2^{56}$ ($\approx 7.2\times10^{16}$ environ 72 quadrillions de clés). En moyenne, pour trouver la bonne clé, il faut en essayer la moitié, soit $2^{55} \approx 3.6\times10^{16}$ clés à tester.

Une ASIC moderne spécialisée dans le minage de Bitcoin (comme l’Antminer S19) peut atteindre environ $100×10^{12}$$hachages$SHA-256 par seconde. Mais le calcul pour DES est différent. Si on conçoit une ASIC spécifiquement optimisée pour DES, on peut estimer sa capacité.

Prenons une ASIC moderne dédiée au DES :

• Fréquence : 1 GHz (1 milliard d’opérations par seconde)
• Nombre de cœurs : 1000 cœurs par puce
• Nombre de puces : 100 puces par machine

Soit une capacité totale de : $$$10^9 \text{op/s} × 1000 × 100 = 10^{14}$ clés/seconde.
Le temps moyen pour casser DES est donc : $\dfrac{2^{55} \text{clés}}{10^{14} \text{clés/s}} ≈ 360 \text{secondes} ≈ 6 \text{minutes}$.

Comparaison :
– EFF Deep Crack (1998) : 88 milliards clés/s → environ 56 heures pour tester tout l’espace (soit 28 heures en moyenne)
– ASIC moderne : 100 000 milliards clés/s → environ 6 minutes en moyenne

Soit un gain de vitesse d’environ 280 fois par rapport au Deep Crack.

Le facteur coût : la vraie révolution

La véritable avancée réside dans le coût. En 1998, il fallait un budget de 250 000 $.

Aujourd’hui, avec le même budget (250 000 $), on pourrait acheter environ 90 ASICs (250 000 / 2 800). En les faisant travailler ensemble, le temps de cassage tomberait à seulement 4 secondes.

Message à retenir : Un algorithme de chiffrement doit résister à la fois à la puissance de calcul croissante (loi de Moore) et aux avancées de la cryptanalyse théorique. Le cas DES montre qu’une clé de 56 bits, considérée comme sûre dans les années 1970, est devenue vulnérable en 20 ans, et totalement obsolète aujourd’hui face aux capacités de calcul parallélisées à bas coût.

Dans le DES, certaines clés produisent des comportements cryptographiques anormaux car elles génèrent des sous-clés identiques ou présentant des symétries. On distingue quatre catégories.

1. Clés faibles (4 clés)

Une clé est dite faible lorsque les 16 sous-clés générées sont toutes identiques. Cela signifie que chiffrer deux fois avec la même clé ramène au message original : DESₖ(DESₖ(M)) = M.

Pourquoi ? Cela arrive quand les deux moitiés de la clé (C et D) sont composées uniquement de 0 ou uniquement de 1. Les décalages ne changent rien.

Les 4 clés faibles (en hexadécimal, avec bits de parité) sont :

Conséquence : Pour ces clés, le chiffrement est involutif (chiffrer deux fois déchiffre).

2. Clés semi-faibles (12 clés)

Des clés sont dites semi-faibles lorsqu’elles existent par paires : la clé K₁ génère les mêmes sous-clés qu’une autre clé K₂, mais dans l’ordre inverse. Ainsi : DESₖ₁(DESₖ₂(M)) = M.

Cela arrive quand les moitiés C et D produisent des séquences de sous-clés qui sont simplement inversées entre les deux clés.

Exemple de paire :

• K₁ = 0x01FE01FE01FE01FE
• K₂ = 0xFE01FE01FE01FE01

Conséquence : Ces clés créent une relation de dualité entre chiffrement et déchiffrement.

3. Clés possiblement faibles (48 clés)

Une catégorie intermédiaire où les sous-clés ne sont pas toutes identiques, mais se répètent avec une période courte (4 ou 2 sous-clés distinctes seulement au lieu de 16). Cela réduit la complexité effective du chiffrement.

4. Clés totalement faibles

Cas extrême : les clés pour lesquelles **chaque bit est identique** (tout 0 ou tout 1, mais avec les bits de parité corrects) :

• 0x0000000000000000 (théoriquement invalide à cause de la parité, mais conceptuellement)
• 0xFFFFFFFFFFFFFFFF

Avec ces clés, le DES devient complètement linéaire dans certaines configurations.

Pourquoi ces clés existent ?

La structure de génération des sous-clés par décalage est responsable :

• Si C et D sont constants (tout 0 ou tout 1), les décalages ne changent rien → clés faibles
• Si C et D ont des motifs symétriques, on obtient des paires de clés qui s’inversent → clés semi-faibles

Impact pratique

Bien que ces clés existent, leur nombre est infime par rapport à l’espace total des clés (seulement 64 clés concernées sur $2^{56} ≈ 7,2 × 10^{16}$). Le risque de les choisir aléatoirement est donc négligeable (environ $10^{-15}$).

Cependant, une implémentation sérieuse du DES doit détecter et rejeter ces clés, car leur utilisation compromet totalement la sécurité.