PES : Pyramidal Encryption Standard

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:

---

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:

---

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:

---

Texte

---

Convertissons-la en codes numériques :

Code:

---

84 101 120 116 101

---

Ensuite, appliquons le principe des nombre pyramidaux :

Code:

---

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:

---

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:

---

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:

---

mdpmdp

---

Convertissons-la en codes numériques :

Code:

---

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:

---

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:

---

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:

---

͔੽ፏ᥷᫿

---

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.

Citation:

---

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:

---

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 ;)

Chouette, du feedback, merci... :P

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.

Citation:

---

Envoyé par manticore

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.

Citation:

---

Envoyé par manticore

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. ;)

Citation:

---

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 :

Citation:

---

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 ?

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

Code:

---

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.

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:

---

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é :

Citation:

---

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.

Si je comprends bien ton raisonnement...

Tu modifies la chaîne chiffrée pour déterminer une plage ascii, afin de restreindre le champs de recherche...

Mais, c'est en connaissant la clef! Sans, en quoi cela restreint-il quoi que ce soit?

Je ne connais pas la clé.

je sais juste que si je modifie le dernier octet chiffré de 1, sa valeur descend de 1 sauf à de très rare cas.

Je n'ai besoin que du texte chiffré pour manipuler un octet. C'est un problème majeur si il s'agit par exemple d'un compte bancaire non ?

Sans être spécialiste de cryptographie mais juste un amateur je suis capable de trouver quelque chose de manipulable avec une grande probabilité. Je pense vraiment que l'addition n'est pas adapté au chiffrement. Il te faut faire du xor, c'est plus efficace ;)

[EDIT]
J'ajouterai que ton code n'est pas résistant, car il s'agit d'une simple transposition, à l'aide d'une clé, comme un vigénère :

http://fr.wikipedia.org/wiki/Cryptan..._Vigen%C3%A8re

Avec une analyse de la longueur de la clé avec la méthode de kasiski :
http://www.bibmath.net/crypto/poly/viganalyse.php3

Et ensuite c'est presque gagné.

Et si tu utilises une clé de la même longueur que le message il te suffit d'un xor pour avoir un code indéchiffrable.
[/EDIT]

Ah, je comprends mieux...

Le but n'est pas de déchiffrer le message mais juste de l'altérer, ok...

Mais cela permet-il de déchiffrer?


Concernant ton edit, ici, il n'y a pas de répétition de clef, donc pas de répétition liée dans le message chiffré...

Oui, si tu utilises une clé de la même longueur que le message, mais je pense que tu vois toi même le problème.

Comment envoyer cette clé ?

Imagine la taille supplémentaire du message tu multiplies par deux. Tu veux envoyer un CD de 700 mo il te faut 1400mo. C'est impraticable.

Cela se fait ou se faisait pour les téléphones diplomatiques, comme par exemple le téléphone rouge, ou on transportait par valise diplomatique les codes. Mais c'est tout.

Bah, clef plus courte, n fois...

Tu me diras, du coup, il y a répétition de clef, ok.

Chaîne à chiffrer :
abcdeabcde

Clef (abcde x 2):
abcdeabcde

Résultat :
пᕿ䍜鍩䐹玲蜋谼豷

Pas de répétition dans la chaîne chiffrée :)

Ouais tu tires un peu par les cheveux la ;)

Si je te donne la lettre z

Tu as peu de chance de trouver la réponse.

J'avais utilisé l'un des chiffrements les plus vieux, un césar c'était un w. Comme tu le vois un message très court ne peut pas être déchiffré avec une bonne probabilité, car il faut de la matière sur quoi travailler, ou avoir un algorithme qui ne repose sur aucun secret et le connaître.

Pour faire bref, on évalue la résistance d'un algorithme par rapport aux nombres d'opérations nécessaire en moyenne pour trouver la bonne réponse. Et cela dans divers scénarios, par exemple des attaques ou l'attaquant connaît :

Les texte non-chiffré et chiffré. (Ton algorithme ne tient pas fasse à cette attaque aussi tient.)

