Ed448 og Brainpool ECDSA i ren Pascal til PDF

PDFlibPas signerer og verificerer med Ed448 og med de tre Brainpool ECDSA-kurver i ren Object Pascal. Intet eksternt kryptografibibliotek, ingen platformudbyder, ingen DLL: PDFlibEd448 implementerer RFC 8032 PureEdDSA på edwards448, og PDFlibBrainpool implementerer RFC 5639 brainpoolP256r1, brainpoolP384r1 og brainpoolP512r1. Begge blev bygget på samme måde, mod kendt-svar-vektorer (known-answer vectors), der blev genereret uafhængigt, før der var skrevet nogen Pascal, og begge er især værd at skrive om på grund af fejlene

Legemearitmetik er usædvanligt ærlig kode. Den matcher enten offentliggjorte vektorer byte for byte, eller også gør den ikke, så der er ingen plads til at "næsten virke". Det vanskelige er, at en forkert implementation stadig producerer signaturer, stadig verificerer sine egne signaturer og stadig ser fuldstændig plausibel ud

Hvorfor disse kurver, og hvorfor i Pascal

Brainpool-kurver optræder i europæiske profiler for kvalificerede signaturer, så et bibliotek, der signerer dokumenter til det marked, kan ikke behandle dem som eksotiske. Ed448 er blandt de algoritmer, som ISO/TS 32002 bringer til PDF, hvor dens interne digest er SHAKE256 frem for SHA-2. Ingen af familierne findes i de gængse Pascal-kryptografibiblioteker, så et PDF-bibliotek, som vil have dem, må eje dem selv

Udrulningsargumentet er det samme, som gælder for al kryptografien i dette bibliotek: en applikation, der udsender én binær fil uden kryptografiske afhængigheder, har ingen udbyder at opdage, ingen version at matche og ingen adfærd, der ændrer sig, når værten bliver patchet. Signering er præcis det område, hvor du allerhelst ikke vil have en afhængighed, der flytter sig

Konstanter kommer fra specifikationsteksten, aldrig fra hukommelsen

Det første forsøg på edwards448's basispunkt blev skrevet fra hukommelsen og var forkert. Det er ikke en bemærkelsesværdig fejl, men den er meget dyr, fordi et forkert basispunkt producerer et selvkonsistent system: din nøglegenerering, signering og verificering er alle enige indbyrdes og uenige med resten af verden

Den arbejdsgang, der virker, er at tage alle domæneparametre fra specifikationsteksten og derefter krydsverificere. For edwards448 betyder det primtallet, kurvekonstanten, gruppeordenen og begge decimalkoordinater for basispunktet fra RFC 8032, konverteret til den interne limb-repræsentation og derefter tjekket mod offentliggjorte testvektorer fra samme dokument. For Brainpool-kurverne betyder det parametrene fra RFC 5639, en uafhængig implementation skrevet til at generere vektorer og et krydstjek mod et systembibliotek i begge retninger, før nogen Pascal overhovedet kørte

En genvej i afledningen fortjener en advarsel, fordi den ser universel ud og ikke er det: at gendanne basispunktet fra en fast y-værdi virker for 25519-kurven og virker ikke for edwards448, hvor den værdi ikke har nogen kvadratrod. Et script modbeviste det på sekunder, hvilket er langt billigere end at opdage det via en debugger

Metoden: en spejlimplementation på limb-niveau, før nogen Pascal

Teknikken, der gjorde begge units håndterbare, er en spejlimplementation i et sprog med ubegrænsede heltal, bygget nedefra og op. Først aritmetiklaget alene: legememultiplikation, subtraktion og carry-propagering, stresstestet mod deres algebraiske invarianter over et par hundrede tilfældige tilfælde. Derefter den fulde nøglegenerering inde i spejlet, og det er dér, de semantiske fejl lever, og hvor de er billige at finde. Først derefter Pascal-transskriptionen

Ubyttet er diagnostisk snarere end udviklingsmæssigt. Når spejlet først er kendt for at være korrekt, er enhver uenighed mellem spejl og Pascal en transskriptionsfejl, og at indfange den samme mellemværdi i begge implementationer lokaliserer den straks. Det omdanner en klasse af fejl, som ellers er næsten ufejlfindbar — et enkelt forkert limb dybt inde i en skalarmultiplikation — til en sammenligning, der tager fem minutter

Fire rodårsager i Ed448

Alle fire blev fundet ved at indfange mellemværdier, og alle fire er af den slags, der producerer output, der ser gyldigt ud

Den første er en notationsfælde. De fleste offentliggjorte formler for forenet Edwards-addition antager en kurvekonstant på minus én, og edwards448 har plus ét. Overført uændret skrives tælleren i y-koordinaten som en sum, hvor den burde være en differens. Rettelsen er ikke at lappe fortegnet, men at genaflede den inversfri produktform ud fra den affine additionslov for den korrekte kurve, hvilket giver de fire koordinatudtryk og ikke efterlader plads til, at et fortegn kan nedarves fra den forkerte kilde

Den anden er i punkttekomprimeringen. At gendanne den affine x fra projektive koordinater kræver én multiplikation med inversen af Z. Multiplicerer man i stedet med den kvadrerede inverse, får man en værdi, der stadig er en gyldig projektiv repræsentation, men den forkerte affine koordinat, så symptomet er en korrekt y med en forkert x. Når som helst den ene koordinat er rigtig og den anden ikke er, sidder fejlen i normaliseringen, ikke i aritmetikken

