Ed448 és Brainpool ECDSA tiszta Pascalban PDF-hez

A PDFlibPas tiszta Object Pascalban ír és ellenőriz aláírásokat Ed448-mal és a három Brainpool ECDSA-görbével. Nincs külső titkosítási függvénytár, nincs platformszolgáltató, nincs DLL: a PDFlibEd448 az RFC 8032 PureEdDSA-t valósítja meg edwards448-on, a PDFlibBrainpool pedig az RFC 5639 brainpoolP256r1, brainpoolP384r1 és brainpoolP512r1 görbéit. Mindkettőt ugyanúgy építették: a Pascal egyetlen sora megírása előtt egymástól függetlenül előállított ismert válaszvektorokkal szemben, és mindkettőről főleg a hibák miatt érdemes írni

A testi aritmetika szokatlanul becsületes kód. Vagy bájtonként egyezik a publikált vektorokkal, vagy nem, így a „nagyrészt működő” állapotnak nincs helye. A nehézséget az jelenti, hogy egy hibás implementáció is előáll aláírásokat, ellenőrzi is a saját aláírásait, és teljesen hihetőnek tűnik

Miért éppen ezek a görbék, és miért Pascalban

A Brainpool-görbék az európai minősített aláírási profilokban szerepelnek, tehát egy olyan könyvtár, amely erre a piacra ír alá dokumentumokat, nem tekintheti egzotikusnak őket. Az Ed448 abban az algoritumuskészletben van, amelyet az ISO/TS 32002 a PDF-be hoz, ahol belső kivonatolása SHAKE256, nem pedig SHA-2. A két görbecsalád egyike sem érhető el a közhasználatú Pascal titkosítási függvénytárakban, tehát amelyik PDF-könyvtár igényli őket, annak birtokolnia kell őket

A telepítési érv ugyanaz, amely a könyvtár teljes titkosítására teljesül: az az alkalmazás, amely egyetlen bináris fájlként kerül kiadásra titkosítási függőség nélkül, nem tartalmaz észlelendő szolgáltatót, nincs illesztendő verzió, és a viselkedése nem változik meg, amikor a gazdagépet foltozzák. Az aláírás éppen az a terület, ahol legkevésbé kívánatos egy mozgó függőség

A konstansok a specifikáció szövegéből jönnek, soha nem emlékezetből

Az edwards448 bázispontjának első megkísérlése emlékezetből íródott, és hibás lett. Ez nem különösebben emlékezetes hiba, ám nagyon drága, mert egy rossz bázispont önkonzisztens rendszert hoz létre: a kulcsgenerálás, az aláírás és az ellenőrzés mind egyetértenek egymással, és mind eltérnek a világ többi részétől

A működő eljárás az, hogy minden tartományparamétert a specifikáció szövegéből veszünk, majd keresztben ellenőrzünk. Az edwards448 esetében ez azt jelenti, hogy a prím, a görbekonstans, a csoport rendje és a bázispont mindkét decimális koordinátája az RFC 8032-ből származik, belső limb-ábrázolássá alakítva, majd ugyanabból a dokumentumból származó publikált tesztvektorokkal ellenőrizve. A Brainpool-görbéknél ez az RFC 5639 paramétereit, egy kifejezetten vektorok előállítására írt független implementációt és egy kétirányú keresztellenőrzést jelent egy rendszerkönyvtárral szemben, még mielőtt egyetlen Pascal sor is lefutott volna

Egy levezetési rövidítés figyelmeztetést érdemel, mert univerzálisnak tűnik, de nem az: a bázispont visszanyerése egy rögzített y értékből a 25519 görbén működik, edwards448-on viszont nem, ahol annak az értéknek nincs négyzetgyöke. Egy szkript másodpercek alatt megcáfolta, ami jóval olcsóbb, mint felfedezni egy hibakeresőn keresztül

A módszer: limb szintű tükörimplementáció még bármilyen Pascal előtt

A technika, amely mindkét egységet kezelhetővé tette, egy tükörimplementáció egy korlátlan egész számokkal dolgozó nyelven, alulról felfelé építve. Először csak az aritmetikai réteg: testi szorzás, kivonás és az átvitel terjedése, stressztesztelve az algebrai invariánsaikkal szemben néhány száz véletlen esetben. Aztán a teljes kulcsgenerálás a tükörön belül, mert a szemantikai hibák ott laknak, és ott olcsó megtalálni őket. Csak ezután jön a Pascal átírás

