Clé jetable usage unique

On 27 juin, 00:10, "almas" <al...@naturo.com> wrote:

Bonjour à tous.
Je sais qu'il faut n'utiliser qu'une fois une clé....
Mais si je fais
a XOR b = c
d XOR b = e

c et e étant les fichiers en sortie, si on dispose de c et e
comment fait-on pour retrouver la clé b ?

La question va paraitre simple pour un habitué...
mais pour un novice comme moi ....

A partir de là, on connait c XOR e = a XOR d, c'est à dire qu'on
connait la somme des 2 messages clairs. A partir de là, il est
possible de retrouver des informations sur ces 2 messages clairs.

"spook" <thomas.dingos@gmail.com> a écrit dans le message de news:
ce25e728-d868-46cc-af05-e1beeb7074ea@d1g2000hsg.googlegroups.com...
On 27 juin, 00:10, "almas" <al...@naturo.com> wrote:

Bonjour à tous.
Je sais qu'il faut n'utiliser qu'une fois une clé....
Mais si je fais
a XOR b = c
d XOR b = e

c et e étant les fichiers en sortie, si on dispose de c et e
comment fait-on pour retrouver la clé b ?

La question va paraitre simple pour un habitué...
mais pour un novice comme moi ....

A partir de là, on connait c XOR e = a XOR d, c'est à dire qu'on
connait la somme des 2 messages clairs. A partir de là, il est
possible de retrouver des informations sur ces 2 messages clairs.....

Merci pour la réponse,
J'étais arrivé au même résultat.
Si on a 3 messages de sortie, si on a la même clé on a
(s1 XOR s2 ) XOR (s1 XOR s3 ) = s1 XOR s3
Si la propriété n'est pas vérifiée, alors la clé est différente.
Mais, on reste avec un ? XOR ?

Je suppose que si le texte commence toujours par
Monsieur X 115 rue du chien bleu Paris 15ème
on a une longue chaine qui révèle la clé.

Idem si on sait que le message contient un mot particulier
'( Exemple [ not' Président de Groland ... ]
Dans ce cas, on a là aussi une chaine de caractères "sensible"
Mais faut-il encore savoir qu'un message contient cela.
Et rien n'interdit d'avoir au préalable comprimé un message avec un bon
vieux PkZip ou autre

En résumé, je comprends que la même clé affaiblit,
mais je n'ai pas trouvé une méthode pour à tout coup trouver le message.

... je me suis trompé : voir en fin de texte :
Avec S1 à S3 3 messages de sortie..

Si on fait ( s1 XOR s2) XOR ( s1 XOR s3 ) = s2 XOR s3
Il fallait lire s2 Ror s3 ( et pas s1* s3 )
La propriété n'est vérifiée que si on a la même clé qui a servi 3 fois.

La clé disparait en codant 2 messages.
On n'a pas les messages en clair, mais si on connait une partie, par exemple
l'entête d'un fichier : Octets PK pour un ZIP... on a décodé 2 octets. Du
coup, on pourra décoder 2 octets en modulo [ longueur de clé ]
Nota : pour m'amuser, j'ai fait une clé avec un XOR 20 :
ca met majuscule- Minuscule

Je voudrais savoir s'il existe une méthode pour trouver à tout coup la clé
si usage multiples, avec une clé "sérieuse"
----- Original Message -----
From: "almas" <almas@naturo.com>
Newsgroups: fr.misc.cryptologie
Sent: Friday, June 27, 2008 8:46 PM
Subject: Re: Clé jetable usage unique


"spook" <thomas.dingos@gmail.com> a écrit dans le message de news:
ce25e728-d868-46cc-af05-e1beeb7074ea@d1g2000hsg.googlegroups.com...
On 27 juin, 00:10, "almas" <al...@naturo.com> wrote:

Bonjour à tous.
Je sais qu'il faut n'utiliser qu'une fois une clé....
Mais si je fais
a XOR b = c
d XOR b = e

c et e étant les fichiers en sortie, si on dispose de c et e
comment fait-on pour retrouver la clé b ?

La question va paraitre simple pour un habitué...
mais pour un novice comme moi ....

A partir de là, on connait c XOR e = a XOR d, c'est à dire qu'on
connait la somme des 2 messages clairs. A partir de là, il est
possible de retrouver des informations sur ces 2 messages clairs.....

Merci pour la réponse,
J'étais arrivé au même résultat.
Si on a 3 messages de sortie, si on a la même clé on a
(s1 XOR s2 ) XOR (s1 XOR s3 ) = s1 XOR s3
Si la propriété n'est pas vérifiée, alors la clé est différente.
Mais, on reste avec un ? XOR ?

Je suppose que si le texte commence toujours par
Monsieur X 115 rue du chien bleu Paris 15ème
on a une longue chaine qui révèle la clé.

Idem si on sait que le message contient un mot particulier
'( Exemple [ not' Président de Groland ... ]
Dans ce cas, on a là aussi une chaine de caractères "sensible"
Mais faut-il encore savoir qu'un message contient cela.
Et rien n'interdit d'avoir au préalable comprimé un message avec un bon
vieux PkZip ou autre

