CRYSTALS-KYBER
Općenito
Kyber je skup algoritama za razmjenu ključeva čija se sigurnost postiže pomoću LWE (Learning with Errors) problema. Rješavanje LWE problema svodi se na rješavanje sustava jednadžbi, no ubačena pogreška pri generaciji čini cijeli problem iznimno teškim, čak i kvantnim računalima. Kyber se zapravo temelji na modularnom LWE problemu, a cijeli problem se može svesti na sljedeću jednadžbu:
B = As + e mod q
Problem leži u činjenici da ako poznajemo A i B iznimno je teško odrediti s. U izvedbi algoritma konkatenacija A i B su javni ključ, s je tajni ključ, e je ubačena greška, a q je neki dovoljno velik prost broj. U pravilu su sve navedene varijable vektori, no Kyber za A koristi matricu.
Drugi algoritmi i protokoli poput NewHopea i Frodoa koriste prstenastu LWE odnosno običnu LWE varijantu svaka od kojih ima svoje prednosti i mane. Prednosti prstenastog LWE-a su velika učinkovitost na području brzine i veličini ključeva i šifriranog teksta, a mane predstavljaju problem da povećavanjem algebarske strukture algoritma, cijeli mehanizam može postati ranjiviji na napade te problemi skalabilnosti između učinkovitosti i sigurnosti. Obična LWE varijanta ima prednost minimalne strukture koja omogućava jednostavnu skalabilnost, no uz cijenu smanjivanja cjelokupne učinkovitosti. Modularni LWE kojeg Kyber koristi se nalazi negdje između te dvije varijante; struktura je smanjena u odnosu na prstenasti LWE, ali je zato skalabilnost puno bolja, a performanse vrlo slične.
Kyber je također tzv. IND-CCA2 siguran. Značenje toga ćemo objasniti na primjeru.
- Pretpostavimo da napadač ima sposobnost kriptiranja i dekriptiranja proizvoljnih poruka, s tim porukama smije raditi koje god operacije želi u polinomnom vremenu
- Također pretpostavimo da imamo i žrtvu koja koristi IND-CCA2 siguran algoritam za kriptiranje poruka, te je njime generirao javni i tajni ključ
- Napadač zatim žrtvi pošalje dvije proizvoljne nekriptirane poruke
- Žrtva nasumično bira jednu od tih poruka i kriptira ju svojim tajnim ključem
- Napadač sada opet smije kriptirati i dekriptirati proizvoljne poruke (osim poruka koje je poslao žrtvi) i izvršavati proizvoljne operacije
- Napadač pogađa koju je poruku žrtva izabrala u koraku 4
Ukoliko napadač u prosjeku više puta netočno odgovori nego točno, algoritam je IND-CCA2 siguran. Bitno je spomenuti da su CCA sigurni algoritmi takozvano aktivno sigurni. Aktivna sigurnost podrazumijeva otpornost ne samo na pasivne napadače koji prisluškuju, nego i na aktivne koji se ubacuju u kanal komunikacije i pokušavaju mijenjati poruke. IND-CCA2 sigurnost osigurava da bilo koja promjena šifriranog teksta ne vodi predvidljivoj promjeni dekriptiranog teksta.
Svojstva
Pošto algoritam u mnogim svojim koracima koristi iznimno brzu varijantu diskretne Fourierove transformacije, ocjena performansi algoritma većinski ovisi o performansama korištenih kriptografskih primitiva. Svi kriptografski primitivi koje Kyber koristi dolaze iz Keccak obitelji algoritama. Iz tog razloga, algoritam je iznimno brz na računalima koja imaju sklopovsku podršku za izvedbe takvih kriptografskih funkcija.
Sigurnost
Kyber ima tri varijante, svaka od kojih predstavlja tri različite razine sigurnosti, a one su redom po jačini Kyber512, Kyber768 i Kyber1024. Kyber se može ‘pobjediti’ na dva načina: pronalazeći i iskorištavajući greške ili mane u temeljnim kriptografskim primitivima ili rješavajući modularni LWE problem. Oba slučaja su teška za izvesti.
| core-SVP (klasično) | core-SVP (kvantno) | Razina sigurnosti | |
|---|---|---|---|
| Kyber512 | 111 | 100 | 1 (AES-128) |
| Kyber768 | 181 | 164 | 3 (AES-192) |
| Kyber1024 | 254 | 230 | 5 (AES-256) |
Prednosti i mane
Teško je Kyberu pronaći manu, ali zato ima mnogo prednosti. Zbog korištenja brze Fourierove transformacije i brzih Keccak algoritama, performanse su mu izvrsne pri svakoj razini implementacije. Također, ne smijemo zaboraviti na IND-CCA2 svojstvo koje donosi još jednu dodatnu razinu sigurnosti. Uz sve to, algoritam je i vrlo skalabilan gdje povećanje razine sigurnosti zahtjeva samo promjenu dimenzija matrice.