TD Symmetric Ciphers

Exercice 1 : Mode ECB (Electronic Codebook)

Convention de la permutation

L'énoncé fournit une matrice de permutation p pour des vecteurs binaires de taille 4 : (4 3 2 1) (1 4 3 2) Cette notation indique que le bit initialement en position 4 va en position 1, le bit 3 va en position 4, le bit 2 va en position 3, et le bit 1 va en position 2. Il s'agit d'un décalage circulaire d'une position vers la droite. Pour un bloc d'entrée b1 b2 b3 b4, la permutation p donne : b4 b1 b2 b3. La permutation inverse (pour le déchiffrement) p⁻¹ effectue un décalage vers la gauche : le bloc c1 c2 c3 c4 devient c2 c3 c4 c1.

Question 1 - Description du fonctionnement ECB

Dans le mode ECB, le message clair est divisé en blocs de taille fixe. Chaque bloc clair P_i est chiffré indépendamment avec la même clé pour produire le bloc chiffré C_i. Mathématiquement : C_i = E(P_i) où E est la fonction de chiffrement (ici la permutation p). Pseudo-code : POUR chaque bloc P_i du message clair: C_i = p(P_i) FIN POUR

Question 2 - Décomposition et bourrage

Le message clair est m = 101100010100101. Sa longueur est de 15 bits. Les blocs doivent être de taille 4. Il faut ajouter un bit de bourrage (zéro) à la fin pour obtenir une taille multiple de 4 (16 bits). Message avec bourrage : 1011 0001 0100 1010 Décomposition : P1 = 1011 P2 = 0001 P3 = 0100 P4 = 1010

Question 3 - Application du chiffrement ECB

On applique la permutation p (décalage à droite d'un bit) sur chaque bloc : C1 = p(1011) = 1101 C2 = p(0001) = 1000 C3 = p(0100) = 0010 C4 = p(1010) = 0101

Question 4 - Ciphertext final

En concaténant les blocs C_i, le texte chiffré final est : C = 1101100000100101

Question 5 - Déchiffrement et vérification

On applique p⁻¹ (décalage à gauche d'un bit) sur chaque bloc chiffré : P1 = p⁻¹(1101) = 1011 (Correct) P2 = p⁻¹(1000) = 0001 (Correct) P3 = p⁻¹(0010) = 0100 (Correct) P4 = p⁻¹(0101) = 1010 (Correct) Le message original est bien retrouvé.

Question 6 - Propagation de la redondance

Si le message clair est composé des mêmes blocs (ex: 1010 1010), le chiffrement ECB donnera le même bloc chiffré pour chaque occurrence car C_i ne dépend que de P_i. p(1010) = 0101, donc le chiffré sera 0101 0101. Oui, la redondance est intégralement propagée dans le ciphertext.

Question 7 - Modification de l'ordre des blocs

Si l'ordre des blocs chiffrés est modifié, le décryptage de chaque bloc reste tout à fait possible et s'effectuera sans erreur locale. Cependant, les blocs en clair obtenus seront dans le désordre, ce qui altèrera la sémantique du message final.

Question 8 - Sécurité et applications appropriées

La sécurité de l'ECB est très faible pour des données structurées, car les motifs répétitifs du clair se retrouvent dans le chiffré (vulnérabilité à l'analyse statistique). Ce mode n'est approprié que pour chiffrer des données très courtes et totalement aléatoires (comme la transmission d'une clé cryptographique de petite taille) où aucune répétition n'est possible.

Exercice 2 : Mode CBC (Cipher Block Chaining)

Remarque préliminaire

La question 3 de cet exercice demande d'"Appliquer le mode ECB lors du chiffrement". Il s'agit d'une erreur typographique évidente dans l'énoncé de l'Exercice 2 consacré au CBC. La résolution appliquera logiquement le mode CBC.

Question 1 - Description du fonctionnement CBC

Dans le mode CBC, chaque bloc clair est combiné avec le bloc chiffré précédent via une opération XOR (⊕) avant d'être chiffré, introduisant ainsi une chaîne de dépendance. Mathématiquement : C_0 = IV (Vecteur d'Initialisation) C_i = E(P_i ⊕ C_i-1) Pseudo-code : C_prev = IV POUR chaque bloc P_i: C_i = p(P_i ⊕ C_prev) C_prev = C_i FIN POUR

