différenciation aléatoire / chiffré

Kevin Denis wrote:

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Est ce que quelqu'un dispose d'un pointeur vers une doc
"officielle" affirmant ce point? Je suis assez d'accord avec ce
principe, mais je ne trouve pas de justificatif style document
de l'ANSSI ou équivalent.

Ce n'est pas une doc officielle, mais tu n'auras plus de doute sur
la réponse après avoir lu (et compris) ça :

http://www.cacr.math.uwaterloo.ca/hac/

Le 16/05/2010 16:56, Stephane CARPENTIER a fait rien qu'à écrire :

Kevin Denis wrote:

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Ben, en fait, c'est tout simple: si un algorithme de chiffrement
laisse des caractéristiques statistiques, reconnaissables faci-
lement et/ou différentes de celles d'un flux aléatoire, c'est
une faiblesse.

ENfin, ça permet au moins de le reconnaitre, et c'est déja ça..

Est ce que quelqu'un dispose d'un pointeur vers une doc
"officielle" affirmant ce point? Je suis assez d'accord avec ce
principe, mais je ne trouve pas de justificatif style document
de l'ANSSI ou équivalent.

En lâchant "crypt random distinguisher" dans un moteur, ça remonte
plein de trucs, de quoi se faire une idée:
distinguishing attack on ZK-Crypt cipher
Most Efficient Distinguishing Attack on VMPC and RC4A
Distinguishers Based on Random Mappings against Stream Ciphers

Ce n'est pas une doc officielle, mais tu n'auras plus de doute sur
la réponse après avoir lu (et compris) ça :

http://www.cacr.math.uwaterloo.ca/hac/

..je sais pas si le monsieur, il va se fader 800 pages
d'algorithmes en tous genre pour trouver réponse à sa
question ?..


--
christophe.

xtof.pernod wrote:

Le 16/05/2010 16:56, Stephane CARPENTIER a fait rien qu'à écrire :

Kevin Denis wrote:

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Ben, en fait, c'est tout simple: si un algorithme de chiffrement
laisse des caractéristiques statistiques, reconnaissables faci-
lement et/ou différentes de celles d'un flux aléatoire, c'est
une faiblesse.

ENfin, ça permet au moins de le reconnaitre, et c'est déja ça..

Bonjour,

Une petite astuce à ce propos d'ailleurs: vu ces propriétés, il est
assez facile de savoir si un algorithme de chiffrement est de mauvaise
qualité... Il suffit de tenter de compresser le chiffré: si le fichier
résultant est sensiblement plus petit, c'est bien qu'il restait des
choses pas vraiment totalement aléatoires dans le fichier chiffré avant
compression (restes de structures ou autres)...

On ne peut malheureusement rien déduire dans le cas inverse: une absence
de compression ou une compression très faible du chiffré n'implique pas
forcément un bon algo, il y a d'autres failles potentielles. ;-)

Cordialement,

Bruno

xtof.pernod wrote:

Le 16/05/2010 16:56, Stephane CARPENTIER a fait rien qu'à écrire :

Ce n'est pas une doc officielle, mais tu n'auras plus de doute sur
la réponse après avoir lu (et compris) ça :

http://www.cacr.math.uwaterloo.ca/hac/

..je sais pas si le monsieur, il va se fader 800 pages
d'algorithmes en tous genre pour trouver réponse à sa
question ?..

Il veut une doc, je lui donne une doc.

J'espère que le monsieur est capable de lire une table des
matières pour savoir ce qui l'intéresse dans un livre. Il n'a
pas besoin de tout lire pour avoir une réponse.

Le 19/05/2010 08:30, Bruno Tréguier a fait rien qu'à écrire :

xtof.pernod wrote:

Kevin Denis wrote:

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Tiens, ça vient de me revenir: j'avais vu passer un papier
sur un "distingueur" entre un flux ''aléatoire'' et un flux
codé par rc4.

Somme toute assez théorique, je crois qu'il nécessitait
quelque chose comme 2^50 bits de flux chiffré.

Mais il disait de manière déterministe:
"Ce flux n'a pas pu être chiffré par rc4"


On peut supposer que pour (presque) tous les algorithmes de
chiffrement [par blocs], on peut concevoir un algorithme
qui distingue un flux chiffré par cet algo. de tout autre flux..

