1. diel - Úvod do šifrovanie a blokové šifry

Hoci o nich v mnohých prípadoch ani nevieme, šifrovanie, hashovanie a príbuzné činnosti patrí medzi každodenné chleba našich počítačov. A aj kvôli nim sa jedná o nepostrádateľné činnosti, ak chceme v dnešnej dobe zabezpečiť aspoň nejakú úroveň bezpečnosti a súkromia. Našťastie máme k dispozícii rad knižníc a programov, ktoré nám s týmito úlohami značne pomôžu, bez toho aby sme museli poznať teóriu kryptografie.

Tento seriál si kladie za cieľ časť tejto teórie (a prax) priblížiť a ukázať, na akých predpokladoch dnes staviame napríklad mechanizmami bezpečnej komunikácie. Hoci existuje veľa knižníc, ktoré kryptografické mechanizmy implementujú dobre, je rozumné trochu vedieť, ako to funguje "pod pokrievkou", pretože aj pri použití dobrého šifrovania možno ľahko urobiť hlúposť, ktorá jeho bezpečnosť degraduje či úplne zruší.

Podobne ako v iných odboroch, aj v kryptografiu je snaha vystačiť s málom. To znamená mať k dispozícii malé množstvo primitív s určitými (ideálne dokázateľnými) vlastnosťami, z ktorých zostavíme zložitejšie veci, ako napríklad šifrovaný e-mail. V tomto seriáli sa na tieto primitíva pozrieme zblízka.

Bloková šifra

Bloková šifra jednoznačne patrí medzi najčastejšie používaná primitíva. Jej cieľom je pri zadanom kľúči zmeniť pre všetky čitateľnú správu (otvorený text, plaintext) do tvaru nečitateľného pre všetky (okrem vlastníkov kľúča). Tento nečitateľný tvar sa označuje ako šifrový text (ciphertext). Proces prevodu otvoreného textu na šifrový nazývame šifrovaním, opačný proces dešifrovaním.

Z pohľadu teórie blokovú šifru reprezentujeme tzv. Pseudonáhodnej permutácií (pseudorandom permutation, PRP). Zrozumiteľne povedané to znamená, že:

• prevádza celé čísla z určitého rozsahu na iné v rovnakom rozsahu,
• mapuje spôsobom jedna ku jednej, čím je garantovaná existencie obrátené permutácie pre dešifrovanie,
• je (pseudo) náhodná, takže ani zo znalosti mnohých párov otvoreného a šifrového textu nie sme schopní dopočítať ďalšie takéto páry či dokonca odvodiť kľúč.

PRP zvyčajne pracujú s číslami v intervale <0; 2 ⁿ - 1>, teda prevádza ľubovoľná n-bitová dáta na iné. Hodnota n sa tiež označuje ako veľkosť bloku. Šifrovanie a dešifrovanie si môžeme názorne ukázať na tejto schéme:

Základné pojmy.

Tu môžeme oprávnene namietať, že okrem otvoreného textu do blokovej šifry musíme dodať aj tzv. Kľúč, ktorý je v tomto prípade tvorený (pseudo) náhodnou postupnosťou k bitov (napr. 128, 192 či 256 pre AES) a že sa bloková šifra stáva PRP až v okamihu, keď jej nejaký kľúč priradíme. To je pravda. Na kľúč môžeme tiež vnímať ako akýsi index, ktorým určíme, ktorú z PRP definovaných algoritmov blokovej šifry budeme používať.

V praxi máme problémy najmä s požiadavkou (pseudo) náhodnosti. Ako môžeme o nejakej permutáciu všeobecne dokázať, že je (pseudo) náhodná? V zásade nijako. Môžeme samozrejme vykonať rôzne štatistické testy, ktorými overíme, že sa pseudonáhodnej chová, ale to nám nedáva žiadne teoretické garancie. Kým sa nám daný algoritmus nepodarí prelomiť (dešifrovať bez znalosti kľúča), predpokladáme, že sa správa ako pseudonáhodná permutácie, o ktorej vieme, že je pre účely šifrovania bezpečná.

Ponúka sa otázka, prečo našej bezpečnosť nezaložíte na mechanizme, ktorého teoretická neprolomitelnost je dokázaná. Problém spočíva vo fakte, že veľa preukázateľne bezpečných konceptov nepoznáme a aj tie známe často majú vlastnosti, ktoré ich robia pre každodenné použitie neprijateľnými. Áno, poznáme šifru, ktorú nemožno prelomiť ani s nekonečným výpočtovým výkonom, ale vzhľadom na to, že kľúč pre ňu musí byť náhodný a rovnako dlhý ako šifrovaná správa, pre bežné použitie sa nehodí.

Jednou z vlastností súvisiace s (pseudo) náhodnosti, ktorú by každá bloková šifra mala disponovať je IND-CPA. Tá nám hovorí, že ak nám útočník dá dva ním vybranej otvorené texty, my ich oboch zašifrujeme jemu neznámym kľúčom a vrátime mu náhodný z nich, nie je schopný s rozumnou pravdepodobnosťou (výrazne odlišnú od 50%) spoznať, ku ktorej správe prislúcha. Podobných vlastností existuje celý rad a vďaka nim dokážeme povedať zaujímavé veci o zložitejších schémach zostavených z primitív ako je práve bloková šifra.

