Hašovací funkce nové Hašovací funkce nové generace SNMACgenerace SNMAC

Vlastimil Klíma

Nezávislý kryptolog, v.klima (at) volny.cz, http://cryptography.hyperlink.cz

Mikulášská kryptobesídka 2006, Praha, Hotel Olympik,7. – 8. prosinec 2006, http://mkb.buslab.org/

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

ÚvodÚvod Proč téma hašovací funkce? Prolomena řada hašovacích funkcí. Nalezeny generické slabiny u všech současných hašovacích

funkcí. Žádná současná hašovací funkce neposkytuje o nic moc víc

než víru v její bezpečnost. Hledá se východisko, nový koncept.

ObsahObsah V příspěvku se zabýváme koncepcí hašovacích funkcí nové generace

SNMAC (Special Nested Message Authentication Codes), které byly navrženy v říjnu 2006 [Kli06c].

Použití klasické blokové šifry v kompresní funkci je systémovou chybou konstrukce a příčinou současných i budoucích problémů hašovacích funkcí.

Navrhujeme nové kryptografické primitivum - speciální blokovou šifru (SBŠ).

Na bázi SBŠ navrhujeme novou třídu hašovacích funkcí SNMAC.– SNMAC je obecnou konstrukcí, která má tyto důkazy bezpečnosti:

Coron a kol. [CDMP05] v roce 2005 ukázali, že konstrukce SNMAC se limitně stává výpočetně neodlišitelnou od náhodného orákula.

Klíma [Kli06c] v roce 2006 ukázal, že funkce třídy SNMAC jsou výpočetně odolné proti nalezení vzoru a kolize.

– Takové důkazy bezpečnosti nemá žádná jiná konstrukce hašovací funkce. Byly navrženy konkrétní instance SBŠ a SNMAC

Bezpečná hašovací funkceBezpečná hašovací funkce Hlavní problém bezpečné hašovací funkce - žádná taková

prakticky využitelná funkce neexistuje. Bezkoliznost - nemůže být z principu

– Prof. Rivest určitě věřil, že MD5 je kvalitní. Za 14 let…– Kryptografové se snaží matematické zákony oklamat a takovou

funkci navrhnout (je potřeba pro zcela praktické věci, jakými jsou digitální podpis apod.)

Jednocestnost - všechny "důkazy" jednocestnosti všech používaných hašovacích funkcí jsou založeny na různých matematických modelech. Ty se mohou ukázat jako neodpovídající realitě. Nakonec nám zůstane jen víra v to, že nelze invertovat nějakou složitou funkci.

Závěr 1: současný stav – víme, že BHF neexistuje, snažíme se jí ale přiblížit.

Proč nepoužít SHA-2 ?Proč nepoužít SHA-2 ? Měla být perspektivní náhradou SHA-1. Dnes už jsou ale obavy o její bezpečnost.

– Trpí hlavními generickými útoky na současné hašovací funkce. – Má podobnou strukturu jako SHA-0 a SHA-1, které byly kryptograficky

prolomeny.– Neznáme návrhová kritéria. Případné „přídavné zesílení“ bez znalosti

návrhových kritérií může tato kritéria porušit a funkce tak zeslabit. Možnosti případného zkvalitnění má jen NSA.

– Ve skutečnosti je jejich bezpečnost hodně založena na víře, že je NSA navrhla kvalitně.

Závěr 2: Žádná ze současných hašovacích funkcí současnosti není perspektivní, neboť všechny mají bezpečnostní problémy.

Nový konceptNový koncept NIST – připravuje mnohaletý program na hledání nového konceptu

hašovací funkce. Proběhlo několik mezinárodních kryptologických konferencí, žádný nový

hašovací standard. – Panelová diskuse, 2nd NIST Cryptographic Hash Workshop, August 2006,

USA:

– všichni panelisté souhlasili. Závěr 3: Domníváme se, že hlavní příčinou současného stavu je:

– Nebyly pojmenovány, analyzovány a zobecněny skutečné příčiny současných útoků na hašovací funkce (lze udělat poměrně snadno)

– Chybí teoretický koncept pro novou generaci hašovacích funkcí ( to je velký problém)

– Navrhujeme řešení obou problémů

–Antoine Joux: „Nevíme, co děláme a nevíme, co ve skutečnosti

chceme…“

Základní model Základní model iterativní hašovací funkceiterativní hašovací funkce

f

část zprávyKbitů

n bitůstarý kontext nový kontextn bitů

Základní model Základní model iterativní hašovací funkceiterativní hašovací funkce

f

m1

h0f

m2

h1f

mL

hL-1 hL

K bitů

n bitů

K bitů K bitů

n bitůn bitů n bitů

Základní model iterativní hašovací funkceZákladní model iterativní hašovací funkce

Vznikl v roce 1989 - klasický Merkle-Damgardův model [Mer89][Dam89].

Je přirozený Je základem všech moderních hašovacích funkcí Trpí všemi hlavními generickými útoky

– Útok prodloužením zprávy [Tsu92]– Jouxův [:žuův:] multikolizní útok [Jou04]– Kelsey-Schneierův multivzorový útok [KS05]

Závěr 4: Opustit přirozenou konstrukci nemůžeme, musíme se zřejmě smířit s tím, že hašovací funkce nové generace bude z teoretického hlediska náchylná k multikolizním a multivzorovým útokům. Možnou obranou může být výpočetní složitost.

(Útoku prodloužením zprávy lze zabránit.)

Současná stavba kompresní funkceSoučasná stavba kompresní funkce Vycházíme z Merkle-Damgardova modelu Konstruujeme kompresní funkci f Při hašování jednoho bloku odpovídá f celé hašovací funkci,

takže f by měla být jednosměrná a bezkolizní, nejlépe náhodné orákulum.

Závěr 5: hledáme náhodné orákulum na místě kompresní funkce f

f

m1

h0f

m2

h1f

mL

hL-1 hL

f

mi

hi-1 hi

~

Současná stavba kompresní funkceSoučasná stavba kompresní funkce

Místo funkce f se využívá klasická bloková šifra, ale s úpravami tak, aby vzniklé zobrazení bylo náhodné orákulum (zabraňuje hledání kolizí a vzoru). Nejčastěji Davies-Meyerova a Miyaguchi-Preneelova úprava.

mi

hi-1

E

fhi

hi-1 hi

mi

=

klíč

Ehi-1 hi

klíč

mi

Současná stavba kompresní funkceSoučasná stavba kompresní funkce

Další varianty navrhli Black a kol. [BRS02] v r. 2002 (na obrázku je výběr)

Lze je všechny charakterizovat výrazem ELin(Lin) xor Lin, kde Lin jsou jakékoliv (různé) lineární

kombinace původních jednoduchých vstupů (hi-1, mi)

klíč

ELin hi

Lin

Lin

Současná stavba kompresní funkceSoučasná stavba kompresní funkce

Další variantu navrhl Hirose v roce 2004 [Hir04]

Lze ho charakterizovat jako dvojici( ELin(Lin) xor Lin, ELin (Lin) xor Lin )kde Lin jsou opět nějaké lineární kombinace původních jednoduchých vstupů

Současná stavba kompresní funkceSoučasná stavba kompresní funkce Všechny hlavní současné hašovací funkce mají tuto stavbu: ELin(Lin) xor Lin Zdála se být vyhovující Dokud nepřišly útoky na MD, SHA a jiné Ukázaly, že tato stavba je špatná

klíč

ELin hi

Lin

Lin

Skutečné příčiny současných útoků na Skutečné příčiny současných útoků na hašovací funkcehašovací funkce

Útoky na MD5, SHA-0, SHA-1 aj.využily toho, že při konstantním otevřeném textu lze změnami v klíči řídit změny na výstupu použité blokové šifry (pro klasické blokové šifry je to nesmysl, ale o tom až za chvíli)

