nombre caracteres et bits ?

Francois Grieu wrote:

Avec OTP, tous les textes clairs sont possibles, et la force
brute est non applicable.

Je voulais dire des clairs "plausibles", compréhensibles. À partir de deux
clés et d'un même chiffré obtenir deux textes absolument logiques et
compréhensibles, mais différents.

Si je ne m'abuse, un bon exemple figure dans le Brauer.

Connais pas.

J'essaye de te retrouver ça.

--
Arnold McDonald (AMcD)

http://arnold.mcdonald.free.fr/

Francois Grieu

Phil l'ancien

Mais comment le programme attaquant sait-il
qu'il a trouvé la bonne clé ?

Il faut en effet qu'il dispose d'un test de plausibilité
du texte déchifré.

Exemple : disons que le texte clair est :
"Attaquez demain à l'aube", et que la clé
utilisée est : "MEDOR".
...
Disons qu'avec la clé "REX" j'obtiens
(par hasard) le texte incorrectement déchiffré :
"Battez en retraite mercredi".

Cette hypothèse est extrèmement improbable...

D'accord avec ça et ce que tu dis plus bas,
mais je n'ai choisi des phrases en français que
pour illustrer ma question.

Il peut tout aussi bien s'agir de suites
d'octets sans interprétation évidente
(par exemple résultant d'une compression,
ou d'un simple "brouillage" par un xor tout
bête).


Au final, si je comprends bien ta réponse,
pour un clair arbitraire sur lequel on n'a pas
d'informations a priori, l'attaque par force
brute n'existe pas en réalité au niveau algorithmique.

Par contre elle existe effectivement au niveau
applicatif, par exemple quand on casse le mot
de passe d'un document MS Office, une archive
rar, etc.
(parce que c'est l'applicatif lui-même qui répond
à l'attaquant : "clé incorrecte", en quelque sorte).


C'est bien correct ?


Phil l'ancien-

Bon, l'exemple *d'OTP* générant deux textes absolument crédibles dont je
parlais plus haut ne figure pas dans le Brauer, mais dans le Stallings
(honte à moi).

ciphertext: ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key: pxlmvmsydofuyrvzwc tnlebnecvgdupahfzzlmnyih
plaintext: mr mustard with the candlestick in the hall

ciphertext: ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key: mfugpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwt
plaintext: miss scarlet with the knife in the library

Évidemment, la clé n'est pas courte puisqu'elle est aussi longue que le
texte (en même temps, vu que c'est du OTP...). Mais bon, le chiffré a une
taille sympa qui permet de dépasser les cas d'école souvent constitués de
quelques caractères...

Concernant des algos de chiffrages plus intéressants pour nous, notamment du
point de vue de la taille de la clé, il me semble toutefois avoir également
vu un exemple du même accabit, chiffré générant deux textes crédibles lors
de l'utilisation de deux clés (courtes) différentes. Chiffré de plusieurs
centaines de caractères. Mais où ? J'ai tellement de bouquins à fouiller
aussi :-). Si ça me revient, je le posterai à l'occasion.

--
Arnold McDonald (AMcD)

http://arnold.mcdonald.free.fr/

Dans l'article <46e880b7$0$27413$ba4acef3@news.orange.fr>,
"Phil l'ancien" écrit:

pour un clair arbitraire sur lequel on n'a pas
d'informations a priori, l'attaque par force brute
n'existe pas en réalité au niveau algorithmique.

Ce n'est pas tout à fait vrai: la force brute ne donne pas
d'information sur la clé, mais peut néanmoins exhiber
de l'information sur le clair.
En déchiffrant le chiffré avec toutes les clés possibles,
on obtient tous les clairs possibles, ce qui par exemple
peut permettre de construire une courte chaîne dont on est
certain qu'elle ne figure pas dans le clair, et une très
courte chaîne dont on est certain qu'elle figure dans le
clair.

Plus précisément: dans un cryptosystème réversible pour
toute clé admissible et tout clair, et où clair et chiffré
ont toujours exactement la même taille, si le clair est
aléatoire et non corrélé à une information connue de
l'attaquant autre que le chiffré, aucune attaque
cryptanalytique ne peut révéler une information quelconque
sur la clé. Et l'incertitude résiduelle sur le clair est
au moins égale à l'incertitude initiale sur la clé.

Noter que l'hypothèse "clair aléatoire et non corrélé
à une information connue de l'attaquant" est très éloignée
de la réalité pratique. En particulier, si le clair en
question est utilisé dans quelque chose observé par
l'attaquant (comme clé d'un autre cryptosystème...),
ou est chiffré d'une autre façon, l'hypothèse tombe.

