BIS - Simetrični kriptosistemi.

Kriptografija

  • Potiče od grčke reči kriptos što znači tajna.

  • Proučava tehnike korišćene za šifrovanje i zaštitu komunikacije.

  • Koristi se za zaštitu sledećih bezbednosnih ciljeva:

    • Poverljivost podataka

    • Integritet podataka

    • Autentičnost

    • Uračunljivost

Primeri korišćenja kriptografije

  • VPN (virtual private network)

  • E-komerc

  • Siguran prenos email-a

  • Sigurni web sajtovi

  • Sigurne sesije

  • Blockchain (kriptovalute)

Šifre i ključevi

Šifre

  • Predstavljaju skup pravila ili algoritam po kome se obavlja šifrovanje ili dešifrovanje neke poruke uz pomoć ključa.

  • Postoje stotine javno poznatih šifri, a ima i vlasničkih za posebne namene.

Ključevi

  • Simetrični: Isti ključ se koristi i za šifrovanje i za dešifrovanje.

  • Asimetrični: Koriste se različiti ključevi za šifrovanje i dešifrovanje.

  • Ključevi mogu biti i jednokratni (OTP – one time pad).

Podela kriptografije

Prema vrsti operacije koja se koristi za šifrovanje

  • Supstitucija (zamena)

  • Polialfabetik (zamena grupe slova drugom grupom)

  • Transpozicija (permutacija)

Prema broju upotrebljenih ključeva

  • Simetričan (jedan ključ-tajni)

  • Asimetričan (dva ključa – jedan javni, jedan privatni)

Prema načinu obrade otvorenog teksta

  • Blok šifra

  • Protočna šifra

Princip rada

  • Bezbedni kanal

  • Izvor ključa

  • Izvor poruke

  • Odrediste

  • Kryptanalitičar

Simetrični kriptosistemi

Princip simetričnog šifrovanja

  • Za simetrično šifrovanje neophodni su:

    • Otvoreni tekst

    • Algoritam šifrovanja

    • Tajni ključ

    • Šifrat

    • Algoritam dešifrovanja

Šifarski sistemi

  • Šifarski sistem tajnim ključem je familija parova funkcija za svaki ključ $k$ iz skupa ključeva $K$, definisana na sledeći način:

    • Ek:M<br>ightarrowXE_k: M <br>ightarrow X

    • Dk:X<br>ightarrowMD_k: X <br>ightarrow M

  • M i X su skupovi otvorenih tekstova i šifrata, respektivno.

  • Za svaki otvoreni tekst $m$ iz $M$ važi: D<em>k(E</em>k(m))=mD<em>k (E</em>k (m)) = m

  • Da bi se koristio ovakav sistem, korisnici A i B se dogovore da uzmu tajni ključ $k$ iz $K$. Ako A želi da pošalje poruku $m$ iz $M$ korisniku B, šifruje je pomoću funkcije $Ek$, i rezultat $c$ se šalje korisniku B. Da bi rekonstruisao originalnu poruku, B dešifruje primljeni šifrat $c$ pomoću funkcije $Dk$: D<em>k(c)=D</em>k(Ek(m))=mD<em>k (c) = D</em>k (E_k (m)) = m

Problemi u kriptografiji sa tajnim ključevima

  • Distribucija ključeva: Dva korisnika moraju da izaberu tajni ključ pre početka komunikacije i da za njegovo prenošenje koriste siguran kanal. Ovakav siguran kanal nije uvek na raspolaganju.

  • Manipulacija ključevima: U mreži sa $n$ korisnika, svaki par korisnika mora da ima svoj sopstveni tajni ključ, što čini ukupno racn(n−1)2rac{n(n−1)}{2} ključeva za tu mrežu.

  • Nemogućnost realizacije procedure digitalnog potpisa: U šifarskim sistemima sa tajnim ključevima nema mogućnosti, u opštem slučaju, za digitalno potpisivanje poruka, tako da onaj koji prima poruku ne može da bude siguran da je onaj koji mu je poslao poruku zaista njen autor.

