NIST-käyräaritmetiikka puhtaalla Pascalilla PDF:ään

HotPDF suorittaa ellipsikäyrien avainsopimuksen ja allekirjoitusten varmennuksen PDF:lle puhtaassa Object Pascalissa ilman OpenSSL-sidontaa, eikä polulla ole alustan salauspalveluntarjoajaa. Se kattaa viisi käyrää: P-256, P-384 ja P-521 NIST-alkulukuperheille sekä X25519 ja X448 Montgomery-käyrän avainsopimukseen. Syy kirjoittaa kyseinen koodi linkittämisen sijaan on jakelu, ei puhtaus. Delphi- tai Free Pascal -sovellus, joka toimittaa yhden suoritettavan eikä mitään salaus-DLL:ää, ei hallitse versioeroja, ei havaitse alustakohtaisia tarjoajia, eikä mikään muutu, kun asiakas paikkaa järjestelmäkirjastojaan

Hinta on, että omistat nyt aritmetiikan. Suurkokonaislukujen modulaarikertolasku on armoton koodi: se joko tuottaa tavuidenttisiä tuloksia julkaistuja testivektoreita vastaan tai tuottaa uskottavan näköistä roskaa, ja näiden kahden tilan etäisyys voi olla yksi vertailu. Tämä on tuon vertailun tarina, koska virheen muoto yleistyy mille tahansa kunta-aritmetiikan Pascal-portille

Miksi PDF-kirjasto tarvitsee käyräaritmetiikkaa ylipäätään?

Kaksi ominaisuutta vetää sen sisään. Ensimmäinen on dokumenttien julkisen avaimen salaus: ISO 32000:n vastaanottajaluettelokäsittelijä käärii dokumenttikohtaisen avaimen nimetyille sertifikaateille, ja kun vastaanottajalla on EC-avain, kääriminen kulkee avainsopimuksen kautta RSA-avainkuljetuksen sijaan. Ilman ECDH:tä ei ole tapaa avata sellaista dokumenttia. Toinen on allekirjoitusten validointi. ECDSA-allekirjoituksen varmentaminen /ByteRange-tavujen yllä vaatii pistekertolaskun allekirjoittajan käyrällä, ja P-384 on yleinen hallinto- ja kvalifioitujen allekirjoitusten profiileissa, joissa P-256 katsotaan lattiaksi eikä tavoitteeksi. HotPDF paljastaa kyseisen työn tulokset ECDSA- ja CMS-varmennuspolun kautta sekä liitettävän allekirjoitustarjoajamallin kautta

Kaavio siitä, missä HotPDF:n puhdasta Pascal-käyräaritmetiikkaa käytetään: vastaanottajaluettelon ECDH-salaus ja ECDSA-allekirjoituksen varmennus ByteRangen yllä — Avainsopimus avaa EC-salatut dokumentit nimetyille vastaanottajille, kun taas allekirjoitusten validointi vaatii pistekertolaskun allekirjoittajan käyrällä

CIOS ja se yksi vähennyslasku lopussa

Montgomery-kertolasku välttää jakolaskun toimimalla muunnetussa domaanissa, jossa reduktio on siirto. Variantti, jota HotPDF käyttää, on Coarsely Integrated Operand Scanning, joka lomittaa kertolaskun ja reduktion limb kerrallaan, joten väliarvo ei koskaan kasva moduluksen leveyden plus yhden limb:n ohi. Silmukkarunko on suoraviivainen ja helppo testata. Häntä ei ole: lomitettujen läpikäyntien jälkeen kertymä voi olla missä tahansa aina moduluksen kaksinkertaiseen asti, joten algoritmi päättyy ehdolliseen vähennykseen, joka poistaa yhden kopion alkuluvusta jos ja vain jos kertymä on suurempi tai yhtä suuri kuin se

Kahden monilimbisen luvun vertailu tarkoittaa kulkemista merkitsevimmästä limbistä alaspäin lainaa kantaen. Ilmeinen tapa kirjoittaa se on verrata kertymän limb:iä moduluksen limb:iin plus saapuvaan lainaan. Tuo lauseke on väärä, ja se on väärin tavalla, jonka useimmat käyrät piilottavat

