Christophe HENRY

Ce site ne comporte aucune information d’intérêt, sauf pour celui qui la cherche — Ĉi-retejo ne enhavas informon interesan, krom por iu kiu ĝin serĉas — This website doesn’t have any information of interest, except for who looks for it

Cryptanalyse de HashMask

09/05/2012 - 7 commentaires

Le chiffre de Vernam est démontré incassable, mais difficilement utilisable en pratique car il faut, entre autres, ne pas réutiliser la clé. L'algorithme HashMask est équivalent à un Vernam affaibli, où il ne faut pas réutiliser la clé mais qui est bien plus courte.

Analyse


La clé sert de générateur à une suite périodique et pseudo-aléatoire constituant le masque. Le masque est ensuite appliqué via un ou-exclusif.

chiffré = clair XOR masque(clé)

Comme nous le verrons plus bas, le masque est plutôt robuste. C'est sûrement très difficile d'entrer par cette porte blindée. Alors on entre par la fenêtre. À une clé donnée correspond un masque et un seul. Si on chiffre deux messages avec cette clé, nous obtenons ceci :

C1 = m1 XOR masque
C2 = m2 XOR masque

C'est la faiblesse fatale typique du Vernam, le masque jetable, dont il ne faut pas réutiliser la clé sous peine d'être vulnérable à l'attaque par mot probable. Pas la peine de chercher la clé, puisqu'il suffit d'extraire le masque. Cet algorithme est inutilisable en pratique, puisqu'il faut refaire une clé à chaque fois.

Cependant, poursuivons l'étude du masque. Le vrai chiffrement invulnérable, Vernam, est contraignant du fait de la taille de la clé, qui doit être au moins égale à celle du clair. Est-il possible de sacrifier un peu la sécurité au profit de plus de fonctionnalité, c'est-à-dire avec un simple mot de passe à transmettre ?

Dans la suite, nous supposerons que le mot de passe n'est pas vulnérable à une attaque par force brute.

Le masque


L'algorithme opère un ou-exclusif entre le clair et le masque. Chaque bit du masque est extrait du flot du masque. Il s'agit d'un chiffrement par flot.

Description


Le flot est composé de segments de 256 bits, générés au moyen de l'algorithme suivant :

SI vide(segment) ALORS segment = hash(clé)
segment = hash(segment+clé) // concaténation, "a"+"b"="ab"
ENVOI segment

descriptif Qui fournit les sorties suivantes, toutes de 256 bits :
1:
hash(hash(clé)+clé)
2:
hash(hash(hash(clé)+clé)+clé)
3:
hash(hash(hash(hash(clé)+clé)+clé)+clé)
4:
(...)

Ne pas utiliser
hash(clé)
comme premier segment généré permet de ne pas être vulnérable à une attaque par dictionnaire. La fonction de hachage (à sens unique) est SHA-256. La salage avec la clé empêche l'utilisation de tables arc-en-ciel. Cela correspond au mode d'opération Output Feedback, hash(clé) étant le vecteur d'initialisation.

Dès lors que le flot rencontre à nouveau le même segment, on a trouvé un cycle puisque chaque segment est toujours fonction du segment précédent, à clé fixée. Comme il y a un nombre limité de segments possibles (2^256 =~ 10^77), on tombe forcément sur un cycle. Un masque est donc composé d'une séquence de segment suivie d'un cycle de séquence de segment. Compte tenu de la méthode utilisée, je conjecture que la longueur des cycles est très grande et très probablement toujours plus grande que le clair. Si ce n'était pas suffisant, on pourrait utiliser d'autres algorithme de hachage tels que SHA-512...

Cela veut dire qu'en pratique, on extrait une suite imprévisible, qui pourrait faire l'affaire en tant que masque jetable mais seulement parmi un sous-ensemble des masques possibles, déterminés par l'espace des clés. Évidemment, il n'y a pas toutes les possibilités de masque comme pour le Vernam, et c'est pour ça que cet algorithme n'est pas inconditionnellement invulnérable, même si on n'utilise qu'une seule fois la clé. À supposer que la suite pseudo-aléatoire est robuste, et que la clé est choisie judicieusement, la sécurité semble intéressante. Une attaque classique nécessiterait un clair grand par rapport à un masque doté d'une période hypothétiquement très grande.

Attaques sur le masque


