Ren Pascal-aritmetik för NIST-kurvor vid PDF-signering

HotPDF utför elliptisk kurvnyckelöverenskommelse och signaturverifiering för PDF i ren Object Pascal, utan OpenSSL-bindning och utan plattformskryptoprovidern i vägen. Det täcker fem kurvor: P-256, P-384 och P-521 för NIST-primfamiljerna, plus X25519 och X448 för nyckelöverenskommelse på Montgomery-kurvor. Anledningen att skriva den koden snarare än att länka den är distribution, inte renhet. En Delphi- eller Free Pascal-applikation som levererar en körbar fil och inget kryptografiskt DLL har ingen versionsskevhet att hantera, ingen per plattform-provider att detektera och inget som ändrar beteende när en kund patchar sina systembibliotek

Kostnaden är att du nu äger aritmetiken. Modulär multiplikation av stora heltal är obarmhärtig kod: den ger antingen byteidentiska resultat mot publicerade testvektorer eller så ger den plausibelt seende skräp, och avståndet mellan de två tillstånden kan vara en enda jämförelse. Detta är berättelsen om den jämförelsen, eftersom buggens form generaliserar till vilken Pascal-port av kroppsaritmetik som helst

Varför behöver ett PDF-bibliotek överhuvudtaget kurvaritmetik?

Två funktioner drar in den. Den första är publik nyckelkryptering av dokument: ISO 32000-mottagarlistehanteraren wrappar en nyckel per dokument för namngivna certifikat, och när en mottagare har en EC-nyckel går wrappningen via nyckelöverenskommelse i stället för RSA-nyckeltransport. Utan ECDH finns inget sätt att öppna ett sådant dokument. Den andra är signaturvalidering. Att verifiera en ECDSA-signatur över /ByteRange-bytena behöver en punktmultiplikation på undertecknarkurvan, och P-384 är vanlig i statliga och kvalificerade signaturprofiler där P-256 ses som golvet snarare än målet. HotPDF exponerar resultatet av det arbetet via ECDSA- och CMS-verifieringsvägen och via den pluggbara signaturprovidermodellen

CIOS och den enda subtraktionen på slutet

Montgomery-multiplikation undviker division genom att arbeta i en transformerad domän där reduktion är ett skift. Den variant HotPDF använder är Coarsely Integrated Operand Scanning, som flätar ihop multiplikationen och reduktionen limb för limb så att mellanvärdet aldrig växer förbi modulusbredden plus en limb. Loopkroppen är enkel och lätt att testa. Svansen är inte det: efter de flätade passerna kan ackumulatorn ligga var som helst i intervallet upp till dubbla modulus, så algoritmen slutar med en villkorlig subtraktion som tar bort en kopia av primtalet om och bara om ackumulatorn är större än eller lika med det

Att jämföra två multi-limb-tal betyder att vandra från den mest signifikanta limben nedåt medan man bär på en borrow. Det uppenbara sättet att skriva det är att jämföra ackumulatorlimben mot moduluslimben plus inkommande borrow. Det uttrycket är fel, och det är fel på ett sätt som de flesta kurvor gömmer

// Fel: P[I] + Borrow kan wrap:a när P[I] är $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Rätt: jämför utan att någonsin addera till en limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Hur ser en borrow-överrullning egentligen ut?

Den ser ut som en kurva som fungerar överallt utom i produktion. Primtalen för P-384 och P-521 innehåller limbar som är helt ettor, så P[I] är lika med $FFFFFFFFFFFFFFFF. Lägg till den inkommande borrow av ett till det och ett 64-bit osignerat värde wrap:ar till noll. Jämförelsen frågar sedan om ackumulatorlimben är mindre än noll, avgör att den inte är det och drar slutsatsen att ingen borrow behövs. En limb av resultatet är fel med ett

P-256 undkommer eftersom ingen av dess limbar är enbart ettor, så additionen svämmar aldrig över och det buggiga uttrycket råkar stämma med det korrekta. Det är det sämsta tänkbara utfallet för en testsvit: den mest testade kurvan passerar, de mindre testade misslyckas periodvis beroende på operandvärden, och felet ytan som ett verifieringsresultat av ”ogiltig signatur” på dokument som är helt giltiga. HotPDF bar en uttrycklig spärr på P-384 av exakt den anledningen, med returnering av en otillgänglig-status i stället för ett felaktigt svar, tills aritmetiken var beprövad mot referensvektorer

