Ed448 i Brainpool ECDSA u čistom Pascalu za PDF

PDFlibPas potpisuje i verifikuje sa Ed448 i sa tri Brainpool ECDSA krive u čistom Object Pascalu. Bez spoljne kriptografske biblioteke, bez platformskog provajdera, bez DLL-a: PDFlibEd448 implementira RFC 8032 PureEdDSA na edwards448, a PDFlibBrainpool implementira RFC 5639 brainpoolP256r1, brainpoolP384r1 i brainpoolP512r1. Obe jedinice izgrađene su na isti način, u odnosu na test vektore sa poznatim odgovorima generisane nezavisno pre nego što je ijedna linija Pascala napisana, i obe vredi opisati pre svega zbog grešaka

Aritmetika polja je neobično pošten kod. Ili se poklapa sa objavljenim vektorima bajt po bajt ili se ne poklapa, pa nema mesta za "skoro ispravno". Ono što otežava posao jeste to što pogrešna implementacija i dalje proizvodi potpise, i dalje verifikuje sopstvene potpise i i dalje deluje potpuno uverljivo

Zašto baš ove krive i zašto u Pascalu

Brainpool krive pojavljuju se u evropskim profilima kvalifikovanih potpisa, pa biblioteka koja potpisuje dokumente za to tržište ne može da ih tretira kao egzotiku. Ed448 je u skupu algoritama koje ISO/TS 32002 unosi u PDF, gde je njegov interni sažetak SHAKE256 umesto SHA-2. Ni jedna od te dve familije nije dostupna u uobičajeno korišćenim Pascal kriptografskim bibliotekama, pa ih PDF biblioteka koja ih želi mora sama posedovati

Argument za raspoređivanje isti je kao i za svu kriptografiju ove biblioteke: aplikacija koja isporučuje jednu binarnu datoteku bez kriptografske zavisnosti nema provajdera za otkrivanje, nema verziju za upoređivanje i nema ponašanje koje se menja kada se domaćin zakrpi. Potpisivanje je upravo oblast u kojoj najmanje želite pokretnu zavisnost

Konstante dolaze iz teksta specifikacije, nikada iz memorije

Prvi pokušaj bazne tačke edwards448 napisan je iz memorije i bio je pogrešan. To nije izuzetna greška i vrlo je skupa, jer pogrešna bazna tačka proizvodi samo-konzistentan sistem: vaše generisanje ključeva, potpisivanje i verifikacija slažu se međusobno i ne slažu sa ostatkom sveta

Funkcionišuća procedura je da se svaki domen parametar uzme iz teksta specifikacije, a zatim unakrsno verifikuje. Za edwards448 to znači prost broj, konstantu krive, red grupe i obe decimalne koordinate bazne tačke iz RFC 8032, pretvorene u interno limb predstavljanje, a zatim proverene u odnosu na objavljene test vektore iz istog dokumenta. Za Brainpool krive to znači parametre iz RFC 5639, nezavisnu implementaciju napisanu za generisanje vektora i unakrsnu proveru u odnosu na sistemsku biblioteku u oba smera pre nego što je bilo kakav Pascal pokrenut

Jedna prečica pri izvođenju zaslužuje upozorenje jer deluje univerzalno a nije: rekonstrukcija bazne tačke iz fiksne vrednosti y funkcioniše za krivu 25519 i ne funkcioniše za edwards448, gde ta vrednost nema kvadratni koren. Skripta ju je opovrgla u nekoliko sekundi, što je mnogo jeftinije nego da je otkrijete kroz debugger

Metoda: ogledalna implementacija na nivou limbova pre bilo kakvog Pascala

Tehnika koja je učinila obe jedinice obvladivim jeste ogledalna implementacija u jeziku sa neograničenim celim brojevima, izgrađena odozdo nagore. Prvo sam aritmetički sloj: množenje po polju, oduzimanje i propagacija prenosa, stres-testirani u odnosu na njihove algebarske invarijante na nekoliko stotina slučajnih slučajeva. Zatim kompletno generisanje ključeva unutar ogledala, gde žive semantičke greške i gde je jeftino pronaći ih. Tek tada Pascal transkripcija

