Ren Pascal NIST-kurvearitmetikk for PDF-signering

HotPDF utfører elliptisk kurvenøkkelavtale og signaturverifisering for PDF i ren Object Pascal, uten OpenSSL-binding og uten plattformkryptoprovider i veien. Det dekker fem kurver: P-256, P-384 og P-521 for NIST-primefamiliene, pluss X25519 og X448 for Montgomery-kurve nøkkelavtale. Grunnen til å skrive den koden snarere enn å linke den, er utrulling, ikke renhet. En Delphi- eller Free Pascal-applikasjon som sender ut én kjørbar fil og ingen kryptografisk DLL, har ingen versjonsskjevhet å administrere, ingen per-plattform-provider å oppdage, og ingenting som endrer oppførsel når en kunde patcher sine systembiblioteker

Kostnaden er at du nå eier aritmetikken. Stort-heltall modulær multiplikasjon er ubarmhjertig kode: den produserer enten byte-identiske resultater mot publiserte testvektorer, eller den produserer plausibel seende søppel, og avstanden mellom de to tilstandene kan være én enkelt sammenligning. Dette er historien om den sammenligningen, fordi feilens form generaliserer til enhver Pascal-portering av kroppsaritmetikk

Hvorfor trenger et PDF-bibliotek i det hele tatt kurvearitmetikk?

To funksjoner trekker den inn. Den første er offentlig-nøkkelkryptering av dokumenter: ISO 32000 mottakerlistebehandleren pakker en per dokument-nøkkel for navngitte sertifikater, og når en mottaker holder en EC-nøkkel, går pakkingen gjennom nøkkelavtale snarere enn RSA nøkkeltransport. Uten ECDH finnes ingen måte å åpne et slikt dokument på. Den andre er signaturvalidering. Å verifisere en ECDSA-signatur over /ByteRange-bytene trenger en punktmultiplikasjon på signatarens kurve, og P-384 er vanlig i offentlige og kvalifiserte-signatur-profiler der P-256 regnes som gulvet snarere enn målet. HotPDF eksponerer resultatene av det arbeidet gjennom ECDSA- og CMS-verifiseringsveien og gjennom den pluggbare signaturprovider-modellen

CIOS, og den ene subtraksjonen på slutten

Montgomery-multiplikasjon unngår divisjon ved å arbeide i et transformert domene der reduksjon er et skift. Varianten HotPDF bruker er Coarsely Integrated Operand Scanning, som fletter multiplikasjonen og reduksjonen limb for limb slik at mellomproduktet aldri vokser forbi modulusbredden pluss én limb. Løkkekroppen er rettfram og lett å teste. Halen er ikke det: etter de flettede passeringene kan akkumulatoren være hvor som helst i området opp til det dobbelte av modulus, så algoritmen slutter med en betinget subtraksjon som fjerner én kopi av primtallet hvis og bare hvis akkumulatoren er større enn eller lik det

Å sammenligne to multi-limb-tall betyr å gå fra den mest signifikante limben nedover mens man bærer en borrow. Den opplagte måten å skrive det på, er å sammenligne akkumulatorlimben mot moduluslimben pluss innkommende borrow. Det uttrykket er feil, og det er feil på en måte de fleste kurver skjuler

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

// Korrekt: sammenligne uten noensinne å legge til en limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Hvordan ser en borrow wrap-around faktisk ut?

Det ser ut som en kurve som fungerer overalt unntatt i produksjon. Primtallene for P-384 og P-521 inneholder limber som helt er ener, så P[I] er lik $FFFFFFFFFFFFFFFF. Legg den innkommende borrowen på én til det, og en 64-bit usignert wrapper til null. Sammenligningen spør deretter om akkumulatorlimben er mindre enn null, avgjør at den ikke er det, og konkluderer med at ingen borrow trengs. Én limb av resultatet er feil med én

P-256 unnslipper fordi ingen av limbene er alle-ener, så addisjonen flyter aldri over og det feilbårne uttrykket tilfeldigvis er enig med det korrekte. Det er det verste mulige utfallet for en testpakke: den mest-testede kurven passerer, de mindre-testede feiler intermitterende avhengig av operandverdier, og feilen kommer til overflaten som et verifiseringsresultat «ugyldig signatur» på dokumenter som er helt gyldige. HotPDF bar en eksplisitt gate på P-384 av nettopp denne grunnen, og returnerte en utilgjengelig status snarere enn et feil svar, til aritmetikken var bevist mot referansevektorer