En fait, l'implémentation de référence stocke le nom de fichier à la fin du chiffré. Cela ouvre l'accès aux derniers bits du masque, ce mot probable permet de débuter la cryptanalyse. Cela a pour but, visiblement, de transmettre un fichier au nom générique, le vrai nom de fichier n'étant connu que lors du déchiffrement. On ignorera cette faille de sécurité car la fonctionnalité qu'elle apporterait est faible par rapport au risque pris.

Lors d'un chiffrement à clair connu, on retrouve facilement les segments. la connaissance d'un segment permet de caractériser très probablement la clé et de deviner si deux chiffrés utilisent la même clé. La connaissance de deux segments (consécutifs serait le mieux) ouvre une attaque par force brute sur la clé car l'un est toujours fonction de l'autre et de la clé. La connaissance de tous les segments utilisées pour un chiffré donné ne permet pas de déduire les segments suivants, du fait du salage avec la clé.

La période du masque est la plus courte distance entre deux segments identiques. La connaître est équivalent à connaître la clé. Et réciproquement.

Cryptanalyse


Problème posé


Soient C1, C2, C3 les trois chiffrés d'un clair c avec les clés k1, k2, et k3. De même, soient D1, D2, D3 les trois chiffrés d'un clair d avec les clés k1, k2 et k3. On sait que le texte de c est inclus dans d. Le texte original du problème est ici.

Étant connus c, C1, C2, C3, D1, D2, D3, trouver d. On ne connaît pas les clés k1, k2 et k3.

Preuve formelle de la résolution


On suppose que tous les fichiers font la même taille, et on a :

C1 = H(k1,c) et C2 = H(k2,c) et C3 = H(k3,c) avec H notre fonction de chiffrement.
D1 = H(k1,d) et D2 = H(k2,d) et D3 = H(k3,d)

On a vu précédemment qu'en général : X = H(clé,Y) = Y ⊕ masque(clé)

Avec M1, M2 et M3 les masques correspondants aux clés k1, k2 et k3 :

C1 = c ⊕ M1 et C2 = c ⊕ M2 et C3 = c ⊕ M3
D1 = d ⊕ M1 et D2 = d ⊕ M2 et D3 = d ⊕ M3.

Il vient que :
d = D1 ⊕ M1 ainsi que M1 = C1 ⊕ c
d = D2 ⊕ M2 ainsi que M2 = C2 ⊕ c
d = D3 ⊕ M3 ainsi que M3 = C3 ⊕ c

Et donc :
d = D1 ⊕ C1 ⊕ c
d = D2 ⊕ C2 ⊕ c
d = D3 ⊕ C3 ⊕ c

C1, C2, C3, D1, D2, D3 et c étant connus, on dispose de trois façons de retrouver le clair d.

Cette méthode ne peut pas décrypter au-delà de la longueur du clair c connu. Les informations concernant le clair d, situées au-delà de la longueur de c sont inaccessibles parce qu'on ne sait pas calculer le masque au-delà du clair.

Question ouvertes


Cet algorithme n'a rien inventé, RC4 est basé sur un principe similaire. Il a été cassé, mais en contexte de réutilisation de la clé.

Quelle est en moyenne la longueur du masque ?

Peut-on prédire les segments suivants à partir d'un segment connu ? De deux ? De trois ? etc.

Peut-on retrouver la clé à partir d'un segment ? De deux ? etc.

Quelle est la probabilité que deux clés soient dépendantes ? C'est-à-dire que l'une génère une séquence incluse dans l'autre.

Encore une fois, merci à Dimitri MESTDAGH, le développeur de l'implémentation de référence et à Philippe LHEUREUX, le concepteur de l'algorithme.

EDIT: code source ici.

Tags de l'article :

Cryptanalyse de l'algorithme CENAv03

22/04/2012 - 3 commentaires

J'ai cassé l'algorithme CENA en m'aidant de l'implémentation de référence. Le langage de programmation utilisé est Php. le code source en licence libre GPLv3+ est téléchargeable ici.

Je me suis contenté d'attaquer assez souvent un seul caractère. La technique est donc basique ici.

Dans la suite, il ne sera jamais question d'octet, mais toujours de caractère. Et pour conserver une relative simplicité, il sera fait mention de lettres clair et de lettres chiffrées. On ne considère que les lettres de l'alphabet. L'implémentation n'utilise jamais de dispositif aléatoire, mais simplement pseudo-aléatoire, mais cela n'a pas de conséquence pour la suite.

