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 :
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 :
Ce schéma représente un seul tour de notre fonction de compression. On peut y reconnaître nos 3 entrées de fonction :
La suite [A,B,C,D,E,F,G,H].
Wt que nous avions nommé Wi.
Kt que nous avions nommé Ki.
On peut déjà observer que ce tour nous donne en sortie une nouvelle suite [A,B,C,D,E,F,G,H]. Comme expliqué précédemment, cette nouvelle suite servira d’entrée pour le tour suivant, et on continue de même jusqu’au 64ème tour.
Le symbole [+] sur le schéma ci-dessus correspond à une addition modulo 2^32. Les autres calculs du tour se décomposent comme cela :
Ch(E, F, G) = (E ∧ F) ⊕ ((¬E) ∧ G)
Maj(A, B, C) = (A ∧ B) ⊕ (A ∧ C) ⊕ (B ∧ C)
∑0{256}(A) = RotR^2(A) ⊕ RotR^13(A) ⊕ RotR^22(A)
∑1{256}(E) = RotR^6(E) ⊕ RotR^11(E) ⊕ RotR^25(E)L’objectif d’un tour est donc d’obtenir en sortie une nouvelle suite [A,B,C,D,E,F,G,H], où chaque lettre est un nouveau nombre de 32 bits.
Voici en détail comment obtenir notre sortie [As,Bs,Cs,Ds,Es,Fs,Gs,Hs] à partir de notre entrée [Ae,Be,Ce,De,Ee,Fe,Ge,He] et des 2 autres inputs connus : Wi et Ki :
Ici, la couleur orange permet de mettre en évidence la suite de sortie et la couleur bleu indique la suite d’entrée d’un seul tour de la fonction de compression.
Pour i de 0 à 63 :∑1{256}(Ee) = RotR^6(Ee) ⊕ RotR^11(Ee) ⊕ RotR^25(Ee)Ch(Ee, Fe, Ge) = (Ee ∧ Fe) ⊕ ((¬ Ee) ∧ Ge) temp1 = He + ∑1{256}(Ee) + Ch(Ee, Fe, Ge) + Ki + Wi ∑0{256}(Ae) = RotR^2(Ae) ⊕ RotR^13(Ae) ⊕ RotR^22(Ae)Maj(Ae, Be, Ce) = (Ae ∧ Be) ⊕ (Ae ∧ Ce) ⊕ (Be ∧ Ce) temp2 = ∑0{256}(Ae) + Maj(Ae, Be, Ce)As = temp1 + temp2
Bs = Ae
Cs = Be
Ds = Ce
Es = De + temp1
Fs = Ee
Gs = Fe
Hs = GeLe symbole (+) correspond encore à une addition modulo 2^32.
Voici donc comment se décompose un tour.
Voici donc comment se décompose un seul tour. Une fois que l’on a la sortie de ce tour (la nouvelle suite de [As,Bs,Cs,Ds,Es,Fs,Gs,Hs]), on l’utilise comme entrée pour le tour suivant. On continue ainsi de suite jusqu’à arriver au 64ème tour du morceau. L’output du 64ème tour sera additionné modulo 232 à l’input du premier tour de ce morceau, soit la suite [A0,B0,C0,D0,E0,F0,G0,H0] initiale. Chaque lettre sera additionnée mod 2^32 à sa même lettre en entrée :
A = A0 + A63
B = B0 + B63
C = C0 + C63
D = D0 + D63
E = E0 + E63
F = F0 + F63
G = G0 + G63
H = H0 + H63Cette nouvelle suite [A,B,C,D,E,F,G,H] est concaténée dans l’ordre alphabétique pour ne donner plus qu’un nombre de 256 bits. Ce nombre est le hash intermédiaire du premier morceau. Ce condensat intermédiaire servira d’input pour le premier tour du second morceau de 512 bits. Ce second morceau va également passer ses 64 tours. Et on continue ainsi de suite jusqu’à avoir traité tous les morceaux de 512 bits de notre message initial égalisé.
L’opération de concaténation consiste à mettre bout à bout les opérandes.
La sortie finale de notre fonction de hachage SHA256 est l’output du 64ème tour du dernier morceau additionné modulo 2^32 à l’input du 1er tour du dernier morceau. C’est-à-dire que la sortie de la fonction de hachage est le hash intermédiaire du dernier morceau.
Dans cette suite [A,B,C,D,E,F,G,H], chaque lettre fait 32 bits. Elles sont concaténées pour obtenir le hash de sortie de fonction. Nous aurons donc bien une sortie finale de la fonction de hachage d’une taille fixe de 256 bits :
Mais alors, en quoi cette fonction est-elle irréversible, résistante aux collisions et résistante à la falsification ?
Pour la résistance à la falsification c’est assez simple à comprendre. Il y a tellement de calculs effectués en cascade, qui dépendent à la fois de l’entrée et des constantes, que la moindre modification du message initial change complètement le chemin parcouru, et donc change complètement le hash de sortie.
Cette propriété est en partie assurée par le mélange des états intermédiaires avec les états initiaux pour chaque morceau.
Ensuite, lorsque l’on parle d’une fonction de hachage cryptographique, le terme "irréversibilité" n’est généralement pas utilisé. À la place, on parle de “résistance à la préimage” qui spécifie que pour tout y donné, il est difficile de trouver un x tel que h(x) = y. Cette résistance à la préimage, quant à elle, est garantie par les opérations utilisées dans la fonction de compression et par la perte de certaines informations essentielles dans le processus. Par exemple, pour un résultat donné à une addition modulo il existe plusieurs opérandes possibles :
3+2 mod 10 = 5
7+8 mod 10 = 5
5+10 mod 10 = 5On voit bien dans cet exemple qu’en sachant uniquement le modulo utilisé (10) et le résultat (5) on ne peut pas déterminer avec certitude quelles sont les deux bonnes opérandes utilisées dans l’addition. On dit qu’il existe plusieurs congrus modulo 10.
Pour l’opération XOR on est confronté au même problème. Rappelez vous de la table de vérité de cette opération : toute sortie de 1 bit peut être déterminée par deux configurations différentes en entrées qui ont exactement la même probabilité d’être les bonnes valeurs. On ne peut donc pas déterminer avec certitude les opérandes d’un XOR en sachant uniquement son résultat. Si on augmente la taille des opérandes du XOR, le nombre de possibles entrées en sachant uniquement le résultat augmente de façon exponentielle. De plus, le XOR est souvent utilisé aux côtés d’autres opérations au niveau du bit, comme l’opération RotR, qui viennent ajouter encore plus d’interprétations possibles au résultat.
On utilise également au sein de la fonction de compression l’opération ShR. Celle-ci vient supprimer une partie de l’information de base qui est donc impossible à retrouver par la suite. Il n’y a encore une fois pas de moyen algébrique pour inverser cette opération. Toutes ces opérations à sens unique et ces opérations de perte d’information sont utilisées à de très nombreuses reprises dans les fonctions de compression. Le nombre de possibles entrées pour une sortie donnée est donc presque infini, et chaque tentative de calcul inverse mènerait à des équations avec un nombre d’inconnus très élevé qui augmenterait exponentiellement à chaque étape.
Enfin, pour la caractéristique de résistance aux collisions, plusieurs paramètres entrent en compte. Le pré-traitement du message d’origine tient un rôle essentiel. Sans ce pré-traitement, il pourrait être plus facile de trouver des collisions sur la fonction.
Cette caractéristique est aussi assurée par les propriétés de résistance à la préimage et de résistance à la falsification.
En effet, pour qu’il y est une résistance aux collisions, il faut que toute sortie de la fonction soit imprévisible. Toute prévisibilité peut être utilisée pour chercher des collisions plus rapidement que par une attaque des anniversaires (brute force). L’objectif étant que tout bit en sortie ne puisse être deviné à l’avance avec une probabilité supérieure à 0,5.
Généralement, les cryptographes qui construisent de telles fonctions déterminent d’abord les meilleures attaques possibles pour trouver une collision, puis ils adaptent leurs paramètres afin de rendre ces attaques désuètes.
Comme vu précédemment, la collision est impossible à éviter au vu du principe des tiroirs. Si l’on néglige le fait que l’étape du rembourrage vient limiter la taille maximum de l’entrée à environ 2 exaoctets, alors pour toute valeur donnée en entrée il existe une infinité d’autres valeurs qui produisent une collision sur la fonction.
Néanmoins, si le résultat de la fonction est imprévisible, on peut alors admettre que les hash ont une distribution pseudo-aléatoire par rapport au message d’origine. Si l’ensemble des valeurs réalistes en entrée est inférieur à l’ensemble des sorties possibles, et si la distribution est pseudo-aléatoire, alors le risque de collision est très faible sur une fonction qui produit un hash suffisamment grand.
⇨ Cette structure de la fonction de hachage SHA256 est une construction dite de Merkle-Damgard. Il existe d’autres types de constructions comme la construction de l’éponge utilisée pour la famille de fonctions de hachage SHA3 ou pour Keccak-256*, une des fonctions de hachage utilisées sur Ethereum.
Ce type de construction de Merkle-Damgard rend certaines fonctions de hachage vulnérables aux attaques par extension de longueur. Ce type d’attaque peut notamment être réalisée sur un hachage qui utilise en entrée une concaténation de deux informations.
C’est probablement pour cette raison que Satoshi Nakamoto a implémenté un double hachage SHA256 à plusieurs endroits dans le protocole, au lieu d’un simple hachage SHA256.
*Keccak est la fonction initiale, conçue par Guido Bertoni, Joan Daemen, Michaël Peeters, Seth Hoffert, Ronny Van Keer et Gilles Van Assche, gagnante du concours du NIST pour le standard SHA-3. Cette fonction fut légèrement modifiée par le NIST pour définir le standard SHA-3 final. Aujourd’hui, on différencie Keccak qui est l'algorithme original et SHA-3 qui est l'algorithme modifié par le NIST. Les deux fonctions sont similaires mais elles ne produisent pas les mêmes condensats.
Les algorithmes utilisés pour la dérivation.
À partir de ces primitives cryptographiques que représentent les fonctions de hachage, le protocole Bitcoin utilise également des algorithmes cryptographiques pour de la dérivation. Ces fonctions de dérivation sont basées sur des fonctions de hachage, elles sont donc comparables à ces dernières. La principale différence entre une fonction de hachage et un algorithme utilisé pour de la dérivation est le nombre d’entrées et le modèle de sécurité. Étant donné que ces algorithmes sont basés sur une fonction de hachage, ils conservent en partie les mêmes caractéristiques que celle-ci à savoir : l’irréversibilité, la résistance à la falsification et la résistance à la collision.
On en utilise deux sur le protocole Bitcoin : HMAC (Hash-based Message Authentication Code) et PBKDF2 (Password Based Key Derivation Function 2).
HMAC-SHA512.
HMAC est un algorithme cryptographique permettant de calculer un code d’authentification en utilisant une combinaison d’une fonction de hachage et d’une clé secrète. C’est une fonction dérivée de l'algorithme NMAC.
Dans Bitcoin on utilise HMAC-SHA512, c’est-à-dire l’algorithme HMAC intégrant la fonction de hachage SHA512 (qui est similaire à SHA256 mais qui donne une sortie de 512 bits).
Voici son schéma de fonctionnement :
Étudions plus en détail ce qu’il se passe dans cette boîte noire HMAC-SHA512. Soit la fonction HMAC-SHA512 avec :
Soit la fonction HMAC-SHA512 avec :
m : message de taille arbitraire choisi par l’utilisateur (entrée 1).
K : clé arbitraire choisie par l’utilisateur (entrée 2).
K’ : la clé K ajustée à la taille B des blocs.
SHA512 : La fonction de hachage SHA512.
⊕ (XOR) : Fonction ou exclusif.
|| : Opération de concaténation, c’est-à-dire de mettre les deux opérandes l’une à la suite de l’autre.
opad : constante définie par l’octet 0x5c répété B fois.
ipad : constante définie par l’octet 0x36 répété B fois.
B : La taille des morceaux de la fonction de hachage utilisée.
Avant de commencer, il existe une étape de prétraitement qui consiste à ajuster la taille de la clé et des constantes. Ces informations seront ajustées à la taille B qui est égale à la taille des morceaux (ou blocs) utilisés dans la fonction de hachage choisie.
Par exemple, si nous avions choisi d’utiliser la fonction SHA256 au sein de la fonction HMAC, nous aurions eu un B égal à 512 bits, soit 64 octets. Dans Bitcoin on utilise SHA512 dans la fonction HMAC, nous avons donc un B égal à 128 octets (1024 bits).
L’étape de prétraitement consiste premièrement à égaliser la clé de taille arbitraire choisie par l’utilisateur. Pour ce faire, si la clé est d’une taille inférieure à B, on la rembourre avec des zéros à la fin de la chaîne de bits jusqu’à atteindre la taille B. Si la clé est d’une taille supérieure à B, on la hache avec la fonction de hachage choisie, puis on rembourre le condensat avec des zéros à la fin de la chaîne de bits jusqu’à atteindre la taille B.
Pour les constantes opad et ipad, on va simplement répéter leur octet le nombre de fois nécessaire pour atteindre la taille B. Par exemple, si nous avons un B égal à 128 octets, opad sera une concaténation de 128 0x5c :
opad = 0x5c5c5c5c5c5c[...]5c5c5c5c5c
→ 128 fois 5cLa fonction HMAC-SHA512 est alors définie par l’équation suivante :
HMAC-SHA512K(m) = SHA512 ((K’ ⊕ opad) || SHA512 ((K’ ⊕ ipad) || m))Schématiquement, cela représenterait cela :
Voici les étapes décomposées de cette fonction :
On XOR la clé égalisée avec ipad ce qui donne i clé pad.
On XOR la clé égalisée avec opad ce qui donne o clé pad.
On concatène i clé pad avec le message (entrée 1).
On hache ce résultat avec SHA512 ce qui donne hash 1.
On concatène o clé pad avec hash 1.
On hache ce résultat avec SHA512 ce qui donne la sortie.
Cette fonction HMAC est utilisée dans Bitcoin à la fois dans les chemins de dérivation de clés sur les portefeuilles HD, et également au sein d’une autre fonction nommée PBKDF2.
PBKDF2.
PBKDF2, pour Password-Based Key Derivation Function 2, est une fonction de dérivation de clé. Cet algorithme va simplement appliquer une fonction choisie par l’utilisateur à un message de taille arbitraire avec un sel cryptographique, et il va répéter cette opération un certain nombre de fois pour sortir une clé comparable à un condensat.
Étant donné que cet algorithme utilise une fonction de hachage en son sein, il dispose en partie des mêmes caractéristiques que cette dernière : irréversibilité, résistance à la falsification et résistance à la collision.
Dans le protocole Bitcoin, on utilise PBKDF2 pour dériver la graine d’un portefeuille HD (seed) depuis la phrase mnémonique (ou phrase de récupération).
La fonction pseudo-aléatoire utilisée est alors HMAC-SHA512, le sel représente la passphrase et le nombre d’itérations est de 2048.
Schématiquement, PBKDF2 représenterait cela :
Nous avons donc pu découvrir les fonctions de hachage utilisées dans Bitcoin et les algorithmes utilisés pour de la dérivation intégrant ces mêmes fonctions.
Tout cela vous paraît peut-être encore flou, mais ne vous inquiétez pas, nous verrons leurs utilisations concrètes sur le protocole dès le tome 2.
Étant donné que ces fonctions sont utilisées à toutes les étapes du protocole Bitcoin, j’ai souhaité les décrire dès le premier tome afin de ne pas avoir à y revenir dans chaque tome suivant.
Dans la partie suivante, nous allons étudier et vulgariser la deuxième grande catégorie de méthodes cryptographiques utilisées dans le protocole Bitcoin : Les signatures numériques.
Cet article est extrait de l'ebook Bitcoin Démocratisé 1 : Bitcoin et la cryptographie, rédigé par Loïc Morel.
Pour aller plus loin :
Ressources externes :
Articles sur les opérations à l’échelle du bit et l'algèbre de Boole :
Articles et ressources sur le fonctionnement technique des fonctions de hachage :
Rapport FIPS 180-4 : Secure Hash Standard (SHS) :