Hašovací funkce MD5 a další prolomeny!

(průběžně aktualizováno na stránkách autora)

Uplynulý týden byl špatným týdnem pro hašovací fukce a dobrým pro kryptoanalytiky, kteří dosáhli neočekávaných vědeckých úspěchů. Definitivně byly prolomeny MD4, MD5, RIPEMD a HAVAL-128 [1] a byly nalezeny nové obecnější techniky hledání slabin iterativních hašovacích funkcí, což jsou právě všechny důležité současné hašovací funkce [1, 2, 3, 4]. Výsledkem je trochu mrazení v zádech, zda tyto moderní hašovací funkce a zejména převládající SHA-1 ustojí tyto techniky a na nich založené útoky. Dobrou zprávou je, že zatím je vše v pořádku, tj. SHA-1 a novější třída funkcí SHA-256, SHA-512, SHA-384 a SHA-224 (souhrnně jsou označovány jako třída SHA-2) zůstávají bezpečné. Další dobrou zprávou je, že funkce HMAC, používající MD5, tj. HMAC-MD5, nemusí být v některých případech vyměňovány a že HMAC v kombinaci s funkcemi SHA-1 nebo třídou SHA-2 zůstávají také bezpečné.

Prolomením hašovací funkce zde máme na mysli nalezení kolize, tj. dvou různých zpráv vedoucích na stejnou haš. Bezkoliznost je důležitá u digitálních podpisů. Jakmile je u hašovací funkce nalezena kolize, musí být ze schématu digitálního podpisu vyloučena. Kolize byly nyní nalezeny a předvedeny u hašovacích funkcí SHA-0, MD4 (už dříve, nyní velká třída kolizí), MD-5, RIPEMD a HAVAL-128. (Časová náročnost je od sekund po 1–2 hodiny.) Jejich používání v digitálních podpisech by tedy mělo být vyloučeno.

Hašovací funkce se používají ve spojení s tajným klíčem i v HMAC, kde mají v zásadě dva typy použití. První je jako PRF (pseudonáhodná funkce) a druhé použití je ve smyslu MAC (autentizační kód zprávy). V prvním případě se pomocí hašovací funkce a klíče generuje větší množství (pseudonáhodných) dat a zde by se prolomené funkce neměly používat (i když není ukázán žádný devastující útok typu nalezení kolize, pouze jsou mírně oslabeny bezpečnostní vlastnosti). U použití typu MAC se stručně řečeno hašovací funkce použije mnohokrát a produkuje krátký výstup, zde není známo žádné devastující oslabení funkce autentizačního kódu. Toto vysvětlení je vágní, ale jeho cílem je prvotní zpráva a orientace, nikoli přesnost. O přesné interpretaci výsledků [1,2,3,4] kryptologové diskutují, protože objevitelé kolizí [1] nepublikovali svůj postup, ale pouze výsledky. Je to velmi neobvyklé a lze to přičíst tomu, že výsledky chtěli prezentovat v neformálním fóru (jedná se o tzv. rump session) na nejprestižnější kryptologické konferenci Crypto 2004, nestihli plný příspěvek sepsat nebo postup precizují nebo ho nechtějí odhalit z jiného důvodu. Díky chybě, kterou udělali při první publikaci výsledků, však vyplynulo, že jsou schopni nalézat kolize pro různé počáteční hodnoty, s nimiž začíná pracovat hašovací funkce. Odtud pak plyne mírné oslabení vlastností HMAC jako PRF.

Poznamenejme ještě, že kolize MD4 byla nalezena Dobbertinem v roce 1996 a že se od ní rychle upustilo. V současné době jsou nejpoužívanějšími SHA-1 a MD5. U MD5 byla v roce 1996 nalezena slabina (kolize v kompresní funkci) a společností RSA bylo doporučeno ji přestat používat. Bohužel zakořenila do mnoha systémů a díky tomu, že nebyla nalezena úplná kolize, bezpečnostní architekti ji v mnoha systémech ponechali, aniž by si nechali zadní vrátka k výměně. V některých systémech tak bude velmi těžké ji nahradit. Prodlužování klinické smrti MD5 se nyní tedy vymstilo.