Descriptif de l'algorithme de chiffrement

descriptif
Chaque caractère est chiffré isolément en fonction d'une clé. La variante de chiffrement de chaque caractère est entièrement déterminé par sa position dans le clair. Chaque caractère clair aboutit à 17 caractères (de '0' à '9') chiffrés. Voici la succession de traitement que subit une lettre :

Vigenère fixé


Le caractère subit d'abord l'algorithme de Vigenère utilisant une clé fixée une fois pour toute. Le caractère de rang 0 (première position) n'est pas modifié, le deuxième est décalé de 1, le troisième de deux, etc.

Expansion


À chaque caractère, on associe un nombre de 6 chiffres pris dans un intervalle déterminé dans la clé. Tous les nombres de l'intervalle ramènent au même clair. Par exemple, A est transformé en un nombre entre 305126 et 308475. L'intervalle est fonction de la clé, et reste fixe pendant le chiffrement.
Le chiffré est passé de 1 caractères à 6 caractères.

Brouillage


Les 6 chiffres précédents sont mélangés dans 11 chiffres aléatoires. L'implémentation utilise une phase ajoutant 10 chiffres et une phase ajoutant 1 chiffre. Cela donne l'illusion que ça ajoute de la complexité parce que la clé est plus difficile à générer et à utiliser, mais en fait c'est tout à fait inutile. Le chiffré est passé maintenant de 6 caractères à 17 caractères.

Analyse de l'algorithme

énigma
Il est a clé de taille fixe, déterminer la longueur de la clé est donc utile. En fait, il suffirait de tester les longueurs de clé de 32 à 64 caractères, ce qui donne 33 possibilités. En fait, on peut faire plus simple !

L'algorithme chiffre caractère par caractère, on peut donc ne se focaliser que sur le premier caractère. Cette approche permet de s'affranchir du Vigenère fixé, car le Vigenère au rang zéro (première position) retourne exactement le caractère en entrée. Donc le Vigenère peut être ignoré.

L'expansion est le point faible de l'algorithme. Par construction, pour une position donnée (mais nous restons toujours au premier caractère) l'ensemble des valeurs attribuables à un caractère commence toujours par les mêmes deux premiers chiffres, le troisième variant assez peu. En reprenant l'exemple de la lettre 'A', les nombres qui lui sont associés vont de 305126 à 308475. Les trois premiers chiffres sont donc 305, 306, 307 et 308.

Le brouillage ajoute 7 chiffres aléatoires. C'est la partie la plus utile de l'algorithme et noye l'information dans un brouillard aléatoire.

Cryptanalyse

descriptif

Sans connaître l'algorithme, on analyse les rapports clairs/chiffrés. On constate que la taille des chiffrés est toujours égale à 17 fois celle du clair. En ne chiffrant qu'un seul caractère de façon répétitive, on s'aperçoit vite que 2 des dix-sept caractères ne varient pas, certains variant un peu plus et d'autres sont quasiment aléatoires. En chiffrant deux caractères identiques, on s'aperçoit que les chiffres non-aléatoires restent les mêmes mais que leur position à changé. À cette étape, on sait déjà que (à une clé donnée) la substitution ne dépend que du caractère et que la transposition ne dépend que de la position du caractère. La cryptanalyse ici consiste à retrouver une clé en soumettant à volonté des clairs. En fait, la vraie clé n'est retrouvée mais seulement une clé inverse. En poussant plus loin l'analyse, il serait possible de créer une clé et de chiffrer des messages.

Rangs utiles


Première étape, on détermine les rangs utiles. À une position donnée correspond une répartition donnée des caractères expansés. Par exemple, les rangs 11, 16 et 1 portent de l'information pour le première caractère chiffré. Les rangs 7, 1 et 13 correspondent au deuxième caractère chiffré. Je demande de très nombreuses fois le chiffrement de certains caractères, un à la fois. Cela fournit le spectre associé à la position : pour chaque rang (de 0 à 16) on détermine la probabilité d'occurrence des chiffres. Dans la pratique, on ne conserve que les 3 meilleurs rangs. Dans un caractère chiffré, on est donc capable de connaître les bons caractères parmis les 17.

Dictionnaire


