md5 est il injectif?

According to Kevin Denis <kevin@alinto.comNOSPAM>:

une simple question:
md5 est il injectif?

Non, et ça se voit facilement : la sortie est plus courte que l'entrée.
Donc il y a plus d'entrées possibles que de sorties, donc fatalement il y
a plusieurs entrées qui ont la même sortie, ce qui contredit
l'injectivité.

Ceci étant :

C'est à dire, est on sur que tous les hashs possibles ont un fichier
source?

Ça, ce n'est pas l'injectivité mais la surjectivité. L'injectivité,
c'est que chaque élément de l'ensemble de sortie (ici les mots de 128
bits) a _au plus_ un antécédent (un message que MD5 hache pour obtenir
cette valeur de 128 bits). La surjectivité, c'est quand chaque élément
a _au moins_ un antécédent.

Il n'est pas prouvé que MD5 soit surjective. On s'attend à ce qu'une
bonne fonction de hachage soit surjective (ou peut s'en faut), mais ce
n'est pas complètement indispensable. Par exemple, si je prends SHA-512
et que je définis SHB-512 tel que SHB-512(m) = SHA-512(m) sauf si
SHA-512(m) = 0...0, où je pose alors SHB-512(m) = 1...1, alors cette
fonction SHB-512 reste une fonction de hachage très décente, et
néanmoins non surjective puisque par construction 0...0 n'a pas
d'antécédent par SHB-512.


Donc ce n'est pas très important que MD5 soit surjectif ou pas. Il
serait _surprenant_ que MD5 ne soit pas surjectif : a priori, vu la tête
de la fonction, comme elle n'a pas été spécialement étudiée pour ne pas
être surjective, elle devrait l'être. Mais par ailleurs on sait que MD5
n'est pas une si bonne fonction de hachage que ça, puisque des
collisions ont été trouvées...

Donc la surjectivité de MD5 est soupçonnée mais pas démontrée. Ce n'est
pas très important. Si on pouvait démontrer la surjectivité, alors ce
serait important : pas que la fonction soit surjective, mais qu'on ait
suffisamment analysé la structure pour pouvoir le démontrer. Ce serait
même louche. On en concevrait une certaine suspicion envers la fonction.
Mais de toutes façons, MD5 est très suspecte (suspecte depuis les
résultats partiels de Dobbertin en 1996, très suspecte depuis les
collisions exhibées par Wang en 2004).


On pourrait aussi dire que c'est une question de définition. Si on dit
que l'ensemble de sortie de la fonction, c'est l'ensemble des valeurs de
sortie possibles, alors la fonction est toujours surjective, par
définition. La question devient alors : est que l'ensemble de sortie de
MD5 est _exactement_ l'ensemble des mots de 128 bits, ou est-ce que
c'est un sous-ensemble strict ? Tout ça revient au même.

Enfin, les mêmes questions posée pour d'autres algorithmes de hachage
ont elles les mêmes réponses?

A priori, sauf construction ad hoc spécifique, une bonne fonction de
hachage devrait être surjective, et on s'attends à ce qu'on ne puisse
pas le démontrer.


--Thomas Pornin

Le 16-01-2009, Thomas Pornin <pornin@bolet.org> a écrit :

C'est à dire, est on sur que tous les hashs possibles ont un fichier
source?

Ça, ce n'est pas l'injectivité mais la surjectivité. L'injectivité,
c'est que chaque élément de l'ensemble de sortie (ici les mots de 128
bits) a _au plus_ un antécédent (un message que MD5 hache pour obtenir
cette valeur de 128 bits). La surjectivité, c'est quand chaque élément
a _au moins_ un antécédent.

Il n'est pas prouvé que MD5 soit surjective. On s'attend à ce qu'une
bonne fonction de hachage soit surjective (ou peut s'en faut), mais ce
n'est pas complètement indispensable. Par exemple, si je prends SHA-512
et que je définis SHB-512 tel que SHB-512(m) = SHA-512(m) sauf si
SHA-512(m) = 0...0, où je pose alors SHB-512(m) = 1...1, alors cette
fonction SHB-512 reste une fonction de hachage très décente, et
néanmoins non surjective puisque par construction 0...0 n'a pas
d'antécédent par SHB-512.


Donc ce n'est pas très important que MD5 soit surjectif ou pas. Il
serait _surprenant_ que MD5 ne soit pas surjectif : a priori, vu la tête
de la fonction, comme elle n'a pas été spécialement étudiée pour ne pas
être surjective, elle devrait l'être. Mais par ailleurs on sait que MD5
n'est pas une si bonne fonction de hachage que ça, puisque des
collisions ont été trouvées...

Donc la surjectivité de MD5 est soupçonnée mais pas démontrée. Ce n'est
pas très important. Si on pouvait démontrer la surjectivité, alors ce
serait important : pas que la fonction soit surjective, mais qu'on ait
suffisamment analysé la structure pour pouvoir le démontrer. Ce serait
même louche. On en concevrait une certaine suspicion envers la fonction.
Mais de toutes façons, MD5 est très suspecte (suspecte depuis les
résultats partiels de Dobbertin en 1996, très suspecte depuis les
collisions exhibées par Wang en 2004).


On pourrait aussi dire que c'est une question de définition. Si on dit
que l'ensemble de sortie de la fonction, c'est l'ensemble des valeurs de
sortie possibles, alors la fonction est toujours surjective, par
définition. La question devient alors : est que l'ensemble de sortie de
MD5 est _exactement_ l'ensemble des mots de 128 bits, ou est-ce que
c'est un sous-ensemble strict ? Tout ça revient au même.

Enfin, les mêmes questions posée pour d'autres algorithmes de hachage
ont elles les mêmes réponses?

A priori, sauf construction ad hoc spécifique, une bonne fonction de
hachage devrait être surjective, et on s'attends à ce qu'on ne puisse
pas le démontrer.


--Thomas Pornin

C'est très clair, brillament expliqué.
Merci. Beaucoup.
--
Kevin

Le (on) vendredi 16 janvier 2009 23:01, Thomas Pornin a écrit (wrote) :

Donc la surjectivité de MD5 est soupçonnée mais pas démontrée. Ce n'est
pas très important. Si on pouvait démontrer la surjectivité, alors ce
serait important : pas que la fonction soit surjective, mais qu'on ait
suffisamment analysé la structure pour pouvoir le démontrer.

Est-ce qu'on ne peut pas envisager, dans le cas où l'espace de sortie de la
fonction est assez petit (ici, 2^128 éléments) une preuve par force
brutale ? Mettons qu'on calcule l'image par md5 d'un grand nombre
d'éléments. Comme leurs images sont réparties uniformément par md5, on doit
pouvoir, en utilisant un nombre d'éléments suffisamment supérieur à 2^128,
avoir une probabilité élevée d'atteindre toutes les images possibles. (Il
faudrait faire le calcul pour savoir, en fonction de epsilon, combien
d'éléments utiliser pour avoir une probabilité 1 - epsilon d'atteindre
toutes les valeurs possibles.)

Si on arrive ainsi à atteindre les 2^128 images a priori possibles, on aura
démontré la surjectivité de md5, mais vraisemblablement pas compris grand
chose sur elle au passage.

Reste que je n'ai aucune idée de la puissance-temps de calcul que ça
demanderait.

Manuel.

According to mpg <mpg-news@elzevir.fr>:

Est-ce qu'on ne peut pas envisager, dans le cas où l'espace de sortie de la
fonction est assez petit (ici, 2^128 éléments) une preuve par force
brutale ?

Tout d'abord, disons tout net qu'une telle preuve ne marcherait que dans
un sens, i.e. prouver la surjectivité en montrant que tous les éléments
sont atteints. Si on n'a pas atteint tous les éléments, on ne sait pas
si ceux qui manquent sont inatteignables, ou simplement qu'on ne les a
pas atteints faute d'avoir suffisamment essayé.

Par ailleurs il faudra passer beaucoup de fois. Si l'ensemble de sortie
présumé est de taille N (ici, N = 2^128), que la fonction est vraiment
"aléatoire" (c'est ce qu'on attend d'une bonne fonction de hachage), et
qu'on essaye k*N entrées distinctes, alors la probabilité pour une
valeur de sortie possible de ne pas être obtenue est ((N-1)/N)^k*N (à
chaque essai, la probabilité de ne pas être obtenue est (N-1)/N, et ces
événements sont supposés indépendants). Cette probabilité est proche
de e^(-k) (pour N assez grand, ce qui est le cas ici).

Les chances d'obtenir avec succès une sortie donnée sont donc de 1-e^(-k).
Mais on veut un succès pour _toutes_ les sorties à la fois. En supposant
les succès des sorties indépendants les uns des autres (hypothèse hardie
et d'ailleurs fausse, mais on peut se convaincre que c'est une
approximation valide), ça veut dire que les chances de couvrir toutes
les sorties à la fois sont de (1-e^(-k))^N, soit environ e^(-N*e^(-k)).
Ou, dit autrement, il faudra que k soit de l'ordre de log N pour que
la preuve par recherche exhaustive ait des chances de succès (une
probabilité de succès de 1/e, soit environ 37%, pour k = log N, soit
environ 88.7).


En bref, une telle preuve nécessiterait dans les 88.7*(2^128) évaluations
de MD5, c'est-à-dire environ 3*10^40. C'est beaucoup.

À quel point est-ce beaucoup ? Évaluons donc ça, l'exercice est
instructif.

MD5 évalue son entrée par blocs de 64 octets. Quand l'entrée fait moins
de 64 octets, elle est étendue à 64 octets ("padding")(ou 128 octets),
donc dans le cas le plus favorable, chaque évaluation de MD5 porte sur
une bloc.

Soit maintenant un processeur classique, en l'occurrence un Intel Core2
Q6600 à 2.4 Ghz, avec quatre coeurs. Grâce aux millions d'exemplaires
vendus et à la puissance combinée des "forces du marché" et des
"économies d'échelle", ce genre de processeur offre un très bon rapport
puissance-prix. Et je m'en suis payé un hier. Regardons par ailleurs à
quelle vitesse cette machine fait du MD5. OpenSSL vient avec du code
assembleur optimisé à la main, et atteint un débit d'environ 424 Mo/s.
Mon propre code C, confié banalement à gcc, atteint 410 Mo/s. Avec des
blocs de 64 octets, ça donne environ 6.6 millions de blocs par seconde.
C'est sur un seul core, et il y en a quatre, donc 26.5 millions de blocs
par seconde pour le processeur complet.

Imaginons maintenant que je sois l'émir d'Abu Dhabi et que plutôt que de
me payer des footballeux brésiliens, je décide de faire des preuves de
surjectivité de MD5. Pour le prix d'un pousseur de ballon, je me dote
d'un petit million de PC avec le processeur Q6600 cité ci-dessus. Par ma
grande magnificence, je considère altièrement que tous les problèmes
pratiques sont résolus, notamment comment produire les 130 mégawatts que
mes joujoux consomment (et dissiper ces mêmes 130 MW qui sont devenus,
in fine, de la chaleur). Après tout, ça ne fait qu'un malheureux dixième
d'une centrale nucléaire de moyenne puissance. Donc, me voilà en
position de pondre mes 26.5*10^12 MD5 à la seconde.

Je dois en produire 3*10^40. Ce qui me prendra donc environ 1.1*10^27
secondes. Soit pas loin de 36 milliards de milliards d'années. Tout émir
que je sois, il me faudra bien blinder mon testament pour que mes
descendants lointains pensent à vérifier le résultat.


En bref, 88.7*2^128, c'est _énorme_. Et c'est heureux : 2^128, c'est
88.7 fois moins que ce qu'on envisage ici, mais ça _doit_ être beaucoup.
En effet, avec 2^128 évaluations, on peut obtenir une collision sur une
fonction de hachage ayant une sortie de 256 bits, par exemple SHA-256.
On peut aussi casser une clé de chiffrement AES. Et pour un effort
nettement moindre, on s'avale du RSA au petit déjeûner. Tout cela
serait, pour les systèmes actuellement en place, un ennui.

Et c'est une des raisons pour lesquelles on s'attend à ce qu'on n'est
pas de preuve de surjectivité. Une preuve "générique" serait beaucoup
trop coûteuse. Donc, si preuve il y a, c'est qu'elle n'est pas
générique, donc qu'elle exploite des caractéristiques spécifique de la
fonction de hachage considérée -- et une fonction de hachage, en tant
que fonction "aléatoire", ne devrait pas avoir de caractéristique
exploitable.


--Thomas Pornin

Thomas Pornin a écrit :


toujours aussi intéressant à lire

dit différemment
un hachage sert a vérifier l' intégrité d'un fichier
contrat code source etc
ce qui veut dire que les collisions ne sont pas très graves en tant
que telles elles sont inévitables

par contre une petite modification de fichier ne doit pas créer de
collision ou qu'une petite modification puisse être annulée par une
autre modif "cachée"

et là cela devient nettement moins facile



remy




--
http://remyaumeunier.chez-alice.fr/

remy wrote:

[...]
un hachage sert a vérifier l' intégrité d'un fichier

Non, pas un hachage "cryptographique"

[...]
ce qui veut dire que les collisions ne sont pas très graves en tant
que telles elles sont inévitables

>

par contre une petite modification de fichier ne doit pas créer de
collision ou qu'une petite modification puisse être annulée par une
autre modif "cachée"

Non plus. Les collisions sur un hachage "cryptographique" sont très
grave *quelle* que soit leur nature.

*Et* pourtant elles sont effectivement inévitables.

Le truc est que la propriété à respecter est que *le temps* nécessaire
pour trouver ne serait-ce qu'une seule et unique collision doit être
très fortement hors de portée des moyens informatiques dont on dispose.

Mais on considère une fonctione de hash comme cassée vis-à-vis d'un
usage en cryptographie dès lors qu'une seule collision a été trouvé,
quel que soit la méthode, quel que soit la nature de la collision.

En général on souhaite aussi que la seule méthode utilisable pour
trouver une collision soit la force brute, car si une autre méthode
existe, même si elle est pour l'instant hors de portée des moyens
informatiques dont on dispose, il est probable qu'elle soit améliorée et
qu'elle devienne ensuite atteignable par des moyens informatique
raisonnables.

Par exemple SHA-1 est dans ce cas. On a exhibé aucune collision jusqu'à
présent car c'est trop difficile en temps de calcul, mais on sait que
les attaques sur MD5 sont transposables au SHA-1, et que c'est donc pour
l'instant essentiellement le fait que pour autant le temps de calcul
reste trop important qui nous protège.

En fait, si quelqu'un arrive à transposer à SHA-1 les dernières avancées
sur le MD-5, ça deviendra très probablement faisable, mais à condition
de disposer de suffisament d'ordinateurs, soit un réseau de milliers,
dizaines de milliers d'ordinateurs, et un bon nombre de mois de calcul.

According to Jean-Marc Desperrier <jmdesp@alussinan.org>:

En fait, si quelqu'un arrive à transposer à SHA-1 les dernières avancées
sur le MD-5, ça deviendra très probablement faisable, mais à condition
de disposer de suffisament d'ordinateurs, soit un réseau de milliers,
dizaines de milliers d'ordinateurs, et un bon nombre de mois de calcul.

L'équipe de Rechberger (Université de Graz, en Autriche) a commencé,
d'ailleurs, et ils cherchent des volontaires :

http://boinc.iaik.tugraz.at/

C'est du bon gros calcul distribué avec un coût théorique en O(2^63),
donc très comparable au cassage par recherche exhaustive d'une clé RC5,
qui avait pris environ 10000 machines et 4 ans (mais c'était il y a
presque dix ans).

Notons que ces 2^63 sont nettement meilleurs que les 2^80 théoriques
pour une bonne fonction de hachage avec 160 bits de sortie : on a trouvé
des attaques sur SHA-1 exploitant des recettes similaires à ce qui s'est
fait sur MD5 (i.e., de la recherche de chemin différentiel). Pour le
moment, ces attaques sur SHA-1 restent théoriques, et Rechberger et son
équipe s'emploient à fabriquer le premier cas pratique.

Depuis quelques années déjà, on recommande de passer à SHA-2 (SHA-256 ou
SHA-512) pour tous nouveaux usages. Et les faiblesses annoncées de SHA-1
sont aussi un moteur de la compétition de sélection du futur SHA-3,
lancée il y a quelques mois (ce sera un standard américain, mais on
s'attend à ce que ça deviennent un standard mondial de fait).


--Thomas Pornin

Thomas Pornin <pornin@bolet.org> écrivait :

According to Jean-Marc Desperrier <jmdesp@alussinan.org>:

En fait, si quelqu'un arrive à transposer à SHA-1 les dernières avancées
sur le MD-5, ça deviendra très probablement faisable, mais à condition
de disposer de suffisament d'ordinateurs, soit un réseau de milliers,
dizaines de milliers d'ordinateurs, et un bon nombre de mois de calcul.

L'équipe de Rechberger (Université de Graz, en Autriche) a commencé,
d'ailleurs, et ils cherchent des volontaires :

http://boinc.iaik.tugraz.at/

C'est du bon gros calcul distribué avec un coût théorique en O(2^63),

euh, O(cste)=O(1), non ?



--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé

À (at) Tue, 20 Jan 2009 15:22:08 +0100,
Erwan David <erwan@rail.eu.org> écrivait (wrote):

Thomas Pornin <pornin@bolet.org> écrivait :

C'est du bon gros calcul distribué avec un coût théorique en O(2^63),

euh, O(cste)=O(1), non ?

O(cste) est bien du même ordre que O(1) mais pas strictement
égal.

Effectivement le coût théorique d'une recherche de collision sur SHA-1
(par un algorithme donné) est bien une constante... mais c'est une
constante *énorme* (2^63). ;-)

--
Paul Gaborit - <http://perso.enstimac.fr/~gaborit/>

Paul Gaborit <Paul.Gaborit@invalid.invalid> écrivait :

À (at) Tue, 20 Jan 2009 15:22:08 +0100,
Erwan David <erwan@rail.eu.org> écrivait (wrote):

Thomas Pornin <pornin@bolet.org> écrivait :

C'est du bon gros calcul distribué avec un coût théorique en O(2^63),

euh, O(cste)=O(1), non ?

O(cste) est bien du même ordre que O(1) mais pas strictement
égal.

Effectivement le coût théorique d'une recherche de collision sur SHA-1
(par un algorithme donné) est bien une constante... mais c'est une
constante *énorme* (2^63). ;-)

Oui, mais O(f(n)) signifie que lim(temps(programme)/f(n)) quand n tend
vers l'infini est une constante non nulle... Donc O(cste) signifie
(comme O(1)) que le programme s'exécute en temps constant, et ne donne
aucune information supplémentaire.

--
Le travail n'est pas une bonne chose. Si ça l'était,
les riches l'auraient accaparé