Aplikace kombinatoriky v kryptologii

Ve stejnojmenném projektu, s nímž jsem se letos v květnu stala jednou ze tří laureátek stipendia Pro ženy ve vědě, se věnuji dvěma aktuálním tématům současné kryptologie: hašovacím funkcím a generátorům náhodných čísel. V článku blíže popisuji první oblast, tedy ditherované hašovací funkce, pro které jsem našla i spolupracovníky – studenta Fakulty jaderné a fyzikálně inženýrské ČVUT v Praze Jana Legerského a tým prof. Juhy Kortelainena z univerzity v Oulu (Finsko). Aktuálnost tématu ilustruje i skutečnost, že National Institute of Standards and Technology (NIST) vyhlásil v říjnu 2012 vítěze několikaleté soutěže o nový hašovací standard – algoritmus Keccak.

Foto: Stanislava Kyselová, Akademický bulletin
Autorka příspěvku Ľubomíra Balková při přebírání ceny pro vítězku stipendia L’Oréal Pro ženy ve vědě.

Hašovací funkce jsou zázračné: z dlouhých zpráv vyrábějí jejich krátké otisky – anglicky hash. Chovají se jako tzv. náhodná orákula – otisky jsou tedy jakoby náhodně losovány. Funkce musí být dále jednocestné, tj. musí splňovat, že hašování (získávání otisku zprávy), je rychlé, zatímco k danému otisku je výpočetně nemožné najít zprávu, jež by tento otisk měla. Podle konkrétní aplikace následně klademe na hašovací funkce další požadavky. Ukazuje se, že iterativní prin­cip, na kterém se většina současných hašovacích funkcí zakládá, není dostatečně silný proti útoku na druhý vzor a multikolize. Ronald Rivest navrhl jako jedno z řešení metodu ditherování. V projektu se zabýváme studiem jejích výhod a nevýhod a využíváme výsledků z kombinatoriky na slovech pro konstrukci vhodných ditheračních posloupností.

Hašovací funkce

Hašovací funkce f: {0,1}^N →  {0,1}ⁿ je zobrazení přiřazující zprávě M délky maximálně N řetězec pevně dané délky n, kde N je mnohem větší než n a má následující vlastnosti:
• Je snadné spočítat haš (otisk) zprávy  f(M).
• Je odolná vůči nalezení vzoru: k dané haši htarget je výpočetně nemožné nalézt zprávu M takovou, že f(M) = h_target.
• Je odolná vůči nalezení druhého vzoru: k dané zprávě Mtarget je výpočetně nemožné nalézt jinou zprávu M takovou, že f(M) =  f(M_target).
• Je odolná vůči kolizi: je výpočetně nemožné nalézt různé zprávy M a M’ takové, že  f(M) = f(M’).
• Chová se jako náhodné orákulum: při jakékoli změně vstupu se na výstupu změní každý bit s pravděpodobností 50 %.

Z vlastností hašovací funkce je zřejmé, že není pros­tá a že se velké množství zpráv zobrazí na stejnou haš (průměrně 2^N–n). Přesto ale požadujeme, aby bylo výpočetně nemožné najít vzor, druhý vzor i kolizi, což znamená, že současné počítače nesmí umět takovou úlohu řešit v reálném čase. Teoretická složitost nalezení vzoru i druhého vzoru je úměrná 2ⁿ volání hašovací funkce, zatímco složitost nalezení kolize je úměrná 2ⁿ² volání hašovací funkce. Po hašovacích funkcích požadujeme, aby byla složitost nalezení vzoru, druhého vzoru i kolize blízká složitosti teoretické.
Pokud je jednodušší najít druhý vzor, může dojít i k vážnému zneužití. Digitální podepisování chápe haš jako jednoznačnou identifikaci dokumentu, podobně jako je jedinečný otisk prstu. Právě haš zprávy se podepisuje. Pokud by bylo možné najít k haši podepsané zprávy smysluplný druhý vzor, pak by digitální podpis nebyl spolehlivý.

V roce 1996 prezentoval Hans Dobbertin na konferenci FSE 1996 metodu nalézání kolizí u algoritmu MD4.

