Discussion :

[Lcf.vs]

Bonjour à tous,

Il y a quelques jours, j'ai développé un algorithme de chiffrement symétrique, simpliste mais efficace, et je viens vous le présenter.

Le Pyramidal Encryption Standard est basé sur le principe des nombres pyramidaux.

Ses forces :

• Longueur de clef indéfinie * (plages à brute-forcer, de 0 à l'infini)
• Basé sur l'encodage de caractères (défini par l'utilisateur)
• Pas de dictionnaire
• Pas de marqueurs
• Longueur de la chaine chiffrée égale à celle de la chaîne de départ

Ses faiblesses :

• Gourmand en ressources, selon la longueur de la clef et de la chaîne à (dé)chiffrer

* Personnellement, je recommande longueur de la chaîne à chiffrer + 1 (par défaut), afin d'assurer, au minimum, un double écrasement de toutes les valeurs.

Le concept, par étapes :

Prenons donc un exemple de nombres.

Code :

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

1   2   3   4   5

Pour chaque rang, la valeur inscrite dans une colonne est augmentée de la valeur de inscrite, au rang précédent, dans la colonne précédente.

Code :

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

1
2
3
4
 
1   3   5   7   9
1   4   8  12  16
1   5  12  20  28

Appliquons cela à une chaîne de caractères :
C'est assez simple, dans un encodage défini, à tout caractère correspond une valeur numérique.

Pour cet exemple, tout comme pour la démo, j'ai choisi l'UTF-8, mais ce principe est applicable à n'importe quel encodage.

Prenons la chaine une chaîne anodine :

Code :

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

Texte

Convertissons-la en codes numériques :

Code :

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

84 101 120 116 101

Ensuite, appliquons le principe des nombre pyramidaux :

Code :

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

1
2
3
84 185 221 236 217
84 269 406 457 453
84 353 675 863 910

Afin de pouvoir représenter ces nombres sous forme de caractères (chaîne chiffrée), toute valeur au moins égale à au nombre de caractères défini par l'encodage se verra diminuée de ce nombre. Dans le cas de l'UTF-8, il y a 65536 caractères.

Donc, par exemple :

Code :

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

1
2
3
4
 
charCode=67536
si (charCode >= 65536)
alors charCode = charCode - 65536 // 2000

La clef :
Sans une clef, vous l'aurez remarqué, il est assez facile de prédire le message original. De plus, le premier caractère est toujours en clair.

Prenons donc une clef anodine :

Code :

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

mdp

Côté script, afin de renforcer le chiffrage, tant que la longueur de cette clef est inférieure à la longueur du message, nous allons concaténer cette clef à elle-même, dans le cas présent, cela donnera :

Code :

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

mdpmdp

Convertissons-la en codes numériques :

Code :

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

109 100 112 109 100 112

Introduction de la clef :
Pour chaque code de la clef, nous allons créer un rang à la suite de codes de notre chaîne à chiffrer, où nous allons additionner ce code à la valeur de la 1ère colonne de ce rang et y appliquer un XOR code de la clef.

Ce qui donne :

Code :

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

1
2
3
4
5
6
172  212  176  129  180
372  484  480  341  337
404  808  948  837  726
620 1233 1713 1684 1654
692 1881 3046 3361 3438
852 2685 4943 6519 6911

Au lieu de :

Code :

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

1
2
3
84 185 221 236 217
84 269 406 457 453
84 353 675 863 910

Et, reconverti en caractères (en UTF-8) :

Code :

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

͔੽ፏ᥷᫿

Voilà, qu'en pensez-vous?


N.B. : La démo étant en JavaScript, on est un peu limités au niveau de la récursivité, donc n'abusez pas trop sur vos longueurs de mot de passe/texte à (dé)chiffrer.

