Ed448 ja Brainpool ECDSA puhtaalla Pascalilla PDF:lle

PDFlibPas allekirjoittaa ja tarkistaa Ed448:lla ja kolmella Brainpool ECDSA -käyrällä puhtaassa Object Pascalissa. Ei ulkoista salakirjastoa, ei alustatarjoajaa, ei DLL:iä: PDFlibEd448 toteuttaa RFC 8032 PureEdDSA:n edwards448:lla ja PDFlibBrainpool toteuttaa RFC 5639 brainpoolP256r1-, brainpoolP384r1- ja brainpoolP512r1-käyrät. Molemmat rakennettiin samalla tavalla, itsenäisesti tuotettuihin known-answer-testivektoreihin vertaamalla ennen kuin yhtään Pascal-koodia oli kirjoitettu, ja molemmat on syytä esitellä ennen kaikkea virheidensä vuoksi

Kunta-aritmetiikka on epätavallisen rehellistä koodia. Se joko täsmää julkaistuihin vektoreihin tavu tavulta tai ei täsmää, joten tilaa ei jää ”enimmäkseen toimivalle”. Vaikeutta tuo se, että väärä toteutus silti tuottaa allekirjoituksia, silti tarkistaa omat allekirjoituksensa ja silti näyttää täysin uskottavalta

Miksi nämä käyrät, ja miksi Pascalissa

Brainpool-käyrät esiintyvät eurooppalaisissa kvalifioitujen allekirjoitusten profiileissa, joten kirjasto, joka allekirjoittaa dokumentteja sille markkinalle, ei voi pitää niitä eksoottisina. Ed448 kuuluu algoritmijoukkoon, jonka ISO/TS 32002 tuo PDF:ään, ja sen sisäinen tiiviste on SHA-2:n sijaan SHAKE256. Kumpaakaan perhettä ei ole yleisessä käytössä olevissa Pascal-salakirjastoissa, joten PDF-kirjaston, joka niitä haluaa, on omistettava ne itse

Jakeluargumentti on sama, joka pätee tämän kirjaston koko kryptografiaan: sovellus, joka toimittaa yhden binäärin ilman kryptografisia riippuvuuksia, ei tarvitse havaita tarjoajaa, ei sovittaa versioita eikä käyttäydy eri tavalla, kun isäntäympäristöä paikataan. Allekirjoitus on juuri se alue, jossa liikkuvaa riippuvuutta haluaa vähiten

Vakiot tulevat määrittelytekstistä, ei koskaan muistista

Ensimmäinen yritys edwards448-kantapisteeksi kirjoitettiin muistista ja oli väärä. Se ei ole erikoinen virhe, mutta se on erittäin kallis, koska väärä kantapiste tuottaa itsensä kanssa yhtenäisen järjestelmän: avaingenerointisi, allekirjoituksesi ja tarkistuksesi sopivat keskenään ja eroavat muusta maailmasta

Toimiva menettely on ottaa jokainen domaaniparametri määrittelytekstistä ja sitten ristiintarkistaa. edwards448:n osalta se tarkoittaa alkulukua, käyrävakiota, ryhmän kertalukua ja kantapisteen molempia desimaalikoordinaatteja RFC 8032:sta, muunnettuna sisäiseen limbiesitykseen ja sen jälkeen tarkistettuna samasta dokumentista saatujen julkaistujen testivektoreiden avulla. Brainpool-käyrien osalta se tarkoittaa parametreja RFC 5639:stä, vektorien tuottamiseen kirjoitettua itsenäistä toteutusta ja ristiintarkistusta järjestelmäkirjastoa vastaan molempiin suuntiin ennen kuin yhtään Pascal-koodia ajettiin

Yksi johtamisoikotie ansaitsee varoituksen, koska se näyttää yleispätevältä eikä ole: kantapisteen palauttaminen kiinteästä y-arvosta toimii 25519-käyrälle eikä toimi edwards448:lle, jossa tuolla arvolla ei ole neliöjuurta. Skripti kumosi oletuksen sekunneissa, mikä on paljon halvempaa kuin sen havaitseminen debuggerin kautta

Menetelmä: limbitason peilitoteutus ennen mitään Pascalia

Tekniikka, joka teki molemmista yksiköistä hallittavia, on peilitoteutus kielellä, jonka kokonaisluvut ovat rajoittamattomia, rakennettuna alhaalta ylöspäin. Ensin pelkkä aritmeettinen kerros: kuntakertolasku, vähennyslasku ja siirtojen eteneminen, stressitestattuna niiden algebrallisia invariantteja vastaan parissasadassa satunnaisessa tapauksessa. Sitten täysi avaingenerointi peilin sisällä, sillä semanttiset virheet asuvat siellä ja niiden löytäminen on siellä halpaa. Vasta sen jälkeen Pascal-transkriptio