Pokud funkce není bezkolizní, nelze ji považovat za kryptograficky bezpečnou. Obrázek zobrazuje dva dokumenty se stejnou haší (to je umožněno zdánlivě bezvýznamnými znaky v textu reprezentovanými hvězdičkami). Jeden z nich by mohl být podstrčen k podpisu a druhý (falešný) dokument by poté také měl stejný podpis.

Hašovací funkce se využívají v mnoha situacích.
Podle využití se liší nároky, které na ně klademe: největší požadavky na bezkoliznost a odolnost vůči hledání druhého vzoru se kladou v kryptografii, v jiných oblastech je spíše hlavní rychlost hašování. Vyjmenujme alespoň několik použití: autentizace dat, digitální podpisy, ověřování a ukládání hesel, identifikace dat nebo souborů, hašovací tabulky, generátory pseudonáhodných čísel, prokazování znalosti nebo autorství.

Digitální podepisování
Podepisovací algoritmus je časově náročná procedura. Proto se zpráva nejprve zahašuje a teprve haš zprávy se podepisuje. Z velkých dat vytváří hašovací funkce jejich identifikátor (říkáme také digitální otisk – digital fingerprint – nebo výtah zprávy – message digest). V mnoha zemích stojí digitální otisky na úrovni otisků prstů pro identifikaci lidí; při digitálním podpisu zprávy proto stačí podepsat její haš. Díky odolnosti vůči hledání druhého vzoru nelze pak takovou zprávu zfalšovat, tj. nalézt jinou zprávu se stejnou haší, a tedy stejným podpisem.

Autentizace uživatele
Hašování se používá v elektronické komunikaci k ověření totožnosti uživatele. Odesílatel k otevřené zprávě přiloží ještě text zprávy zahašovaný spolu s klíčem, který sdílí s adresátem. Ten po přijetí zprávu také zahašuje se sdíleným klíčem a ověří totožnost haše od odesílatele s tou, kterou vytvořil. Pokud by útočník změnil text zprávy, haše by se neshodovaly (klíčem totiž útočník nedisponuje), a tím by byla manipulace zprávy odhalena.
Pokud jde o pouhé ověření totožnosti uživatele bez posílání zprávy, dotazovatel (server) odešle uživateli výzvu – challenge, kterou uživatel opět spolu se sdíleným klíčem zahašuje, a haš odešle zpět.

Shodnost dat
Dalším využitím hašování je kontrola kopírovaných dat, jde tedy o ochranu před náhodnými chybami. K tomu se využívají speciální hašovací funkce, na které se nekladou zvláštní bezpečnostní nároky. Takovou je například CRC – Cyclic Redundancy Check. Funkce vytváří kontrolní součet, který je vzhledem k velikosti souboru miniaturní, ale již při nepatrném rozdílu v souboru se změní. Srovnává se tedy kontrolní součet původního souboru a přeneseného. V případě shody jsou téměř jistě soubory identické, v případě neshody jednoznačně odlišné.

Ověřování a ukládání hesel
Místo hesel se ukládají jejich haše. Když je nabourán systém, nejsou hesla díky jednocestnosti hašovací funkce kompromitována. Během přihlašování do systému se po síti přenáší pouze vypočtená hodnota haše, která se porovnává s uloženou hodnotou.

Konstrukce hašovacích funkcí

Prozatím jsme se dozvěděli, jaké neskromné nároky klademe na hašovací funkce. Je tedy přirozené se ptát, jak takové zázračné funkce konstruovat. Nejčastější konstrukcí je iterativní Merkleovo-Damgårdovo paradigma založené na použití kompresní funkce F. Název nese po tvůrcích, kteří je v roce 1989 navrhli nezávisle na sobě na stejné konferenci CRYPTO ’89.
Haš  f(M) zprávy M délky menší než N = 2^t – 1 spočteme následovně:
1. Rozsekáme zprávu M na bloky velikosti m:
M₁M₂…M’_ℓ–1M’_ℓ ‖1‖ 00…0 ‖ length(M).

Do posledního bloku jsme doplnili jedničku a nuly, aby posledních t bitů bylo vyhrazeno na binární zápis délky zprávy. Takové úpravě se říká Merkleovo-Damgårdovo zesílení.

