Aritmetika krivulj NIST v čistem Pascalu za podpis PDF

HotPDF izvede dogovor ključev eliptičnih krivulj in preverjanje podpisov za PDF v čistem Object Pascalu, brez vezave OpenSSL in brez kriptografskega ponudnika platforme na poti. To pokriva pet krivulj: P-256, P-384 in P-521 za praštevilčne družine NIST, plus X25519 in X448 za dogovor ključev na Montgomeryjevi krivulji. Razlog za pisanje te kode namesto povezovanja je namestitev, ne čistost. Aplikacija Delphi ali Free Pascal, ki pošlje eno izvedljivo datoteko in brez kriptografskega DLL, nima odmika različic za upravljanje, brez ponudnika po platformi za odkrivanje in ničesar, kar bi spremenilo vedenje, ko stranka zakrpa svoje sistemske knjižnice

Strošek je, da zdaj lastite aritmetiko. Modularno množenje velikih celih števil je neusmiljena koda: ali proizvede rezultate identične bajtom proti objavljenim testnim vektorjem ali proizvede smeti, ki izgledajo verodostojno, in razdalja med tema dvema stanjema je lahko ena sama primerjava. To je zgodba te primerjave, ker se oblika hrošča generalizira na vsak Pascalov prenos aritmetike telesa

Zakaj sploh PDF knjižnica potrebuje aritmetiko krivulj?

Dve funkciji jo privlečeta noter. Prva je šifriranje dokumentov z javnim ključem: obravnavalec seznamov prejemnikov ISO 32000 ovije ključ na dokument za poimenovane certifikate, in ko prejemnik drži ključ EC, teče ovijanje skozi dogovor ključev in ne skozi prenos ključev RSA. Brez ECDH ni načina odpreti takšnega dokumenta. Druga je validacija podpisov. Preverjanje podpisa ECDSA nad bajti /ByteRange potrebuje množenje točk na krivulji podpisnika, P-384 pa je pogost v vladnih profilih in profilih kvalificiranih podpisov, kjer je P-256 obravnavan kot tla in ne kot cilj. HotPDF izpostavi rezultate tega dela skozi pot preverjanja ECDSA in CMS in skozi model priklopnih ponudnikov podpisov

CIOS in eno odštevanje na koncu

Montgomeryjevo množenje se izogne deljenju z delovanjem v preoblikovanem telesu, kjer je redukcija premik. Različica, ki jo uporablja HotPDF, je Coarsely Integrated Operand Scanning, ki prepleta množenje in redukcijo okončino za okončino, tako da vmesna nikoli ne zraste čez širino modula plus ena okončina. Telo zanke je premo in enostavno za testiranje. Rep ni: po prepletenih prehodih je lahko akumulator kjer koli v razponu do dvakratnika modula, zato se algoritem konča s pogojnim odštevanjem, ki odstrani eno kopijo praštevila natanko takrat, ko je akumulator večji ali enak njemu

Primerjanje dveh števil več okončin pomeni hojo od najbolj pomembne okončine navzdol med nošenjem izposoje. Očiten način pisanja je primerjati okončino akumulatorja proti okončini modula plus dohodnja izposoja. Ta izraz je napačen in je napačen na način, ki ga večina krivulj skriva

// Napačno: P[I] + Borrow se lahko zvije, ko je P[I] $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Pravilno: primerjajte brez dodajanja na okončino
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Kako izgleda zvijanje izposoje dejansko?

Izgleda kot krivulja, ki deluje povsod razen v produkciji. Praštevila za P-384 in P-521 vsebujejo okončine, ki so popolnoma enice, zato je P[I] enako $FFFFFFFFFFFFFFFF. Dodajte dohodnjo izposojo ena temu in 64-bitno neoznačeno se zvije v nič. Primerjava nato vpraša, ali je okončina akumulatorja manjša od nič, se odloči, da ni, in sklepa, da izposoja ni potrebna. Ena okončina rezultata je za ena predaleč

P-256 ubeži, ker nobena od njegovih okončin ni vseh enic, zato se seštevanje nikoli ne prelije in napačen izraz slučajno soglaša s pravilnim. To je najslabši možni izid za testno zbirko: najbolj testirana krivulja gre, manj testirane odpovedo občasno odvisno od vrednosti operandov, odpoved pa se pokaže kot rezultat preverjanja »neveljaven podpis« na dokumentih, ki so popolnoma veljavni. HotPDF je nosil izrecna vrata na P-384 natanko iz tega razloga, vračajoč stanje nerazpoložljivo namesto napačnega odgovora, dokler aritmetika ni bila dokazana proti referenčnim vektorjem

Kako je bil hrošč dejansko lociran