Deuxième étape, on demande un grand nombre de fois le chiffrement de tous les caractères, toujours un à la fois. Les 17 chiffres sont filtrés grâce aux rangs utiles collectés à la première étape, dans la pratique, 3. Grâce au grand nombre d'essais, j'en arrive à déterminer toutes les combinaisons possibles de 3 chiffres. Concrètement, cela revient à déterminer les trois premiers chiffres correspondant à chaque lettre. Par exemple l'expansion de la lettre 'A' est l'ensemble des nombres entre 305126 et 308475 inclus. Le "3" et le "0" apparaissent toujours à la même position dans les chiffrés tandis qu'une position ne contient que "5,"6","7" ou "8". Ce faisant, on récolte pour chaque lettre en clair ces trois nombres caractérisant son expansion. En fait, il existe des cas où il y a ambiguïté. Ces cas ouvrent la voie à l'analyse fréquentielle pour les éliminer, mais qui ne sera pas traitée ici.

Clé inverse


Troisième étape, calcul de la clé inverse. Elle porte toujours sur un seul et premier caractère, ce qui élimine le vigenère du début. En combinant les deux étapes précédentes, on détermine quels 3 chiffres on doit lire parmi les 17 et quelle est la (parfois les) lettre en clair liée à ces 3 chiffres.

Le déchiffrement au moyen de la clé inverse se déroule comme suit :
  • On ne conserve que les trois chiffres utiles.
  • On regarde à quel caractère correspond ces trois chiffres utiles.

Comment améliorer la cryptanalyse ?


Elle ne porte que sur un caractère, ce qui oblige à faire des milliers de requêtes de chiffrement de un caractère. On peut chiffrer un seul gros fichier contenant toutes les lettres par paquets de quelques milliers. Le débrouillage est réalisé en testant les 33 hypothèses de longueur de la clé. Avec la bonne longueur du clé, la prééminence des 3 chiffres apparaît.

L'analyse fréquentielle peut, sous réserve d'avoir un clair et un chiffré de longueur suffisante, lever les dernières ambiguïtés et permettre de reconstituer la clé d'origine.

Et la longueur de la clé ?


La phase de cryptanalyse n'a pas vraiment besoin de la longueur de la clé. En fait, il faut la déterminer seulement s'il faudra déchiffrer des messages de longueur supérieure et pour généraliser le déchiffrement. La longueur de la clé est tout de même calculée pendant la cryptanalyse. Pendant le débrouillage, on reboucle sur la clé lorsqu'on retrouve les mêmes positions caractéristiques.

Comment améliorer l'algorithme ?

descriptif
Injection de l'intru : la phase d'injection de l'intru est inutile car elle est équivalente à rajouter un caractère de brouillage. À supprimer.

Brouillage : le brouillage lui-même peut être contourné par une analyse fréquentielle. En effet, le brouillage est aléatoire, contrairement aux informations entrées en clair.

Expansion : elle a grandement permis de casser l'algorithme. En fait, on peut l'améliorer comme suit. L'algorithme partitionne un intervalle de nombres en associant à chaque intervalle une lettre. Par exemple, si on sait que 305126 et 308475 désigne la lettre 'A', alors on sait que tous les nombres entre les deux désignent aussi 'A'.
Pour faire mieux, on pourrait associer à chaque nombre de l'intervalle une lettre de sorte à ce que chaque lettre soit associée à la même quantité de nombre, mais qu'il n'est pas possible de prévoir à quelle lettre est associée un nombre. Par contre, il faudra utiliser une clé de 899999 caractères pour l'expansion... Cela éviterait de pouvoir extraire les 3 chiffres caractéristiques d'une lettre.

Comment faire mieux que l'algorithme ?


Utiliser un vigenère a clé fixée n'est d'aucune utilité et n'a pas freiné la cryptanalyse, autant l'abandonner. Le brouillage ralentit la cryptanalyse, mais n'est pas efficace, donc autant l'abandonner aussi. L'expansion est une fausse bonne idée, et il serait plus efficace de faire un simple vigenère. Par exemple, on pourrait générer une clé infinie au moyen d'un tirage aléatoire provenant d'une suite déterminée par la clé. Par exemple, fixer le sel de la clé (srand() en Php) permet de faire autant de tirages pseudo-aléatoires que voulu... Évidemment, mais si c'est plus efficace, cela reste faible.

En gros, il serait plus efficace de faire du Vigenère au moyen d'une clé pseudo-aléatoire. Mais même comme ça, ce n'est pas gagné contre les techniques d'aujourd'hui.

Merci à Dimitri MESTDAGH, le développeur de l'implémentation de référence et à Philippe LHEUREUX, le concepteur de l'algorithme.

