Bloková šifra

V kryptografii je bloková šifra deterministický algoritmus pracujúci na skupinách bitov s pevnou dĺžkou, nazývaných bloky . Blokové šifry sú špecifikované elementárne komponenty pri navrhovaní mnohých kryptografických protokolov a sú široko používané na šifrovanie veľkého množstva údajov, vrátane protokolov na výmenu údajov. Bloková šifra používa bloky ako nemennú transformáciu.

Dokonca aj zabezpečená bloková šifra je vhodná na šifrovanie iba jedného bloku údajov naraz pomocou pevného kľúča. Množstvo prevádzkových režimov bolo navrhnutých tak, aby umožnili ich opakované používanie bezpečným spôsobom na dosiahnutie bezpečnostných cieľov dôvernosti a autenticity . Blokové šifry sa však môžu vyskytovať aj ako stavebné bloky v iných kryptografických protokoloch, ako sú univerzálne hešovacie funkcie a generátory pseudonáhodných čísel .

Definícia

Bloková šifra pozostáva z dvoch párových algoritmov, jeden na šifrovanie $E$,  a druhý na dešifrovanie $D$, Oba algoritmy akceptujú dva vstupy: vstupný blok veľkosti n bitov a kľúč veľkosti k bitov; a obe poskytujú n-bitový výstupný blok. Algoritmus dešifrovania $D$ je definovaný ako inverzná funkcia šifrovania, tj $D=E^{-1}$. Formálnejšie, je bloková šifra špecifikovaná šifrovacou funkciou

$E_{K}(P):=E(K,P):\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1\}^{n}$

ktorý berie ako vstup kľúč $K$ , bitovej dĺžky $k$ (nazývaná veľkosť kľúča ) a bitový reťazec $P$ , dĺžky $n$ (nazýva sa veľkosť bloku ) a vráti reťazec $C$ dĺžky $n$ bitov. $P$ sa nazýva otvorený text a $C$ sa nazýva šifrovaný text . Pre každé $C$ , funkcia $E_{K}(P)$  musí mať inverzné zobrazenie na {0,1}ⁿ. Inverzná funkcia k funkcii $E$ je funkcia

$E_{K}^{-1}(C):=D_{K}(C)=D(K,C):\{0,1\}^{k}\times \{0,1\}^{n}\rightarrow \{0,1\}^{n}$

ktorá berie kľúč $K$ a šifrovaný text $C$ , a vracia otvorený text $P$ taký, že

$\forall P:D_{K}(E_{K}(P))=P.$

Napríklad šifrovací algoritmus blokovej šifry môže prijať 128-bitový blok otvoreného textu ako vstup a vygenerovať výstup zodpovedajúci 128-bitovému bloku šifrovaného textu. Presná transformácia je riadená pomocou druhého vstupu – tajného kľúča. Dešifrovanie je podobné: dešifrovací algoritmus v tomto príklade berie 128-bitový blok šifrovaného textu spolu s tajným kľúčom a vráti pôvodný 128-bitový blok čistého textu.

Pre každý kľúč K je E_K permutácia ₍ bijektívne zobrazenie) cez množinu vstupných blokov. Každý kľúč vyberá jednu permutáciu z množiny $(2^{n})!$ možných permutácií.

História

Moderný dizajn blokových šifier je založený na koncepte iterovanej produktovej šifry . Claude Shannon vo svojej kľúčovej publikácii z roku 1949 Komunikačná teória tajných systémov analyzoval produktové šifry a navrhol ich ako prostriedok na efektívne zlepšenie bezpečnosti kombináciou jednoduchých operácií, ako sú substitúcie a permutácie. Iterované produktové šifry vykonávajú šifrovanie vo viacerých kolách, z ktorých každé používa iný podkľúč odvodený od pôvodného kľúča. Jedna rozšírená implementácia takýchto šifier, pomenovaná ako sieť Feistel podľa Horsta Feistela, je implementovaná najmä v šifre DES . Mnohé ďalšie realizácie blokových šifier, ako napríklad AES, sú klasifikované ako substitučno-permutačné siete .

Základ všetkých formátov kryptografických blokov používaných v rámci štandardov PCI DSS ( Payment Card Industry Data Security Standard ) a American National Standards Institute (ANSI) spočíva v Atalla Key Block (AKB), ktorý bol kľúčovou inováciou Atalla Boxu, prvého hardvérového bezpečnostného modulu (HSM). Bol vyvinutý v roku 1972 Mohamedom M. Atallom, zakladateľom spoločnosti Atalla Corporation (teraz Utimaco Atalla ), a vydaný v roku 1973. AKB bol kľúčový blok, ktorý je potrebný na bezpečnú výmenu symetrických kľúčov alebo PINov s inými aktérmi bankového sektora . Táto bezpečná výmena sa vykonáva pomocou formátu AKB. Atalla Box chránil viac ako 90 % všetkých bankomatových sietí v prevádzke od roku 1998 a produkty Atalla stále zabezpečujú väčšinu svetových bankomatových transakcií od roku 2014.