EDIT : Correction du bug lié à une clef trop courte (oubli d'un passage de paramètre)

Ajout d'un XOR placé de manière à empêcher l'altération des données.

[manticore]

Personnellement, je recommande longueur de la chaîne à chiffrer + 1 (par défaut), afin d'assurer, au minimum, un double écrasement de toutes les valeurs.

Si tu utilises une clé de la longueur + 1, tu es déjà sur un chiffrement parfait un simple xor te permet d'avoir un code "incassable" sans la clé.

Maintenant je suis pas expert dans la théorie des nombres, mais j'ai l'impression que l'on peut casser ton code en cherchant des caractères ascii, vu que tu encodes en utf-8, on sort rapidement de la plage ascii.

Donc un brute-force intelligent doit être capable de casser ton code en moins de 2^(n/2) (ou n est la longueur de la clé).

Les chiffrement symétrique repose généralement sur des problèmes NP-complet et je n'ai pas l'impression que le tiens en soit un.

Sinon il y a de la diffusion d'informations, donc on ne peut pas attaquer un "bout" sans modifier toute la suite du message mais on peut attaqué le dernier byte. Je m'explique :

Si tu as une transaction, il est possible de modifier le dernier octets sans modifier la suite du message donc si tu sais que le message est :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
Dette manticore 9999
 
Avec la clé : "Dette manticore 9999 Dette manticore 9999"
 
Je reçois :
 
ผ⪧룜ࡓ庶⺃瀳⫞㜉㕣옧晛䱐藶뾡엗俴⍋
 
Si je modifie le caractère ⍋ par le caractère précédent (et la j'ai la flemme de chercher)
 
Je vais pouvoir transformer en 9998.

Il me semble que cela suffit pour considérer que ton code est cassé théoriquement.

Sinon pour le brute-force il faudrait essayer, c'est qu'une supposition mais il me semble aussi que c'est faisable.

p.s. tout ceci n'est que des réflexions, j'ai pas fais de tests et il probable que je me trompe

[Lcf.vs]

Chouette, du feedback, merci...

Alors, bon, je suis loin d'être un expert non-plus, j'ai eu cette idée qui me semblait efficace et je l'ai développée, simplement.

Maintenant je suis pas expert dans la théorie des nombres, mais j'ai l'impression que l'on peut casser ton code en cherchant des caractères ascii, vu que tu encodes en utf-8, on sort rapidement de la plage ascii.

En fait, l'encodage étant défini par celui qui a chiffré la chaine, il faudrait déjà pouvoir le deviner. Chaque encodage pouvant avoir des valeurs différentes, pour un même caractère, cela complique déjà les choses.

Sinon il y a de la diffusion d'informations, donc on ne peut pas attaquer un "bout" sans modifier toute la suite du message mais on peut attaqué le dernier byte. ...

Comme chaque valeur chiffrée est le résultat d'une succession d'additions et puisque toute valeur supérieure à la longueur max de l'encodage choisi est diminuée de cette longueur, je ne vois pas comment tu peux déterminer :

1. combien de fois on a bouclé dessus
2. la valeur de chacun des caractères de la clef qui ont été ajoutés
3. ce qui tient de la clef et ce qui tient du message

Que ce soit pour le premier ou le dernier caractère du message chiffré.

A mon sens, au mieux, tu trouveras la correspondance pour ton message, avec ta clef... mais qui ne correspondra pas avec ceux d'un autre...

Mais, bon, je ne suis certain de sa force, hein... mais je serais ravi que des spécialistes l'éprouvent.

[manticore]

Comme chaque valeur chiffrée est le résultat d'une succession d'additions et puisque toute valeur supérieure à la longueur max de l'encodage choisi est diminuée de cette longueur, je ne vois pas comment tu peux déterminer :

combien de fois on a bouclé dessus
la valeur de chacun des caractères de la clef qui ont été ajoutés
ce qui tient de la clef et ce qui tient du message

Je loupe peut-être une étape, mais je vois rien qui empêche de modifier le dernier byte d'une valeur de 1 pour faire descendre la valeur chiffré de 1 (sauf dans certains cas avec le modulo).

La valeur de la clé est une addition donc -1 reste -1 sur le résultats.
Le nombre de boucle pareil que des additions.
Le nombre de boucle (c'est peut-être la que je me trompe), c'est bien le nombre de ligne ici :

1 3 5 7 9
1 4 8 11 16
1 5 12 19 27

Donc à nouveau que des additions. Si tu additionnes 100 à 9 ça me donne 109. Même sans savoir le processus si je met 108 tu déchiffreras un 8 non ?

[Lcf.vs]

Factorisons la chose (valeurs de la chaîne de départ : a b c, clef : k l m n) :

Code :

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

1
2
3
4
      a+k           a+b           b+c
    a+k+l        2a+k+b        a+2b+c
  a+k+l+m     3a+2k+l+b     3a+k+2b+c
a+k+l+m+n  4a+3k+2l+m+b  6a+3k+l+3b+c

Si tu fais 6a+3k+l+3b+c-1, tu vas en impacter toute la chaîne qui, à moins d'un énorme coup de bol, vu que tout est lié, va t'empêcher de tirer des conclusions sur la valeur de a, b, c, d, e, k, l, m et n

Donc, je ne comprends pas ce qu'apporte ton décalage de 1.

[manticore]

Alors j'ai fais un essai et j'arrive à modifier la dernière valeur juste en sachant qu'il s'agit un chiffre. Tu vas me dire et alors ?

C'est vrai que les implications pratiques sont peu élevé, mais ça suffit normalement en cryptographie pour dire que ton code n'est pas sûr.

Exemple avec ton calculateur online :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
String to encrypt :
je suis un test 999
 
Key length (default value -> string length + 1) :
12
 
Encrypted string (auto default value) :
֪∨耟仏謉�핼君駌↜⋋ꎧ筕瘃锲튥Ĝ
 
Encryption key :
test
 
Decrypted string :
je suis un test 999

La valeur de du dernier caractère est Ĝ, je prend le caractère précédent ĝ dans la table unicode. Et je remplace dans la chaîne chiffré :

Encrypted string (auto default value) :
֪∨耟仏謉�핼君駌↜⋋ꎧ筕瘃锲튥Ĝ

devient :
֪∨耟仏謉�핼君駌↜⋋ꎧ筕瘃锲튥ě

Et le décodage :
je suis un test 998

Après si j'avais plus de temps je relirai un peu mes cours de crypto, et je pense que l'on peut trouver d'autre problèmes. De mon point de vue, j'ai l'impression que tu devrais faire des xor à la place des additions.