Hlavní navigace

Vlastimil Klíma: Zcela nový koncept hašovacích funkcí

13. 11. 2006
Doba čtení: 12 minut

Sdílet

Všechny současné hašovací funkce mají bezpečnostní problémy. Ve světě probíhá intenzivní úsilí k nalezení nového konceptu. Ukazujeme, jak jednoduchá je příčina současných problémů a navrhujeme nový koncept. V tomto příspěvku prezentujeme část výsledků projektu NBÚ Bezpečná hašovací funkce.

Úvod

Je trochu odvážné o tomhle psát pro Root, protože to nemusí být zajímavé. Nový koncept hašovacích funkcí jsme poslali jako příspěvek do mezinárodní kryptologické konference Eurocrypt 2007, ale než se bude konat, uveřejnili jsme jeho rozšířenou část na kryptologickém webu. Český překlad jsme dali k dispozici na naši domácí stránku. V reakcích na aktuálně.cz bylo ale řečeno, že je to úplně stejné, jako by to bylo v rumunštině. Zřejmě proto se nediskutovalo o nových věcech, ale o prolomení MD5 a možnosti jejího zneužití, což je téma, které je zcela mimo současné problémy (tady na Rootu jsme to probírali v březnu). Teď jde o to, jak navrhnout nové hašovací funkce. Pokusíme se tedy velmi stručně prezentovat hlavní myšlenky z nové práce. Jsou velmi jednoduché. Uvidíte sami.

Hašovací funkce

Všechny moderní hašovací funkce rozdělují zprávu do bloků a zpracovávají ji po těchto blocích pomocí kompresní funkce f, viz obr.1. Při hašování tedy vzniká průběžná hašovací hodnota (hi), kterou nazýváme kontext.

Klima - obr 1

Obr.1: Iterativní hašovací funkce

Kompresní funkce f má dva vstupy, starý kontext a aktuální blok zprávy, a vytváří nový kontext, viz obr. 2.

Klima - obr 2

Obr.2: kompresní funkce

Klima - obr 3

Obr.3: Davies-Meyerova a Miyaguchi-Preneelova úprava

Protože hašovací funkce musí zachovávat všechny vlastnosti i při hašování jednoho bloku, můžeme si zkoumání hašovací funkce zjednodušit na jednu aplikaci kompresní funkce, tj. na zkoumání kompresní funkce. Všechny současné hašovací funkce vytváří kompresní funkci z klasické blokové šifry poměrně jednoduchou úpravou. Je to zejména Davies-Meyerova nebo Miyaguchi-Preneelova úprava (obr. 3) nebo některé další navrhované (obr. 4).

Klima - obr 4

Obr.4: Některé úpravy blokové šifry podle [BRS02]

Ve všech těchto případech se vstup do klíče blokové šifry a do otevřeného textu nějak lineárně kombinuje z hodnot kontextu a bloku zprávy a na výstup z blokové šifry se eventuálně také načítá některá nebo obě z těchto hodnot. Tyto úpravy jsou velmi důležité, protože bloková šifra je při pevném klíči permutací, zatímco my potřebujeme, aby kompresní funkce (hašovací funkce) byla náhodným zobrazením a aby nebyla invertibilní. Tu neinvertibilitu potřebujeme proto, aby z hašovacího kódu nešlo určit vzor – hašovanou zprávu. Proto se bloková šifra, která je jinak invertibilní, upravuje těmito úpravami. Všimněte si, že například v populární Davies-Meyerově úpravě jsou správně narušeny obě vlastnosti – i když známe klíč (mi), nemůžeme normálně odšifrovat a získat hi-1.

Proč jsou současné hašovací funkce slabé a nejde to spravit?