Par contre l'attaque par force brute existe effectivement
au niveau applicatif, par exemple quand on casse le mot
de passe d'un document MS Office, une archive rar, etc.

Oui, d'autant plus que le nombre de clés à examiner est
faible, le chiffré long, le clair redondant ou partiellement
connu, et le cryptosystème pas conçu en fonction de la
contrainte d'une clé de faible entropie (contrainte trop
souvent ignorée alors que c'est la réalité terrain, et
qu'il existe des solutions efficaces pour composer avec
cette réalité, à condition d'accepter un petit délai au
début du déchiffrement).

(parce que c'est l'applicatif lui-même qui répond
à l'attaquant : "clé incorrecte", en quelque sorte).

Oui, si par "applicatif" on entend la logique qui rend
le clair redondant (exemple: clair destiné à être lisible
par un Français, ou/et clair produit par tel programme).
Mais rien n'oblige l'attaquant à utiliser exactement
cet applicatif là pour tester la validité du clair: il
peut utiliser un test ad hoc (classiquement: portion du
clair connue, fréquence des lettres/bigrammes/trigrammes).


François Grieu

Dans l'article <46e880b7$0$27413$ba4acef3@news.orange.fr>,
"Phil l'ancien" écrit:

pour un clair arbitraire sur lequel on n'a pas
d'informations a priori, l'attaque par force brute
n'existe pas en réalité au niveau algorithmique.

Ce n'est pas tout à fait vrai: la force brute ne donne pas
d'information sur la clé, mais peut néanmoins exhiber
de l'information sur le clair.
En déchiffrant le chiffré avec toutes les clés possibles,
on obtient tous les clairs possibles, ce qui par exemple
peut permettre de construire une courte chaîne dont on est
certain qu'elle ne figure pas dans le clair, et une très
courte chaîne dont on est certain qu'elle figure dans le
clair.

Plus précisément: dans un cryptosystème réversible pour
toute clé admissible et tout clair, et où clair et chiffré
ont toujours exactement la même taille, si le clair est
aléatoire et non corrélé à une information connue de
l'attaquant autre que le chiffré, aucune attaque
cryptanalytique ne peut révéler une information quelconque
sur la clé.

Noter que l'hypothèse "clair aléatoire et non corrélé
à une information connue de l'attaquant" est très éloignée
de la réalité pratique. En particulier, si le clair en
question est utilisé dans quelque chose observé par
l'attaquant (comme clé d'un autre cryptosystème...),
ou est chiffré d'une autre façon, l'hypothèse tombe.

Par contre l'attaque par force brute existe effectivement
au niveau applicatif, par exemple quand on casse le mot
de passe d'un document MS Office, une archive rar, etc.

Oui, d'autant plus que le nombre de clés à examiner est
faible, le chiffré long, le clair redondant ou partiellement
connu, et le cryptosystème pas conçu en fonction de la
contrainte d'une clé de faible entropie (contrainte trop
souvent ignorée alors que c'est la réalité terrain, et
qu'il existe des solutions efficaces pour composer avec
cette réalité, à condition d'accepter un petit délai au
début du déchiffrement).