Korist je dijagnostička pre nego razvojna. Kada se jednom zna da je ogledalo ispravno, svako neslaganje između ogledala i Pascala je greška u transkripciji, i ispitivanje iste međuvrednosti u obe implementacije odmah je locira. To klasu grešaka koja je inače skoro nedebugabilna, jedan pogrešan limb duboko unutar skalarnog množenja, pretvara u poređenje od pet minuta

Četiri osnovna uzroka u Ed448

Sva četiri pronađena su ispitivanjem međuvrednosti, i sva četiri su vrsta problema koja proizvodi izlaz koji deluje valjano

Prvi je zamka notacije. Većina objavljenih formula za ujedinjeno Edwards sabiranje pretpostavlja konstantu krive minus jedan, a edwards448 ima plus jedan. Prenešeno nepromenjeno, brojilac y koordinate piše se kao zbir gde treba biti razlika. Popravka nije zakrpa znaka nego ponovno izvođenje oblika proizvoda bez inverzije iz afinog zakona sabiranja za ispravnu krivu, što proizvodi četiri izraza koordinata i ne ostavlja mesta da se znak nasledi iz pogrešnog izvora

Drugi je u dekompresiji tačke. Rekonstrukcija afine x iz projektivnih koordinata zahteva jedno množenje inverzom Z. Množenje kvadratom inverza daje vrednost koja je i dalje valjana projektivna reprezentacija i koja je pogrešna afina koordinata, pa je simptom ispravan y sa pogrešnim x-om. Svaki put kada je jedna koordinata ispravna a druga nije, greška je u normalizaciji, ne u aritmetici

Treći je navika uvezena sa kraće krive. I skalarni broj po potpisu i skalarni izazov moraju se redukovati iz kompletnog sažetka, koji je za Ed448 114 bajtova, a ne iz njegovih prvih 57. Kriva od 32 bajta takođe koristi svoj pun sažetak od 64 bajta, pa je pravilo konzistentno; pogrešna je samo pretpostavka da je "pola sažetka širina skalara"

Četvrti je redosled. Prefiks separacije domena dolazi prvi, pre prefiksa konteksta i poruke, što nije redosled koji sugeriše intuitivno čitanje R i A u specifikaciji. Greška ovde proizvodi potpise koji se verifikuju u odnosu na vašu sopstvenu implementaciju i ništa drugo, što je najobmanjujući mogući neuspeh

// Dizajn prenosa po polju: čista propagacija sa floor semantikom, pa
// i pozitivni i negativni limbovi rade, a oduzimanje ne traži bias.
// Gornji prenos savija se nazad preko 2^448 = 2^224 + 1 (mod p), što
// dira limb 0 i limb 8. Ograničeno na četiri kruga; dva viđena
// u praksi
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]);          // floor, ne odsecanje
      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;

Starija verzija te rutine primenjivala je bias pre propagacije, i pri velikim ulazima savijala je lažan prenos pogrešnog reda veličine u donje limbove. Šeme prenosa zasnovana na bias-u uporna su izvor ove klase defekata; floor semantika sa ograničenom ponavljajućom petljom lakša je za rasuđivanje i merljivo dovoljno brza

Dva osnovna uzroka u Brainpool

Prvi uopšte nije kriptografija. Radna reprezentacija ima 33 limbova, pa proizvod dve vrednosti traži 66, a niz proizvoda deklarisan je sa 64. Pisanje preko kraja oštetilo je susednu memoriju, što se najpre manifestovalo kao pogrešni rezultati, a tek je postalo pad kada je dodat širi sken. Pravilo koje je iz toga izašlo vredi primeniti na svaki numerički bafer fiksne veličine: odredite veličinu prema najgoroj širini proizvoda, dodajte rezervu, a zatim o tome nikad više ne razmišljajte. Niz u kodu koji se isporučuje ima 68 limbova