Zverejnenie šifry DES Národným úradom pre štandardy Spojených štátov (následne Národným inštitútom pre štandardy a technológie v USA, NIST) rokom 1977 bolo základom pre verejné chápanie moderného dizajnu blokových šifier. Ovplyvnilo to aj akademický vývoj kryptoanalytických útokov . Diferenciálna aj lineárna kryptoanalýza vyplynuli zo štúdií o dizajne DES. Od roku 2016 existuje paleta útočných techník, proti ktorým musí byť bloková šifra zabezpečená, okrem toho, že musí byť odolná proti útokom hrubou silou .

Dizajn

Iterované (opakované) blokové šifry

Väčšina algoritmov blokovej šifry sú klasifikované ako iterované blokové šifry, čo znamená, že transformujú bloky s pevnou veľkosťou otvoreného textu na bloky šifrovaného textu rovnakej veľkosti prostredníctvom opakovanej aplikácie invertovateľnej transformácie známej ako obehová funkcia, pričom každá iterácia sa označuje ako obeh (jedno "kolečko").

Obyčajne obehová funkcia R berie ako druhý vstup rôzne čiastkové kľúče K_i, ktoré sú odvodené od pôvodného kľúča:

$M_{i}=R_{K_{i}}(M_{i-1})$

kde $M_{0}$ je čistý text a $M_{r}$ šifrový text, pričom r je počet obehov.

Okrem toho sa často používa bielenie kľúčom . Na začiatku a na konci sú údaje upravené kľúčom (často pomocou operácie XOR, ale používajú sa aj jednoduché aritmetické operácie ako sčítanie a odčítanie):

$M_{0}=M\oplus K_{0}$

$M_{i}=R_{K_{i}}(M_{i-1})\;;\;i=1\dots r$

$C=M_{r}\oplus K_{r+1}$

Vzhľadom na jednu zo štandardných iterovaných schém návrhu blokovej šifry je pomerne jednoduché zostaviť blokovú šifru, ktorá je kryptograficky bezpečná, jednoducho použitím veľkého počtu kôl. To však spôsobí, že šifra nebude efektívna. Efektívnosť je teda najdôležitejším dodatočným kritériom návrhu pre profesionálne šifry. Okrem toho je dobrá bloková šifra navrhnutá tak, aby sa vyhla útokom na bočný kanál, ako je predikcia vetvenia a prístupy do pamäte závislé od vstupov, cez ktoré by mohli uniknúť tajné dáta cez stav vyrovnávacej pamäte alebo čas vykonania. Okrem toho by šifra mala byť stručná, pre malé hardvérové a softvérové implementácie (napr. na mikropočítačoch). Napokon, šifra by mala byť ľahko kryptoanalyzovateľná, aby bolo možné ukázať, na koľko kôl je potrebné šifru zredukovať, aby fungovali existujúce kryptografické útoky – a naopak, aby bolo možné ukázať, že počet skutočných kôl je dostatočne veľký na to, aby sa pred nimi chránili.

Substitučno-permutačné siete

Náčrt substitučno-permutačnej siete s 3 kolami, ktorá šifruje blok otvoreného textu 16 bitov do bloku šifrovaného textu 16 bitov. S-boxy sú _Si, P-boxy sú rovnaké P a okrúhle klávesy sú _Ki .

Jeden dôležitý typ iterovanej blokovej šifry známej ako substitučná-permutačná sieť (SPN) berie blok otvoreného textu a kľúč ako vstupy a aplikuje niekoľko striedajúcich sa kôl pozostávajúcich z substitučnej fázy, po ktorej nasleduje permutačná fáza – na vytvorenie každého bloku výstupu šifrovaného textu. Fáza nelineárnej substitúcie mieša kľúčové bity s bitmi otvoreného textu, čo vytvára Shannonov zmätok . Štádium lineárnej permutácie potom rozptýli redundancie a vytvorí difúziu .

Substitučný box (S-box) nahrádza malý blok vstupných bitov iným blokom výstupných bitov. Táto substitúcia musí byť jedna k jednej, aby sa zabezpečila invertibilita (teda dešifrovanie). Bezpečný S-box bude mať tú vlastnosť, že zmena jedného vstupného bitu zmení v priemere asi polovicu výstupných bitov, prejaví sa to, čo je známe ako lavínový efekt – tj má tú vlastnosť, že každý výstupný bit bude závisieť od každého vstupného bitu.

Permutačný box (P-box) je permutáciou všetkých bitov: berie výstupy všetkých S-boxov jedného kola, permutuje bity a dodáva ich do S-boxov ďalšieho kola. Dobrý P-box má tú vlastnosť, že výstupné bity akéhokoľvek S-boxu sú distribuované na čo najviac vstupov S-boxu.

V každom kole sa podkľúč pre daný beh (získaný z kľúča niekoľkými jednoduchými operáciami, napríklad pomocou S-boxov a P-boxov) kombinuje pomocou nejakej skupinovej operácie, typicky XOR .

Dešifrovanie sa vykonáva jednoduchým obrátením procesu (použitím inverzných S-boxov a P-boxov a použitím okrúhlych kľúčov v opačnom poradí).

