PROJEKT R

2021/22

slika

Pobjednici natječaja CAESAR

KEYAK

Autorica teksta: I. Dasović

Specifikacija algoritma
Broj rundi n_r [bytes] 12
Kapacitet c [bytes] 256
Veličina oznake T τ [bytes] 128


W (jedinica poravnavanja)[bytes] l (key pack) [bytes]
RIVER KEYAK 32 36
LAKE KEYAK 64 40
SEA KEYAK 64 40
OCEAN KEYAK 64 40
LUNAR KEYAK 64 40

Veličina poruke i nonce (nuncij) varijabilne duljine
Enkriptiranje i dekriptiranje
KEYAK je familija algoritama koja se zasniva na Motorist autentificirajućem enkripcijskom modulu i KECCAK- p permutacijskim funkcijama. KECCAK- p permutacijske funkcije predstavljaju niz operacija koje su nastale iz KECCAK- f funkcija, a izvode se nad stanjem A. Širina permutacije iznosi b = 25 * 2l, broj rundi je nr te se stanje A tada prikazuje trodimenzionalnom matricom [5, 5, w] gdje je w = 2l. Svi blokovi A duljine su p bitova, osim posljednjeg koji može imati i manje bitova, ali ne smije biti prazan.

Motorist modul ima spužvastu konstrukciju i troslojnu arhitekturu. Svaki sloj Motorist modula zadužen je za osiguravanje različitih funkcionalnosti te kao ulaz prima niz bajtova. Piston je entitet najnižeg sloja, koristi funkciju za permutacije te tijekom operacija nad podacima ne radi razliku između ulančanih vrijednosti i meta podataka. Koristi offset s 4 fragmenta: EOM je fragment koji označava broj bajtova u sljedećem izlaznom bloku i odvaja poruke, Crypt End fragment označava kraj fragmenta poruke u trenutnom ulaznom bloku, Inject Start fragment označava početak meta podataka u trenutnom ulaznom bloku (jednak je nuli ukoliko trenutni ulazni blok sadrži samo meta podatke) te Inject End kodira kraj meta podataka fragmenta u trenutnom ulaznom bloku.

Funkcija Piston.Crypt omogućuje enkripciju ili dekripciju, ovisno o oznaci decrypt koja označava koja se operacija treba izvest. Funkcija Piston.Inject ubacuje meta podatke iz ulaznog niza kodirajući pritom početak meta podataka s offsetom Inject Start i kraj meta podataka s offsetom Inject End te u konačnici ponovno postavi offsete u njihovo početno stanje. Funkcija Piston.Spark primjenjuje permutacije f na stanje, a poziva se iz roditeljskog objekta Engine, koji je objekt srednjeg sloja, ukoliko još uvijek postoji neobrađeni dio poruke ili meta podataka. Funkcija Piston.GetTag dodaje poruci oznaku T.

GetTag(T, l):
  assert (𝑙 ≤ 𝑅𝑠)
  T.put(state[i]) for 𝑖 ∈ {0, . . , 𝑙 − 1}
  Return
T- oznaka
l- bitovi stanja S
Rs- indeks kraja poruke


Pretpostavlja se da su ulazni niz poruka i meta podataka statični između inject funkcija i kriptiranja, tj. da nema nadopunjavanja poruka ili meta podataka. Engine je srednji sloj u ovoj arhitekturi. U ovom sloju ne održavaju se stanja već se oslanja na to da svaki Piston objekt održava stanja i offsete.