Drugi je pomešani oblik stepenovanja. Postoje dva ispravna oblika kvadriraj-i-množi i oni troše eksponent u suprotnim smerovima: oblik sdesna-ulevo množi pa kvadrira bazu i mora čitati bitove od najmanje značajnog kraja, dok oblik sleva-udesno kvadrira pa množi i čita od najznačajnijeg kraja. Petlja modularne inverzije imala je telo sdesna-ulevo sa obilaskom bitova počevši od najznačajnijeg. Obe polovine su udžbeničke, kombinacija nije, a rezultat je pogrešan inverz koji i dalje deluje kao uverljiv element polja

// Jakobijansko udvajanje i sabiranje gde ciljni zapis može biti
// ista promenljiva kao izvor. Kopija celog zapisa na ulazu jedina je
// pouzdana odbrana: pisanje u limbove R zagađuje kasnija čitanja P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // prvo kopiraj, pa računaj samo iz Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Dve lekcije procesa koje su koštale više od grešaka

Inkrementalno krpljenje u hodu ne konvergira ka kriptografskoj jedinici. Jedan nacrt krpljen je višestruko dok nije nosio 32 duplicirane rutine i oštećenu strukturu, i popravljen je tek prepisivanjem. Obrazac koji treba usvojiti je ili napisati ga jednom iz validiranog ogledala ili ga prespisati; niz lokalnih popravki aritmetike koju još ne razumete nagomilava se brže nego što je koriguje

I proverite vremenski pečat izvršne datoteke pre nego što poverujete rezultatu testa. Inkrementalna izgradnja koja kompajlira ali ne relinkuje pokreće prethodnu binarnu datoteku, što je proizvelo celu rundu lažnih tragova o nedostajućim sondama i dupliciranom izlazu. Pri otklanjanju grešaka u kriptografiji, neobjašnjiv rezultat treba da podstakne pitanje "da li je ovo binarna datoteka koju sam upravo izgradio" pre pitanja "da li je algoritam pogrešan"

Performanse, obuhvat i kako ga pozvati

Modularna redukcija u Brainpool jedinici je bitno-serijsko pomeranje-i-oduzimanje od najvišeg postavljenog bita proizvoda, pa množenje košta otprilike reda širine bita. P-256 verifikacija staje u donje stotine milisekundi, što je neupadljivo za potpisivanje ili verifikaciju dokumenata, a bilo bi nedovoljno za TLS terminator. Barrettova redukcija je očigledno unapređenje i traži širu radnu vrednost nego što trenutna reprezentacija nosi, pa je to promena koju treba napraviti kada radno opterećenje to zatraži, a ne unapred

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, SHAKE256 interno, ključevi od 57 bajtova
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: pozivalac dostavlja nonce po potpisu, pa politika
  // nonce-a ostaje u aplikaciji
  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;

Obratite pažnju da Brainpool ulazna tačka potpisivanja prima nonce umesto da ga generiše. To je namerno: generisanje nonce-a jedina je najkatastrofalnija stvar koju u ECDSA možete pogrešiti, jer ponovljena ili predvidiva vrednost otkriva privatni ključ, a odluka o tome odakle dolazi slučajnost pripada aplikaciji i njenom režimu usaglašenosti, ne PDF biblioteci

Ove krive stoje uz post-quantum rad opisan u članku o FIPS 204 ML-DSA, i uključuju se u isti pipeline potpisivanja i validacije pokriven u PAdES potpisivanju i validaciji. Za test sertifikate na ovim krivama, put lokalnog generisanja opisan je u samopotpisanim sertifikatima sa CryptoAPI-jem. Kompletna matrica algoritama navedena je na stranici proizvoda losLab PDF Developer Library