Praktická implementácia

Hoci to tak z doterajších informácií nevyzerá, blokové šifry sa používajú na ochranu veľkého množstva dát, čo na ich implementáciu kladie požiadavku rýchlosti. Z tohto dôvodu sa v ich algoritmoch používajú operácie jednoduché pre dnešné procesory (či ľahko implementovateľné v hardware):

• sčítanie,
• bitové operácie (najmä XOR), posuny a rotácie,
• modulo 2 n,
• indexovanie v (malých) poliach.

Malá pole spomínaná v poslednej zarážke sa označujú ako S-boxy (substitučná tabuľky) a ich veľkosť sa obvykle pohybuje do 16 (2 ⁴⁾ položiek. Používajú sa ako úsporný spôsob pre implementáciu pseudonáhodných funkcií operujúcich nad malým počtom bitov. Efektívna je tiež ich "výpočet", vstupné dáta sú použité ako index do poľa.

Ďalším bežným rysom blokových šifier je opakované vstupovanie šifrovaných (či dešifrovaných) dát do hlavného algoritmu. Bloková šifra teda pracuje v opakovaniach, tzv. Rundách. Napríklad šifra definovaná štandardom AES používa v 10 rund v prípade 128-bitového kľúča. Návrh blokové šifry totiž neznamená iba vytvoriť tak zložitú permutáciu, že ju nikto neprehliadne. Permutácie musí byť rozumne zložitá, aby sme na dešifrovanie museli poznať kľúč. Zároveň ju ale chceme vedieť aspoň trochu analyzovať, aby sme o nej mohli prípadne zistiť rôzne zaujímavé vlastnosti.

Feistalova sieť

Feistalova sieť predstavuje teoretický koncept, ktorý nám ukazuje, akým spôsobom môžeme vytvoriť hlavné algoritmus blokovej šifry za predpokladu, že sme si vymysleli malú pseudonáhodnej funkciu (PRF). Pritom možno dokázať, že šifra založená na Feistalově sieti je IND-CPA, ak je počet rund aspoň 3. Zaujímavé tiež je, že ak dáta do Feistalovy siete pošleme z opačného smeru, prevádzame dešifrovanie. Všimnime si tiež, že naša malá PRF nemusí byť permutácií (nemusí existovať opačná funkcia). Feistalova sieť vlastne z pseudonáhodnej funkcie F pracujúci s n bitmi vytvorí pseudonáhodnej funkciu pracujúci s 2n bity.

Feistalova sieť vykonáva nasledujúce kroky:

• rozdelí vstupné dáta na dve rovnako veľké polovice A a B,
• na A prixoruje hodnotu B, na ktorú ich predtým aplikovaná naše funkcie F,
• pošle na výstup (B, A´), kde A´ vzniklo z A v predchádzajúcom kroku.

Jedna runda Feistalovy siete.

Okrem dát B do našej funkcie F vstupuje aj hodnota k_i. Tá je odvodená z kľúča pre šifru (K) a líši sa podľa čísla rundy. Označuje sa tiež ako rundovní kľúč, proces jeho získanie sa nazýva expanzia kľúča.

Pseudokód pre 10tich Rundová šifru založenú čisto na Feistalově sieti by mohol vyzerať napríklad takto:

x = p;
for (i = 0; i < 10; ++i) {
  k_i = expand(k, i);
  (A, B) = x;
  A = A xor F(B, k_i);
  x = (B, A)
}
c = x;

Použitie v konkrétnych šifrách a implementáciách sa nadrobno líšia, a to nielen vo zvolenej pseudonáhodnej funkcii F. Celú expanziu kľúče napríklad môžeme previesť ešte pred zahájením vlastného šifrovanie či aplikovať ďalšie transformácie na šifrované dáta.

Zarovnanie (padding)

Bloková šifra teda dokáže zaistiť ukrytie našich najhlbších tajomstiev, ale bohužiaľ len tých veľkosťou presne zodpovedajúcich jednej bloku, teda napríklad 16 bajtov v prípade AES. Čo keď ale chceme ukryť aj tajomstvo menšieho rozsahu?

Riešenie tohto problému je celkom priamočiare. Doplníme naše tajomstvo pred šifrovaním tak, aby jeho dĺžka zodpovedala veľkosti bloku a aby sme po dešifrovanie poznali, koľko bajtov musíme odstrániť. Takto pridaná dáta sa nazývajú zarovnanie (padding) a majú rôzne podoby. Napríklad môžeme naše tajomstvo doplniť bajty, kde každý bude udávať, koľko sme ich pridali. Ak má teda naše tajomstvo veľkosť 10 bajtov a blok má dĺžku 16 bajtov, doplníme 6 bajtov s hodnotou 6:

Zarovnanie 10bajtového tajomstvo na veľkosť bloku (16 bajtov).

Ak chceme takým spôsobom zarovnať aj prázdne tajomstvo (0 bajtov), celý blok vyplníme bajty o hodnote 16.

Existujú samozrejme aj spôsoby, ako ukryť tajomstvo väčšie ako jeden blok. Označujeme ich ako módy blokových šifier as niektorým módom sa stretneme v ďalšom diele tohto seriálu.

V ďalšej lekcii, Ukážka jednoduchej šifrace textu Albertiho šifra , si ukážeme šifru Albertiho.