Ne z branjem kode. Produktivno zaporedje je bilo mehansko in je ponovno uporabljivo. Najprej odpravite konstante: vsaka okončina p, R in R^2 je bila znova generirana neodvisno in primerjana okončina za okončino, kar izloči en sam najpogostejši vir napak krivulj. Drugič, opremite aritmetiko in ne API: začasna procedura odlaganja je natisnila vmesne vrednosti Montgomeryjevega množenja R^2, x^3 in y^2 za znano točko, tako da so bile lahko preverjene proti neodvisno izračunani resnici

Ta primerjava je pokazala naravnost na krivca. Veriga x je bila pravilna od konca do konca, y^2 pa se je razlikoval v natanko eni okončini za natanko ena. Razlika ene okončine za ena ni napaka množenja, napaka širjenja prenosa ali napaka konstante; je napaka verige izposoje, edina veriga izposoje v rutini pa je končno pogojno odštevanje. Ena podrobnost je to skoraj izrela s tirnic: referenčna konstanta, uporabljena za odlaganje, je bila sama zapisana v napačnem bajtnem vrstnem redu ob prvem poskusu, kar je proizvedlo neskladje v vrednosti y in za kratek čas nakazalo drugo, neobstoječo napako. Preverite endianness vaše resnice na tleh, preden ji zaupate, da obtoži vašo kodo

Sosednje pasti v isti rutini

Trije nadaljnji načini odpovedi živijo znotraj nekaj vrstic te primerjave in vsi trije so bili živi na neki točki med razvojem

// 1. Akumulator ima eno okončino nad širino modula. Primerjanje samo
//    nizkih L okončin zamudi primer, kjer je T natanko enako p plus
//    2^(64*L), kar se zgodi za smiselni delež naključnih vhodov, ker 2p
//    presega 2^256 za P-256 in 2^384 za P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Splošno odštevanje več okončin ima isto nevarnost zvijanja: ko
//    je Y[I] $FFFFFFFFFFFFFFFF, se Y[I] + Borrow zvije v nič in
//    izposoja mora preživeti v naslednjo okončino namesto da bi bila počiščena
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Tretji ni koda, je poreklo. Praštevilo za P-521 je bilo sprva prepisano s 130 šestnajstiškimi števkami namesto 131, en F kratek, Montgomeryjeve konstante pa so bile nato izračunane iz tega napačnega praštevila, zato so bile konstante samoskladne in skupno napačne. Parametri krivulj morajo biti izpeljani, nikoli tipkani: izračunajte R kot (1 shl (64 * L)) mod p iz praštevila, ki ga dejansko uporabljate, nato navzkrižno preverite R * R mod p proti vrednosti, ki jo vaša konstanta R^2 trdi. Par konstant, ki soglašata drug z drugim, ne dokaže ničesar o nobeni

Strategija preverjanja, ki se meri čez eno krivuljo

Tehnika, ki je naredila X25519 in X448 obvladujoča, je bila pisanje zrcalne implementacije v jeziku z neomejenimi celimi števili in prepisovanje Pascalovega toka nadzora vanjo vrstico za vrstico. Ko zrcalo proizvede pravi odgovor in Pascal ne, je napaka spodrsljaj pri prepisu in sondiranje iste vmesne vrednosti v obeh implementacijah jo najde v sekundah. Vse tri klasične napake lestvice (ladder) RFC 7748 so bile ujete na ta način: izmenjava konstantnega časa, katere druga vrstica je ponovno uporabila že zamenjano vrednost, končna inverzija, ki je vrnila z na potenco minus ena namesto da bi jo pomnožila v X, in množenje z malo konstanto, ki je sestavila produkte pol besed z bitnim ali in izgubila prenos

Za testno gradivo vzemite vektorje kot bajte in ne kot besedilo. Izvlečenje zasebnega ključa z besedilnim vzorcem je način, kako pravilna implementacija dobi obtožbo napake za ena bajt, ki živi povsem v koraku izvlečenja. Režite šestnajstiško iz kodiranja DER na znanih odmikih in primerjajte bajtne matrike

S popravljeno verigo izposoje vseh pet krivulj ujema objavljene referenčne vektorje bajt za bajtom in HotPDF ne postavlja več vrat na nobeno od njiju. Če integrirate podpisovanje na osnovi certifikatov ali šifriranje seznamov prejemnikov, je praktični izkupiček ta, da je izbira krivulje zdaj odločitev politike in ne vprašanje zmožnosti; profili in pasti bajtnega vrstnega reda strani podpisovanja so pokriti v vodniku po podpisovanju PAdES. Podrobnosti komponente in podprta matrika algoritmov so na strani produkta HotPDF Delphi PDF component