Engine sloj ima 4 funkcije iz kojih pozivaju funkcije Piston objekata od kojih svaki obrađuje fragment ulazne poruke. Funkcija Engine.Spark poziva funkciju Piston.spark za svaki Piston objekt. Funkcija Engine.Wrap šalje ulazni niz Piston objektima te poziva Piston.Crypt nad svim Piston objektima te u izlazni stream O sprema odgovarajuće izlazne nizove. Funkcija Engine.InjectCollective(X, diversifyFlag) ubacuje iste meta podatke svim Piston objektima pozivajući Piston.Inject funkciju te se koristi za ubacivanje SUV (secret and unique value) i ulančanih vrijednosti. Ako je diversifyFlag = true, u meta podatke ubacuju se 2 bita: jedan koji enkodira stupanj paralelizma za separaciju domene između instanci s različitim brojem Piston objekata a drugi za enkodiranje indeksa Piston objekta za separaciju među Piston objektima i za izbjegavanje korištenja identičnog ključa. Funkcija Engine.getTag(T, l) poziva Piston.Spark nad svakim Piston objektom te skuplja odgovarajuće oznake u izlazni niz T pozivajući funkciju Piston.GetTag

GetTags(T, l):
  assert (if endOfMessage)
  Spark(true, l)
  Pistons[i].GetTag(T, 𝑙[𝑖]) for 𝑖 ∈ {0, . . ,Π− 1}
  Return
T- oznaka
l- bitovi stanja S
i- indeks piston objekta, 𝑖 ∈ {0, . . ,Π− 1}


Parametar l je zapravo vektor što omogućuje uzimanje različitog broja bitova za svaki Piston objekt. Proces završava pozivanjem funkcije Piston.Spark ili Piston.GetTag koje se mogu pozivati jedna za drugom ili paralelno. Funkcije Piston.Crypt i Piston.Inject također se mogu pozivati jedna za drugom ili paralelno. Motorist je najviši sloj u ovoj arhitekturi te on implementira korisničko sučelje. Motorist kontrolira Engine objekte te poziva parametrizirane Piston objekte. Sam Motorist parametriziran je jedinicom poravnavanja W što omogućuje da su fragment start offsets i duljina oznaka T, ulančane vrijednosti i fragmenti višekratnici W dopustajući manipuliranje podacima u višebajtnim komadima. Stanja se odražavaju atributom phase koji može biti: Ready- Motorist objekt je inicijaliziran i još uvijek nema ulaznih podataka, Riding- Motorist objekt je procesuirao SUV i u stanju je zaprakirati/ otpakirati podatke i Failed- Motorist objekt je primio neispravnu oznaku T. Sesija započinje pozivom funkcije Motorist.StartEngine kada je Motorist objekt u stanju ready te se koliko god je puta to potrebno poziva Motorist.Wrap funkcija. Funkcija Motorist.StartEngine(SUV, tagFlag, T, decryptFlag) započinje sesiju čitanjem SUV iz ulaznog niza. Zastavica forgetFlag označuje je li čvor (knot) potreban ili ne, ukoliko je zastavica decryptFlag postavljena na 0 vraća se oznaka T a u protivnom se verificira oznaka T i ako je verifikacija oznake T bila uspješna prelazi se u stanje riding. Funkcija Motorist.MakeKnot omogućuje da stanja Piston objekata međusobno ovise te se poziva samo u slučaju kada je to potrebno.
sbox
Slika prikazuje čvor. U ovom slučaju međusobno ovise stanja 4 Piston objekta. Svaka linija prikazuje stanje Piston objekta. Ulančane vrijednosti iz svih Piston objekata zajedno su ubačene u svaki Piston objekt.


U stanju riding poziva se i funkcija Motorist.Wrap(I, O, A, decryptFlag, forgetFlag) kojom se kriptogram zapakirava kada je decryptFlag = 0 pri čemu I predstavlja ulaznu poruku, a O izlaznu enkriptiranu poruku ili otpakirava kada je decryptFlage = 1 pri čemu je I ulazni niz koji predstavlja enkriptiranu poruku, a O izlazni niz koji sadrži dekriptiranu poruku ukoliko je oznaka T ispravna. Obje strane koje komuniciraju moraju sinkronizirati vrijednosti parametara tagFlag i forgetFlag.
Obilježja
KEYAK je familija parametriziranih algoritama za autentificiranu enkripciju. Svi algoritmi koriste KECCAK- p permutacije i imaju Motorist modul sa spužvastom konstrukcijom. Paket ključa koristi jednostavan padding te se sastoji od 3 dijela: prvi bajt koji označava duljinu ključa u bajtovima, ključa te jednostavnog paddinga. Keyak algoritmi imaju unificirani način enkodiranja tajnog ključa kao prefiks od SUV-a.Instanca Keyak objekta definira se:
Keyak [b, n_r, П, c, τ] = Motorist [ Keccakp [b, nr], П, W, c, τ] gdje je: W = max(b/25, 8)

