Postkvanttisalaus – uusi algoritmi "meni 60 minuutissa"

Olemme kirjoittaneet PQC:stä, lyhenteestä postkvanttinen salaus, useita kertoja aiemmin.

Jos olet missannut kaiken viime vuosien median jännityksen niin sanotusta kvanttilaskennasta…

…se on (jos suokaa anteeksi, mitä jotkut asiantuntijat luultavasti pitävät holtittomana liiallisena yksinkertaistuksena) tapa rakentaa tietokonelaitteita, jotka voivat seurata useita mahdollisia tuloksia laskelmasta samanaikaisesti.

Suurella huolellisuudella ja ehkä hieman onnellakin tämä tarkoittaa, että voit kirjoittaa uudelleen tietyntyyppiset algoritmit oikean vastauksen mukaan tai ainakin hylätä oikein joukon vääriä vastauksia ilman, että yrität ja testaat kaikkia mahdollisia tuloksia. yksi kerrallaan.

Kaksi mielenkiintoista kryptanalyyttistä nopeutusta on mahdollista kvanttilaskentalaitteella, olettaen, että sopivan tehokas ja luotettava voidaan rakentaa:

• Groverin kvanttihakualgoritmi. Yleensä, jos haluat etsiä satunnaisesti järjestetyistä vastausjoukosta nähdäksesi, onko omasi luettelossa, odotat pahimmillaan käyvän läpi koko luettelon ennen kuin saat lopullisen vastauksen. Jos esimerkiksi haluat löytää 128-bittisen AES-salauksenpurkuavaimen asiakirjan salauksen purkamiseksi, sinun on etsittävä kaikkien mahdollisten avainten luettelosta alkaen 000..001, ..2, ..3, ja niin edelleen, aina asti FFF..FFF (16 tavua FF), varmistaaksesi, että ongelma saadaan päätökseen. Toisin sanoen sinun on varattava budjetti kokeillaksesi kaikkia kahta¹²⁸ mahdolliset avaimet ennen oikean avaimen löytämistä tai sen määrittämistä, ettei sitä ole. Groverin algoritmi väittää kuitenkin pystyvänsä suorittamaan saman saavutuksen, kun otetaan huomioon riittävän suuri ja tehokas kvanttitietokone. neliöjuuri tavanomaisesta vaivasta, mikä murtaa koodin teoriassa vain kahdessa⁶⁴ yrittää sen sijaan.
• Shorin kvanttifaktorointialgoritmi. Useat nykyaikaiset salausalgoritmit luottavat siihen tosiasiaan, että kahden suuren alkuluvun kertominen yhteen voidaan tehdä nopeasti, kun taas niiden tuotteen jakaminen takaisin kahdeksi luvuksi, joilla aloitit, on yhtä hyvin kuin mahdotonta. Saadaksesi tunteen tästä, kokeile kertoa 59 × 87 kynällä ja paperilla. Sen saaminen ulos voi kestää hetken (5133 on vastaus), mutta se ei ole niin vaikeaa. Kokeile nyt toisin. Jaa esimerkiksi 4171 takaisin kahteen tekijään. Paljon vaikeampaa! (Se on 43×97.) Kuvittele nyt tekeväsi tämän numerolla, joka on 600 numeroa pitkä. Löyhästi sanottuna olet jumissa yrittäessäsi jakaa 600-numeroisen luvun jokaisella mahdollisella 300-numeroisella alkuluvulla, kunnes saavutat jättipotin tai huomaat, että vastausta ei ole. Shorin algoritmi lupaa kuitenkin ratkaista tämän ongelman logaritmi tavanomaisesta vaivannäöstä. Täten 2048 binäärinumeron laskemisen pitäisi kestää vain kaksi kertaa niin kauan kuin 1024-bittisen luvun laskeminen, ei kaksi kertaa niin kauan kuin 2047-bittisen luvun laskeminen, mikä edustaa valtavaa nopeutta.

Uhkaa vastaan

