Aritmetika křivek NIST v čistém Pascalu pro podpisy PDF

HotPDF provádí dohodu klíčů eliptických křivek a ověřování podpisů pro PDF v čistém Object Pascalu bez vazby na OpenSSL a bez platformového krypto providera v cestě. Pokrývá pět křivek: P-256, P-384 a P-521 pro prvočíselné rodiny NIST, plus X25519 a X448 pro dohodu klíčů na Montgomeryových křivkách. Důvodem psaní tohoto kódu namísto linkování je nasazení, nikoli čistota. Aplikace Delphi či Free Pascal, která dodává jeden spustitelný soubor a žádnou kryptografickou DLL, nemá žádný rozkol verzí ke správě, žádného providera na platformu k detekci a nic, co by změnilo chování, když zákazník záplatuje své systémové knihovny

Cenou je, že nyní aritmetiku vlastníte. Modulární násobení velkých celých čísel je neúprosný kód: buď produkuje výsledky identické bajt po bajtu proti publikovaným testovacím vektorům, nebo produkuje věrohodně vypadající odpad a vzdálenost mezi těmito dvěma stavy může být jediné srovnání. Toto je příběh toho srovnání, protože tvar chyby se zobecňuje na jakýkoli Pascal port aritmetiky těles

Proč PDF knihovna vůbec potřebuje aritmetiku křivek?

Dvě funkce jej přitahují. První je šifrování dokumentů veřejným klíčem: obsluha recipient list ISO 32000 zabaluje klíč pro daný dokument pro pojmenované certifikáty a když má příjemce EC klíč, běží zabalení přes dohodu klíčů namísto přenosu klíče RSA. Bez ECDH neexistuje způsob, jak takový dokument otevřít. Druhá je validace podpisů. Ověření ECDSA podpisu nad bajty /ByteRange potřebuje násobení bodů na křivce podepisujícího a P-384 je běžná ve vládních a profilech kvalifikovaných podpisů, kde je P-256 považována za spodní hranici, nikoli cíl. HotPDF vystavuje výsledky té práce přes cestu ověřování ECDSA a CMS a přes model zásuvných poskytovatelů podpisů

CIOS a jediné odčítání na konci

Montgomeryovo násobení se vyhýbá dělení prací v transformované doméně, kde redukce je posuv. Varianta, kterou HotPDF používá, je Coarsely Integrated Operand Scanning, která proplétá násobení a redukci limb po limb, takže mezivýsledek nikdy neroste přes šířku modulu plus jeden limb. Tělo smyčky je přímočaré a snadno testovatelné. Ocas nikoli: po propletených průchodech může být akumulátor kdekoli v rozsahu až dvojnásobku modulu, takže algoritmus končí podmíněným odčítáním, které odstraní jednu kopii prvočísla tehdy a jen tehdy, je-li akumulátor větší nebo roven

Srovnání dvou více-limb čísel znamená jít od nejvýznamnějšího limb dolů a nést borrow. Zjevný způsob zápisu je srovnat limb akumulátoru s limblem modulu plus přicházejícím borrowem. Tento výraz je chybný a je chybný způsobem, který většina křivek skrývá

// Špatně: P[I] + Borrow může přetéct, když je P[I] $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Správně: srovnávejte bez jakéhokoli přičítání do limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Jak ve skutečnosti vypadá přetečení borrowu?

Vypadá to jako křivka, která funguje všude kromě produkce. Prvočísla P-384 a P-521 obsahují limb, které jsou úplně jedničkové, takže P[I] se rovná $FFFFFFFFFFFFFFFF. Přičtete-li přicházející borrow jedničky, 64bitové bezznaménkové číslo se přetočí na nulu. Srovnání se pak ptá, zda je limb akumulátoru menší než nula, usoudí, že není, a dojde k závěru, že borrow není potřeba. Jeden limb výsledku je odchýlen o jedničku

P-256 uniká, protože žádný z jejích limbů není plný jedniček, takže sčítání nikdy nepřeteče a chybný výraz se náhodou shoduje se správným. To je nejhorší možný výsledek pro testovací sadu: nejvíce testovaná křivka projde, méně testované selhávají občasně podle hodnot operandů a selhání se projevuje jako výsledek ověření „neplatný podpis“ u dokumentů, které jsou zcela platné. HotPDF z tohoto přesně důvodu nosil explicitní bránu na P-384, vracející stav nedostupnosti namísto špatné odpovědi, dokud aritmetika nebyla prokázána proti referenčním vektorům