A haszna diagnosztikai, nem fejlesztési. Ha egyszer ismert, hogy a tükör helyes, a tükör és a Pascal közötti bármilyen eltérés átírási baklövés, és ugyanazon köztes érték megvizsgálása mindkét implementációban azonnal megtalálja. Ez átalakítja azt a hibaosztályt, amely egyébként szinte hibakereshetetlen — egyetlen rossz limb egy skalárszorzás mélyén — egy ötperces összehasonlítássá

Négy gyökérok az Ed448-ban

Mind a négy köztes értékek vizsgálatával került elő, és mind a négy olyan hiba, amely érvényesnek látszó kimenetet állít elő

Az első egy jelölési csapda. A legtöbb publikált képlet az egységes Edwards-összeadásra mínusz egyes görbekonstansokat feltételez, edwards448 pedig plusz eggyel rendelkezik. Változatlanul átemelve az y koordináta számlálója összeget kap, ahol különbség kellene. A javítás nem az előjel foltozása, hanem az inverziómentes szorzatalak újralevezése a helyes görbe affin összeadási törvényéből, amely előállítja a négy koordinátakifejezést, és nem hagy helyet annak, hogy egy előjel a rossz forrásból öröklődjön

A második a pontdekompreszióban lakik. Az affin x visszanyerése projektív koordinátákból egyetlen szorzást igényel Z inverzével. Az inverz négyzetével való szorzás egy olyan értéket ad, amely még érvényes projektív ábrázolás, viszont a rossz affin koordináta, így a tünet egy helyes y rossz x-szel. Akárhányszor az egyik koordináta helyes, a másik nem, a hiba a normalizációban van, nem az aritmetikában

A harmadik egy a rövidebb görbéről importált szokás. Az aláírásenkénti skalárt és a kihívásskalárt is a teljes kivonatból kell redukálni, amely Ed448 esetén 114 bájt, nem az első 57 bájtból. A 32 bájtos görbe is a teljes 64 bájtos kivonatát használja, tehát a szabály következetes; csak az a feltételezés hibás, hogy „a kivonat fele a skalár szélessége”

A negyedik a sorrend. A tartományszétválasztás előtagja első helyen áll, a kontextuselőtag és az üzenet előtt, ami nem az a sorrend, amelyet a specifikációban a R és A intuitív olvasata sugall. Ha ezt elrontja, olyan aláírások születnek, amelyek csak a saját implementációja ellenében ellenőrizhetők, és semmi más ellenében, ami a legfélrevezetőbb lehetséges hibamód

// Testi átvitel terve: tisztán padlószemantikájú terjedés, így a pozitív és a negatív limb egyaránt működik, és a
// kivonásnak nincs szüksége torzításra. A felső átvitel 2^448 = 2^224 + 1
// (mod p) mentén hajlik vissza, amely a 0. és a 8. limbet érinti.
// Négy körre korlátozva; a gyakorlatban kettő fordult elő
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]);          // padló, nem csonkolás
      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;

Az eljárás egy korábbi változata torzítást alkalmazott a terjesztés előtt, és nagy bemeneteknél hamis átvitelt hajtogatott rossz nagyságrenddel az alsó limbekbe. A torzításon alapuló átviteli sémák e hibaosztály makacs forrásai; a korlátos ismétlő ciklussal működő padlószemantika könnyebben áttekinthető, és mérhetően elég gyors

Két gyökérok a Brainpoolban

Az első egyáltalán nem titkosítás. A működő ábrázolás 33 limb, tehát két érték szorzatához 66 kell, a szorzattömböt viszont 64-gyel deklarálták. A vége túlra írás szomszédos memóriát rongált, amely először rossz eredményként mutatkozott meg, és csak azután lett összeomlás, amikor egy szélesebb beolvasás került bele. A belőle született szabály minden rögzített méretű numerikus pufferre érdemes alkalmazni: méretezze a legrosszabb esetbeli szorzatszélességből, adjon hozzá tartalékot, majd gondolkodás nélkül felejtse el. A kiszállított kódban a tömb 68 limb

