SOBER - 128

UVOD

SOBER-128 je simetrični algoritam za kriptiranje toka podataka predviđen za ključeve duljine do 128 bitova. Izlaz iz algoritma je keystream podijeljen u 32-bitne blokove. Algoritam se temelji na jednostavnim 32-bitnim operacijama kao što su 32-bitni XOR i zbrajanje po modulu 2**32. napravljen je tako da bude brz, lako razumljiv, dostupan i povrh svega siguran pa nije čudo da se može pronaći na mnogim mjestima - od pametnih kartica do složenijih računalnih sustava.

KRATKI POVIJESNI PREGLED

SOBER-128 je razvijen iz SOBER-a kojeg je 1998. godine predstavio Gregory G. Rose. Prva verzija SOBER-a se temeljila na 8-bitnim operacijama i ubrzo ju je, nakon što su pronađeni mnogi nedostaci, zamijenio SOBER-II. Tada se pojavio i S16 koji je po strukturi u potpunosti odgovarao SOBER-u II, no temeljio se na 16-bitnim operacijama. Daljnjim istraživanjima uočeno je da bi se SOBER II i S16 mogli unaprijediti pa su, zajedno s u međuvremenu napravljenom i 32-bitnom verzijom, zamijenjeni novom, takozvanom, t-klasom SOBER algoritama. U t-klasi pripadaju tri algoritma: SOBER-t8, SOBER-t16 kojemu je duljina ključa do 128 bita i SOBER-t32 s 256-bitnim ključem. SOBER-t16 i SOBER-t32 su prijavljeni NESSIE programu i, iako su bili među najjačim algoritmima za kriptiranje toka podataka, nijedan nije zadovoljio visoke zahtjeve programa. SOBER-128 je poboljšana verzija SOBERa-t32. Razlike se direktno odnose na osobitosti t-klase koje su se kroz analize ipak pokazale nezadovoljavajućima.

OPIS ALGORITMA

SOBER-128 se sastoji od linearnog posmičnog registra LFSR (linear feedback shift register), nelinearnog filtera NLF i nelinearne funkcije MFF (MAC feedback function) koja kao parametar koristi jasni tekst. Na slici 1 nalazi se grafički prikaz stvaranja keystreama, dok je na slici 2 prikazana MFF funkcija. Algoritam se bazira na 32-bitnim operacijama i 32-bitnim blokovima, pri čemu se svaki takav blok naziva riječ (word). LFSR generira niz riječi {s[t]} koristeći operacije nad Galiosovim poljem reda veličine 2**32 (GF(2**32)). Vektor St=(s[0],..,s[16]) naziva se stanje LFSR-a u vremenu t, a stanje S0=(s[0],..,s[16]) je definirano kao inicijalno stanje. Učitavanjem 128-bitnog ključa, LFSR se dovodi u key state, a i generira se 32-bitna, o ključu ovisna riječ, Konst. Pomoću NLF-a se zatim generira keystream, a MFF se koristi za modifikaciju LFSR-a kada se stara MAC (Message Authentication Code).

Kada dobijemo keystream (v(t)) kriptiranje se odvija tako da se obavi operacija XOR između bitova jasnog teksta i keystreama.

Naravno, vrijedi i obrat. Ako želimo dekriptirati kriptirani tekst, obavit ćemo operaciju xor između bitova kriptiranog teksta i bitova keystreama. Kao rezultat bismo trebali dobiti niz bitova jasnog teksta.

Postoje dva načina upotrebe SOBERa-128:

Moguće je koristiti MFF bez namjere generiranja MAC-a. To se, doduše, ne preporučuje jer se, gledajući duži vremenski period, smanjuje učinkovitost LFSR-a, a ne postiže se nikakva dobit. Umjesto toga, za unošenje posebnosti u procesuiranje svake poruke, trebao bi se koristiti nonce.

U slučaju da se u algoritmu obavlja i stvaranje koda za autentifikaciju poruke, u linearni posmični registar (LFSR) uvode se bitovi jasnog teksta koji su prije toga obrađeni na nelinearni način. Iako se, u ovom slučaju, linearni posmični registar više ne može smatrati linearnim, nastavit ćemo ga zvati LFSR.

