Ed448 in Brainpool ECDSA v čistem Pascalu za PDF

PDFlibPas podpisuje in preverja z Ed448 in s tremi krivuljami Brainpool ECDSA v čistem Object Pascalu. Brez zunanje kriptografske knjižnice, brez ponudnika platforme, brez DLL: PDFlibEd448 implementira RFC 8032 PureEdDSA na edwards448, PDFlibBrainpool pa implementira RFC 5639 brainpoolP256r1, brainpoolP384r1 in brainpoolP512r1. Oba sta bila zgrajena na enak način, proti vektorjem znanih odgovorov, generiranim neodvisno, še preden je bil napisan kateri koli Pascal, in vredna pisanja sta predvsem zaradi hroščev

Aritmetika telesa (field arithmetic) je nenavadno iskrena koda. Ali se ujema z objavljenimi vektorji bajt za bajtom ali pa ne, zato ni prostora za »večinoma delujoče«. Težavna postane, ker napačna implementacija še vedno proizvaja podpise, še vedno preverja svoje podpise in še vedno izgleda popolnoma verodostojno

Zakaj te krivulje in zakaj v Pascalu

Krivulje Brainpool se pojavljajo v evropskih profih kvalificiranih podpisov, zato jih knjižnica, ki podpisuje dokumente za ta trg, ne more obravnavati kot eksotične. Ed448 je v naboru algoritmov, ki ga ISO/TS 32002 prinaša v PDF, kjer je njegova notranja prebava (digest) SHAKE256 in ne SHA-2. Nobena od teh družin ni na voljo v splošno uporabljenih kriptografskih knjižnicah za Pascal, zato si jih mora PDF knjižnica, ki jih želi, lastiti sama

Argument za namestitev je isti, ki velja za vso kriptografijo te knjižnice: aplikacija, ki pošilja eno binarno datoteko brez kriptografske odvisnosti, nima ponudnika za odkrivanje, ne različice za usklajevanje in ne vedenja, ki se spremeni, ko je gostitelj popravljen. Podpisovanje je ravno tisto področje, kjer najmanj želite premikajočo se odvisnost

Konstante prihajajo iz besedila specifikacije, nikoli iz spomina

Prvi poskus osnovne točke edwards448 je bil napisan iz spomina in je bil napačen. To ni izjemna napaka in je zelo draga, ker napačna osnovna točka proizvede samoskladni sistem: vaša generacija ključev, podpisovanje in preverjanje se med sabo vsi ujemajo in neujemajo s preostalim svetom

Delovni postopek je, da vsak domen parameter (domain parameter) vzamete iz besedila specifikacije in ga nato navzkrižno preverite. Za edwards448 to pomeni praštevilo, konstanto krivulje, red grupe in obe decimalni koordinati osnovne točke iz RFC 8032, pretvorjene v notranjo predstavitev okončin (limbs), in nato preverjene proti objavljenim testnim vektorjem iz istega dokumenta. Za krivulje Brainpool to pomeni parametre iz RFC 5639, neodvisno implementacijo, napisano za generiranje vektorjev, in navzkrižno preverjanje proti sistemski knjižnici v obeh smereh, preden je tekel kateri koli Pascal

Ena bližnjica pri izpeljavi si zasluži opozorilo, ker izgleda splošna in ni: rekonstrukcija osnovne točke iz fiksne vrednosti y deluje za krivuljo 25519 in ne deluje za edwards448, kjer ta vrednost nima kvadratnega korena. Skripta jo je ovrgla v sekundah, kar je veliko ceneje, kot da bi jo odkrili skozi razhroščevalnik

Metoda: zrcalna implementacija na ravni okončin pred vsakim Pascalom

Tehnika, ki je naredila obe enoti obvladujoči, je zrcalna implementacija v jeziku z neomejenimi celimi števili, zgrajena od spodaj navzgor. Najprej sama aritmetična plast: množenje telesa, odštevanje in širjenje prenosa (carry propagation), stresno testirana proti njihovim algebraičnim invariantam na nekaj sto naključnih primerih. Nato celotna generacija ključev znotraj zrcala, kjer živijo semantični hrošči in kjer je njihovo odkritje poceni. Šele nato Pascalov prepis