Question 2 - Décomposition et bourrage

La méthode est identique à l'exercice 1. P1 = 1011 P2 = 0001 P3 = 0100 P4 = 1010

Question 3 - Application du chiffrement CBC

On donne IV = 1010.

• Bloc 1 : P1 ⊕ IV = 1011 ⊕ 1010 = 0001 C1 = p(0001) = 1000
• Bloc 2 : P2 ⊕ C1 = 0001 ⊕ 1000 = 1001 C2 = p(1001) = 1100
• Bloc 3 : P3 ⊕ C2 = 0100 ⊕ 1100 = 1000 C3 = p(1000) = 0100
• Bloc 4 : P4 ⊕ C3 = 1010 ⊕ 0100 = 1110 C4 = p(1110) = 0111

Question 4 - Ciphertext final

Le texte chiffré final est : C = 1000110001000111

Question 5 - Déchiffrement et vérification

La formule de déchiffrement est : P_i = p⁻¹(C_i) ⊕ C_i-1

• Bloc 1 : P1 = p⁻¹(1000) ⊕ 1010 = 0001 ⊕ 1010 = 1011 (Correct)
• Bloc 2 : P2 = p⁻¹(1100) ⊕ 1000 = 1001 ⊕ 1000 = 0001 (Correct)
• Bloc 3 : P3 = p⁻¹(0100) ⊕ 1100 = 1000 ⊕ 1100 = 0100 (Correct)
• Bloc 4 : P4 = p⁻¹(0111) ⊕ 0100 = 1110 ⊕ 0100 = 1010 (Correct)

Question 6 - Propagation de la redondance

Prenons un message formé de blocs identiques P1 = 1011 et P2 = 1011. C1 = p(1011 ⊕ 1010) = p(0001) = 1000 C2 = p(1011 ⊕ 1000) = p(0011) = 1001 Les blocs chiffrés C1 et C2 sont différents. La redondance du message clair n'est pas propagée, ce qui valide la solidité du mode CBC face à l'analyse de motifs.

Question 7 - Modification de l'ordre des blocs

Si l'ordre des blocs chiffrés est modifié, le décryptage échouera pour les blocs déplacés. Le déchiffrement d'un bloc C_i requiert impérativement la connaissance du bloc chiffré C_i-1 qui le précédait lors du chiffrement. Tout changement d'ordre désynchronise l'opération XOR et produit des blocs clairs corrompus.

Question 8 - Sécurité et applications appropriées

Le CBC offre un bon niveau de sécurité car il masque les redondances statistiques du message clair. Il est approprié pour le chiffrement de fichiers, de bases de données ou de flux de communications (ex: TLS/SSL historiques), à condition que l'IV soit imprévisible.

Question 9 - Propagation d'erreur

Si un bit est corrompu dans le premier bloc chiffré C1 :

• Le bloc clair P1 est totalement corrompu, car l'erreur affecte l'entrée de la fonction de déchiffrement p⁻¹.
• Le bloc clair P2 présentera exactement la même erreur d'un bit à la même position, en raison du XOR direct avec C1 lors du calcul : P2 = p⁻¹(C2) ⊕ C1.
• Les blocs P3 et suivants seront totalement intacts car ils ne dépendent que des blocs chiffrés C2, C3, etc., qui n'ont pas été altérés. La propagation d'erreur est donc limitée au bloc courant (totalement) et au bloc suivant (partiellement).

Question 10 - Application appropriée

Le CBC est particulièrement approprié pour les réseaux de transmission par paquets fiables ou le stockage de données sur disque, là où les pertes de blocs n'arrivent pas, car il résiste bien aux attaques statistiques tout en circonscrivant les erreurs de transmission occasionnelles.

Exercice 3 : Mode CFB (Cipher Feedback)

Configuration et initialisation

On a r = 3 et IV = 1010. Le plaintext est m = 101100010100101 (15 bits). Puisque r = 3, le découpage produit des blocs de 3 bits sans nécessiter de bourrage : P1=101, P2=100, P3=010, P4=100, P5=101. Le registre d'entrée initial est I_1 = IV = 1010.

Exécution du chiffrement

Pour chaque étape i, on chiffre I_i, on prend les r=3 bits de poids fort (gauche) que l'on nomme K_i, on calcule C_i = P_i ⊕ K_i. Ensuite, on met à jour I_i+1 en décalant I_i de r bits vers la gauche et en insérant C_i à droite.