Kriptoanaliza

  • Proces otkrivanja otvorenog teksta ili ključa.

    • Klasična kriptoanaliza

    • Analiza učestanosti

    • Računanje podudaranja

    • Kasiski ispitivanje

    • Simetrična kriptoanaliza

    • Vrste napada:

      • Poznat otvoren tekst

      • Određeni (odabrani) otvoreni tekst

      • Samo šifrat

      • Odabrani šifrat

      • Skup izabranih ključeva

Simetrični algoritmi

  • Koriste isti tajni ključ i za šifrovanje i za dešifrovanje.

  • Podaci koji se prenose VPN-om šifruju se simetričnim algoritmom.

  • Simetrični algoritmi su mnogo brži i manje koriste procesor od asimetričnih algoritama.

  • Tipične dužine ključa su od 112 do 256 bita (duži ključ – veća sigurnost).

  • 128 bita je minimalna dužina ključa za koju se smatra da je šifrovanje prilično pouzdano.

Blok šifre i protočne šifre

  • Algoritmi za šifrovanje mogu obrađivati bite, bajtove ili blokove podataka.

  • Blok šifre koriste simetrični ključ i obrađuju grupe bita (blokove), generišući blokove šifrovanog teksta. Ako u poslednjem bloku nema dovoljno podataka, dodaje se tzv. padding.

  • Protočne šifre takođe koriste simetrični ključ (kao strim, npr. pseudoslučajni niz), ali obrađuju bit po bit, generišući šifrovani strim.

Simetrični blokovski algoritmi šifrovanja

  • DES

  • 3DES

  • AES

  • IDEA

  • RC2, RC4, RC5, RC6

  • Blowfish

DES – simetrični blok algoritam

  • Data Encryption Standard

  • Radi sa blokovima podataka od 64 bita i ključem od 56 bita.

    • Početni ključ – 16 podključeva.

  • Koristi Feistelove šifre.

  • Problem: distribucija tajnog ključa.

DES - šifrovanje

  • Blok običnog teksta $X$ se izloži inicijalnoj permutaciji $IP$.

  • Blok se deli na dve polovine (levi i desni blok), koje na kraju runde menjaju mesta.

  • U okviru jedne runde vrši se šifrovanje bloka običnog teksta pomoću jednog podključa.

  • Postupak se ponavlja 16 puta (ima 16 rundi) sa različitim podključevima.

  • Posle prolaska kroz 16 koraka ceo blok podataka se podvrgava inverznoj permutaciji i dobija se šifrovani blok podataka $Y$.

DES - i-ti korak u šifrovanju

  • L<em>i=R</em>i−1L<em>{i} = R</em>{i-1}

  • R{i} = L{i-1} igoplus f(R{i-1}, K{i})

Funkcija F(Ri-1, Ki)

  • Funkcija u osnovi vrši sabiranje po modulu 2.

  • Pre toga radi se linearna ekspanzija niza od 32 bita na 48, koliko ima i svaki podključ.

  • Nakon sabiranja vrši se nelinearna kompresija na 32 bita.

  • Na kraju vrši se permutacija izabrana tako da difuzija bita u bloku bude maksimalna.

Funkcija desne polovine niza i podključa

  • $X$: Ulazni blok od 32 bita

  • $E$: Ekspanzija od 32 do 48 bita

  • $K$: Ključ od 48 bita

  • Suma po modulu 2 bit za bit sa ključem (48 bita).

DES - dešifrovanje

  • Redosled procesiranja podključeva je obrnut: $i=16, 15, 14, \ldots, 1$.

  • R<em>i−1=L</em>iR<em>{i-1} = L</em>{i}

  • L{i-1} = R{i} igoplus f(L{i},K{i})

Osnovne osobine DES-a

  • Međusobna zavisnost simbola: Svaki bit šifrata je jedna složena funkcija svih bita i svih bita otvorenog teksta.

  • Promena ulaznih bita: Promena jednog bita poruke prouzrokuje promenu približno 50% bita bloka šifrata.

  • Promena bita ključa: Promena jednog bita ključa prouzrokuje promenu približno 50% bita bloka šifrata.

