Kvantjärgne krüptograafia – uus algoritm "läinud 60 minutiga"

Oleme kirjutanud PQC-st, lühendatult postkvantkrüptograafia, mitu korda varem.

Juhul, kui olete vahele jätnud kogu viimaste aastate meediapõnevuse niinimetatud kvantarvutuse kohta…

…see on (vabandage, mida mõned eksperdid peavad ilmselt hoolimatuks ülelihtsustuseks) viis luua arvutusseadmeid, mis suudavad jälgida mitu võimalikku tulemust samal ajal arvutada.

Suure ettevaatusega ja võib-olla natuke õnnega tähendab see, et saate teatud tüüpi algoritme õige vastuse juurde kirjutada või vähemalt terve hulga valesid vastuseid õigesti kõrvale jätta, ilma et prooviksite ja katsetaks kõiki võimalikke tulemusi. ükshaaval.

Kvantarvutusseadme abil on võimalik kaks huvitavat krüptoanalüütilist kiirendamist, eeldades, et tegelikult saab konstrueerida sobivalt võimsa ja usaldusväärse:

• Groveri kvantotsingu algoritm. Tavaliselt, kui soovite otsida juhuslikult järjestatud vastuste komplekti, et näha, kas teie oma on loendis, peaksite halvimal juhul enne lõpliku vastuse saamist kogu loendi läbi kündma. Näiteks kui soovite leida 128-bitist AES-i dekrüpteerimisvõtit dokumendi lahtikodeerimiseks, peate otsima kõigi võimalike võtmete loendist, alustades 000..001, ..2, ..3ja nii edasi kuni FFF..FFF (16 baiti väärtuses FF), et olla kindel probleemi lahendamises. Teisisõnu, kõigi kahe proovimiseks peate eelarvesse määrama¹²⁸ võimalikke võtmeid enne õige võtme leidmist või selle puudumise tuvastamist. Groveri algoritm aga, arvestades piisavalt suurt ja võimsat kvantarvutit, väidab, et suudab sama vägiteo sooritada ka ruutjuur tavalisest pingutusest, murdes seega koodi teoreetiliselt vaid 2-ga⁶⁴ selle asemel proovib.
• Shori kvantfaktoriseerimise algoritm. Mitmed kaasaegsed krüpteerimisalgoritmid tuginevad asjaolule, et kahe suure algarvu korrutamist saab teha kiiresti, samas kui nende korrutise jagamine kaheks arvuks, millest alustasite, on sama hästi kui võimatu. Selle tunnetamiseks proovige pliiatsi ja paberi abil korrutada 59 × 87. Selle eemaldamiseks võib kuluda umbes minut (vastus on 5133), kuid see pole nii raske. Nüüd proovige teist teed. Jagage näiteks 4171 kaheks teguriks. Palju raskem! (See on 43 × 97.) Kujutage ette, et teeksite seda numbriga, mis on 600 numbrit pikk. Kui rääkida lõdvalt, siis proovite jagada 600-kohalist arvu kõigi võimalike 300-kohaliste algarvudega, kuni saavutate jackpoti või avastate, et vastust pole. Shori algoritm lubab aga selle probleemi lahendada logaritm tavapärasest pingutusest. Seega peaks 2048-bitise kahendnumbri faktooreerimine võtma vaid kaks korda kauem aega kui 1024-bitise arvu faktooreerimine, mitte aga kaks korda kauem kui 2047-bitise numbri faktoorimine, mis tähendab tohutut kiirust.

Ohu vastu võitlemine

Groveri algoritmist tulenevat ohtu saab tõrjuda lihtsalt kasutatavate numbrite suuruse suurendamisega, muutes need ruutudeks, mis tähendab krüptograafilise räsi või sümmeetrilise krüpteerimisvõtme bittide arvu kahekordistamist. (Teisisõnu, kui arvate, et SHA-256 on praegu korras, annaks selle asemel SHA-512 kasutamine PQC-kindla alternatiivi.)

Kuid Shori algoritmi ei saa nii lihtsalt vastu panna.

2048-bitise avaliku võtme suurust tuleks suurendada eksponentsiaalselt, mitte lihtsalt ruudu muutmise teel, nii et võtme 2 × 2048 = 4096 bitise asemel oleks vaja uut võtit võimatu suurusega 2²⁰⁴⁸ tükid…

…või peaksite kasutama täiesti uut tüüpi postkvant-krüpteerimissüsteemi, millele Shori algoritm ei kehtinud.

Noh, USA standardiorganisatsioon NIST on töötanud a PQC "võistlus" alates 2017. aasta lõpust.

Protsess on olnud avatud kõigile, kõik osalejad on teretulnud, kõik algoritmid on avalikult avaldatud ja avalik kontroll pole mitte ainult võimalik, vaid aktiivselt julgustada:

Konkursikutse. [Suletud 2017]. […] Uued avaliku võtmega krüptograafiastandardid määravad kindlaks ühe või mitu täiendavat salastamata, avalikult avaldatavat digitaalallkirja, avaliku võtmega krüptimist ja võtme kehtestamise algoritmi, mis on saadaval kogu maailmas ja mis on võimelised kaitsma tundlikku valitsusteavet. juba lähitulevikus, sealhulgas pärast kvantarvutite tulekut.

Pärast kolme vooru esitamist ja arutelusid NIST teatas, 2022-07-05, et ta oli valinud neli algoritmi, mida pidas koheselt „standarditeks” ja millel kõigil on meeldivalt kõlavad nimed: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONja SPHINCS+.