Při dvou otevřených textech, které mají určitou diferenci, se tyto změny dají řídit současně až do vzájemného vynulování (nebo docílení předem dané diference na výstupu) (pro klasické blokové šifry je to dvojitý nesmysl, ale o tom až za chvíli)

f

mi

hi-1 hi

klíčklíč

Ehi-1 hi

mi

Ehi-1 hi

miEOT

Klíč

ŠT

Skutečné příčiny současných útoků na Skutečné příčiny současných útoků na hašovací funkcehašovací funkce

Útoky lze zobecnit z diferencí v (hi-1, mi) na diference v lineárních kombinacích původních jednoduchých vstupů

Principiálně lze stejně útočit na všechna schémata typu ELin (Lin) xor Lin, což jsou všechna současná schémata

i zdánlivě komplikované

schéma

Hirose

klíčklíč

ELin hi

Lin

ELin hi

Lin

mi

mi

hi-1

hi-1

LinLin

Lin

LinLin

Závěr 6: Pokud bloková šifra umožní propagaci změn v otevřeném textu a/nebo v klíči do šifrového textu, není vhodná pro konstrukci typu ELin(Lin) xor Lin

Ale klasické blokové šifry nebyly konstruovány proto, aby a priori tomuto zabránily

Protože …. u moderních blokových šifer se klíč volí náhodně (RNG, KDF, haš) a předpokládá se, že ho útočník nezná

Klasické blokové šifry nebyly a nejsou připraveny na to, – že by útočník při konstantním otevřeném textu mohl volit klíč a manipulovat s ním

(klíč není jeho vlastnictvím, nezná ho, teprve později se vyskytly chybové kanály, které připustily možnost znalosti diference v klíči, ale nikoli znalost vlastní hodnoty klíče)

– že by bylo životně důležité zabránit řízené propagaci těchto změn v klíči do změn v šifrovém textu (klíč se volí náhodně, není znám útočníkovi, diference v klíči jsou omezeně dostupné útočníkovi)

– že by bylo životně důležité zabránit řízené propagaci změn v otevřeném textu a současně v klíči do změn v šifrovém textu (klíč se volí náhodně, není znám útočníkovi, diference v klíči jsou omezeně dostupné útočníkovi, ale při jakémkoliv útoku alespoň část z hodnot (OT, klíč) není známa útočníkovi)

Kolize v MD5, SHA-0, SHA-1 aj. využily právě nepřipravenost jejich blokových šifer na uvedené tři útoky.

Závěr 7: Klasické blokové šifry u všech současných hašovacích funkcí nejsou na uvedené tři útoky a priori připraveny a proti nim konstruovány. Všechny současné hašovací funkce jsou principiálně těmito útoky ohroženy.

f

mi

hi-1 hi

klíčklíč

Ehi-1 hi

mi

Ehi-1 hi

mi

EOT

Klíč

ŠT

Znalost, možnost manipulace všemi vstupy f (tj. i blokové šifry E)

Skutečné příčiny současných útoků na hašovací funkceSkutečné příčiny současných útoků na hašovací funkce

Závěr 8: Základní hluboký rozpor mezi klasickou blokovou šifrou a kompresní funkcí je, že u blokové šifry útočník nezná všechny vstupy a nemá možnost s nimi libovolně manipulovat, zatímco u hašovací funkce ano.

(Abychom se možnosti manipulace se všemi vstupy vyhnuli, předsadili jsme jim náhodná orákula.) Dokud tento rozpor nevyřešíme, budeme stále potvrzovat Jouxovo: „Nevíme, co děláme a nevíme, co ve skutečnosti chceme…“ Chceme náhodné orákulum.

Pokusme se zabránit řízení diferencí v klíči a v otevřeném textu použitím nějaké nelineární funkce místo lineární, která diference v (hi-1, mi) nepropaguje na výstup