Feistelove šifry

Mnohé blokové šifry, ako napríklad DES a Blowfish, využívajú štruktúry známe ako Feistelove šifry

Vo Feistelovej šifre je blok obyčajného textu, ktorý sa má zašifrovať, rozdelený na dve rovnako veľké polovice. Funkcia sa aplikuje na jednu polovicu pomocou podkľúča a potom sa výstup XORuje s druhou polovicou. Potom sa obe polovice vymenia.

Nech ${\rm {F}}$ je obehová funkcia a nech $K_{0},K_{1},\ldots ,K_{n}$ sú podkľúčmi pre kolá $0,1,\ldots ,n$.

Potom je základný algoritmus nasledovný:

Rozdeľ blok čistého textu na dve rovnaké časti, ( $L_{0}$, $R_{0}$ )

Pre každé kolo $i=0,1,\dots ,n$, vypočítaj

$L_{i+1}=R_{i}\,$

$R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})$ .

Potom je šifrovaný text $(R_{n+1},L_{n+1})$ .

Dešifrovanie šifrovaného textu $(R_{n+1},L_{n+1})$ sa dosiahne výpočtom pre $i=n,n-1,\ldots ,0$

$R_{i}=L_{i+1}\,$

$L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})$ .

Potom $(L_{0},R_{0})$ je opäť čistý text.

Jednou z výhod Feistelovho modelu v porovnaní so substitučno-permutačnou sieťou je to, že obehová funkcia ${\rm {F}}$ nemusí byť invertibilná.

Lai-Massey šifry

Schéma Lai-Massey. Archetypickou šifrou, ktorá ju využíva, je IDEA .

Schéma Lai–Massey ponúka bezpečnostné vlastnosti podobné tým, ktoré majú Feistelove šifry. Jej výhodou je, že obehová funkcia $\mathrm {F}$ nemusí byť invertibilná. Ďalšou podobnosťou je, že tiež rozdeľuje vstupný blok na dve rovnaké časti. Obehová funkcia sa však aplikuje na rozdiel medzi týmito dvoma časťami a výsledok sa potom pripočíta k obom polovičným blokom.

Nech $\mathrm {F}$ je obehová funkcia a $\mathrm {H}$ pol-obehová funkcia a nech $K_{0},K_{1},\ldots ,K_{n}$ je podkľúčmi pre kolá $0,1,\ldots ,n$.

Potom je základný algoritmus nasledovný:

Rozdeľ blok čistého textu na dve rovnaké časti, ( $L_{0}$, $R_{0}$ )

Pre každé kolo $i=0,1,\dots ,n$, vypočítaj

$(L_{i+1}',R_{i+1}')=\mathrm {H} (L_{i}'+T_{i},R_{i}'+T_{i}),$

kde $T_{i}=\mathrm {F} (L_{i}'-R_{i}',K_{i})$ a $(L_{0}',R_{0}')=\mathrm {H} (L_{0},R_{0})$

Potom je šifrovaný text $(L_{n+1},R_{n+1})=(L_{n+1}',R_{n+1}')$ .

Dešifrovanie šifrovaného textu $(L_{n+1},R_{n+1})$ sa dosiahne výpočtom pre $i=n,n-1,\ldots ,0$

$(L_{i}',R_{i}')=\mathrm {H} ^{-1}(L_{i+1}'-T_{i},R_{i+1}'-T_{i})$

kde $T_{i}=\mathrm {F} (L_{i+1}'-R_{i+1}',K_{i})$ a $(L_{n+1}',R_{n+1}')=\mathrm {H} ^{-1}(L_{n+1},R_{n+1})$

Potom $(L_{0},R_{0})=(L_{0}',R_{0}')$ je opäť čistý text.

Operácie

ARX (sčítať-rotovať-XOR)

Mnohé moderné blokové šifry a hash sú algoritmy ARX – ich obehová funkcia zahŕňa iba tri operácie: (A) sčítanie s modulom, (R) rotácia s pevným počtom rotácií a (X) XOR . Príklady zahŕňajú ChaCha20, Speck, XXTEA a BLAKE . Mnohí autori kreslia sieť ARX ako diagram toku údajov, na ilustráciu takejto obehovej funkcie.

Tieto operácie ARX sú obľúbené, pretože sú relatívne rýchle a lacno realizovateľné v hardvéri a softvéri, ich implementácia môže byť mimoriadne jednoduchá a tiež preto, že bežia v konštantnom čase, a preto sú imúnne voči časovacím útokom . Technika rotačnej kryptoanalýzy sa pokúša napadnúť takéto obehové funkcie.

Iné operácie

Medzi ďalšie operácie často používané v blokových šifrách patria rotácie závislé od údajov ako v RC5 a RC6, substitučný box implementovaný ako vyhľadávacia tabuľka ako v Data Encryption Standard a Advanced Encryption Standard, permutačný box a násobenie ako v algoritme IDEA .

Prevádzkové režimy

Nezabezpečené šifrovanie obrazu v dôsledku kódovania v režime elektronického číselníka (ECB).