Nedostaci DES-a

  • Slabi ključevi: Postoje četiri slaba ključa koji omogućavaju lako dekriptovanje šifrovane poruke, zato što su u slučaju upotrebe tih ključeva svi podključevi $K1$ do $K{16}$ međusobno jednaki.

  • Postoji 28 “delimično slabih" ključeva koji omogućavaju lako dekriptovanje šifrovane poruke, zato što su u slučaju upotrebe tih ključeva samo dva ili četiri podključa međusobno različita.

  • Greška pri prenosu dela šifrata prostire se na ceo blok u kome je taj deo.

  • Dužina ključa od 56 bita je nedovoljna za trenutno stanje tehnologije.

  • Postoje specijalni napadi na blok šifre, kao što su linearna i diferencijalna kriptoanaliza.

3DES algoritam

  • 3DES algoritam radi sa trostrukim ključem ukupne dužine 168 bita (3 x 56 bita).

  • $K1$, $K2$, $K3$ – Tri različita početna ključa.

  • C=E<em>K3[D</em>K2[EK1(P)]]C = E<em>{K3}[D</em>{K2}[E_{K1}(P)]] - izraz za dobijanje šifrovanog teksta $C$.

  • P=D<em>K1[E</em>K2[DK3(C)]]P = D<em>{K1}[E</em>{K2}[D_{K3}(C)]] - izraz za dobijanje dešifrovanog teksta $P$.

  • Dešifrovanje u drugoj fazi 3DES šifrovanja omogućava kompatibilnost sa DES sistemima ($K1 = K2 = K3 = K$).

3DES - osobine

  • Dužina ključa od 168 bita efektivno onemogućava napade grubom silom.

  • Generalno otporan na kriptoanalitičke napade, ali je glavni nedostatak tromost algoritma u softverskoj varijanti (projektovan za implementaciju hardverom i ne daje efikasan softverski kod).

  • 3DES je tri puta sporiji od DES.

  • Poželjna je veća dužina bloka podataka (radi sa blokom od 64 bita) zbog efikasnosti i bezbednosti.

AES (Rijndael)

  • Zbog slabosti DES-a, u SAD su odlučili da ga zamene novom blok-šifrom, nazvanom AES (Advanced Encryption Standard).

  • Konačna verzija algoritma AES bila je izabrana između 5 kandidata – izabran je algoritam rijndael (2001).

Rijndael

  • Iterativna blok-šifra sa dužinom bloka od 128 bita.

  • Dužina ključa je promenljiva i može biti 128, 192 i 256 bita.

  • Osnovni element ove šifre se naziva Stanje (State), što je matrica sa 4 vrste i $Nb$ kolona, gde je $Nb$ jednako dužini bloka podeljenoj sa 32 (za blok od 128 bita $Nb=4$).

  • Ključ je takođe dat matricom sa 4 vrste i $Nk$ kolona, gde je $Nk$ jednako dužini ključa podeljenoj sa 32.

  • Broj rundi $Nr$ zavisi od vrednosti $Nb$ i $Nk$: $Nr$ uzima različite vrednosti u zavisnosti od dužine ključa: 128 - 10 rundi, 192 – 12 rundi i 256 – 14 rundi.

Transformacija u okviru jedne runde

Sastoji se od 4 koraka:

  1. Nelinearna supstitucija bajtova (ByteSub).

  2. Ciklični pomeraji u vrstama matrice State (ShiftRow).

  3. Množenje kolona matrice State fiksnim polinomom po modulu (MixColumn).

  4. Sabiranje ključa runde sa matricom State (RoundKey) - XOR.

  • Slabi, kao i delimično slabi ključevi ne mogu da se pojave kod Rijndael-a, pošto algoritmi šifrovanja i dešifrovanja koriste različite komponente.

  • Ova šifra je otporna na linearnu i diferencijalnu kriptoanalizu, kao i na neke druge publikovane napade na blok-šifre.

Područja primene blok šifara

  • Blok-šifre su pogodne za šifrovanje kratkih poruka – ključevi, identifikacioni podaci, potpisi, lozinke, itd.

  • Nisu pogodne za šifrovanje velikih količina podataka, kao što su formatirani tekstovi, listinzi programa, tabele i naročito grafičke datoteke, pošto se struktura takvih dokumenata lako određuje.

