Ed448 a Brainpool ECDSA v čistom Pascale pre PDF

PDFlibPas podpisuje a overuje pomocou Ed448 a troch kriviek Brainpool ECDSA v čistom Object Pascale. Žiadna externá kryptografická knižnica, žiadny platformový provider, žiadna DLL: PDFlibEd448 implementuje RFC 8032 PureEdDSA na krivke edwards448 a PDFlibBrainpool implementuje RFC 5639 brainpoolP256r1, brainpoolP384r1 a brainpoolP512r1. Obe vznikli rovnakým spôsobom, proti known-answer vektorom vygenerovaným nezávisle skôr, než bol napísaný jediný riadok Pascalu, a obe stoja za spomenutie predovšetkým kvôli chybám

Aritmetika telesa je neobvykle úprimný kód. Buď sa zhoduje s publikovanými vektormi bajt po bajte, alebo nie, takže tu nie je priestor na „takmer funkčné“. To, čo to robí ťažkým, je skutočnosť, že chybná implementácia stále produkuje podpisy, stále overuje vlastné podpisy a stále pôsobí úplne dôveryhodne

Prečo práve tieto krivky a prečo v Pascale

Krivky Brainpool sa objavujú v európskych profiloch kvalifikovaného podpisu, takže knižnica, ktorá pre tento trh podpisuje dokumenty, si ich nemôže dovoliť považovať za exotiku. Ed448 je v sade algoritmov, ktorú do PDF prináša ISO/TS 32002, a jej vnútorný digest je SHAKE256 namiesto SHA-2. Ani jedna rodina nie je k dispozícii v bežne používaných kryptografických knižniciach pre Pascal, takže PDF knižnica, ktorá ich chce, si ich musí napísať sama

Argument nasadenia je ten istý, ktorý platí pre celú kryptografiu tejto knižnice: aplikácia, ktorá dodáva jeden binárny súbor bez kryptografickej závislosti, nemá žiadneho providera na detekciu, žiadnu verziu na zladenie a žiadne správanie, ktoré by sa zmenilo po záplate hostiteľa. Podpisovanie je presne tá oblasť, v ktorej je pohyblivá závislosť najmenej žiaduca

Konštanty pochádzajú z textu špecifikácie, nikdy nie z pamäti

Prvý pokus o základný bod krivky edwards448 bol napísaný spomäťou a bol chybný. Nie je to nijako pozoruhodná chyba, ale je to veľmi drahá chyba, pretože nesprávny základný bod vytvára vnútorne konzistentný systém: vaše generovanie kľúčov, podpisovanie aj overenie sa navzájom zhodujú a nezhodujú so zvyškom sveta

Funkčný postup je vziať každý doménový parameter z textu špecifikácie a potom ich krížovo overiť. Pre edwards448 to znamená prvočíslo, konštantu krivky, rád grupy a obe desatinné súradnice základného bodu z RFC 8032, prevedené do vnútornej reprezentácie limbov a následne skontrolované oproti publikovaným testovacím vektorom z tej istej normy. Pri krivkách Brainpool to znamená parametre z RFC 5639, nezávislú implementáciu napísanú na generovanie vektorov a krížovú kontrolu proti systémovej knižnici v oboch smeroch skôr, než bežal jediný riadok Pascalu

Jedna odvodená skratka si zaslúži varovanie, pretože vyzerá univerzálne, ale nie je: obnovenie základného bodu z pevnej hodnoty y funguje pri krivke 25519 a nefunguje pri edwards448, kde táto hodnota nemá druhú odmocninu. Skript to vyvrátil v priebehu sekúnd, čo je podstatne lacnejšie ako to objavovať v debugeri

Metóda: zrkadlová implementácia na úrovni limbov skôr, než akýkoľvek Pascal

Technika, vďaka ktorej boli obe jednotky zvládnuteľné, je zrkadlová implementácia v jazyku s neobmedzenými celými číslami, budovaná zdola nahor. Najprv samotná aritmetická vrstva: násobenie a odčítanie v telese a propagácia prenosu, namáhané testami proti ich algebraickým invariantom na približne dvesto náhodných prípadoch. Potom úplné generovanie kľúčov vnútri zrkadla, kde bývajú sémantické chyby a kde je ich nájdenie lacné. Až potom prepis do Pascalu