Un algorithmes comme l'AES, même en ayant des textes chiffré et non chiffré, résiste pendant un temps raisonnable.

Lorsque l'on déchiffre un message il nous faut un critère d'arrêt, Par exemple je te donne le texte chiffré :

asdf -> Il peut s'agir de n'importe quel mot de 4 lettres français

C'est le problème principale par exemple du déchiffrement des hiéroglyphes, comment déchiffrer un message dont l'on ne connaît rien ?

Maintenant si je te donne un bouquin chiffré, l'objectif est que tu ne puisses rien en déduire, ce qui n'est pas le cas avec ton algorithmes (à mon avis), ou avec un césar ou un vigénère.

Ton algorithmes est très sympa, il a une résistance équivalente aux algorithmes d'avant l'informatique ;) Il ferai un bon challenge sur des sites spécialisé comme http://www.newbiecontest.org/

Tiré par les cheveux? bof, il le gère déjà automatiquement. :)

Version finale postée :

Ajout d'une condition permettant de switcher lors des itérations.

Certaines fois, le tableau est inversé, ainsi, le report de chiffrement qui était à sens unique se retrouve en forme de nuage.

Du coup, chaque caractère de la chaine chiffrée peut contenir des bits de chacun des autres

La personne voulant déchiffrer, sans la clef et/ou sans l'encodage, ne saura dire si tel bit vient de la gauche ou de la droite, à aucun moment. (le chat de schrodinger)

Mais alors, comment vous, vous savez qu'il faut faire l'inversion, durant votre processus de décodage ?

Salut LittleWhite :)

C'est simple, j'effectue exactement le même test lors du déchiffrement que lors du chiffrement :

Code:

---

1 2 3

if(!((Math.min.apply(null,dataCodes)^Math.max.apply(null,dataCodes)^keyCode^encodingLength)%2)){ dataCodes.reverse(); }

---

Où dataCodes correspond à un tableau contenant la liste des valeurs courantes des codes de la chaîne (à chaque itération sur les codes de la clef).

Oui c'est déjà une amélioration. D'autres algorithmes utilise des blocs plus gros (chiffrement de plusieurs caractères d'un coup), ce qui permet d'empêcher l'attaque que j'ai fait.

Maintenant je pense pas que tu résistes à une "Known-plaintext attack" :

http://en.wikipedia.org/wiki/Known-plaintext_attack

Je ne saurais dire, n'ayant les connaissances nécessaires...

Néanmoins, si c'est possible, cela me semble vraiment laborieux...

Oui comprendre les différentes attaques cryptographiques c'est pas la joie ;)

Je pense quand même que je suis capable de casser ton code avec un known plaintext ;) Affirmation sans conséquence vu que je n'ai de toute façon pas le temps de le prouver :ccool:


Sur quoi je m'appuie pour affirmer cela ? On va comparer avec un autre algorithme symétrique DES (d'ailleurs lent et la clé est trop courte).

- Tu utilises des additions, et cela me semble vraiment faible par rapport à un xor. D'ailleurs j'ai le souvenir dans les cours de crypto, que l'on disait que si l'on pouvait résoudre un algo avec des additions/soustraction c'était faible mais à vérifier avec un cryptographe.

- Tu n'as pas de confusion (par exemple des S-BOX) http://fr.wikipedia.org/wiki/S-Box -> attaque par cryptanalyse différentielle (par contre la c'est clairement quelques niveau en dessus de mes compétences).

- En connaissant le texte clair, et le texte chiffré on peut retrouver la clé sans problème non ?

Je ne pense pas que cela soit si facile que cela...

Je ne sais pas si tu as lu les edits du post original et tous les post entre-temps, j'ai fait quelques changements au niveau de mes additions.

Pour t'éviter de devoir rechercher parmi tout ça, voici le lien vers la doc que je suis en train de faire.

http://www.lcfvs.com/PES/

Désolé, ce n'est pas très esthétique, c'est en cours de construction.