En résumé, je comprends que la même clé affaiblit,
mais je n'ai pas trouvé une méthode pour à tout coup trouver le message.

almas a écrit :

A partir de là, on connait c XOR e = a XOR d, c'est à dire qu'on
connait la somme des 2 messages clairs. A partir de là, il est
possible de retrouver des informations sur ces 2 messages clairs.....

Merci pour la réponse,
J'étais arrivé au même résultat.
Si on a 3 messages de sortie, si on a la même clé on a
(s1 XOR s2 ) XOR (s1 XOR s3 ) = s1 XOR s3

...

Et rien n'interdit d'avoir au préalable comprimé un message avec un bon
vieux PkZip ou autre

tout a fait! c'est un conseil général qu'on donne. si on a pas une
confiance totale dans l'algo de chiffrement, il faut compresser.
dans ce cas il y a moins de redondance dans le message clair que
pourrait détecter un algorithme de décryptage.

le décryptage d'un corpus de messages est basé sur les ses redondances.
sans redondances, pas possible de savoir si le résultat est bon ou pas.
or un algo de compression élimine les redondance d'un message.
a l'opposé un bon algo de chiffrement fait disparaitre toute information
sur le texte clair, y compris ses redondances, et donc un compresseur ne
doit pas pouvoir compresser un chiffré.

En résumé, je comprends que la même clé affaiblit,

c'est l'essentiel.
une clé affaiblie, c'est quand on réduit l'espace des clés
possibles/probables.

si par exemple sur une clé incassable de 64bits on arrive à éliminer 16
bits d'entropie, le problème (2^48 tests) devient difficile mais réalisable

avec une clé très très longue (type one-time pad réutilisée) c'est pas
simple d'accumuler assez d'"indices" pour orienter la recherche des clés.
dans notre cas avec quelques centaines de messages en langue
simple non compressés on devrait pouvoir deviner la plupart des bits de
clés.

en poussant au niveau théorique, avec de la théorie de l'information
j'avais lu que dans un texte anglais chaque lettre n'apporte en moyenne
que 1,5 bits d'entropie, mais fait 8bits par caractère. donc pour chaque
lettre on a 6,5 bits de prévisible et 1,5 de surprenant.

avec 2 messages on a des chances de retrouver le xor des 6.5 bits
prévisibles, donc de remonter à 6,5 bits de clés ... c'est au mieux et à
la louche, mais en gros avec 2 message si tu est parfait tu récupère
tout sauf 1,5 bits par caractère... soit 80% des bits de la clé.
en fait tu retrouvera pas 80% des bits, mais tu réduira l'espace des
"raisonnables" par l'application d'une racine (6.5/8)
avec 3 messages tu récupèrera encore d'autres bits , tu réduira l'espace
des clés possible... pas de 80% car certains bits de la clés seront plus
dur a trouver que d'autre (en ascii les bits de poids forts sont
triviaux a deviner, pas les poids faibles, et yen a de couplés)


bon c'est en théorie en supposant que tu as une puissance de calcul et
de mémoire infinie et un algorithme parfait...

bon après il faut être plus réaliste mais tu vois que si ton texte clair
est très redondant un xor bête peux te donner autant de bits de clé que
de bits de redondance.

d'ou l'intérêt de compresser, et surtout de pas réutiliser une clé
one-time pad.
d'ou aussi l'intérêt de pas utiliser trop longtemps une clé avec un algo
plus solide... plus le corpus est gros plus il y a de grain (de
redondance) à moudre (à analyser)

mais je n'ai pas trouvé une méthode pour à tout coup trouver le message.

ca dépend de l'algorithme et du nombre de message

pour le xor réutilisé. je vois plusieurs axes de recherche.

si tu connais des morceaux de clair, ca aide, mais si ce sont les
entête, comme la clé est longue, ca ne t'aidera pas pour la suite.

une solution si on connais des caractères très fréquents c'est que entre
deux messages , le caractère le plus fréquent (genre E ou S en francais)
a une très forete (le carré de sa fréquence) proba d'être dans 2
messages au même endroit.
si tu repère un zero tu peux deviner que le caractère est un caractère
probable, et donc quel est la clé correspondante probable. rien de
certain mais tu verifiera après

ensuite tu peux travailler par digramme, savoir qu'après une lettre on
trouve souvent une autre, quels sont les digramme fréquents, et donc
avec les résultats précédents remonter quelques clés...
puis de digramme tu remontera en mots, en expressions, voir à des
connaissance sémantique.

il y a certainement des méthodes statistiques plus puissantes que la
mienne.(qui connaitrait ici)
peut être même selon la langue tu pourra remonter sur des équations
statistiques bits à bits et non lettre à lettre, ou des digrammes bits
à bits et non lettre à lettres... un peut comme en cryptanalyse linéaire.

évidemment plus tu as de corpus plus tu as de chance de casser la clé.
et plus c'est compressé moins c'est simple.

si le domaine t'intéresse essaye de lire "applied cryptograpy" par bruce
schneier (ya un autre qui porte un nom proche genre cryptography theory
and practice)... les premiers chapitres parlent de ce genre de problèmes