Difference between revisions of "VT2021 Merkle Trees fiche"

From air
Jump to navigation Jump to search
Line 1: Line 1:
<pre style="color: red">⚠️ Cette page est en cours d'édition et de ce fait beaucoup d'informations sont encore manquantes... ⚠️</pre>
+
<pre style="color: red">⚠️ Cette page est en cours de construction et de ce fait beaucoup d'informations sont encore manquantes... ⚠️</pre>
   
 
Présenté par :
 
Présenté par :
Line 20: Line 20:
 
== Fonctionnement ==
 
== Fonctionnement ==
   
  +
=== Principe ===
Les arbres de Merkle sont des structure de données organisées en arbres (binaires en général) utilisées pour effectuer de la vérification de données sur Internet. Chaque noeud de l'arbre va contenir un hachage différent. Le hachage pour un noeud est obtenu en concaténant le hashage de ses deux enfants et en passant le résultat dans une fonction de hashage. Il se construit donc une dépendance général ou la valeur de chaque noeud dépend de ses noeuds enfants. Les feuilles de l'arbre vont contenir le hachage correspondant aux données que l'on cherche à valider.
 
  +
  +
[[File:Merkle_Tree.png|300px|thumb|right|Simple Merkle Tree]]
  +
 
Les arbres de Merkle sont des arbres binaires utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque noeud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale la valeur de chaque noeud dépend des valeurs de ses noeuds enfants.
  +
  +
L'image ci-dessous contient un arbre de Merkle servant à valider une donnée découpée en quatre blocs (Data Nodes). Les feuilles de l'abre (Merkle leaves) vont contenir le hachage correspondant pour chaque bloc. Les noeuds intermédiaires (Merkle branches) vont contenir le hachage issu de la concaténation des hachages de leurs deux enfants. Enfin, la racine de l'arbre (Merkle root) va contenir le hachage final servant à identifier l'arbre de Merkle.
  +
  +
  +
   
[[File:Merkle_Tree.png]]
 
   
 
=== Un point sur le hachage ===
 
=== Un point sur le hachage ===
   
  +
Avant de s'immiscer dans le fonctionnement des arbres, il est important de parler du hachage et plus particulièrement des fonctions de hachage.
En cryptographie, une fonction de hachage est une fonction qui, à partir d'une donnée fournie en entrée, va être capable de calculer une empreinte numérique qui va permettre d'identifier rapidement la donnée initiale. La taille en sortie de cette empreinte est fixe et ne dépend pas de la taille de la donnée en entrée. Ce qui fait la puissance et la fiabilité d'une fonction de hachage c'est l'incapacité de remonter à la donnée initiale à partir de son empreinte. Il est donc pour une donnée en entrée, très simple de calculer son hachage, alors qu'il est mathématiquement extrêmement compliqué de remonter d'un hachage à la donnée source. Une utilisation notable du hachage de nos jours va être pour le stockage de mots de passe. Lors d'une inscription sur un site Web, on ne va directement stocker le mot de passe en clair dans une base de données. A la place, on va calculer le hachage du mot de passe et c'est cela que l'on va stocker dans la base. A chaque fois que l'on voudra s'authentifier sur le dit site en rentrant le mot de passe, le hachage sera calculé et comparé à celui présent dans la base de données. Si les deux sont égaux, alors il s'agit du bon mot de passe. On peut donc vérifier qu'un mot de passe est valide sans l'avoir stocker dans la base au préalable, ce qui sécurise d'avantage les comptes utilisateurs.
 
  +
  +
En cryptographie, une fonction de hachage est une fonction qui, à partir d'une donnée fournie en entrée, va être capable de calculer une empreinte numérique qui va permettre d'identifier rapidement la donnée initiale. La taille en sortie de cette empreinte est fixe et ne dépend pas de la taille de la donnée en entrée. Par idempotence, chaque donnée donnera toujours la même empreinte. Dans l'idéal, on voudrait s'assurer que les fonctions de hachages soient bijectives de manière à ce que chaque donnée ait une seule empreinte et que chaque empreinte ne corresponde qu'à une seule donnée. En pratique, les fonctions de hachages sont surjectives, cela est dûe au fait que l'ensemble d'arrivée correspondant aux empreintes soit de taille fini contrairement à l'ensemble des données en entrées qui lui est infini. On pourra donc avoir deux données différentes qui ont la même empreinte. La fréquence à laquelle ce genre de phénomènes se produit dépend de l'algorithme de hachage utilisé mais en principe, il est extrêmement peu probable que deux données différentes partagent la même empreinte.
  +
 