C'était : 2 sous de conjecture de tôt-le-matin.

(...)

ENfin, ça permet au moins de le reconnaitre, et c'est déja ça..

Bonjour,

Une petite astuce à ce propos d'ailleurs: vu ces propriétés, il est
assez facile de savoir si un algorithme de chiffrement est de mauvaise
qualité... Il suffit de tenter de compresser le chiffré: si le fichier
résultant est sensiblement plus petit, c'est bien qu'il restait des
choses pas vraiment totalement aléatoires dans le fichier chiffré avant
compression (restes de structures ou autres)...

Absolument ! En effet, ca permet par ex. de "tauper":
. les "chiffrements" par substitution (ne changent pas les fréquences =>
aussi compressibles qu'un fichier texte)
. les "chiffrements" par OU exclusif entre une clé binaire de longueur N
et un texte quelconque

. etc..

On ne peut malheureusement rien déduire dans le cas inverse: une absence
de compression ou une compression très faible du chiffré n'implique pas
forcément un bon algo, il y a d'autres failles potentielles. ;-)

Cordialement,

Bruno

Eh oui. Sinon ça serait trop facile =)
--
christophe.

Kevin Denis wrote:

Bonjour,

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Est ce que quelqu'un dispose d'un pointeur vers une doc
"officielle" affirmant ce point? Je suis assez d'accord avec ce
principe, mais je ne trouve pas de justificatif style document
de l'ANSSI ou équivalent.

Ca avait été un point important de l'évaluation des candidats AES, voir
http://csrc.nist.gov/publications/nistir/ir6390.pdf pour le rapport émit
à l'époque sur les candidats. Si je me rappelle bien ça avait été
instrumental dans l'élimination de deux favoris, RC6 et Twofish.

According to Bruno Rohee <bruno+fmc@rohee.com>:

Si je me rappelle bien ça avait été instrumental dans l'élimination de
deux favoris, RC6 et Twofish.

Pas que je sache. Ces déviations n'étaient pas significatives. L'idée
générale est que quand on fait cent tests, ben il est normal de voir
apparaître quelques résultats rares, le genre qui n'arrive qu'une fois
sur cent.

Ce rapport a été fait pendant le round 1, et n'a pas empêché RC6 et
Twofish d'être sélectionnés pour le round 2.


Pour ce qui est de l'indistinguabilité : on attend d'un bon chiffrement
par block d'être indistinguable d'une permutation aléatoire. Il faut
imaginer le scénario suivant : on fabrique deux boîtes opaques. L'une
des deux implémente un block cipher avec une clé fixée mais inconnue.
L'autre choisit une permutation aléatoire parmi les (2^128)! possibles
(une façon de l'émuler est de faire une boîte qui choisit aléatoirement
la sortie, en notant ses sorties précédentes, pour redonner la même
valeur si on lui redonne la même entrée, mais pas sur une entrée
différente). Chaque boîte accepte donc des entrées (des mots de 128
bits) et fournit à chaque fois la sortie correspondante. Le but est
alors de deviner laquelle des deux boîtes utilise l'algorithme de
chiffrement.

Pour un bon algorithme de chiffrement, les chances de succès (deviner
correctement la boîte) ne doivent pas différer substantiellement de 1/2
(le "substantiellement" se quantifie en fonction de la puissance de
calcul accessible, et du nombre de requêtes aux boîtes). Nous parlons
ici d'un attaquant qui sait pertinemment que la boîte qu'il cherche
implémente un algorithme qu'il connaît ; seule la clé lui est inconnue.

Les tests faits par le NIST sont "génériques". C'est le cas restreint
d'un attaquant qui ne connaît même pas l'algorithme de chiffrement. Ces
tests ne sont censés détecter que les déviations flagrantes avec le
modèle de la permutation aléatoire. On s'attendait à ce qu'aucun des
candidats AES ne montre de telle déviation flagrante, et c'est le cas ;
le NIST monte un peu en épingle quelques fluctuations qui sont
statistiquement attendues, parce qu'il fallait bien mettre quelque chose
dans le rapport (la conclusion du rapport l'admet d'ailleurs assez
volontiers). L'opinion générale était que c'était bien que quelqu'un se
colle à faire ces tests statistiques, ne serait-ce que pour des raisons
pédagogiques, mais par ailleurs il aurait fallu qu'un candidat soit fort
mal conçu pour être cassé avec ce genre de tests statistique. Ce que ces
tests montrent, c'est que les candidats AES étaient tous "sérieux".