• Étape 1 : I_1 = 1010 O_1 = p(1010) = 0101 K_1 = 010 C_1 = P1 ⊕ K_1 = 101 ⊕ 010 = 111 Mise à jour : décalage de 1010 (on garde le '0') et on ajoute 111 -> I_2 = 0111

• Étape 2 : I_2 = 0111 O_2 = p(0111) = 1011 K_2 = 101 C_2 = P2 ⊕ K_2 = 100 ⊕ 101 = 001 Mise à jour : décalage de 0111 (on garde le '0') et on ajoute 001 -> I_3 = 1001

• Étape 3 : I_3 = 1001 O_3 = p(1001) = 1100 K_3 = 110 C_3 = P3 ⊕ K_3 = 010 ⊕ 110 = 100 Mise à jour : décalage de 1001 (on garde le '1') et on ajoute 100 -> I_4 = 1100

• Étape 4 : I_4 = 1100 O_4 = p(1100) = 0110 K_4 = 011 C_4 = P4 ⊕ K_4 = 100 ⊕ 011 = 111 Mise à jour : décalage de 1100 (on garde le '0') et on ajoute 111 -> I_5 = 0111

• Étape 5 : I_5 = 0111 O_5 = p(0111) = 1011 K_5 = 101 C_5 = P5 ⊕ K_5 = 101 ⊕ 101 = 000

Le texte chiffré final est : C = 111 001 100 111 000.

Exercice 4 : Mode OFB (Output Feedback)

Exécution du chiffrement

Les conditions initiales sont les mêmes (r=3, IV=1010, découpage par 3 bits). Dans OFB, le registre est mis à jour non pas avec C_i, mais directement avec la sortie de la clé générée K_i.

• Étape 1 : I_1 = 1010 O_1 = p(1010) = 0101 K_1 = 010 C_1 = P1 ⊕ K_1 = 101 ⊕ 010 = 111 Mise à jour : décalage de 1010 et on insère K_1 -> I_2 = 0010

• Étape 2 : I_2 = 0010 O_2 = p(0010) = 0001 K_2 = 000 C_2 = P2 ⊕ K_2 = 100 ⊕ 000 = 100 Mise à jour : décalage de 0010 et on insère K_2 -> I_3 = 0000

• Étape 3 : I_3 = 0000 O_3 = p(0000) = 0000 K_3 = 000 C_3 = P3 ⊕ K_3 = 010 ⊕ 000 = 010 Mise à jour : I_4 = 0000

• Étape 4 : I_4 = 0000 O_4 = p(0000) = 0000 K_4 = 000 C_4 = P4 ⊕ K_4 = 100 ⊕ 000 = 100 Mise à jour : I_5 = 0000

• Étape 5 : I_5 = 0000 O_5 = p(0000) = 0000 K_5 = 000 C_5 = P5 ⊕ K_5 = 101 ⊕ 000 = 101

Le texte chiffré final est : C = 111 100 010 100 101.

Analyse demandée

• Propagation d'erreur : Contrairement au CFB, une erreur d'un bit dans la transmission de C_i affectera un et un seul bit lors du déchiffrement de P_i. Il n'y a aucune propagation d'erreur car le chiffré n'entre jamais dans la génération de la clé.
• Sécurité : L'exemple montre la vulnérabilité de la variante OFB avec r inférieur à la taille du bloc (OFB-r). Le registre tombe dans un cycle court (ici sur la valeur 0000), ce qui annule la sécurité (K_i devient une suite de zéros). Il ne faut jamais réutiliser le même IV.
• Rapidité : Le mode OFB est très rapide lors du traitement des données, car le flux de clés (K_1, K_2...) dépend uniquement de l'IV et peut être précalculé entièrement avant même l'arrivée du message clair.

Exercice 5 : Cryptographie Hybride et Protocoles

Question 1 - Méthode d'authentification

Pour prouver l'origine du broadcast, BeIN doit utiliser une signature numérique. BeIN calcule une empreinte (hash) de son message et la chiffre avec sa propre clé privée Kpr. Les abonnés déchiffreront cette signature avec la clé publique de BeIN pour vérifier l'intégrité et l'authenticité.

Question 2 - Clé pour l'authentification côté abonné

