Ovisi li sigurnost blokovskih šifri o višestrukom kombiniranju operacija zbunjenosti i difuzije?
Sigurnost blokovskih šifri u osnovi je ukorijenjena u iterativnoj primjeni operacija konfuzije i difuzije. Ovaj koncept prvi je formalizirao Claude Shannon u svom ključnom radu o komunikacijskoj teoriji tajnih sustava, gdje je artikulirao potrebu i za konfuzijom i za difuzijom u kriptografskim sustavima kako bi se spriječili statistički i strukturni napadi. Razumijevanje zašto su potrebni višestruki krugovi ovih operacija i kako su međusobno povezani ključno je za razumijevanje dizajna i sigurnosti modernih blokovskih šifri kao što su Standard šifriranja podataka (DES) i Napredni standard šifriranja (AES).
Zbunjenost i difuzija: definicije i uloge
Zbunjenost nastoji učiniti odnos između šifriranog teksta i ključa što složenijim. To čini maskiranjem statističke strukture otvorenog teksta, često korištenjem nelinearnih zamjena (npr. S-kutije u DES-u i AES-u). Što je ovo mapiranje nelinearnije i složenije, to je napadaču teže izvesti informacije o ključu, čak i ako ima pristup mnogim parovima otvorenog teksta i šifriranog teksta.
Difuzija, s druge strane, ima za cilj proširiti utjecaj svakog bita otvorenog teksta na mnoge bitove šifriranog teksta, tako da promjena jednog ulaznog bita rezultira promjenama mnogih izlaznih bitova. Ovo svojstvo osigurava da se statistička svojstva otvorenog teksta raspršuju kroz šifrirani tekst, što napadačima onemogućuje iskorištavanje obrazaca putem frekvencijske analize ili sličnih tehnika. Difuzija se obično postiže linearnim operacijama miješanja, kao što su permutacija, bitni XOR-ovi ili množenje matrica (kao u operaciji MixColumns u AES-u).
Struktura iterativnih blokovskih šifri
Većina blokovskih šifri strukturirana je kao iterirane šifre, što znači da više puta primjenjuju jednostavnu kružnu funkciju kako bi postigle visoku razinu sigurnosti. Kružna funkcija obično kombinira i konfuziju (npr. putem S-box aplikacija) i difuziju (npr. putem permutacije ili koraka miješanja). Razlog korištenja više rundi je taj što jedna primjena konfuzije i difuzije nije dovoljna da prikrije sve strukturne odnose između otvorenog teksta, šifriranog teksta i ključa. Svaka runda postupno povećava složenost tih odnosa i tek nakon nekoliko rundi šifra postiže željenu razinu sigurnosti od poznatih kriptoanalitičkih napada.
Na primjer, uzimajući u obzir AES šifru, svaka runda šifriranja sastoji se od sljedećih ključnih koraka:
1. Podbajtovi (Zbunjenost): Svaki bajt u matrici stanja zamjenjuje se drugim prema fiksnoj nelinearnoj S-kutiji, uvodeći nelinearnost.
2. ShiftRows (Difuzija): Redci matrice stanja se ciklički pomiču, premještajući bajtove u različite stupce i olakšavajući miješanje vrijednosti.
3. MixColumns (Difuzija): Stupci stanja se miješaju množenjem matrica u konačnom polju, dodatno šireći utjecaj svakog ulaznog bajta.
4. AddRoundKey (Zbunjenost): Matrica stanja kombinira se s podključem izvedenim iz glavnog ključa, uvodeći ovisnost ključa u svakoj rundi.
Učinkovitost šifre ne ovisi samo o snazi svake pojedinačne operacije, već i o broju primjena tih operacija. Kriptoanalitičari su pokazali da smanjenje broja rundi u šifri poput AES ili DES može je učiniti ranjivom na napade poput diferencijalne i linearne kriptoanalize. Na primjer, dok puna AES-128 koristi 10 rundi, verzije sa samo 6 rundi podložne su određenim kriptoanalitičkim tehnikama.
Nužnost više rundi
Radi dodatnog pojašnjenja, razmotrimo što se događa ako se primijeni samo jedan krug zbunjenosti i difuzije. Čak i ako se koriste jake S-kutije i slojevi miješanja, statistički odnosi i obrasci mogu se zadržati. Napadači bi mogli iskoristiti ove rezidualne obrasce koristeći napade odabranim otvorenim tekstom ili poznatim otvorenim tekstom. Višestruki krugovi osiguravaju da je utjecaj svakog ključa i bita otvorenog teksta potpuno raspoređen po cijelom šifriranom tekstu, što čini nemogućim izvođenje takvih napada.
Koncept "efekta lavine" ovdje je središnji. Jaka šifra osigurava da mala promjena u otvorenom tekstu (poput okretanja jednog bita) rezultira promjenom otprilike polovice bitova šifriranog teksta, a to se svojstvo postiže tek nakon nekoliko rundi zbunjenosti i difuzije. Iterativna struktura modernih blokovskih šifri posebno je dizajnirana kako bi pojačala ovaj učinak, čineći šifru otpornom na napade koji se oslanjaju na praćenje odnosa ulaz-izlaz.
Primjeri: DES i AES
Povijesna DES šifra dobro ilustrira ovaj princip. DES koristi 16 rundi u svojoj Feistel mrežnoj strukturi, pri čemu se svaka runda sastoji od širenja, S-box supstitucije (konfuzije) i permutacije (difuzije). Opsežna kriptoanaliza pokazala je da korištenje manje od 16 rundi dovodi do slabosti; diferencijalna kriptoanaliza učinkovita je protiv verzija s manje rundi. Dizajneri su odabrali 16 rundi kako bi osigurali marginu sigurnosti od napretka u kriptoanalizi, naglašavajući važnost višestrukih iteracija.
AES, dizajniran desetljećima kasnije, primjenjuje 10, 12 ili 14 rundi ovisno o veličini ključa (128, 192 ili 256 bita). Svaka runda uključuje kombinirane učinke zbunjenosti i difuzije kroz svoje korake SubBytes, ShiftRows i MixColumns. Broj rundi pažljivo je odabran na temelju kriptoanalitičkih nalaza kako bi se uravnotežila sigurnost i performanse.
Načini rada i njihov odnos
Dok je unutarnja sigurnost blokovskih šifri određena ponovljenom konfuzijom i difuzijom, način rada (npr. ECB, CBC, CFB, OFB, CTR) određuje kako se blokovske šifre primjenjuju na podatke veće od jednog bloka. Sigurnosna svojstva blokovske šifre u danom načinu rada u osnovi ovise o otpornosti blokovske šifre na napade, što je, pak, funkcija toga koliko se temeljito postižu konfuzija i difuzija u više rundi. Ako je temeljna blokovska šifra slaba (na primjer, s premalo rundi), nijedan način rada ne može nadoknaditi taj nedostatak.
Kriptoanalitički napadi i runde
Nekoliko kriptoanalitičkih napada iskorištava nedovoljnu konfuziju i difuziju u blokovskim šiframa. Diferencijalna kriptoanaliza, na primjer, proučava kako razlike u otvorenim tekstovima utječu na rezultirajuće razlike u šifriranom tekstu. Ako šifra nije adekvatno difuzirala ulazne razlike, napadač može predvidjeti kako se te razlike šire i upotrijebiti to znanje za oporavak ključa. Slično tome, linearna kriptoanaliza traži linearne aproksimacije između otvorenog teksta, šifriranog teksta i bitova ključa. Učinkovitost ovih napada smanjuje se s povećanjem broja rundi, pod uvjetom da svaka runda učinkovito implementira konfuziju i difuziju.
Za ilustraciju, DES s 8 rundi (polovica standardnog broja) podložan je diferencijalnoj kriptoanalizi, ali sa 16 rundi, vjerojatnost širenja korisnog diferencijalnog traga kroz sve runde postaje zanemariva. To pokazuje da je iterativna struktura, a posebno broj rundi, temeljna za postizanje praktične sigurnosti.
Ustupci dizajna
Dizajneri šifri moraju uravnotežiti broj rundi sa zahtjevima za performansama. Više rundi općenito znači veću sigurnost, ali i veće računalne troškove. Broj rundi se obično odabire kako bi se osigurala sigurnosna margina iznad najpoznatijih napada u vrijeme dizajna, s očekivanjem da bi budući napredak u kriptoanalizi mogao smanjiti tu marginu. Ovaj konzervativni pristup osigurava da šifra ostane sigurna tijekom svog očekivanog životnog vijeka.
Matematičko opravdanje
S teorijskog stajališta, iterativni dizajni blokovskih šifri mogu se promatrati kroz prizmu modela "iterativne šifre proizvoda". Pod određenim pretpostavkama, pokazano je da sastav više slabih šifri (od kojih svaka implementira slabu konfuziju i/ili difuziju) može proizvesti jaku ukupnu šifru, pod uvjetom da su komponente dovoljno neovisne i da je broj rundi velik. To opravdava iterativni pristup konfuziji i difuziji u praktičnom dizajnu šifri.
Praktični primjeri
Poučan primjer je struktura mreže supstitucije-permutacije (SPN) koju koristi AES. U SPN-u, otvoreni tekst je podvrgnut naizmjeničnim slojevima supstitucije (konfuzije) i permutacije (difuzije). Nakon nekoliko rundi, svaki izlazni bit ovisi o svakom ulaznom bitu na vrlo nelinearan način. Ovo svojstvo se ne postiže jednom rundom; kumulativni učinak više rundi osigurava da je svaki bit šifriranog teksta složena funkcija svakog bita otvorenog teksta i ključa, svojstvo poznato kao potpuna difuzija.
Feistelova mreža, kakva se koristi u DES-u, postiže sličnu sigurnost iterativnom primjenom kružne funkcije koja kombinira supstituciju i permutaciju, pri čemu izlaz svake runde ulazi u sljedeću. Sigurnost takvih konstrukcija raste eksponencijalno s brojem rundi, pod pretpostavkom da sama kružna funkcija nije trivijalno invertibilna ili linearna.
Zaključak: Sigurnosna ovisnost o iteraciji
Snaga blokovskih šifri usko je povezana s ponovljenom primjenom operacija zbunjenosti i difuzije. Moderne šifre dizajnirane su s dovoljnim brojem rundi kako bi se osiguralo da se eliminiraju svi preostali statistički odnosi iz otvorenog teksta ili ključa te da na svaki bit šifriranog teksta utječe svaki bit otvorenog teksta i ključa. Ovaj iterativni proces nije samo detalj implementacije, već temeljni princip sigurnosti šifre. Broj rundi odabire se na temelju opsežne kriptoanalize kako bi se osigurala margina sigurnosti i periodično se preispituje kako se pojavljuju novi napadi. U svim praktičnim i teorijskim aspektima, sigurnost blokovskih šifri doista ovisi o kombiniranju operacija zbunjenosti i difuzije više puta.
Ostala nedavna pitanja i odgovori u vezi Primjene blok šifri:
- Što bi blok šifra trebala sadržavati prema Shannonu?
- Znači li difuzija da su pojedinačni dijelovi šifriranog teksta pod utjecajem mnogih dijelova otvorenog teksta?
- Rastavlja li ECB način veliki ulazni otvoreni tekst u sljedeće blokove
- Možemo li koristiti blok šifru za izradu hash funkcije ili MAC-a?
- Može li se OFB način koristiti kao generator toka ključeva?
- Može li enkripcija biti deterministička?
- Koji su načini rada?
- Što način rada ECB čini jednostavnim blok šiframa
- Može li se PSRNG izraditi pomoću blok šifri?
- Može li se MAC izgraditi blok šiframa?
Više pitanja i odgovora potražite u Primjenama blok šifri