SOBER-128 dopušta kriptiranje/dekriptiranje i autentifikaciju jasnog teksta bilo koje duljine, no većina operacija je strukturirana za obavljanje nad 32- bitnim blokovima. U slučaju da duljina (u bitovima) jasnog teksta nije djeljiva s 32, tada se prilagođava duljina keystreama, tj. zadnji bitovi keystreama se odbacuju.

LINEARNI POSMAČNI REGISTAR (LFSR)

Kod SOBERa-128 LFSR se sastoji od 17 32-bitnih riječi koje određuju njegovo trenutno stanje. Teorijski je osmišljen u tri koraka:

1. Kao karakterističan polinom izabran je p(X) = X**17 + X**15 + X**4 + a nad GF(2**32). Eksponenti 17, 15 i 4 su izabrani jer je ustanovljeno da pružaju najveću sigurnost.
2. Koeficijent a je definiran kao broj 0x00000100 iz razloga što olakšava programsku izradu algoritma. Množenje nekog broja s a se postiže uzimanjem već unaprijed izračunate konstante koja se nalazi u tablici i to s indeksom kojeg određuju najviše značajnih 8 bitova. Broj koji se množi se posmiče u lijevu stranu za 8 bitova i na kraju XOR-a s brojem uzetim iz tablice. Ovakav način množenja se koristi i kod algoritma SNOW, a i kod Turinga. U programskom jeziku C, novi element koji se umeće u LFSR se izračunava na ovaj način: novi = R[15] ^ R[4] ^ (R[0] << 8) ^ Multab[(R[0]>>24) & 0xFF];, pri čemu je ^ znak za operaciju XOR, << je posmak ulijevo, a znak >> simbolizira posmak udesno. Tablica Multab je priložena izvornom kodu.
3. LFSR se pomiče jednom prije stvaranja svake riječi keystreama i/ili prije akumulacije svake riječi prilikom izračunavanja MAC-a.

NELINEARNI FILTER (NFF)

NLF obuhvaća sljedeće operacije: XOR, zbrajanje po modulu 2*32, posmicanje i nelinearnu funkciju f koja koristi S kutiju (SBox).

NLF je definirana kao: v(t) = F(s[t], s[t+1], s[t+6], s[t+13], s[t+16], Konst) = f(((f(s[t] + s[t+16])>>>8 + s[t+1]) XOR Konst) + s[t+6]) + s[t+13], pri čemu je Konst konstanta koja nastaje prilikom inicijalizacije algoritma.

Za 32-bitnu vrijednost a, f(a) = SBox[aH] XOR a, pri čemu je aH 8 najviše značajnih bitova riječi a. Na slici 3 je grafički prikaz ostvarenja funkcije f.

S kutiju koju koristi SOBER-128 je kombinacija S kutija algoritma Skipjack i S kutija koje je napravio Informacijsko sigurnosni računalni centar (IRSC) pri Sveučilištu tehnologije u Queenslandu (QUD). IRSC-ova S kutija je napravljena kao 24-bitna međusobno nepovezana i posve nelinearna funkcija. Dakle, 8 najviše značajnih bitova rezultata funkcije f su zapravo izlaz iz S kutije algoritma Skipjack, dok su ostala 24 rezultat operacije XOR između izlaza IRSC-ove S kutije i 24 manje značajnih bitova ulaznog parametra funkcije.

Funkcija f je ostvarena na ovaj način da bi se postigla apsolutna nelinearnost uz upotrebu malene S kutije.

UČITAVANJE KLJUČA

Kod SOBERa-128 ključ se učitava na način tako da izravno utječe na stanje u linearnom posmičnom registru. Pritom se koriste dvije osnovne funkcije:

• Include(X): Ova funkcija zbraja po modulu 2**32 riječ X s R[15], pri čemu je R niz u kojem je spremljeno inicijalno stanje LFSR-a.
• Diffuse(): Nakon što obavi pomak LFSR-a, uzima izlaz iz NLF-a v i vrijednost R[4] zamjenjuje s (v XOR R[4])

