Lekce 1 - Úvod do šifrování a blokové šifry

Ač o nich v mnoha případech ani nevíme, šifrování, hashování a příbuzné činnosti patří mezi každodenní chleba našich počítačů. A i kvůli nim se jedná o nepostradatelné činnosti, pokud chceme v dnešní době zajistit alespoň nějakou úroveň bezpečnosti a soukromí. Naštěstí máme k dispozici řadu knihoven a programů, které nám s těmito úkoly značně pomohou, aniž bychom museli znát teorii kryptografie.

Tento seriál si klade za cíl část této teorie (a praxe) přiblížit a ukázat, na jakých předpokladech dnes stavíme například mechanismy bezpečné komunikace. Ač existuje mnoho knihoven, které kryptografické mechanismy implementují dobře, je rozumné trochu vědět, jak to funguje "pod pokličkou", protože i při použití dobrého šifrování lze snadno udělat hloupost, která jeho bezpečnost degraduje či úplně zruší.

Podobně jako v jiných oborech, i v kryptografii je snaha vystačit s málem. To znamená mít k dispozici malé množství primitiv s určitými (ideálně dokazatelnými) vlastnostmi, ze kterých sestavíme složitější věci, jako například šifrovaný e-mail. V tomto seriálu se na tato primitiva podíváme zblízka.

Bloková šifra

Bloková šifra jednoznačně patří mezi nejčastěji používaná primitiva. Jejím cílem je při zadaném klíči změnit pro všechny čitelnou zprávu (otevřený text, plaintext) do tvaru nečitelného pro všechny (vyjma vlastníků klíče). Tento nečitelný tvar se označuje jako šifrový text (ciphertext). Proces převodu otevřeného textu na šifrový nazýváme šifrováním, opačný proces dešifrováním.

Z pohledu teorie blokovou šifru reprezentujeme tzv. pseudonáhodnou permutací (pseudorandom permutation, PRP). Srozumitelně řečeno to znamená, že:

• převádí celá čísla z určitého rozsahu na jiná ve stejném rozsahu,
• mapuje způsobem jedna ku jedné, čímž je garantována existence obrácené permutace pro dešifrování,
• je (pseudo)náhodná, takže ani ze znalosti mnoha párů otevřeného a šifrového textu nejsme schopni dopočítat další takové páry či dokonce odvodit klíč.

PRP obvykle pracují s čísly v intervalu <0; 2ⁿ - 1>, tedy převádí libovolná n-bitová data na jiná. Hodnota n se také označuje jako velikost bloku. Šifrování a dešifrování si můžeme názorně ukázat na tomto schématu:

Základní pojmy.

Zde můžeme oprávněně namítnout, že kromě otevřeného textu do blokové šifry musíme dodat i tzv. klíč, který je v tomto případě tvořen (pseudo)náhodnou posloupností k bitů (např. 128, 192 či 256 pro AES) a že se bloková šifra stává PRP až v okamžiku, kdy jí nějaký klíč přiřadíme. To je pravda. Na klíč můžeme také nahlížet jako na jakýsi index, jímž určíme, kterou z PRP definovaných algoritmů blokové šifry budeme používat.

V praxi máme problémy zejména s požadavkem (pseudo)náhodnosti. Jak můžeme o nějaké permutaci obecně dokázat, že je (pseudo)náhodná? V zásadě nijak. Můžeme samozřejmě provést různé statistické testy, kterými ověříme, že se pseudonáhodně chová, ale to nám nedává žádné teoretické garance. Dokud se nám daný algoritmus nepodaří prolomit (dešifrovat bez znalosti klíče), předpokládáme, že se chová jako pseudonáhodná permutace, o které víme, že je pro účely šifrování bezpečná.

Nabízí se otázka, proč naší bezpečnost nezaložíme na mechanismu, jehož teoretická neprolomitelnost je dokázána. Potíž spočívá ve faktu, že mnoho prokazatelně bezpečných konceptů neznáme a i ty známé často mají vlastnosti, které je dělají pro každodenní použití nepřijatelnými. Ano, známe šifru, kterou nelze prolomit ani s nekonečným výpočetním výkonem, ale vzhledem k tomu, že klíč pro ni musí být náhodný a stejně dlouhý jako šifrovaná zpráva, pro běžné použití se nehodí.

Jednou z vlastností související s (pseudo)náhodností, kterou by každá bloková šifra měla disponovat je IND-CPA. Ta nám říká, že pokud nám útočník dá dva jím vybrané otevřené texty, my je oba zašifrujeme jemu neznámým klíčem a vrátíme mu náhodný z nich, není schopen s rozumnou pravděpodobností (výrazně odlišnou od 50 %) poznat, ke které zprávě přísluší. Podobných vlastností existuje celá řada a díky nim dokážeme říci zajímavé věci o složitějších schématech sestavených z primitiv jako je právě bloková šifra.

