Ed448 och Brainpool-ECDSA i ren Pascal för PDF

PDFlibPas signerar och verifierar med Ed448 och med de tre Brainpool-ECDSA-kurvorna i ren Object Pascal. Inget externt kryptografiskt bibliotek, ingen plattformsprovider, ingen DLL: PDFlibEd448 implementerar RFC 8032 PureEdDSA på edwards448 och PDFlibBrainpool implementerar RFC 5639 brainpoolP256r1, brainpoolP384r1 och brainpoolP512r1. Båda byggdes på samma sätt, mot känd-svar-vektorer som genererades oberoende innan någon Pascal skrevs, och båda är värda att skriva om främst för buggarnas skull

Kroppsaritmetiken är ovanligt ärlig kod. Den matchar antingen publicerade vektorer byte för byte eller så gör den inte det, så det finns inget utrymme för ett tillstånd av mestadels fungerande. Det som gör den svår är att en felaktig implementering ändå producerar signaturer, ändå verifierar sina egna signaturer och ändå ser helt plausibel ut

Varför dessa kurvor, och varför i Pascal

Brainpool-kurvorna förekommer i europeiska profiler för kvalificerade signaturer, så ett bibliotek som signerar dokument för den marknaden kan inte behandla dem som exotiska. Ed448 ingår i algoritmuppsättningen som ISO/TS 32002 ger till PDF, där dess interna sammandrag är SHAKE256 i stället för SHA-2. Ingen av de två familjerna finns i de Pascal-kryptografiska bibliotek som är i vanligt bruk, så ett PDF-bibliotek som vill ha dem får äga dem själv

Distributionsargumentet är detsamma som gäller all kryptografi i detta bibliotek: en applikation som levererar en binärfil utan kryptografiskt beroende har ingen provider att detektera, ingen version att matcha och inget beteende som ändras när värdsystemet patchas. Signering är precis det område där du minst av allt vill ha ett rörligt beroende

Konstanterna tas från specifikationstexten, aldrig från minnet

Ett första försök till edwards448-baspunkt skrevs ur minnet och blev fel. Det är inte ett anmärkningsvärt misstag, men det är ett mycket dyrt sådant, för en fel baspunkt ger ett självkonsistent system: din nyckelgenerering, signering och verifiering håller med varandra och står i strid med resten av världen

Den fungerande proceduren är att hämta varje domänparameter från specifikationstexten och sedan korsverifiera. För edwards448 innebär det primtalet, kurvkonstanten, gruppordningen och båda decimala koordinaterna för baspunkten ur RFC 8032, omvandlade till den interna limb-representationen och därefter kontrollerade mot publicerade testvektorer ur samma dokument. För Brainpool-kurvorna innebär det parametrarna ur RFC 5639, en oberoende implementering skriven för att generera vektorer och en korskontroll mot ett systembibliotek i båda riktningarna innan någon Pascal kördes

En genväg vid härledningen förtjänar en varning eftersom den ser universell ut och inte är det: att återvinna baspunkten från ett fast y-värde fungerar för 25519-kurvan och fungerar inte för edwards448, där det värdet saknar kvadratrot. Ett skript motbevisade den på sekunder, vilket är mycket billigare än att upptäcka det genom en debugger

Metoden: en spegel på limb-nivå innan någon Pascal

Tekniken som gjorde båda enheterna hanterbara är en spegelimplementering i ett språk med obegränsade heltal, byggd nerifrån och upp. Först enbart aritmetiklagret: multiplikation, subtraktion och carriespridning i kroppen, stresstestade mot sina algebraiska invarianter över ett par hundra slumpmässiga fall. Sedan den fullständiga nyckelgenereringen inuti spegeln, vilket är där de semantiska buggarna bor och där de är billiga att hitta. Först därefter Pascal-överföringen

Utbytet är diagnostiskt snarare än utvecklingsmässigt. När spegeln väl är känd korrekt är varje avvikelse mellan spegel och Pascal ett överföringsfel, och att sondera samma mellanvärde i båda implementeringarna lokaliserar det omedelbart. Det förvandlar en klass av buggar som annars är nästan odebuggbar, ett enda felaktigt limb djupt inne i en skalärmultiplikation, till en femminuters jämförelse

Fyra grundorsaker i Ed448

Alla fyra hittades genom att sondera mellanvärden, och alla fyra är av det slag som producerar utdata som ser giltigt ut

Den första är en notationsfälla. De flesta publicerade formler för unified Edwards-addition förutsätter en kurvkonstant på minus ett, och edwards448 har plus ett. Överförd oförändrad skrivs täljaren av y-koordinaten som en summa där den borde vara en differens. Rättelsen är inte att lappa tecknet utan att härleda den inversfria produktformen om från den affina additionslagen för rätt kurva, vilket ger de fyra koordinatuttrycken och inte lämnar något utrymme för att ett tecken ska ärvas från fel källa

Den andra sitter i punktdekomprimering. Att återvinna den affina x-koordinaten ur projektiva koordinater kräver en multiplikation med inversen av Z. Multiplicera med den kvadrerade inversen i stället ger ett värde som fortfarande är en giltig projektiv representation men är den felaktiga affina koordinaten, så symptomet är en korrekt y med en felaktig x. Närhelst en koordinat stämmer och den andra inte gör det sitter buggen i normaliseringen, inte i aritmetiken