f

mi

hi-1 hi

klíčklíč

ELin hi

Lin

ELin hi

Lin

mi

mi

hi-1

hi-1

LinLin

Lin

LinLin

Bude to fungovat

Potřebujeme jen kvalitní nelineární funkci,

která převádí (hi-1, mi) na výstup, třeba funkci f:

Ocitli jsme se na začátku problému. Konstrukce pomocí blokové šifry nám nepomohla. Proč?

klíčklíč

EhiE

hi

mi

mi

hi-1

hi-1

Non-Lin

Non-Lin

Non-Lin

Skutečné příčiny současných útoků na Skutečné příčiny současných útoků na hašovací funkcehašovací funkce

Rozpory mezi klasickou blokovou šifrou a hašovací funkcí jsou ještě hlubší

f

mi

hi-1 hiE

OT

Klíč

ŠT

Klasická bloková šifra Ek(x) Kompresní funkce f

Obsahuje prvek neznámý útočníkovi(Moderní útoky začínají zeslabovat vlastnost neznalosti klíče)

Útočník zná všechny vstupy kompresní funkce a může s nimi dokonce manipulovat

Je určena k zakrytí struktury a obsahu otevřeného textu v šifrovém textu na základě tajného prvku, neznámého útočníkovi

Je určena k zakrytí struktury a obsahu (nejen části, ale) celého vstupu ve výstupu, neopírá se o žádný utajený prvek

Při fixovaném klíči je permutací Požaduje se náhodné zobrazení

Je invertibilní Požaduje se neinvertibilita

Bezkoliznost je nezajímavou vlastnostíx2 = Dk2(Ek1(x1))

Požaduje se bezkoliznost

Skutečné příčiny současných útoků na Skutečné příčiny současných útoků na hašovací funkcehašovací funkce

Klasické blokové šifry - útočník nezná šifrovací klíč - pomocí něj se utajuje způsob převodu otevřeného textu na šifrový a naopak. Stavební prvky, které spoléhají na něco utajeného.

Utajenost "zneužívána" k tomu, že bity klíče jsou použity velmi jednoduše (TripleDES, AES). Nebyl důvod připravovat blokovou šifru na to, že útočník zná šifrovací klíč. To by byl nesmysl.

Pokud odstraníme předpoklad utajenosti klíče, už se nejedná o klasickou blokovou šifru, ale náhodné orákulum.

Závěr 9: Nejzákladnější příčinou problémů současných hašovacích funkcí je to, že

místo náhodného orákula používají stavební prvek, který byl původně určen pro řešení problému utajení dat.

f

mi

hi-1 hiE

OT

Klíč

ŠT

2.hlavní téma: Návrh náhodného orákula - 2.hlavní téma: Návrh náhodného orákula - speciální blokové šifry (SBŠ)speciální blokové šifry (SBŠ)

(U ideální blokové šifry jsme museli zajistit tak jako tak, že výše uvedené zobrazení je náhodné orákulum, a to pro jakýkoliv pevný otevřený text)

Využijeme technologii blokových šifer Klíč je u SBŠ potřeba zpracovávat velmi silně, a to zhruba na stejné úrovni jako

dříve otevřený text u klasické blokové šifry Výhoda: homogenita vstupních prvků, jednocestnost, náhodnost, cílená složitost Toto náhodné orákulum nazýváme speciální bloková šifra

f

mi

hi-1 hi

ECONST

Klíč

ŠT

mi hi-1 Způsob zpracováníklíče u speciální

blokové šifry musíbýt na stejné úrovni

jako způsobzpracování

otevřeného textu uklasické blokové

šifry

x =CONST0

x =CONST1

Ek(x) Ek(CONST0)

Náhodné orákulum konstruujeme jako zobrazení f: {0, 1}K {0, 1}n : k Ek(Const0)

3.hlavní téma: Jak z malého náhodného 3.hlavní téma: Jak z malého náhodného orákula udělat velké ?orákula udělat velké ?