Úžitok je skôr diagnostický než vývojový. Keď je raz zrkadlo overené ako správne, každý nesúhlas medzi zrkadlom a Pascalom je preklep pri prepise a preskúmanie tej istej medzihodnoty v oboch implementáciách ho okamžite lokalizuje. Trieda chýb, ktorá je inak takmer neladovateľná — jediný nesprávny limb hlboko vnútri skalárneho násobenia — sa tak mení na päťminútové porovnanie

Štyri koreňové príčiny v Ed448

Všetky štyri sa našli preskúmavaním medzihodnôt a všetky štyri sú typu, ktorý produkuje výstup vyzerajúci ako platný

Prvá je pasca v notácii. Väčšina publikovaných vzorcov pre unifikované Edwards sčítanie predpokladá konštantu krivky mínus jedna, zatiaľ čo edwards448 má plus jedna. Prenesené nezmenene sa čitateľ súradnice y zapíše ako súčet tam, kde má byť rozdiel. Opravou nie je opraviť znamienko, ale znovu odvodiť produktový tvar bez inverzie z affinného sčítacieho zákona pre správnu krivku, čo vedie na štyri výrazy súradníc a nedáva žiadny priestor na to, aby sa znamienko zdedilo z nesprávneho zdroja

Druhá je v dekompresii bodu. Obnovenie affinnej súradnice x z projektívnych súradníc vyžaduje jedno násobenie inverziou hodnoty Z. Násobenie druhou mocninou inverzie dáva hodnotu, ktorá je stále platnou projektívnou reprezentáciou a zároveň nesprávnou affinnou súradnicou, takže príznakom je správne y s nesprávnym x. Kedykoľvek je jedna súradnica správna a druhá nie, chyba je v normalizácii, nie v aritmetike

Tretia je zvyk dovezený z kratšej krivky. Skalár pre každý podpis aj challenge skalár sa musia redukovať z úplného digestu, ktorý má pri Ed448 114 bajtov, nie z jeho prvých 57. Krivka s 32 bajtami používa svoj celý 64-bajtový digest tiež, takže pravidlo je konzistentné; chybný je len predpoklad, že „polovica digestu je šírka skaláru“

Štvrtá je poradie. Predpona doménovej separácie prichádza ako prvá, ešte pred predponou kontextu a správou, čo nie je poradie, ktoré naznačuje intuitívne čítanie R a A v špecifikácii. Chyba v tomto produkuje podpisy, ktoré sa overia voči vašej vlastnej implementácii a voči ničomu inému, čo je čo najviac zavádzajúce zlyhanie

// Návrh prenosu v telese: čistá propagácia so sémantikou floor, takže
// fungujú kladné aj záporné limby a odčítanie nevyžaduje bias.
// Horný prenos sa vracia cez 2^448 = 2^224 + 1 (mod p), čím sa
// dotýka limb 0 a limb 8. Ohraničené na štyri priebehy; v praxi
// pozorované dva
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, nie orezanie
      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;

Skoršia verzia tejto rutiny aplikovala bias pred propagáciou a pri veľkých vstupoch zložila falošný prenos nesprávnej magnitúdy do nízkych limbov. Schémy prenosu založené na biase sú trvalým zdrojom tejto triedy defektov; sémantika floor s ohraničeným cyklom repeat je ľahšie pochopiteľná a je merateľne dostatočne rýchla

Dve koreňové príčiny v Brainpool

Prvá nie je vôbec kryptografiou. Pracovná reprezentácia má 33 limbov, takže súčin dvoch hodnôt potrebuje 66 a pole súčinu bolo deklarované s 64. Zápis za koniec poškodil susednú pamäť, čo sa najprv prejavilo ako nesprávne výsledky a na pád sa zmenilo až po pridaní širšieho skenu. Pravidlo, ktoré z toho vzišlo, stojí za uplatnenie na každý číselný buffer pevnej veľkosti: dimenzujte ho podľa šírky súčinu v najhoršom prípade, pridajte rezervu a už sa tým viac nezaoberajte. Pole vo finálnom kóde má 68 limbov

