Ed448 a Brainpool ECDSA v čistém Pascalu pro PDF

PDFlibPas podepisuje a ověřuje pomocí Ed448 a tří křivek Brainpool ECDSA v čistém Object Pascalu. Žádná externí kryptografická knihovna, žádný platformový provider, žádná DLL: PDFlibEd448 implementuje PureEdDSA z RFC 8032 na křivce edwards448 a PDFlibBrainpool implementuje brainpoolP256r1, brainpoolP384r1 a brainpoolP512r1 z RFC 5639. Obě jednotky vznikly stejným způsobem, proti známým testovacím vektorům generovaným nezávisle dříve, než byl napsán jediný řádek Pascalu, a za zmínku stojí především kvůli chybám

Aritmetika těles je neobvykle upřímný kód. Buď odpovídá publikovaným vektorům bajt za bajtem, nebo neodpovídá, takže prostor pro „téměř funkční“ zde není. Ztěžuje to okolnost, že chybná implementace stále generuje podpisy, stále ověřuje vlastní podpisy a stále vypadá zcela důvěryhodně

Proč právě tyto křivky a proč v Pascalu

Křivky Brainpool se objevují v evropských profilech kvalifikovaných podpisů, takže knihovna, která pro tento trh podepisuje dokumenty, je nemůže považovat za exotiku. Ed448 patří do sady algoritmů, kterou ISO/TS 32002 přináší do PDF, přičemž jeho interním hašem je SHAKE256 namísto SHA-2. Ani jedna z těchto rodin není k dispozici v běžně používaných kryptografických knihovnách pro Pascal, takže si je PDF knihovna, která je chce využívat, musí implementovat sama

Argument pro nasazení je stejný jako u veškeré kryptografie této knihovny: aplikace, která dodává jedinou binárku bez kryptografické závislosti, nemá žádný provider k detekci, žádnou verzi ke sladění a žádné chování, které by se změnilo při záplatování hostitelského systému. Podepisování je přesně tou oblastí, kde se pohyblivá závislost hodí nejméně ze všeho

Konstanty pocházejí z textu specifikace, nikdy z paměti

První pokus o základní bod edwards448 byl zapsán z paměti a byl chybný. Nejde o nijak pozoruhodnou chybu, zato je velmi drahá, protože chybný základní bod vytváří soběstačně konzistentní systém: vaše generování klíčů, podepisování i ověřování se navzájem shodují a s okolním světem nesouhlasí

Funkční postup spočívá v tom, že každý doménový parametr převezmete z textu specifikace a poté jej křížově ověříte. U edwards448 to znamená prvočíslo, konstantu křivky, řád grupy a obě desetinné souřadnice základního bodu z RFC 8032, převedené do interní reprezentace limbů, a následnou kontrolu proti publikovaným testovacím vektorům z téhož dokumentu. U křivek Brainpool jde o parametry z RFC 5639, nezávisle napsanou implementaci určenou ke generování vektorů a obousměrné křížové ověření proti systémové knihovně, než se vůbec spustil jakýkoli Pascal

Jedna zkratka při odvozování si zaslouží varování, protože působí univerzálně, ale není: obnovení základního bodu z pevné hodnoty y funguje u křivky 25519, zatímco u edwards448 ne, protože daná hodnota nemá druhou odmocninu. Skript to vyvrátil během několika sekund, což je mnohem levnější než odhalování v debuggeru

Metoda: zrcadlová implementace na úrovni limbů před jakýmkoli Pascalem

Technikou, díky níž byly obě jednotky zvládnutelné, je zrcadlová implementace v jazyce s neomezenými celými čísly, stavěná zdola nahoru. Nejprve samotná aritmetická vrstva: násobení a odčítání v tělese a šíření přenosů, zatížené testy proti algebraickým invariantům na několika stovkách náhodných případů. Potom plné generování klíčů uvnitř zrcadla, protože právě tam sídlí sémantické chyby a právě tam je jejich odhalení levné. Teprve potom přepis do Pascalu

Přínos je spíše diagnostický než vývojový. Jakmile je zrcadlo známo jako správné, každá neshoda mezi zrcadlem a Pascalem je přepisovým překlepem a prozkoumání téhož mezivýsledku v obou implementacích jej okamžitě lokalizuje. Tím se třída chyb, která je jinak téměř neladitelná — jediný chybný limb hluboko uvnitř skalárního násobení — mění na pětiminutové porovnání

Čtyři kořenové příčiny v Ed448

Všechny čtyři byly odhaleny sondováním mezivýsledků a všechny čtyři jsou typem chyby, která produkuje výstup vypadající jako platný

První je past v notaci. Většina publikovaných vzorců pro unifikované sčítání na Edwardsových křivkách předpokládá konstantu křivky minus jedna, zatímco edwards448 má plus jedna. Při přenesení beze změny se čitatel souřadnice y zapíše jako součet tam, kde má být rozdíl. Oprava nespočívá v úpravě znaménka, ale v opětovném odvození tvaru součinu bez inverze z afinního sčítacího zákona pro správnou křivku, což vytvoří všechny čtyři souřadnicové výrazy a neponechá prostor, aby se znaménko zdědilo ze špatného zdroje

Druhá se týká dekomprese bodu. Obnovení afinní souřadnice x z projektivních souřadnic vyžaduje jedno násobení inverzí hodnoty Z. Násobení čtvercem inverze dá hodnotu, která je stále platnou projektivní reprezentací, ale jde o špatnou afinní souřadnici, takže příznakem je správné y se špatným x. Kdykoli je jedna souřadnice správná a druhá ne, chyba je v normalizaci, nikoli v aritmetice