Groverin algoritmin aiheuttamaa uhkaa voidaan torjua yksinkertaisesti lisäämällä käyttämiesi numeroiden kokoa neliöimällä ne, mikä tarkoittaa, että bittien määrä kaksinkertaistuu kryptografisessa tiivisteessäsi tai symmetrisessä salausavaimessasi. (Toisin sanoen, jos uskot, että SHA-256 on hyvä juuri nyt, SHA-512:n käyttäminen sen sijaan tarjoaisi PQC-kestävän vaihtoehdon.)

Mutta Shorin algoritmia ei voida torjua aivan niin helposti.

2048-bittisen julkisen avaimen kokoa olisi lisättävä eksponentiaalisesti, ei pelkästään neliöimällä, joten 2×2048=4096-bittisen avaimen sijasta tarvitsisit joko uuden avaimen, jonka koko on mahdoton.²⁰⁴⁸ bittiä…

…tai sinun on otettava käyttöön täysin uudenlainen post-kvanttisalausjärjestelmä, johon Shorin algoritmi ei soveltunut.

No, Yhdysvaltain standardointielin NIST on ajanut a PQC "kilpailu" vuoden 2017 lopusta lähtien.

Prosessi on ollut avoin kaikille, kaikki osallistujat ovat tervetulleita, kaikki algoritmit on julkaistu avoimesti ja julkinen valvonta ei ole pelkästään mahdollista, vaan kannustetaan aktiivisesti:

Pyydä ehdotuksia. [Suljettu 2017]. […] Tarkoituksena on, että uudet julkisen avaimen salausstandardit määrittelevät yhden tai useamman ylimääräisen luokittelemattoman, julkisesti julkistetun digitaalisen allekirjoituksen, julkisen avaimen salauksen ja avainten määrittämisalgoritmin, jotka ovat saatavilla maailmanlaajuisesti ja jotka pystyvät suojaamaan arkaluontoisia valtion tietoja. pitkälle lähitulevaisuudessa, myös kvanttitietokoneiden tulon jälkeen.

Kolmen esittelykierroksen ja keskustelujen jälkeen NIST ilmoitti, 2022-07-05, että se oli valinnut neljä algoritmia, joita se piti "standardeina", joilla on välitön vaikutus, ja kaikilla on ihastuttavalta kuulostavat nimet: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCONja SPHINCS+.

Ensimmäinen (CRYSTALS-KYBER) käytetään nimellä a Keskeinen sopimusmekanismi (KEM), jossa julkisen viestintäkanavan kaksi päätä muodostavat turvallisesti kertaluonteisen yksityisen salausavaimen istunnon arvoisen datan luottamuksellista vaihtamista varten. (Yksinkertaisesti sanottuna: nuuskijat saavat vain silputtua kaalia, joten he eivät voi salakuunnella keskustelua.)

Kolmea muuta algoritmia käytetään Digitaaliset allekirjoitukset, jonka avulla voit varmistaa, että saamasi tiedot vastaavat täsmälleen sitä, mitä lähettäjä on syöttänyt toiselle, estäen näin peukaloinnin ja varmistat eheyden. (Yksinkertaisesti sanottuna: Jos joku yrittää turmella tai sotkea tietoja, tiedät sen.)

Lisää algoritmeja tarvitaan

Samaan aikaan kun uudet standardit julkisti, NIST ilmoitti myös a neljäs kierros kilpailijoistaan ​​ja esittää neljä muuta algoritmia mahdollisina vaihtoehtoisina KEM:inä. (Muista, että tätä kirjoittaessamme meillä on jo kolme hyväksyttyä digitaalisen allekirjoitusalgoritmia, joista valita, mutta vain yksi virallinen KEM.)

Nämä olivat: BIKE, Classic McEliece, HQC ja SIKE.

Kiehtovaa, McEliece-algoritmi sen keksi 1970-luvulla amerikkalainen kryptografi Robert Mc Eliece, joka kuoli vuonna 2019, paljon sen jälkeen, kun NIST:n kilpailu oli jo käynnissä.

Se ei kuitenkaan koskaan tarttunut kiinni, koska se vaati valtavia määriä avainmateriaalia verrattuna päivän suosittuun vaihtoehtoon, Diffie-Hellman-Merkle-algoritmiin (DHM tai joskus vain DH).

