Ed448 i Brainpool ECDSA u čistom Pascalu za PDF

PDFlibPas potpisuje i provjerava s Ed448 i s tri Brainpool ECDSA krivulje u čistom Object Pascalu. Bez vanjske kriptografske knjižnice, bez platformskog davatelja, bez DLL-a: PDFlibEd448 implementira RFC 8032 PureEdDSA na edwards448, a PDFlibBrainpool implementira RFC 5639 brainpoolP256r1, brainpoolP384r1 i brainpoolP512r1. Obje su jedinice izgrađene na isti način, u odnosu na vektore poznatih odgovora generirane neovisno prije nego što je ijedan redak Pascala napisan, i obje vrijedi opisati prije svega zbog grešaka

Aritmetika polja neobično je iskren kôd. Ili se poklapa s objavljenim vektorima bajt po bajt ili se ne poklapa, pa nema prostora za "uglavnom radi". Ono što to otežava jest to da pogrešna implementacija i dalje proizvodi potpise, i dalje provjerava vlastite potpise i i dalje izgleda potpuno uvjerljivo

Zašto baš te krivulje i zašto u Pascalu

Brainpool krivulje pojavljuju se u europskim profilima kvalificiranih potpisa, pa knjižnica koja potpisuje dokumente za to tržište ne može ih tretirati kao egzotične. Ed448 je u skupu algoritama koje ISO/TS 32002 donosi u PDF, gdje je njegov interni sažetak SHAKE256, a ne SHA-2. Ni jedna od te dvije obitelji nije dostupna u uobičajeno korištenim Pascal kriptografskim knjižnicama, pa ih PDF knjižnica koja ih želi mora posjedovati sama

Argument o raspoređivanju isti je onaj koji vrijedi za svu kriptografiju ove knjižnice: aplikacija koja isporučuje jednu binarnu datoteku bez kriptografske ovisnosti nema davatelja kojeg treba otkriti, nema verziju koju treba uskladiti i nema ponašanje koje se mijenja kada se domaćin zakrpi. Potpisivanje je točno područje u kojem najmanje želite pokretnu ovisnost

Konstante dolaze iz teksta specifikacije, nikad iz memorije

Prvi pokušaj točke baze edwards448 napisan je napamet i bio je pogrešan. To nije izvanredna greška, ali je vrlo skupa, jer pogrešna točka baze proizvodi samokonzistentan sustav: vaše generiranje ključeva, potpisivanje i provjera valjanosti slažu se međusobno i ne slažu se s ostatkom svijeta

Radni postupak je da se svaki parametar domene uzme iz teksta specifikacije, a zatim unakrsno provjeri. Za edwards448 to znači prost broj, konstantu krivulje, red grupe i obje decimalne koordinate točke baze iz RFC 8032, pretvorene u internu limb reprezentaciju, a zatim provjerene u odnosu na objavljene testne vektore iz istog dokumenta. Za Brainpool krivulje to znači parametre iz RFC 5639, neovisnu implementaciju napisanu za generiranje vektora i unakrsnu provjeru u odnosu na sistemsku knjižnicu u oba smjera prije nego što je bilo koji Pascal pokrenut

Jedan prečac pri izvođenju zaslužuje upozorenje jer izgleda univerzalno a nije: rekonstrukcija točke baze iz fiksne vrijednosti y radi za krivulju 25519 i ne radi za edwards448, gdje ta vrijednost nema kvadratni korijen. Skripta ju je opovrgnula u nekoliko sekundi, što je mnogo jeftinije nego to otkriti kroz debugger

Metoda: zrcalna implementacija na razini limbova prije bilo kojeg Pascala

Tehnika koja je obje jedinice učinila savladivim jest zrcalna implementacija u jeziku s neograničenim cjelobrojnim vrijednostima, izgrađena od dna prema gore. Najprije sami aritmetički sloj: množenje polja, oduzimanje i propagacija prijenosa, stresno testirani u odnosu na njihove algebarske invariante kroz nekoliko stotinu slučajnih primjera. Zatim puno generiranje ključeva unutar zrcala, tamo gdje žive semantičke greške i gdje su jeftine za pronalaženje. Tek onda Pascalov prijepis