Třetí je návyk přenesený z kratší křivky. Jak skalár jednotlivého podpisu, tak challenge skalár musí být redukovány z kompletního hashe, který má u Ed448 114 bajtů, a nikoli z jeho prvních 57. Dvaatřicetibajtová křivka používá plný šedesátibajtový hash taktéž, takže pravidlo je konzistentní; chybný je pouze předpoklad, že „polovina hashe je šířka skaláru“

Čtvrtá je pořadí. Prefix oddělení domén přichází jako první, před prefixem kontextu a zprávou, což není pořadí, které naznačuje intuitivní čtení R a A ve specifikaci. Chyba zde vytváří podpisy, které ověří vaše vlastní implementace a nic jiného, a to je možné nejvíce klamné selhání

// Návrh přenosů v tělese: čisté šíření se sémantikou floor, takže
// fungují kladné i záporné limby a odčítání nepotřebuje bias.
// Nejvyšší přenos se vrací zpět přes 2^448 = 2^224 + 1 (mod p), což
// zasahuje limb 0 a limb 8. Omezeno na čtyři průchody; v praxi byly
// pozorovány 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, nikoli oříznutí
      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;

Starší verze této rutiny aplikovala bias před šířením a při velkých vstupech zapracovala do spodních limbů falešný přenos špatné velikosti. Schémata přenosů založená na biasu jsou vytrvalým zdrojem této třídy defektů; sémantika floor s ohraničenou opakovanou smyčkou se snáze uvažuje a je měřitelně dostatečně rychlá

Dvě kořenové příčiny v Brainpool

První není vůbec kryptografií. Funkční reprezentace má 33 limbů, takže součin dvou hodnot potřebuje 66 a pole součinu bylo deklarováno s 64. Zápis za konec pole poškodil přilehlou paměť, což se nejprve projevovalo jako chybné výsledky a teprve po přidání širšího skenu se stalo pádem aplikace. Pravidlo, které z toho vzešlo, stojí za uplatnění u každého číselného bufferu pevné velikosti: nastavte velikost podle nejhorší možné šířky součinu a přidejte rezervu, a pak na to už nikdy nemyslete. Pole v dodávaném kódu má 68 limbů

Druhou je pomíchaný tvar umocňování. Existují dva správné tvary square-and-multiply a exponent zpracovávají v opačných směrech: forma zprava doleva násobí a pak umocňuje základ a musí číst bity od nejméně významného konce, zatímco forma zleva doprava umocňuje a pak násobí a čte od nejvýznamnějšího konce. Smyčka modulární inverze měla tělo typu zprava doleva s průchodem bity od nejvýznamnějšího. Obě poloviny jsou učebnicové, kombinace nikoli, a výsledkem je chybná inverze, která přesto vypadá jako věrohodný prvek tělesa

// Jakobiánské zdvojnásobení a sčítání, kde cílový záznam může být
// tatáž proměnná jako zdroj. Zkopírování celého záznamu na vstupu je
// jediná spolehlivá obrana: zápis do limbů R znečistí pozdější čtení P
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // nejprve kopie, poté výpočet pouze z Pin
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Dvě lekce procesu, které stály víc než samotné chyby

Inkrementální hotfixování nekonverguje u kryptografické jednotky. Jeden koncept byl opakovaně záplatován, dokud nenesl 32 duplikovaných rutin a poškozenou strukturu, a napraven byl pouze přepsáním. Vzor, který je třeba přijmout, zní: buď jednou napište z validovaného zrcadla, nebo kód přepište; řada lokálních oprav aritmetiky, které ještě nechápete, se hromadí rychleji, než opravuje

A ověřte časové razítko spustitelného souboru, než uvěříte výsledku testu. Inkrementální sestavení, které zkompiluje, ale neprovede relink, spouští předchozí binárku, což vyrobilo celé kolo falešných stop o chybějících sondách a duplikovaném výstupu. Při ladění kryptografie by nevysvětlitelný výsledek měl vyvolat otázku „je to binárka, kterou jsem právě sestavil“ dříve než „je algoritmus špatný“

Výkon, rozsah a způsob volání

Modulární redukce v jednotce Brainpool je bitově sériové odečítání s posuvem od nejvyššího nastaveného bitu součinu, takže násobení stojí řádově zhruba šířku bitu. Ověření P-256 se pohybuje v nižších stovkách milisekund, což je u podepisování a ověřování dokumentů běžně akceptovatelné, kdežto pro TLS terminátor by to nestačilo. Barrettova redukce je zjevný upgrade a vyžaduje širší pracovní hodnotu, než jakou aktuální reprezentace nese, takže jde o změnu, kterou provést, až si ji vyžádá pracovní zátěž, nikoli preventivně

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, interně SHAKE256, 57bajtové klíče
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: nonce pro jednotlivý podpis dodává volající, takže
  // politika nonce zůstává v aplikaci
  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šimněte si, že vstupní bod pro podepisování Brainpool přebírá nonce, místo aby jej generoval. Je to záměrné: generování nonce je v ECDSA tou nejvíce katastrofickou věcí, kterou lze pokazit, protože opakovaná či předvídatelná hodnota prozradí soukromý klíč, a rozhodnutí o tom, odkud náhodnost pochází, patří aplikaci a jejímu režimu shody s předpisy, nikoli PDF knihovně

Tyto křivky stojí vedle postkvantové práce popsané v článku o FIPS 204 ML-DSA a zapojují se do téhož podpisového a validačního potrubí, které pokrývá podepisování a ověřování PAdES. Postup místního generování testovacích certifikátů na těchto křivkách popisuje článek o vlastnoručně podepsaných certifikátech s CryptoAPI. Kompletní matici algoritmů uvádí stránka produktu losLab PDF Developer Library