Den tredje er en vane importeret fra den kortere kurve. Både den pr. signatur gældende skalar og challenge-skalarlen skal reduceres fra den fuldstændige digest, som for Ed448 er 114 bytes, og ikke fra dens første 57. 32-byte-kurven bruger også sin fulde 64-byte-digest, så reglen er konsistent; det er kun antagelsen om, at "halvdelen af digesten er skalarens bredde", der er forkert

Den fjerde er rækkefølgen. Præfikset for domæneseparation kommer først, før kontekstpræfikset og beskeden, hvilket ikke er den rækkefølge, den intuitive læsning af R og A i specifikationen antyder. Gør man dette forkert, får man signaturer, der verificerer mod sin egen implementation og intet andet, og det er den mest vildledende fejl, man kan begå

// Felcarry-design: ren propagering med gulv-semantik (floor), så både
// positive og negative limbs virker, og subtraktion ikke behøver bias.
// Det øverste carry foldes tilbage gennem 2^448 = 2^224 + 1 (mod p), hvilket
// berører limb 0 og limb 8. Begrænset til fire runder; to observeret
// i praksis
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]);          // gulv, ikke trunkering
      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;

En tidligere version af den rutine tilføjede en bias, før den propagerede, og ved store inputs foldede den et forkert carry af forkert størrelsesorden ind i de lave limbs. Carry-ordninger baseret på bias er en vedvarende kilde til denne type defekt; gulv-semantik med en afgrænset gentagelsesløkke er lettere at ræsonnere om og målbart hurtig nok

To rodårsager i Brainpool

Den første er slet ikke kryptografi. Den brugte repræsentation er 33 limbs, så produktet af to værdier behøver 66, og produktarrayet var erklæret med 64. At skrive forbi enden korrumperede tilstødende hukommelse, hvilket først viste sig som forkerte resultater og først blev et crash, da en bredere scanning blev tilføjet. Reglen, der kom ud af det, er værd at anvende på alle numeriske buffere med fast størrelse: dimensionér efter produktbredden i værste tilfælde og læg margen til, og tænk derefter aldrig mere på det. Arrayet i den udsendte kode er på 68 limbs

Den anden er en forvekslet eksponentiationsform. Der findes to korrekte square-and-multiply-former, og de indtager eksponenten i modsatte retninger: højre-mod-venstre-formen multiplicerer og kvadrerer derefter basen og skal læse bits fra den mindst signifikante ende, mens venstre-mod-højre-formen kvadrerer og multiplicerer og læser fra den mest signifikante ende. Modulinversionsløkken havde en højre-mod-venstre-krop med et bit-løb, der startede ved den mest signifikante ende. Begge halvdele er lærebogsstof, kombinationen er det ikke, og resultatet er en forkert invers, der stadig ser ud som et plausibelt legeme-element

// Jacobiansk fordobling og addition, hvor destinationsrecorden kan være
// den samme variabel som en kilde. En kopi af hele recorden ved indgang
// er eneste pålidelige forsvar: skrivning af R's limbs forurener senere
// læsninger af P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // kopiér først, beregn derefter kun fra Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

To proceslektier, der kostede mere end fejlene

Trinvis hotfixning konvergerer ikke på en kryptografisk unit. Et udkast blev lappet gentagne gange, indtil det bar på 32 duplikerede rutiner og en beskadiget struktur, og det blev først fikset ved at omskrive det. Mønsteret, man skal tage til sig, er enten at skrive det én gang ud fra et valideret spejl eller at omskrive det; en række lokale rettelser til aritmetik, du endnu ikke forstår, akkumulerer hurtigere, end den korrigerer

Og tjek tidsstemplen på den eksekverbare fil, før du tror på et testresultat. Et inkrementelt build, der kompilerer, men ikke genlinker, kører den forrige binære fil, hvilket fabrikerede en hel runde falske spor om manglende probes og duplikeret output. Ved fejlfinding på kryptografi bør et uforklarligt resultat udløse spørgsmålet "er dette det binary, jeg lige har bygget", før "er algoritmen forkert"

Ydelse, omfang og hvordan man kalder det

Modulær reduktion i Brainpool-uniten er bitserielt shift-subtract fra produktets højeste satte bit, så en multiplikation koster nogenlunde i størrelsesordenen bitbredden. En P-256-verificering lander i de lave hundreder af millisekunder, hvilket er uproblematisk for signering eller verificering af dokumenter og ville være utilstrækkeligt for en TLS-terminator. Barrett-reduktion er den oplagte opgradering og kræver en bredere arbejdsværdi, end den nuværende repræsentation bærer, så det er en ændring, man laver, når en arbejdsbyrde efterspørger den, frem for forebyggende

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, SHAKE256 internt, 57-byte-nøgler
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: kalderen leverer den pr. signatur gældende nonce, så
  // nonce-politikken forbliver hos applikationen
  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;

Bemærk, at Brainpool-signeringens entry point tager nonce'en som argument i stedet for at generere en. Det er bevidst: nonce-generering er den eneste mest katastrofale ting at tage fejl af i ECDSA, da en gentaget eller forudsigelig værdi afslører den private nøgle, og beslutningen om, hvor tilfældigheden kommer fra, tilhører applikationen og dens compliance-regime, ikke et PDF-bibliotek

Disse kurver står side om side med det post-kvantearbejde, der er beskrevet i artiklen om FIPS 204 ML-DSA, og de kobles på samme signerings- og verificeringspipeline, som er dækket i PAdES-signering og -verificering. Til testcertifikater på disse kurver er den lokale genereringsvej beskrevet i selvsignerede certifikater med CryptoAPI. Den fulde algoritmematrise er opført på produktsiden losLab PDF Developer Library