OVH Cloud OVH Cloud

Algo pour crypter.

36 réponses
Avatar
Horace
Bonjour...

J'essaye de développer un petit algorithme pour crypter/décrypter un
fichier de n'importe quel type. C'est plus ou moins clair dans ma tête (une
partie oui, une partie non). J'essaye de mettre ça en forme avec TURBO
PASCAL, mais j'ai des gros problèmes pour programmer (en raison de la
compatibilité des fichiers entre MS-DOS et WINDOWS).
En gros, je voulais vous expliquer un peu mon idée, et voir votre avis
là-dessus.

Ce que je veux faire : un programme (et donc un algo :) qui permette de
crypter un fichier de n'importe quel nature, s'il n'est pas trop gros
(maximum 1 à 5 Mo). En raison des contraintes imposées par le langage, on ne
peut crypter qu'un fichier à la fois. J'ai déjà fait des petits programmes
de cryptage, mais c'était des petits trucs de bricolage. Là, sans avoir
envie de pondre du DES ou quoi, j'ai quand même envie de faire quelque chose
de 'sérieux', je veux dire quelque chose qui soit vraiment dur à casser.

Il y a deux parties dans l'algorithme.
1. L'encodage.
On décompose le fichier en blocs de 8 octets (ça tombe toujours juste,
c'est arrangé...), ça nous donne un tableau 8x8 rempli de 0 ou de 1 (plus
précisément, chaque ligne comporte le code binaire d'un octet). On répète 10
fois l'ensemble suivant :
- on retourne chaque tableau individuellement ;
- on déplace les octets d'un tableau à un autre. Le résultat est assez
complexe (si on cherche à voir où les octets atterrissent).
Après l'encodage, les bits sont complètement mélangés, et on a reformé
un fichier de caractères.
2. Le cryptage.
Là, c'est un peu moins clair dans mon esprit. Je pense prendre une clef
de 16 caractères (donc en gros 255 possibilités par caractère de la clef,
moins une vingtaine (entrée, supprimer, etc.) inutilisables, donc en gros
220^16 clefs possibles). Avec cette clef, on génère une liste de nombre
pseudo-aléatoires longue (probablement 1024 octets). On code le résultat de
l'encodage avec cette clef au moyen d'un XOR. Certes, il y a répétition,
mais d'une part, la chaîne est très longue, et d'autre part, l'encodage a
complètement brouillé les bits. Je ne pense pas qu'une telle répétition
porte préjudice à la sécurité du code.

Voilà. Le principe de cryptage est très simple, en lui-même, mais il est
assez solide, je pense, du fait que la chaîne avec laquelle on code est
longue (on peut encore la rallonger), et d'autre part du fait du grand
nombre de clefs possibles qui rend très difficile le cassage par force
brute. D'autre part, l'extrême simplicité de ce procédé garantit au moins
une chose : il n'y a pas de trappe dans l'algorithme (volontaire ou
involontaire).

Alors, deux questions :
1. Est-ce que l'encodage est absolument nécessaire ? S'il est là, après
avoir testé X clefs (attaque par force brute), on reste obligé de décoder,
ça fait perdre du temps.
2. Quelle sécurité offre un algorithme de ce genre ? Les calculs ne sont
pas compliqués (donc pas longs), mais il y a un grand nombre de clefs
possibles. C'est un cryptage à combien de bits, il faudrait combien de temps
à un ordinateur classique pour casser ça par la force brute (une idée ?) ?
3. Est-ce qu'il ne vaudrait pas mieux mêler l'encodage et le cryptage,
c'est-à-dire crypter au fur et à mesure qu'on encode. Je pense que la
sécurité en serait améliorée (plus de calculs à effectuer pour un cassage
par force brute).

Merci à vous si vous prenez un peu de votre temps pour me répondre...


Cordialement,
Christophe

10 réponses

1 2 3 4
Avatar
Marco
1. L'encodage.
Phase totalement inutile, AMHA.



Je pense qu'il veut faire cela afin de d'empecher les attaques sur la
forme du clair (frequences, entetes ...). Je doute également que ça
ait une quelquonque utilité, mais je ne suis pas capable de le
prouver.


Oui, c'est bien ça ce que je recherche. Mais je ne comprends pas
pourquoi ce serait inutile, dans la mesure où ce ne sont même pas les
caractères qu'on échange, mais les bits qui leurs correspondent.
Enfin, si vous pouviez expliquer tout ça...


Alors, la transformation qui vous appelez encodage est une transformation
linéaire, n'ayant pas de clé (élément inconnu); par la suite ce texte
est soumis à une autre opération linéaire qui est le XOR avec une
séquence pseudo-aléatoire. Il est évident que les deux opérations
commutent, et que donc on peut inverser l'opération d'encodage sur le
texte chiffré sans avoir à connaitre la séquence pseudo-aléatoire. De
plus, comme la longueur des blocs qui sont encodés est un diviseur de la
longueur de la séquence pseudo-aléatoire, on peut remarquer que dans
cette transformation inverse la séquence pseudo-aléatoire est
transformée toujours de la mème manière, en permettant une attaque
comme celui pour l'algoritme Vernam.

Ensuite, comme on reprend la meme séquence pseudo-aléatoire tous les
1024 octets, il suffit de faire un xor sur le texte chiffré avec lui-meme
décalé de 1024 octets pour éliminer la partie dépendente de la clé et
avoir simplemente un deux textes en clair superposés, problème qu'on
peut resoudre aisément avec des techniques statistiques bien connues.

Sans brutalité, le système proposé est beaucoup plus lent qu'un simple
stream-cipher, et nettement plus faible, il ne faut pas prendre ombrage si
on vous dit que vous avez encore beaucoup à étudier avant de pouvoir
"produire" quelque chose qui soit du moins marginalement intéressant.

Marco




Le but recherché, c'est peut-être comme bien d'autres il s'ennuie à
la plage et préfère rester chez lui à codouiller des trucs pour
passer le temps.


... gagné !


Bien à vous,
Christophe





Avatar
Horace
Michel :

La clé fait 16 octets. Point barre. Si c'est ça, il ne va pas aller
loin.


220^16, c'est pas beaucoup ?


~~
Christophe

Avatar
Michel Arboi
On Thu Aug 12 2004 at 21:33, Horace wrote:

La clé fait 16 octets. Point barre. Si c'est ça, il ne va pas aller
loin.
220^16, c'est pas beaucoup ?



On parlait d'avoir des données de taille proche de la clé, si je me
souviens bien.


Avatar
Michel Arboi
On Thu Aug 12 2004 at 17:21, Horace wrote:

Comme partout, peut-être. Mais ici un peu plus qu'ailleurs, c'est vrai,
mais j'ignore pourquoi...


Parce que c'est un sujet pointu et qu'il est inutile de se précipiter
sur un clavier avant d'avoir digéré la littérature sur le sujet.

Dans les autres domaines fumeux de l'informatique, on peut espérer
faire illusion si on se lance tête baissée dans un problème sans
s'être un poil renseigné avant.
En crypto, non. Dans d'autres sujets pointus non plus.

Et dans tous les domaines on gagne du temps à se cultiver avant d'agir
ou de couiner que ça ne marche pas. On évite aussi aux autres d'en
perdre pour expliquer des règles de survie de base dans ce monde
cruel.

--
http://arboi.da.ru
FAQNOPI de fr.comp.securite http://faqnopi.da.ru/
NASL2 reference manual http://michel.arboi.free.fr/nasl2ref/

Avatar
BlackFlag
Le 12-08-2004, Michel Arboi a écrit:
Marc aura très bien répondu à cette question...


Alors si c'est pour passer le temps, commencez plutôt par des bons
bouquins sur le sujet. Par exemple :
"The codebreakers" de Davin Kahn (historique)
"Cryptography: theory & practice" de Stinson.
Sans oublier les bouquins de Bruce Schneier, comme "Cryptographie Appliquée".


Cordialement,


Avatar
le_troll
Salut Horace, t'as pas envie de t'essayer au décryptage télévisuel :o)