Références



Le code source est disponible ici.

Tags de l'article :

Cryptanalyse de HashMask

09/05/2012 - 7 commentaires

Le chiffre de Vernam est démontré incassable, mais difficilement utilisable en pratique car il faut, entre autres, ne pas réutiliser la clé. L'algorithme HashMask est équivalent à un Vernam affaibli, où il ne faut pas réutiliser la clé mais qui est bien plus courte.

Analyse


La clé sert de générateur à une suite périodique et pseudo-aléatoire constituant le masque. Le masque est ensuite appliqué via un ou-exclusif.

chiffré = clair XOR masque(clé)

Comme nous le verrons plus bas, le masque est plutôt robuste. C'est sûrement très difficile d'entrer par cette porte blindée. Alors on entre par la fenêtre. À une clé donnée correspond un masque et un seul. Si on chiffre deux messages avec cette clé, nous obtenons ceci :

C1 = m1 XOR masque
C2 = m2 XOR masque

C'est la faiblesse fatale typique du Vernam, le masque jetable, dont il ne faut pas réutiliser la clé sous peine d'être vulnérable à l'attaque par mot probable. Pas la peine de chercher la clé, puisqu'il suffit d'extraire le masque. Cet algorithme est inutilisable en pratique, puisqu'il faut refaire une clé à chaque fois.

Cependant, poursuivons l'étude du masque. Le vrai chiffrement invulnérable, Vernam, est contraignant du fait de la taille de la clé, qui doit être au moins égale à celle du clair. Est-il possible de sacrifier un peu la sécurité au profit de plus de fonctionnalité, c'est-à-dire avec un simple mot de passe à transmettre ?

Dans la suite, nous supposerons que le mot de passe n'est pas vulnérable à une attaque par force brute.

Le masque


L'algorithme opère un ou-exclusif entre le clair et le masque. Chaque bit du masque est extrait du flot du masque. Il s'agit d'un chiffrement par flot.

Description


Le flot est composé de segments de 256 bits, générés au moyen de l'algorithme suivant :

SI vide(segment) ALORS segment = hash(clé)
segment = hash(segment+clé) // concaténation, "a"+"b"="ab"
ENVOI segment

descriptif Qui fournit les sorties suivantes, toutes de 256 bits :
1:
hash(hash(clé)+clé)
2:
hash(hash(hash(clé)+clé)+clé)
3:
hash(hash(hash(hash(clé)+clé)+clé)+clé)
4:
(...)

Ne pas utiliser
hash(clé)
comme premier segment généré permet de ne pas être vulnérable à une attaque par dictionnaire. La fonction de hachage (à sens unique) est SHA-256. La salage avec la clé empêche l'utilisation de tables arc-en-ciel. Cela correspond au mode d'opération Output Feedback, hash(clé) étant le vecteur d'initialisation.

Dès lors que le flot rencontre à nouveau le même segment, on a trouvé un cycle puisque chaque segment est toujours fonction du segment précédent, à clé fixée. Comme il y a un nombre limité de segments possibles (2^256 =~ 10^77), on tombe forcément sur un cycle. Un masque est donc composé d'une séquence de segment suivie d'un cycle de séquence de segment. Compte tenu de la méthode utilisée, je conjecture que la longueur des cycles est très grande et très probablement toujours plus grande que le clair. Si ce n'était pas suffisant, on pourrait utiliser d'autres algorithme de hachage tels que SHA-512...

Cela veut dire qu'en pratique, on extrait une suite imprévisible, qui pourrait faire l'affaire en tant que masque jetable mais seulement parmi un sous-ensemble des masques possibles, déterminés par l'espace des clés. Évidemment, il n'y a pas toutes les possibilités de masque comme pour le Vernam, et c'est pour ça que cet algorithme n'est pas inconditionnellement invulnérable, même si on n'utilise qu'une seule fois la clé. À supposer que la suite pseudo-aléatoire est robuste, et que la clé est choisie judicieusement, la sécurité semble intéressante. Une attaque classique nécessiterait un clair grand par rapport à un masque doté d'une période hypothétiquement très grande.

Attaques sur le masque