Korist je dijagnostička, a ne razvojna. Kad se jednom zna da je zrcalo ispravno, svako neslaganje između zrcala i Pascala jest promašaj u prijepisu, a ispitivanje iste međuvrijednosti u obje implementacije odmah ga locira. To razred grešaka koji je inače gotovo nerazradašljiv — jedan pogrešan limb duboko unutar množenja skalarom — pretvara u usporedbu od pet minuta

Četiri korijenska uzroka u Ed448

Sva četiri pronađena su ispitivanjem međuvrijednosti, a sva četiri su onakva da proizvode izlaz koji izgleda valjano

Prvi je zamka notacije. Većina objavljenih formula za ujedinjeno Edwards zbrajanje pretpostavlja konstantu krivulje minus jedan, a edwards448 ima plus jedan. Prenesena nepromijenjena, brojnik koordinate y zapisan je kao zbroj gdje treba biti razlika. Ispravak nije zakrpa predznaka nego ponovno izvođenje oblika produkta bez inverzije iz afinog zakona zbrajanja za ispravnu krivulju, što proizvodi četiri izraza koordinata i ne ostavlja prostora da se predznak naslijedi iz pogrešnog izvora

Drugi je u dekompresiji točke. Rekonstrukcija afine x iz projekcijskih koordinata zahtijeva jedno množenje inverzijom od Z. Množenje kvadratom inverzije daje vrijednost koja je i dalje valjana projekcijska reprezentacija, ali je pogrešna afina koordinata, pa je simptom ispravan y s pogrešnim x. Kad god je jedna koordinata točna a druga nije, greška je u normalizaciji, ne u aritmetici

Treća je navika uvezena s kraće krivulje. I skalar po potpisu i skalar izazova moraju se reducirati iz potpunog sažetka, koji je za Ed448 114 bajtova, a ne iz njegovih prvih 57. Krivulja od 32 bajta također koristi svoj puni 64-bajtni sažetak, pa je pravilo konzistentno; pogrešna je samo pretpostavka da je "pola sažetka širina skalara"

Četvrti je redoslijed. Prefiks odvajanja domene dolazi prvi, prije prefiksa konteksta i poruke, što nije redoslijed koji sugerira intuitivno čitanje R i A u specifikaciji. Pogreška tu proizvodi potpise koji se provjeravaju u odnosu na vašu vlastitu implementaciju i ništa drugo, što je najvarljiviji mogući neuspjeh

// Dizajn prijenosa u polju: čista propagacija sa semantikom poda, tako
// da rade i pozitivni i negativni limbovi, a oduzimanje ne treba bias.
// Gornji prijenos savija se natrag kroz 2^448 = 2^224 + 1 (mod p),
// što dodiruje limb 0 i limb 8. Ograničeno na četiri kruga; dva
// zapaž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]);          // pod, ne odsijecanje
      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 primjenjivala je bias prije propagacije, i pri velikim ulazima savijala je lažni prijenos pogrešnog reda veličine u niske limbove. Sheme prijenosa temeljene na biasu uporni su izvor ove klase defekata; semantika poda s ograničenom ponavljajućom petljom lakša je za razmišljanje i mjerljivo dovoljno brza

Dva korijenska uzroka u Brainpoolu

Prvi uopće nije kriptografija. Radna reprezentacija ima 33 limba, pa produkt dviju vrijednosti treba 66, a niz produkta deklariran je sa 64. Pisanje preko kraja oštećivalo je susjednu memoriju, što se najprije pokazivalo kao pogrešni rezultati i tek je uz dodatak šireg skeniranja postalo rušenje. Pravilo koje je iz toga izašlo vrijedi primijeniti na svaki numerički međuspremnik fiksne veličine: odredite veličinu po širini produkta u najgorem slučaju, dodajte marginu i više o tome nikad ne razmišljajte. Niz u kôdu koji se isporučuje ima 68 limbova