SHA-0 byla krátkou dobu oficiálním standardem, ale byla rychle nahrazena SHA-1, proto by její odpis neměl být problémem (jenom u totálních ignorantů) – nalezení kolizí bylo nyní ukázáno dokonce dvakrát (v [1] a [3]), i když se značnou složitostí. RIPEMD a HAVAL se příliš neujaly (RIPEMD byl nahrazen bezpečnějšími variantami), takže předvedení kolizí u nich bylo pouze pro demonstraci síly objevených technik. U SHA-1 byly předvedeny některé techniky, které ji více prozkoumávají, ale nesnižují její bezpečnost [2,4].

Z publikovaných příspěvků v minulém týdnu vyplynula určitá nervozita, zda tato odhalení nějak nenarušují bezpečnost systémů, používajících SHA-1. Dobrá zpráva je, že nikoli, ale to mrazení v zádech by mělo všechny dostatečně poučit. Co kdyby to vliv mělo? Hašovací funkce nové třídy SHA-2 jsou použity zatím jen minimálně, protože se spoléhá na bezpečnost SHA-1 a není ochota příliš věci měnit. Poučení tedy je, že je nutné se na průšvihy tohoto typu připravit jako na normální jevy, tak jako je normální u složitých programů vydávat záplaty. Nové paradigma by mělo být „nedůvěřovat slepě jen jedné funkci, ale systémy budovat tak, aby se kryptografické nástroje v nich mohly pružně měnit“. Bezpečnost není absolutní, je to proces. Tuhle poučku sice každý zná, ale v oblasti používání kryptografických nástrojů jakoby všichni ztuhli.

Můžete si ověřit MD5 haš od těchto dvou řetězců

(Pozn. red.: mezery byly do řetězců přidány kvůli sazbě –Johanka)

první:

d131dd02c5e6eec4 693d9a0698aff95c2fc ab58712467eab400458
3eb8fb7f8955ad34060 9f4b30283e488832571 415a085125e8f7cdc99
fd91dbdf280373c5b96 0b1dd1dc417b9ce4d89 7f45a6555d535739ac7
f0ebfd0c3029f166d10 9b18f75277f7930d55c eb22e8adba79cc155ce
d74cbdd5fc5d36db19b 0ad835cca7e3 

druhý:

d131dd02c5e6eec4 693d9a0698aff95c2fc ab50712467eab400458
3eb8fb7f8955ad34060 9f4b30283e4888325f1 415a085125e8f7cdc99
fd91dbd7280373c5b96 0b1dd1dc417b9ce4d89 7f45a6555d535739a47
f0ebfd0c3029f166d10 9b18f75277f7930d55c eb22e8adba794c155ce
d74cbdd5fc5d36db19b 0a5835cca7e3 

společná haš:

a4c0d35c95a63a805915367dcfe6b751 

SHA-0 kolize [3]:

první řetězec:

a766a602 b65cffe7 73bcf258 26b322b3 d01b1a97 2684ef53
3e3b4b7f 53fe3762 24c08e47 e959b2bc 3b519880 b9286568
247d110f 70f5c5e2 b4590ca3 f55f52fe effd4c8f e68de835
329e603c c51e7f02 545410d1 671d108d f5a4000d cf20a439
4949d72c d14fbb03 45cf3a29 5dcda89f 998f8755 2c9a58b1
bdc38483 5e477185 f96e68be bb0025d2 d2b69edf 21724198
f688b41d eb9b4913 fbe696b5 457ab399 21e1d759 1f89de84
57e8613c 6c9e3b24 2879d4d8 783b2d9c a9935ea5 26a729c0
6edfc501 37e69330 be976012 cc5dfe1c 14c4c68b d1db3ecb
24438a59 a09b5db4 35563e0d 8bdf572f 77b53065 cef31f32
dc9dbaa0 4146261e 9994bd5c d0758e3d

druhý řetězec:

a766a602 b65cffe7 73bcf258 26b322b1 d01b1ad7 2684ef51
be3b4b7f d3fe3762 a4c08e45 e959b2fc 3b519880 39286528
a47d110d 70f5c5e0 34590ce3 755f52fc 6ffd4c8d 668de875
329e603e 451e7f02 d45410d1 e71d108d f5a4000d cf20a439
4949d72c d14fbb01 45cf3a69 5dcda89d 198f8755 ac9a58b1
3dc38481 5e4771c5 796e68fe bb0025d0 52b69edd a17241d8
7688b41f 6b9b4911 7be696f5 c57ab399 a1e1d719 9f89de86
57e8613c ec9e3b26 a879d498 783b2d9e 29935ea7 a6a72980
6edfc503 37e69330 3e976010 4c5dfe5c 14c4c689 51db3ecb
a4438a59 209b5db4 35563e0d 8bdf572f 77b53065 cef31f30
dc9dbae0 4146261c 1994bd5c 50758e3d

společná haš:

c9f160777d4086fe8095fba58b7e20c228a4006b

Literatura a linky

[1] Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, rump session, Crypto 2004,

[2] Eli Biham, Rafi Chen, Near Collisions of SHA-0, Crypto 2004,

[3] Antoine Joux: Collisions in SHA-0, Crypto 2004 Rump Session

[4] Eli Biham, Rafi Chen: New results on SHA-0 and SHA-1, Crypto 2004 Rump Session

[5] Populárně o jednotlivých kauzách v češtině, další informace a další linky viz sekci News v týdnu od 16. 8. na crypto-world.info/news

[6] Elektronicky dostupné dokumenty a populární články v češtině:

Přednášky na MFF UK (zejména první a třetí):

V. Klíma: Základy moderní kryptologie – Symetrická kryptografie III. (operační mody blokových šifer a hašovací funkce), MFF UK, prosloveno v rámci přednášek oboru „Matematické metody informační bezpečnosti“, adela.karlin.mff­.cuni.cz/~tuma/ncip­hers.html.

V. Klíma: Základy moderní kryptologie – Symetrická kryptografie II. (symetrická kryptografie, proudové a blokové šifry, DES, EAS), MFF UK, prosloveno v rámci přednášek oboru „Matematické metody informační bezpečnosti“, adela.karlin.mff­.cuni.cz/~tuma/ncip­hers.html.

V. Klíma: Základy moderní kryptologie – Symetrická kryptografie I. (nové myšlenky kryptografie, bezpečnostní cíle, kryptoanalýza, typy kryptografických systémů, kryptologie), MFF UK, prosloveno v rámci přednášek oboru „Matematické metody informační bezpečnosti“, adela.karlin.mff­.cuni.cz/~tuma/ncip­hers.html.

Hašovací kód HMAC:

V. Klíma, T. Rosa: Kryptologie pro praxi (8) – funkce HMAC, Sdělovací technika, 2/2004, str. 17, cryptography.hy­perlink.cz/2004/st_­2004_02_17_17­.pdf.

Úvod k hašovacím funkcím a popis perspektiví SHA-1:

V.Klíma: Počítačová bezpečnost (Hašovací funkce a kódy): Výživná haše, Chip, březen 1999, str. 40 – 43, cryptography.hy­perlink.cz/1999/chip-1999–03–40–43.pdf.

Hašovací funkce MD, RIPEMD a HMAC, kompresní funkce a kolize hašovacích funkcí:

V. Klíma: Počítačová bezpečnost (Hašovací funkce a kódy): Jak se melou data, Chip, duben 1999, str. 44 – 46, cryptography.hy­perlink.cz/1999/chip-1999–04–44–46.pdf.

Nové hašovací funkce SHA-256, SHA-384 a SHA-512:

V. Klíma: Jednoznačné otisky dat, Chip, srpen 2001, str. 138 – 139, cryptography.hy­perlink.cz/2001/chip-2001–08–138–139.pdf.

[7] Ilustrovaný úvod do hašovacích funkcí, velmi pěkné – www.unixwiz.net/techtip­s/iguide-crypto-hashes.html