En fait, l'implémentation de référence stocke le nom de fichier à la fin du chiffré. Cela ouvre l'accès aux derniers bits du masque, ce mot probable permet de débuter la cryptanalyse. Cela a pour but, visiblement, de transmettre un fichier au nom générique, le vrai nom de fichier n'étant connu que lors du déchiffrement. On ignorera cette faille de sécurité car la fonctionnalité qu'elle apporterait est faible par rapport au risque pris.

Lors d'un chiffrement à clair connu, on retrouve facilement les segments. la connaissance d'un segment permet de caractériser très probablement la clé et de deviner si deux chiffrés utilisent la même clé. La connaissance de deux segments (consécutifs serait le mieux) ouvre une attaque par force brute sur la clé car l'un est toujours fonction de l'autre et de la clé. La connaissance de tous les segments utilisées pour un chiffré donné ne permet pas de déduire les segments suivants, du fait du salage avec la clé.

La période du masque est la plus courte distance entre deux segments identiques. La connaître est équivalent à connaître la clé. Et réciproquement.

Cryptanalyse


Problème posé


Soient C1, C2, C3 les trois chiffrés d'un clair c avec les clés k1, k2, et k3. De même, soient D1, D2, D3 les trois chiffrés d'un clair d avec les clés k1, k2 et k3. On sait que le texte de c est inclus dans d. Le texte original du problème est ici.

Étant connus c, C1, C2, C3, D1, D2, D3, trouver d. On ne connaît pas les clés k1, k2 et k3.

Preuve formelle de la résolution


On suppose que tous les fichiers font la même taille, et on a :

C1 = H(k1,c) et C2 = H(k2,c) et C3 = H(k3,c) avec H notre fonction de chiffrement.
D1 = H(k1,d) et D2 = H(k2,d) et D3 = H(k3,d)

On a vu précédemment qu'en général : X = H(clé,Y) = Y ⊕ masque(clé)

Avec M1, M2 et M3 les masques correspondants aux clés k1, k2 et k3 :

C1 = c ⊕ M1 et C2 = c ⊕ M2 et C3 = c ⊕ M3
D1 = d ⊕ M1 et D2 = d ⊕ M2 et D3 = d ⊕ M3.

Il vient que :
d = D1 ⊕ M1 ainsi que M1 = C1 ⊕ c
d = D2 ⊕ M2 ainsi que M2 = C2 ⊕ c
d = D3 ⊕ M3 ainsi que M3 = C3 ⊕ c

Et donc :
d = D1 ⊕ C1 ⊕ c
d = D2 ⊕ C2 ⊕ c
d = D3 ⊕ C3 ⊕ c

C1, C2, C3, D1, D2, D3 et c étant connus, on dispose de trois façons de retrouver le clair d.

Cette méthode ne peut pas décrypter au-delà de la longueur du clair c connu. Les informations concernant le clair d, situées au-delà de la longueur de c sont inaccessibles parce qu'on ne sait pas calculer le masque au-delà du clair.

Question ouvertes


Cet algorithme n'a rien inventé, RC4 est basé sur un principe similaire. Il a été cassé, mais en contexte de réutilisation de la clé.

Quelle est en moyenne la longueur du masque ?

Peut-on prédire les segments suivants à partir d'un segment connu ? De deux ? De trois ? etc.

Peut-on retrouver la clé à partir d'un segment ? De deux ? etc.

Quelle est la probabilité que deux clés soient dépendantes ? C'est-à-dire que l'une génère une séquence incluse dans l'autre.

Encore une fois, merci à Dimitri MESTDAGH, le développeur de l'implémentation de référence et à Philippe LHEUREUX, le concepteur de l'algorithme.

EDIT: code source ici.

Tags de l'article :

Cryptanalyse de l'algorithme CENAv03

22/04/2012 - 3 commentaires

J'ai cassé l'algorithme CENA en m'aidant de l'implémentation de référence. Le langage de programmation utilisé est Php. le code source en licence libre GPLv3+ est téléchargeable ici.

Je me suis contenté d'attaquer assez souvent un seul caractère. La technique est donc basique ici.

Dans la suite, il ne sera jamais question d'octet, mais toujours de caractère. Et pour conserver une relative simplicité, il sera fait mention de lettres clair et de lettres chiffrées. On ne considère que les lettres de l'alphabet. L'implémentation n'utilise jamais de dispositif aléatoire, mais simplement pseudo-aléatoire, mais cela n'a pas de conséquence pour la suite.

Descriptif de l'algorithme de chiffrement