// Väärin: P[I] + Borrow voi kiertää, kun P[I] on $FFFFFFFFFFFFFFFF
if T[I] < P[I] + Borrow then
begin
  Borrow := 1;
  Break;
end;

// Oikein: vertaa koskaan lisäämättä limb:iin
if (T[I] < P[I]) or ((T[I] = P[I]) and (Borrow = 1)) then
begin
  Borrow := 1;
  Break;
end;

Miltä lainan ympyräkierto oikeasti näyttää?

Se näyttää käyrältä, joka toimii kaikkialla paitsi tuotannossa. P-384:n ja P-521:n alkuluvut sisältävät limbejä, jotka ovat kokonaan ykkösiä, joten P[I] on yhtä suuri kuin $FFFFFFFFFFFFFFFF. Lisää siihen saapuva laina ykkösenä, ja 64-bittinen etumerkitön kiertää nollaan. Vertailu kysyy sitten, onko kertymän limb pienempi kuin nolla, päättää ettei ole ja päättelee, ettei lainaa tarvita. Tuloksen yksi limb on yhden väärässä

Montgomery-reduktion lainankiertokaavio, joka asettaa vastakkain väärän limb-vertailun ja oikean lainan etenemisen HotPDF:n P-384-aritmetiikassa — Lainan lisääminen kaikki-ykkösiä olevaan limbiin kiertää nollaan, joten P-384 ja P-521 jäävät ilman vähennystä, kun taas P-256 piilottaa vian

P-256 selviytyy, koska yksikään sen limbeistä ei ole kaikki-ykkösiä, joten yhteenlasku ei koskaan vuoda ja viallinen lauseke sattuu sopimaan yhteen oikean kanssa. Se on mahdollisimman pahin lopputulos testisarjalle: testatuin käyrä läpäisee, vähemmän testatut epäonnistuvat katkonaisesti operandiarvojen mukaan, ja vika ilmenee varmennustuloksena ”virheellinen allekirjoitus” täysin pätevissä dokumenteissa. HotPDF kantoi nimenomaista porttia P-384:lla täsmälleen tästä syystä palauttaen ei-saatavissa-tilan väärän vastauksen sijaan, kunnes aritmetiikka oli todistettu vertailuvektoreita vastaan

Miten virhe oikeasti paikannettiin

Ei lukemalla koodia. Tuottava jakso oli mekaaninen, ja se on uudelleenkäytettävä. Ensiksi, eliminoidaan vakiot: jokainen p:n, R:n ja R^2:n limb regeneroitiin itsenäisesti ja verrattiin limb kerralta, mikä sulkee pois yleisimmän käyrävirheiden lähteen. Toiseksi, instrumentoidaan aritmetiikkaa API:n sijaan: väliaikainen dump-proseduuri tulosti Montgomery-kertolaskun väliarvot luvuille R^2, x^3 ja y^2 tunnetulle pisteelle, joten ne voitiin tarkistaa itsenäisesti laskettua totuutta vastaan

Tuo vertailu osoitti suoraan syylliseen. x-ketju oli oikea päästä päähän, kun taas y^2 erosi täsmälleen yhdessä limbissä täsmälleen yhdellä. Yhden limb:n ero yhdellä ei ole kertolaskuvika, siirron etenemisen vika eikä vakiovika; se on lainaketjun vika, ja ainoa lainaketju rutiinissa on lopullinen ehdollinen vähennys. Yksi yksityiskohta lähes suistasi tämän raiteiltaan: dumpiin käytetty vertailuvakio oli itse kirjoitettu väärään tavujärjestykseen ensimmäisellä yrityksellä, mikä tuotti erimielisyyden y-arvossa ja ehdotti hetken aikaa toista, olematonta viaa. Varmista totuusarvosi tavujärjestys ennen kuin luotat sen syyttävän koodiasi

Vuokaavio siitä, miten HotPDF:n käyrävika paikannettiin regeneroimalla vakiot, vedostamalla Montgomery-väliarvot ja diffaamalla peilitotuuutta vastaan — Yhden limb:n ero täsmälleen yhdellä osoitti suoraan rutiinin ainoaan lainaketjuun, ja tavujärjestystä vaihdettu vertailu lähes suisti jahtia harhaan