Korist je diagnostična in ne razvojna. Ko je znano, da je zrcalo pravilno, je vsako neskladje med zrcalom in Pascalom spodrsljaj pri prepisu, in sondiranje iste vmesne vrednosti v obeh implementacijah ga takoj locira. To pretvori razred hroščev, ki je sicer skoraj nerazhroščljiv, eno samo napačno okončino globoko znotraj skalarnega množenja, v petminutno primerjavo

Štirje korenski vzroki v Ed448

Vsi štirje so bili odkriti s sondiranjem vmesnih vrednosti in vsi štirje so tiste vrste, ki proizvaja izhod, ki izgleda veljavno

Prvi je past notacije. Večina objavljenih formul za enotno Edwardsovo seštevanje predpostavlja konstanto krivulje minus ena, edwards448 pa ima plus ena. Prenešeno nespremenjeno, števec koordinate y je zapisan kot vsota, kjer bi morala biti razlika. Popravek ni zakrpati predznak, ampak znova izpeljati obliko produkta brez inverzije iz afinega zakona seštevanja za pravo krivuljo, kar proizvede štiri izraze koordinat in ne pusti prostora, da bi bil predznak podedovan iz napačnega vira

Drugi je pri dekompresiji točke. Rekonstrukcija afinega x iz projektivnih koordinat zahteva eno množenje z inverzom Z. Množenje s kvadratom inverza da vrednost, ki je še vedno veljavna projektivna predstavitev in je napačna afina koordinata, zato je simptom pravilen y z napačnim x. Vsakič, ko je ena koordinata pravilna in druga ne, je hrošč v normalizaciji, ne v aritmetiki

Tretji je navada, uvožena iz krajše krivulje. Tako skalar za vsak podpis kot izzivski skalar morata biti reducirana iz popolne prebave, ki je za Ed448 114 bajtov, in ne iz njenih prvih 57. Krivulja 32 bajtov prav tako uporablja svojo celotno 64-bajtno prebavo, zato je pravilo skladno; napačna je samo predpostavka, da je »polovica prebave širina skalara«

Četrti je vrstni red. Predpona ločevanja domen pride prva, pred predpono konteksta in sporočilom, kar ni vrstni red, ki ga nakazuje intuitivno branje R in A v specifikaciji. Napačno to proizvede podpise, ki se preverijo proti vaši lastni implementaciji in ničemer drugemu, kar je najbolj zavajajoča mogoča napaka

// Oblikovanje prenosa telesa: čisto širjenje s semantiko poda (floor), tako
// da delujeta tako pozitivni kot negativni okončini in odštevanje ne
// potrebuje pristranskosti. Zgornji prenos se zvije nazaj skozi
// 2^448 = 2^224 + 1 (mod p), kar se dotakne okončine 0 in okončine 8.
// Omejeno na štiri kroge; dva opažena v 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 odrezovanje
      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;

Zgodnejša različica te rutine je uporabila pristranskost pred širjenjem, in pri velikih vhodih je zvila lažni prenos napačne magnitude v nizke okončine. Sheme prenosa na osnovi pristranskosti so vztrajen vir te vrste napak; semantika poda z omejeno zanko ponavljanja je lažja za razumevanje in merljivo dovolj hitra

Dva korenska vzroka v Brainpoolu

Prvi sploh ni kriptografija. Delujoča predstavitev je 33 okončin, zato produkt dveh vrednosti potrebuje 66, polje produktov pa je bilo deklarirano s 64. Pisanje čez konec je pokvarilo sosednji pomnilnik, kar se je najprej pokazalo kot napačni rezultati in je šele z dodanim širšim pregledom postalo sesutje. Pravilo, ki je iz tega nastalo, je vredno uporabiti na vsakem numeričnem predpomnilniku fiksne velikosti: določite velikost iz širine produkta najslabšega primera, dodajte rezervo in o tem nikoli več ne razmišljajte. Polje v izdani kodi je 68 okončin