(parce que c'est l'applicatif lui-même qui répond
à l'attaquant : "clé incorrecte", en quelque sorte).

Oui, si par "applicatif" on entend la logique qui rend
le clair redondant (exemple: clair destiné à être lisible
par un Français, ou/et clair produit par tel programme).
Mais rien n'oblige l'attaquant à utiliser exactement
cet applicatif là pour tester la validité du clair: il
peut utiliser un test ad hoc (classiquement: portion du
clair connue, fréquence des lettres/bigrammes/trigrammes).


François Grieu
[reposté avec une connerie en moins]

Le (on) jeudi 13 septembre 2007 04:25, Arnold McDonald (AMcD) a écrit
(wrote) :

Bon, l'exemple *d'OTP* générant deux textes absolument crédibles dont je
parlais plus haut ne figure pas dans le Brauer, mais dans le Stallings
(honte à moi).

ciphertext: ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key: pxlmvmsydofuyrvzwc tnlebnecvgdupahfzzlmnyih
plaintext: mr mustard with the candlestick in the hall

ciphertext: ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key: mfugpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwt
plaintext: miss scarlet with the knife in the library

Évidemment, la clé n'est pas courte puisqu'elle est aussi longue que le
texte (en même temps, vu que c'est du OTP...). Mais bon, le chiffré a une
taille sympa qui permet de dépasser les cas d'école souvent constitués de
quelques caractères...

Euh, je vais peut-être dire une grosse c*nnerie, mais... Est-ce qu'il n'est

pas absolument trivial qu'avec un masque jetable, pour un chiffré donné,
tous les messages ayant exactement la même longueur que le chiffré sont des
déchiffrés possibles ?

Il me semble que c'est même en un sens la force du masque jetable, non ?

Concernant des algos de chiffrages plus intéressants pour nous, notamment
du point de vue de la taille de la clé, il me semble toutefois avoir
également vu un exemple du même accabit, chiffré générant deux textes
crédibles lors de l'utilisation de deux clés (courtes) différentes.
Chiffré de plusieurs centaines de caractères. Mais où ? J'ai tellement de
bouquins à fouiller aussi :-). Si ça me revient, je le posterai à
l'occasion.

Ça, ça m'intéresserait bien. Quoique dans la vraie vie, je pense qu'un

attaquant qui se trouverait avec deux clairs possibles saurait distinguer
lequel est le bon sur d'autres critères (contexte).

Manuel.

Francois Grieu

Phil l'ancien

Mais comment le programme attaquant sait-il
qu'il a trouvé la bonne clé ?

Il faut en effet qu'il dispose d'un test de plausibilité
du texte déchifré.

A la reflexion, c'est très proche du problème
de SETI ;-)


Phil l'ancien-

Euh, je vais peut-être dire une grosse c*nnerie, mais... Est-ce qu'il
n'est
pas absolument trivial qu'avec un masque jetable, pour un chiffré donné,
tous les messages ayant exactement la même longueur que le chiffré sont
des
déchiffrés possibles ?

Ouaip. Mais ici, l'intérêt est que les deux déchiffrés ont des sens
absolument similaires ! Ce ne sont pas des séries de mots mais des phrases
au sens très proche, qui fait qu'il est impossible de choisir l'une ou
l'autre. Cas d'école, certes, mais joli :-).

Il me semble que c'est même en un sens la force du masque jetable, non ?

Oui, tout est possible avec l'OTP, même de trouver des cas théoriques très
intéressants :-).

Ça, ça m'intéresserait bien.

Je cherche, je cherche... J'ai déjà mis une journée à me remémorer l'autre
exemple là, alors, ça risque de prendre du temps.

Quoique dans la vraie vie, je pense qu'un
attaquant qui se trouverait avec deux clairs possibles saurait distinguer
lequel est le bon sur d'autres critères (contexte).

Hmmm, regarde l'exemple ci-dessus :-).

Arnold McDonald

Le (on) jeudi 13 septembre 2007 23:51, Arnold McDonald a écrit (wrote) :

