Ed448 et Brainpool ECDSA en Pascal pur pour PDF

PDFlibPas signe et vérifie avec Ed448 et avec les trois courbes ECDSA Brainpool en Object Pascal pur. Pas de bibliothèque cryptographique externe, pas de fournisseur de plateforme, pas de DLL : PDFlibEd448 implémente PureEdDSA de la RFC 8032 sur edwards448, et PDFlibBrainpool implémente brainpoolP256r1, brainpoolP384r1 et brainpoolP512r1 de la RFC 5639. Les deux unités ont été construites de la même manière, contre des vecteurs de réponse connue générés indépendamment avant qu'une ligne de Pascal ne soit écrite, et toutes deux méritent qu'on écrive sur elles surtout pour leurs bugs

L'arithmétique de corps est un code d'une honnêteté rare. Elle correspond octet par octet aux vecteurs publiés ou elle ne correspond pas, il n'y a donc aucune place pour un « fonctionne en grande partie ». Ce qui rend la tâche difficile, c'est qu'une implémentation fausse produit quand même des signatures, vérifie ses propres signatures et paraît parfaitement plausible

Pourquoi ces courbes, et pourquoi en Pascal

Les courbes Brainpool apparaissent dans les profils européens de signature qualifiée, une bibliothèque qui signe des documents pour ce marché ne peut donc pas les considérer comme exotiques. Ed448 fait partie du jeu d'algorithmes que l'ISO/TS 32002 apporte au PDF, où son condensé interne est SHAKE256 plutôt que SHA-2. Aucune de ces deux familles n'est disponible dans les bibliothèques cryptographiques Pascal d'usage courant, une bibliothèque PDF qui les veut doit donc les écrire elle-même

L'argument de déploiement est le même que pour toute la cryptographie de cette bibliothèque : une application qui livre un binaire unique sans dépendance cryptographique n'a aucun fournisseur à détecter, aucune version à faire correspondre et aucun comportement qui change quand l'hôte est corrigé. La signature est précisément le domaine où une dépendance mobile est la moins souhaitable

Les constantes viennent du texte de spécification, jamais de mémoire

La première tentative pour le point de base d'edwards448 a été écrite de mémoire et était fausse. Ce n'est pas une erreur remarquable, mais elle coûte très cher, car un point de base faux produit un système auto-cohérent : votre génération de clés, votre signature et votre vérification s'accordent entre elles et divergent du reste du monde

La procédure qui fonctionne consiste à prendre chaque paramètre de domaine dans le texte de la spécification, puis à contre-vérifier. Pour edwards448, cela signifie le nombre premier, la constante de courbe, l'ordre du groupe et les deux coordonnées décimales du point de base tirés de la RFC 8032, convertis dans la représentation interne en limbs, puis confrontés aux vecteurs de test publiés dans le même document. Pour les courbes Brainpool, cela signifie les paramètres de la RFC 5639, une implémentation indépendante écrite pour générer les vecteurs, et une contre-vérification bidirectionnelle contre une bibliothèque système avant toute ligne de Pascal

Un raccourci de dérivation mérite un avertissement, car il semble universel et ne l'est pas : retrouver le point de base à partir d'une valeur y fixe fonctionne pour la courbe 25519 et ne fonctionne pas pour edwards448, où cette valeur n'a pas de racine carrée. Un script l'a réfuté en quelques secondes, ce qui coûte bien moins cher que de le découvrir au débogueur

La méthode : un miroir au niveau des limbs avant tout Pascal

La technique qui a rendu les deux unités maîtrisables est une implémentation miroir dans un langage à entiers non bornés, construite de bas en haut. D'abord la couche arithmétique seule : multiplication de corps, soustraction et propagation de retenue, soumises à un test de charge contre leurs invariants algébriques sur quelques centaines de cas aléatoires. Ensuite la génération de clés complète à l'intérieur du miroir, c'est là que vivent les bugs sémantiques et qu'ils sont peu coûteux à trouver. Seulement ensuite, la transcription en Pascal