2. Iterujeme ℓ-krát kompresní funkci
F (h_i–1, M_i):{0,1}ⁿ_x{0,1}^m→ {0,1}ⁿ
a vyrábíme tak průběžné haše (kontexty) h_i:
2. h₀ = IV
2. h_i = F(h_i–1, M_i),
2. přičemž h₀ je nějaká pevně daná inicializační hodnota IV.

3. Získáme otisk:
2.  f(M) = g(h_ℓ),
2. za funkci g se často volí identita.

V čem spočívá výhoda Merkleova-Damgårdova schématu? Autoři dokázali, že je-li použita jejich konstrukce, odolnost kompresní funkce F proti kolizím implikuje odolnost celé hašovací funkce f proti kolizím. Hlídat odolnost kompresní funkce proti kolizím je daleko jednodušší, protože taková funkce zkracuje bloky délky n + m na bloky délky n, zatímco hašovací funkce komprimuje zprávy délky až N = 2^t – 1 na haše délky n. Pro konkrétní představu uveďme, že při použi­tí hašovací funkce SHA512 je t = 128, m = 1024 a n = 512 bitů.

Slabiny iterativní konstrukce
Dosud nejčastěji užívané hašovací funkce MD5, SHA-1 a SHA-2 využívají Merkleovo-Damgårdovo paradigma a také tzv. Daviesovu-Meyerovu konstrukci, která se zakládá na aplikaci blokové šifry. Slabinou Daviesovy-Meyerovy konstrukce je snadné hledání pevných bodů: ke každé zprávě M umíme najít právě jeden kontext h tak, že h = F(h, M). Na základě této slabiny nalezli Richard D. Dean, John Kelsey a Bruce Schneier útok na druhý vzor pomocí rozšiřitelné zprávy – expandable message, což je struktura umožňující produkovat zprávy délky v daném rozmezí se stejnou poslední průběžnou haší. Konstrukce nezahrnuje Merkleovo-Damgårdovo zesílení, a proto nevznikají přímo kolize zpráv; rozšiřitelnou zprávu můžeme použít k hledání druhého vzoru napojením na určité místo cílové zprávy (detailní popis útoku viz Balková L., Legerský J., Hašovací funkce a kombinatorika na slovech, přijato do Pokroků matematiky, fyziky a astronomie, 2013).

Ditherování

K obraně proti útoku pomocí rozšiřitelné zprávy navrhl Ronald Rivest metodu ditherování, která souvisí s kombinatorikou na slovech.
Název je vypůjčen ze zpracování obrazu, kde znamená simulaci barev, jež nemáme, náhodným mícháním pixelů podobných barev s cílem odstranit nežádoucí linie. R. Rivest navrhl následující metodu k vylepšení odolnosti hašovací funkce proti útoku na druhý vzor.
Při každé iteraci přidáváme do vstupu kompresní funkce písmeno di nekonečného slova d:
h_i = F(h_i–1, M_i, d_i).

Je-li nekonečné slovo d bez čtverců, tedy neobsahuje dva stejné po sobě jdoucí bloky, pak ditherování znemožní útok pomocí rozšiřitelné zprávy. Jak již to v kryptologii bývá, přišli John Kelsey, Adi Shamir a kolektiv s útokem na ditherovanou hašovací funkci. Zobecnili známý útok pomocí tzv. kolizního stromu i pro ditherované hašovací funkce; ukázalo se, že složitost útoku se zvětší úměrně komplexitě použitého ditheračního slova (komplexita udává počet faktorů dané délky, které nekonečné slovo obsahuje). Jde tedy o úspěšný útok proti konkrétním Rivestovým návrhům ditherovaných hašovacích funkcí, ve kterých pracoval s ditheračním slovem majícím lineární komplexitu.
Pokud ovšem zvolíme ditherační slovo s vysokou komplexitou (takovým konstrukcím se právě s využitím znalostí z kombinatoriky na slovech věnujeme) nebo velkou abecedou – například ditherování čítačem v hašovací funkci HAIFA, znemožníme útok pomocí kolizního stromu a znesnadníme i některé další útoky.

ĽUBOMÍRA BALKOVÁ,
Fakulta jaderné a fyzikálně inženýrská,
České vysoké učení technické v Praze