Criptografia post-cuantică – un nou algoritm „dispus în 60 de minute”

Am scris despre PQC, prescurtare pentru criptografia post-cuantică, de mai multe ori înainte.

În cazul în care ați ratat toată entuziasmul media din ultimii câțiva ani despre așa-numitul calcul cuantic...

... este (dacă veți scuza ceea ce unii experți probabil vor considera o simplificare excesivă nesăbuită) o modalitate de a construi dispozitive de calcul care pot ține evidența multiple rezultate posibile a unui calcul în acelaşi timp.

Cu multă grijă și poate cu puțin noroc, acest lucru înseamnă că puteți rescrie unele tipuri de algoritm pentru a găsi răspunsul corect sau cel puțin să renunțați corect la o mulțime de răspunsuri greșite, fără a încerca și a testa fiecare rezultat posibil. unul câte unul.

Două accelerări criptoanalitice interesante sunt posibile folosind un dispozitiv de calcul cuantic, presupunând că poate fi construit unul adecvat puternic și de încredere:

• Algoritmul de căutare cuantică al lui Grover. De obicei, dacă doriți să căutați un set de răspunsuri ordonate aleatoriu pentru a vedea dacă al dvs. se află pe listă, vă așteptați să parcurgeți întreaga listă, în cel mai rău caz, înainte de a obține un răspuns definitiv. De exemplu, dacă doriți să găsiți cheia de decriptare AES pe 128 de biți pentru a decripta un document, va trebui să căutați în lista tuturor cheilor posibile, începând cu 000..001, ..2, ..3, și așa mai departe, până la FFF..FFF (valoarea de 16 octeți de FF), pentru a fi sigur că rezolvați problema. Cu alte cuvinte, trebuie să aveți buget pentru a încerca toate cele două¹²⁸ posibile chei înainte fie de a găsi cheia potrivită, fie de a determina că nu există una. Cu toate acestea, algoritmul lui Grover, având în vedere un computer cuantic suficient de mare și de puternic, pretinde că poate finaliza aceeași performanță cu rădăcină pătrată a efortului obișnuit, spargând astfel codul, în teorie, în doar 2⁶⁴ încearcă în schimb.
• Algoritmul de factorizare cuantică a lui Shor. Mai mulți algoritmi de criptare contemporani se bazează pe faptul că înmulțirea a două numere prime mari împreună se poate face rapid, în timp ce împărțirea produsului lor înapoi în cele două numere cu care ați început este cât se poate de bună. Pentru a înțelege acest lucru, încercați să înmulțiți 59×87 folosind creion și hârtie. Ar putea dura un minut sau cam asa ceva pentru a-l scoate (5133 este răspunsul), dar nu este atât de greu. Acum încearcă în alt mod. Împărțiți, să zicem, 4171 înapoi în cei doi factori ai săi. Mult mai greu! (Este 43×97.) Acum imaginați-vă că faceți asta cu un număr care are 600 de cifre. Vorbind în mod liber, ești blocat să încerci să împărțiți numărul de 600 de cifre la fiecare număr prim posibil de 300 de cifre până când ajungeți la jackpot sau descoperiți că nu există un răspuns. Cu toate acestea, algoritmul lui Shor promite să rezolve această problemă cu logaritm a efortului obişnuit. Astfel, factorizarea unui număr de 2048 de cifre binare ar trebui să dureze doar de două ori mai mult decât factorizarea unui număr de 1024 de biți, nu de două ori mai mult decât factorizarea unui număr de 2047 de biți, ceea ce reprezintă o accelerare uriașă.

Contracararea amenințării

Amenințarea din algoritmul lui Grover poate fi contracarată pur și simplu prin creșterea dimensiunii numerelor pe care le utilizați prin pătrarea lor, ceea ce înseamnă dublarea numărului de biți din hash-ul criptografic sau cheia de criptare simetrică. (Cu alte cuvinte, dacă credeți că SHA-256 este bine acum, folosirea SHA-512 ar oferi o alternativă rezistentă la PQC.)

Dar algoritmul lui Shor nu poate fi contracarat atât de ușor.

O cheie publică de 2048 de biți ar avea nevoie de mărirea ei exponențială, nu doar prin pătrat, astfel încât în ​​loc de o cheie de 2×2048=4096 de biți, fie ai avea nevoie de o nouă cheie cu dimensiunea imposibilă de 2.²⁰⁴⁸ bucăți…

…sau ar trebui să adoptați un tip complet nou de sistem de criptare post-cuantică căruia nu i se aplica algoritmul lui Shor.

Ei bine, organismul american de standarde NIST a condus un „Competiție” PQC de la sfârșitul anului 2017.

Procesul a fost deschis tuturor, toți participanții sunt bineveniți, toți algoritmii publicati în mod deschis și controlul public nu este doar posibil, ci încurajat activ:

Suna pentru propuneri. [Închis 2017-11-30]. […] Se intenționează ca noile standarde de criptare cu cheie publică să specifice unul sau mai mulți algoritmi suplimentari de semnătură digitală neclasificată, dezvăluite public, de criptare a cheii publice și de stabilire a cheilor, care sunt disponibili în întreaga lume și sunt capabili să protejeze informațiile guvernamentale sensibile. în viitorul apropiat, inclusiv după apariția computerelor cuantice.