Načini rada blok šifara – kriptografski modovi rada

  • Elektronska kodna knjiga (Electronic Codebook, ECB)

  • Ulančavanje šifrovanih blokova (Cipher Block Chaining, CBC)

  • Šifrat u povratnoj sprezi (Cipher Feedback, CFB)

  • Izlazni niz u povratnoj sprezi (Output Feedback, OFB)

  • Brojački režim rada (Counter mod, CTR)

Elektronska kodna knjiga

  • Može se zamisliti džinovska knjiga šifara u kojoj za svaki uzorak otvorenog teksta postoji odgovarajući šifrat.

  • Isti blok otvorenog teksta daće uvek isti šifrat.

  • Ako poruka sadrži blokove koji se sukcesivno ponavljaju, to je moguće prepoznati pri kriptoanalizi.

Ulančavanje šifrovanih blokova

  • Ulaz algoritam šifrovanja je rezultat operacije XOR tekućeg bloka poruke (otvorenog teksta) i prethodnog bloka šifrata.

  • Za sve blokove koristi se isti ključ.

  • Na početku se u pomerački registar uvodi n bita inicijalnog vektora (IV), koji ne mora da se deži u tajnosti, ali je bitno da se generiše na slučajan način.

  • Jednake poruke se šifruju na različite načine promenom sadržaja registra u povratnoj sprezi.

Šifrat u povratnoj sprezi

  • Na početku se u pomerački registar uvodi n bita inicijalnog vektora (IV) koji ne mora da se drži u tajnosti, ali je pogodno da se generiše na slučajan način.

  • Otvoreni tekst se deli na blokove od po $m$ bita. Blokovi se sabiraju po modulu 2, bit za bit, gde $m$ može da varira između 1 i n.

  • Pomerački registar dužine n bita se pomera ulevo $m$ bita posle šifrovanja svakog bloka.

  • U ovom načinu rada blok-šifra se pretvara u sekvencijalnu šifru, jednake poruke se mogu šifrovati na različite načine promenom vektora IV, ograničava se propagacija grešaka u prenosu.

Brojački režim rada

  • Koristi se brojač jednak veličini bloka poruke.

  • Vrednost brojača mora da bude različita za svaki blok poruke.

  • Nema ulančavanja i može se raditi paralelno na više blokova.

  • Sadržaj brojača se šifruje ključem, pa se na šifrovan sadržaj i blok poruke primeni XOR.

Sekvencijalni šifarski sistemi

  • Poseduju generatore pseudoslučajnih brojeva – deterministički algoritmi, ili nizovi simbola koje oni generišu imaju slične osobine kao i slučajni nizovi.

  • Koriste kratke ključeve radi započinjanja procesa generisanja.

  • Izlazni niz generatora se sabira po modulu 2 sa nizom otvorenog teksta i na taj način se dobija niz šifrata.

Zahtevi koje svaki šifarski niz mora da zadovolji

  • Period šifarskog niza mora da bude bar jednake dužine kao i dužina niza koji se šifruje.

  • U praksi, generišu se nizovi čiji je period mnogo redova veličine veći od dužine niza koji se šifruje.

Primer sekvencijalnog algoritma: RC4

  • RC4 algoritam koristi tablicu S-box dužine 256 bajtova.

  • Za generisanje slučajnog broja $K$ treba uraditi sledeće:

    • $i=0$, $j=0$

    • $i=(i+1) ext{mod} 256$

    • $j=(j+S_i) ext{mod} 256$

    • $Si$ i $Sj$ zamene mesta.

    • $K=S_t$.

  • Dobijeni bajt $K$ se koristi za XOR-ovanje sa otvorenim tekstom za dobijanje šifrata.

RC4 – Inicijalizacija S-box

  • Inicijalizacija S-box je jednostavna. Prvo se linearno napuni tako da je: $S0=0, \ldots, S{255}=255$.

  • Zatim se generiše niz od 256 bajtova ključa (ponavljanjem).

  • Tada se S-box popunjava na sledeći način:

    • $j=0$;

    • Za $i=0$ do 255: $j=(j + Si + Ki) ext{mod} 256$; $Si$ i $Sj$ zamene mesta.