Nelze to jednoduše, jak ukázaly tři generické útoky na uvedenou konstrukci

Řešení přinesly konstrukce NMAC a HMAC, navržené v roce 1996 [BCK96]

Důkazy vlastností – Coron a kol. 2005 [CDMP05], Klíma 2006 [Kli06c]

f

m1

h0f

m2

h1f

mL

hL-1 hL <- f

mi

hi-1 hi

Konstrukce NMAC a HMACKonstrukce NMAC a HMAC

Konstrukce NMAC a HMAC

NMAC(m)

f

m1

h0f

m2

h1f

mL

hL-1 ghL

f HMAC(m)f

NULL m1

h0IVf

m2

h1f

mL

hL-1

doplněk(K-n)

nulovýchbitů

E

K

hi-1Ef

hi hi-1 hi

K

=

hL

hL_pad

klíč

Obrana proti útoku prodloužením zprávy

Coron a kol. [CDMP05] ukázali, že při zvyšování délek bloku do nekonečna se NMAC a HMAC stávají výpočetně neodlišitelnými od náhodných orákul (náhodná orákula to být nemohou – viz generické útoky, ale mohou být od nich obtížně odlišitelné)

Z hlediska konkrétních útoků na získání vzorů a kolizí byly získány kvantitativní důkazy [Kli06c]: k nalezení kolize nebo vzoru u konstrukcí NMAC a HMAC by případný útočník nutně potřeboval řádově tolik operací jako kdyby místo nich byla náhodná orákula.

Takové kvalitativní a kvantitativní důkazy nemá žádná jiná konstrukce. Tím se problém BHF uzavírá následujícím návrhem.

4. Téma: SNMAC – Special Nested 4. Téma: SNMAC – Special Nested Message Authentication CodeMessage Authentication Code

Závěr 10: Koncept SNMAC může být kandidátem na hašovací funkce nové generace. Má dokazatelnou výpočetní odolnost proti nalezení vzoru a kolize, limitně se blíží náhodnému orákulu a umožňuje návrh různých instancí pomocí různých SBŠ.

Návrh nepředepisuje instance SBŠ, jen se říkají jejich vlastnosti. Konkrétní instance SBŠ (funkce DN) a na ní založené hašovací funkce (HDN) byly navrženy a budou brzy publikovány

[Kli06b]. Velikost hašovacího kódu HDN je 512 bitů a rychlost při použití „vojenské“ bezpečnostní rezervy je cca 3-4x nižší než

u SHA-512. V komerční verzi je možné téměř stejný výkon jako u SHA-512. (Programový kód nebyl optimalizován.)

NMAC(m)

f

m1

h0f

m2

h1f

mL

hL-1 ghL

f, g – speciální blokové šifryf: {0, 1}K {0, 1}n : X EX(Const0)g: {0, 1}n {0, 1}n : X EX (Const1)

LiteraturaLiteratura [BCK96] M. Bellare, R. Canetti and H. Krawczyk. Keying hash functions for message

authentication. Advances in Cryptology – CRYPTO ’96, Lecture Notes in Computer Science Vol. 1109, pp. 1-15, Springer-Verlag, 1996.

[BCJ05] E. Biham, R. Chen, A. Joux, P. Carribault, Ch. Lemuet and W. Jalby. Collisions of SHA-0 and Reduced SHA-1. Advances in Cryptology –EUROCRYPT 2005, Lecture Notes in Computer Science Vol. 3494, pp. 36–57, Springer-Verlag, 2005.

[BDK07] E. Biham, O. Dunkelman, and N. Keller. A Simple Related-Key Attack on the Full SHACAL-1, to be published, CT-RSA 2007, RSA Conference 2007, Cryptographers' Track, February 5-9, 2007, Moscone Center, San Francisco, USA.