Le bénéfice est diagnostique plutôt que développemental. Une fois que le miroir est réputé correct, tout désaccord entre le miroir et le Pascal est une erreur de transcription, et sonder la même valeur intermédiaire dans les deux implémentations la localise immédiatement. Cela transforme une catégorie de bug sinon presque indébogable, un seul limb faux au plus profond d'une multiplication scalaire, en une comparaison de cinq minutes

Quatre causes racines dans Ed448

Les quatre ont été trouvées en sondant des valeurs intermédiaires, et les quatre sont du genre à produire une sortie d'apparence valide

La première est un piège de notation. La plupart des formules publiées pour l'addition d'Edwards unifiée supposent une constante de courbe de moins un, alors qu'edwards448 a plus un. Reprise telle quelle, le numérateur de la coordonnée y s'écrit comme une somme là où il faudrait une différence. La correction ne consiste pas à patcher le signe, mais à redériver la forme produit sans inversion à partir de la loi d'addition affine de la bonne courbe, ce qui produit les quatre expressions de coordonnées et ne laisse aucune place à un signe hérité de la mauvaise source

La deuxième concerne la décompression de points. Retrouver le x affine depuis les coordonnées projectives exige une multiplication par l'inverse de Z. Multiplier par l'inverse au carré donne une valeur qui reste une représentation projective valide et qui est la mauvaise coordonnée affine, si bien que le symptôme est un y correct avec un x faux. Chaque fois qu'une coordonnée est juste et l'autre non, le bug se trouve dans la normalisation, pas dans l'arithmétique

La troisième est une habitude importée de la courbe plus courte. Le scalaire par signature comme le scalaire de défi doivent être réduits à partir du condensé complet, qui fait 114 octets pour Ed448, et non à partir de ses 57 premiers. La courbe de 32 octets utilise elle aussi la totalité de son condensé de 64 octets, la règle est donc cohérente ; seule l'hypothèse « la moitié du condensé fait la largeur du scalaire » est fausse

La quatrième est l'ordre. Le préfixe de séparation de domaine vient en premier, avant le préfixe de contexte et le message, ce qui n'est pas l'ordre que suggère la lecture intuitive de R et de A dans la spécification. Se tromper produit des signatures qui se vérifient contre votre propre implémentation et rien d'autre, ce qui est l'échec le plus trompeur possible

// Conception de la retenue de corps : propagation en sémantique plancher pure, de sorte
// que les limbs positifs comme négatifs fonctionnent et que la soustraction n'exige aucun biais.
// La retenue supérieure se replie via 2^448 = 2^224 + 1 (mod p), ce qui
// touche le limb 0 et le limb 8. Borné à quatre passes ; deux observées
// en pratique
procedure FeCarry(var A: TFe448);
var
  I, Round: Integer;
  Carry: Int64;
begin
  for Round := 1 to 4 do
  begin
    Carry := 0;
    for I := 0 to 15 do
    begin
      A[I] := A[I] + Carry;
      Carry := Floor28(A[I]);          // plancher, pas troncature
      A[I] := A[I] - (Carry shl 28);
    end;
    if Carry = 0 then
      Break;
    A[0] := A[0] + Carry;              // 2^448 == 1
    A[8] := A[8] + Carry;              // 2^448 == 2^224
  end;
end;

Une version antérieure de cette routine appliquait un biais avant de propager, et sur de grandes entrées elle repliait une retenue parasite de mauvaise magnitude dans les limbs bas. Les schémas de retenue à biais sont une source persistante de cette classe de défaut ; la sémantique de plancher avec une boucle répétée bornée est plus facile à raisonner et mesurablement assez rapide

Deux causes racines dans Brainpool

La première n'est pas de la cryptographie du tout. La représentation de travail fait 33 limbs, le produit de deux valeurs en demande donc 66, et le tableau de produit avait été déclaré avec 64. Écrire au-delà de la fin corrompait la mémoire adjacente, ce qui s'est d'abord présenté comme des résultats faux et n'est devenu un plantage qu'une fois un balayage plus large ajouté. La règle qui en est sortie vaut la peine d'être appliquée à chaque tampon numérique de taille fixe : le dimensionner d'après la largeur de produit au pire cas, ajouter une marge, puis ne plus jamais y penser. Le tableau du code livré fait 68 limbs

