une simple question:
md5 est il injectif?
C'est à dire, est on sur que tous les hashs possibles ont un fichier
source?
Enfin, les mêmes questions posée pour d'autres algorithmes de hachage
ont elles les mêmes réponses?
une simple question:
md5 est il injectif?
C'est à dire, est on sur que tous les hashs possibles ont un fichier
source?
Enfin, les mêmes questions posée pour d'autres algorithmes de hachage
ont elles les mêmes réponses?
une simple question:
md5 est il injectif?
C'est à dire, est on sur que tous les hashs possibles ont un fichier
source?
Enfin, les mêmes questions posée pour d'autres algorithmes de hachage
ont elles les mêmes réponses?
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 à 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 à 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
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.
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.
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 ?
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 ?
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 ?
[...]
un hachage sert a vérifier l' intégrité d'un fichier
[...]
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"
[...]
un hachage sert a vérifier l' intégrité d'un fichier
[...]
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"
[...]
un hachage sert a vérifier l' intégrité d'un fichier
[...]
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"
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.
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.
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 :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),
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),
According to Jean-Marc Desperrier :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),
Thomas Pornin écrivait :C'est du bon gros calcul distribué avec un coût théorique en O(2^63),
euh, O(cste)=O(1), non ?
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 ?
Thomas Pornin écrivait :C'est du bon gros calcul distribué avec un coût théorique en O(2^63),
euh, O(cste)=O(1), non ?
À (at) Tue, 20 Jan 2009 15:22:08 +0100,
Erwan David écrivait (wrote):Thomas Pornin é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). ;-)
À (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). ;-)
À (at) Tue, 20 Jan 2009 15:22:08 +0100,
Erwan David écrivait (wrote):Thomas Pornin é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). ;-)