Současné hašovací funkce jsou slabé proto, že se snaží v kompresní funkci f, viz obr. 2, použít klasickou blokovou šifru. Je zcela jedno, jakým způsobem, ať slabou nebo silnou, jednoduše nebo složitě, jednonásobně nebo vícenásobně. Klasické blokové šifry byly navrhovány s předpokladem, že útočník nezná šifrovací klíč. Jejich cílem bylo pomocí této neznámé hodnoty utajit způsob převodu otevřeného textu na šifrový a naopak. Jsou to tedy stavební prvky, které spoléhají na něco utajeného. V kompresní funkci však nic utajeného není a útočník zná všechny hodnoty, které do ní vstupují. Může je dokonce volit a libovolně s nimi manipulovat, včetně proměnné, která je klíčem klasické blokové šifry. A to je onen základní a podstatný rozpor.

Jistě, teď namítnete, že přece funguje ta obezlička s načítáním klíče nebo otevřeného textu na výstup, viz obr. 3 a 4. Říkáme ale, že to je základní a hluboký rozpor. Neprojeví se přímo a hned. Je totiž zakuklen do stavby blokové šifry. Konstruktéři měli u blokové šifry prostě základní předpoklad, že útočník všechno zná, a nezná pouze šifrovací klíč. Kryptografové tuto neznalost „zneužívali“ k tomu, aby konstruovali blokové šifry rychlé a bity klíče zpracovávali velmi jednoduše, někdy dokonce vůbec ne. Například u TripleDES není klíč nijak modifikován a je pouze mnohokrát využíván v čisté podobě. U AES je klíč modifikován pouze velmi slabě oproti funkcím, které jsou použity na modifikaci otevřeného textu. Stavba klasické blokové šifry je proto těžce založena na tom, že velká část jeho vstupu (klíč) je útočníkovi neznámá. Žádná klasická bloková šifra nebyla konstruována ani připravována na situaci, kdy útočník zná šifrovací klíč. To by byl nesmysl. A přesto, u hašovacích funkcí je klíč zcela volně útočníkovi dostupný a může si ho volit, modifikovat a dělat si s ním, co chce. Klíčem je většinou totiž zpráva, která se hašuje. Když útočník hledá kolizi nebo vzor, zprávu si může libovolně volit, měnit a tvořit. Manipuluje tedy s klíčem oné blokové šifry podle potřeby. Na to nebyly klasické blokové šifry připraveny a nikdy proti této možnosti chráněny. je u klasických blokových šifer zcela základním výchozím bodem. Pokud odstraníme předpoklad, že útočník nezná klíč, už se nejedná o klasickou blokovou šifru určenou k šifrování. Kdyby někdo chtěl klasickou blokovou šifru použít v hašovací funkci správně, aby byla chráněna i proti útokům ze strany klíče, přeměnil by ji na něco jiného, co má zcela jiné cíle než chránit otevřený text pomocí utajeného klíče. „To něco jiného“ je nové kryptografické primitivum, nový základní stavební prvek, který musíme zkoumat a navrhnout. Musíme také říci, co od něj vlastně očekáváme. Nazýváme ho speciální bloková šifra.

Příčinou problémů řady současných hašovacích funkcí je to, že používají stavební prvek, který byl určen pro řešení problému utajení. I přes to by pravděpodobně bylo možné ho použít ke konstrukci kompresní funkce, ale nelze to současně udělat efektivně, protože ten prvek není primárně konstruován pro použití v kompresní funkci. Protože současné hašovací funkce se snaží být efektivní, dostávají se do rozporu s bezpečností.

Nové kryptografické primitivum