Den tredje är en vana importerad från den kortare kurvan. Både skalären per signatur och challenge-skälären måste reduceras från det fullständiga sammandraget, som för Ed448 är 114 byte, inte från dess första 57. 32-byte-kurvan använder också sitt fulla 64-byte-sammandrag, så regeln är konsekvent; det är bara antagandet att hälften av sammandraget är skalärbredden som är fel

Den fjärde är ordningen. Domänsepareringsprefixet kommer först, före kontextprefixet och meddelandet, vilket inte är den ordning som en intuitiv läsning av R och A i specifikationen antyder. Att få detta fel ger signaturer som verifierar mot din egen implementering och inget annat, vilket är det mest vilseledande tänkbara misslyckandet

// Design av kroppscarry: ren spridning med golvsemantik, så att
// både positiva och negativa limbs fungerar och subtraktion inte
// behöver någon bias. Topp-carryn viks tillbaka via 2^448 = 2^224 + 1
// (mod p), vilket berör limb 0 och limb 8. Begränsad till fyra
// varv; två iakttagna i praktiken
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]);          // golv, inte 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 tidigare version av den rutinen applicerade en bias före spridningen, och vid stora indatavärden vek den in en spurios carry av fel storleksordning i de låga limbs. Carry-scheman baserade på bias är en beständig källa till denna klass av defekter; golvsemantik med en begränsad upprepningsloop är lättare att resonera om och mätbart snabb nog

Två grundorsaker i Brainpool

Den första är inte kryptografi alls. Den fungerande representationen är 33 limbs, så produkten av två värden behöver 66, och produktarrayen var deklarerad med 64. Att skriva förbi slutet korrumperade angränsande minne, vilket först visade sig som felaktiga resultat och först blev en krasch när en bredare skanning lades till. Regeln som kom ur det är värd att tillämpa på varje numerisk buffert med fast storlek: dimensionera den efter produktbredden i värsta fall och lägg till marginal, och tänk sedan aldrig på det igen. Arrayen i den levererade koden är 68 limbs

Den andra är en ihopblandad exponentieringsform. Det finns två korrekta square-and-multiply-former och de konsumerar exponenten i motsatta riktningar: höger-till-vänster-formen multiplicerar och kvadrerar sedan basen och måste läsa bitar från den minst signifikanta änden, medan vänster-till-höger-formen kvadrerar och multiplicerar sedan och läser från den mest signifikanta änden. Den modulära inversloopen hade en höger-till-vänster-kropp med en bitvandring som börjar mest signifikant. Båda halvorna är läroboksmaterial, kombinationen är det inte, och resultatet är en felaktig invers som ändå ser ut som ett plausibelt kroppselement

// Jacobiansk dubbling och addition där destinationsposten kan vara
// samma variabel som en källa. En hel-postkopia vid inträdet är det
// enda tillförlitliga skyddet: att skriva till R:s limbs förorenar
// senare läsningar av P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // kopiera först, beräkna sedan bara från Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Två processlärdomar som kostade mer än buggarna

Inkrementell hotfixning konvergerar inte på en kryptografisk enhet. Ett utkast patchades om och om igen tills det bar på 32 duplicerade rutiner och en skadad struktur, och det blev bara lagat genom att skrivas om. Mönstret att anta är att antingen skriva det en gång från en validerad spegel eller skriva om det; en sekvens av lokala fixar på aritmetik du ännu inte förstår ackumuleras snabbare än den rättar

Och kontrollera tidsstämpeln på den körbara filen innan du tror på ett testresultat. En inkrementell byggnad som kompilerar men inte länkar om kör den föregående binärfilen, vilket tillverkade en hel runda av falska spår om saknade sonder och duplicerad utdata. Vid felsökning av kryptografi bör ett oförklarligt resultat väcka frågan ”är detta binärfilen jag just byggde” innan frågan ”är algoritmen fel”

Prestanda, omfattning och hur man anropar den

Modulär reduktion i Brainpool-enheten är bitseriell skift-och-subtrahera från den högsta sättade biten i produkten, så en multiplikation kostar grovt sett i storleksordningen bitbredden. En P-256-verifiering hamnar i de låga hundratala millisekunderna, vilket är tämligen obetydligt för signering eller verifiering av dokument och skulle vara otillräckligt för en TLS-terminator. Barrett-reduktion är den uppenbara uppgraderingen och behöver ett bredare arbetsvärde än den nuvarande representationen bär, så det är en förändring att göra när en arbetsbelastning kräver det snarare än förebyggande

uses
  PDFlibEd448, PDFlibBrainpool;

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

  // Brainpool: anroparen levererar noncen per signatur, så
  // nonce-policyn stannar 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;

Observera att ingångspunkten för Brainpool-signering tar noncen i stället för att generera en. Det är medvetet: noncegenerering är den allra mest katastrofala saken att få fel i ECDSA, eftersom ett upprepat eller förutsägbart värde röjer den privata nyckeln, och beslutet om var slumpen kommer från tillhör applikationen och dess regelefterlevnadsregim, inte ett PDF-bibliotek

Dessa kurvor står sida vid sida med post-kvant-arbetet som beskrivs i artikeln om FIPS 204 ML-DSA, och de kopplas in i samma signerings- och valideringspipeline som tas upp i PAdES-signering och validering. För testcertifikat på dessa kurvor beskrivs den lokala genereringsvägen i självsignerade certifikat med CryptoAPI. Den fullständiga algoritmmatrisen finns listad på produktsidan för losLab PDF Developer Library