Jak byla chyba skutečně lokalizována

Ne čtením kódu. Produktivní sekvence byla mechanická a je znovupoužitelná. Nejprve eliminujte konstanty: každý limb p, R a R^2 byl regenerován nezávisle a srovnáván limb po limb, což vyloučí nejčastější jediný zdroj chyb křivek. Za druhé instrumentujte aritmetiku, nikoli API: dočasná procedura výpisu tiskla mezihodnoty Montgomeryova násobení R^2, x^3 a y^2 pro známý bod, takže je bylo možné zkontrolovat proti nezávisle vypočtené pravdě

Toto srovnání ukázalo rovnou na viníka. Řetězec x byl správný od začátku do konce, zatímco y^2 se lišil přesně v jednom limb přesně o jedničku. Rozdíl jednoho limb o jedničku není chyba násobení, chyba šíření přenosu ani chyba konstanty; je to chyba borrow řetězce a jediný borrow řetězec v rutině je finální podmíněné odčítání. Jeden detail to téměř svedl ze stopy: referenční konstanta použitá pro výpis byla sama zapsána v prvním pokusu ve špatném pořadí bajtů, což vytvořilo neshodu v hodnotě y a krátce naznačilo druhý, neexistující defekt. Ověřte endianness své pravdy, než jí uvěříte, že obviní váš kód

Sousední pasti v téže rutině

Tři další režimy selhání žijí v několika řádcích od toho srovnání a všechny tři byly v určitém okamžiku vývoje živé

// 1. Akumulátor má jeden limb nad šířkou modulu. Srovnání pouze
//    nízkých L limbů přehlédne případ, kdy se T přesně rovná p plus 2^(64*L),
//    což se stává u významného podílu náhodných vstupů, protože 2p
//    přesahuje 2^256 pro P-256 a 2^384 pro P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Obecné více-limb odčítání má stejné riziko přetečení: když je
//    Y[I] $FFFFFFFFFFFFFFFF, Y[I] + Borrow se přetočí na nulu a borrow
//    musí přežít do dalšího limb, nikoli být vynulován
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Třetí není kód, je to provenience. Prvočíslo P-521 bylo zpočátku přepsáno se 130 hexadecimálními číslicemi namísto 131, o jedno F krát, a Montgomeryovy konstanty byly pak vypočteny z toho chybného prvočísla, takže konstanty byly soběstačně konzistentní a společně chybné. Parametry křivek musí být odvozovány, nikdy vypsány: vypočítejte R jako (1 shl (64 * L)) mod p z prvočísla, které skutečně používáte, a poté křížově zkontrolujte R * R mod p proti hodnotě, kterou vaše konstanta R^2 tvrdí. Pár konstant, které se navzájem shodují, nedokazuje nic o žádné z nich

Ověřovací strategie, která škáluje za jednu křivku

Technikou, která učinila X25519 a X448 zvládnutelnými, bylo napsání zrcadlové implementace v jazyce s neomezenými celými čísly a přepis Pascal řídicího toku do ní řádek po řádku. Když zrcadlo produkuje správnou odpověď a Pascal nikoli, defektem je přepisovský překlep a sondování téže mezihodnoty v obou implementacích jej najde během sekund. Všechny tři klasické chyby žebříku RFC 7748 byly takto chyceny: swap s konstantním časem, jehož druhý řádek znovupoužil už prohozenou hodnotu; finální inverze vracející z na mocninu minus jedna namísto vynásobení do X; a násobení malou konstantou skládající poloslovní součiny bitovým or, které ztratilo přenos

Pro testovací materiál berte vektory jako bajty, nikoli jako text. Vytahování soukromého klíče textovým vzorem je způsob, jakým se správná implementace obviní z chyby o jeden bajt, která žije zcela v kroku extrakce. Vykrojte hex z DER kódování na známých ofsetech a porovnávejte bajtová pole

S opraveným borrow řetězcem odpovídají všech pět křivek publikovaným referenčním vektorům bajt za bajtem a HotPDF už žádnou nebrání. Pokud integrujete podepisování založené na certifikátech nebo šifrování recipient list, praktickým ponaučením je, že volba křivky je nyní politické rozhodnutí namísto otázky schopností; profily a pasti pořadí bajtů podepisující strany pokrývá průvodce podepisováním PAdES. Detaily komponenty a matice podporovaných algoritmů jsou na stránce produktu HotPDF Delphi PDF component