2. Composants cryptographiques
2. Composants cryptographiques
2.1. Arbres de hachage de Merkle
Les journaux utilisent un arbre de hachage de Merkle binaire pour un audit efficace. L’algorithme de hachage est SHA-256 [FIPS.180-4] (noter que ceci est fixé pour cette expérimentation, mais il est anticipé que chaque journal pourrait spécifier un algorithme de hachage). L’entrée du hachage d’arbre de Merkle (Merkle Tree Hash) est une liste d’entrées de données ; ces entrées seront hachées pour former les feuilles de l’arbre de hachage de Merkle. La sortie est un hachage d’arbre de Merkle unique de 32 octets. Étant donné une liste ordonnée de n entrées, D[n] = {d(0), d(1), ..., d(n-1)}, le hachage d’arbre de Merkle (MTH) est donc défini comme suit :
Le hachage d’une liste vide est le hachage d’une chaîne vide :
MTH({}) = SHA-256().
Le hachage d’une liste à une entrée (également appelé hachage de feuille) est :
MTH({d(0)}) = SHA-256(0x00 || d(0)).
Pour n > 1, soit k la plus grande puissance de deux strictement inférieure à n (c’est-à-dire, k < n <= 2k). Le hachage d’arbre de Merkle d’une liste D[n] à n éléments est alors défini récursivement par
MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])),
où || est la concaténation et D[k1:k2] désigne la liste {d(k1), d(k1+1),..., d(k2-1)} de longueur (k2 - k1). (Noter que les calculs de hachage pour les feuilles et les nœuds diffèrent. Cette séparation de domaines est requise pour donner la résistance aux secondes images.)
Noter que nous n’exigeons pas que la longueur de la liste d’entrée soit une puissance de deux. L’arbre de Merkle résultant peut donc ne pas être équilibré ; toutefois, sa forme est uniquement déterminée par le nombre de feuilles. (Note : cet arbre de Merkle est essentiellement le même que la proposition d’arbre d’historique [CrosbyWallach], sauf que notre définition traite les arbres non complets différemment.)
2.1.1. Chemins d’audit Merkle
Un chemin d’audit Merkle pour une feuille dans un arbre de hachage de Merkle est la liste la plus courte de nœuds supplémentaires dans l’arbre de Merkle requise pour calculer le hachage d’arbre de Merkle pour cet arbre. Chaque nœud dans l’arbre est soit une feuille, soit est calculé à partir des deux nœuds immédiatement en dessous (c’est-à-dire, vers les feuilles). À chaque étape vers le haut dans l’arbre (vers la racine), un nœud du chemin d’audit est combiné avec le nœud calculé jusqu’ici. En d’autres termes, le chemin d’audit consiste en la liste des nœuds manquants requis pour calculer les nœuds menant d’une feuille à la racine de l’arbre. Si la racine calculée à partir du chemin d’audit correspond à la vraie racine, alors le chemin d’audit est la preuve que la feuille existe dans l’arbre.
Étant donné une liste ordonnée de n entrées dans l’arbre, D[n] = {d(0), ..., d(n-1)}, le chemin d’audit Merkle PATH(m, D[n]) pour la (m+1)-ième entrée d(m), 0 <= m < n, est défini comme suit :
Le chemin pour la feuille unique dans un arbre avec une liste d’entrée à un élément D[1] = {d(0)} est vide :
PATH(0, {d(0)}) = {}
Pour n > 1, soit k la plus grande puissance de deux strictement inférieure à n. Le chemin pour le (m+1)-ième élément d(m) dans une liste de n > m éléments est alors défini récursivement par
PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and
PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for m >= k,
où : est la concaténation de listes et D[k1:k2] désigne la liste de longueur (k2 - k1) {d(k1), d(k1+1),..., d(k2-1)} comme auparavant.
2.1.2. Preuves de cohérence Merkle
Les preuves de cohérence Merkle prouvent la propriété append-only de l’arbre. Une preuve de cohérence Merkle pour un hachage d’arbre de Merkle MTH(D[n]) et un hachage précédemment annoncé MTH(D[0:m]) des m premières feuilles, m <= n, est la liste des nœuds dans l’arbre de Merkle requise pour vérifier que les m premières entrées D[0:m] sont égales dans les deux arbres. Ainsi, une preuve de cohérence doit contenir un ensemble de nœuds intermédiaires (c’est-à-dire des engagements sur les entrées) suffisant pour vérifier MTH(D[n]), tel que (un sous-ensemble de) les mêmes nœuds peut être utilisé pour vérifier MTH(D[0:m]). Nous définissons un algorithme qui produit la preuve de cohérence minimale (unique).
Étant donné une liste ordonnée de n entrées dans l’arbre, D[n] = {d(0), ..., d(n-1)}, la preuve de cohérence Merkle PROOF(m, D[n]) pour un hachage d’arbre de Merkle antérieur MTH(D[0:m]), 0 < m < n, est définie par :
PROOF(m, D[n]) = SUBPROOF(m, D[n], true)
La sous-preuve pour m = n est vide si m est la valeur pour laquelle PROOF a été initialement demandée (signifiant que le hachage d’arbre de Merkle du sous-arbre MTH(D[0:m]) est connu) :
SUBPROOF(m, D[m], true) = {}
La sous-preuve pour m = n est le hachage d’arbre de Merkle engageant les entrées D[0:m] ; sinon :
SUBPROOF(m, D[m], false) = {MTH(D[m])}
Pour m < n, soit k la plus grande puissance de deux strictement inférieure à n. La sous-preuve est alors définie récursivement.
Si m <= k, les entrées du sous-arbre droit D[k:n] n’existent que dans l’arbre courant. Nous prouvons que les entrées du sous-arbre gauche D[0:k] sont cohérentes et ajoutons un engagement sur D[k:n] :
SUBPROOF(m, D[n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])
Si m > k, les entrées du sous-arbre gauche D[0:k] sont identiques dans les deux arbres. Nous prouvons que les entrées du sous-arbre droit D[k:n] sont cohérentes et ajoutons un engagement sur D[0:k].
SUBPROOF(m, D[n], b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])
Ici, : est une concaténation de listes, et D[k1:k2] désigne la liste de longueur (k2 - k1) {d(k1), d(k1+1),..., d(k2-1)} comme auparavant.
Le nombre de nœuds dans la preuve résultante est majoré par ceil(log2(n)) + 1.
2.1.3. Exemple
L’arbre de Merkle binaire à 7 feuilles :
hash
/ \
/ \
/ \
/ \
/ \
k l
/ \ / \
/ \ / \
/ \ / \
g h i j
/ \ / \ / \ |
a b c d e f d6
| | | | | |
d0 d1 d2 d3 d4 d5
Le chemin d’audit pour d0 est [b, h, l].
Le chemin d’audit pour d3 est [c, g, l].
Le chemin d’audit pour d4 est [f, j, k].
Le chemin d’audit pour d6 est [i, k].
Le même arbre, construit de façon incrémentale en quatre étapes :
hash0 hash1=k
/ \ / \
/ \ / \
/ \ / \
g c g h
/ \ | / \ / \
a b d2 a b c d
| | | | | |
d0 d1 d0 d1 d2 d3
hash2 hash
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
k i k l
/ \ / \ / \ / \
/ \ e f / \ / \
/ \ | | / \ / \
g h d4 d5 g h i j
/ \ / \ / \ / \ / \ |
a b c d a b c d e f d6
| | | | | | | | | |
d0 d1 d2 d3 d0 d1 d2 d3 d4 d5
La preuve de cohérence entre hash0 et hash est PROOF(3, D[7]) = [c, d, g, l]. c, g sont utilisés pour vérifier hash0, et d, l sont en outre utilisés pour montrer que hash est cohérent avec hash0.
La preuve de cohérence entre hash1 et hash est PROOF(4, D[7]) = [l]. hash peut être vérifié en utilisant hash1=k et l.
La preuve de cohérence entre hash2 et hash est PROOF(6, D[7]) = [i, j, k]. k, i sont utilisés pour vérifier hash2, et j est en outre utilisé pour montrer que hash est cohérent avec hash2.
2.1.4. Signatures
Diverses structures de données sont signées. Un journal DOIT utiliser soit des signatures sur courbe elliptique avec la courbe NIST P-256 (section D.1.2.3 du Digital Signature Standard [DSS]), soit des signatures RSA (RSASSA-PKCS1-V1_5 avec SHA-256, section 8.2 de [RFC3447]) avec une clé d’au moins 2048 bits.