Ce qui fait la puissance et la fiabilité d'une fonction de hachage c'est l'incapacité de remonter à la donnée initiale à partir de son empreinte. Il est très simple, pour une donnée en entrée, de calculer le hachage correspondant, tandis que l'opération inverse correspondant à retrouver la donnée initiale à partir de son empreinte est mathématiquement extrêmement compliquée, et de ce fait, impossible à mettre en place sur les ordinateurs de nos jours. Une utilisation notable du hachage va être pour le stockage de mots de passe. Lors d'une inscription sur un site Web, on ne va jamais stocker le mot de passe en clair dans une base de données. A la place, on va calculer le hachage correspondant au mot de passe et le stocker dans la base. A chaque fois que l'on voudra s'authentifier sur le site en rentrant le mot de passe, le hachage sera calculé et comparé à celui présent dans la base de données. Si les deux sont égaux, alors il s'agit du bon mot de passe. On peut donc vérifier qu'un mot de passe est valide sans l'avoir stocker dans la base au préalable, ce qui sécurise d'avantage les comptes utilisateurs.
  +
  +
Nous avons évoqué plus haut le fait que les fonctions de hachages ne garantissent pas la bijectivité et que des collisions puissent arriver (deux données différentes avec la même empreinte), pour des données aussi petites que des mots de passes (une cinquantaine de caractères tout au plus), le phénomène de collisions a une probabilité d'arriver quasi nulle.
  +
  +
Les fonctions de hachage ont tout de même quelques faiblesses notables. La première, réside dans la complexité de l'algorithme de hachage et de sa résistance aux collisions. C'est le cas de la fonction MD5 inventée en 1991, qui a pu être utilisée de manière fiable jusqu'en 2004 où une équipe choise a réussi à casser la fonction et prouver qu'elle ne garantissait une assez bonne résistance aux collisions. Le MD5 est aujourd'hui encore utilisé dans certains cas de figures. (notamment pour vérifier l'intégrité d'une donnée, c'est le cas pour les sommes de contrôle de certaines distributions Linux par exemple). Toutefois, il est bannir pour le hachage de mots de passe qui sont des données extrêmement sensibles. Il existe aujourd'hui d'autres fonctions tel que la famille SHA (pour Secure Hashing Algorithm) et notamment SHA-2 et SHA-3 qui n'ont pas encore été cassés.
  +
  +
Une autre faiblesse des fonctions de hachage est l'idempotence. Puisque chaque donnée a une empreinte unique, un attaquant pourrait calculer en amont les hachages pour des centaines de millions de données différentes et se contenter de les comparer à des hachages volés dans des bases de données de manière à identifier la donnée source. Dans le cadre du vol de mot de passe, on parle de tables arc-en-ciel (ou Rainbow table) qui sont simplement des gigantesques tables faisant correspondre un mot de passe à son hachage. Il existe différentes méthodes que l'on peut mettre en place pour limiter le vol de mots de passe tel que le principe de salage ou encore l'utilisation d'algorithmes lents tel que bcrypt visant à ralentir l'opération de hachage.
  +
  +
Toutefois, il est important de garder à l'esprit que toutes les méthodes mises en places ne résolvent pas le problème, elles visent simplement à ralentir considérablement les attaquants. Un attaquant disposant de suffisamment de temps et de puissance de calcul finira par retrouver n'importe quel mot de passe.
   
 
Toutefois, les fonctions de hachage ne sont pas parfaites, certains algorithmes ont été rendu obsolète pour l'utilisation sécurisée du hachage tel que MD5. Il est fortement déconseillé de stocker des hachages MD5 de mots de passe étant donné qu'avec la puissance dont nos ordinateurs disposent aujourd'hui, l'opération permettant de retrouver le mot de passe à partir de son empreinte est facilement exécutable. On privilégiera donc des fonctions de hachage plus sécurisées comme SHA2, SHA-256 ou encore SHA3.
 
Toutefois, les fonctions de hachage ne sont pas parfaites, certains algorithmes ont été rendu obsolète pour l'utilisation sécurisée du hachage tel que MD5. Il est fortement déconseillé de stocker des hachages MD5 de mots de passe étant donné qu'avec la puissance dont nos ordinateurs disposent aujourd'hui, l'opération permettant de retrouver le mot de passe à partir de son empreinte est facilement exécutable. On privilégiera donc des fonctions de hachage plus sécurisées comme SHA2, SHA-256 ou encore SHA3.

