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

icon 09/05/2012

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.

icon Tags de l'article :

7 commentaires

Identitools - 09/05/2012 à 15:15:26

Bonjour, je n'ai pas trouvé de formulaire de contact alors je vous contacte ici.

Ce n'est pas très gentil de supprimer les crédits sur le footer de la page d'accueil ;)
Enfin ce n'est rien je viens juste vous informer que vous utilisez une version périmée du thème je ne fais plus les mises à jour du thème via http://identitools.fr mais via cette page : http://ignorez-moi.fr/ressources/theme-blogoclean/

Bonne journée à vous.
Nicolas.

@répondre #lien

Sbgodin - 09/05/2012 à 16:17:34

Bonjour Nicolas,

J'ai laissé "publié avec BlogoText" sur le pied de page. Je ne sais plus pourquoi j'ai modifié cette partie-là. Je vais remettre tout ça.

J'ai personnalisé ce thème, je l'avais déjà corrigé depuis la dernière migration en suivant les directives publiées sur votre site. Voyez-vous des soucis avec le thème tel qu'il est actuellement ?

La page de contact est sur http://www.sbgodin.fr/

Merci pour le travail accompli :-)

@répondre #lien

Identitools - 09/05/2012 à 19:20:57

Le code à été ré-écrit (utilisation de css3 & html5) mise à jour pour les nouvelles versions de blogotext. Rien de bien critique mais c'est déjà ça :)

@répondre #lien

Lheureux - 10/05/2012 à 10:37:52

J'aurais plutôt tendance à penser que cet algo permet au contraire de faciliter l'échange de clé ( masque ) qui rendait impossible l'utilisation du chiffre de Vernam.
Certes , la clé , plus courte est attaquable par force brute mais elle bénéficie aussi d'avantages liés à l'utilisation des fonctions de Hachage.
A savoir : La moindre modification de caractère dans la clé change complètement le masque.Cela permet par exemple aux correspondants de changer de clé à chaque message en incrémentant la clé originelle.Ils peuvent aussi se transmettre facilement la clé de manière totalement invisible. Prendre par exemple comme clé la troisième lettre ( si elle existe ) des 20 premiers mots d'un message transmis lors de l'envoi du fichier crypté. ici cela donnerait :
aunnetgrncé .... Simplicité = efficacité.

@répondre #lien

Lheureux - 10/05/2012 à 10:53:40

Pour le transfert invisible d'une clé, on peut prendre par exemple la première et la dernière lettre des 20 premiers mots.

"Bonjour , je t'envoi un fichier crypté qui te donnera l'adresse de notre rendez-vous ainsi que mon numéro de téléphone.Je pense que nous allons bien nous entendre et que notre rencontre permettra de faire avancer les choses."


Donnera la clé :

Brjetiunfrcéqitedaledenersaiqemnnodeteje

qui va permettre d'initialiser le masque. Le changement de clé à chaque utilisation n'est donc absolument pas un problème.

@répondre #lien

Lheureux - 10/05/2012 à 18:26:17

Christophe ,
Je viens de remédier au problème de la clé qui générait un masque identique pour tous les fichiers chiffrés avec une même clé.Maintenant on peut utiliser la même clé avec HashMask pour crypter autant de fichiers que l'on souhaite sans aucun risque de pouvoir réutiliser un masque pour déchiffrer un autre fichier.
je t'invite à aller lire HashMask 512 en bas de la page http://www.superlutin.net/cec.html
Ton avis est le bienvenu ! Elle est ou la faiblesse maintenant ?
Dimitri est déja sur la version qui sera bientôt mise en ligne pour test.

@répondre #lien

Sbgodin - 10/05/2012 à 23:35:19

Estimé Philippe,

J'avais indiqué que la cryptanalyse prenait du temps. Mon temps à y consacrer est écoulé, mais c'était très instructif.

Cela dit, je pense que tes changements sont positifs, d'après ce que j'ai compris de ta description de l'algorithme.

@répondre #lien

icon Flux RSS des commentaires de cet article