Podíváme-li se na úlohu kompresní funkce f, chceme, aby byla jednosměrná. Tedy jakákoliv klasická bloková šifra zde není vhodná, protože ta umí dešifrovat. Zde musí být použita funkce, která dešifrovat neumí. Nikoli náhodou se dostáváme do blízkosti kryptografie s veřejným klíčem, neboť ta je založena na jednosměrných funkcích se zadními vrátky – útočník dešifrovat neumí, jen majitel privátního klíče (padacích vrátek). Zde však žádná padací vrátka nesmí existovat, neboť v hašovací funkci nesmí být žádný privátní klíč. Bloková šifra dešifrovat umí, proto, jak jsme si řekli, byla různými způsoby modifikována, aby se z ní stala jednocestná funkce i při znalosti klíče. My navrhujeme jinou konstrukci. Vyšli jsme z toho, že znalost klíče nemá poskytnout příliš mnoho informací o otevřeném textu, ideálně žádnou informaci. Jaký zdroj neposkytuje žádnou informaci? Zdroj, který emituje pouze jednu hodnotu, konstantu. Otevřený text musí být tedy konstantní. Pokud bychom navrhli toto primitivum na základě této úvahy, nabízí se konstrukce

f: {0, 1}K → {0, 1}n : k → Ek(Const0)

kde E je vhodná (nikoli klasická, ale speciální) bloková šifra a Const0 konstanta. E nemůže být klasickou blokovou šifrou, protože ty nebyly připraveny a konstruovány tak, aby se používaly ve výše uvedené formě. Vidíme, že speciální bloková šifra formálně nic nešifruje. Má ale v názvu „bloková šifra“, protože ji budeme konstruovat na pomocí technologie (nižších stavebních prvků) blokových šifer.

Druhý problém hašovacích funkcí – teoretické základy a důkazy bezpečnosti

Hlavním problémem je, že žádná bezpečná hašovací funkce (která by byla prakticky využitelná) neexistuje. Například proto, že by měla být bezkolizní, a přitom je jasné, že (má-li být prakticky použitelná) bezkolizní být nemůže. Když bude mít n bitový kód, například 512 bitů, nemohla by hašovat zprávy, které jsou delší než n (512) bitů. Pak to ale není žádná prakticky použitelná hašovací funkce. To samé je s vlastností jednocestnosti. Všechny „důkazy“ jednocestnosti všech používaných hašovacích funkcí jsou založeny na víře, že lidé nebudou schopni invertovat nějakou složitou funkci. Ba co víc, nejsilnější hašovací funkce současnosti (třída SHA-2), jsou založeny na víře, že NSA je navrhla kvalitně. Skutečně, SHA-2 mají punc kvality, i když žádné důkazy bezpečnosti předloženy nebyly. I když existují veřejné studie o bezpečnosti SHA-2, neobsahují potřebné důkazy.

Je to dokonce ještě horší – nejsou známa jejich návrhová kritéria. Jedna z cest jak najít bezpečnou hašovací funkci, byla vyjít z SHA-2 a udělat takové úpravy, které znemožní současné útoky a ještě přidat nějakou rezervu. Nevýhodou SHA-2 však je, že jejich návrhová kritéria NSA tají. Zcela zásadní otázka pak je, jestli se nějakou úpravou místo zesílení nezapříčiní naopak porušení některých návrhových kritérií a v důsledku toho oslabení výsledné funkce. Proto touto cestou se může odpovědně vydat pouze NSA a nikdo jiný.

Přesto mnozí kryptologové věří, že tyto funkce jsou dobré. V kvalitu své funkce věřil určitě i prof. Rivest z MIT, když navrhoval tehdy dost silně vyhlížející MD5. Za 14 let poté můžeme vytvářet kolize MD5 během sekund na počítači, a ten si můžeme koupit v samoobsluze s elektronikou. Kolize MD5 na běžném PC v průměru za 17 sekund, program a postup viz [Kli06a].

Bude to také platit o funkcích SHA-2? Jistě, nikdo nemůže říci, že to nastane ani nenastane. V tom je ta potíž. Chybí důkazy bezpečnosti.

Matematické modely hašovacích funkcí