Hur buggen egentligen lokaliserades

Inte genom att läsa koden. Den produktiva sekvensen var mekanisk, och den är återanvändbar. Först, eliminera konstanterna: varje limb av p, R och R^2 regenererades oberoende och jämfördes limb för limb, vilket utesluter den enskilt vanligaste källan till kurvbuggar. Sedan, instrumentera aritmetiken i stället för API:et: en tillfällig dumpprocedur skrev ut mellanvärdena av Montgomery-multiplikationen av R^2, av x^3 och av y^2 för en känd punkt, så att de kunde kontrolleras mot oberoende beräknad sanning

Den jämförelsen pekade rakt på boven. x-kedjan var korrekt ände till ände, medan y^2 skilde sig i exakt en limb med exakt ett. En enskild limb-skillnad på ett är inte en multiplikationsbugg, en carry-spridningsbugg eller en konstantbugg; det är en borrow-kedjebugg, och den enda borrow-kedjan i rutinen är den avslutande villkorliga subtraktionen. En detalj spårade ur detta nästan: referenskonstanten som användes för dumpen var själv skriven i fel byteordning vid första försöket, vilket gav en avvikelse i y-värdet och kort antydde en andra, icke existerande defekt. Verifiera byteordningen hos din referenssanning innan du litar på den för att anklaga din kod

De närliggande fällorna i samma rutin

Ytterligare tre fellägen bor inom några rader från den jämförelsen, och alla tre var levande någon tid under utvecklingen

// 1. Ackumulatorn har en limb ovanför modulusbredden. Att jämföra bara
//    de låga L limbarna missar fallet där T är exakt p plus 2^(64*L),
//    vilket händer för en betydande andel slumpmässiga indata eftersom 2p
//    överstiger 2^256 för P-256 och 2^384 för P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. En generisk multi-limb-subtraktion har samma wrap-risk: när
//    Y[I] är $FFFFFFFFFFFFFFFF wrap:ar Y[I] + Borrow till noll och
//    borrow måste överleva in i nästa limb i stället för att rensas
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Den tredje är inte kod, det är ursprung. Primtalet för P-521 transkriberades initialt med 130 hexadecimala siffror i stället för 131, en F för kort, och Montgomery-konstanterna beräknades sedan från det felaktiga primtalet, så konstanterna var självkonsistenta och gemensamt felaktiga. Kurvparametrar måste härledas, aldrig knappa in: beräkna R som (1 shl (64 * L)) mod p från primtalet du faktiskt använder, och korskontrollera sedan R * R mod p mot det värde din R^2-konstant utger sig för. Ett par konstanter som stämmer med varandra bevisar inget om någon av dem

Verifieringsstrategi som skalar bortom en kurva

Tekniken som gjorde X25519 och X448 hanterbara var att skriva en spegelimplementering i ett språk med obegränsade heltal och transkribera Pascal-kontrollflödet in i den rad för rad. När spegeln ger rätt svar och Pascal inte gör det är defekten ett transkriptionsfel, och att sondera samma mellanvärde i båda implementeringarna hittar det på sekunder. Alla tre klassiska misstagen i RFC 7748-stegen fångades på det sättet: en constant-time-swap vars andra rad återanvände det redan växlade värdet, en avslutande inversion som returnerade z upphöjt till minus ett i stället för att multiplicera in den i X, och en multiplikation med liten konstant som sammansatte halvordsprodukter med ett bitvis or och tappade carryn

För testmaterial, ta vektorer som byte i stället för som text. Att extrahera en privat nyckel med ett textmönster är hur en korrekt implementering blir anklagad för ett av-en-byte-fel som bor helt i extraheringssteget. Skär ut hex ur DER-kodningen vid kända offset och jämför bytearrayer

Med borrow-kedjan korrigerad matchar alla fem kurvor publicerade referensvektorer byte för byte, och HotPDF spärrar inte längre någon av dem. Om du integrerar certifikatbaserad signering eller mottagarlistekryptering är det praktiska medskicket att kurvval nu är ett policybeslut snarare än en förmågefråga; profilerna och byteordningsfällorna på signeringssidan tas upp i genomgången av PAdES-signering. Komponentdetaljer och den stödda algoritmmatrisen finns på produktsidan för HotPDF Delphi PDF component