După trei runde de depuneri și discuții, NIST a anunțat, pe 2022-07-05, că a ales patru algoritmi pe care i-a considerat „standarde” cu efect imediat, toți cu nume care sună încântător: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, și SPHINCS+.

Primul (CRYSTALS-KYBER) este folosit ca ceea ce se numește a Mecanism cheie de acord (KEM), în care două capete ale unui canal de comunicare public creează în siguranță o cheie de criptare privată unică pentru a schimba în mod confidențial valoarea unei sesiuni de date. (Pur și simplu pune: snoopers primesc doar varză mărunțită, așa că nu pot asculta conversația.)

Ceilalți trei algoritmi sunt folosiți pentru Semnături digitale, prin care vă puteți asigura că datele pe care le-ați scos la capăt se potrivesc exact cu ceea ce a introdus expeditorul la celălalt, prevenind astfel manipularea și asigurând integritatea. (Pur și simplu pune: dacă cineva încearcă să corupeze sau să se încurce cu datele, veți ști.)

Sunt necesari mai mulți algoritmi

Concomitent cu anunțarea noilor standarde, NIST a anunțat și a runda a patra a concurenței sale, propunând încă patru algoritmi ca posibile KEM alternative. (Rețineți că, la momentul scrierii, avem deja trei algoritmi de semnătură digitală aprobați din care să alegeți, dar doar un KEM oficial.)

Acestea erau: BIKE, Classic McEliece, HQC și SIKE.

În mod intrigant, cel Algoritmul McEliece a fost inventat în anii 1970 de către criptograful american Robert Mc Eliece, care a murit în 2019, mult după ce concursul NIST era deja în desfășurare.

Totuși, nu a prins niciodată, deoarece necesita cantități uriașe de material cheie în comparație cu alternativa populară a zilei, algoritmul Diffie-Hellman-Merkle (DHM, sau uneori doar DH).

Din nefericire, unul dintre cei trei algoritmi Runda Patru, și anume SIKE, pare să fi fost crăpat.

Într-o lucrare care răsucește creierul intitulată UN ATAC EFICIENT DE RECUPERARE CHEIE PE SIDH (VERSIUNEA PRELIMINARĂ), criptografii belgieni Wouter Castryk și Thomas Decru par să fi dat o lovitură mortală algoritmului SIKE

În cazul în care vă întrebați, SIKE este prescurtarea pentru Încapsularea cheii de izogenie supersingulară, iar SIDH înseamnă Izogenie supersingulară Diffie-Hellman, o utilizare specifică a Algoritmul SIKE prin care două capete ale unui canal de comunicație realizează o „criptodanță” asemănătoare DHM pentru a schimba o mulțime de date publice care permite fiecărui capăt să obțină o valoare privată pentru a fi folosită ca o cheie de criptare secretă unică.

Nu vom încerca să explicăm atacul aici; Vom repeta doar ceea ce susține lucrarea, și anume că:

Foarte vag, intrările aici includ datele publice furnizate de unul dintre participanții la criptodanceul instituției cheie, împreună cu parametrii predeterminați (și, prin urmare, cunoscuți public) utilizați în proces.

Dar rezultatul care este extras (informația denumită izogenia φ de mai sus) ar trebui să fie partea niciodată dezvăluită a procesului – așa-numita cheie privată.

Cu alte cuvinte, doar din informațiile publice, cum ar fi datele schimbate în mod deschis în timpul configurării cheii, criptografii pretind că pot recupera cheia privată a unuia dintre participanți.

Și odată ce îmi cunoașteți cheia privată, puteți pretinde ușor și nedetectabil că sunt eu, așa că procesul de criptare este întrerupt.

Aparent, algoritmul de spargere a tastelor durează aproximativ o oră pentru a-și face treaba, folosind doar un singur nucleu de procesor cu genul de putere de procesare pe care l-ai găsi într-un laptop de zi cu zi.

Acest lucru este împotriva algoritmului SIKE atunci când este configurat pentru a îndeplini Nivelul 1, gradul de bază de securitate de criptare al NIST.

Ce să fac?

Nimic!

(Aceasta este vestea bună.)

După cum sugerează autorii lucrării, după ce au remarcat că rezultatul lor este încă preliminar, „Cu starea actuală a lucrurilor, SIDH pare să fie complet ruptă pentru orice curbă de bază generată public.”

(Aceasta este vestea proastă.)

Cu toate acestea, având în vedere că algoritmul SIKE nu este încă aprobat oficial, acum poate fi fie adaptat pentru a contracara acest atac special (ceva ce autorii admit că ar putea fi posibil), fie pur și simplu renunțat cu totul.

Orice s-ar întâmpla în cele din urmă cu SIKE, acesta este un excelent reamintire a motivului pentru care încercarea de a vă inventa proprii algoritmi de criptare este plină de pericole.

Este, de asemenea, un exemplu clar de ce sisteme de criptare proprietare care se bazează pe secretul algoritmului însuși pentru a-și menține securitatea sunt pur și simplu inacceptabile în 2022.

Dacă un algoritm PQC, cum ar fi SIKE, a supraviețuit experților din întreaga lume mai mult de cinci ani, în ciuda faptului că a fost dezvăluit în mod special, astfel încât să poată fi supus controlului public...

…atunci nu este nevoie să vă întrebați cât de bine se vor descurca algoritmii dvs. de criptare de casă, ascunși din vedere, atunci când sunt eliberați în sălbăticie!

---