Praktická implementace

Ač to tak z dosavadních informací nevypadá, blokové šifry se používají k ochraně velkého množství dat, což na jejich implementaci klade požadavek rychlosti. Z tohoto důvodu se v jejich algoritmech používají operace jednoduché pro dnešní procesory (či snadno implementovatelné v hardware):

• sčítání,
• bitové operace (zejména XOR), posuny a rotace,
• modulo 2ⁿ,
• indexování v (malých) polích.

Malá pole zmíněná v poslední odrážce se označují jako S-boxy (substituční tabulky) a jejich velikost se obvykle pohybuje do 16 (2⁴) položek. Používají se jako úsporný způsob pro implementaci pseudonáhodných funkcí operujících nad malým počtem bitů. Efektivní je také jejich "výpočet", vstupní data jsou použita jako index do pole.

Dalším běžným rysem blokových šifer je opakované vstupování šifrovaných (či dešifrovaných) dat do hlavního algoritmu. Bloková šifra tedy pracuje v iteracích, tzv. rundách. Například šifra definovaná standardem AES použivá 10 rund v případě 128bitového klíče. Návrh blokové šifry totiž neznamená pouze vytvořit tak složitou permutaci, že ji nikdo neprohlédne. Permutace musí být rozumně složitá, abychom k dešifrování museli znát klíč. Zároveň ji ale chceme umět alespoň trochu analyzovat, abychom o ní mohli případně zjistit různé zajímavé vlastnosti.

Feistalova síť

Feistalova síť představuje teoretický koncept, který nám ukazuje, jakým způsobem můžeme vytvořit hlavní algoritmus blokové šifry za předpokladu, že jsme si vymysleli malou pseudonáhodnou funkci (PRF). Přitom lze dokázat, že šifra založená na Feistalově síti je IND-CPA, pokud je počet rund alespoň 3. Zajímavé také je, že pokud data do Feistalovy sítě pošleme z opačného směru, provádíme dešifrování. Všimněme si také, že naše malá PRF nemusí být permutací (nemusí existovat opačná funkce). Feistalova síť vlastně z pseudonáhodné funkce F pracující s n bity vytvoří pseudonáhodnou funkci pracující s 2n bity.

Feistalova síť provádí následující kroky:

• rozdělí vstupní data na dvě stejně velké poloviny A a B,
• na A přixoruje hodnotu B, na kterou je předtím aplikována naše funkce F,
• pošle na výstup (B, A´), kde A´ vzniklo z A v předchozím kroku.

Jedna runda Feistalovy sítě.

Kromě dat B do naší funkce F vstupuje i hodnota k_i. Ta je odvozená z klíče pro šifru (K) a liší se podle čísla rundy. Označuje se také jako rundovní klíč, proces jeho získání se nazývá expanze klíče.

Pseudokód pro 10ti rundovou šifru založenou čistě na Feistalově síti by mohl vypadat třeba 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žití v konkrétních šifrách a implementacích se drobně liší, a to nejen ve zvolené pseudonáhodné funkci F. Celou expanzi klíče například můžeme provést ještě před zahájením vlastního šifrování či aplikovat další transformace na šifrovaná data.

Zarovnání (padding)

Bloková šifra tedy dokáže zajistit ukrytí našich nejhlubších tajemství, ale bohužel jen těch velikostí přesně odpovídajících jednomu bloku, tedy například 16ti bajtů v případě AES. Co když ale chceme ukrýt i tajemství menšího rozsahu?

Řešení tohoto problému je celkem přímočaré. Doplníme naše tajemství před šifrováním tak, aby jeho délka odpovídala velikosti bloku a abychom po dešifrování poznali, kolik bajtů musíme odebrat. Takto přidaná data se nazývají zarovnání (padding) a mají různé podoby. Například můžeme naše tajemství doplnit bajty, kde každý bude udávat, kolik jsme jich přidali. Má-li tedy naše tajemství velikost 10 bajtů a blok má délku 16 bajtů, doplníme 6 bajtů o hodnotě 6:

Zarovnání 10bajtového tajemství na velikost bloku (16 bajtů).

Chceme-li takovým způsobem zarovnat i prázdné tajemství (0 bajtů), celý blok vyplníme bajty o hodnotě 16.

Existují samozřejmě i způsoby, jak ukrýt tajemství větší než jeden blok. Označujeme je jako módy blokových šifer a s některým módem se setkáme v dalším díle tohoto seriálu.

V další lekci, Ukázka jednoduché šifrace textu Albertiho šifra, si ukážeme šifru Albertiho.