--
Merci, @+, bye, Joe
troll75 AROBASE iFrance POINT com
------------------------------------------
Ce message est plein de virus "certifiés"
Le_Troll, éleveur de Trolls depuis César, qui disait:
Avec une hache, celui qui tient le manche a toujours raison !
------------------------------------------


"Horace" a écrit dans le message de news:
cfad8b$a96$
Bonjour...

J'essaye de développer un petit algorithme pour crypter/décrypter un
fichier de n'importe quel type. C'est plus ou moins clair dans ma tête
(une

partie oui, une partie non). J'essaye de mettre ça en forme avec TURBO
PASCAL, mais j'ai des gros problèmes pour programmer (en raison de la
compatibilité des fichiers entre MS-DOS et WINDOWS).
En gros, je voulais vous expliquer un peu mon idée, et voir votre avis
là-dessus.

Ce que je veux faire : un programme (et donc un algo :) qui permette
de

crypter un fichier de n'importe quel nature, s'il n'est pas trop gros
(maximum 1 à 5 Mo). En raison des contraintes imposées par le langage, on
ne

peut crypter qu'un fichier à la fois. J'ai déjà fait des petits programmes
de cryptage, mais c'était des petits trucs de bricolage. Là, sans avoir
envie de pondre du DES ou quoi, j'ai quand même envie de faire quelque
chose

