questions théoriques de cryptanalyse

Salut,

On Tue, 07 Sep 2004 23:48:06 +0200, Guillaume Kaddouch <gkweb@wanadoo.fr>
wrote:

Soit un algo de chiffrement (ex : AES), une clé, un message chiffré, et
un message clair.

Si l'attaquant possède l'algo, le message chiffré, et le message en
clair, peut il en déduire automatiquement la clé dans le cas d'AES s'il
ne la connait pas ?

Dans le pire des cas, par la force brute, oui (mais ça risque de prendre
beaucoup de temps par la force brute avec AES et une clef bien choisie).
En tous cas il peut trouver au moins une clef (il pourrait y en avoir
plusieurs) qui permet d'arriver à ce chiffré à partir de ce clair. Si le
message est assez long, il y a peu de chances qu'il y en ait plusieurs.
Ensuite, suivant l'algo utilisé, il peut y avoir des raccourcis qui
permettent d'éliminer certaines clefs, ou de ne pas faire la totalité du
chiffrement avant de se rendre compte qu'une clef donnée ne convient pas.

Maintenant le cas qui m'interesse encore plus, si ds le même enoncé que
precedemment, au lieu de connaitre le message en clair complet,
l'attaquant ne connait que le debut (par ex les 2 premiers octets) et la
taille du texte clair (par ex 16 octets) cela peut il egalement le mener
à la clé ?

Ca risque de le mener à une série de clefs possibles.

ou bien le fait de ne connaitre qu'une partie du texte clair,
ne sert a rien si elle est inférieur au bloc chiffré ? (ici 128 bits).

Ca permet d'éliminer des clefs dont on se rend compte que le résultat ne
correspond pas. Reste à savoir si ça en élimine assez pour que ce soit
utile, mais avec 2 octets sur 16 seulement, statistiquement, ça n'aide pas
beaucoup...

Jacques.
--
Interactive Media Factory
Création, développement et hébergement
de services interactifs: SMS, SMS+, Audiotel...
http://www.imfeurope.com/

Jacques Caron :

Si l'attaquant possède l'algo, le message chiffré, et le message
en clair, peut il en déduire automatiquement la clé dans le cas
d'AES s'il ne la connait pas ?

Dans le pire des cas, par la force brute, oui (mais ça risque de
prendre beaucoup de temps par la force brute avec AES et une clef
bien choisie).

Je pense que le préopinant voulait dire: "étant donnés une clef K et
un texte chiffré C, peut-on résoudre l'équation C®S(P,K) de la même
façon qu'on peut, sans faire une recherche exhaustive des clefs,
réoudre C=Vigenère(P,K) ?" (c'est impossible dans la pratique, car AES
est un algo beaucoup plus complexe que Vigenère, par exemple, et on ne
connaît pas de fonction simple réciproque d'AES, alors qu'il est
trivial d'inverser les algos simples comme Vigenère).

--
`cat ~/.signature`

Guillaume Kaddouch wrote:

Si l'attaquant possède l'algo, le message chiffré, et le message en
clair, peut il en déduire automatiquement la clé dans le cas d'AES s'il
ne la connait pas ?

Arriver à faire cela s'appelle une "attaque à texte clair connu", et un
algorithme de chiffrement n'est considéré comme de bonne qualité que
s'il y résiste parfaitement.

C'est évidemment le cas pour AES qui n'a pas de faiblesse connue.

Jean-Marc Desperrier :

Arriver à faire cela s'appelle une "attaque à texte clair connu", et
un algorithme de chiffrement n'est considéré comme de bonne qualité
que s'il y résiste parfaitement.

Et, mieux, il doit résister aux attaques à texte clair choisi.

--
`cat ~/.signature`

Bonjour,

une autre question théorique, dont la réponse est probablement evidente
pour les initiés.
Peut importe l'algorithme de chiffrement (aller, prenons AES ou
Blowfish), si avant de chiffrer le texte clair je le traduit en binaire,
et que je le chiffre après : est ce que la répétition de 1 et de 0
brouille le chemin et rend plus difficile la cryptanalyse, ou au
contraire l'aide-t-elle ?

Si cela complique la cryptanalyse (ce dont je doute, sinon cette methode
serait connue) l'avantage est il supérieur au fait de multiplier la
taille du message par 8 ? (ce qui est quand même un gros inconvénient).

Merci d'avance.
Cordialement,

Guillaume.

According to Guillaume Kaddouch <gkweb@wanadoo.fr>:

Peut importe l'algorithme de chiffrement (aller, prenons AES ou
Blowfish), si avant de chiffrer le texte clair je le traduit en
binaire, et que je le chiffre après : est ce que la répétition de 1 et
de 0 brouille le chemin et rend plus difficile la cryptanalyse, ou au
contraire l'aide-t-elle ?

Précisons : par définition, AES travaille sur des blocs de 128 bits,
donc, stricto sensu, du binaire. Je suppose que ce que vous voulez dire,
c'est que vous convertissez le texte clair en une suite de _caractères_
0 et 1, que vous représentez ensuite en binaire en associant à chaque 0
ou 1 son code ASCII (donc, respectivement, 00110000 et 00110001). Cette
conversion étend effectivement la taille du message d'un facteur 8 (ce
qui est habituellement rédhibitoire en soi).


À froid, je peux en dire deux choses :

1) Si cette conversion rend le message mesurablement plus difficile
à attaquer, alors c'est que le système de chiffrement d'origine
(l'algorithme, ou son emploi) ne valait pas un kopeck, et mieux vaut
commencer par arranger ça.

2) Cette conversion peut rendre le système de chiffrement plus _facile_
à attaquer s'il n'était déjà pas très bien fait à la base. Je pense
au mode de chiffrement ECB : le texte est découpé en blocs de la
taille voulue par l'algorithme (8 octets pour Blowfish, 16 octets pour
l'AES) et chaque bloc est chiffré indépendamment. Ce mode est rarement
recommandé parce que deux blocs clairs identiques donneront deux
blocs chiffrés identiques (pour la même clé) et que ça pourra se voir
par observation du texte chiffré. La conversion en "binaire" aggrave
fortement le problème : comme il n'y a que 256 suites possibles de
8 caractères 0 et 1, les risques d'avoir deux blocs identiques sont
grandement augmentés (pour l'AES, ça fait 65536 suites possibles de 16
caractères 0 et 1, ce qui n'est guère mieux).


En bref : bof.


--Thomas Pornin