Hyöty on diagnostinen pikemminkin kuin kehittävä. Kun peili tiedetään oikeaksi, jokainen ristiriita peilin ja Pascalin välillä on transkriptiomokka, ja saman väliarvon tutkiminen molemmissa toteutuksissa paikantaa sen välittömästi. Se muuntaa virheluokan, joka on muuten lähes debuggaamaton – yksi väärä limb syvällä skalaarikertolaskun sisällä – viiden minuutin vertailuksi

Neljä juurisyytä Ed448:ssa

Kaikki neljä löytyivät väliarvoja tutkimalla, ja kaikki neljä ovat sellaisia, että ne tuottavat pätevän näköistä tulostetta

Ensimmäinen on merkintätavan ansa. Useimmat julkaistut yhtenäisen Edwards-lisäyksen kaavat olettavat käyrävakioksi miinukselle ykkösen, ja edwards448:lla se on plus ykkönen. Muuttumattomana siirrettynä y-koordinaatin osoittaja kirjoitetaan summaksi, vaikka sen pitäisi olla erotus. Korjaus ei ole merkin paikkaaminen vaan inversiottoman tulomuodon uudelleenjohtaminen oikean käyrän affiinisesta lisäyslaista, mikä tuottaa neljä koordinaattilauseketta eikä jätä tilaa sille, että merkki periytyisi väärästä lähteestä

Toinen on pisteen dekompressiossa. Affiinisen x:n palauttaminen projektiivisista koordinaateista vaatii yhden kertolaskun Z:n käänteisarvolla. Kertolasku käänteisarvon neliöllä tuottaa arvon, joka on yhä pätevä projektiivinen esitys ja on väärä affiininen koordinaatti, joten oire on oikea y väärällä x:llä. Aina kun toinen koordinaatti on oikea ja toinen ei, virhe on normalisoinnissa, ei aritmetiikassa

Kolmas on lyhyemmästä käyrästä tuotu tapa. Sekä allekirjoituskohtainen skalaari että haasteskalaari on redusoitava täydellisestä tiivisteestä, joka Ed448:lla on 114 tavua, ei sen ensimmäisestä 57:stä. 32-tavuinen käyrä käyttää täyttä 64-tavuista tiivistettään myös, joten sääntö on johdonmukainen; vain oletus siitä, että ”puolet tiivisteestä on skalaarin leveys”, on väärä

Neljäs on järjestys. Domaanin erotteluetuliite tulee ensin, ennen kontekstietuliitetta ja viestiä, mikä ei ole se järjestys, jota määrittelyn R:n ja A:n intuitiivinen lukutapa antaisi ymmärtää. Tämän saaminen väärin tuottaa allekirjoituksia, jotka tarkistuvat vasten omaa toteutustasi eikä mitään muuta, mikä on mahdollisimman harhaanjohtava vika

// Kuntacarryn suunnittelu: puhdas floor-semantiikan mukainen eteneminen, joten
// sekä positiiviset että negatiiviset limb-arvot toimivat ja vähennyslasku
// ei vaadi biasia.
// Ylin carry taituu takaisin muodossa 2^448 = 2^224 + 1 (mod p), mikä
// koskettaa limbejä 0 ja 8. Rajattu neljään kierrokseen; kaksi havaittu
// käytännössä
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, ei katkaisua
      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;

Kyseisen rutiinin aiempi versio sovelsi biasia ennen etenemistä, ja suurilla syötteillä se taitoi väärän suuruisen virheellisen carryn mataliin limbeihin. Biasiin perustuvat carry-ratkaisut ovat pysyvä tämän virheluokan lähde; floor-semantiikka rajatulla toistorakenteella on helpompi päätellä ja mitattavasti riittävän nopea

Kaksi juurisyytä Brainpoolissa

Ensimmäinen ei ole kryptografiaa lainkaan. Toimiva esitys on 33 limbiä, joten kahden arvon tulo vaatii 66, ja tulotaulukko oli ilmoitettu 64:lle. Rajojen yli kirjoittaminen korruptoi viereistä muistia, mikä ilmeni ensin väärinä tuloksina ja muuttui kaatumiseksi vasta, kun laajempi skannaus lisättiin. Siitä syntynyt sääntö kannattaa soveltaa jokaiseen kiinteän kokoiseen numeeriseen puskuriin: kokoa se pahimman mahdollisen tulon leveyden mukaan ja lisää varaa, äläkä ajattele asiaa sen jälkeen enää. Toimitettavassa koodissa taulukko on 68 limbiä

Toinen on sekoittunut potenssiinkorotusmuoto. Oikeita neliöi ja kerro -muotoja on kaksi, ja ne kuluttavat eksponentin vastakkaisiin suuntiin: oikealta vasemmalle etenevässä muodossa kertolasku tulee ensin ja kanta korotetaan neliöön sen jälkeen, ja bitit on luettava vähiten merkitsevästä päästä, kun taas vasemmalta oikealle etenevässä muodossa kanta korotetaan neliöön ensin ja kertolasku tulee sen jälkeen, ja bitit luetaan merkitsevimmästä päästä. Modulaarisen inversiollaupulla oli oikealta vasemmalle etenevä runko, jossa bittikulku lähti merkitsevimmästä päästä. Molemmat puoliskot ovat oppikirja-ainesta, yhdistelmä ei ole, ja tulos on väärä käänteisarvo, joka silti näyttää uskottavalta kunnan alkiolta