Víru v bezpečnost hašovacích funkcí (podobně jako u blokových šifer) mají podpořit matematické modely a důkazy jejich vlastností. Tady bylo a dosud je, na rozdíl od blokových šifer, dost velké vakuum. Kromě základního Merkle-Damgardova modelu [Mer89] [Dam89] nebyly dlouho k dispozici žádné jiné modely. Přelomem byla práce Corona a kol. v roce 2005 [CDMP05]. Ukázal, že staré konstrukce, známé jako NMAC a HMAC (viz obr. 5), které byly vynalezeny před deseti lety Bellarem a kol. [BCK96], se při zvyšování délek bloku do nekonečna stávají něčím, co je kryptologickým grálem – náhodnými orákuly. Přesto jejich příspěvek ještě nebyl zcela doceněn (a nebo se na něm v tichosti pracuje ?). NBÚ rozhodl návrh bezpečné hašovací funkce SNMAC zcela zveřejnit k všeobecné diskusi a oponentuře. Nemusí tomu tak být ale u jiných bezpečnostních úřadů ve světě.

Důkazy bezpečnosni NMAC a HMAC

Za základ nové hašovací funkce jsme se rozhodli použít právě Bellare-Coronovy konstrukce NMAC/HMAC. Když jsme měli v rukou Coronův důkaz ideální bezpečnosti těchto konstrukcí v nekonečnu, bylo nutné předložit i další důkazy pro konečné rozměry. Pro konečné rozměry nás u hašovacích funkcí zajímají nejvíce odolnost proti kolizi a proti nalezení vzoru. Předložili jsme matematicky dokázané kvantitativní dolní a horní odhady bezpečnosti. Tvoří polovinu práce na novém konceptu [Kli06c], tady jen poznamenáme, co znamenají. Říkají, že k nalezení kolize nebo vzoru u konstrukcí NMAC/HMAC by případný útočník nutně potřeboval řádově tolik operací, jako kdyby místo nich byla náhodná orákula! Připomeňme, že pokud dáme zhašovat nějakou zprávu náhodnému (hašovacímu) orákulu, vygeneruje si právě v tom okamžiku náhodný řetězec, o kterém nemělo předtím ani potuchy, a vrátí vám ho. Orákulum si ještě vede tabulku už vygenerovaných hodnot, a pokud mu náhodou dáte zhašovat starou zprávu, vrátí vám výsledek stejný jako při prvním dotazu, tentokrát ze své tabulky.

Odhady jsou těsné (dolní a horní mez jsou stejného řádu) a říkají, že k nalezení kolize nebo vzoru potřebuje šestileté dítě a geniální útočník řádově stejně operací (oba dva se musí pohybovat mezi dolní a horní mezí), tj. že řádově nejlepší útok na něj je útok šestiletého dítěte nebo zcela náhodný útok (který také vyžaduje počet operací nalézající se mezi dolní a horní mezí). Z jedné strany tak máme Coronovy důkazy, které říkají, že kvalitativně se konstrukce NMAC/HMAC blíží ideálu (v nekonečnu) a z druhé strany (pro konečné rozměry) naše důkazy, že jejich odolnost proti nalezení vzoru a kolize je kvantitativně stejná jako u náhodných orákul. Takové vlastnosti nemá prokázány žádná hašovací konstrukce.

Konstrukce SBŠ