Bloková šifra sama o sebe umožňuje zašifrovať iba jeden dátový blok s dĺžkou bloku šifry. V prípade správy s premenlivou dĺžkou musia byť údaje najskôr rozdelené do samostatných šifrovacích blokov. V najjednoduchšom prípade, ktorý je známy ako režim elektronického číselníka (ECB), sa správa najprv rozdelí na samostatné bloky s veľkosťou bloku šifry (prípadne predĺži posledný blok o tzv. padding) a potom sa každý blok zašifruje a dešifruje nezávisle. Takáto naivná metóda je však vo všeobecnosti neistá, pretože rovnaké bloky otvoreného textu budú vždy generovať rovnaké bloky šifrovaného textu (pre rovnaký kľúč), takže vzory v nešifrovanej správe sa prejavia vo výstupe zašifrovaného textu.

Na prekonanie tohto obmedzenia bolo navrhnutých niekoľko takzvaných blokových šifrovacích režimov prevádzky špecifikovaných v národných odporúčaniach, ako sú NIST 800-38A a BSI TR-02102a medzinárodných štandardoch, ako je ISO /IEC 10116 . Všeobecnou koncepciou je použitie randomizácie údajov v nešifrovanom texte na základe dodatočnej vstupnej hodnoty, často nazývanej inicializačný vektor, na vytvorenie toho, čo sa nazýva pravdepodobnostné šifrovanie . V populárnom režime cipher block chaining (CBC), aby bolo šifrovanie bezpečné, musí byť inicializačný vektor odovzdaný spolu so správou v otvorenom texte ako náhodná alebo pseudonáhodná hodnota, ktorá sa pridáva XOR operáciou k prvej hodnote bloku nešifrovaného textu pred jeho zašifrovaním. Výsledný blok šifrovaného textu sa potom použije ako nový inicializačný vektor pre ďalší blok nešifrovaného textu. V režime šifrovanej spätnej väzby (CFB), ktorý emuluje samosynchronizujúcu prúdovú šifru, je inicializačný vektor najprv zašifrovaný a potom pridaný do bloku otvoreného textu. Režim výstupnej spätnej väzby (OFB) opakovane zašifruje inicializačný vektor, aby vytvoril kľúčový prúd na emuláciu synchrónnej prúdovej šifry . Novší režim počítadla (CTR) podobne vytvára kľúčový tok, ale má tú výhodu, že ako inicializačné vektory potrebuje iba jedinečné a nie (pseudo-)náhodné hodnoty; potrebná náhodnosť je odvodená interne použitím inicializačného vektora ako počítadla blokov a zašifrovaním tohto počítadla pre každý blok.

Z bezpečnostného teoretického hľadiska musia prevádzkové režimy poskytovať to, čo je známe ako sémantická bezpečnosť . Neformálne to znamená, že pri zadaní nejakého zašifrovaného textu pod neznámym kľúčom nemožno zo zašifrovaného textu prakticky odvodiť žiadnu informáciu (okrem dĺžky správy) nad tým, čo by človek vedel bez toho, aby videl zašifrovaný text. Ukázalo sa, že všetky vyššie diskutované režimy, s výnimkou režimu ECB, poskytujú túto vlastnosť pri takzvaných útokov na vybraný nezašifrovaný text.

Padding (výplň resp. zarovnanie)

Niektoré režimy, ako napríklad režim CBC, fungujú iba na úplných blokoch otvoreného textu. Jednoduché rozšírenie posledného bloku správy s nulovými bitmi je nedostatočné, pretože neumožňuje prijímateľovi ľahko rozlíšiť správy, ktoré sa líšia iba množstvom výplňových bitov. Ešte dôležitejšie je, že takéto jednoduché riešenie vedie k veľmi účinným útokom orákula. Na zarovnanie posledného bloku otvoreného textu na veľkosť bloku šifry je preto potrebná vhodná schéma výplne . Zatiaľ čo sa mnohé populárne schémy opísané v štandardoch a v literatúre ukázali ako zraniteľné voči útokom orákula, riešenie, ktoré pridáva jednotku na koniec dát a potom k ním pridá nuly až na veľkosť bloku, štandardizované ako „ metóda padding 2" v ISO/IEC 9797-1, sa ukázalo ako bezpečné proti týmto útokom.

Kryptoanalýza

Útoky hrubou silou

Táto vlastnosť vedie k kvadratickému zhoršovaniu bezpečnosti šifry a je potrebné ju vziať do úvahy pri výbere veľkosti bloku. Existuje však kompromis, pretože veľké veľkosti blokov môžu viesť k tomu, že algoritmus sa stane neefektívnym. Skoršie blokové šifry, ako napríklad DES, si zvyčajne vybrali 64-bitovú veľkosť bloku, zatiaľ čo novšie návrhy, ako napríklad AES, podporujú veľkosť bloku 128 bitov alebo viac, pričom niektoré šifry podporujú celý rad rôznych veľkostí blokov.

Lineárna kryptoanalýza

