Ed448 og Brainpool ECDSA i ren Pascal for PDF

PDFlibPas signerer og verifiserer med Ed448 og med de tre Brainpool ECDSA-kurvene i ren Object Pascal. Intet eksternt kryptografisk bibliotek, ingen plattformsprovider, ingen DLL: PDFlibEd448 implementerer RFC 8032 PureEdDSA på edwards448, og PDFlibBrainpool implementerer RFC 5639 brainpoolP256r1, brainpoolP384r1 og brainpoolP512r1. Begge ble bygget på samme måte, mot kjente-svar-vektorer generert uavhengig før noe Pascal var skrevet, og begge er verdt å skrive om først og fremst på grunn av feilene

Kroppsaritmetikken er uvanlig ærlig kode. Den samsvarer enten byte for byte med publiserte vektorer, eller så gjør den ikke det, så det finnes ingen plass til «nesten fungerende». Det som gjør det vanskelig, er at en feil implementering likevel produserer signaturer, likevel verifiserer sine egne signaturer og likevel ser helt plausibel ut

Hvorfor disse kurvene, og hvorfor i Pascal

Brainpool-kurvene opptrer i europeiske profiler for kvalifiserte signaturer, så et bibliotek som signerer dokumenter for det markedet, kan ikke behandle dem som eksotiske. Ed448 er i algoritmesettet som ISO/TS 32002 bringer til PDF, der dens interne digest er SHAKE256 snarere enn SHA-2. Ingen av de to familiene finnes i Pascal-kryptografibibliotekene i vanlig bruk, så et PDF-bibliotek som vil ha dem, må eie dem selv

Utrullingsargumentet er det samme som gjelder for all kryptografien i dette biblioteket: en applikasjon som sender ut én binærfil uten kryptografiske avhengigheter, har ingen provider å oppdage, ingen versjon å matche og ingen oppførsel som endrer seg når vertsmaskinen patches. Signering er nettopp området der du minst ønsker en bevegelig avhengighet

Konstanter kommer fra spesifikasjonsteksten, aldri fra hukommelsen

Det første forsøket på edwards448 basispunkt ble skrevet fra hukommelsen og var feil. Det er ikke en bemerkelsesverdig feil, men den er svært kostbar, fordi et feil basispunkt produserer et selvkonsistent system: nøkkelgenereringen, signeringen og verifiseringen din er alle enige med hverandre og uenige med resten av verden

Prosedyren som fungerer, er å ta hver domeneparameter fra spesifikasjonsteksten og deretter kryssverifisere. For edwards448 betyr det primtallet, kurvekonstanten, gruppeordenen og begge desimalkoordinatene til basispunktet fra RFC 8032, konvertert til den interne limb-representasjonen, og deretter sjekket mot publiserte testvektorer fra det samme dokumentet. For Brainpool-kurvene betyr det parametrene fra RFC 5639, en uavhengig implementering skrevet for å generere vektorer, og en krysssjekk mot et systembibliotek i begge retninger før noe Pascal kjørte

Én avledningssnarvei fortjener en advarsel fordi den ser universell ut og ikke er det: å gjenopprette basispunktet fra en fast y-verdi fungerer for 25519-kurven og fungerer ikke for edwards448, der den verdien ikke har noen kvadratrot. Et skript motbeviste det på sekunder, noe som er mye rimeligere enn å oppdage det gjennom en feilsøker

Metoden: en speiling på limb-nivå før noe Pascal

Teknikken som gjorde begge enhetene håndterbare, er en speilimplementering i et språk med ubegrensede heltall, bygget nedefra og opp. Først aritmetikklaget alene: kroppsmultiplikasjon, subtraksjon og carry-propagering, stresstestet mot sine algebraiske invarianter over et par hundre tilfeldige tilfeller. Deretter hele nøkkelgenereringen inne i speilingen, som er der de semantiske feilene bor og der de er billige å finne. Først deretter Pascal-transkripsjonen

Ubyttet er diagnostisk snarere enn utviklingsmessig. Når speilingen er kjent korrekt, er enhver uenighet mellom speiling og Pascal en transkripsjonsfeil, og å undersøke den samme mellomverdien i begge implementeringene lokaliserer den umiddelbart. Det omdanner en klasse feil som ellers er nesten ufeilsøkbar, en enkelt feil limb dypt inne i en skalarmultiplikasjon, til en sammenligning på fem minutter

Fire rotårsaker i Ed448

Alle fire ble funnet ved å undersøke mellomverdier, og alle fire er av den typen som produserer output som ser gyldig ut

Den første er en notasjonsfelle. De fleste publiserte formler for uniform Edwards-addisjon antar en kurvekonstant på minus én, og edwards448 har pluss én. Overført uendret skrives telleren i y-koordinaten som en sum der den skulle vært en differanse. Fiksen er ikke å lappe fortegnet, men å utlede den inversfrie produktformen på nytt fra den affine addisjonsloven for den riktige kurven, noe som produserer de fire koordinatuttrykkene og ikke etterlater rom for at et fortegn kan arves fra feil kilde

Den andre ligger i punktdekompresjon. Å gjenopprette den affine x fra projektive koordinater krever én multiplikasjon med inversen av Z. Å multiplisere med den kvadrerte inversen gir en verdi som fortsatt er en gyldig projektiv representasjon og er den feil affine koordinaten, så symptomet er en korrekt y med en feil x. Hver gang én koordinat er riktig og den andre ikke er det, sitter feilen i normaliseringen, ikke i aritmetikken

