Kolízie hašovacích funkcií

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Kolízia hašovacej funkcie je stav, kedy hašovacia funkcia dvom rôznym vstupom priraďuje rovnaký výstup (haš). Existencia kolízii je z princípu očakávateľná, pretože hašovacie funkcie priraďujú všetkým možným vstupom fixne obmedzený výstup (zobrazenie z väčšej množiny do menšej). Hľadanie kolízii musí byť však výpočtovo náročný problém.

Nájdenie teoretického postupu (metódy) hľadania kolízii alebo konkrétneho príkladu kolízií degraduje bezpečnosť použitej hašovacej funkcie. Pri existencii takéhoto postupu, by bolo možné napríklad predložiť dve rôzne správy s rovnakým platným digitálnym podpisom alebo elektronickým podpisom.

Po zverejnení rýchleho, efektívneho postupu hľadania kolízii dochádza k kryptografickému prelomeniu hašovacej funkcie a je potrebné hľadať opatrenia na minimalizáciu rizík – funkcie nemožno ďalej bezpečne používať.

Rozdelenie kolízii[upraviť | upraviť zdroj]

Kryptografické prelomenia hašovacích funkcií možno rozdeliť nasledovne:[1]

Teoretické prelomenie[upraviť | upraviť zdroj]

K teoretickému prelomeniu dôjde, pokiaľ bol nájdený spôsob hľadania kolízii s nižšou zložitosťou než je odolnosť hašovacej funkcie. Odolnosť je vypočítaná na základe predpokladu, že hašovacia funkcia sa chová ako náhodné orákulum. Kryptografická odolnosť je teda rovná 2dĺžka hašu. Pri krátkom haši je odolnosť exponenciálne nižšia. Ďalej teoretické prelomenie znamená, že existuje taký algoritmus a taká výpočtová sila, ktorá umožní nájsť kolízu v rozumnom čase, napríklad pomocou distribuovaných výpočtov.

Praktické prelomenie[upraviť | upraviť zdroj]

Praktické prelomenie predstavuje nájdenie už konkrétnych kolízii. Zložitosť ich hľadania svisí s narodeninovým paradoxom, ktorý znižuje rád zložitosti na polovicu. Teda odolnosť je v praxi rovná 2dĺžka hašu/2. Pri krátkom haši je možné hľadanie kolízii previesť útokom hrubou silou – skúšanie všetkých možných kombinácii.

Kolízie v MD5[upraviť | upraviť zdroj]

Kryptografická hašovacia funkcia MD5 bola dávno teoreticky prelomená. V roku 2004 už aj prakticky prelomená. Na jeseň 2004 publikovala Xiaoyun Wangová (Čína) konkrétne príklady kolízii. Neskôr postup hľadania kolízii zrýchlil na rád hodín, potom len sekúnd Vlastimil Klíma (Česko) a publikoval metódou tunelovania.[2] Teda MD5 sa už definitívne nepovažuje za bezpečnú, kvôli možnosti nájsť kolízie v rádoch sekúnd na bežnom počítači.

Odporúčania

Už po nájdení chýb v algoritme (teoretické prelomenie) sa odporúčalo MD5 nahradiť bezpečnejšími funkciami. Prípadne v systémoch zaviesť paralelný výpočet hašu ďalšími funkciami. Existujú upravené algoritmy, ktoré odolávajú postupu Wangovej a Klímu, no nie sú dostatočne rozšírené ani štandardizované.

Kolízie v SHA-1[upraviť | upraviť zdroj]

Kryptografická hašovacia funkcia SHA-1 je teoreticky prelomená. Zníženie časovej zložitosti publikovala v februári 2005 opäť Xiaoyun Wangová, z 280 na 269. V auguste 2005 na konferencii CRYPTO 2005 Wangová, Andrew Yao a Frances Yao už na 263. V decembri 2007 dôkaz tohto prelomenia poskytol Martin Cochran.[3]

Odporúčania

NIST v 2007 odporučila v dokumente SP800-57[4] používať SHA-1 len do roku 2010. V nových systémoch ju už len spätne podporovať a nahradiť bezpečnejšími kryptografickými hašovacími funkciami. Napríklad z rodiny funkcií SHA-2, ktoré majú dlhší hash a niekoľko opravných zásahov do algoritmov.

NIST vyhlásil výberový konkurz na kryptografickú hašovaciu funkciu[5], ktorý bude štandardizovaný ako SHA-3 v roku 2012. V decembri 2008 NIST zverejnil 51 kandidátov do prvého výberového kola.

Referencie[upraviť | upraviť zdroj]

  1. VONDRUŠKA, P. Hledá se náhrada za kolizní funkce… Crypto-World [online]. Číslo 5/2006 [cit. 2008-12-31]. ISSN 1801-21.
  2. KLÍMA, V. Tunely v hašovacích funkcích: kolize MD5 do minuty [online]. Verzia 2. 4/2006 [cit. 2009-01-01].
  3. COCHRAN, M. Notes on the Wang et al. 263 SHA-1 Differential Path [online]. Publikované 12/2007. Revidované 8/2008 [cit. 2009-01-01].
  4. BAKER, E. – BARKER, W. – POLK, W. ai. Recommendation for Key Management [online]. Special Publication 800-57 Part 1. NIST, 2007 [cit. 2008-12-31].
  5. NIST. Cryptographic hash Algorithm Competition [online]. NIST, 2008 [cit. 2008-12-31].

Externé odkazy[upraviť | upraviť zdroj]