de 'sérieux', je veux dire quelque chose qui soit vraiment dur à casser.

Il y a deux parties dans l'algorithme.
1. L'encodage.
On décompose le fichier en blocs de 8 octets (ça tombe toujours juste,
c'est arrangé...), ça nous donne un tableau 8x8 rempli de 0 ou de 1 (plus
précisément, chaque ligne comporte le code binaire d'un octet). On répète
10

fois l'ensemble suivant :
- on retourne chaque tableau individuellement ;
- on déplace les octets d'un tableau à un autre. Le résultat est assez
complexe (si on cherche à voir où les octets atterrissent).
Après l'encodage, les bits sont complètement mélangés, et on a reformé
un fichier de caractères.
2. Le cryptage.
Là, c'est un peu moins clair dans mon esprit. Je pense prendre une
clef

de 16 caractères (donc en gros 255 possibilités par caractère de la clef,
moins une vingtaine (entrée, supprimer, etc.) inutilisables, donc en gros
220^16 clefs possibles). Avec cette clef, on génère une liste de nombre
pseudo-aléatoires longue (probablement 1024 octets). On code le résultat
de

l'encodage avec cette clef au moyen d'un XOR. Certes, il y a répétition,
mais d'une part, la chaîne est très longue, et d'autre part, l'encodage a
complètement brouillé les bits. Je ne pense pas qu'une telle répétition
porte préjudice à la sécurité du code.

Voilà. Le principe de cryptage est très simple, en lui-même, mais il
est

assez solide, je pense, du fait que la chaîne avec laquelle on code est
longue (on peut encore la rallonger), et d'autre part du fait du grand
nombre de clefs possibles qui rend très difficile le cassage par force
brute. D'autre part, l'extrême simplicité de ce procédé garantit au moins
une chose : il n'y a pas de trappe dans l'algorithme (volontaire ou
involontaire).

Alors, deux questions :
1. Est-ce que l'encodage est absolument nécessaire ? S'il est là,
après

avoir testé X clefs (attaque par force brute), on reste obligé de décoder,
ça fait perdre du temps.
2. Quelle sécurité offre un algorithme de ce genre ? Les calculs ne
sont

pas compliqués (donc pas longs), mais il y a un grand nombre de clefs
possibles. C'est un cryptage à combien de bits, il faudrait combien de
temps

à un ordinateur classique pour casser ça par la force brute (une idée ?) ?
3. Est-ce qu'il ne vaudrait pas mieux mêler l'encodage et le cryptage,
c'est-à-dire crypter au fur et à mesure qu'on encode. Je pense que la
sécurité en serait améliorée (plus de calculs à effectuer pour un cassage
par force brute).

Merci à vous si vous prenez un peu de votre temps pour me répondre...


Cordialement,
Christophe




Avatar
Horace
le_troll :

Salut Horace, t'as pas envie de t'essayer au décryptage télévisuel :o)


Désolé, je ne comprends pas, là...


~~
Christophe

Avatar
Horace
Michel :