Den tredje er en vane importert fra den kortere kurven. Både skalareren per signatur og utfordringsskalareren må reduseres fra det komplette digestet, som for Ed448 er 114 byte, ikke fra de første 57. 32-byte-kurven bruker også sitt fulle 64-byte-digest, så regelen er konsistent; det er bare antakelsen om at «halve digestet er skalarbredden» som er feil

Den fjerde er rekkefølgen. Domeneskillingsprefikset kommer først, før kontekstprefikset og meldingen, noe som ikke er rekkefølgen den intuitive lesingen av R og A i spesifikasjonen antyder. Å ta dette feil produserer signaturer som verifiserer mot din egen implementering og ingenting annet, noe som er den mest villedende tenkelige feilen

// Design av kroppscarry: ren propagering med gulvsemantikk, slik at
// både positive og negative limbs fungerer og subtraksjon ikke trenger
// noe bias. Topp-carryen foldes tilbake gjennom 2^448 = 2^224 + 1 (mod p),
// noe som berører limb 0 og limb 8. Avgrenset til fire runder; to
// observert 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 avkorting
      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 versjon av den rutinen anvendte et bias før propagering, og ved store inndata foldet den en falsk carry av feil størrelsesorden inn i de lave limbene. Bias-baserte carry-ordninger er en vedvarende kilde til denne klassen av defekter; gulvsemantikk med en avgrenset repeat-løkke er enklere å resonnere om og målbar rask nok

To rotårsaker i Brainpool

Den første er i det hele tatt ikke kryptografi. Den fungerende representasjonen er 33 limbs, så produktet av to verdier trenger 66, og produktarrayet ble deklarert med 64. Å skrive forbi slutten korrupterte tilstøtende minne, noe som først viste seg som feil resultater og først ble et krasj da en bredere skanning ble lagt til. Regelen som kom ut av det, er verdt å anvende på hver numeriske buffer med fast størrelse: dimensjoner den etter produktbredden i verste fall og legg til margin, og tenk aldri på det igjen. Arrayet i leveringskoden er 68 limbs

Den andre er en forvekslet eksponentieringsform. Det finnes to korrekte square-and-multiply-former, og de konsumerer eksponenten i motsatte retninger: høyre-til-venstre-formen multipliserer og kvadrerer deretter basen og må lese biter fra den minst signifikante enden, mens venstre-til-høyre-formen kvadrerer og multipliserer deretter og leser fra den mest signifikante enden. Den modulare inverseringsløkken hadde en høyre-til-venstre-kropp med en bitgjennomgang som gikk mest-signifikant-først. Begge halvdeler er lærebokstoff, kombinasjonen er det ikke, og resultatet er en feil invers som fortsatt ser ut som et plausibelt kroppselement

// Dobling og addisjon i Jacobian-form der målrecorden kan være den
// samme variabelen som en kilde. En kopi av hele recorden ved inngang
// er det eneste pålitelige forsvaret: å skrive Rs limbs forurenser
// senere lesinger av P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // kopier først, og beregn deretter bare fra Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

To prosessleksjoner som kostet mer enn feilene

Inkrementell hurtigfiksing konvergerer ikke på en kryptografisk enhet. Ett utkast ble lappet gjentatte ganger til det bar på 32 dupliserte rutiner og en skadet struktur, og det ble bare fikset ved å skrive det om. Mønsteret å ta i bruk, er enten å skrive det én gang fra en validert speiling eller å skrive det om; en sekvens av lokale fikser på aritmetikk du ennå ikke forstår, akkumulerer raskere enn den retter

Og sjekk tidsstempelet på den kjørbare filen før du tror på et testresultat. Et inkrementelt bygg som kompilerer, men ikke lenker på nytt, kjører den forrige binærfilen, noe som fabrikkerte en hel runde med falske spor om manglende probes og duplisert output. Ved feilsøking av kryptografi bør et uforklarlig resultat utløse spørsmålet «er dette binærfilen jeg nettopp bygde» før «er algoritmen feil»

Ytelse, omfang og hvordan du kaller det

Modulær reduksjon i Brainpool-enheten er bitvis seriell skift-og-trekk fra den høyeste satte biten i produktet, så en multiplikasjon koster grovt sett i størrelsesordenen av bitbredden. En P-256-verifisering havner et sted i de lavere hundre millisekundene, noe som er helt greit for signering eller verifisering av dokumenter og ville være utilstrekkelig for en TLS-terminator. Barrett-reduksjon er den opplagte oppgraderingen og trenger en bredere arbeidsverdi enn den nåværende representasjonen bærer, så det er en endring man gjør når en arbeidsmengde ber om det, snarere enn forebyggende

uses
  PDFlibEd448, PDFlibBrainpool;

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

  // Brainpool: kalleren leverer noncen per signatur, så nonce-
  // politikken blir værende hos applikasjonen
  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;

Merk at Brainpoolens signeringsinngangspunkt tar imot noncen i stedet for å generere én. Det er bevisst: nonce-generering er den aller mest katastrofale tingen å ta feil på i ECDSA, siden en gjentatt eller forutsigbar verdi avslører den private nøkkelen, og avgjørelsen om hvor tilfeldigheten kommer fra, tilhører applikasjonen og dens etterlevelsesregime, ikke et PDF-bibliotek

Disse kurvene står side om side med post-kvantum-arbeidet som er beskrevet i FIPS 204 ML-DSA-artikkelen, og de kobles inn i den samme signerings- og valideringspipelinen som dekkes i PAdES-signering og -validering. For testsertifikater på disse kurvene er den lokale genereringsruten beskrevet i selvsignerte sertifikater med CryptoAPI. Den komplette algoritmematrisen er oppført på produktsiden for losLab PDF Developer Library