Multicollision
Une multicolision se produit lorsque k entrées distinctes d'une fonction de hachage correspondent à la même valeur de hachage ; Joux l'a introduite pour analyser la sécurité des fonctions itérées.
Objectif
Elle analyse la dégradation de sécurité des fonctions de hachage itérées (Merkle-Damgård) face aux multicolisions, avec des conséquences pour les conceptions de hachage en cascade.
Mécanisme
Joux a montré que pour un hachage itéré de n bits, construire une collision à 2^k branches ne coûte que k×2^(n/2) opérations, donc la mise en cascade de deux hachages de n bits n'offre qu'une sécurité de 2^(n/2)+2^(n/2) au lieu de 2^n.
Cas d’usage
- Analyse de sécurité des hachages itérés
- Évaluation de sécurité des hachages en cascade
- Conception de fonctions de hachage