A második egy összekevert hatványozási forma. Két helyes négyzetre-emelés és szorzás forma létezik, és ezek ellentétes irányban fogyasztják a kitevőt: a jobbról balra forma szoroz, majd négyzetre emeli az alapot, és a legkevésbé szignifikáns végről kell olvasnia a biteket, míg a balról jobbra forma négyzetre emel, majd szoroz, és a legszignifikánsabb végről olvas. A moduláris inverzió ciklusa jobbról balra testet kapott, legszignifikánsabb-bit-előre bitjárással. Mindkét fele tankönyvi, a kombináció nem az, és az eredmény egy rossz inverz, amely még mindig hihető testelemnek tűnik

// Jacobi duplázás és összeadás arra az esetre, amikor a célrekord
// ugyanaz a változó lehet, mint egy forrás. Teljes rekordmásolat a
// belépéskor az egyetlen megbízható védelem: R limbjeinek írása
// beszennyezi P későbbi olvasatait
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // előbb másolás, majd számítás kizárólag Pinből
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Két folyamatbeli tanulság, amelyek többe kerültek, mint a hibák

Az inkrementális gyorsjavítás nem konvergál egy titkosítási egységen. Az egyik vázlatot ismételten foltozták, míg 32 duplikált rutint és sérült struktúrát cipelt, és csak átírással lett rendbe hozva. A követendő minta az, hogy vagy egyszer megírja egy validált tükörből, vagy átírja; az olyan aritmetikára adott helyi javítások sorozata, amelyet még nem ért, gyorsabban halmozódik, mint amilyen gyorsan helyesbít

És nézze meg a végrehajtható fájl időbélyegét, mielőtt elhisz egy teszteredményt. Az inkrementális build, amely fordul, de nem kapcsol újra, az előző bináris fájlt futtatja, és ez egy teljes környi vakvágányt gyártott az eltűnt szondákról és a duplikált kimenetről. Titkosítás hibakeresésekor egy magyarázat nélküli eredmény először azt a kérdést váltja ki, hogy „ez-e az imént lefordított bináris fájl”, mielőtt az, hogy „rossz-e az algoritmus”

Teljesítmény, hatókör és így hívható

A moduláris redukció a Brainpool egységben bitsoros léptetés-kivonás a szorzat legmagasabb beállított bitjétől, tehát egy szorzás nagyjából a bitszélesség nagyságrendjébe kerül. Egy P-256 ellenőrzés alacsony százhányados ezredmásodpercekbe esik, ami dokumentumok aláírásához és ellenőrzéséhez nem számít kiemelkedőnek, egy TLS-lezáróhoz viszont nem lenne elegendő. A Barrett-redukció a kézenfekvő fejlesztés, és szélesebb munkaértéket igényel, mint amennyit a jelenlegi ábrázolás hordoz, tehát olyan változtatás, amelyet akkor érdemes megtenni, amikor a terhelés kéri, és nem előre

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, belül SHAKE256, 57 bájtos kulcsok
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: a hívó adja az aláírásenkénti nonce-t, így a
  // nonce-politika az alkalmazásnál marad
  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;

Vegye észre, hogy a Brainpool aláírási belépési pontja a nonce-t veszi át ahelyett, hogy generálná. Ez szándékos: a nonce generálása a legkatasztrofálisabb dolog, amit ECDSA-ban el lehet rontani, mert egy ismételt vagy kitalálható érték felfedi a privát kulcsot, és arról a döntés, hogy honnan jön a véletlenszerűség, az alkalmazás és a megfelelőségi rendszere dolga, nem egy PDF-könyvtáré

Ezek a görbék az utókvantum munka mellett helyezkednek el, amelyről az FIPS 204 ML-DSA cikk ír, és ugyanabba az aláírási és érvényesítési vezetékbe csatlakoznak, amelyet a PAdES aláírás és érvényesítés tárgyal. Teszttanúsítványokhoz ezeken a görbéken a helyi generálási útvonalat a önaláírt tanúsítványok CryptoAPI-val cikk írja le. A teljes algoritmusmátrix a losLab PDF Developer Library terméklapon található