Lineárna kryptoanalýza je forma kryptoanalýzy založená na hľadaní afinných aproximácií k činnosti šifry . Lineárna kryptoanalýza je jedným z dvoch najpoužívanejších útokov na blokové šifry; druhá je diferenciálna kryptanalýza .Objav sa pripisuje Mitsuru Matsuimu, ktorý ako prvý použil túto techniku na šifru FEAL (Matsui a Yamagishi, 1992).

Integrálna kryptoanalýza

Integrálna kryptoanalýza je kryptoanalytický útok, ktorý je použiteľný najmä na blokové šifry založené na substitučno-permutačných sieťach. Na rozdiel od diferenciálnej kryptoanalýzy, ktorá používa dvojice vybraných otvorených textov s pevným rozdielom XOR, integrálna kryptoanalýza používa množiny alebo dokonca multimnožiny vybraných otvorených textov, z ktorých časť zostáva konštantná a iná sa mení všetkými možnosťami. Napríklad útok môže použiť 256 vybraných otvorených textov, ktoré majú všetky bity okrem 8 rovnaké, ale všetky sa líšia v týchto 8 bitoch. Takáto množina má nevyhnutne súčet XOR rovný 0 a súčty XOR zodpovedajúcich množín šifrových textov poskytujú informácie o fungovaní šifry. Tento kontrast medzi rozdielmi dvojíc textov a súčtom väčších súborov textov inšpiroval názov „integrálna kryptanalýza“, ktorý prevzal terminológiu kalkulu.

Iné techniky

Vývoj bumerangového útoku umožnil použiť techniky diferenciálnej kryptoanalýzy na mnohé šifry, ktoré boli predtým považované za bezpečné proti diferenciálnym útokom.

Okrem lineárnej a diferenciálnej kryptoanalýzy rastie katalóg útokov: skrátená diferenciálna kryptanalýza, čiastočná diferenciálna kryptanalýza, integrálna kryptoanalýza, ktorá zahŕňa štvorcové a integrálne útoky, útoky slide, bumerangové útoky, XSL útok, nemožná diferenciálna kryptanalýza a algebraické útoky . Aby mal nový návrh blokovej šifry akúkoľvek dôveryhodnosť, musí preukázať bezpečnosť proti známym útokom.

Preukázateľné zabezpečenie

Keď sa v danom režime prevádzky použije bloková šifra, výsledný algoritmus by mal byť v ideálnom prípade taký bezpečný ako samotná bloková šifra. ECB (diskutovaná vyššie) dôrazne chýba táto vlastnosť: bez ohľadu na to, ako bezpečná je základná bloková šifra, režim ECB môže byť ľahko napadnutý. Na druhej strane, režim CBC môže byť preukázaný ako bezpečný za predpokladu, že základná bloková šifra je tiež bezpečná. Všimnite si však, že takéto vyhlásenia si vyžadujú formálne matematické definície toho, čo znamená, že šifrovací algoritmus alebo bloková šifra „byť bezpečné“. Táto časť popisuje dve bežné predstavy o tom, aké vlastnosti by mala mať bloková šifra. Každý zodpovedá matematickému modelu, ktorý možno použiť na preukázanie vlastností algoritmov vyššej úrovne, ako je CBC.

Tento všeobecný prístup ku kryptografii – dokazovanie, že algoritmy vyššej úrovne (ako je CBC) sú bezpečné za explicitne uvedených predpokladov týkajúcich sa ich komponentov (ako je bloková šifra) – je známy ako preukázateľná bezpečnosť .

Štandardný model

Neformálne je bloková šifra v štandardnom modeli bezpečná, ak útočník nedokáže rozlíšiť medzi blokovou šifrou (vybavenou náhodným kľúčom) a náhodnou permutáciou.

Aby sme boli trochu presnejší, nech E je n -bitová bloková šifra. Predstavme si nasledujúcu hru:

1. Osoba, ktorá hrá hru, hodí mincou.
   • Ak minca dopadne na hlavu, vyberie si náhodný kľúč K a definuje funkciu f = E _K .
   • Ak minca pristane na chvoste, zvolí náhodnú permutáciu π na množine n -bitových reťazcov a definuje funkciu f = π .
2. Útočník si vyberie n -bitový reťazec X a osoba, ktorá hrá hru, mu povie hodnotu f ( X ).
3. Krok 2 sa opakuje celkom q -krát. (Každá z týchto q interakcií je dotaz . )
4. Útočník háda, ako minca dopadla. Vyhráva, ak je jeho odhad správny.

Útočník, ktorého môžeme modelovať ako algoritmus, sa nazýva protivník . Funkcia f (na ktorú sa protivník mohol opýtať) sa nazýva oracle .

