Ren Pascal NIST-kurve-aritmetik til PDF-signering

HotPDF udfører elliptisk kurve-nøgleaftale og signaturverificering til PDF i ren Object Pascal uden OpenSSL-binding og uden platformkrypto-udbyder i vejen. Det dækker fem kurver: P-256, P-384 og P-521 for NIST-primfamilierne plus X25519 og X448 til Montgomery-kurve-nøgleaftale. Grunden til at skrive den kode frem for at linke den er udrulning, ikke renhed. En Delphi- eller Free Pascal-applikation, der udsender én eksekverbar og ingen kryptografisk DLL, har ingen versionsskew at administrere, ingen pr. platform gældende udbyder at opdage og intet, der ændrer adfærd, når en kunde patcher sine systembiblioteker

Omkostningen er, at du nu ejer aritmetikken. Big-integer-modulær multiplikation er skånselsløs kode: den producerer enten byte-identiske resultater mod offentliggjorte testvektorer eller plausible udseende skrald, og afstanden mellem de to tilstande kan være en enkelt sammenligning. Dette er historien om den sammenligning, for fejlens form generaliserer til enhver Pascal-portering af legemearitmetik

Hvorfor behøver et PDF-bibliotek overhovedet kurve-aritmetik?

To funktioner trækker den ind. Den første er offentlig nøglekryptering af dokumenter: ISO 32000-modtagerlistehåndtereren pakker en pr. dokument gældende nøgle til navngivne certifikater, og når en modtager har en EC-nøgle, kører indpakningen gennem nøgleaftale frem for RSA-nøgletransport. Uden ECDH er der ingen måde at åbne et sådant dokument på. Den anden er signaturvalidering. At verificere en ECDSA-signatur over /ByteRange-bytes behøver en punktmultiplikation på underskriverkurven, og P-384 er almindelig i offentlige og kvalificerede signaturprofiler, hvor P-256 betragtes som gulvet frem for målet. HotPDF eksponerer resultaterne af det arbejde gennem ECDSA- og CMS-verificeringsvejen og gennem den pluggbare signaturudbydermodel

CIOS og den ene subtraktion til sidst

Montgomery-multiplikation undgår division ved at arbejde i et transformeret domæne, hvor reduktion er et shift. Den variant, HotPDF bruger, er Coarsely Integrated Operand Scanning, som fletter multiplikationen og reduktionen limb for limb, så mellemresultatet aldrig vokser forbi modulusbredden plus én limb. Løkkelegemet er ligetil og let at teste. Halen er det ikke: efter de flettede gennemløb kan akkumulatoren være hvor som helst i intervallet op til det dobbelte af modulus, så algoritmen slutter med en betinget subtraktion, der fjerner én kopi af primtallet, hvis og kun hvis akkumulatoren er større end eller lig med det

At sammenligne to multi-limb-tal betyder at gå fra den mest signifikante limb nedad, mens man bærer en borrow. Den oplagte måde at skrive det på er at sammenligne akkumulator-limben med modulus-limben plus den indkommende borrow. Det udtryk er forkert, og det er forkert på en måde, som de fleste kurver skjuler

// Forkert: P[I] + Borrow kan wrappe, når P[I] er $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Korrekt: sammenlign uden nogensinde at lægge til en limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Hvordan ser et borrow wrap-around egentlig ud?

Det ser ud som en kurve, der virker overalt undtagen i produktion. Primtallene for P-384 og P-521 indeholder limbe, der udelukkende er ener, så P[I] er lig $FFFFFFFFFFFFFFFF. Læg den indkommende borrow på én til, og en 64-bit unsigned wrappes til nul. Sammenligningen spørger så, om akkumulator-limben er mindre end nul, beslutter, at den ikke er, og konkluderer, at ingen borrow behøves. Én limb af resultatet er forskudt med én

P-256 slipper nemt, for ingen af dens limbe er kun ener, så additionen overløber aldrig, og det fejlbehæftede udtryk tilfældigvis er enig med det korrekte. Det er det værst tænkelige udfald for en testpakke: den mest testede kurve består, de mindre testede fejler uregelmæssigt afhængigt af operandværdier, og fejlen viser sig som et verificeringsresultat af "invalid signature" på dokumenter, der er fuldstændig gyldige. HotPDF bar en eksplicit gate på P-384 af netop denne grund og returnerede en unavailable-status frem for et forkert svar, indtil aritmetikken var bevist mod referencevektorer

