Fonctions de hachage

Une fonction de hachage permet d’associer une valeur numérique unique à n’importe quelle information stockée sous forme de bits. Le tableau suivant montre les valeurs de hachage MD5 pour des mots, des phrases ou des valeurs numériques :

Ici, les valeurs de hachage sont représentées en hexadécimal (comme chacune comprend 32 caractères, à 4 bits par caractère, on en déduit que MD5 donne des « empreintes numériques » de 128 bits).

Les fonctions de hachage ont les propriétés suivantes :

• Taille constante: Peu importe la taille du message original, une fonction de hachage donnée donnera un nombre dont la taille en bits sera toujours la même (128 bits pour MD5, 160 bits pour SHA-0 et SHA-1, 256 bits pour SHA-256, etc.).

• Déterministes: Une valeur d’entrée produira toujours la même valeur de sortie.

• Sans collisions, à date: Deux valeurs d’entrées différentes n’ont jamais produit la même valeur de sortie jusqu’à maintenant, la probabilité d’une collision est de 1 / 2^256.

• Irréversibles: Il est impossible de calculer la valeur d’entrée à partir de la valeur de sortie.

• Uniformes: Les résultats doivent être uniformément distribués dans les valeurs possibles.

• Pseudo-aléatoires: Toute variation dans la valeur d’entrée doit avoir un impact important dans le résultat.

De nombreux algorithmes de hachage satisfont ces propriétés; certains d’entre eux (MD5, SHA1, SHA256, etc.) sont disponibles sous linux à partir de la ligne de commande.

olivier@ubusrv:~$ echo "allo" | md5sum
d40ea526169cb99ec8b81ff4d60ebd78  -

olivier@ubusrv:~$ echo "allo" | sha1sum
69faafb743f087d1306010b7f301dd509e9703e0  -

olivier@ubusrv:~$ echo "allo" | sha256sum
1ddfb769eb0b8876bc570e25580e6a53afcf973362ee1ee4b54a807da2e5eed7  -

Applications des fonctions de hachage

Les propriétés des fonctions de hachage font qu’on les utilise dans de nombreux contextes en informatique :

• Validation de l’intégrité (“checksum”): Lors de la transmission d’un message, l’expéditeur fournit l’empreinte du message ; ainsi le destinataire peut lancer la fonction de hachage lors de la réception du message et en comparant les deux empreintes, vérifier que le message a bien été transmis.

• Structures de données (“hashtables”): En programmation, pour des données représentées en paires « clé-valeur » (par exemple, une adresse courriel et le nom de son propriétaire), on stocke les valeurs à des adresses mémoire correspondant aux empreintes des clés hachées auxquelles elles sont associées.

• Mots de passe: Stocker les empreintes des mots de passe permet d’avoir l’assurance que leurs valeurs ne pourraient pas être décryptées si elles venaient à être divulguées.

Par exemple, dans le fichier /etc/shadow sur Linux, les champs sont les suivants :

1. Fonction de hachage – 6 désigne l’algorithme SHA-512
2. Sel cryptographique – une valeur numérique (représentée en base-64) qui est ajoutée au mot de passe entré par l’utilisateur lors du calcul de l’empreinte. Permet de bloquer les attaques par « rainbow tables » car les empreintes qui auraient été calculées à l’avance pour des milliards de mots de passe possibles ne correspondront jamais à l’empreinte du mot de passe « salé ».
3. Empreinte du mot de passe – le résultat de la fonction de hachage (en base-64) appliquée sur le mot de passe de l’utilisateur + le sel cryptographique
4. Date du dernier changement de mot de passe en nombre de jours depuis le 1er janvier 1970.
5. Nombre de jours minimum entre deux changements de mots de passe pour un utilisateur.
6. Nombre de jours maximum entre deux changements de mot de passe (= durée de validité).
7. Nombre de jours précédant la fin de validité du mot de passe durant lesquels l’utilisateur sera prévenu qu’il doit le renouveler.

Validation de l’identité

Les signatures numériques sont une technique qui permet (un peu comme une signature « manuelle ») d’attester que le contenu d’un message provient bel et bien d’un expéditeur donné, et que ce contenu n’a pas été altéré entre sa source et sa destination. Elles utilisent à la fois le chiffrement et le hachage ; cependant, le message lui-même n’a pas besoin d’être chiffré : c’est la signature qu’on lui ajoute qui l’est.

Dans une signature numérique, on inverse les rôles de la clé privée et de la clé publique, c’est-à-dire qu’on chiffre avec la clé privée et qu’on déchiffre avec la clé publique. En effet, si on reçoit des données chiffrées et qu’on arrive à les déchiffrer avec la clé publique de A, on peut supposer que c’est bien A qui nous a envoyé ces données, partant du principe que seul A dispose de la clé privée qui a permis de les chiffrer.

Supposons que A et B ont déjà échangé leurs clés publiques. Par la suite, B veut s’assurer que les messages qu’il reçoit proviennent bel et bien de A et n’ont pas été modifiés durant la transmission.

Lorsqu’il envoie son message, A appliquera alors la démarche suivante:

1. A génère une empreinte E de son message M

2. A utilise sa clé privée pour chiffrer cette empreinte. C’est cette empreinte chiffrée qui constitue la signature; A la joint à son message

Pour vérifier l’authenticité du message, B appliquera la procédure suivante:

3. B utilise la clé publique de A pour déchiffrer l’empreinte E

4. B génère sa propre empreinte du message

5. B compare les deux empreintes; si elles sont identiques, alors le message n’a pas été modifié (les empreintes le prouvent) et il provient bien de A (le déchiffrement de la signature le prouve).