Všimnite si, že protivník si môže triviálne zabezpečiť 50% šancu na výhru jednoduchým náhodným hádaním (alebo dokonca napríklad tým, že vždy háda „hlavy“). Preto nech P _E ( A ) označuje pravdepodobnosť, že protivník A vyhrá túto hru proti E a definujte výhodu A ako 2( P _E ( A ) − 1/2). Z toho vyplýva, že ak A náhodne uhádne, jeho výhoda bude 0; na druhej strane, ak A vždy vyhrá, jeho výhoda je 1. Bloková šifra E je pseudonáhodná permutácia (PRP), ak žiadny protivník nemá výhodu výrazne väčšiu ako 0, vzhľadom na špecifikované obmedzenia na q a dobu trvania protivníka. Ak majú v kroku 2 vyššie protivníci možnosť naučiť sa f ⁻¹ ( X ) namiesto f ( X ) (ale stále majú len malé výhody), potom E je silný PRP (SPRP). Protivník je neprispôsobivý, ak si vyberie všetky hodnoty q pre X pred začiatkom hry (to znamená, že nepoužíva žiadne informácie získané z predchádzajúcich dotazov na výber každého X priebežne).

Tieto definície sa ukázali ako užitočné pri analýze rôznych režimov prevádzky. Napríklad je možné definovať podobnú hru na meranie bezpečnosti šifrovacieho algoritmu založeného na blokovej šifre a potom sa pokúsiť ukázať (prostredníctvom redukčného argumentu ), že pravdepodobnosť, že protivník vyhrá túto novú hru, nie je oveľa väčšia ako P _E ( A ) pre niektoré A. (Zníženie zvyčajne poskytuje limity pre q a čas hrania A . ) Ekvivalentne, ak je PE ( A ) malé pre všetky relevantné _A, potom žiadny útočník nemá významnú pravdepodobnosť víťazstva v novej hre. Toto formalizuje myšlienku, že algoritmus vyššej úrovne zdedí bezpečnosť blokovej šifry.

Praktické hodnotenie

Blokové šifry možno v praxi hodnotiť podľa viacerých kritérií. Medzi bežné faktory patria:

• Kľúčové parametre, ako je veľkosť jeho kľúča a veľkosť bloku, ktoré oba poskytujú hornú hranicu bezpečnosti šifry.
• Odhadovaná úroveň bezpečnosti, ktorá je založená na dôvere získanej v návrhu blokovej šifry po tom, čo v priebehu času z veľkej časti odolal veľkému úsiliu v kryptoanalýze, matematickej spoľahlivosti návrhu a existencii praktických alebo certifikačných útokov.
• Zložitosť šifry a jej vhodnosť na implementáciu v hardvéri alebo softvéri . Hardvérové implementácie môžu merať zložitosť z hľadiska počtu brán alebo spotreby energie, čo sú dôležité parametre pre zariadenia s obmedzenými zdrojmi.
• Výkon šifry z hľadiska priepustnosti spracovania na rôznych platformách, vrátane požiadaviek na pamäť .
• Náklady na šifru, ktorá sa vzťahuje na licenčné požiadavky, ktoré sa môžu vzťahovať na práva duševného vlastníctva .
• Flexibilita šifry, ktorá zahŕňa jej schopnosť podporovať viacero veľkostí kľúčov a dĺžok blokov.

Pozoruhodné blokové šifry

Lucifer / DES

Lucifer sa vo všeobecnosti považuje za prvú civilnú blokovú šifru vyvinutú v IBM v 70. rokoch minulého storočia na základe práce Horsta Feistela . Revidovaná verzia algoritmu bola prijatá ako federálny štandard spracovania informácií vlády USA: FIPS PUB 46 Data Encryption Standard (DES). Vybral ho Národný úrad pre štandardy USA (NBS) po verejnej výzve na predkladanie návrhov a niektorých vnútorných zmenách zo strany NBS (a prípadne NBÚ ). DES bol verejne vydaný v roku 1976 a bol široko používaný.

DES bol navrhnutý tak, aby, okrem iného, odolal istému kryptanalytickému útoku, o ktorom vedela NSA a znovu ho objavila IBM, hoci verejne neznámy, kým ho znovu neobjavili a nezverejnili ho Eli Biham a Adi Shamir koncom osemdesiatych rokov. Táto technika sa nazýva diferenciálna kryptanalýza a zostáva jedným z mála všeobecných útokov proti blokovým šifrám; lineárna kryptoanalýza je ďalšou, ale mohla byť neznáma dokonca ani NSA, pred jej zverejnením Mitsuru Matsui . DES podnietil veľké množstvo ďalších prác a publikácií v oblasti kryptografie a kryptoanalýzy v otvorenej komunite a inšpiroval mnoho nových návrhov šifry.

DES má veľkosť bloku 64 bitov a veľkosť kľúča 56 bitov. 64-bitové bloky sa stali bežnými v návrhoch blokových šifier po DES. Dĺžka kľúča závisela od viacerých faktorov vrátane vládneho nariadenia. Veľa pozorovateľov  v sedemdesiatych rokoch poznamenal, že 56-bitová dĺžka kľúča používaná pre DES bola príliš krátka. Postupom času sa ukázala jeho nedostatočnosť, najmä potom, čo nadácia Electronic Frontier Foundation v roku 1998 demonštrovala stroj na špeciálne účely navrhnutý na prelomenie DES . Rozšírenie k DES, Triple DES, trikrát zašifruje každý blok buď dvoma nezávislými kľúčmi (112-bitový kľúč a 80-bitové zabezpečenie) alebo tromi nezávislými kľúčmi (168-bitový kľúč a 112-bitové zabezpečenie). Bol široko prijatý ako náhrada. Od roku 2011 sa trojkľúčová verzia stále považuje za bezpečnú, hoci štandardy Národného inštitútu pre štandardy a technológie (NIST) už nepovoľujú používanie dvojkľúčovej verzie v nových aplikáciách z dôvodu jej 80-bitovej úrovne zabezpečenia.