Dalším úkolem bylo navržení speciální blokové šifry (SBŠ). Tyto vlastnosti jsme odvodili a zde je jen uvedeme. Základní vlastností je manipulovatelnost s klíčem a homogenita ve zpracování všech vstupních bitů. Tyto vlastnosti nemá žádná současná klasická bloková šifra, protože všechny ke své efektivitě zneužívaly postavení tajného prvku (šifrovacího klíče), jehož bity byly zpracovávány slabě a rozdílně než bity otevřeného textu. Konstrukce speciální blokové šifry ve tvaru f: {0, 1}K → {0, 1}n : k → Ek(Const0) umožňuje naplnit oba požadavky. Zatím máme formulovány vlastnosti SBŠ, ale nemáme žádný konkrétní příklad. Konkrétní instance SBŠ (funkce DN) a konkrétní instance hašovací funkce na ní založené (funkce HDN) byly už navrženy, a čeká se pouze na schválení jejich publikace. Navzdory tomu, že jejich návrh provokuje zvědavost, jejich konkrétní podoba nemá už takový význam jako objev jejich existence. Tak jako bloková šifra může mít spoustu instancí a (DES, AES,…), které mohou být více či méně robustní, mohou mít různé rozměry, různé vnitřní stavební bloky apod., to samé je u speciální blokové šifry. SBŠ je obecným primitivem, seznamem vlastností, které lze splnit různými algoritmy a funkcemi a je otevřen prostor pro mnoo různých návrhů, různě efektivních, používajících různé matematické principy a operace. Konkrétní instance DN a HDN, které jsme navrhli, pouze ukazují jeden způsob, jakým lze tato nová primitiva konstruovat.

Hašovací funkce nové generace SNMAC

SNMAC je zkratkou pro Special Nested Message Authentication Code. Tato hašovací funkce vznikne, když do konstrukce NMAC vložíme místo náhodného orákula f speciální blokovou šifru f: {0, 1}K → {0, 1}n : k → Ek(Const0) a místo náhodného orákula g speciální blokovou šifru g: {0, 1}K → {0, 1}n : k → Ek(Const1).

Klima - obr 5

Obr.5: Definice hašovací funkce NMAC (viz [BCK96], [CDMP05])

Klima - obr 6

Obr.6: Definice SNMAC, založená na SBŠ a NMAC

Klima - obr 7

Obr.7: Definice hašovací funkce HMAC (viz [BCK96], [CDMP05])

Okrajová poznámka. Na obrázcích vidíme, že SNMAC je jakýmsi kompromisem mezi HMAC a NMAC. SNMAC můžeme konstruovat „shora“ z NMAC, když náhodná orákula v ní nahradíme speciální blokovou šifrou, nebo „zdola“ z HMAC, když klasickou blokovou šifru v ní nahradíme speciální blokovou šifrou.

Speciální bloková šifra DN a hašovací funkce HDN

Návrh konkrétních instancí kruh uzavírá. Ukazuje se, že navržená hašovací funkce HDN jako realizace konstrukce SNMAC je reálně použitelná. Má hašovací kód 512 bitů a její rychlost (v SW) je ve srovnání s SHA-512 pouze 3–4 x nižší. Srovnáme-li však návrhy obou funkcí, vidíme, že HDN je mnohem robustnější a má velkou bezpečnostní rezervu. HDN bude mít oproti SHA-512 také veřejná návrhová kritéria, má dokazatelné teoretické vlastnosti a má důkaz výpočetní odolnosti proti kolizi a nalezení vzoru. Takové vlastnosti nemá žádná současná hašovací funkce. Proto se domníváme, že konstrukce SNMAC na bázi speciální blokové šifry může být novým konceptem hašovacích funkcí. Instance DN a HDN pak mohou být prvními návrhy pro diskusi jejich bezpečnosti a konkrétní realizaci.

Závěr

Kryptologové náš nový koncept přijmout nemusí, ale vzhledem k tomu, že žádný jiný není a tento má navíc takové důkazy jako žádná jiná hašovací funkce, je tu určitá naděje, že se s ním bude někdo zabývat. Na druhé straně akademické komunitě trvá někdy léta, než něco přijme a použije. Tuhle dobu by mohl zkrátit fakt, že nový koncept se v mezinárodním měřítku právě nyní intenzivně hledá.

root_podpora

Literatura

Viz úplná verze článku [Kli06c].

Poznámka: V tomto příspěvku prezentujeme část výsledků projektu NBÚ Bezpečná hašovací funkce (ST20052005017).

Byl pro vás článek přínosný?

Autor článku