Esimene (CRYSTALS-KYBER) kasutatakse nn a Peamine kokkuleppe mehhanism (KEM), kus avaliku sidekanali kaks otsa loovad turvaliselt ühekordse privaatse krüpteerimisvõtme seansi andmete konfidentsiaalseks vahetamiseks. (Lihtsamalt öeldes: nuhkijad saavad lihtsalt hakitud kapsast, nii et nad ei saa vestlust pealt kuulata.)

Ülejäänud kolme algoritmi kasutatakse Digitaalallkirjad, millega saate tagada, et teie lõpust saadud andmed vastavad täpselt sellele, mida saatja teisele sisestas, vältides sellega rikkumist ja tagades terviklikkuse. (Lihtsamalt öeldes: kui keegi üritab andmeid rikkuda või segada, siis saate teada.)

Vaja on rohkem algoritme

Uute standardite väljakuulutamisega samal ajal teatas NIST ka a neljas ring pakkudes välja veel neli algoritmi kui võimalikud alternatiivsed KEM-id. (Pidage meeles, et selle artikli kirjutamise ajal on meil juba valida kolme heakskiidetud digitaalallkirja algoritmi vahel, kuid ainult üks ametlik KEM.)

Need olid: BIKE, Classic McEliece, HQC ja SIKE.

Huvitaval kombel on McEliece'i algoritm leiutas 1970. aastatel Ameerika krüptograaf Robert Mc Eliece, kes suri 2019. aastal, palju pärast seda, kui NIST-i võistlus oli juba käimas.

See ei saanud aga kunagi kätte, sest see nõudis tohutul hulgal võtmematerjali võrreldes tolleaegse populaarse alternatiiviga Diffie-Hellman-Merkle algoritmiga (DHM või mõnikord lihtsalt DH).

Kahjuks üks kolmest Round Four algoritmist, nimelt SIKE, näib olevat mõranenud.

Aju keeravas artiklis pealkirjaga EFEKTIIVNE VÕTME TAASTAMISE RÜND SIDH-LE (ESIAALNE VERSION)Belgia krüptograafid Wouter Castryk ja Thomas Decru näivad olevat andnud SIKE-algoritmile surmava hoobi.

Kui teil tekib küsimus, on SIKE lühend sõnadest Supersingular isogeny Key kapseldus, ja SIDH tähistab Supersingular Isogeny Diffie-Hellman, konkreetne kasutamine SIKE algoritm kusjuures sidekanali kaks otsa sooritavad DHM-i sarnase "krüptotantsu", et vahetada hunnikut avalikke andmeid, mis võimaldab mõlemal otsal saada privaatset väärtust, mida kasutada ühekordse salajase krüpteerimisvõtmena.

Me ei püüa siin rünnakut selgitada; kordame lihtsalt seda, mida paber väidab, nimelt seda:

Väga lõdvalt öeldes sisaldavad siinsed sisendid võtme loomise krüptotantsus ühe osaleja esitatud avalikke andmeid koos protsessis kasutatavate etteantud (ja seega avalikult tuntud) parameetritega.

Kuid ekstraheeritud väljund (teave, millele viidatakse kui isogeensus φ ülal) peaks olema protsessi kunagi avaldamata osa – nn privaatvõti.

Teisisõnu, ainuüksi avalikust teabest, näiteks võtme seadistamise ajal avalikult vahetatud andmetest, väidavad krüptograafid, et suudavad taastada ühe osaleja privaatvõtme.

Ja kui teate minu privaatvõtit, saate hõlpsalt ja tuvastamatult teeselda, et olen mina, nii et krüpteerimisprotsess katkeb.

Ilmselt kulub võtmemurdmise algoritmil oma töö tegemiseks aega umbes tund, kasutades vaid ühte CPU-tuuma sellise töötlemisvõimsusega nagu igapäevases sülearvutis.

See on vastuolus SIKE-algoritmiga, kui see on konfigureeritud vastama 1. tasemele, NIST-i põhilisele krüpteerimisturvalisusele.

Mida teha?

Midagi!

(See on hea uudis.)

Nagu artikli autorid soovitavad, pärast märkimist, et nende tulemus on veel esialgne, "Praeguse olukorra juures näib, et SIDH on kõigi avalikult loodud baaskõverate puhul täiesti katki."

(See on halb uudis.)

Arvestades aga, et SIKE algoritm pole veel ametlikult heaks kiidetud, saab seda nüüd kohandada selle konkreetse rünnaku nurjamiseks (miski, mida autorid tunnistavad, et see võib olla võimalik) või lihtsalt loobuda.

Mis iganes lõpuks SIKE-ga juhtub, on see suurepärane meeldetuletus sellest, miks on oma krüpteerimisalgoritmide leiutamine ohtlik.

See on ka hea näide selle kohta, miks patenteeritud krüptimissüsteemid mis tuginevad algoritmi enda saladusele nende turvalisuse säilitamine on 2022. aastal lihtsalt vastuvõetamatu.

Kui PQC-algoritm, nagu SIKE, elaks üle maailma ekspertide poolt veendunult ja sondeerituna üle viie aasta, hoolimata sellest, et see avalikustati spetsiaalselt selleks, et seda saaks avalikkusele kontrollida ...

…siis pole vaja endalt küsida, kui hästi teie kodus valmistatud, vaate eest varjatud krüpteerimisalgoritmidel tõenäoliselt läheb, kui need loodusesse lastakse!

---