IDEA

International Data Encryption Algorithm ( IDEA ) je bloková šifra, ktorú navrhli James Massey z ETH Zurich a Xuejia Lai ; prvýkrát bol opísaný v roku 1991 ako zamýšľaná náhrada za DES.

IDEA pracuje na 64-bitových blokoch s použitím 128-bitového kľúča a pozostáva zo série ôsmich identických transformácií (kolo) a výstupnej transformácie (polovičné kolo). Procesy šifrovania a dešifrovania sú podobné. IDEA odvodzuje veľkú časť svojej bezpečnosti prekladaním operácií z rôznych skupín – modulárne sčítanie a násobenie a bitové exkluzívne alebo (XOR) – ktoré sú v určitom zmysle algebraicky „nekompatibilné“.

Dizajnéri analyzovali IDEA, aby zmerali jej silu proti diferenciálnej kryptoanalýze a dospeli k záveru, že je za určitých predpokladov imúnna. Neboli zaznamenané žiadne úspešné lineárne alebo algebraické nedostatky. Od roku 2012, najlepší útok, ktorý sa vzťahuje na všetky kľúče, dokáže prelomiť plnú 8,5-kolovú šifru IDEA použitím úzkeho biklikového útoku asi štyrikrát rýchlejšie ako hrubou silou.

RC5

Jedno kolo (dve polkolá) blokovej šifry RC5

RC5 je bloková šifra navrhnutá Ronaldom Rivestom v roku 1994, ktorá má na rozdiel od mnohých iných šifier variabilnú veľkosť bloku (32, 64 alebo 128 bitov), veľkosť kľúča (0 až 2040 bitov) a počet kôl (0 až 255). Pôvodným navrhovaným výberom parametrov bola veľkosť bloku 64 bitov, 128-bitový kľúč a 12 kôl.

Kľúčovou vlastnosťou RC5 je použitie rotácií závislých od údajov; jedným z cieľov RC5 bolo podnietiť štúdium a vyhodnotenie takýchto operácií ako kryptografického primitíva. RC5 tiež pozostáva z množstva modulárnych doplnkov a XOR. Všeobecná štruktúra algoritmu je sieť podobná Feistelovi . Rutiny šifrovania a dešifrovania môžu byť špecifikované v niekoľkých riadkoch kódu. Harmonogram kľúča je však zložitejší a rozširuje kľúč pomocou v podstate jednosmernej funkcie s binárnymi expanziami e a zlatého rezu ako zdrojmi „ čísel nič v rukáve “. Príťažlivá jednoduchosť algoritmu spolu s novosťou rotácií závislých od údajov urobili z RC5 atraktívny predmet štúdia pre kryptoanalytikov.

12-kolový RC5 (so 64-bitovými blokmi) je náchylný na diferenciálny útok pomocou 2 ⁴⁴ vybraných otvorených textov. Ako dostatočná ochrana sa odporúča 18–20 nábojov.

Rijndael / AES

Šifra Rijndael vyvinutá belgickými kryptografmi Joan Daemen a Vincent Rijmen bola jedným z konkurenčných návrhov, ktoré nahradili DES. Vyhrala 5-ročnú verejnú súťaž o AES (Advanced Encryption Standard).

AES, prijatý NIST v roku 2001, má pevnú veľkosť bloku 128 bitov a veľkosť kľúča 128, 192 alebo 256 bitov, zatiaľ čo Rijndael môže byť špecifikovaný s veľkosťou bloku a kľúča v akomkoľvek násobku 32 bitov, s minimom 128. bitov. Veľkosť bloku má maximálne 256 bitov, ale veľkosť kľúča nemá žiadne teoretické maximum. AES funguje na 4×4 stĺpcovo-hlavnej matici bajtov, ktorá sa nazýva stav (verzie Rijndael s väčšou veľkosťou bloku majú v stave ďalšie stĺpce).

Blowfish

Blowfish je bloková šifra, ktorú v roku 1993 navrhol Bruce Schneier a je zahrnutá do veľkého množstva šifrovacích súprav a šifrovacích produktov. Blowfish má 64-bitovú veľkosť bloku a variabilnú dĺžku kľúča od 1 bitu až po 448 bitov. Je to 16- kolová Feistelova šifra a používa veľké S-boxy závislé od kľúča. Medzi pozoruhodné vlastnosti dizajnu patria kľúčovo závislé S-boxy a veľmi zložitý rozvrh kľúčov .