Drugi je pomiješani oblik potenciranja. Postoje dva ispravna oblika kvadriraj-i-množi i troše eksponent u suprotnim smjerovima: oblik zdesna nalijevo množi pa kvadrira bazu i mora čitati bitove s najmanje značajnog kraja, dok oblik slijeva nadesno kvadrira pa množi i čita s najznačajnijeg kraja. Petlja modularne inverzije imala je tijelo zdesna nalijevo s obilaskom bitova od najznačajnijega. Obje polovice su udžbeničke, kombinacija nije, a rezultat je pogrešan inverz koji i dalje izgleda kao uvjerljiv element polja

// Jacobianovo udvostručavanje i zbrajanje kod kojih odredišni zapis
// može biti ista varijabla kao izvor. Kopija cijelog zapisa na ulazu
// jedina je pouzdana obrana: pisanje limbova R-a onečišćuje kasnija
// čitanja P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // najprije kopiraj, zatim računaj samo iz Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Dvije pouke o procesu koje su koštale više od grešaka

Inkrementalno zakrpljivanje u hodu ne konvergira prema kriptografskoj jedinici. Jedna je skica zakrpljivana više puta sve dok nije nosila 32 duplicirane rutine i oštećenu strukturu, a popravljena je jedino ponovnim pisanjem. Obrazac koji treba usvojiti jest ili napisati jednom iz provjerenog zrcala ili napisati iznova; niz lokalnih ispravaka aritmetike koju još ne razumijete nagomilava se brže nego što je ispravlja

I provjerite vremenski žig izvršne datoteke prije nego povjerujete rezultatu testa. Inkrementalna izgradnja koja kompajlira ali ne ponovno povezuje pokreće prethodnu binarnu datoteku, što je proizvelo cijeli krug lažnih traga o nedostajućim sondama i dupliciranom izlazu. Kod otklanjanja grešaka u kriptografiji, neobjašnjen rezultat treba potaknuti pitanje "je li ovo binarna datoteka koju sam upravo izgradio" prije "je li algoritam pogrešan"

Performanse, opseg i kako pozvati API

Modularna redukcija u jedinici Brainpool jest po-bitno serijsko pomakni-i-oduzmi od najvišeg postavljenog bita produkta, pa množenje košta približno reda veličine širine bita. P-256 provjera valjanosti spada u niske stotine milisekundi, što nije ništa neobično za potpisivanje ili provjeru dokumenata i bilo bi neadekvatno za TLS terminator. Barrettova redukcija očita je nadogradnja i treba širu radnu vrijednost nego što je trenutna reprezentacija nosi, pa je to promjena koju treba napraviti kada radno opterećenje to zatraži, a ne preventivno

uses
  PDFlibEd448, PDFlibBrainpool;

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

  // Brainpool: pozivatelj dostavlja nonce po potpisu, pa politika
  // noncea 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 pozornost na to da Brainpool ulazna točka za potpisivanje prima nonce umjesto da ga generira. To je namjerno: generiranje noncea najkatastrofalnija je pojedinačna stvar koju treba pogriješiti u ECDSA-u, jer ponovljena ili predvidiva vrijednost otkriva privatni ključ, a odluka o tome odakle dolazi slučajnost pripada aplikaciji i njezinu režimu usklađenosti, a ne PDF knjižnici

Ove krivulje stoje uz postkvantni rad opisan u članku o FIPS 204 ML-DSA, te se uključuju u isti cjevovod potpisivanja i provjere valjanosti pokriven u PAdES potpisivanju i provjeri valjanosti. Za testne certifikate na ovim krivuljama, put lokalnog generiranja opisan je u samopotpisanim certifikatima s CryptoAPI. Potpuna matrica algoritama navedena je na stranici proizvoda losLab PDF Developer Library