Hvordan feilen faktisk ble lokalisert

Ikke ved å lese koden. Den produktive sekvensen var mekanisk, og den er gjenbrukbar. Først, eliminer konstantene: hver limb av p, R og R^2 ble regenerert uavhengig og sammenlignet limb for limb, noe som utelukker den aller vanligste kilden til kurvefeil. For det andre, instrumenter aritmetikken snarere enn API-en: en midlertidig dump-prosedyre skrev ut mellomverdiene av Montgomery-multiplikasjonen av R^2, av x^3 og av y^2 for et kjent punkt, slik at de kunne sjekkes mot uavhengig beregnet sannhet

Den sammenligningen pekte rett på synderen. x-kjeden var korrekt ende til ende, mens y^2 avvek i nøyaktig én limb med nøyaktig én. En enkelt-limb-forskjell på én er ikke en multiplikasjonsfeil, en carry-propageringsfeil eller en konstantfeil; det er en borrow-kjedefeil, og den eneste borrow-kjeden i rutinen er den endelige betingede subtraksjonen. Én detalj sporet dette nesten av: referansekonstanten brukt for dumpen var selv skrevet i feil byte-rekkefølge ved første forsøk, noe som produserte et avvik i y-verdien og kort antydet en annen, ikke-eksisterende defekt. Verifiser endianness til din grunnsannhet før du stoler på den til å anklage koden din

Nabofellene i den samme rutinen

Tre flere feilmoduser bor innenfor noen få linjer fra den sammenligningen, og alle tre var levende på et eller annet tidspunkt under utviklingen

// 1. Akkumulatoren har én limb over modulusbredden. Å sammenligne bare
//    de lave L-limbene mister tilfellet der T er nøyaktig p pluss 2^(64*L),
//    noe som skjer for en meningsfull andel tilfeldige inndata 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-subtraksjon har den samme wrap-faren: når
//    Y[I] er $FFFFFFFFFFFFFFFF, wrapper Y[I] + Borrow til null og
//    borrowen må overleve inn i neste limb snarere enn å bli nullstilt
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 ble først transkribert med 130 heksadesimale siffer i stedet for 131, én F for kort, og Montgomery-konstantene ble deretter beregnet fra det feil primtallet, så konstantene var selv-konsistente og felles feil. Kurveparametere må utledes, aldri tastes: beregn R som (1 shl (64 * L)) mod p fra primtallet du faktisk bruker, og krysssjekk deretter R * R mod p mot verdien R^2-konstanten din hevder. Et par konstanter som er enige med hverandre, beviser ingenting om noen av dem

Verifiseringsstrategi som skalerer utover én kurve

Teknikken som gjorde X25519 og X448 håndterbare, var å skrive en speilimplementering i et språk med ubegrensede heltall og transkribere Pascal kontrollflyten inn i den linje for linje. Når speilingen produserer det riktige svaret og Pascal ikke gjør det, er defekten en transkripsjonsfeil, og å undersøke den samme mellomverdien i begge implementeringene finner den på sekunder. Alle tre klassiske RFC 7748 stigefeilene ble fanget på denne måten: en konstant-tid swap hvis andre linje gjenbrukte den allerede-byttede verdien, en endelig inversjon som returnerte z i potens minus én i stedet for å multiplisere den inn i X, og en liten-konstant-multiplikasjon som monterte halvord-produkter med en bitwise or og mistet carryen

For testmateriale, ta vektorer som byte snarere enn som tekst. Å trekke ut en privat nøkkel med et tekstmønster er hvordan en korrekt implementering blir anklaget for en av-med-én-byte-feil som bor fullstendig i uttrekkssteget. Skjær heksen ut av DER-kodingen ved kjente forskyvninger og sammenligne bytearrayer

Med borrow-kjeden korrigert, matcher alle fem kurver publiserte referansevektorer byte for byte, og HotPDF gater ingen av dem lenger. Hvis du integrerer sertifikatbasert signering eller mottakerlistekryptering, er det praktiske uttaket at kurvevalg nå er en policyavgjørelse snarere enn et evnespørsmål; profilene og byte-rekkefølge-fellgruvene på signeringssiden er dekket i PAdES-signeringsgjennomgangen. Komponentdetaljer og den støttede algoritmematrisen står på produktsiden for HotPDF Delphi PDF component