Drugi je zmešana oblika potenciranja. Obstajata dve pravilni obliki kvadriraj-in-pomnoži (square-and-multiply) in v si eksponent porabljata v nasprotnih smereh: oblika z desne na levo najprej pomnoži in nato kvadrira osnovo ter mora brati bite z najmanj pomembnega konca, oblika z leve na desno pa najprej kvadrira in nato pomnoži ter bere z najbolj pomembnega konca. Zanka modularne inverzije je imela telo z desne na levo z bitnim sprehodom od najbolj pomembnega bita. Obe polovici sta učbeniški, kombinacija pa ni, rezultat pa je napačen inverz, ki še vedno izgleda kot verodostojen element telesa

// Jacobianovo podvajanje in seštevanje, kjer je lahko ciljni zapis
// ista spremenljivka kot vir. Kopija celotnega zapisa na vstopu je edini
// zanesljiv obrambni mehanizem: pisanje okončin R onesnaži poznejša
// branja P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // najprej kopiraj, nato računaj samo iz Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Dve lekciji o procesu, ki sta stale več kot hrošči

Inkrementalno vroče krpanje ne konvergira na kriptografsko enoto. En osnutek je bil večkrat zakrpan, dokler ni nosil 32 podvojenih rutin in poškodovano strukturo, popravljena pa je bila samo s prepisovanjem. Vzorec, ki ga je treba sprejeti, je ali napisati enkrat iz preverjenega zrcala ali ga prepisati; zaporedje lokalnih popravkov aritmetike, ki je še ne razumete, se nabira hitreje, kot jo popravlja

In preverite časovni žig na izvedljivi datoteki, preden verjamete testnemu rezultatu. Inkrementalna gradnja, ki prevede a ne ponovno poveže, poganja prejšnjo binarno datoteko, kar je izmislilo celoten krog lažnih sledi o manjkajočih sondah in podvojenem izhodu. Pri razhroščevanju kriptografije naj nerazložen rezultat sproži vprašanje »ali je to binarna datoteka, ki sem jo pravkar zgradil«, preden »ali je algoritem napačen«

Zmogljivost, obseg in kako ga klicati

Modularna redukcija v enoti Brainpool je bitno serijsko premikanje in odštevanje od najvišjega nastavljenega bita produkta, zato množenje stane približno v redu širine bitov. Preverjanje P-256 pristane v nizkih stotinah milisekund, kar je neopazno za podpisovanje ali preverjanje dokumentov in bi bilo neustrezno za TLS terminator. Barrettova redukcija je očitna nadgradnja in potrebuje širšo delovno vrednost, kot jo nosi trenutna predstavitev, zato je to sprememba, ki jo naredite, ko jo zahteva delovna obremenitev, in ne preventivno

uses
  PDFlibEd448, PDFlibBrainpool;

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

  // Brainpool: klicatelj preskrbi nonce za vsak podpis, zato
  // politika nonce ostane pri 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;

Upoštevajte, da vstopna točka podpisovanja Brainpool vzame nonce namesto da ga generira. To je namerno: generacija nonce je najbolj katastrofalna stvar, ki jo lahko v ECDSA pokvarite, ker ponovljena ali napovedljiva vrednost razkrije zasebni ključ, odločitev o tem, od kod prihaja naključnost, pa pripada aplikaciji in njenemu skladnostnemu režimu, ne PDF knjižnici

Te krivulje stojijo ob strani kvantno odpornega dela, opisanega v članku FIPS 204 ML-DSA, in se priklopijo na isti cevovod podpisovanja in validacije, ki ga pokriva PAdES podpisovanje in validacija. Za testna certifikata na teh krivuljah je lokalna pot generacije opisana v samo-podpisanih certifikatih s CryptoAPI. Polna matrika algoritmov je navedena na strani produkta losLab PDF Developer Library