(Si on fait un parallèle avec la compétition SHA-3, on ne peut que
spéculer sur les 13 candidats rejetés avant le round 1 -- le NIST ayant
reçu 64 embryons de candidats mais seulement 51 dossiers "recevables".)


In fine, il y a eu deux candidats AES avec des attaques "académiques"
(du genre en 2^90, ce qui est infaisable mais quand même moins que
2^128). Le reste de la sélection s'est fait surtout sur des questions de
performance, et sur du "feeling" (avec des sondages des participants
pendant les conférences AES, d'ailleurs).


--Thomas Pornin

Le 15/05/2010 15:38, Kevin Denis a fait rien qu'à écrire :

Bonjour,

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Est ce que quelqu'un dispose d'un pointeur vers une doc
"officielle" affirmant ce point? Je suis assez d'accord avec ce
principe, mais je ne trouve pas de justificatif style document
de l'ANSSI ou équivalent.

Tiens, un truc tout bête: en lâchant "distinguisher" dans un
moteur de recherche quelconque, ça remonte quelques dizaines
de mille de résultats ; le mot doit exister depuis un certain
temps.

Avec "distingueur", qui a du être néologisé que très récemment,
ça donne quelques centaines de résultats, en français et en
rapport avec la crypto. (la science a progressé, d'ailleurs..)


::

Resoolts 1 - 30 ooff ebuoot 878 fur distingueur
Resoolts 1 - 30 ooff ebuoot 47,400 fur distinguisher

Web results 1-10 of 143 for distingueur
Web results 1-10 of 12,419 for distinguisher

::


Etonnant, non.

--
christophe.

Kevin Denis wrote in message
<slrnhut9ce.3h7.kevin@slackwall.local.tux>:

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Dit comme cela, ça ne s'applique en tout cas pas au chiffrement à clef
publique. Pour la plupart des chiffrements à clef publique usuels, il
existe un distingueur trivial entre une chaîne de bits aléatoire et un
chiffré valide : par exemple un chiffré RSA ou El-Gamal est inférieur au
module (public), un point sur une courbe elliptique est effectivement sur
la courbe, etc. Ce n'est pas une faiblesse.

La notion de sécurité pertinente dans ce cadre est celle de sécurité
sémantique : elle dit que si un adversaire choisit deux messages et qu'il
obtient un chiffré de l'un des deux, il ne doit pas pouvoir déterminer
lequel[*]. Ça implique en particulier qu'un chiffré d'un message précis est
indistinguable d'un *chiffré* d'un aléa, mais le fait que les chiffrés
soient représentés par des chaînes de bits non aléatoires n'est pas un
problème.


[*] Bien entendu, un algorithme de chiffrement déterministe ne peut pas
être sémantiquement sûr, donc est forcément « mauvais ».

Le 21/05/2010 16:16, Mehdi Tibouchi a fait rien qu'à écrire :

Kevin Denis wrote in message
<slrnhut9ce.3h7.kevin@slackwall.local.tux>:

j'ai souvent lu qu'un critère pour un bon chiffrement repose
sur le fait qu'il ne doit pas être possible de différencier de
l'aléatoire du chiffré.

Dit comme cela, ça ne s'applique en tout cas pas au chiffrement à clef
publique. Pour la plupart des chiffrements à clef publique usuels, il
existe un distingueur trivial entre une chaîne de bits aléatoire et un
chiffré valide :

Dans le cas 'trivial', il faut disposer de 2 textes chiffrés et de la
clé publique, non ?

Si on a pas tout ça, existe-t-il un algorithme qui réponde avec
certitude (ou un peu moins ..) "ce flux n'a pas été chiffré par
RSA (ou équivalent)" ?

par exemple un chiffré RSA ou El-Gamal est inférieur au
module (public), un point sur une courbe elliptique est effectivement sur
la courbe, etc. Ce n'est pas une faiblesse.
(...)

--
chirstophe.