Hvordan fejlen reelt blev lokaliseret

Ikke ved at læse koden. Den produktive sekvens var mekanisk, og den er genanvendelig. For det første: eliminer konstanterne. Hver limb af p, R og R^2 blev regenereret uafhængigt og sammenlignet limb for limb, hvilket udelukker den mest almindelige kilde til kurvefejl. For det andet: instrumentér aritmetikken frem for API'en. En midlertidig dump-procedure udskrev mellemværdierne af Montgomery-multiplikationen af R^2, af x^3 og af y^2 for et kendt punkt, så de kunne tjekkes mod uafhængigt beregnet sandhed

Den sammenligning pegede direkte på synderen. x-kæden var korrekt hele vejen, mens y^2 afveg i præcis én limb med præcis én. En forskel på én i én enkelt limb er ikke en multiplikationsfejl, en carry-propageringsfejl eller en konstantfejl; det er en borrow-kæde-fejl, og den eneste borrow-kæde i rutinen er den afsluttende betingede subtraktion. Én detalje afsporede det næsten: referencekonstanten, der blev brugt til dumpen, var selv skrevet i forkert byte-orden ved første forsøg, hvilket gav en uoverensstemmelse i y-værdien og kort antydede en anden, ikke-eksisterende defekt. Verificér endianness i din grundsandhed, før du stoler på, at den anklager din kode

De nærliggende fælder i samme rutine

Tre fejltilstande mere bor inden for få linjer fra den sammenligning, og alle tre var live på et tidspunkt under udviklingen

// 1. Akkumulatoren har én limb over modulusbredden. At sammenligne kun
//    de lave L-limbe misser tilfældet, hvor T er lig præcis p plus 2^(64*L),
//    hvilket sker for en markant andel af tilfældige inputs, fordi 2p
//    overstiger 2^256 for P-256 og 2^384 for P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. En generisk multi-limb-subtraktion har den samme wrap-fare: når
//    Y[I] er $FFFFFFFFFFFFFFFF, wrappes Y[I] + Borrow til nul, og
//    borrowen skal overleve ind i næste limb frem for at blive ryddet
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Den tredje er ikke kode, det er proveniens. Primtallet for P-521 var oprindeligt transskriberet med 130 hexadecimale cifre i stedet for 131, ét F for lidt, og Montgomery-konstanterne blev derefter beregnet ud fra det forkerte primtal, så konstanterne var selvkonsistente og fælles forkerte. Kurveparametre skal afledes, aldrig tastes: beregn R som (1 shl (64 * L)) mod p ud fra det primtal, du reelt bruger, og krydstjek derefter R * R mod p mod den værdi, din R^2-konstant hævder. Et par konstanter, der er enige med hinanden, beviser ingenting om nogen af dem

Verifikationsstrategi, der skalerer ud over én kurve

Teknikken, der gjorde X25519 og X448 håndterbare, var at skrive en spejlimplementation i et sprog med ubegrænsede heltal og transskribere Pascals kontrolflow ind i den linje for linje. Når spejlet producerer det rigtige svar, og Pascal ikke gør, er defekten en transskriptionsfejl, og at indfange den samme mellemværdi i begge implementationer finder den på sekunder. Alle tre klassiske RFC 7748 ladder-fejl blev fanget på den måde: et constant-time swap, hvis anden linje genbrugte den allerede ombyttede værdi, en afsluttende inversion, der returnerede z i potensen minus én i stedet for at multiplicere den ind i X, og en lille-konstant-multiplikation, der samlede halford-produkter med en bitwise or og mistede carryen

Til testmateriale: tag vektorer som bytes frem for som tekst. At udtrække en privat nøgle med et tekstmønster er sådan, en korrekt implementation bliver anklaget for en off-by-one-byte-fejl, der udelukkende bor i udtrækningstrinnet. Skær hex ud af DER-kodningen ved kendte offsets og sammenligne byte-arrays

Med borrow-kæden rettet matcher alle fem kurver offentliggjorte referencevektorer byte for byte, og HotPDF gater ikke længere nogen af dem. Hvis du integrerer certifikatbaseret signering eller modtagerlistekryptering, er den praktiske konklusion, at kurvevalg nu er en politikbeslutning frem for et evne-spørgsmål; profilerne og byte-ordens-fælderne på signeringssiden er dækket i PAdES-signeringsgennemgangen. Komponentdetaljer og den understøttede algoritmematrise findes på produktsiden HotPDF Delphi PDF component