Ed448 ir Brainpool ECDSA gryname Pascale PDF failams

PDFlibPas pasirašo ir tikrina naudodamas Ed448 bei tris Brainpool ECDSA kreives gryname Object Pascal. Jokios išorinės kriptografijos bibliotekos, jokio platformos teikėjo, jokios DLL: PDFlibEd448 įgyvendina RFC 8032 PureEdDSA edwards448 kreivei, o PDFlibBrainpool įgyvendina RFC 5639 brainpoolP256r1, brainpoolP384r1 ir brainpoolP512r1. Abi dalys kurtos tuo pačiu būdu — remiantis known-answer vektoriais, nepriklausomai sugeneruotais dar prieš parašant bent eilutę Pascal kodo, ir abi verta aprašyti visų pirma dėl jose rastų klaidų

Lauko aritmetika yra neįprastai sąžiningas kodas. Ji arba baitas po baito sutampa su paskelbtais vektoriais, arba nesutampa, todėl čia nėra vietos „daugiausia veikiančiam“ rezultatui. Sunkiausia tai, kad neteisinga realizacija vis tiek sugeneruoja parašus, vis tiek patvirtina savo pačios parašus ir vis tiek atrodo visiškai tikėtinai

Kodėl būtent šios kreivės ir kodėl Pascal

Brainpool kreivės pasirodo Europos kvalifikuoto parašo profiliuose, todėl biblioteka, pasirašanti dokumentus tai rinkai, negali jų laikyti egzotišku retumu. Ed448 priklauso algoritmų rinkiniui, kurį į PDF atneša ISO/TS 32002, ir jo vidinė maiša yra SHAKE256, o ne SHA-2. Nė viena iš šių dviejų šeimų neprieinama įprastose Pascal kriptografijos bibliotekose, todėl PDF biblioteka, kuriai jų reikia, privalo jas turėti pati

Diegimo argumentas tas pats, kuris taikomas visai šios bibliotekos kriptografijai: programa, išsiunčiama kaip vienas dvejetainis failas be kriptografijos priklausomybių, neturi teikėjo, kurį reikėtų aptikti, neturi versijos, kurią reikėtų sulyginti, ir neturi elgsenos, kuri pasikeistų atnaujinus pagrindinę sistemą. Pasirašymas yra būtent ta sritis, kurioje besislančios priklausomybės norėtumėte mažiausiai

Konstantos imamos iš specifikacijos teksto, o niekada iš galvos

Pirmasis edwards448 bazinio taško užrašas buvo rašytas iš galvos ir pasirodė neteisingas. Tai ne išskirtinė klaida, bet labai brangi, nes neteisingas bazinis taškas sukuria viduje nuoseklią sistemą: rakto generavimas, pasirašymas ir patikrinimas sutaria tarp savęs ir nesutaria su likusiu pasauliu

Darbanti tvarka yra imti kiekvieną srities parametrą iš specifikacijos teksto, o tada kryžmiškai patikrinti. edwards448 kreivei tai reiškia pirminį skaičių, kreivės konstantą, grupės tvarką ir abi bazinio taško dešimtaines koordinatas iš RFC 8032, pavertimą viduline limb atstovavimo forma, o tada tikrinimą pagal to paties dokumento paskelbtus testinius vektorius. Brainpool kreivėms tai reiškia parametrus iš RFC 5639, nepriklausomą realizaciją, parašytą vektoriams generuoti, ir kryžminę patikrą su sistemine biblioteka abiem kryptimis dar prieš paleidžiant bet kokį Pascal kodą

Vienas išvedimo sutrumpinimas nusipelno įspėjimo, nes atrodo universali, bet ja nėra: bazinio taško atkūrimas iš fiksuotos y reikšmės veikia 25519 kreivei ir neveikia edwards448, kur toji reikšmė neturi kvadratinės šaknies. Scenarijus tai paneigė per sekundes, o tai daug pigiau nei atrasti su derintuve

Metodas: veidrodinė realizacija limb lygiu prieš bet kokį Pascal

Technika, padariusi abu modulius valdomus, yra veidrodinė realizacija kalba su neribotais sveikaisiais skaičiais, kuriama iš apačios į viršų. Pirma vien aritmetikos sluoksnis: lauko daugyba, atimtis ir pernešimo sklidimas, išbandytas pagal jų algebrainius invariantus per porą šimtų atsitiktinių atvejų. Tada pilnas rakto generavimas veidrodyje — ten gyvena semantinės klaidos ir ten jas rasti pigiausia. Tik tada Pascal perkėlimas

