Discussion :

[SkyBack]

Bonjour, je viens présenter un algo de cryptage de mon cru pour vous demander votre avis. Vous trouverez l'essentiel sur cette page : http://ashaku.free.fr/mudi.php c'est-à-dire un formulaire d'essai et un lien pour télécharger les sources du projet (PHP).

L'idée du truc, c'est de manipuler un objet quadri-dimensionnel : le tesseract. Le message clair est entré dans cet objet (un caractère par "case" du tesseract) puis on effectue des rotations sur lui, ce qui "mélange" les cases et donc les valeurs (imaginez un rubrik's cube). Il suffit de lire les cases du tesseract dans l'ordre pour obtenir le message chiffré.


Diagramme d'utilisation des classes pour chiffrer un message.

Le principal acteur du chiffrement est donc la fonction "permuter()" de l'objet "hypercube". Je ne développerais pas ici ce mécanisme pour plutôt me concentrer sur l'algo qui le met en œuvre. Que pensez-vous de cette méthode ? Vous semble-t-elle fiable ? Quelles failles évidentes m'ont échappé selon vous ?

Ce projet est toujours en développement chez moi. Même si j'ai débuggé une version stable, je bute toujours sur quelques problèmes :
- la méthode étant symétrique, il faut transmettre la clé. J'ai ajouté un module pour crypter cette dernière et l'insérer dans le message mais de manière assez naïve pour l'instant. De plus, ca nécessite que l'émetteur et le récepteur se soient mis d'accord sur le format de ce cryptage.
- le format de restitution du message chiffré : au début, je renvoyais une version texte de l'information mais -interface web oblige- certains caractères spéciaux provoquaient des erreurs lors du POST. Je renvoie donc maintenant les valeurs hexadécimales des caractères chiffrés.
- les caractères du message d'origine ne sont bien évidement pas utilisés directement. Avant de les insérer dans l'hypercube, je les convertit en hexa ou en binaire. Le premier permet de traiter de plus grandes chaines, le deuxième fournit un meilleur codage. Lequel utiliser ?
- pour pouvoir insérer un message dans un cube, il faut que celui-ci soit suffisamment grand (logique) je comble ensuite les cases restantes avec des valeurs aléatoires. Ce qui fait que plus la taille du message est éloignée d'une taille max pour un cube (1, 8, 27, ... ) plus le message chiffré contiendra de données parasites.
Le problème, c'est que l'inverse est vrai. Ainsi, la chaine "aaaaaaaa" ne sera quasiment pas modifiée par le chiffrement. En effet, je vais remplir un cube de "6" et de "1" (61 étant la représentation hexa du caractère "a") puis permuter tous ces "6" et ces "1" avant de relire le cube ... qui me restituera une série de "6" et de "1" :/

[Graffito]

la méthode étant symétrique, il faut transmettre la clé. J'ai ajouté un module pour crypter cette dernière et l'insérer dans le message mais de manière assez naïve pour l'instant. De plus, ca nécessite que l'émetteur et le récepteur se soient mis d'accord sur le format de ce cryptage.

C'est là le coeur du problème :

• comment crypter la clé ? Avec une autre clé (à crypter aussi) ?
• la clé déterminant un enchainement de permutations, il faut que ces permutations soient suffisament nombreuses pour ne pas pouvoir casser le cryptage avec de la force brute (ce qu'on peut théoriquement faire en décryptant avec toutes les clés possibles jusqu'à identifier quelque chose contenant des mots connus).

[SkyBack]

comment crypter la clé ? Avec une autre clé (à crypter aussi) ?

Je me suis posé la question ... ce serait un peu récursif
Pour crypter la clé, j'utilise la méthode de polybe (dans un cube au lieu d'un simple tableau) J'ai mis un § là-dessus dans la doc. Ca nécessite que l'émetteur et le récepteur se soit mis d'accord sur le positionnement des valeurs, soit qu'ils utilisent exactement le même cube de polybe pour chiffrer/déchiffrer.
Ce qui me gène le plus là dedans, c'est qu'avec plusieurs messages chiffrés, on peut facilement déduire que les premiers octets servent à décrire quelque chose et ne font pas partie des données chiffrées.