descriptif
Chaque caractère est chiffré isolément en fonction d'une clé. La variante de chiffrement de chaque caractère est entièrement déterminé par sa position dans le clair. Chaque caractère clair aboutit à 17 caractères (de '0' à '9') chiffrés. Voici la succession de traitement que subit une lettre :

Vigenère fixé


Le caractère subit d'abord l'algorithme de Vigenère utilisant une clé fixée une fois pour toute. Le caractère de rang 0 (première position) n'est pas modifié, le deuxième est décalé de 1, le troisième de deux, etc.

Expansion


À chaque caractère, on associe un nombre de 6 chiffres pris dans un intervalle déterminé dans la clé. Tous les nombres de l'intervalle ramènent au même clair. Par exemple, A est transformé en un nombre entre 305126 et 308475. L'intervalle est fonction de la clé, et reste fixe pendant le chiffrement.
Le chiffré est passé de 1 caractères à 6 caractères.

Brouillage


Les 6 chiffres précédents sont mélangés dans 11 chiffres aléatoires. L'implémentation utilise une phase ajoutant 10 chiffres et une phase ajoutant 1 chiffre. Cela donne l'illusion que ça ajoute de la complexité parce que la clé est plus difficile à générer et à utiliser, mais en fait c'est tout à fait inutile. Le chiffré est passé maintenant de 6 caractères à 17 caractères.

Analyse de l'algorithme

énigma
Il est a clé de taille fixe, déterminer la longueur de la clé est donc utile. En fait, il suffirait de tester les longueurs de clé de 32 à 64 caractères, ce qui donne 33 possibilités. En fait, on peut faire plus simple !

L'algorithme chiffre caractère par caractère, on peut donc ne se focaliser que sur le premier caractère. Cette approche permet de s'affranchir du Vigenère fixé, car le Vigenère au rang zéro (première position) retourne exactement le caractère en entrée. Donc le Vigenère peut être ignoré.

L'expansion est le point faible de l'algorithme. Par construction, pour une position donnée (mais nous restons toujours au premier caractère) l'ensemble des valeurs attribuables à un caractère commence toujours par les mêmes deux premiers chiffres, le troisième variant assez peu. En reprenant l'exemple de la lettre 'A', les nombres qui lui sont associés vont de 305126 à 308475. Les trois premiers chiffres sont donc 305, 306, 307 et 308.

Le brouillage ajoute 7 chiffres aléatoires. C'est la partie la plus utile de l'algorithme et noye l'information dans un brouillard aléatoire.

Cryptanalyse

descriptif

Sans connaître l'algorithme, on analyse les rapports clairs/chiffrés. On constate que la taille des chiffrés est toujours égale à 17 fois celle du clair. En ne chiffrant qu'un seul caractère de façon répétitive, on s'aperçoit vite que 2 des dix-sept caractères ne varient pas, certains variant un peu plus et d'autres sont quasiment aléatoires. En chiffrant deux caractères identiques, on s'aperçoit que les chiffres non-aléatoires restent les mêmes mais que leur position à changé. À cette étape, on sait déjà que (à une clé donnée) la substitution ne dépend que du caractère et que la transposition ne dépend que de la position du caractère. La cryptanalyse ici consiste à retrouver une clé en soumettant à volonté des clairs. En fait, la vraie clé n'est retrouvée mais seulement une clé inverse. En poussant plus loin l'analyse, il serait possible de créer une clé et de chiffrer des messages.

Rangs utiles


Première étape, on détermine les rangs utiles. À une position donnée correspond une répartition donnée des caractères expansés. Par exemple, les rangs 11, 16 et 1 portent de l'information pour le première caractère chiffré. Les rangs 7, 1 et 13 correspondent au deuxième caractère chiffré. Je demande de très nombreuses fois le chiffrement de certains caractères, un à la fois. Cela fournit le spectre associé à la position : pour chaque rang (de 0 à 16) on détermine la probabilité d'occurrence des chiffres. Dans la pratique, on ne conserve que les 3 meilleurs rangs. Dans un caractère chiffré, on est donc capable de connaître les bons caractères parmis les 17.

Dictionnaire