Revision as of 16:00, 3 December 2021

⚠️ Cette page est en cours de construction et de ce fait beaucoup d'informations sont encore manquantes... ⚠️

Présenté par :


Merkle Trees

Résumé

Mots-clé: Merkle, arbres, hachage, structure de données, validation

Abstract

Merkle Trees are binary trees in which every node is labelled with a cryptographic hash.

Keywords: Merkle, Trees, hash, data structure, validation

Fonctionnement

Principe

Simple Merkle Tree

Les arbres de Merkle sont des arbres binaires utilisés pour effectuer de la validation de données. Pour ce faire, chaque feuille de l'arbre va contenir le hachage correspondant à une partie de la donnée à valider. Chaque noeud de l'arbre va également contenir un hachage. Ce hachage est obtenu en concaténant le hachage des deux enfants et en passant le résultat dans une fonction pour créer un tout nouveau hachage. Il se construit alors une dépendance générale où la valeur de chaque noeud dépend des valeurs de ses noeuds enfants.

L'image ci-dessous contient un arbre de Merkle servant à valider une donnée découpée en quatre blocs (Data Nodes). Les feuilles de l'abre (Merkle leaves) vont contenir le hachage correspondant pour chaque bloc. Les noeuds intermédiaires (Merkle branches) vont contenir le hachage issu de la concaténation des hachages de leurs deux enfants. Enfin, la racine de l'arbre (Merkle root) va contenir le hachage final servant à identifier l'arbre de Merkle.



Un point sur le hachage

Avant de s'immiscer dans le fonctionnement des arbres, il est important de parler du hachage et plus particulièrement des fonctions de hachage.

En cryptographie, une fonction de hachage est une fonction qui, à partir d'une donnée fournie en entrée, va être capable de calculer une empreinte numérique qui va permettre d'identifier rapidement la donnée initiale. La taille en sortie de cette empreinte est fixe et ne dépend pas de la taille de la donnée en entrée. Par idempotence, chaque donnée donnera toujours la même empreinte. Dans l'idéal, on voudrait s'assurer que les fonctions de hachages soient bijectives de manière à ce que chaque donnée ait une seule empreinte et que chaque empreinte ne corresponde qu'à une seule donnée. En pratique, les fonctions de hachages sont surjectives, cela est dûe au fait que l'ensemble d'arrivée correspondant aux empreintes soit de taille fini contrairement à l'ensemble des données en entrées qui lui est infini. On pourra donc avoir deux données différentes qui ont la même empreinte. La fréquence à laquelle ce genre de phénomènes se produit dépend de l'algorithme de hachage utilisé mais en principe, il est extrêmement peu probable que deux données différentes partagent la même empreinte.

Ce qui fait la puissance et la fiabilité d'une fonction de hachage c'est l'incapacité de remonter à la donnée initiale à partir de son empreinte. Il est très simple, pour une donnée en entrée, de calculer le hachage correspondant, tandis que l'opération inverse correspondant à retrouver la donnée initiale à partir de son empreinte est mathématiquement extrêmement compliquée, et de ce fait, impossible à mettre en place sur les ordinateurs de nos jours. Une utilisation notable du hachage va être pour le stockage de mots de passe. Lors d'une inscription sur un site Web, on ne va jamais stocker le mot de passe en clair dans une base de données. A la place, on va calculer le hachage correspondant au mot de passe et le stocker dans la base. A chaque fois que l'on voudra s'authentifier sur le site en rentrant le mot de passe, le hachage sera calculé et comparé à celui présent dans la base de données. Si les deux sont égaux, alors il s'agit du bon mot de passe. On peut donc vérifier qu'un mot de passe est valide sans l'avoir stocker dans la base au préalable, ce qui sécurise d'avantage les comptes utilisateurs.

Nous avons évoqué plus haut le fait que les fonctions de hachages ne garantissent pas la bijectivité et que des collisions puissent arriver (deux données différentes avec la même empreinte), pour des données aussi petites que des mots de passes (une cinquantaine de caractères tout au plus), le phénomène de collisions a une probabilité d'arriver quasi nulle.

