Beaucoup de monde semble considérer ce post comme "pertinent", mais n'empêche que c'est faux aussi :)
Certes, une fonction associant à un ensemble de 256^n éléments, un élément pris parmi un ensemble de 2^128 éléments, n'a aucune chance d'être injective. Ce qui veut dire qu'il existe, forcément, des collisions.
Par contre, là où tu te trompes, c'est avec cette histoire de "sens informatique". Déjà, ça ne veut rien dire. Ensuite, il est assez facile de prouver que, pour la plupart des formats de fichiers donnés (voire même, pour tous ceux que je connais), il y a au moins deux fichiers valides qui ont le même hash, et même, pour un fichier donné, il y a forcément un fichier valide, mais différent, qui a le même hash.
Prenons, par exemple, un programme en C. Genre, un hello world (1):
int main() {
printf("Hello, world\n");
}
Prenons ensuite le programme suivant (2):
int main() {
char *u = "zhbvatvyvropeituuuuuuiuiu1337eoprjrnhiziopjpoerjiztopijgreopig";
printf("Goodbye, world\n");
}
Bien sûr, j'ai mis u au pif. Des combinaisons pour u, il y en a énormément, aussi. Si u est plus grand que la taille du hash, paf! on est plus injectif. Il y a forcément deux programmes (2) qui ont le même hash.
Si u est beaucoup plus grand que la taille du hash, et qu'on considère que la répartition est homogène, il y a même forcément un programme (2) qui a le même hash que le programme (1).
Ce qui fait qu'un hash est sûr, c'est non pas l'impossibilité théorique de la collision, mais l'impossibilité pratique de trouver deux messages en collision.
Dans l'exemple que je cite, en testant toutes les valeurs possibles de la chaîne de caractères u, je devrais pouvoir arriver à avoir n'importe quel hash à la fin. Mais ça veut aussi dire que, pour un hash de 128 bits, je devrai en moyenne en tester 2^127 afin d'arriver à mes fins, ce qui est censé être hors de portée, en un temps raisonnable, des moyens de calcul actuels. Si on veut "cracker" un hash, on a donc deux solutions:
* Soit avoir des moyens de calculs supérieurs aux moyens de calcul actuel
* Soit trouver une méthode pour avoir moins de 2^127 combinaisons possibles à tester
La deuxième méthode revient à trouver des faiblesses dans l'algorithme: si on trouve un moyen d'avoir des informations sur le message haché à partir du hash, alors on pourra exclude des combinaisons sans avoir à calculer leur hash. Si on arrive à trouver suffisamment de faiblesses dans l'algorithme, on peut revenir à un nombre de calculs accessible.
[^] # Re: MD5, un algo de cryptage ?
Posté par Gruik Man . En réponse au journal Deux Cryptage cassé ???. Évalué à 7.
Certes, une fonction associant à un ensemble de 256^n éléments, un élément pris parmi un ensemble de 2^128 éléments, n'a aucune chance d'être injective. Ce qui veut dire qu'il existe, forcément, des collisions.
Par contre, là où tu te trompes, c'est avec cette histoire de "sens informatique". Déjà, ça ne veut rien dire. Ensuite, il est assez facile de prouver que, pour la plupart des formats de fichiers donnés (voire même, pour tous ceux que je connais), il y a au moins deux fichiers valides qui ont le même hash, et même, pour un fichier donné, il y a forcément un fichier valide, mais différent, qui a le même hash.
Prenons, par exemple, un programme en C. Genre, un hello world (1):
int main() {printf("Hello, world\n");
}
Prenons ensuite le programme suivant (2):
int main() {char *u = "zhbvatvyvropeituuuuuuiuiu1337eoprjrnhiziopjpoerjiztopijgreopig";
printf("Goodbye, world\n");
}
Bien sûr, j'ai mis u au pif. Des combinaisons pour u, il y en a énormément, aussi. Si u est plus grand que la taille du hash, paf! on est plus injectif. Il y a forcément deux programmes (2) qui ont le même hash.
Si u est beaucoup plus grand que la taille du hash, et qu'on considère que la répartition est homogène, il y a même forcément un programme (2) qui a le même hash que le programme (1).
Ce qui fait qu'un hash est sûr, c'est non pas l'impossibilité théorique de la collision, mais l'impossibilité pratique de trouver deux messages en collision.
Dans l'exemple que je cite, en testant toutes les valeurs possibles de la chaîne de caractères u, je devrais pouvoir arriver à avoir n'importe quel hash à la fin. Mais ça veut aussi dire que, pour un hash de 128 bits, je devrai en moyenne en tester 2^127 afin d'arriver à mes fins, ce qui est censé être hors de portée, en un temps raisonnable, des moyens de calcul actuels. Si on veut "cracker" un hash, on a donc deux solutions:
* Soit avoir des moyens de calculs supérieurs aux moyens de calcul actuel
* Soit trouver une méthode pour avoir moins de 2^127 combinaisons possibles à tester
La deuxième méthode revient à trouver des faiblesses dans l'algorithme: si on trouve un moyen d'avoir des informations sur le message haché à partir du hash, alors on pourra exclude des combinaisons sans avoir à calculer leur hash. Si on arrive à trouver suffisamment de faiblesses dans l'algorithme, on peut revenir à un nombre de calculs accessible.