Les fonctions de hachage - extrait ebook Bitcoin Démocratisé 1.
Sommaire :
Ce premier tome est en quelque sorte préparatoire pour la suite de la série d’ebooks. Nous allons y étudier les différents algorithmes liés à la cryptographie qui interviennent au sein du protocole Bitcoin. L’objectif sera de vulgariser et d’entrer dans le détail, mais promis, je ne vais pas vous faire un cours de mathématiques pures. Il y en aura un petit peu, puisqu’elles sont à la base de la cryptographie, mais le but sera que quiconque puisse comprendre l’idée derrière chaque mécanisme.
Toute la sécurité inhérente à Bitcoin est basée sur cette cryptographie. On la retrouve à tous les étages du protocole. La cryptographie est dans les wallets, dans les blocs, dans la communication… Elle est omniprésente dans Bitcoin. Comprendre comment elle fonctionne, et pourquoi elle est utilisée dans le protocole, représente selon moi un premier pas indispensable pour étudier par la suite les rouages techniques de Bitcoin.
Mais finalement, c’est quoi la cryptographie ?
Etymologiquement, le mot “cryptographie” vient des mots en grec ancien “kruptos” qui veut dire “caché”, et “graphein” qui veut dire “écriture”. La cryptographie est donc initialement la science de cacher un message.
On la classe parmi les sciences de la cryptologie qui englobent également l’authentification, la non-répudiation ou encore la cryptanalyse. Aujourd’hui, on confond souvent ces deux termes en un seul. Ainsi, selon le NIST (National Institute of Standards and Technology), la cryptographie moderne est une discipline qui incarne les principes, les moyens et les méthodes de transformation des données afin de masquer leur contenu sémantique, d'empêcher leur utilisation non autorisée ou d'empêcher leur modification non détectée.
Il est intéressant de remarquer que cette discipline existe au moins depuis l’antiquité avec notamment le chiffre de César, une méthode de chiffrement d’un message par simple décalage de lettres.
Dans le protocole Bitcoin, les deux principales applications de la cryptographie sont les fonctions de hachage et les signatures numériques. Voyons ensemble ce en quoi elles consistent.
Si vous ne comprenez pas certains mots techniques utilisés dans cet article, nous avons rédigé un glossaire permettant de définir tous ces termes. Retrouvez le en cliquant ici : https://www.pandul.fr/post/glossaire-s%C3%A9rie-d-ebooks-bitcoin-d%C3%A9mocratis%C3%A9
Cet article reprend exclusivement la première partie de l'ebook Bitcoin Démocratisé 1. Cette partie a été légèrement modifiée par rapport à l'ouvrage original afin de l'adapter au format du blog. Pour accéder à la seconde partie portant sur les signatures numériques, cliquez ici : https://www.pandul.fr/ressources
Cet ouvrage est mis à disposition selon les termes de la Licence Creative Commons : Attribution - Partage dans les Mêmes Conditions 4.0 International (CC BY-SA 4.0), à l'exception des logos de Pandul seuls qui demeurent la propriété intellectuelle de l'Ei Loïc Morel.
Pour en savoir plus, cliquez ici :
https://creativecommons.org/licenses/by-sa/4.0/
Merci à l’ensemble des personnes qui m’ont apporté leur aide, leurs conseils d’experts et leurs encouragements sur l'ouvrage original :
Grittoshi → https://twitter.com/Grittoshi
200KEKS → https://twitter.com/200KEKS
Fanis Michalakis → https://twitter.com/FanisMichalakis
Sosthène → https://twitter.com/Sosthene___
Merci également à tous ceux qui m’ont apporté leur aide sur ce projet mais qui ont préféré rester anonymes.
Caractéristiques d’une fonction de hachage.
Le premier type d'algorithmes cryptographiques utilisé dans Bitcoin regroupe les fonctions de hachage. Elles sont utilisées à de nombreuses reprises dans le protocole.
Le hachage est un procédé permettant de mapper une chaîne de bits de longueur arbitraire à une chaîne de bits de longueur fixe grâce à une fonction de hachage cryptographique. En d'autres termes, la fonction de hachage prend en entrée (input) une information de taille arbitraire pour la convertir en une empreinte de taille fixe appelée “hash” en sortie (output).
⇨ Ce hash est parfois également nommé : “digest”, “condensat”, “condensé” ou encore “haché”.
Par exemple, la fonction SHA256 produira un hash d’une taille fixe de 256 bits. Ainsi, si l’on met en entrée de cette fonction “Pandul”, un message de taille arbitraire, le hash en sortie est : “bbde98…”, une empreinte de 256 bits au format hexadécimal.
Ces fonctions de hachage cryptographiques sont utilisées dans Bitcoin car elles disposent de 3 caractéristiques intéressantes.
La première caractéristique d’une fonction de hachage cryptographique est l’irréversibilité.
L’irréversibilité se vérifie lorsque le calcul du hash sachant l’information en entrée peut être réalisé facilement, mais le calcul inverse, c’est-à-dire le calcul de l’information en entrée sachant le hash, est impossible. C’est ce que l’on appelle une fonction à sens unique ou “trap door function”.
En réalité, le terme technique utilisé pour décrire cette caractéristique d’irréversibilité est la “Résistance à la préimage”.
Dans notre exemple, obtenir le hash bbde98… en connaissant le message en entrée Pandul est très facile. En revanche, il est impossible de trouver Pandul en ayant connaissance uniquement du hash bbde98….
La deuxième caractéristique d’une fonction de hachage cryptographique est la résistance à la falsification.
Cette caractéristique est vérifiée uniquement si la moindre petite modification sur le message en entrée résulte en un hash profondément différent en sortie. Ainsi, si nous reprenons notre exemple, nous pouvons voir que le simple ajout d’un chiffre sur le message en entrée modifie complètement le hash en sortie :
Grâce à cette caractéristique, les fonctions de hachage sont utilisées pour vérifier l’intégrité d’une information en mettant en évidence la moindre modification de l’entrée originelle.
La troisième caractéristique d’une fonction de hachage cryptographique est la résistance à la collision.
Cette caractéristique se vérifie s’il est difficile de trouver deux entrées différentes qui donnent le même condensat en sortie.
La situation de collision est mathématiquement impossible à éviter au vu de la limitation de la taille de la sortie et de la différence de taille entre les entrées et les sorties*. Ainsi, une bonne fonction de hachage cryptographique est une fonction pour laquelle le risque de collision entre deux valeurs est tellement faible qu’il peut être considéré comme nul.
* Ce phénomène est appelé le principe des tiroirs (“Pigeonhole principle” en anglais).
Pour que cette caractéristique soit attribuée à une fonction, il ne faut pas qu’une collision puisse être trouvée sur celle-ci plus rapidement qu’en essayant simplement des entrées aléatoires une à une, comme avec l’attaque des anniversaires. Cette attaque illustre une limite à la résistance à la collision d’une fonction de hachage égale à 2^(n/2), où n est la taille du condensat en bits.
Par exemple, la fonction de hachage SHA256 a une résistance aux collisions attendue limitée à 2^128. Concrètement, cela veut dire que si un attaquant essaie 2^128 entrées aléatoires différentes, il est très probable qu’il puisse trouver une collision en sortie de la fonction.
On peut donc admettre que pour deux valeurs distinctes en entrée d’une fonction de hachage cryptographique, il est presque impossible d’obtenir exactement le même hash en sortie.
Cette caractéristique n’est par exemple plus vérifiée sur les algorithmes SHA-0 et SHA-1, prédécesseurs des SHA-2, pour lesquels des collisions ont été trouvées. Ces fonctions sont donc aujourd’hui déconseillées et souvent considérées comme désuètes.
Il existe une quatrième caractéristique que l’on peut observer sur une fonction de hachage cryptographique qui est la résistance à la seconde préimage.
Je ne vais pas la détailler ici puisqu’une résistance aux collisions implique forcément une résistance à la seconde préimage. La différence entre les deux tient aux informations imposées à un attaquant.
Pour la résistance à la seconde préimage, un attaquant dispose d’un message imposé m1 et il doit trouver un message m2 donnant le même hash que m1. Pour la résistance à la collision, un attaquant peut choisir librement m1 et m2.
Ces trois caractéristiques que je viens de décrire permettent de déterminer de nombreux cas d’usages pour ces primitives cryptographiques que représentent les fonctions de hachage.
Les fonctions de hachage dans Bitcoin.
La fonction de hachage la plus utilisée dans le protocole Bitcoin est SHA256. Comme nous l’avons vu précédemment, c’est une fonction de hachage qui produit en sortie un condensat de 256 bits.
Conçue au début des années 2000 par la NSA, elle est aujourd’hui un standard fédéral de traitement des données aux États-Unis.
Elle est employée au sein du protocole Bitcoin à différents niveaux. Elle est notamment utilisée pour hacher l’entête d’un bloc dans le mécanisme de Proof-of-Work. On la retrouve également dans le processus de dérivation des adresses de réception, dans la structuration des transactions en Arbre de Merkle au sein des blocs, ou encore dans le calcul de la somme de contrôle d’une phrase de récupération.
Je reviendrai évidemment sur toutes ces utilisations en détail dans les tomes suivants.
On utilise aussi dans Bitcoin sa variante SHA512, qui fait partie de la même famille des SHA2, mais qui produit un condensat de 512 bits. Elle est notamment utilisée dans la dérivation d’un portefeuille HD (Hierarchical Deterministic, en français déterministe hiérarchique.), processus que nous étudierons en détail dans le tome 2. Notons que cette fonction de hachage cryptographique n’est pas implémentée directement sur le protocole Bitcoin, mais on la retrouve au sein d’autres algorithmes cryptographiques implémentés.
Enfin, la troisième fonction de hachage utilisée dans le protocole est RIPEMD160. Comme son nom l’indique, elle produit un condensat de 160 bits. On la retrouve notamment dans le processus de dérivation des adresses de réception.
RIPEMD : RACE Integrity Primitives Evaluation Message Digest.
RACE : Research and Development in Advanced Communications Technologies in Europe.
Lorsque l’on évoque HASH256 dans Bitcoin, cela décrit un double hachage successif avec la fonction SHA256. Cette double fonction est notamment utilisée dans les arbres de Merkle et dans le protocole de preuve de travail. Lorsque l’on évoque HASH160, cela décrit un double hachage successif utilisant d'abord SHA256 puis RIPEMD160. Cette double fonction est notamment utilisée dans le processus de dérivation d’une adresse de réception, et pour générer les empreintes de clés.
Les rouages de SHA256.
Nous avons vu précédemment que les fonctions de hachage disposent de caractéristiques intéressantes qui justifient un usage au sein du protocole Bitcoin. Voyons maintenant ensemble les rouages de ces fonctions de hachage qui leur permettent de disposer de ces caractéristiques.
Les fonctions SHA256 et SHA512 appartiennent à la famille des Secure Hash Algorithm 2. Le mécanisme de ces deux fonctions de hachage est très similaire. Il est basé sur une construction spécifique appelée Merkle-Damgard. RIPEMD160 est également basée sur le même type de construction. Dans cet ebook, nous allons donc étudier uniquement le fonctionnement de SHA256.
Pour rappel, nous disposons d’un message de taille arbitraire en entrée. L’objectif est de le passer dans la fonction SHA256 afin de disposer d’un hash de 256 bits en sortie.
Ce processus se décompose en plusieurs étapes :
1- Les bits de rembourrage (pré-traitement).
Pour commencer, il va falloir égaliser notre message en entrée afin qu’il dispose d’une taille d’un multiple de 512 bits.
Les bits de rembourrage consistent à ajouter des bits à notre message initial afin qu’il atteigne premièrement une taille égale au multiple de 512 bits supérieur le plus proche, moins 65 bits.
On a donc :
M + 1 + P + 64 = n * 512où :
M est la taille de notre message initial (arbitraire).
P est la taille de nos bits de rembourrage sans le séparateur.
n*512 est le premier multiple de 512 bits supérieur à M+64+1.
1 est le bit réservé au séparateur “1” entre le message et les bits de rembourrage.
64 est le nombre de bits réservés pour le rembourrage avec la taille (voir étape 2).
Les bits de rembourrage commencent donc par un séparateur 1, suivi par le nombre de 0 nécessaires pour avoir une taille de n*512-64 bits.
Par exemple, si le message en entrée de SHA256 fait 950 bits, nous aurons :
Le premier multiple de 512 supérieur à M+64+1 est :
1024 = 2 * 512
Nous avons donc :
→ M + 1 + P + 64 = 1024
→ 950 + P = 1024 - 1 - 64
→ P = 1024 - 1 - 64 - 950
→ P = 9Dans cet exemple, notre première partie de rembourrage doit être de 9 bits + le bit réservé au séparateur 1. On commence donc par un “1”, puis on complète les bits de rembourrage avec 9 bits égaux à “0”.
Dans notre exemple, cela nous donne les bits de rembourrage avec séparateur suivants :
1 000 000 000.
Nous ajoutons ces bits de rembourrage à la suite de notre message initial.
2- Le rembourrage avec la taille (pré-traitement).
Pour terminer d’égaliser notre input, nous allons ajouter les 64 bits manquants afin d’atteindre une taille totale égale à un multiple de 512 bits.
Ces 64 bits sont la représentation binaire de la taille du message initial en bits. Si on reprend notre exemple avec un message initial de 950 bits, on va convertir le nombre décimal 950 en nombre binaire ce qui nous donne 11 1011 0110. On complète ce nombre avec des zéros à la base pour faire 64 bits au total.
Dans notre exemple, cela donne :
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0011 1011 0110Puis nous ajoutons ces 64 bits au résultat de l’étape 1 pour arriver à notre input égalisé sur un multiple de 512 bits.
3- Les constantes et vecteurs d’initialisation.
La fonction SHA256 est configurée avec plusieurs valeurs de 32 bits par défaut dont nous aurons besoin à l’étape suivante. Tout d’abord, il existe 8 vecteurs d’initialisation constants associés aux lettres A à H :
A = 0x6a09e667
B = 0xbb67ae85
C = 0x3c6ef372
D = 0xa54ff53a
E = 0x510e527f
F = 0x9b05688c
G = 0x1f83d9ab
H = 0x5be0cd19Ces vecteurs d’initialisation représentent chacun les 32 premiers bits des parties décimales des racines carrées des 8 premiers nombres premiers.
0x est un préfixe noté avant une nombre pour signifier que celui-ci est au format hexadécimal (base 16). Par exemple, 0x1F désigne le nombre 1F en hexadécimal.
On définit également 64 constantes associées à la lettre Ki :
K[0..63] =
0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2Ces constantes représentent chacune les 32 premiers bits des parties décimales des racines cubiques des 64 premiers nombres premiers.
Toutes ces informations seront utiles à l’étape suivante.
4- La compression.
On va maintenant pouvoir s’attaquer au traitement. Pour commencer, nous allons diviser notre input égalisé (résultat de l’étape 2) en morceaux de 512 bits chacun. Etant donné que notre input égalisé est d’une taille de n * 512 bits, nous divisons notre input en n morceaux, chacun d’une taille de 512 bits. Chaque morceau va ensuite passer dans la fonction de compression. Cette fonction consiste à effectuer 64 opérations sur chaque morceau.
Avant d’étudier les rouages de la fonction de compression, il est important de comprendre le fonctionnement des opérations utilisées au sein de celle-ci. Nous allons utiliser des calculs basées sur l’algèbre de Boole afin de réaliser des opérations au niveau du bit. Ce sont des opérations logiques qui peuvent être décrites par trois opérations de base :
La disjonction (OR).
La conjonction (AND).
La négation (NOT).
A partir de ces opérations logiques, nous allons pouvoir déterminer des fonctions plus complexes comme le XOR (OU exclusif), une opération très utilisée en cryptographie. Le but de toutes ces opérations est de traiter les opérandes au niveau du bit.
Ces calculs permettent donc de modéliser des raisonnements logiques à partir d’un état et en fonction de conditions. Chaque opération dispose d’une table de vérité produisant un résultat de façon déterministe à partir des deux opérandes de celle-ci.
Au sein de la fonction de compression des algorithmes de hachage de la famille SHA-2, on utilise les opérations suivantes :
XOR (⊕)
AND (∧)
NOT (¬)
Les tables de vérité de ces opérations sont les suivantes pour toute opérande p et q :
p | q | XOR (⊕) | AND (∧) | NOT p (¬p) | NOT q (¬q) |
1 | 1 | 0 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 0 |
0 | 0 | 0 | 0 | 1 | 1 |
Par exemple, si on XOR (⊕) le nombre de 6 bits 101100 avec le nombre 001000 cela nous donnera cela :
101100 ⊕ 001000 = 100100Dans cet exemple, nous avons simplement traité chaque bit de la première opérande avec son bit de même rang sur la deuxième opérande en appliquant la table de vérité du XOR présentée ci-dessus.
En plus de ces opérations logiques, la fonction de compression des SHA-2 utilise des opérations de décalage de bits. En l'occurrence, nous allons utiliser l’opération de décalage à droite ShR (Shift Right) et l’opération de décalage circulaire à droite RotR (Rotate Right Shift).
Leur fonctionnement est très simple. A partir d’une chaîne de bits, l’opération ShR^n va décaler tous les bits à droite de n rangs, et va compléter les n trous réalisés sur la chaîne avec n zéros. Par exemple :
ShR^4 (101100001) = 000010110Schématiquement, l’opération ShR^4 sur notre exemple ressemble à cela :
Quant à l’opération RotR^n, à partir d’une chaîne de bits, elle va simplement prendre les n derniers bits de la suite pour les placer en premiers, décalant ainsi les autres bits de n rangs à droite. Par exemple :
RotR^4 (101100001) = 000110110Schématiquement, l’opération RotR^4 sur notre exemple ressemble à cela :
Toutes ces opérations au niveau du bit sont utilisées au sein de la fonction de compression de SHA256. Maintenant que nous avons compris comment fonctionnent ces opérations, étudions ensemble les rouages de celle-ci.
Schématiquement, la fonction de compression ressemblera à cela :
Dans ce schéma, nous pouvons voir que nous avons pour chaque tour 3 inputs : Wi, Ki et une suite que nous verrons plus tard.
Wi est un nombre de 32 bits. Les 16 premiers Wi, c’est-à-dire W0, W1, W2, […], W15, sont constitués par notre morceau de message.
Pour rappel, chaque morceau fait 512 bits. Ses 32 premiers bits seront donc W0, les 32 bits suivants seront W1, les 32 bits suivants W2... Jusqu’à W15 qui prendra les 32 derniers bits de notre morceau de message.
Pour déterminer les Wi après W15, c’est-à-dire W16, W17, […], W63, il existe une formule qui consiste à appliquer certaines des opérations que nous venons de voir sur les bits du message pour générer les nombres de W16 à W63 :
Wi = W(i-16) + σ0{256} + W(i-7) + σ1{256}
où :
σ0{256} = RotR^7(W(i-15)) ⊕ RotR^18(W(i-15)) ⊕ ShR^3(W(i-15))
σ1{256} = RotR^17(W(i-2)) ⊕ RotR^19(W(i-2)) ⊕ ShR^10(W(i-2))L’addition (+) est effectuée modulo 2^32.
⇨ mod, pour modulo, est simplement une opération mathématique qui permet entre deux nombres entiers de renvoyer le reste de la division euclidienne du premier par le deuxième nombre. Par exemple, 16 mod 5 est égal à 1. On l’utilise ici afin de ramener la taille d’un message donné à 32 bits.
On sait donc maintenant comment déterminer chaque entrée Wi.
Les entrées Ki, c'est-à-dire K0, K1, […], K63, correspondent simplement aux 64 constantes décrites à l’étape 3. Elles vont être notre deuxième entrée.
Enfin, la troisième entrée de notre fonction de compression est la suite [A,B,C,D,E,F,G,H] décrite à l’étape 3, où chaque lettre correspond à un nombre de 32 bits. Cette suite de vecteurs d'initialisation est utilisée en input pour le premier tour du premier morceau seulement.
L’output du premier tour donnera une autre suite [A,B,C,D,E,F,G,H]. Cette nouvelle suite sera utilisée en input pour le deuxième tour. L’output du deuxième tour deviendra l’input du troisième tour, et ainsi de suite.
Maintenant que nous disposons de nos 3 entrées, regardons plus en détail comment fonctionnent ces 64 tours :