Vous avez déjà entendu parlé de fonctions de hachage et vous ne savez pas ce que c'est ? Je vais essayer de tout vous expliquer dans la suite de ce cours, sans pour autant embrumer votre cerveau d'obscures formules mathématiques.
Qu'est-ce qu'une fonction de hachage ?
Le concept de fonction de hachage est plutôt simple. Il s'agit d'une fonction mathématique qui à partir d'une donnée de taille arbitraire fournie en entrée, produit une sortie de taille fixe.
La donnée en entrée (appelé message) est en binaire (voir le cours sur la représentation de l'information), cela peut donc être du texte, une image, une vidéo, une archive ZIP, etc.
La sortie de taille fixe (appelé haché ou empreinte) est également en binaire, pour plus de lisibilité lors de l'affichage, on la représente souvent sous forme hexadécimal.
La fonction quant à elle peut être librement définie, il en existe des milliers. Elle peut être très simple (une fonction où le haché serait les 10 premiers caractères d'un message) ou plus compliqué (construction de Merkle-Damgård).
Comme la taille d'un message en entrée est variable (donc potentiellement infinie) et que la taille d'un haché en sortie est fixe, on se rend vite compte qu'il peut y avoir certains messages qui, bien que différents, auront le même haché : lorsque cela arrive, on parle de collision. C'est par exemple le cas dans l'illustration précédente où le premier élément (l'image) et le dernier (la vidéo) aboutissent au même haché.
Applications
Stockage de mots de passe
Sommes de contrôle (checksums)
Signatures numériques
Tables de hachage
Propriétés nécessaires à la cryptographie
Pour qu'une fonction de hachage puisse être utilisé en cryptographie, elle a besoin de satisfaire au moins 3 propriétés dont voici un aperçu.
Résistance à la préimage
La première propriété à satisfaire s'appelle la résistance à la préimage. Une fonction satisfait cette propriété s'il est difficile, en ayant un haché, de trouver un message correspondant.
Autrement dit, pour tout haché h, il doit être difficile de trouver m tel que hachage(m) = h. Par exemple, imaginons que l'on nous donne le haché "5baa61e4c9b93f3f". Une attaque sur la préimage consiste à trouver un message qui lorsqu'on la passe en entrée d'une fonction de hachage nous donne ce haché.
Résistance à la seconde préimage
La deuxième propriété est la résistance à la seconde préimage. Pour satisfaire cette propriété, il faut qu'en ayant un message, il soit difficile d'en trouver un deuxième différent dont le haché est le même.
Autrement dit, pour tout message m1, il doit être difficile de trouver un message m2 différent de m1 tel que hachage(m1) = hachage(m2). Par exemple, imaginons que l'on ait le message "Bonjour à tous !" associé au haché "a765d61d8". Une attaque sur la seconde préimage consiste à trouver un message différent correspondant à ce haché.
Résistance aux collisions
La troisième propriété est la résistance aux collisions (on a vu ce terme dans le première partie). Il doit être difficile de trouver 2 messages différents aboutissant au même haché.
Autrement dit, il doit être difficile de trouver une paire de messages (m1, m2) tel que hachage(m1) = hachage(m2).