SHA-256 sécurise à peu près tout ce que vous touchez sans le voir : les mots de passe stockés, les commits git, les certificats TLS, les blockchains. Et pourtant, 99,9 % des programmeurs qui l’utilisent n’ont jamais vu ce qu’il y a dedans. On écrit hashlib.sha256(data) ou sha256sum fichier, et une boîte noire recrache 64 caractères hexadécimaux.

Cet article ouvre l’arc cryptographique de la série. On va construire SHA-256 à partir de rien — pas d’appel de bibliothèque, pas de runtime, pas d’interpréteur. Juste du code machine natif émis par verbose, qui produit exactement le même hash que sha256sum, octet pour octet. Et qui le prouve.

Si vous n’avez pas lu les articles précédents : on s’appuie ici sur l’émission native et la récursion (article #1) et sur les preuves de terminaison (article #3). On va en avoir besoin.

SHA-256 en une phrase

SHA-256 prend un message de longueur quelconque et le réduit à 256 bits (32 octets), de façon déterministe et irréversible. Sous le capot, c’est étonnamment mécanique :

  1. On découpe le message en blocs de 64 octets (en le complétant — le padding).
  2. Pour chaque bloc, on fait tourner une fonction de compression : 64 tours de mélange bit à bit sur un état de 8 mots de 32 bits.
  3. L’état final, c’est le hash.

Vu de loin, le pipeline tient en quelques étapes :

   MESSAGE  (n'importe quelle taille)
        │
        ▼   on complète (padding), puis on découpe
   ┌──────┐┌──────┐┌──────┐┌──────┐
   │bloc 0││bloc 1││bloc 2││bloc N│   ← 64 octets chacun
   └──────┘└──────┘└──────┘└──────┘
        │
        ▼   chaque bloc : 64 tours de compression ;
        │   l'état (8 mots) passe d'un bloc au suivant
        ▼
   ┌───────────────────┐
   │  HASH : 32 octets  │   ← toujours la même taille,
   └───────────────────┘      quelle que soit l'entrée

Tout SHA-256 tient dans une poignée d’opérations sur les bits : rotations, ET, OU, XOR, additions modulo 2³². Pas de magie. Juste de l’arithmétique binaire, répétée avec discipline.

C’est exactement le genre de chose que verbose sait émettre en natif.

Les briques : des opérations bit à bit, pas des fonctions

SHA-256 repose sur six primitives. Voici la première, rotr32 — une rotation à droite de n bits dans un champ de 32 bits :

rule rotr32
  @intention: "rotate right by n bits within a 32-bit field"
  input:
    w : WordAndShift
  output:
    out : number
  logic:
    out = band(bor(shr(w.x, w.n), shl(w.x, 32 - w.n)), 4294967295)

Lisez la logique : on décale à droite de n (shr), on décale à gauche de 32 - n (shl), on combine au OU (bor), et on masque sur 32 bits avec band(..., 4294967295) (4294967295 = 2³² − 1). C’est la définition mathématique d’une rotation, écrite telle quelle.

Le point qui compte : cette ligne ne devient pas un appel de fonction. Le compilateur verbose la traduit directement en quelques instructions x86-64 — des shr, shl, or, and. Pas de dispatch, pas de pile d’appel, pas de bibliothèque. Le binaire est la rotation.

La deuxième primitive, ch (« choose » — pour chaque bit, choisir y si x, sinon z) :

rule ch
  @intention: "(x AND y) XOR ((NOT x) AND z)"
  logic:
    out = band(bxor(band(t.x, t.y), band(bnot(t.x), t.z)), 4294967295)

Et les quatre autres suivent le même moule : maj (la majorité bit à bit), et les sigmas Σ₀ Σ₁ σ₀ σ₁ — chacune n’est qu’une combinaison de rotr32 et de XOR. Par exemple Σ₁(x) = rotr(x,6) ⊕ rotr(x,11) ⊕ rotr(x,25). Six règles, zéro dépendance, tout en code machine.

La compression : 64 tours, écrits en récursion

Le cœur de SHA-256, c’est une boucle de 64 tours. En verbose, il n’y a pas de mot-clé « boucle » — on l’exprime en récursion, exactement comme la factorielle de l’article #1 :

let t1 = band(s.h + big_sigma1(...) + ch(...) + k + w, 4294967295)
let t2 = band(big_sigma0(...) + maj(...), 4294967295)
let na = band(t1 + t2, 4294967295)
let ne = band(s.d + t1, 4294967295)
out = if s.round >= 63 then na
      else compress(State { a: na, b: s.a, c: s.b, ..., round: s.round + 1, ... })

À chaque tour, on calcule le nouvel état, et tant que round < 63, on se rappelle soi-même avec round + 1. La condition s.round >= 63 est le cas de base — et c’est elle qui garantit la terminaison (article #3). Le compilateur reconnaît la récursion terminale et la transforme en boucle native : 64 tours, zéro débordement de pile.

L’état, ce sont 8 mots (a à h). Un tour ne fait que les décaler — un tapis roulant avec deux points d’injection :

  Avant :   a    b    c    d    e    f    g    h
  Après :   a'   a    b    c    e'   e    f    g
  • Six mots glissent d’un cran vers la droite (a→b, b→c, c→d, e→f, f→g, g→h).
  • Deux reçoivent une valeur neuve : a' = T1 + T2 et e' = d + T1 (les T sont calculés avec les primitives Σ, ch, maj).
  • Le dernier mot, h, est consommé dans le calcul, puis disparaît.

Et on répète ça 64 fois — en récursion, que le compilateur replie en boucle. Côté machine, il n’y a pas 64 frames empilées : juste un compteur qui monte de 0 à 63.

Le message schedule (les 64 valeurs W[t] consommées par la boucle) suit la même logique. Les 16 premières viennent des octets du message ; les 48 suivantes sont calculées au fil des tours avec σ₀ et σ₁, dans une fenêtre glissante de 16 mots. On ne stocke jamais les 64 — on n’en garde que 16 à la fois.

Le morceau intéressant : du bloc unique aux blocs multiples

Un bloc SHA-256 fait 64 octets. Un message de 3 octets (« abc ») tient dans un bloc. Mais « le contenu d’un certificat TLS » n’y tient pas. Il faut gérer N blocs — et c’est là que la progression devient instructive.

D’abord, à quoi ressemble un message complété (le padding) ? Vu à l’échelle, un bloc de 64 octets pour « abc » (3 octets seulement) ressemble à ça — chaque caractère est un octet :

  ███▓░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▒▒▒▒▒▒▒▒

  ███ = « abc »   (3 octets de message)
  ▓   = 0x80      (1 octet — marque la fin du message)
  ░   = zéros     (52 octets de remplissage)
  ▒   = longueur  (8 octets — la taille du message en bits)

Trois octets de message (███), un octet 0x80 (▓) qui marque la fin, puis une mer de zéros (░) qui remplit l’espace, et tout au bout la longueur du message en bits (▒). Tant que tout tient dans un bloc, c’est simple. Le problème commence quand le message déborde sur plusieurs blocs.

Elle s’est faite par paliers :

  • 1 bloc — jusqu’à 55 octets. Le padding (le 0x80 qui marque la fin, les zéros, puis la longueur sur les derniers octets) tient dans le bloc.
  • 2 blocs — jusqu’à 119 octets. Le padding peut déborder sur un second bloc. La règle qui calcule « quel octet à la position (bloc, pos) ? » doit raisonner en position absolue.
  • 8 blocs — jusqu’à 503 octets. Même logique, bornes plus larges. Mais il faut calculer combien de blocs : un if à huit branches, if len < 56 then 1 else if len < 120 then 2 else ... else 8.

Et puis le déclic. Cette cascade de if n’est qu’un arrondi vers le haut déguisé. On peut l’écrire en une formule arithmétique :

let n_blocks = (len + 72) / 64

(len + 72) / 64 (division entière) calcule exactement le nombre de blocs pour n’importe quelle longueur. Le +72, c’est +8 pour le champ de longueur, +1 pour le séparateur 0x80, et +63 pour arrondir vers le haut. Une ligne remplace les huit branches — et la borne passe de 503 octets à 4087 octets (64 blocs) sans rien changer d’autre.

Le détail qui fait sourire : le binaire devient plus petit. La version 64 blocs fait 11912 octets ; la version 8 blocs en faisait 12200. Une instruction div est plus compacte qu’un if à huit branches. On gère huit fois plus de données avec moins de code machine.

Et tout ça reste vérifié statiquement : les bornes (text[..4087], n_blocks dans [1, 64]) sont fixées à la compilation. Le compilateur prouve que pour toute longueur ≤ 4087, le nombre de blocs ≤ 64. Pas d’allocation dynamique, pas de débordement possible.

Comment on sait que c’est juste ?

C’est toute la question — et c’est le cœur de verbose. Affirmer « j’ai implémenté SHA-256 » ne vaut rien sans preuve. Voici l’oracle.

Le harnais de test (en Rust) ne calcule rien lui-même. Il :

  1. compile le .verbose en un binaire ELF autonome (sans libc) ;
  2. exécute ce binaire ;
  3. compare sa sortie à celle de sha256sum — l’outil système de référence.
// sha256("abc"), premier mot de 32 bits
assert_eq!(stdout, "3128432319\n"); // 0xba7816bf

0xba7816bf = 3128432319, et c’est exactement le début du SHA-256 de « abc » que crache echo -n abc | sha256sum. La version complète vérifie les 8 mots :

ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad

octet pour octet. La validation couvre des vecteurs de test (« abc », « hello », la chaîne vide, et des longueurs aux frontières de blocs : 0, 500, 1000, 2000, 4087 octets). Soyons précis : ce sont des points de contrôle, pas une preuve formelle pour toute entrée possible. Mais quand une implémentation matche sha256sum sur ces vecteurs et qu’elle est dérivée directement de la spec FIPS 180-4 brique par brique, on a une confiance solide — la même que pour n’importe quelle implémentation crypto sérieuse.

Ce que ça veut dire

Reprenons la couture, parce qu’elle compte. Le hash — chaque rotation, chaque XOR, chaque tour de compression, le découpage en blocs, le padding — est entièrement dans le binaire verbose natif. Il n’y a aucune bibliothèque crypto, aucun runtime, aucun interpréteur. Le harnais Rust n’est que l’oracle : il appelle sha256sum pour vérifier, il ne participe pas au calcul. Le binaire est SHA-256.

Et SHA-256, c’est la première brique de quelque chose de plus grand. Au-dessus viennent le chiffrement AES, les signatures Ed25519, l’échange de clés X25519 — les ingrédients d’un vrai canal TLS. Chacun se construit, comme ici, à partir des mêmes opérations bit à bit, en natif, et prouvé contre une référence.

On a commencé par une factorielle de 802 octets. On en est à un hash cryptographique qui matche l’outil système, en 12 Ko de code machine sans dépendances. La suite de l’arc va plus haut — mais la méthode ne change pas : déclarer, émettre, vérifier.