Aritmetika NIST kriviek v čistom Pascale pre podpis PDF

HotPDF vykonáva dohodu kľúčov na eliptických krivkách a overovanie podpisov pre PDF v čistom Object Pascale, bez viazania na OpenSSL a bez platformového kryptografického providera v ceste. Pokrýva päť kriviek: P-256, P-384 a P-521 pre rodiny NIST prvočísel plus X25519 a X448 pre dohodu kľúčov na Montgomery krivke. Dôvod napísať ten kód namiesto linkovania je nasadenie, nie čistota. Aplikácia Delphi či Free Pascal, ktorá dodáva jeden spustiteľný súbor a žiadnu kryptografickú DLL, nemá žiadnu rozkolísanosť verzií na spravovanie, žiadneho providera na platformu na detekciu a nič, čo by menilo správanie, keď zákazník záplataje svoje systémové knižnice

Cenou je, že aritmetiku teraz vlastníte. Modulárne násobenie veľkých celých čísel je neúprosný kód: buď produkuje výsledky identické po bajtoch voči publikovaným testovacím vektorom, alebo produkuje odpad vyzerajúci dôveryhodne a vzdialenosť medzi tými dvomi stavmi môže byť jediné porovnanie. Toto je príbeh toho porovnania, pretože tvar chyby sa zovšeobecňuje na akýkoľvek pascaleský port aritmetiky telesa

Prečo vôbec PDF knižnica potrebuje aritmetiku kriviek?

Dve funkcie to k sebe priťahujú. Prvá je šifrovanie dokumentov verejným kľúčom: handler zoznamu príjemcov ISO 32000 zabaľuje kľúč per dokument pre menované certifikáty a keď príjemca drží EC kľúč, beží zabalenie cez dohodu kľúčov namiesto RSA key transport. Bez ECDH niet spôsobu, ako taký dokument otvoriť. Druhá je validácia podpisov. Overenie ECDSA podpisu nad bajtmi /ByteRange potrebuje násobenie bodov na krivke podpisovateľa a P-384 je bežná vo vládnych a profiloch kvalifikovaného podpisu, kde je P-256 považovaná za podlahu, nie za cieľ. HotPDF vystavuje výsledky tej práce cez cestu overovania ECDSA a CMS a cez zásuvný model signature-provider

CIOS a jediné odčítanie na konci

Montgomery násobenie sa vyhýba deleniu prácou v transformovanej doméne, kde redukcia je posun. Varianta, ktorú HotPDF používa, je Coarsely Integrated Operand Scanning, ktorá prepleta násobenie a redukciu limb po limbe, takže medzivýsledok nikdy nenarastie nad šírku modulu plus jeden limb. Telo cyklu je priamočiare a ľahko testovateľné. Chvost nie: po prepletených priechodoch môže byť akumulátor kdekoľvek v rozsahu až do dvojnásobku modulu, takže algoritmus končí podmieneným odčítaním, ktoré odobrá jednu kópiu prvočísla vtedy a len vtedy, keď je akumulátor väčší alebo rovný

Porovnávanie dvoch viac-limbových čísel znamená kráčať z najvýznamnejšieho limbom nadol a pritom niesť výpožičku. Zjavný spôsob, ako to napísať, je porovnať limb akumulátora s limbom modulu plus prichádzajúcou výpožičkou. Ten výraz je zlý a je zlý spôsobom, ktorý väčšina kriviek skrýva

// Zle: P[I] + Borrow môže pretekať, keď P[I] je $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Správne: porovnávať bez akéhokoľvek pripočítania do limb
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Ako vlastne vyzerá pretekanie výpožičky?

Vyzerá to ako krivka, ktorá funguje všade okrem produkcie. Prvočísla pre P-384 a P-521 obsahujú limb, ktoré sú celé jedničky, takže P[I] sa rovná $FFFFFFFFFFFFFFFF. Pripočítajte k tomu prichádzajúcu výpožičku jedna a 64-bit unsigned sa pretočí na nulu. Porovnanie sa potom pýta, či je limb akumulátora menší než nula, rozhodne, že nie je, a uzavrie, že výpožička nie je potrebná. Jeden limb výsledku je o jedno vedľa

P-256 uniká, pretože žiadny z jej limbov nie je celý jedničkový, takže sčítanie nikdy nepretečie a chybný výraz náhodou súhlasí so správnym. To je najhorší možný výsledok pre testovaciu sadu: najviac testovaná krivka prechádza, menej testované zlyhávajú prerušovane podľa hodnôt operandov a zlyhanie sa vynorí ako výsledok overenia „neplatný podpis“ na dokumentoch, ktoré sú úplne platné. HotPDF niesol výslovnú bránu na P-384 presne z tohto dôvodu, vracal status nedostupný namiesto zlej odpovede, kým nebola aritmetika dokázaná voči referenčným vektorom