la clé déterminant un enchainement de permutations, il faut que ces permutations soient suffisamment nombreuses pour ne pas pouvoir casser le cryptage avec de la force brute (ce qu'on peut théoriquement faire en décryptant avec toutes les clés possibles jusqu'à identifier quelque chose contenant des mots connus).

Disons que, de part la structure de l'objet 4D et la façon de le permuter, cela peut produire toute sortes de données y compris du texte clair selon le hasard de permutation des valeurs dans l'hypercube (bon j'avoue la probabilité est très faible).

La vraie parade au brut force, c'est la volumétrie des combinaisons possibles sur 4 dimensions. Une permutation peut être décomposée en 4 paramètres :
- quel type de permutation ? par sommet ou par arête ?
- sur quel cube interne ? (8 possibilités parmi les cubes internes)
- sur quelle dimension/autour de quel axe ? w, x, y ou z ?
- de combien de cran ? 1, 2 ou 3 ? (à 4 on revient à la position d'origine)
soit 192 possibilités pour une seule permutation ! Tester toutes les possibilités de permutations entre elles serait exponentiellement gourmand en ressources. Perso, je me contente d'une seule permutation pour chiffrer le message (le rendre illisible). A 3 permutations, ca fait un ensemble de 7 millions de permutations possibles (192^3 si je ne m'abuse). On peut imaginer une clé à 12 éléments (12 permutations) ce ne serait pas long pour coder/décoder, et le cracker aurait alors 2 509 659 166 022 727 122 011 815 936 permutations à vérifier !! Donc, coté brut force, je suis pas trop inquiet

Ce qui m'inquiète plus, ce sont toutes les simplifications que l'on peut faire en amont grâce à la connaissance de la méthode : dans mon algo je fais toujours une permutation par arête à partir du cube ana, ce qui réduit les possibilités de clés différentes à seulement 12 valeurs possibles. Il faudrait que je me motive à coder la permutation par sommet et la rendre possible sur n'importe quel cube interne.

Pour une meilleure visualisation, je met un lien vers cette belle applet qui m'a beaucoup aidé à appréhender la permutation 4D :
http://www.superliminal.com/cube/applet.html

[Jimmy_]

Bonjour,

Il n'y a pas assez d'element pour voir si ta méthode de cryptage est fiable ou pas. Tous les algorithmes de cryptage on par essence un algorithme ouvert, tout le monde y a accès. Mais ton histoire de permutation à la rubik cube, ressemble a un shéma classique de substitution permutation comme AES par exemple.
Reste a voir si tu l'as conçu pour résister aux attaques les plus simples, as-tu par exemple un effet avalache sur tes sorties ? As-tu envisager de corriger les clés faibles avec une matrice ?

1) Il faut imaginer qu'un cryptanalyse ne va jamais attaquer un algorithme par la force brute. C'est justement ce qu'il veux eviter de faire
La première chose il va modifier légèrement les entrées, pour voir l'effet sur les sorties. Si tu n'as pas un effet avalanche suffisant tes sorties ne bougeront pas beaucoup et il sera possible de faire des déductions sur ta structure.

2) Le pire de tout est la présence de clé faible, par exemple : chiffrer deux fois de suite le même texte, produit le texte en clair.

Sinon pour faire transiter une clé on utilise un autre algorithme , mais asymétrique cette fois, comme RSA. La clé publique de RSA permet de faire transiter ta clé secrête avec plus de sécurité.


Bon courage, mais il faut savoir que les algorithmes de cryptage vraiement performant sont très très rares et nécéssite des années de recherches. Mais ton idée est sympa pour s'initier à la discipline.

[SkyBack]

Salut Jimmy

Bon courage, mais il faut savoir que les algorithmes de cryptage vraiement performant sont très très rares et nécéssite des années de recherches. Mais ton idée est sympa pour s'initier à la discipline.