Les fonctions de hachage ont tout de même quelques faiblesses notables. La première, réside dans la complexité de l'algorithme de hachage et de sa résistance aux collisions. C'est le cas de la fonction MD5 inventée en 1991, qui a pu être utilisée de manière fiable jusqu'en 2004 où une équipe choise a réussi à casser la fonction et prouver qu'elle ne garantissait une assez bonne résistance aux collisions. Le MD5 est aujourd'hui encore utilisé dans certains cas de figures. (notamment pour vérifier l'intégrité d'une donnée, c'est le cas pour les sommes de contrôle de certaines distributions Linux par exemple). Toutefois, il est bannir pour le hachage de mots de passe qui sont des données extrêmement sensibles. Il existe aujourd'hui d'autres fonctions tel que la famille SHA (pour Secure Hashing Algorithm) et notamment SHA-2 et SHA-3 qui n'ont pas encore été cassés.

Une autre faiblesse des fonctions de hachage est l'idempotence. Puisque chaque donnée a une empreinte unique, un attaquant pourrait calculer en amont les hachages pour des centaines de millions de données différentes et se contenter de les comparer à des hachages volés dans des bases de données de manière à identifier la donnée source. Dans le cadre du vol de mot de passe, on parle de tables arc-en-ciel (ou Rainbow table) qui sont simplement des gigantesques tables faisant correspondre un mot de passe à son hachage. Il existe différentes méthodes que l'on peut mettre en place pour limiter le vol de mots de passe tel que le principe de salage ou encore l'utilisation d'algorithmes lents tel que bcrypt visant à ralentir l'opération de hachage.

Toutefois, il est important de garder à l'esprit que toutes les méthodes mises en places ne résolvent pas le problème, elles visent simplement à ralentir considérablement les attaquants. Un attaquant disposant de suffisamment de temps et de puissance de calcul finira par retrouver n'importe quel mot de passe.

Toutefois, les fonctions de hachage ne sont pas parfaites, certains algorithmes ont été rendu obsolète pour l'utilisation sécurisée du hachage tel que MD5. Il est fortement déconseillé de stocker des hachages MD5 de mots de passe étant donné qu'avec la puissance dont nos ordinateurs disposent aujourd'hui, l'opération permettant de retrouver le mot de passe à partir de son empreinte est facilement exécutable. On privilégiera donc des fonctions de hachage plus sécurisées comme SHA2, SHA-256 ou encore SHA3.

Création d'un arbre

Pour réaliser un arbre de Merkle pour une donnée particulière, on va commencer par découper la donnée en entrée en un certain nombres de blocs. Le nombre de blocs va varier en fonction de la taille de la donnée. Une fois la donnée scindée en blocs, on va calculer pour chaque bloc son hachage et l'ajouter à l'arbre de Merkle. Deux blocs consécutifs vont être reliés par un nouveau noeud parent dont le hachage sera calculé en effectuant la concaténation des deux hachages enfant et en hachant une dernière fois ce résultat. On va réitérer cette opération pour chaque bloc, jusqu'à ce que tous les blocs de données hachés appartiennent à l'abre et qu'une racine soit calculée. Une fois la racine obtenue, la construction de l'abre est terminée.

Pour ce qui est de l'algorithme de hachage utilisé, celui-ci va varier en fonction des implémentations. Généralement, on utilisera des fonctions de hachage robustes tel que le SHA2 ou SHA3.

Arbre de Merkle désiquilibré

Nous avons parlé précédemment de comment les abres de Merkel étaient construits mais nous avons oublié d'évoquer un point. L'algorithme décrit marche très bien lorsque le nombre de blocs en entrée est une puissance de 2. Par exemple, avec quatre blocs, on aura quatre feuilles (noeud de hauteur 2), deux noeuds de hauteur 1 et un noeud de hauteur 0 (la racine). Mais que se passe-t-il si au lieu d'avoir quatre blocs, nous en avions six ? Nous aurions alors six feuilles, trois noeuds de hauteur 1 et... Comment faire? Chaque noeud ne peut avoir que deux enfants et nous nous trouvons avec un nombre impair de noeud, devons-nous changer la structure de l'abre et autoriser des noeuds à avoir trois enfants ?

Ils existent différentes approches permettant de pallier ce problème.

Duplication du noeud impair (Bitcoin)

Pour cette première approche, on va dupliquer les noeuds qui se retrouvent tout seul. Dans l'exemple suivant, on va donc dupliquer Hash5 de manière à pouvoir créer un parent dont les enfants seront deux copies de Hash5. On va réitérer l'opération à chaque fois qu'on montera d'un niveau de manière à avoir un arbre équilibré.

Merkle Tree Duplicating Node.png

Création d'un arbre parfait (Monero)

Validation de données

Limites et faiblesses

Cas d'utilisations

Blockchain

Amazon AWS DynamoDB

Système de fichier ZFS

Git

Références