Oui, tout à fait. Mais à prirori, il faut essayer 2^{n/2} messages différents avant de trouver une collision (grace au paradoxe des anniversaires), et ça n'est pas faisable en pratique (on choisit n suffisament grand). Dans certaines preuves de sécurités, on suppose qu'il est impossible de trouver une collision dans la fonction de hachage utilisé, même si on sait qu'il en existe.
En fait ce qui passe avec SHA-1, c'est qu'on a une méthode pour trouver des collisions plus efficacement que ça, donc on considère que SHA-1 est cassée. Mais en fait, l'algo est en 2^{63} (pour l'instant ...) donc ça reste hors de portée, et on a pas de collisions connues dans SHA-1. Par contre, on en a pour MD4 et MD5.
[^] # Re: collisions...
Posté par newbix . En réponse à la dépêche Nouvelles fonctions de hachage. Évalué à 8.
En fait ce qui passe avec SHA-1, c'est qu'on a une méthode pour trouver des collisions plus efficacement que ça, donc on considère que SHA-1 est cassée. Mais en fait, l'algo est en 2^{63} (pour l'instant ...) donc ça reste hors de portée, et on a pas de collisions connues dans SHA-1. Par contre, on en a pour MD4 et MD5.