Très bon résumé de la situation. Je n'y connais pas grand chose en cryptanalyse, j'ai juste eu une idée marrante et envie de la coder pour voir le résultat Une recherche sur le web m'a appris que personne n'avait essayé cette méthode, j'en ai donc déduit qu'elle devait avoir un gros défaut. Je fais appel aux connaisseurs pour m'aider à mettre le doigt dessus.

J'ai déjà l'intuition d'un problème de ressources nécessaires pour traiter de gros volumes de données (génération d'hypercubes énormes) mais qui pourrait être amélioré en optimisant le code. Pour l'instant, j'ai surtout fait un genre de simulateur en PHP (pas très performant, mais rapide à mettre en œuvre)
Quant à l'efficacité du chiffrement lui-même, j'avoue ne pas pouvoir me le représenter, je n'ai pas fait les maths. J'ai juste observé qu'une seule permutation permet de modifier presque toutes les données contenues dans le cube et ca me semble un bon critère.

Il n'y a pas assez d'élément pour voir si ta méthode de cryptage est fiable ou pas.

Que puis-je ajouter selon toi pour compléter ? Pour la description du principe, le plus simple est de visiter l'applet superliminal (http://www.superliminal.com/cube/applet.html), de s'imaginer que le message clair a été converti en binaire et que chaque bit a été inséré dans une case. Ensuite, tu cliques 2 ou 3 fois sur des cases au hasard et tu verras ce que fait l'algo.

Mais ton histoire de permutation à la rubik cube, ressemble a un shéma classique de substitution permutation comme AES par exemple.

Je n'ai pas vu beaucoup de similitude mais j'ai fait que consulter la page wikipedia. Dans mon cas, la façon dont les données sont modifiées dépend de la clé, qui est générée aléatoirement.

La première chose il va modifier légèrement les entrées, pour voir l'effet sur les sorties. Si tu n'as pas un effet avalanche suffisant tes sorties ne bougeront pas beaucoup et il sera possible de faire des déductions sur ta structure.

Super ! Est ce que quelqu'un qui s'y connait peut essayer ? Je vais m'y mettre mais, en non-connaisseur, un avis plus éclairé me serait utile. Comme ca, d'instinct, l'effet avalanche doit être quasi-nul en hexa mais plutôt bon en binaire (les deux sont possibles) Je vais faire des essais ce soir.

Le pire de tout est la présence de clé faible, par exemple : chiffrer deux fois de suite le même texte, produit le texte en clair.

J'avoue ne pas avoir bien compris. J'ai peur de faire exactement ca : pour déchiffrer, en fait, j'exécute exactement le même code que pour chiffrer à la seule différence que les permutations me sont dictées par la clé au lieu d'être "inventée" au fur et à mesure.

Bon, en tout cas, merci pour ces infos, je vais coder quelques fonctions de tests de qualité pour me rendre compte de ce fameux effet avalanche.

[Jimmy_]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

J'ai juste observé qu'une seule permutation permet de modifier presque toutes les données contenues dans le cube et ca me semble un bon critère.

Effectivement en théorie c'est le critère de base pour résister aux cryptanalyses courante.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Que puis-je ajouter selon toi pour compléter ?

Rien de plus il faut que l'algorithme soit ouvert, c'est la base, rien de caché.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

Dans mon cas, la façon dont les données sont modifiées dépend de la clé, qui est générée aléatoirement.

Ca pourrait être un point faible cette génération aléatoire, car rien n'est aléatoire en informatique c'est forcement une suite prédictible en fonction du vecteur d'initialisation.

Voir mon exemple de clé faible :
Si tu cryptes un texte M, tu obtiens un texte N, si tu recryptes avec la même clé N, il ne faut pas revenir sur M.

Ensuite un autre point est le padding (complèter les octets de fin) il ne doit pas laisser transparaitre la clé, pas de padding a zéro par exemple.

A mon avis cette représentation hypercube offre juste des possibilités de substitution/permutation différentes des matrices classiques. Mais au final cela revient au même. Mais je ne suis qu'un amateur en la matière.