Naapuriansat samassa rutiinissa

Kolme muuta vikamuotoa asuu muutaman rivin päässä tuosta vertailusta, ja kaikki kolme olivat eläviä jossakin kehityksen vaiheessa

// 1. Kertymällä on yksi limb moduluksen leveyden yläpuolella. Vain
//    matalien L limbien vertailu ohittaa tapauksen, jossa T on täsmälleen
//    p plus 2^(64*L), mikä tapahtuu merkittävälle osalle satunnaisista
//    syötteistä, koska 2p ylittää arvon 2^256 P-256:lla ja 2^384 P-384:lla
if (T[L] <> 0) or NotLessThanModulus(T, P, L) then
  SubtractModulus(T, P, L);

// 2. Yleisellä monilimbisellä vähennyksellä on sama kierroriski: kun
//    Y[I] on $FFFFFFFFFFFFFFFF, Y[I] + Borrow kiertää nollaan ja
//    lainan on jäätävä seuraavaan limbiin sen sijaan että se nollataan
Diff := X[I] - Y[I] - Borrow;
NextBorrow := Ord((X[I] < Y[I]) or ((X[I] = Y[I]) and (Borrow = 1)));

Kolmas ei ole koodia, se on alkuperätieto. P-521:n alkuluku oli aluksi transkriboitu 130 heksanumerolla 131:n sijaan, yksi F vajaa, ja Montgomery-vakiot laskettiin sitten siitä väärästä alkuluvusta, joten vakiot olivat itsensä kanssa yhdenmukaisia ja yhteisesti vääriä. Käyräparametrit on johdettava, ei koskaan näppäiltävä: laske R muodossa (1 shl (64 * L)) mod p käyttämästäsi alkuluvusta ja ristiintarkista sitten R * R mod p arvoa vastaan, jota R^2-vakiosi väittää. Vakioaparit, jotka sopivat keskenään, eivät todista mitään kummastakaan

Varmennusstrategia, joka skaalautuu yhden käyrän ohi

Tekniikka, joka teki X25519:sta ja X448:sta hallittavia, oli peilitoteutuksen kirjoittaminen kielellä, jonka kokonaisluvut ovat rajoittamattomia, ja Pascal-ohjausvirran transkriboiminen siihen rivi riviltä. Kun peili tuottaa oikean vastauksen eikä Pascal, vika on transkriptiomokka, ja saman väliarvon tutkiminen molemmissa toteutuksissa löytää sen sekunneissa. Kaikki kolme klassista RFC 7748 -tikapuuvirhettä napattiin tällä tavalla: vakioaikainen vaihto, jonka toinen rivi käytti jo vaihdettua arvoa uudelleen, lopullinen inversio, joka palautti z:n potenssiin miinus yksi sen sijaan että olisi kertonut sen X:n kanssa, ja pienen vakion kertolasku, joka kokosi puolisanojen tulokset bittikohtaisella tai-operaatiolla ja menetti siirron

Testimateriaalin osalta ota vektorit tavuina tekstin sijaan. Yksityisen avaimen poimiminen tekstikuviolla on tapa, jolla oikea toteutus syyllistetään yhden tavun verran pieleen menevästä virheestä, joka asuu kokonaan poimintavaiheessa. Viipaloi heksa DER-koodauksesta tunnetuilta siirtymiltä ja vertaa tavutaulukoita

Lainaketjun korjaamisen jälkeen kaikki viisi käyrää täsmäävät julkaistuihin vertailuvektoreihin tavu tavulta, eikä HotPDF enää rajaa mitään niistä. Jos integroit sertifikaattipohjaista allekirjoittamista tai vastaanottajaluettelosalausta, käytännön opetus on, että käyrän valinta on nyt politiikkapäätös eikä kyvykkyyden kysymys; allekirjoituspuolen profiilit ja tavujärjestysansat käsitellään artikkelissa PAdES-allekirjoituksen läpikäynti. Komponentin yksityiskohdat ja tuettu algoritmimatriisi ovat HotPDF Delphi PDF -komponentin tuotesivulla