La deuxième est une forme d'exponentiation mélangée. Il existe deux formes carré-et-multiplication correctes et elles consomment l'exposant dans des directions opposées : la forme de droite à gauche multiplie puis élève au carré la base et doit lire les bits depuis l'extrémité la moins significative, tandis que la forme de gauche à droite élève au carré puis multiplie et lit depuis l'extrémité la plus significative. La boucle d'inversion modulaire avait un corps de droite à gauche avec un parcours de bits du plus significatif d'abord. Les deux moitiés sont des classiques, la combinaison ne l'est pas, et le résultat est un inverse faux qui ressemble encore à un élément de corps plausible

// Doublement et addition jacobienne quand l'enregistrement de destination peut être
// la même variable qu'une source. Une copie complète de l'enregistrement à l'entrée est la
// seule défense fiable : écrire les limbs de R pollue les lectures ultérieures de P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // copier d'abord, puis calculer uniquement depuis Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Deux leçons de processus qui ont coûté plus cher que les bugs

Le correctif incrémental à chaud ne converge pas sur une unité cryptographique. Une ébauche a été patchée à répétition jusqu'à compter 32 routines dupliquées et une structure endommagée, et elle n'a été réparée qu'en la réécrivant. Le schéma à adopter est soit l'écrire une fois depuis un miroir validé, soit la réécrire ; une succession de corrections locales sur une arithmétique que vous ne comprenez pas encore s'accumule plus vite qu'elle ne corrige

Et vérifiez l'horodatage de l'exécutable avant de croire à un résultat de test. Une construction incrémentale qui compile mais ne réédite pas les liens exécute le binaire précédent, ce qui a fabriqué toute une série de fausses pistes sur des sondes manquantes et une sortie dupliquée. Quand on débogue de la cryptographie, un résultat inexpliqué doit faire se demander « est-ce le binaire que je viens de construire » avant « l'algorithme est-il faux »

Performance, périmètre et manière de l'appeler

La réduction modulaire dans l'unité Brainpool est un décalage-soustraction bit série depuis le bit allumé le plus haut du produit, donc une multiplication coûte grosso modo de l'ordre de la largeur de bit. Une vérification P-256 se situe dans les basses centaines de millisecondes, ce qui est banal pour signer ou vérifier des documents et serait inadéquat pour un terminateur TLS. La réduction de Barrett est la mise à niveau évidente et exige une valeur de travail plus large que celle que porte la représentation actuelle, c'est donc un changement à faire quand une charge de travail le demande plutôt que par précaution

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448 : PureEdDSA, SHAKE256 en interne, clés de 57 octets
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool : l'appelant fournit le nonce par signature, la politique
  // de nonce reste donc du côté de l'application
  Curve := BPLoadCurve(bpP256r1);
  if BPKeyGen(PubX, PubY, PrivateD, Curve) and
     BPSignFixedK(R, S, Hash, PrivateD, Nonce, Curve) then
    Assert(BPVerify(R, S, Hash, PubX, PubY, Curve));
end;

Notez que le point d'entrée de signature Brainpool prend le nonce au lieu d'en générer un. C'est délibéré : la génération de nonce est la chose la plus catastrophique à rater en ECDSA, puisqu'une valeur répétée ou prévisible divulgue la clé privée, et la décision d'où vient l'aléatoire appartient à l'application et à son régime de conformité, pas à une bibliothèque PDF

Ces courbes voisinent avec le travail post-quantique décrit dans l'article sur ML-DSA de FIPS 204, et elles s'intègrent au même pipeline de signature et de validation traité dans la signature et la validation PAdES. Pour des certificats de test sur ces courbes, la voie de génération locale est décrite dans les certificats auto-signés avec CryptoAPI. La matrice complète des algorithmes est listée sur la page produit de la losLab PDF Developer Library