Ako sa chyba naozaj našla

Nie čítaním kódu. Produkcívna sekvencia bola mechanická a je znovu použiteľná. Najprv eliminujte konštanty: každý limb p, R a R^2 sa regeneroval nezávisle a porovnával limb po limbe, čo vylúči jediný najbežnejší zdroj chýb kriviek. Potom inštrumentujte aritmetiku namiesto API: dočasná procedúra dump vypísala medzihodnoty Montgomery násobenia R^2, x^3 a y^2 pre známy bod, takže sa dali skontrolovať voči nezávisle vypočítanej pravde

To porovnanie ukázalo rovno na páchateľa. Reťaz x bol správny od začiatku do konca, zatiaľ čo y^2 sa líšil presne v jednom limite presne o jedno. Rozdiel jedného limb o jedno nie je chyba násobenia, chyba propagácie prenosu ani chyba konštanty; je to chyba reťaze výpožičky a jediná reťaz výpožičky v rutine je finálne podmienené odčítanie. Jeden detail to takmer vykoľajil: referenčná konštanta použitá pre dump bola sama napísaná v zlom poradí bajtov pri prvom pokuse, čo vyprodukovalo nesúlad v hodnote y a krátko naznačilo druhý, neexistujúci defekt. Overte endianitu vašej pravdy, skôr než jej uveríte, že obviní váš kód

Susedné pasce v tej istej rutine

Ďalšie tri režimy zlyhania bývajú niekoľko riadkov od toho porovnania a všetky tri boli v živej prevádzke v určitom momente vývoja

// 1. Akumulátor má jeden limb nad šírkou modulu. Porovnávanie len
//    dolných L limbov prehliada prípad, keď sa T rovná presne p plus 2^(64*L),
//    čo sa stáva na významnom podiele náhodných vstupov, pretože 2p
//    presahuje 2^256 pre P-256 a 2^384 pre P-384
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Všeobecné odčítanie viacerých limbov má rovnaké nebezpečenstvo pretečenia:
//    keď Y[I] je $FFFFFFFFFFFFFFFF, Y[I] + Borrow sa pretočí na nulu a
//    výpožička musí prežiť do ďalšieho limb, nie byť vynulovaná
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Tretia nie je kód, je to proveniencia. Prvočíslo pre P-521 bolo spočiatku prepísané so 130 hexadecimálnymi číslicami namiesto 131, o jedno F menej, a Montgomery konštanty boli potom vypočítané z toho zlého prvočísla, takže konštanty boli vnútorne konzistentné a spoločne zlé. Parametre kriviek sa musia odvodzovať, nikdy vypisovať: spočítajte R ako (1 shl (64 * L)) mod p z prvočísla, ktoré skutočne používate, a potom krížovo skontrolujte R * R mod p voči hodnote, ktorú vaša konštanta R^2 tvrdí. Pár konštánt, ktoré sa navzájom zhodujú, nedokáže nič o ani jednej

Stratégia overenia, ktorá škáluje za jednu krivku

Technika, ktorá spravila X25519 a X448 zvládnuteľnými, bolo napísanie zrkadlovej implementácie v jazyku s neobmedzenými celými číslami a prepis pascaleského toku riadenia do nej riadok po riadku. Keď zrkadlo produkuje správnu odpoveď a Pascal nie, defekt je preklep pri prepise a preskúmanie tej istej medzihodnoty v oboch implementáciách ho nájde v sekundách. Všetky tri klasické chyby rebríka RFC 7748 sa takto chytili: konštantnočasová výmena, ktorej druhý riadok znovu použil už vymenenú hodnotu, finálna inverzia, ktorá vrátila z na mocninu mínus jedna namiesto jej vynásobenia do X, a násobenie malou konštantou, ktoré skladalo produkty polslov bitwise or a stratilo prenos

Pre testovací materiál berte vektory ako bajty, nie ako text. Vytiahnutie súkromného kľúča textovým vzorom je spôsob, ako správna implementácia dostane obvinenie z chyby o jeden bajt, ktorá sídlí úplne v kroku extrakcie. Vystrihnite hex z DER kódovania na známych offsetoch a porovnávajte bajtové polia

S opravenou reťazou výpožičky sa všetkých päť kriviek zhoduje s publikovanými referenčnými vektormi bajt po bajte a HotPDF už nebráni žiadnu z nich. Ak integrujete podpisovanie založené na certifikátoch alebo šifrovanie zoznamu príjemcov, praktické ponaučenie je, že voľba krivky je teraz rozhodnutie politiky, nie otázka schopností; profily a pasce poradia bajtov na strane podpisovania pokrýva sprievodca podpisovaním PAdES. Detaily komponenty a podporovaná matica algoritmov sú na produktovej stránke HotPDF Delphi PDF component