Valitettavasti yksi kolmesta Round Four -algoritmista, nimittäin SIKE, näyttää olevan murtunut.

Aivoja kääntävässä paperissa, jonka otsikko on TEHOKAS AVAIMEN PALAUTUSHYÖKKY SIDH:hen (ALUSTAVA VERSIO)Belgialaiset kryptografit Wouter Castryk ja Thomas Decru näyttävät antaneen tappavan iskun SIKE-algoritmille

Jos mietit, SIKE on lyhenne sanoista Supersingular Isogeny Key -kapselointi, ja SIDH tarkoittaa Supersingulaarinen Isogeny Diffie-Hellman, tietty käyttö SIKE-algoritmi jossa viestintäkanavan kaksi päätä suorittavat DHM:n kaltaisen "cryptodancen" vaihtaakseen joukkoa julkista dataa, jonka avulla molemmat päät voivat johtaa yksityisen arvon käytettäväksi kertaluonteisena salaisena salausavaimena.

Emme aio yrittää selittää hyökkäystä tässä; Toistamme vain sen, mitä lehti väittää, nimittäin että:

Hyvin löyhästi sanottuna syötteet sisältävät yhden avaimenmuodostuksen kryptodanssin osallistujan toimittamat julkiset tiedot sekä prosessissa käytetyt ennalta määrätyt (ja siksi julkisesti tunnetut) parametrit.

Mutta poimittu tulos (tiedot, joihin viitataan nimellä isogenia φ yllä) oletetaan olevan prosessin koskaan paljastettu osa – niin kutsuttu yksityinen avain.

Toisin sanoen pelkästään julkisista tiedoista, kuten avaimen asennuksen aikana avoimesti vaihdetusta tiedosta, kryptografit väittävät pystyvänsä palauttamaan yhden osallistujan yksityisen avaimen.

Ja kun tiedät yksityisen avaimeni, voit helposti ja huomaamattomasti teeskennellä olevani minä, joten salausprosessi on rikki.

Ilmeisesti avainten krakkausalgoritmi kestää noin tunnin tehdä työnsä käyttämällä vain yhtä CPU-ydintä, jolla on sellainen prosessointiteho, joka löytyy jokapäiväisestä kannettavasta tietokoneesta.

Se on vastoin SIKE-algoritmia, kun se on määritetty täyttämään tason 1, NISTin perussalauksen suojausluokan.

Mitä tehdä?

Ei mitään!

(Se on hyvä uutinen.)

Kuten paperin kirjoittajat ehdottavat, todettuaan, että heidän tuloksensa on vielä alustava, "Nykyisellä tilanteella SIDH näyttää olevan täysin rikki kaikilla julkisesti luoduilla peruskäyrillä."

(Se on huono uutinen.)

Kuitenkin, jos SIKE-algoritmia ei ole vielä virallisesti hyväksytty, sitä voidaan nyt joko mukauttaa estämään tämä hyökkäys (jotain, jonka kirjoittajat myöntävät olevan mahdollista), tai yksinkertaisesti hylätä kokonaan.

Mitä ikinä SIKElle lopulta tapahtuu, tämä on erinomainen muistutus siitä, miksi omien salausalgoritmien keksiminen on täynnä vaaraa.

Se on myös terävä esimerkki siitä, miksi omat salausjärjestelmät jotka luottavat itse algoritmin salaisuuteen turvallisuuden säilyttäminen on yksinkertaisesti mahdotonta hyväksyä vuonna 2022.

Jos PQC-algoritmi, kuten SIKE, selviytyisi asiantuntijoiden ympäri maailmaa yli viiden vuoden ajan, vaikka se paljastettiin nimenomaan, jotta se voisi olla julkisen valvonnan alainen…

…niin ei tarvitse kysyä itseltäsi, kuinka hyvin kotitekoiset, näkyvistä piilossa olevat salausalgoritmit todennäköisesti pärjäävät, kun ne päästetään luontoon!

---