Glavna funkcija koja obavlja učitavanje ključa je LoadKey(K[], keylen), pri čemu je K[] niz duljine keylen s elementima ključa. Ključ mora biti duljine koja je višekratnik broja 4, a pritom izražena u byte-ovima. Algoritam funkcije LoadKey(K[], keylen) je:

1. Neka je kwl = keylen/4. Ključ K[] treba prebaciti u niz Kw[] tako da niz Kw[] bude duljine kwl i sastavljen od riječi iz niza K[] po principu "big-endian".
2. Za svaki i, 0 ?i ?( kwl –1), treba izvršiti Include( kw [i] ) i Diffuse().
3. Include(keylen).
4. Izvršiti Diffuse() još 17 puta.

Treba primijetiti da iza svakog izvršavanja funkcije Include(X) treba provesti Diffuse(). U 4. koraku se Diffuse izvršava 17 puta zato da bi se osiguralo da svaki bit ulaznog niza utječe na stanja u LFSR-u na nelinearan način.

INICIJALIZACIJA ALGORITMA

Da bi se NLF funkcijom izgenerirao keystream i/ili stvorio MAC, algoritam je prvo potrebno dovesti u određeno stanje nazvano key state. To se obavlja sljedećim koracima:

1. Kao početno stanje LFSR-a uzima se prvih 17 Fibonaccijevih brojeva. Vrijednost R[0] i R[1] se stavljaju u 1, i dalje se računa R[i ] = R[i -1] + R[i -2] , za 2 ?i ?16. Vrijednost varijable Konst se definira kao 0x6996c53a (INITKONST).
2. Izvršava se funkcija Loadkey(K[], keylen) koja učitava oktete ključa i njegovu dužinu u registar te provodi informaciju kroz cijeli registar.
3. Pomiče se LFSR te se izračunava izlaz iz NLF-a i sprema u privremenu varijablu. To se ponavlja sve dok vrijednost privremene varijable ima najviše značajni oktet različit od nule. Tada se vrijednost varijable Konst postavlja na vrijednost privremene varijable.
4. Ako će se algoritam koristiti za više poruka, tada se R i Konst mogu u ovom trenutku sačuvati. Ovo stanje se naziva key state. Doduše, kod kraćih ključeva, moguće je sačuvati ključ i dosadašnji proces ponoviti za svaku poruku.
5. Ako algoritam ne koristi nikakve inicijalizacijske vektore niti nonce, keystream se dobiva iz ovog stanja. U suprotnom treba još provesti fukciju Loadkey(N[], Nlength), pri čemu je N[] niz kojeg sačinjavaju okteti noncea duljine Nlength.

AUTENTIFIKACIJSKI KOD PORUKE (MAC)

SOBER-128 računa MAC u dva koraka, akumulaciji i finalizaciji.

U fazi akumulacije, obavimo operaciju XOR nad kriptiranim tekstom i keystreamom te dobivenu vrijednost kombiniramo s LFSR-om na nelinearan način kao što je prikazano na slici 2:

s[t+4] = MFF(s[t+4], c(t) XOR v(t), Konst) = f((f(s[t+4] + (c(t) XOR v(t))) >>> 8) + Konst).

Važno je primijetiti da:

• svaki bit jasnog teksta p[i] koji se šalje kriptiran ulazi u MFF kao jasan tekst: c[i] ^ v[i] =p[i] ^ v [i] ^ v[i] = p[i]
• svaki bit jasnog teksta koji se šalje primatelju nekriptiran (c[i] = p[i]), kriptira se prije ulaska u MFF

U slučaju da je zadnji blok jasnog teksta (ili kriptirane poruke) kraći od 32 bita, c(t) ^ v(t) se nadopunjuje nulama prije ulaska u MFF. Broj nula se mora zapamtiti jer se koristi u finalizaciji.

Generalno govoreći, ako se poruka autentificira:

• Keystream se mora izgenerirati prije MAC akumulacije
• Sljedeća keystream riječ se ne može generirati prije nego se provede MAC akumulacija.

Nakon što se obavi akumulacija i kriptiranje cijele poruke, obavlja se finalizacija i to sljedećim algoritmom:

1. Include(INITKONST XOR broj_dodanih_nula)
2. Obavlja se Diffuse() 18 puta
3. Generira se proizvoljan broj riječi keystreama koje čine MAC

Broj dodanih nula se uključuje u finalizaciju zato da bi se onemogućilo mijenjanje tih nula s nekim drugim znakovima. Ponavljanje funkcije Diffuse() 18 puta osigurava da svako mijenjanje jasnog i kriptiranog teksta te keystreama u stanjima prije MAC finalizacije rezultira nepredvidljivim promjenama u konačnom MAC-u.

TESTNI PRIMJERI

Ako kao testni ključ uzmemo niz znakova: "ovo je testni kljuc!", a kao nonce 0x00 0x00 0x00 0x00, kao rezultat kriptiranja jasnog teksta "Veslonošci su vjerojatno najbrojnije životinje na Zemlji." bez stvaranja MAC-a dobivamo:

c[0]=0x4d c[1]=0x28 c[2]=0x9f c[3]=0xf c[4]=0x4b c[5]=0xc1 c[6]=0xf8 c[7]=0x20 c[8]=0x35 c[9]=0x30 c[10]=0xe6 c[11]=0x4 c[12]=0x0 c[13]=0xb7 c[14]=0xb c[15]=0xf c[16]=0x23 c[17]=0x80 c[18]=0x59 c[19]=0x2 c[20]=0x20 c[21]=0x91 c[22]=0xf3 c[23]=0xf7 c[24]=0xe9 c[25]=0xd c[26]=0x86 c[27]=0x6c c[28]=0x99 c[29]=0xe6 c[30]=0xd0 c[31]=0xec c[32]=0x26 c[33]=0x5a c[34]=0x91 c[35]=0x41 c[36]=0xf1 c[37]=0x41 c[38]=0x3a c[39]=0xda c[40]=0xa4 c[41]=0x30 c[42]=0x1a c[43]=0x43 c[44]=0xbe c[45]=0x7 c[46]=0xc0 c[47]=0x43 c[48]=0xde c[49]=0x15 c[50]=0x79 c[51]=0x6c c[52]=0x4e c[53]=0x44 c[54]=0xba c[55]=0xac c[56]=0x1c,

pri čemu je keystream jednak:

v[0]=0x1b v[1]=0x4d v[2]=0xec v[3]=0x63 v[4]=0x24 v[5]=0xaf v[6]=0x97 v[7]=0xba v[8]=0x56 v[9]=0x59 v[10]=0xc6 v[11]=0x77 v[12]=0x75 v[13]=0x97 v[14]=0x7d v[15]=0x65 v[16]=0x46 v[17]=0xf2 v[18]=0x36 v[19]=0x68 v[20]=0x41 v[21]=0xe5 v[22]=0x9d v[23]=0x98 v[24]=0xc9 v[25]=0x63 v[26]=0xe7 v[27]=0x6 v[28]=0xfb v[29]=0x94 v[30]=0xbf v[31]=0x86 v[32]=0x48 v[33]=0x33 v[34]=0xfb v[35]=0x24 v[36]=0xd1 v[37]=0xdf v[38]=0x53 v[39]=0xac v[40]=0xcb v[41]=0x44 v[42]=0x73 v[43]=0x2d v[44]=0xd4 v[45]=0x62 v[46]=0xe0 v[47]=0x2d v[48]=0xbf v[49]=0x35 v[50]=0x23 v[51]=0x9 v[52]=0x23 v[53]=0x28 v[54]=0xd0 v[55]=0xc5 v[56]=0x32.

U slučaju da kao testni ključ uzmemo niz znakova: "ovo je testni kljuc!", a kao nonce 0x00 0x00 0x00 0x00, kao rezultat kriptiranja jasnog teksta "Veslonošci su vjerojatno najbrojnije životinje na Zemlji." sa stvaranjem MAC-a od 20 riječi dobivamo:

c[0]=0x4d c[1]=0x28 c[2]=0x9f c[3]=0xf c[4]=0xd8 c[5]=0x47 c[6]=0xfd c[7]=0xdf c[8]=0xb9 c[9]=0xb1 c[10]=0xe0 c[11]=0xda c[12]=0x6a c[13]=0x8a c[14]=0xc0 c[15]=0xcf c[16]=0xf3 c[17]=0x2 c[18]=0xad c[19]=0x50 c[20]=0xa1 c[21]=0xf c[22]=0xa0 c[23]=0x2c c[24]=0xd6 c[25]=0xaa c[26]=0x78 c[27]=0x4a c[28]=0xd2 c[29]=0xdb c[30]=0xa6 c[31]=0x6 c[32]=0xa1 c[33]=0x1a c[34]=0x6e c[35]=0x4d c[36]=0xa7 c[37]=0xcd c[38]=0x62 c[39]=0xc0 c[40]=0xd1 c[41]=0x8c c[42]=0xbd c[43]=0x6 c[44]=0x54 c[45]=0xdc c[46]=0x62 c[47]=0xae c[48]=0x65 c[49]=0x0 c[50]=0x86 c[51]=0x63 c[52]=0x71 c[53]=0x70 c[54]=0xe9 c[55]=0x6e c[56]=0xb,

uz keystream:

v[0]=0x1b v[1]=0x4d v[2]=0xec v[3]=0x63 v[4]=0xb7 v[5]=0x29 v[6]=0x92 v[7]=0x45 v[8]=0xda v[9]=0xd8 v[10]=0xc0 v[11]=0xa9 v[12]=0x1f v[13]=0xaa v[14]=0xb6 v[15]=0xa5 v[16]=0x96 v[17]=0x70 v[18]=0xc2 v[19]=0x3a v[20]=0xc0 v[21]=0x7b v[22]=0xce v[23]=0x43 v[24]=0xf6 v[25]=0xc4 v[26]=0x19 v[27]=0x20 v[28]=0xb0 v[29]=0xa9 v[30]=0xc9 v[31]=0x6c v[32]=0xcf v[33]=0x73 v[34]=0x4 v[35]=0x28 v[36]=0x87 v[37]=0x53 v[38]=0xb v[39]=0xb6 v[40]=0xbe v[41]=0xf8 v[42]=0xd4 v[43]=0x68 v[44]=0x3e v[45]=0xb9 v[46]=0x42 v[47]=0xc0 v[48]=0x4 v[49]=0x20 v[50]=0xdc v[51]=0x6 v[52]=0x1c v[53]=0x1c v[54]=0x83 v[55]=0x7 v[56]=0x25

i MAC:

m[0]=0xdd m[1]=0x70 m[2]=0x15 m[3]=0x71 m[4]=0xa3 m[5]=0xda m[6]=0x22 m[7]=0xfe m[8]=0xa1 m[9]=0x5f m[10]=0xb6 m[11]=0x17 m[12]=0xf2 m[13]=0x63 m[14]=0x93 m[15]=0x8 m[16]=0x6b m[17]=0xbc m[18]=0xba m[19]=0x26 .

SIGURNOST

SOBER-128 pruža 128-bitnu sigurnost. Glavni napad na SOBER-128 je pronalazak ključa "grubom silom", tj. pretraživanje skupa svih mogućih rješenja. Kompleksnost takvog postupka je 2**128. U svim napadima se pretpostavlja da napadač ima određen broj keystreamova izvedenih iz jednog ili više ključeva te da ima pripadajući jasni tekst i nonce. Vjeruje se da SOBER-128 može izdržati napad kada on zahtjeva da vlasnik ključa generira više od 2**80 keystream riječi, ili kada napadač izvodi ponovno učitavanje ključa (rekey) 2**128 puta i pritom proizvede barem 5 izlaznih riječi. Proizvođači tvrde da SOBER-128 zadovoljava sigurnosne zahtjeve kada korisnik ne koristi isti ključ i nonce više od jednog puta i kada se s jednim ključem ne obradi više od 2**80 riječi.

LINKOVI

• Izvorni kod (zajedno s Multab.h i SBox.h)
• Izvršni kod
• originalna dokumentacija

Seminarski rad iz kolegija Operacijski sustavi 2 - SOBER-128 by Senka Drobac