Druhá je pomiešaný tvar umocňovania. Existujú dva správne tvary square-and-multiply a exponent spotrebúvajú v opačných smeroch: pravoľavý tvar najprv násobí a potom umocňuje základ a musí čítať bity od najmenej významného konca, zatiaľ čo ľavopravý tvar najprv umocňuje a potom násobí a číta od najvýznamnejšieho konca. Cyklus modulárnej inverzie mal pravoľavé telo s prechodom bitov od najvýznamnejšieho. Obe polovice sú učebnicové, ich kombinácia nie, a výsledkom je nesprávna inverzia, ktorá stále vyzerá ako dôveryhodný prvok telesa

// Jacobiánske zdvojnásobenie a sčítanie, keď cieľový záznam môže byť
// tou istou premennou ako zdroj. Kópia celého záznamu na vstupe je
// jediná spoľahlivá obrana: zápis limbov R znečistí neskoršie čítania P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // najprv kópia, potom počítať už len z Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Dve procesné lekcie, ktoré stáli viac než chyby

Postupné hotfixovanie sa na kryptografickej jednotke nekonverguje. Jeden návrh sa patchoval opakovane, kým nestál 32 duplikovaných rutín a poškodenú štruktúru, a napravený bol iba prepísaním. Vzor, ktorý si osvojiť, je buď napísať to raz z overeného zrkadla, alebo to prepísať; postupnosť lokálnych opráv aritmetiky, ktorej ešte nerozumiete, sa hromadí rýchlejšie, než sa napráva

A skontrolujte časovú pečiatku spustiteľného súboru skôr, než uveríte výsledku testu. Inkrementálny build, ktorý skompiluje, ale neprelinkuje, spúšťa predchádzajúci binárny súbor, čo vyrobilo celé kolo falošných stôp o chýbajúcich sondách a duplikovanom výstupe. Pri ladení kryptografie by nevysvetlený výsledok mal vyvolať otázku „je toto binárka, ktorú som práve postavil“ skôr než „je algoritmus zlý“

Výkon, rozsah a ako to volať

Modulárna redukcia v jednotke Brainpool je bitovo sériové shift-subtract od najvyššieho nastaveného bitu súčinu, takže násobenie stojí približne rádovo toľko, koľko je šírka bitov. Overenie P-256 sa pohybuje v nižších stovkách milisekúnd, čo je pri podpisovaní či overovaní dokumentov úplne v poriadku, no pre TLS terminator by nestačilo. Barrettova redukcia je zjavný upgrade a potrebuje širšiu pracovnú hodnotu, než ktorú súčasná reprezentácia nesie, takže je to zmena na moment, keď si ju záťaž vyžiada, nie preventívne

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, interne SHAKE256, 57-bajtové kľúče
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: volajúci dodáva nonce per podpis, takže politika
  // nonce zostáva v aplikácii
  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;

Všimnite si, že vstupný bod podpisovania Brainpool preberá nonce namiesto toho, aby si ho generoval. Je to zámerné: generovanie nonce je v ECDSA tou najkatastrofickejšou vecou, ktorú možno pokaziť, pretože opakovaná či predvídateľná hodnota prezradí súkromný kľúč, a rozhodnutie, odkiaľ náhodnosť pochádza, patrí aplikácii a jej compliance režimu, nie PDF knižnici

Tieto krivky stoja vedľa post-kvantovej práce popísanej v článku o FIPS 204 ML-DSA a zapájajú sa do tej istej pipeline podpisovania a validácie, ktorú pokrýva podpisovanie a validácia PAdES. Pre testovacie certifikáty na týchto krivkách je cesta lokálneho generovania popísaná v sebepodpísaných certifikátoch s CryptoAPI. Kompletná matica algoritmov je uvedená na produktovej stránke losLab PDF Developer Library