KEYAK algoritmi podupiru sesije u kojima se autentificira cijeli niz poruke te obzirom na to da su sesije podržane smanjuje se potreba za nonceom. Sigurnost algoritma se bazira na tajnosti unutarnjih stanja Piston objekata čime se sprječavaju tzv. side channel napadi. Korištenje rundi i KECCAK- p funkcija također štiti od side channel napada jer se lako mogu implementirati u stvarnom vremenu. Mehanizam „zaboravljanja“ u entitetu Motorist osigurava tajnost podataka jer iako bi se napadom moglo saznati stanje objekta, ne može se nikako znati stanje prije što bi bilo ključno za otkrivanje podataka. Unatoč zlouporabe noncea, autentifikacija je osigurana te je šteta privatnosti limitirana. Omogućene su paralelna enkripcija ili dekripcija paralelnim korištenjem različitih Piston objekata.

Postoji 5 instanci Keyak familije algoritama:

NAZIV b Broj paralelnih Piston objekata
RIVER KEYAK 800 1
LAKE KEYAK 1600 1
SEA KEYAK 1600 2
OCEAN KEYAK 1600 4
LUNAR KEYAK 1600 8


KEYAK algoritmi podupiru sesije u kojima se autentificira cijeli niz poruke te obzirom na to da su sesije podržane smanjuje se potreba za nonceom. Sigurnost algoritma se bazira na tajnosti unutarnjih stanja Piston objekata čime se sprječavaju tzv. side channel napadi. Korištenje rundi i KECCAK- p funkcija također štiti od side channel napada jer se lako mogu implementirati u stvarnom vremenu. Mehanizam „zaboravljanja“ u entitetu Motorist osigurava tajnost podataka jer iako bi se napadom moglo saznati stanje objekta, ne može se nikako znati stanje prije što bi bilo ključno za otkrivanje podataka. Unatoč zlouporabe noncea, autentifikacija je osigurana te je šteta privatnosti limitirana. Omogućene su paralelna enkripcija ili dekripcija paralelnim korištenjem različitih Piston objekata.
sbox
Slika prikazuje sesiju u Motorist modu. Sesija započinje danom SUV, a zatim se procesuiraju poruka P1 i meta podaci A1 paralelno. Poruka je enkriptirana u C1, a T1 autentificira SUV, P1 i A1. Nakon procesuiranja sljedeće poruke T2 autentificira SUV, P1, A1, P2 i A2 te nakon procesuiranja treće poruke T3 autentificira cijeli sesiju, tj. SUV, P1, A1, P2, A2, P3 i A3 pri čemu je u ovom slučaju P3 prazna poruka.


KEYAK algoritmi pružaju bolje hardware performanse u usporedbi s drugim algoritmima poput AES- GCM.
Uporaba
KEYAK algoritmi pogodni su za autentificiranu enkripciju niza poruka. Same poruke često se prirodno grupiraju u sesiju primjerice na internetskoj vezi, prilikom transakcije pomoću pametnih kartica ili u razgovoru u nekoj aplikaciji stoga je praktično kriptirati te poruke upravo jednim od KEYAK algoritama. Motorist modul implementiran u KEYAK algoritmima može se koristiti za sigurnu dvosmjernu komunikaciju, ali mora se znati tko je pošiljatelj svake poruke što se može jednostavno ostvariti stavljanjem pošiljateljskog jedinstvenog identifikacijskog broja u meta podatke. KEYAK algoritmi dizajnirani su za uređaje s visokim performansama.