Euh, je vais peut-être dire une grosse c*nnerie, mais... Est-ce qu'il
n'est
pas absolument trivial qu'avec un masque jetable, pour un chiffré donné,
tous les messages ayant exactement la même longueur que le chiffré sont
des
déchiffrés possibles ?

Ouaip. Mais ici, l'intérêt est que les deux déchiffrés ont des sens
absolument similaires ! Ce ne sont pas des séries de mots mais des phrases
au sens très proche, qui fait qu'il est impossible de choisir l'une ou
l'autre. Cas d'école, certes, mais joli :-).

Disons qu'en fait le vrai sens de l'exemple est qu'il existe en anglais deux

phrases ayant le même longueur, deux sens différents, mais tous les deux
plausibles dans un contexte donné. Encore une fois, je ne vois pas trop ce
que ça a de surprenant : il suffit d'effectuer des substitutions de mots en
comptant combien de lettres on enlève ou rajoute à chaque fois et en
s'arrangeant pour que le somme fasse 0.

Quoique dans la vraie vie, je pense qu'un
attaquant qui se trouverait avec deux clairs possibles saurait distinguer
lequel est le bon sur d'autres critères (contexte).

Hmmm, regarde l'exemple ci-dessus :-).

En même temps, vu quel masque jetable est le seul système absolument sûr

d'un point de vue théorique, je n'arrive pas à être très surpris qu'il pose
des problèmes à l'attaquant :)

Manuel.

Euh, je vais peut-être dire une grosse c*nnerie, mais...
non, mais ta modestie montre que tu commence a avoir de l'expérience en

crypto...

Est-ce qu'il >> n'est
pas absolument trivial qu'avec un masque jetable, pour un chiffré donné,
tous les messages ayant exactement la même longueur que le chiffré sont
des
déchiffrés possibles ?
oui

en fait avec un algo de chiffrement à clé de taille finie ,
pour un chiffré donné, le nombre de clair possibles est le nombre de
clés possibles...

d'un autre coté si le clair est redondant (texte non compressé ou mal
compressé, entêtes obligatoires, contraintes de valeurs, interdits...)
seule une proportion (faible) des clairs est réaliste (test d'arrêt)

comme les clairs compatbles avec le chiffré n'ont aucune raisons d'avoir
des relations entre eux qui conservent les contraintes du clair, on peut
estimer qu'ils sont aléatoires indépendants entre eux

donc la proba qu'il y ait plusieurs clairs crédibles pour un chiffré connu
c'est a peu près tant que c'est petit :
le taux de clairs crédibles par rapport au clair possibles multiplié par
le nombre de clé possible

le taux de clairs crédibles dépend (en puissance de 2) en fait de la
quantité d'information transmise, divisé par la taille du message.
or ce taux diminue très vite avec la taille du message.

ainsi si on parle de texte anglais transmis sous forme d'octets,
on a (valeur donne dans certains livres) 1,5 bits d'information en
moyenne par octet, c'est a dire en moyenne
2^1.5=2.8 caractères probables au lieu de 256.... soit une chance sur 90
(6,5 bits) qu'un octet aléatoire soit crédible dans un texte...


avec une algo classique type DES/AES, et un clair long et non compressé
on a un nombre de clés fixe, genre 2^64 ou 128

avec ces chiffres pour 64 bits, dès qu'un texte anglais dépasse la
dizaine de caractère, il y a peu de chance qu'il y ait de doublons crédible

si on compresse le texte de facon à ce que on consomme 2 bits en moyenne
par caractère, il faut au moins 128 caractères pour trouver asse de
redondance dans le texte...

si on compresse à 1,6 bits pas caractère
il faut 640 caractères pour éliminer les doublons...

si la compression est parfaite (ca n'est possible que si le message est
parfaitement aléatoire, par exemple une clé de session dont on ne peut
pas tester la qualité), on peut rien trouver.


avec le one-time pad, le nombre de clé est égal au nombre de clair
possibles, donc la formule ne tient pas, mais en fait tout les clairs
sont possibles