Vai bloku šifru drošība ir atkarīga no apjukuma un difūzijas operāciju daudzkārtējas apvienošanas?
Bloku šifru drošība pamatā sakņojas apjukuma un difūzijas operāciju iteratīvā pielietošanā. Šo koncepciju pirmo reizi formalizēja Klods Šenons savā fundamentālajā darbā par slepenības sistēmu komunikācijas teoriju, kur viņš formulēja gan apjukuma, gan difūzijas nepieciešamību kriptogrāfiskajās sistēmās, lai novērstu statistiskus un strukturālus uzbrukumus. Izpratne par to, kāpēc ir nepieciešamas vairākas šo operāciju kārtas un kā tās ir savstarpēji saistītas, ir ļoti svarīga, lai novērtētu tādu mūsdienu bloku šifru kā datu šifrēšanas standarta (DES) un uzlabotā šifrēšanas standarta (AES) dizainu un drošību.
Apjukums un difūzija: definīcijas un lomas
Apjukuma metode cenšas padarīt šifrteksta un atslēgas attiecības pēc iespējas sarežģītākas. Tas tiek panākts, maskējot vienkāršā teksta statistisko struktūru, bieži vien izmantojot nelineāras aizvietošanas (piemēram, S-lodziņus DES un AES). Jo nelineārāka un sarežģītāka ir šī kartēšana, jo grūtāk uzbrucējam ir izsecināt informāciju par atslēgu, pat ja ir piekļuve daudziem vienkāršā teksta un šifrteksta pāriem.
Savukārt difūzijas mērķis ir izplatīt katra vienkāršā teksta bita ietekmi pa daudziem šifrteksta bitiem, lai izmaiņas vienā ievades bitā izraisītu izmaiņas daudzos izvades bitos. Šī īpašība nodrošina, ka vienkāršā teksta statistiskās īpašības tiek izkliedētas visā šifrtekstā, padarot uzbrucējiem neiespējamu izmantot modeļus, izmantojot frekvenču analīzi vai līdzīgas metodes. Difūzija parasti tiek panākta, izmantojot lineāras sajaukšanas operācijas, piemēram, permutāciju, bitu XOR vai matricu reizināšanu (kā AES MixColumns operācijā).
Iteratīvo bloku šifru struktūra
Lielākā daļa bloku šifru ir strukturēti kā iterēti šifri, kas nozīmē, ka tie vairākas reizes pielieto vienkāršu noapaļošanas funkciju, lai sasniegtu augstu drošības līmeni. Noapaļošanas funkcija parasti apvieno gan apjukumu (piemēram, izmantojot S-box lietojumprogrammas), gan difūziju (piemēram, izmantojot permutācijas vai sajaukšanas soļus). Vairāku kārtu izmantošanas pamatojums ir tāds, ka viena apjukuma un difūzijas pielietošana nav pietiekama, lai slēptu visas strukturālās attiecības starp vienkāršo tekstu, šifrēto tekstu un atslēgu. Katra kārta pakāpeniski palielina šo attiecību sarežģītību, un tikai pēc vairākām kārtām šifrs sasniedz vēlamo drošības līmeni pret zināmiem kriptoanalītiskiem uzbrukumiem.
Piemēram, ņemot vērā AES šifru, katra šifrēšanas kārta sastāv no šādiem galvenajiem soļiem:
1. Apakšbaiti (apjukums): Katrs baits stāvokļa matricā tiek aizstāts ar citu saskaņā ar fiksētu nelineāru S-lodziņu, ieviešot nelinearitāti.
2. ShiftRows (difūzija): Stāvokļa matricas rindas tiek cikliski nobīdītas, pārvietojot baitus uz dažādām kolonnām un atvieglojot vērtību sajaukšanos.
3. MixColumns (difūzija): Stāvokļa kolonnas tiek sajauktas, izmantojot matricu reizināšanu galīgā laukā, vēl vairāk sadalot katra ievades baita ietekmi.
4. AddRoundKey (neskaidrības): Stāvokļa matrica tiek apvienota ar apakšatslēgu, kas atvasināta no galvenās atslēgas, ieviešot atslēgas atkarību katrā kārtā.
Šifra efektivitāte ir atkarīga ne tikai no katras atsevišķās darbības stipruma, bet arī no tā, cik reižu šīs darbības tiek pielietotas. Kriptoanalītiķi ir pierādījuši, ka šifra, piemēram, AES vai DES, kārtu skaita samazināšana var padarīt to neaizsargātu pret tādiem uzbrukumiem kā diferenciālā un lineārā kriptoanalīze. Piemēram, lai gan pilnais AES-128 izmanto 10 kārtas, versijas ar tikai 6 kārtām ir uzņēmīgas pret noteiktām kriptoanalīzes metodēm.
Vairāku raundu nepieciešamība
Lai vēl vairāk precizētu, apsveriet, kas notiek, ja tiek piemērota tikai viena sajaukšanas un izkliedēšanas kārta. Pat ja tiek izmantotas spēcīgas S kastes un sajaukšanas slāņi, statistiskās attiecības un modeļi var saglabāties. Uzbrucēji varētu izmantot šos atlikušos modeļus, izmantojot izvēlēta vienkāršā teksta vai zināma vienkāršā teksta uzbrukumus. Vairākas kārtas nodrošina, ka katras atslēgas un vienkāršā teksta bita ietekme tiek rūpīgi izkliedēta visā šifrētajā tekstā, padarot šādu uzbrukumu veikšanu neiespējamu.
Šeit centrālais ir "lavīnas efekta" jēdziens. Spēcīgs šifrs nodrošina, ka nelielas izmaiņas vienkāršā tekstā (piemēram, viena bita apgriešana) izraisa izmaiņas aptuveni pusē šifrētā teksta bitu, un šī īpašība tiek sasniegta tikai pēc vairākām sajaukšanas un izkliedes kārtām. Mūsdienu bloku šifru iteratīvā struktūra ir īpaši izstrādāta, lai pastiprinātu šo efektu, padarot šifru izturīgu pret uzbrukumiem, kas balstās uz ievades-izvades attiecību izsekošanu.
Piemēri: DES un AES
Vēsturiskais DES šifrs labi ilustrē šo principu. DES savā Feistel tīkla struktūrā izmanto 16 kārtas, katra kārta sastāv no paplašināšanas, S-box aizstāšanas (sajaukšanas) un permutācijas (difūzijas). Plaša kriptoanalīze ir parādījusi, ka mazāk nekā 16 kārtu izmantošana rada vājības; diferenciālā kriptoanalīze ir efektīva pret versijām ar mazāku kārtu skaitu. Izstrādātāji izvēlējās 16 kārtas, lai nodrošinātu drošības rezervi pret kriptoanalīzes sasniegumiem, uzsverot vairāku iterāciju nozīmi.
AES, kas tika izstrādāts vairākus gadu desmitus vēlāk, atkarībā no atslēgas lieluma (attiecīgi 10, 12 vai 14 biti) piemēro 128, 192 vai 256 kārtas. Katra kārta ietver apjukuma un difūzijas kombinēto ietekmi, izmantojot tās SubBytes, ShiftRows un MixColumns soļus. Kārtu skaits tika rūpīgi izvēlēts, pamatojoties uz kriptoanalīzes atklājumiem, lai līdzsvarotu drošību un veiktspēju.
Darbības režīmi un to saistība
Lai gan bloku šifru iekšējo drošību nosaka atkārtota sajaukšana un izplatīšanās, darbības režīms (piemēram, ECB, CBC, CFB, OFB, CTR) nosaka, kā bloku šifri tiek piemēroti datiem, kas lielāki par vienu bloku. Bloku šifra drošības īpašības noteiktā režīmā būtībā ir atkarīgas no bloku šifra izturības pret uzbrukumiem, kas, savukārt, ir atkarīga no tā, cik rūpīgi tiek panākta sajaukšana un izplatīšanās vairākās kārtās. Ja pamatā esošais bloku šifrs ir vājš (piemēram, ar pārāk maz kārtām), neviens darbības režīms nevar kompensēt šo trūkumu.
Kriptoanalītiskie uzbrukumi un raundi
Vairāki kriptoanalītiskie uzbrukumi izmanto nepietiekamu apjukumu un izkliedi bloku šifros. Piemēram, diferenciālā kriptoanalīze pēta, kā atšķirības vienkāršos tekstos ietekmē iegūtās šifrteksta atšķirības. Ja šifrs nav pietiekami izkliedējis ievades atšķirības, uzbrucējs var paredzēt, kā šīs atšķirības izplatās, un izmantot šīs zināšanas, lai atgūtu atslēgu. Līdzīgi lineārā kriptoanalīze meklē lineāras aproksimācijas starp vienkāršo tekstu, šifrtekstu un atslēgas bitiem. Šo uzbrukumu efektivitāte samazinās, palielinoties kārtu skaitam, ar nosacījumu, ka katra kārta efektīvi īsteno apjukumu un izkliedi.
Ilustrācijai, DES ar 8 kārtām (puse no standarta skaita) ir pakļauts diferenciālai kriptoanalīzei, bet ar 16 kārtām noderīgas diferenciālās pēdas izplatīšanās varbūtība visās kārtās kļūst niecīga. Tas parāda, ka iteratīvā struktūra un jo īpaši kārtu skaits ir būtisks praktiskas drošības sasniegšanai.
Dizaina kompromisi
Šifru izstrādātājiem ir jāsabalansē kārtu skaits ar veiktspējas prasībām. Vairāk kārtu parasti nozīmē lielāku drošību, bet arī lielākas skaitļošanas izmaksas. Kārtu skaits parasti tiek izvēlēts tā, lai nodrošinātu drošības rezervi, kas pārsniedz projektēšanas laikā vispazīstamākos uzbrukumus, paredzot, ka turpmākie kriptoanalīzes sasniegumi varētu samazināt šo rezervi. Šī konservatīvā pieeja nodrošina, ka šifrs saglabā drošību visā tā paredzamajā kalpošanas laikā.
Matemātiskais pamatojums
No teorētiskā viedokļa iterētu bloku šifru dizainus var aplūkot caur "iterēta produkta šifra" modeļa prizmu. Saskaņā ar noteiktiem pieņēmumiem ir pierādīts, ka vairāku vāju šifru (katrs no tiem īsteno vāju apjukumu un/vai difūziju) apvienojums var radīt spēcīgu kopējo šifru, ja komponenti ir pietiekami neatkarīgi un kārtu skaits ir liels. Tas attaisno iteratīvo pieeju apjukumam un difūzijai praktiskajā šifru dizainā.
Praktiski piemēri
Labs piemērs ir AES izmantotā aizstāšanas-permutācijas tīkla (SPN) struktūra. SPN vienkāršā teksta struktūra tiek pakļauta mainīgiem aizstāšanas (apjukuma) un permutācijas (difūzijas) slāņiem. Pēc vairākām kārtām katrs izejas bits ir ļoti nelineāri atkarīgs no katra ievades bita. Šī īpašība netiek panākta ar vienu kārtu; tieši vairāku kārtu kumulatīvais efekts nodrošina, ka katrs šifrteksta bits ir sarežģīta funkcija no katra vienkāršā teksta bita un atslēgas, un šī īpašība ir pazīstama kā pilnīga difūzija.
Feistela tīkls, kā tas tiek izmantots DES, panāk līdzīgu drošību, iteratīvi pielietojot apaļo funkciju, kas apvieno aizstāšanu un permutāciju, katras kārtas izvadi iekļaujot nākamajā. Šādu konstrukciju drošība palielinās eksponenciāli līdz ar kārtu skaitu, pieņemot, ka pati apaļā funkcija nav triviāli invertējama vai lineāra.
Secinājums: Drošības atkarība no iterācijas
Bloku šifru stiprums ir cieši saistīts ar atkārtotu apjukuma un difūzijas operāciju pielietošanu. Mūsdienu šifri ir izstrādāti ar pietiekamu kārtu skaitu, lai nodrošinātu, ka jebkādas atlikušās statistiskās attiecības no vienkāršā teksta vai atslēgas tiek novērstas un ka katru šifrteksta bitu ietekmē katrs vienkāršā teksta un atslēgas bits. Šis iteratīvais process nav tikai ieviešanas detaļa, bet gan šifru drošības pamatprincips. Kārtu skaits tiek izvēlēts, pamatojoties uz plašu kriptoanalīzi, lai nodrošinātu drošības rezervi, un tas tiek periodiski pārskatīts, parādoties jauniem uzbrukumiem. Visos praktiskos un teorētiskos aspektos bloku šifru drošība patiešām ir atkarīga no apjukuma un difūzijas operāciju daudzkārtējas apvienošanas.
Citi jaunākie jautājumi un atbildes par Bloku šifru lietojumi:
- Kas, saskaņā ar Šenonu, jāiekļauj bloka šifrā?
- Vai difūzija nozīmē, ka atsevišķus šifrēta teksta bitus ietekmē daudzi vienkāršā teksta biti?
- Vai ECB režīms sadala lielu ievades vienkāršu tekstu nākamajos blokos
- Vai mēs varam izmantot bloka šifru, lai izveidotu jaucējfunkciju vai MAC?
- Vai OFB režīmu var izmantot kā atslēgu plūsmas ģeneratorus?
- Vai šifrējums var būt deterministisks?
- Kādi ir darbības režīmi?
- Ko ECB režīms dara ar vienkāršiem bloķēšanas šifriem
- Vai PSRNG var izveidot, izmantojot bloku šifrus?
- Vai MAC var izveidot, izmantojot bloku šifrus?
Skatiet vairāk jautājumu un atbilžu sadaļā Bloku šifru lietojumprogrammas