Atsiperkamumas — diagnostinis, o ne kūrimo. Kai žinoma, kad veidrodis teisingas, bet koks nesutapimas tarp veidrodžio ir Pascal yra perkėlimo klaidelė, ir tos pačios tarpinės reikšmės ištyrinėjimas abiejose realizacijose jos vietą nustato nedelsiant. Tai paverčia klaidų klasę, kuri kitaip būtų beveik nederinama — vieną neteisingą limb giliai skaliarinės daugybos viduje — penkių minučių palyginimu

Keturios Ed448 klaidų priežastys

Visos keturios buvo rastos tirdami tarpines reikšmes, ir visos keturios yra tokio pobūdžio, kad sukuria tinkamai atrodančius rezultatus

Pirmoji — žymėjimo spąstai. Dauguma paskelbtų vieningo Edwards sudėties formulių numato kreivės konstantą „minus vienas“, o edwards448 turi „plius vienas“. Perkėlus formulę nepakeistą, y koordinatės skaitiklis užrašomas kaip suma ten, kur turėtų būti skirtumas. Pataisa — ne klijuoti lopą ant ženklo, bet iš naujo išvesti be inversijos veikiančią sandaugos formą iš afinės sudėties dėsnio teisingai kreivei, kas duoda keturis koordinačių reiškinius ir nepalieka jokios galimybės ženklui paveldėti iš neteisingo šaltinio

Antroji — taško dekompresijoje. Afinės x atkūrimas iš projektinių koordinačių reikalauja vienos daugybos iš Z inversą. Daugyba iš apversto kvadrato duoda reikšmę, kuri vis dar yra teisėta projekcinė atstovavimo forma, bet yra neteisinga afinė koordinatė, todėl simptomas — teisinga y su neteisinga x. Bet kada viena koordinatė teisinga, o kita ne, klaida yra normalizavime, o ne aritmetikoje

Trečioji — įprotis, atvežtas iš trumpesnės kreivės. Ir kiekvieno parašo skaliaras, ir iššūkio skaliaras turi būti sumažinti iš visos maišos, kuri Ed448 atveju yra 114 baitų, o ne iš pirmųjų jos 57. 32 baitų kreivė taip pat naudoja visą savo 64 baitų maišą, todėl taisyklė nuosekli; neteisinga tik prielaida, kad „pusė maišos yra skaliaro plotis“

Ketvirtoji — eiliškumas. Srities atskyrimo priešdėlis eina pirmas, prieš konteksto priešdėlį ir pranešimą, o tai nėra tvarka, kurią numano intuityvus R ir A skaitymas specifikacijoje. Šios klaidos atveju gaunami parašai, kurie patvirtinami tik pagal jūsų pačių realizaciją ir nieką kitą — tai pats apgaulingiausias galimas gedimas

// Lauko pernešimo (carry) projektavimas: grynas floor semantikos
// sklidimas, todėl veikia ir teigiami, ir neigiami limb, o atimčiai
// nereikia jokio poslinkio. Viršutinis pernešimas grąžinamas atgal per
// 2^448 = 2^224 + 1 (mod p), kas paliečia limb 0 ir limb 8. Ribojama
// iki keturių apvalų; praktikoje pastebėti du
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, o ne apkarpymas
      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;

Ankstesnė šios procedūros versija prieš skleidimą pridėdavo poslinkį, o esant dideliems įėjimams į žemutinius limb įversdavo klaidingo dydžio šiukšlinį pernešimą. Poslinkiu paremtos pernešimo schemos yra nuolatinis tokios klasės defektų šaltinis; floor semantika su ribotu kartojimo ciklu lengviau suprantama ir, kaip parodė matavimai, užtektinai sparti

Dvi Brainpool klaidų priežastys

Pirmoji apskritai nėra kriptografija. Darbinė atstovavimo forma yra 33 limb, todėl dviejų reikšmių sandaugai reikia 66, o sandaugos masyvas buvo deklaruotas su 64. Rašymas už galo sugadino gretimą atmintį — tai pirmiausia pasireiškė kaip neteisingi rezultatai ir virto strigtimi tik pridėjus platesnę skenavimo patikrą. Iš to kilusi taisyklė verta taikyti kiekvienam fiksuoto dydžio skaitiniam buferiui: dydį nustatykite pagal blogiausio atvejo sandaugos plotį ir pridėkite atsargos, o paskui daugiau niekada dėl to nesijaudinkite. Išleistinei versijai pateiktame kode masyvas yra 68 limb

