Postkvantna kriptografija – nov algoritem "izginil v 60 minutah"

Pisali smo o PQC, okrajšavi za postkvantna kriptografija, večkrat prej.

Če ste zamudili vse medijsko navdušenje zadnjih nekaj let o tako imenovanem kvantnem računalništvu ...

… je (če oprostite, kar bodo nekateri strokovnjaki verjetno imeli za nepremišljeno poenostavljanje) način gradnje računalniških naprav, ki lahko sledijo več možnih rezultatov izračuna hkrati.

Z veliko previdnosti in morda malo sreče to pomeni, da lahko nekatere vrste algoritmov prepišete tako, da ugotovite pravi odgovor, ali pa vsaj pravilno zavržete celo vrsto napačnih odgovorov, ne da bi poskušali in testirali vse možne rezultate. enega po enega.

Z uporabo kvantne računalniške naprave sta možni dve zanimivi kriptoanalitični pospešitvi, ob predpostavki, da je mogoče dejansko izdelati ustrezno zmogljivo in zanesljivo:

• Groverjev kvantni iskalni algoritem. Običajno, če želite preiskati naključno urejen niz odgovorov, da vidite, ali je vaš na seznamu, pričakujete, da boste v najslabšem primeru prebrskali celoten seznam, preden boste dobili dokončen odgovor. Če bi na primer želeli najti 128-bitni ključ za dešifriranje AES za dekodiranje dokumenta, bi morali poiskati seznam vseh možnih ključev, začenši pri 000..001, ..2, ..3, in tako naprej, vse do FFF..FFF (v vrednosti 16 bajtov FF), da se prepričate o dokončanju težave. Z drugimi besedami, imeti morate proračun, da poskusite vsa 2¹²⁸ možne ključe, preden najdejo pravi ključ ali ugotovijo, da ga ni. Groverjev algoritem pa ob velikem in dovolj zmogljivem kvantnem računalniku trdi, da je sposoben dokončati isti podvig z kvadratni koren običajnega truda, tako da teoretično razbije kodo v samo 2⁶⁴ poskuša namesto tega.
• Shorov algoritem kvantne faktorizacije. Več sodobnih šifrirnih algoritmov temelji na dejstvu, da je mogoče hitro pomnožiti dve veliki praštevili, medtem ko je delitev njihovega produkta nazaj na dve števili, s katerima ste začeli, skoraj nemogoča. Da bi dobili občutek za to, poskusite pomnožiti 59 × 87 s pisalom in papirjem. Morda bo trajalo kakšno minuto, da ga dobite ven (5133 je odgovor), vendar ni tako težko. Zdaj pa poskusite drugače. Razdelite, recimo, 4171 nazaj na dva faktorja. Veliko težje! (Je 43 × 97.) Zdaj pa si predstavljajte, da to počnete s številko, ki je dolga 600 števk. Ohlapno povedano, obtičate pri poskusu delitve 600-mestnega števila z vsemi možnimi 300-mestnimi praštevili, dokler ne zadenete glavnega dobitka ali ugotovite, da odgovora ni. Shorov algoritem pa obljublja rešitev tega problema z logaritem običajnega napora. Tako bi moralo faktoriziranje števila 2048 binarnih števk trajati samo dvakrat dlje kot faktoriziranje 1024-bitnega števila, ne pa dvakrat dlje kot faktoriziranje 2047-bitnega števila, kar predstavlja ogromno pospešitev.

Boj proti grožnji

Groverjevemu algoritmu se lahko zoperstavite preprosto tako, da povečate velikost števil, ki jih uporabljate, tako da jih kvadrirate, kar pomeni podvojitev števila bitov v vašem kriptografskem zgoščevanju ali vašem simetričnem šifrirnem ključu. (Z drugimi besedami, če menite, da je SHA-256 trenutno v redu, bi uporaba SHA-512 namesto tega zagotovila alternativo, odporno na PQC.)

Toda Shorovemu algoritmu ni mogoče tako zlahka nasprotovati.

2048-bitni javni ključ bi potreboval eksponentno povečanje velikosti, ne zgolj s kvadriranjem, tako da bi namesto ključa 2×2048=4096 bitov potrebovali nov ključ z nemogočo velikostjo 2.²⁰⁴⁸ koščki…

… ali pa bi morali sprejeti popolnoma novo vrsto sistema postkvantnega šifriranja, za katerega Shorov algoritem ni veljal.

No, ameriški organ za standarde NIST vodi a PQC "konkurenca" od konca leta 2017.

Postopek je bil odprt za vsakogar, vsi udeleženci so bili dobrodošli, vsi algoritmi so javno objavljeni, javni nadzor pa ni le mogoč, ampak aktivno spodbujali:

Razpis za zbiranje predlogov. [Zaprto 2017]. […] Namenjeno je, da bodo novi standardi kriptografije z javnimi ključi določali enega ali več dodatnih nerazvrščenih, javno razkritih digitalnih podpisov, šifriranja z javnimi ključi in algoritmov za vzpostavitev ključev, ki so na voljo po vsem svetu in so sposobni zaščititi občutljive vladne podatke. v bližnji prihodnosti, tudi po prihodu kvantnih računalnikov.

Po treh krogih prispevkov in razprav, NIST objavil, dne 2022-07-05, da je izbral štiri algoritme, ki jih je štel za "standarde" s takojšnjim učinkom, vse s čudovito zvenečimi imeni: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONin SPHINCS+.