Pour authentifier le broadcast (vérifier la signature), l'abonné utilise la clé publique de BeIN (Kpu).

Question 3 - Méthode de chiffrement du broadcast

BeIN utilise la clé symétrique secrète Ks pour chiffrer le flux vidéo, car les algorithmes symétriques (comme AES) sont beaucoup plus rapides et adaptés aux flux massifs de données (broadcast). Les abonnés déchiffrent le flux en utilisant cette même clé symétrique Ks.

Question 4 - Correction du protocole d'échange de clé

Le protocole E(Ks, Kpr) est incorrect. Utiliser la clé privée pour chiffrer la nouvelle clé Ks n'apporte aucune confidentialité : n'importe qui possédant la clé publique Kpu (qui est par définition accessible à tous) pourra déchiffrer le message et récupérer la nouvelle clé Ks. La clé privée sert à authentifier (signer), pas à dissimuler un secret. Correction : BeIN devrait chiffrer la nouvelle clé Ks avec la clé publique de chaque abonné autorisé : E(Ks, Kpu_abonne). Dans le cadre d'un broadcast massif, BeIN utiliserait plutôt un système de clés hiérarchiques (une "Master Key" possédée uniquement par les terminaux à jour de paiement, qui sert à déchiffrer la nouvelle Ks).

Question 5 - Longueur minimale de la clé Ks

L'adversaire peut effectuer 2²⁰ essais par seconde. Pour résister 2 ans (2²⁶ secondes), la machine peut tester : 2²⁰ × 2²⁶ = 2⁴⁶ clés. En moyenne, une recherche exhaustive trouve la clé après avoir testé la moitié de l'espace des clés. Donc pour être sécurisé, la taille totale de l'espace (2^N) doit être strictement supérieure à 2 × 2⁴⁶ = 2⁴⁷. La longueur minimale N de la clé secrète doit donc être de 48 bits.

Exercice 6 : Recherche exhaustive de clefs symétriques

Formule de base

Le temps de recherche exhaustive T est proportionnel à l'espace des clés, défini par 2^N où N est le nombre de bits de la clé. Si T(56) = 4,5 jours, alors pour une clé de taille N : T(N) = T(56) × (2^N / 2⁵⁶) = 4,5 × 2^(N - 56) jours.

Cas d'une clé de 40 bits

N = 40. T(40) = 4,5 × 2^(40 - 56) = 4,5 × 2⁻¹⁶ jours. Sachant que 2¹⁶ = 65536 : T(40) = 4,5 / 65536 jours ≈ 0,00006866 jour. En convertissant en secondes (× 24 × 3600) : environ 5,93 secondes. La machine mettrait approximativement 6 secondes.

Cas du Triple-DES (112 bits)

N = 112. T(112) = 4,5 × 2^(112 - 56) = 4,5 × 2⁵⁶ jours. C'est un temps immense. 2⁵⁶ jours représentent environ 1,97 × 10¹⁴ années (près de 200 mille milliards d'années).

Cas de l'AES (256 bits)

N = 256. T(256) = 4,5 × 2^(256 - 56) = 4,5 × 2²⁰⁰ jours. C'est une durée inconcevable à l'échelle de l'univers, démontrant la robustesse absolue de l'AES-256 face à la force brute classique.

Méthode

Face à une épreuve d'architecture cryptographique ou de calcul de complexité :

• Ne devinez jamais la convention des matrices de permutation. Tracez un vecteur test (b1 b2 b3 b4) pour vérifier si la matrice décrit un décalage à droite ou à gauche, puis appliquez rigoureusement cette même règle en sens inverse pour le déchiffrement.
• Dans les modes opératoires comme CBC ou CFB, soyez extrêmement attentif aux opérations XOR. Une seule erreur de calcul binaire se propage aux étapes suivantes dans les schémas de chiffrement et ruine la note finale. Notez bien les états de registre intermédiaires (I_i, K_i) comme effectué plus haut pour faciliter la relecture.
• Concernant les questions d'infrastructures asymétriques (Exercice 5), rappelez-vous toujours la règle d'or : la clé publique chiffre les secrets vers le destinataire et valide les signatures, tandis que la clé privée signe les preuves d'identité et déchiffre les secrets reçus. Inverser ces rôles est l'erreur conceptuelle la plus lourdement pénalisée.