Kolízie hašovacích funkcií

Kolízia hašovacej funkcie je stav, kedy hašovacia funkcia dvom rôznym vstupom priraďuje rovnaký výstup (haš). Existencia kolízií 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ízií musí byť však výpočtovo náročný problém. 

Nájdenie teoretického postupu (metódy) hľadania kolízií 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ízií 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ízií
Kryptografické prelomenia hašovacích funkcií možno rozdeliť nasledovne:

Teoretické prelomenie
K teoretickému prelomeniu dôjde, pokiaľ bol nájdený spôsob hľadania kolízií 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
Praktické prelomenie predstavuje nájdenie už konkrétnych kolízií. 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ízií previesť útokom hrubou silou – skúšanie všetkých možných kombinácii.

Kolízie v MD5
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ízií. Neskôr postup hľadania kolízií zrýchlil na rád hodín, potom len sekúnd Vlastimil Klíma (Česko) a publikoval metódou tunelovania. 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
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.

Odporúčania
NIST v 2007 odporučila v dokumente SP800-57 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, 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

Externé odkazy
 Bezpečné dĺžky kryptografických kľúčov – odporúčania rôznych organizácii pre kľúče symetrických i asymetrických šifier

Kryptografické hašovacie funkcie
Kontrolné súčty
Kryptológia
Počítačová bezpečnosť