Prvi (CRYSTALS-KYBER) se uporablja kot tisto, kar se imenuje a Ključni mehanizem dogovora (KEM), kjer dva konca javnega komunikacijskega kanala varno sestavita enkratni zasebni šifrirni ključ za zaupno izmenjavo podatkov v vrednosti seje. (Enostavno povedano: vohljači dobijo samo narezano zelje, da ne morejo prisluškovati pogovoru.)

Drugi trije algoritmi se uporabljajo za Digitalni podpisi, s čimer lahko zagotovite, da se podatki, ki ste jih poslali na vaši strani, točno ujemajo s tistimi, ki jih je pošiljatelj vnesel drugemu, s čimer preprečite poseganje in zagotovite celovitost. (Enostavno povedano: če bo kdo poskušal poškodovati podatke ali se z njimi zapletati, boste vedeli.)

Potrebno je več algoritmov

Hkrati z objavo novih standardov je NIST objavil tudi a četrti krog svoje konkurence, s čimer je izpostavil nadaljnje štiri algoritme kot možne alternativne KEM. (Ne pozabite, da imamo v času pisanja že na voljo tri odobrene algoritme za digitalno podpisovanje, a samo enega uradnega KEM.)

Ti so bili: BIKE, Classic McEliece, HQC in SIKE.

Zanimivo je, da McEliecejev algoritem je davnega leta 1970 izumil ameriški kriptograf Robert Mc Eliece, ki je umrl leta 2019, precej potem, ko je tekmovanje NIST že potekalo.

Vendar se ni nikoli prijel, ker je zahteval ogromne količine ključnega materiala v primerjavi s priljubljeno alternativo tistega časa, algoritmom Diffie-Hellman-Merkle (DHM ali včasih samo DH).

Na žalost eden od treh algoritmov četrtega kroga, namreč SIKE, se zdi, da je bil razpokan.

V prispevku z naslovom, ki vam prepleta možgane UČINKOVIT NAPAD ZA OBNOVITEV KLJUČEV NA SIDH (PREDHODNA RAZLIČICA), se zdi, da sta belgijska kriptografa Wouter Castryk in Thomas Decru zadala nekakšen smrtonosni udarec algoritmu SIKE

Če se sprašujete, je SIKE okrajšava za Enkapsulacija ključa supersingularne izogenije, SIDH pa pomeni Supersingularna izogenija Diffie-Hellman, posebna uporaba algoritem SIKE pri čemer dva konca komunikacijskega kanala izvajata "kripto ples" podobno DHM za izmenjavo množice javnih podatkov, ki vsakemu koncu omogočajo, da izpelje zasebno vrednost, ki jo uporabi kot enkratni skrivni šifrirni ključ.

Tukaj ne bomo poskušali razložiti napada; samo ponovili bomo, kar trdi časopis, in sicer:

Zelo ohlapno povedano, vhodni podatki tukaj vključujejo javne podatke, ki jih zagotovi eden od udeležencev v ključni ustanovi cryptodance, skupaj z vnaprej določenimi (in zato javno znanimi) parametri, uporabljenimi v procesu.

Toda izhod, ki je ekstrahiran (informacije, imenovane kot izogenija φ zgoraj) naj bi bil nikoli razkriti del procesa – tako imenovani zasebni ključ.

Z drugimi besedami, samo iz javnih informacij, kot so podatki, odprto izmenjani med nastavitvijo ključa, kriptografi trdijo, da lahko obnovijo zasebni ključ enega od udeležencev.

In ko poznate moj zasebni ključ, se lahko zlahka in nezaznavno pretvarjate, da ste jaz, tako da je postopek šifriranja pokvarjen.

Očitno algoritem za razbijanje ključev potrebuje približno eno uro, da opravi svoje delo, pri čemer uporablja samo eno jedro procesorja s takšno procesorsko močjo, kot jo najdete v vsakdanjem prenosniku.

To je v nasprotju z algoritmom SIKE, ko je konfiguriran tako, da izpolnjuje raven 1, osnovno stopnjo varnosti šifriranja NIST.

Kaj storiti?

Nič!

(To je dobra novica.)

Kot predlagajo avtorji prispevka, potem ko so ugotovili, da je njihov rezultat še predhoden, "s trenutnim stanjem se zdi, da je SIDH popolnoma pokvarjen za katero koli javno ustvarjeno osnovno krivuljo."

(To je slaba novica.)

Glede na to, da algoritem SIKE še ni uradno odobren, ga je zdaj mogoče bodisi prilagoditi za preprečitev tega posebnega napada (kar avtorji priznavajo, da je mogoče) ali pa ga preprosto popolnoma opustiti.

Karkoli se končno zgodi s SIKE, je to odličen opomnik, zakaj je poskušanje izumljanja lastnih šifrirnih algoritmov polno nevarnosti.

To je tudi jasen primer, zakaj lastniški sistemi šifriranja ki se zanašajo na tajnost samega algoritma ohranjanje njihove varnosti so v letu 2022 preprosto nesprejemljivi.

Če bi algoritem PQC, kot je SIKE, več kot pet let preživel neprepričljiva in testiranja strokovnjakov z vsega sveta, kljub temu, da je bil posebej razkrit, da bi bil lahko podvržen javnemu nadzoru ...

…potem se ni treba spraševati, kako dobro se bodo obnesli vaši domači, očem skriti šifrirni algoritmi, ko bodo izpuščeni v divjino!

---