Antroji — susimaišiusi kėlimo struktūra. Yra dvi teisingos square-and-multiply formos ir jos vartoja eksponentą priešingomis kryptimis: dešinė-kairė forma pirmiausia daugina, paskui kvadratuoja pagrindą ir privalo skaityti bitus nuo mažiausiai reikšmingo galo, o kairė-dešinė forma pirmiausia kvadratuoja, paskui daugina ir skaito nuo labiausiai reikšmingo galo. Modulinės inversijos ciklas turėjo dešinė-kairė kūną su nuo vyriausio bito pradedančiu ėjimu. Abi pusės yra iš vadovėlio, jų derinys — ne, o rezultatas yra neteisinga inversija, kuri vis tiek atrodo kaip tikėtinas lauko elementas

// Jacobi dvigubinimas ir sudėtis, kai paskirties įrašas gali būti
// tas pats kintamasis kaip ir šaltinis. Viso įrašo kopija įėjime yra
// vienintelė patikima gynyba: rašymas į R limb sugadina vėlesnius P skaitymus
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // pirma kopijuoti, paskui skaičiuoti tik iš Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Dvi proceso pamokos, kainavusios daugiau nei pačios klaidos

Nuolatinis lopymas eigoje nekonverguoja kriptografiniame modulyje. Vienas juodraštis buvo lopinėtas tiek kartų, kad sukaupė 32 dubliuotas procedūras ir sugadintą struktūrą, ir jis buvo ištaisytas tik perrašius iš naujo. Vartotinas modelis — arba parašyti vieną kartą iš patikrinto veidrodžio, arba perrašyti; vietinių pataisų seka aritmetikai, kurios dar nesuprantate, kaupiasi greičiau, nei ją taiso

Ir prieš tikėdami testo rezultatu, pasitikrinkite vykdomojo failo laiko žymą. Pakopinė kompiliacija, kuri sukompiliuoja, bet neperlinkina, paleidžia ankstesnį dvejetainį failą — dėl to atsirado visa eiga klaidingų pėdsakų apie dingusias zondavimo vietas ir dubliuotą išvestį. Derinant kriptografiją, nepaaiškinamas rezultatas turėtų kelti klausimą „ar tai mano ką tik sukurtas dvejetainis failas“, o tik tada „ar algoritmas neteisingas“

Našumas, taikymo sritis ir kaip tai iškviesti

Modulinė redukcija Brainpool modulyje yra bitais skaičiuojamas poslinkio-atimties procesas nuo aukščiausio sandaugos nustatytojo bito, todėl daugyba kainuoja maždaug bitų pločio eilės tvarka. P-256 patikrinimas užima žemąjį šimtą milisekundžių, kas nepastebima pasirašant ar tikrinant dokumentus, bet būtų nepakankama TLS terminatoriaus atveju. Barrett redukcija yra akivaizdus patobulinimas ir reikalauja platesnės darbinės reikšmės, nei neša dabartinė atstovavimo forma, todėl tai pakeitimas, kurį daryti tada, kai to prašo darbo krūvis, o ne iš anksto

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, viduje SHAKE256, 57 baitų raktai
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: iškviečiantysis pateikia kiekvieno parašo nonce, todėl
  // nonce politika lieka pas programą
  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;

Atkreipkite dėmesį, kad Brainpool pasirašymo įėjimo taškas priima nonce, o jo nesugeneruoja pats. Tai sąmoningas sprendimas: nonce generavimas yra vienintelis katastrofiškiausias dalykas, kurį galima padaryti negerai ECDSA atveju, nes pasikartojusi arba nuspėjama reikšmė atskleidžia privatųjį raktą, o sprendimas, iš kur gaunamas atsitiktinumas, priklauso programai ir jos atitikties režimui, o ne PDF bibliotekai

Šios kreivės yra greta pokvantinių darbų, aprašytų FIPS 204 ML-DSA straipsnyje, ir jungiasi į tą patį pasirašymo bei patikros konvejerį, aprašytą PAdES pasirašyme ir patikroje. Testiniams sertifikatams šioms kreivėms vietinio generavimo kelias aprašytas savarankiškai pasirašytuose sertifikatuose su CryptoAPI. Pilna algoritmų matrica išvardyta losLab PDF Developer Library produkto puslapyje