Bol navrhnutý ako všeobecný algoritmus určený ako alternatíva k starnúcemu DES a bez problémov a obmedzení spojených s inými algoritmami. V čase, keď bol Blowfish vydaný, mnoho iných návrhov bolo vlastníctvom, zaťažené patentmi alebo boli obchodným/vládnym tajomstvom. Schneier uviedol, že „Blowfish je nepatentovaný a zostane ním vo všetkých krajinách. Algoritmus je týmto zverejnený a môže ho voľne používať ktokoľvek." To isté platí pre Twofish, nástupnícky algoritmus od Schneiera.

Zovšeobecnenia

Vylepšiteľné blokové šifry

M. Liskov, R. Rivest a D. Wagner opísali zovšeobecnenú verziu blokových šifier nazývanú „vylepšiteľné“ blokové šifry. Vylepšená bloková šifra akceptuje druhý vstup nazývaný tweak spolu so svojím obvyklým vstupom otvoreného textu alebo šifrovaného textu. Tweak spolu s kľúčom vyberá permutáciu vypočítanú šifrou. Ak je zmena vylepšenia dostatočne ľahká (v porovnaní s zvyčajne pomerne nákladnou operáciou nastavenia kľúča), potom budú možné niektoré zaujímavé nové prevádzkové režimy. Článok teórie šifrovania disku popisuje niektoré z týchto režimov.

Šifrovanie zachovávajúce formát

Blokové šifry tradične fungujú v binárnej abecede . To znamená, že vstupom aj výstupom sú binárne reťazce pozostávajúce z n núl a jednotiek. V niektorých situáciách si však možno želať mať blokovú šifru, ktorá funguje nad nejakou inou abecedou; napríklad zašifrovanie 16-miestneho čísla kreditných kariet takým spôsobom, že zašifrovaný text je tiež 16-miestnym číslom, môže uľahčiť pridanie šifrovacej vrstvy do staršieho softvéru. Toto je príklad šifrovania so zachovaním formátu . Všeobecnejšie povedané, šifrovanie so zachovaním formátu vyžaduje kľúčovanú permutáciu v nejakom konečnom jazyku . Vďaka tomu sú šifrovacie schémy zachovávajúce formát prirodzeným zovšeobecnením (vylepšiteľných) blokových šifier. Na rozdiel od toho tradičné šifrovacie schémy, ako je CBC, nie sú permutáciami, pretože rovnaký otvorený text môže šifrovať do viacerých rôznych šifrovaných textov, a to aj pri použití pevného kľúča.

Vzťah k iným kryptografickým primitívom

Blokové šifry je možné použiť na vytvorenie ďalších kryptografických primitív, ako sú tie nižšie. Aby boli tieto ďalšie primitívy kryptograficky bezpečné, je potrebné dbať na ich správne zostavenie.

• Prúdové šifry je možné zostaviť pomocou blokových šifier. Režim OFB a režim CTR sú blokové režimy, ktoré menia blokovú šifru na prúdovú šifru.
• Kryptografické hašovacie funkcie je možné zostaviť pomocou blokových šifier. Popis niekoľkých takýchto metód nájdete vo funkcii jednosmernej kompresie . Metódy sa podobajú režimom blokovej šifry, ktoré sa zvyčajne používajú na šifrovanie.
• Kryptograficky bezpečné generátory pseudonáhodných čísel (CSPRNG) môžu byť zostavené pomocou blokových šifier.s.
• Bezpečné pseudonáhodné permutácie ľubovoľne veľkých konečných množín možno skonštruovať pomocou blokových šifier; pozri Šifrovanie so zachovaním formátu .
• Verejne známa nepredvídateľná permutácia kombinovaná s vybielením kľúča je dostatočná na vytvorenie blokovej šifry – ako je napríklad jednokľúčová Even-Mansourova šifra, možno najjednoduchšia možná preukázateľne bezpečná bloková šifra.
• Overovacie kódy správ (MAC) sú často zostavené z blokových šifier. CBC-MAC, OMAC a PMAC sú také MAC.
• Overené šifrovanie je tiež postavené z blokových šifier. To znamená šifrovať aj MAC súčasne. To znamená poskytnúť dôvernosť aj autentifikáciu . CCM, EAX, GCM a OCB sú takéto overené režimy šifrovania.

Rovnako ako blokové šifry možno použiť na vytváranie hašovacích funkcií, ako napríklad SHA-1 a SHA-2, sú založené na blokových šifrách, ktoré sa tiež používajú samostatne ako SHACAL, hašovacie funkcie možno použiť na vytváranie blokových šifier. Príkladmi takýchto blokových šifier sú BEAR a LION .

Literatúra

• KNUDSEN, Lars R.; ROBSHAW, Matthew. The Block Cipher Companion. [s.l.] : Springer Berlin Heidelberg, 2011. 270 s. ISBN 978-3-642-17341-7.

Pozri aj

• Súhrn zabezpečenia šifry
• Témy v kryptografii
• XOR šifra

Externé odkazy

• Zoznam mnohých symetrických algoritmov, z ktorých väčšina sú blokové šifry.
• Salónik s blokovou šifrou
• Čo je bloková šifra? z RSA FAQ
• Bloková šifra založená na zlatých sekvenciách a chaotickom logistickom stanovom systéme