// Jacobin tuplaus ja lisäys tapauksessa, jossa kohdetietue voi olla
// sama muuttuja kuin jokin lähteistä. Koko tietueen kopiointi alussa on
// ainoa luotettava suoja: R:n limbien kirjoittaminen saastuttaa P:n
// myöhemmät luvut
procedure BPPointDouble(var R: TBPPoint; const P: TBPPoint;
  const Curve: TBPCurve);
var
  Pin: TBPPoint;
begin
  Pin := P;        // kopioi ensin, laske sitten vain Pin-arvoista
  // ... M = 3X^2 + A*Z^4, S = 4*X*Y^2, X3 = M^2 - 2S, ...
end;

Kaksi prosessiopetusta, jotka maksoivat enemmän kuin virheet

Vaiheittainen hotfixaaminen ei konvergoi kryptografisessa yksikössä. Yhtä luonnosta paikattiin toistuvasti, kunnes se kantoi 32 kahdennettua rutiinia ja vaurioitunutta rakennetta, ja se korjautui vain uudelleenkirjoittamalla. Omaksuttava malli on joko kirjoittaa koodi kerran validoidun peilin pohjalta tai kirjoittaa se uudelleen; sarja paikallisia korjauksia aritmetiikkaan, jota ei vielä ymmärrä, kertyy nopeammin kuin korjautuu

Ja tarkista suoritettavan tiedoston aikaleima ennen kuin uskot testitulosta. Inkrementaalinen käännös, joka kääntyy mutta ei linkitä uudelleen, ajaa edellistä binääriä, mikä valmisti kokonaisen kierroksen vääriä johtolankoja puuttuvista tutkimuskohdista ja kahdentuneesta tulosteesta. Kryptografiaa debugatessa selittämättömän tuloksen pitäisi herättää kysymys ”onko tämä juuri kääntämäni binääri” ennen kysymystä ”onko algoritmi väärä”

Suorituskyky, laajuus ja miten sitä kutsutaan

Modulaarinen reduktio Brainpool-yksikössä on bittisarjainen siirto-vähennys tuotteen ylimmästä asetetusta bitistä, joten kertolasku maksaa karkeasti bittileveyden suuruusluokan. P-256-tarkistus mahtuu mataliin satoihin millisekunteihin, mikä on merkityksetöntä dokumenttien allekirjoittamisessa tai tarkistamisessa mutta olisi riittämätöntä TLS-päätteilta. Barrett-reduktio on ilmeinen päivitys ja se tarvitsee leveämmän työarvon kuin nykyinen esitys kantaa, joten se on muutos, joka tehdään silloin, kun kuormitus sitä vaatii, eikä ennakolta

uses
  PDFlibEd448, PDFlibBrainpool;

var
  PublicKey, Signature: AnsiString;
  Curve: TBPCurve;
  R, S, PubX, PubY: TBPValue;
begin
  // Ed448: PureEdDSA, SHAKE256 sisäisesti, 57-tavuiset avaimet
  if Ed448PublicKeyFromSeed(Seed, PublicKey) and
     Ed448Sign(DocumentDigest, Seed, Signature) then
    Assert(Ed448Verify(DocumentDigest, PublicKey, Signature));

  // Brainpool: kutsuja toimittaa allekirjoituskohtaisen noncen, joten
  // nonce-politiikka pysyy sovelluksessa
  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;

Huomaa, että Brainpoolin allekirjoituksen sisääntulopiste ottaa noncen vastaan sen sijaan, että generoisi sen itse. Se on tahallista: noncen generointi on ehdottomasti katastrofaalisin asia, jonka voi saada väärin ECDSA:ssa, sillä toistuva tai ennustettava arvo paljastaa yksityisen avaimen, ja päätös siitä, mistä satunnaisuus tulee, kuuluu sovellukselle ja sen vaatimustenmukaisuusjärjestelmälle, ei PDF-kirjastolle

Nämä käyrät asettuvat rinnalle FIPS 204 ML-DSA -artikkelissa kuvatun post-kvanttityön kanssa, ja ne kytkeytyvät samaan allekirjoitus- ja validointiputkeen, josta PAdES-allekirjoitus ja validointi kertoo. Testisertifikaattien paikallinen generointipolku näillä käyrillä on kuvattu artikkelissa itse allekirjoitetuista sertifikaateista CryptoAPI:lla. Koko algoritmimatriisi on lueteltu losLab PDF Developer Library -tuotesivulla