Svet kvantnega računalništva

NIST standardizacija algoritmov PQC

V enem od prejšnjih blogov in na nedavnem PQC (post-quantum cryptography) webinarju smo pisali o ranljivostih kriptografije javnih ključev (PKI) na kvantne napade, še posebej na napade, ki uporabljajo Shorjev algoritem.

Trenutno so standardi algoritmov kriptografije javnih ključev opisani v vrsti publikacij NIST [1,2,3]. Pričakovano pa je, da se bo kmalu začel prehod na nov razred kvantno odpornih algoritmov. Da bi prehod potekal tekoče in da bi algoritmi izpolnjevali najvišje varnostne zahteve, je treba določiti standarde. Tako je konec leta 2016 NIST objavil javni poziv za oddajo PQC predlogov.

November 2017 je bil zadnji rok za oddajo predlogov algoritmov. Od 82 prijavljenih kandidatov jih je bilo 13 skoraj takoj zlomljenih ali pa so bile najdene očitne pomanjkljivosti. Tako je bilo decembra 2017 v prvi izbirni krog sprejetih 69 kandidatov. Nekaj ​​mesecev za tem, aprila 2018, je potekala 1. NIST konferenca o standardizaciji PQC, na kateri so raziskovalci tako iz NIST organizacije, kot širšega akademskega kroga razpravljali o algoritmih in potencialnih napadih nanje. V začetku leta 2019 je bilo v 2. krogu izbranih 26 kandidatov, kateremu je sledila 2. NIST konferenca o standardizaciji PQC, ki je potekala poleti istega leta. Končno so 22. julija letos razglasili sedem finalistov 3. kroga. NIST je objavil tudi javno poročilo o izbirnem postopku.

Sedem izbranih algoritmov

Oglejmo si finaliste. Delimo jih lahko glede na dve glavni merili. Kakšna je njihova uporaba? In na katerem matematičnem problemu temeljijo?

Algoritmi, ki so v postopku izbire NIST standardizacije, naj bi nadomestili sedanje algoritme asimetrične kriptografije. Toda za razliko od RSA ali ECC algoritmov, ki jih uporabljamo za številne namene, so algoritmi PQC bolj specifični. Zato je prva delitev odvisna od njihove uporabe: uporabljajo se bodisi za šifriranje z javnimi ključi/KEM (mehanizem za enkapsulacijo ključev), bodisi za ustvarjanje digitalnih podpisov, ne pa za oboje. Od skupno sedmih algoritmov so štirje namenjeni šifriranju z javnim ključem in trije ustvarjanju digitalnih podpisov.

Druga delitev temelji na matematičnem problemu, na katerem algoritmi temeljijo. Varnost RSA algoritma temelji na problemu faktorizacije celih števil na prafaktorje. Varnost ECC algoritma temelji na problemu diskretnega logaritma. Ker pa Shorjev algoritem zlomi oba problema, je potrebno za PQC algoritme uporabiti povsem nove razrede problemov. Večina predlogov temelji na shemi strukturiranih mrež (structured lattice scheme) (CRYSTALS-KYBER, CRYSTALS-DILITHIUM, NTRU, SABER, FALCON), eden na multivariabilnih problemih (Rainbow) in eden na kodirnem problemu (Classic McEliece).
PQC algos

Dodatna razlika med predlaganimi PQC algoritmi in tistimi, ki jih uporabljamo danes, je razlika v dolžini podpisa in velikosti javnega ključa. Na zgornji tabeli lahko vidimo, kje so na grafikonu postavljeni RSA in ECC v primerjavi z novimi algoritmi. Naj poudarimo, da je merilo eksponentno. Vidimo lahko, da bodo imeli algoritmi, ki jih bomo uporabljali v prihodnosti, bistveno večjo velikost podpisa (algoritmi, ki temeljijo na razpršilnih funkcijah), večjo dolžino javnega ključa (večina algoritmov, ki temeljijo na multivariabilnih funkcijah), ali pa bodo nekje na sredini (na osnovi strukturirane mreže).

Alternativni kandidati in načrti za prihodnost

Poleg sedmih finalistov je NIST za 3. krog izbral tudi osem alternativnih kandidatov. Ti algoritmi zagotovo ne bodo standardizirani s koncem naslednjega kroga, vendar NIST dopušča možnost, da lahko z dodatnimi modifikacijami vstopijo v potencialni 4. krog. Nato lahko tisti z dovolj dobro zmogljivostjo in dokazano odpornostjo na kriptanalizo še vedno postanejo standardizirani.

Prvotni NISTovi načrti so vključevali gostovanje 3. NIST konference o standardizaciji PQC pomladi ali poleti 2021. Kako bo pandemija COVID-19 vplivala na te načrte, bomo še videli. Pričakuje se, da bo do začetka leta 2022 majhno število algoritmov že izbrano za standardizacijo. Tako bo po poročanju NISTa tretji krog služil kot zadnji krog prve faze standardizacije.


[1] FIPS 186-4, Digital Signature Standard (DSS) 
https://csrc.nist.gov/publications/detail/fips/186/4/final

[2] SP 800-56A Rev. 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography
https://csrc.nist.gov/publications/detail/sp/800-56a/rev-3/final

[3] SP 800-56B Rev. 2, Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography
https://csrc.nist.gov/publications/detail/sp/800-56b/rev-2/final

----

Pripravila: dr. Nastja Cepak, kriptografinja / CREAplus 

Novice

Spletni seminar: Izsiljevalska programska oprema

CynetUdeležite se spletnega seminarja proizvajalca Cynet Security na temo novih platform XDR in zaščite pred izsiljevalskimi virusi (ransomware).

Več

Utimaco HSM MS CA video vodnik za integracijo

Utimaco video IG 4CREAplus je pripravila kratek video vodnik za predstavitev integracije strojnega varnostnega modula (HSM) Utimaco z Microsoft AD CS.

Več

Spletni seminar: Konsolidacija varnostnih rešitev v podjetju

CynetUdeležite se spletnega seminarja proizvajalca Cynet Security na temo konsolidacije varnostnih rešitev v manjših in srednje velikih podjetjih (MSP).

Več

Utimaco na konferenci RISK 2020

Utimaco presentation RISK 2020Podjetje Utimaco bo prisotno tudi na konferenci RISK 2020 s predavanjem "Trust the NEXT Digital Era".

Več

Predavanje o post-kvantni kriptografiji za ZIT

Technical Training Utimaco HSM BG May 2019 20190613 101217 smlPodjetje CREAplus je 6.11.2020 uspešno izvedlo spletno predavanje z naslovom "Spoznajte post-kvatno kriptografijo (PQC) - Kvantno računalništvo in kriptografija". 

Več