[l'encodage]
Parce que c'est une opération qui ne change pas, qui est connue, donc
que tout le monde peut appliquer.


Oui, mais :
1. Pour la force brute, elle augmente considérablement le nombre de
calculs à exécuter pour tester chaque clef. Et comme il y a 220^16 clefs
possibles... ???
2. Elle rend impossible l'analyse de fréquence, du fait qu'après
l'encodage chaque segment de 8 octets contient des bits qui viennent de
n'importe où dans le message.

Mais... mais si on attaque le cryptosystème en comparant des textes
clairs et cryptés, ça n'empêche pas de retrouver la clef, je vous
l'accorde... Donc ça pêche.

Idée (c'est pas nouveau, mais c'est pas grave) : l'encodage dépend de la
clef (et donc ce n'est plus un encodage, je parle de cryptage). En gros, le
message est crypté en fonction de deux paramètres : lui-même (il est
brouillé) et la clef (il est crypté). J'ai aussi quelque chose qui
ressemblerait aux étages, puisque le processus simple (trop :) de
cryptage/renversage/décalage des segments de 8 octets (on travaille sur
leurs correspondants binaires, mais peu importe) est répété un nombre X de
fois, qui dépendrait par exemple de la clef... Par exemple entre 10 et 25
fois, je ne sais pas. Et la valeur du décalage dépend également de la clef.
Là, même si on ne parle pas encore d'algorithme précis, ça semble plus
sûr que l'idée initiale, non ? Vu que la méthode de cryptage dépend de la
clef, si on a les textes clairs et les textes codés, on peut toujours
essayer de les comparer pour trouver la clef, on a un très grand nombre de
calculs à faire vu qu'on ignore en plus la méthode. (Toujours une question
!!!)

Donc, même si on a une clef très longue (1024) et qu'on la répète sur un
texte complètement brouillé, cela porte préjudice à la sécurité... ?
Parce que ça revient grosso modo à un chiffre de Vigenère, qui est

cassable assez facilement. Cf. la littérature sur le sujet, par
exemple Stinson.


Je sais ce qu'est le chiffre de Vigenère, je sais qu'on peut facilement
le casser, mais j'ai du mal à trouver sur le web des infos sur la
cryptanalyse.
Mais avec un message brouillé et une clef de grande longueur, je ne
comprends pas quelle est la brêche pour rendre cela cassable.
Je veux dire... quelle est la méthode employée ? Grande quantité de
texte clair/chiffré qu'on compare ?

Ben on prend une clef de 16 caractères, on génère une clef de 1024
(peu


importe l'algo, c'est une génération de nombre pseudo aléatoire)


Si justement, l'algo importe. Car s'il n'est pas "cryptographiquement
sur", on retrouve la "graine" du générateur aléatoire.


Ok, je comprends. Mais dans mon idée, ça importait peu : celui qui
connaît la petite clef connaît la grande, et vice-versa. Mais oui, je vous
l'accorde, question sécurité, on peut mieux faire.
Solution : on a une clef de 16 octetx, on génère une clef de 128 octets
par une méthode A, on la ramène à 16 octets par une sorte de fonction de
hachage (XOR et calculs modulos), et on reprend la méthode A pour avoir une
clef de 128 octets cryptographiquement sûre.
Ca, ça marche, non ?


Marc aura très bien répondu à cette question...


Alors si c'est pour passer le temps, commencez plutôt par des bons
bouquins sur le sujet. Par exemple :
"The codebreakers" de Davin Kahn (historique)
"Cryptography: theory & practice" de Stinson.


Oh, vous savez, ce n'est pas parce que je ne sais pas tout que je ne lis
pas...
J'avais trouvé un très bon ouvrage en français sur la cryptographie, qui
expliquait la plupart des systèmes (la stéganographie, et puis du code César
jusqu'à la cryptographie quantique (je ne sais plus comment on dit, j'avais
sauté le dernier chapitre... !)), mais je ne me rappelle plus de l'auteur
(et c'est dommage, parce que j'ai envie de le relire). Ca devait être John
Steven, ou quelque chose comme ça, peut-être que vous pourriez me rappeller
le titre et l'auteur, si ça vous rappelle quelque chose.


Bien à vous,
Christophe


Avatar
Horace
Michel :

220^16, c'est pas beaucoup ?


On parlait d'avoir des données de taille proche de la clé, si je me
souviens bien.