Deuxième étape, on demande un grand nombre de fois le chiffrement de tous les caractères, toujours un à la fois. Les 17 chiffres sont filtrés grâce aux rangs utiles collectés à la première étape, dans la pratique, 3. Grâce au grand nombre d'essais, j'en arrive à déterminer toutes les combinaisons possibles de 3 chiffres. Concrètement, cela revient à déterminer les trois premiers chiffres correspondant à chaque lettre. Par exemple l'expansion de la lettre 'A' est l'ensemble des nombres entre 305126 et 308475 inclus. Le "3" et le "0" apparaissent toujours à la même position dans les chiffrés tandis qu'une position ne contient que "5,"6","7" ou "8". Ce faisant, on récolte pour chaque lettre en clair ces trois nombres caractérisant son expansion. En fait, il existe des cas où il y a ambiguïté. Ces cas ouvrent la voie à l'analyse fréquentielle pour les éliminer, mais qui ne sera pas traitée ici.

Clé inverse


Troisième étape, calcul de la clé inverse. Elle porte toujours sur un seul et premier caractère, ce qui élimine le vigenère du début. En combinant les deux étapes précédentes, on détermine quels 3 chiffres on doit lire parmi les 17 et quelle est la (parfois les) lettre en clair liée à ces 3 chiffres.

Le déchiffrement au moyen de la clé inverse se déroule comme suit :
  • On ne conserve que les trois chiffres utiles.
  • On regarde à quel caractère correspond ces trois chiffres utiles.

Comment améliorer la cryptanalyse ?


Elle ne porte que sur un caractère, ce qui oblige à faire des milliers de requêtes de chiffrement de un caractère. On peut chiffrer un seul gros fichier contenant toutes les lettres par paquets de quelques milliers. Le débrouillage est réalisé en testant les 33 hypothèses de longueur de la clé. Avec la bonne longueur du clé, la prééminence des 3 chiffres apparaît.

L'analyse fréquentielle peut, sous réserve d'avoir un clair et un chiffré de longueur suffisante, lever les dernières ambiguïtés et permettre de reconstituer la clé d'origine.

Et la longueur de la clé ?


La phase de cryptanalyse n'a pas vraiment besoin de la longueur de la clé. En fait, il faut la déterminer seulement s'il faudra déchiffrer des messages de longueur supérieure et pour généraliser le déchiffrement. La longueur de la clé est tout de même calculée pendant la cryptanalyse. Pendant le débrouillage, on reboucle sur la clé lorsqu'on retrouve les mêmes positions caractéristiques.

Comment améliorer l'algorithme ?

descriptif
Injection de l'intru : la phase d'injection de l'intru est inutile car elle est équivalente à rajouter un caractère de brouillage. À supprimer.

Brouillage : le brouillage lui-même peut être contourné par une analyse fréquentielle. En effet, le brouillage est aléatoire, contrairement aux informations entrées en clair.

Expansion : elle a grandement permis de casser l'algorithme. En fait, on peut l'améliorer comme suit. L'algorithme partitionne un intervalle de nombres en associant à chaque intervalle une lettre. Par exemple, si on sait que 305126 et 308475 désigne la lettre 'A', alors on sait que tous les nombres entre les deux désignent aussi 'A'.
Pour faire mieux, on pourrait associer à chaque nombre de l'intervalle une lettre de sorte à ce que chaque lettre soit associée à la même quantité de nombre, mais qu'il n'est pas possible de prévoir à quelle lettre est associée un nombre. Par contre, il faudra utiliser une clé de 899999 caractères pour l'expansion... Cela éviterait de pouvoir extraire les 3 chiffres caractéristiques d'une lettre.

Comment faire mieux que l'algorithme ?


Utiliser un vigenère a clé fixée n'est d'aucune utilité et n'a pas freiné la cryptanalyse, autant l'abandonner. Le brouillage ralentit la cryptanalyse, mais n'est pas efficace, donc autant l'abandonner aussi. L'expansion est une fausse bonne idée, et il serait plus efficace de faire un simple vigenère. Par exemple, on pourrait générer une clé infinie au moyen d'un tirage aléatoire provenant d'une suite déterminée par la clé. Par exemple, fixer le sel de la clé (srand() en Php) permet de faire autant de tirages pseudo-aléatoires que voulu... Évidemment, mais si c'est plus efficace, cela reste faible.

En gros, il serait plus efficace de faire du Vigenère au moyen d'une clé pseudo-aléatoire. Mais même comme ça, ce n'est pas gagné contre les techniques d'aujourd'hui.

Merci à Dimitri MESTDAGH, le développeur de l'implémentation de référence et à Philippe LHEUREUX, le concepteur de l'algorithme.

Références



Le code source est disponible ici.

Tags de l'article :