Print

Sujet 21: Fonctions de hachage

Table of contents

1. A traiter [edit]

2. Introduction [edit]

3. Présentation d'une fonction de hachage [edit]

3.1. Définition

3.2. Utilité

4. Exemples de fonction de hachage [edit]

4.1. MD5

4.1.1. Présentation

4.1.2. Construction

4.2. SHA - 1

4.2.1. Présentation

4.2.2. Exemple de message

5. Limitation [edit]

6. Références [edit]

Rédacteur: Lucile Favero Pistoresi

A traiter [edit]

  • Propriétés des fonctions de hachage (rapide à calculer, resistance à la préimage, résistance à la seconde préimage, résistance aux collisions)
  • Exemples (SHA?, construction impliquant le log discret [3]?)

Introduction [edit]

Bien qu’il existe deux types de fonction de hachage ; les fonctions cryptographiques et non cryptographiques ; ce résumé portera sur les fonctions de hachages cryptographiques.

Après une présentation de la fonction de hachage et de son utilité en cryptographie, nous nous intéresserons à des exemples de fonctions connues pour finalement mettre en évidence les limites de ces fonctions.

Présentation d'une fonction de hachage [edit]

Définition

C’est une fonction \(H\) qui a un message de taille arbitraire associe une image de taille fixe ( l’empreinte ou la signature) et possédant les propriétés suivantes :

  1. Rapidité : la valeur de \(H(m)\) est rapide à calculer.
  2. Résistance à la préimage : il est impossible, pour une valeur de hachage donnée, de construire un message ayant cette valeur de hachage ; la fonction de hachage ne fonctionne que dans un sens.
  3. Résistance à la seconde préimage : il est impossible pour un message donné \(m_1\) de trouver un message \(m_2\) de tel sorte que : \(H(m_1)=H(m_2)\)
  4. Résistance aux collisions : il est impossible de trouver deux messages différents ayant la même valeur de hachage.

Remarque : En pratique, de part le fait que l'on réduit l'espace d'arrivé de la fonction, la probabilité d'existence de collisions ( deux messages ayant la même empreinte) est non négligeable.

Utilité

Les fonctions de hachage sont utilisées pour comparer des données entre elles, à partir de leur signature. Cela garantit la non-modification (par erreur ou malveillance) des données.

Exemples de fonction de hachage [edit]

MD5

Présentation

La fonction MD5 (message digest 5) a été crée par le cryptologue Ronald Rivest, en 1991, et se base sur la construction de Merkle-Damgård.

Construction

Idée :

Le message est découpé en blocs de 512 bits et chaque bloc est traité par une fonction de compression. Celle-ci prend en entrée le bloc de 512 bits et une variable de 128 bits, et produit une empreinte de 128 bits.

Construction :

  • Pour le premier bloc du message, un vecteur d'initialisation de 128 bits est défini ( imposé par le standard). Puis on l'introduit avec le premier bloc dans la fonction de compression. L'empreinte de 128 bits retournée est transférée vers le deuxième bloc. Elle servira d'entrée pour appliquer la fonction de compression de ce deuxième bloc.
  • L'empreinte de 128 bits retournée par la fonction de compression du deuxième bloc va être utilisée pour la fonction de compression du troisième bloc et ainsi de suite. Chaque bloc est ainsi traité jusqu'au dernier bloc qui donne alors l'empreinte finale.

Remarque :

  • Si le message n'a pas suffisamment de bits pour remplir complètement le dernier bloc, on procède à un padding (remplissage).

SHA - 1

Présentation

SHA-1 (Secure Hash Algorithm) a été crée par la NSA et publiée par le NIST en 1995. Cette fonction ressemble à MD5 de par son fonctionnement qui se base, tout comme MD5, sur la construction de Merkle-Damgård et utilise des blocs de 512 bits. Néanmoins les empreintes sont plus longues : 160 bits. De plus SHA-1 serait plus sûre que MD5.

Exemple de message

message empreinte SHA-1
Fox dfcd3454bbea788a751a696c24d97009ca992d17
The red fox jumps over the blue dog 0fec050f02cd6201e2ef871ecf8f9d94c1dab7ae
The red fox jumps ouer the blue dog 2f8bd9c55cbcc17e96249174f4b8f513ef167519

Notons que :

  • Bien que les messages soient de tailles variables, l'empreinte a toujours la même taille.
  • En changeant une lettre dans le message, toute l'empreinte est modifiée.

Voici un lien vers un générateur d'empreinte SHA-1 : http://www.sha1-online.com/

Limitation [edit]

Plus haut, nous avons mentionné la relative résistance aux collisions des fonctions de hachage dans le cas pratique. Qu'en est-il du MD5 et du SHA-1 ?

En 2004, Xiaoyun Wang et son équipe (Dengguo Feng, Xuejia Lai et Hongbo Yu) ont découvert une collision complète du MD5. Actuellement, une recherche de collisions est envisageable en l'espace de quelques minutes sur un PC. Ainsi, d'un point de vu cryptographique, le MD5 n'est plus considéré comme sûr.

En ce qui concerne le SHA-1, l'équipe de Xiaoyun Wang a aussi découvert une collision complète. Néanmoins, elle reste théorique car nécessitant \(2^{69}\) opérations.

Ainsi l'utilisation de versions plus robustes comme SHA-256 ou SHA-512 est recommandée.

Remarque : A l'heure actuelle, nous ne connaissons pas de fonction de hachage prouvée sûre. Pour plus d'informations, https://fr.wikibooks.org/wiki/Les_fonctions_de_hachage_cryptographiques#Pr%C3%A9sentation_de_SHA-1

Références [edit]

[1] Lawrence C. Washington, Elliptic Curves: Number Theory and Cryptography, Section 6.5
[2] Yevgeniy Dodis, Introduction to cryptography, Lectures 10, 12
[3] Yevgeniy Dodis, Introduction to cryptography, Lecture 12, 4.3
[4] https://fr.wikibooks.org/wiki/Les_fonctions_de_hachage_cryptographiques