Oui et non. La taille des fichiers aurait été limitée (enfin, elle ne
serait pas limitée dans la pratique, juste déconseillée) surtout en raison
des temps de calculs. Et accessoirement pour cette raison d'éviter une clef
trop petite pour un texte trop grand. Mais bon, toutes les autres remarques
sur le codage (surtout celle de Marco sur la façon de décrypter un texte
codé avec un XOR de clef répétée) rendent inutiles toutes discussions
supplémentaires sur ce point.

Maintenant, je prends le cas d'un algo un peu plus sûr, où la méthode
dépend en partie de la clef. Là, pour une attaque force brute (c'était le
sens de ma question), 220^16, c'est beaucoup, non ?


Bien à vous,
Christophe


Avatar
Horace
Marco :

Alors, la transformation qui vous appelez encodage est une transformation
linéaire, n'ayant pas de clé (élément inconnu); par la suite ce texte
est soumis à une autre opération linéaire qui est le XOR avec une
séquence pseudo-aléatoire. Il est évident que les deux opérations
commutent, et que donc on peut inverser l'opération d'encodage sur le
texte chiffré sans avoir à connaitre la séquence pseudo-aléatoire.


Ok, je vois. J'avais justement posé cette question il y a quelques temps
ici même, et je n'avais pas reçu de réponse.
Donc si je nomme E la fonction d'encodage et Ck le cryptage avec la clef
k, P le texte clair et M le texte crypté, on a :

Ck( E( P ) ) = M
E ( Ck ( P ) ) = M

D'où ce que vous énoncez, on peut dé-encoder le texte crypter avant de
pratiquer une analyse comme vous la décrivez par la suite. Ok.

Je comprends bien ce point, et en même temps, il y a quelque chose qui
me tracasse. Avec l'encodage que j'énonçais, on mélange les bits de chaque
octet entre eux, et avec des bits qui viennent de tout le message. Après, on
code bit à bit avec un XOR (point largement à revoir !).
Mais si on dé-encode avant de décrypter, on aura des bits codés dans
l'ordre du message clair, c'est vrai. Mais la clef qu'on devrait employer
pour décoder via un XOR serait alors différente de la clef qu'on a employée
pour coder. Toutefois, il suffirait d'appliquer la méthode que vous citez
plus loin (1024 bits XOR les 1024 suivants) pour décrypter. Ok. J'ai bon ?
Et après avoir le texte clair, on compare avec le texte crypté pour
deviner la bonne clef. Toujours bon ?

Donc il faut faire intervenir la clef dans l'encodage (qui devient
cryptage). J'en parle dans un autre post, en réponse à Michel. Par exemple
crypter le texte au fur et à mesure qu'on le brouille et décaler les octets
en fonction d'un paramètre qui dépend de la clef, et répéter tout ça un
nombre X fonction de la clef.

De
plus, comme la longueur des blocs qui sont encodés est un diviseur de la
longueur de la séquence pseudo-aléatoire, on peut remarquer que dans
cette transformation inverse la séquence pseudo-aléatoire est
transformée toujours de la mème manière, en permettant une attaque
comme celui pour l'algoritme Vernam.


J'ignore en quoi il consiste, mais je vois qu'il y a faille.

Ensuite, comme on reprend la meme séquence pseudo-aléatoire tous les
1024 octets, il suffit de faire un xor sur le texte chiffré avec lui-meme
décalé de 1024 octets pour éliminer la partie dépendente de la clé et
avoir simplemente un deux textes en clair superposés, problème qu'on
peut resoudre aisément avec des techniques statistiques bien connues.


Ok, pas de problèmes (ou plutôt si !!!) sur ce point...

Sans brutalité, le système proposé est beaucoup plus lent qu'un simple
stream-cipher, et nettement plus faible, il ne faut pas prendre ombrage si
on vous dit que vous avez encore beaucoup à étudier avant de pouvoir
"produire" quelque chose qui soit du moins marginalement intéressant.


Loin de réagir ainsi, j'ai plus envie de vous remercier. Après les
premières réactions, j'avais (presque) désespéré de recevoir des réponses
aussi complètes et claires !


Bien à vous,
Christophe

1 2 3 4