[Bih05] E. Biham: Recent advances in hash functions and the way to go, Conference on Hash Functions (Ecrypt Network of Excellence in Cryptology), June 23-24, 2005, Przegorzaly (Krakow), Poland, http://www.ecrypt.eu.org/stvl/hfw/Biham.ps.

[BRS02] J. Black, P. Rogaway, T. Shrimpton. Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. Advances in Cryptology – CRYPTO 2002, Lecture Notes in Computer Science Vol. 2442, pp. 320-335, Springer-Verlag, 2002. Extended version: Cryptology ePrint Archive, Report 2002/066, http://eprint.iacr.org/2002/066.

[CDMP05] J. S. Coron, Y. Dodis, C. Malinaud and P. Puniya. Merkle-Damgard Revisited: how to construct a hash-function. Advances in Cryptology – CRYPTO 2005, Lecture Notes in Computer Science Vol. 3621, pp. 430 - 448, Springer-Verlag, 2005.

LiteraturaLiteratura [Dam89] I. Damgard. A Design Principle for Hash Functions. Advances in Cryptology -

CRYPTO 1989, Lecture Notes in Computer Science Vol. 435, pp. 416–427, Springer-Verlag, 1990.

[Hir04] S. Hirose: Provably secure double-block-length hash functions in a black-box model, Information Security and Cryptology - ICISC 2004, 7th International Conference, Seoul, Korea, December 2-3, 2004, Lecture Notes in Computer Science, Vol. 3506, pp. 330-342

[Jou04] A. Joux. Multicollisions in Iterated Hash Functions. Advances in Cryptology - CRYPTO 2004, Lecture Notes in Computer Science Vol. 3152, pp. 306–316, Springer-Verlag, 2004.

[Kli06a] V. Klima. Tunnels in Hash Functions: MD5 Collisions Within a Minute, Cryptology ePrint Archive, Report 2006/105, 18 March, 2006.

[Kli06b] SNMAC homepage http://cryptography.hyperlink.cz/SNMAC/SNMAC_CZ.html (in Czech), http://cryptography.hyperlink.cz/SNMAC/SNMAC_EN.html (in English).

[Kli06c] V. Klima: A New Concept of Hash Functions SNMAC Using a Special Block Cipher and NMAC/HMAC Constructions, IACR ePrint archive Report 2006/376 , October, 2006, http://cryptography.hyperlink.cz/SNMAC/SNMAC_EN.pdf (in English), Nový koncept hašovacích funkcí SNMAC s využitím speciální blokové šifry a konstrukcí NMAC/HMAC, http://cryptography.hyperlink.cz/SNMAC/SNMAC_CZ.pdf (in Czech).

[KS05] J. Kelsey and B. Schneier. Second Preimages on n-Bit Hash Functions for Much Less than 2n. Advances in Cryptology - EUROCRYPT 2005, Lecture Notes in Computer Science Vol. 3494, pp. 474–490, Springer-Verlag, 2005.

LiteraturaLiteratura [Mer89] R. C. Merkle. One Way Hash Functions and DES. Advances in

Cryptology - CRYPTO 1989, Lecture Notes in Computer Science Vol. 435, pp. 428–446, Springer-Verlag, 1990.

[MMO85] S. M. Matyas, C. H. Meyer and J. Oseas. Generating strong one-way functions with cryptographic algorithm. IBM Techn. Disclosure Bull., Vol. 27, No. 10A, 1985, pp. 5658 - 5659.

[MPRR06a] F. Mendel, N.Pramstaller, C.Rechberger, and V.Rijmen. Analysis of Step-Reduced SHA-256, to be published, FSE 2006

[PGV03] B. Preneel, R. Govaerts, and J. Vandewalle. Hash functions based on block ciphers: A synthetic approach. In Advances in Cryptology – CRYPTO ’93, Lecture Notes in Computer Science, pages 368–378. Springer-Verlag, 1994.

[Tsu92] G. Tsudik. Message authentication with one-way hash functions. ACM Computer Communications Review, 22(5):29-38, 1992.