Kolize (informatika)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Malý telefonní seznam jako hashovací tabulka

Kolize je v informatice stav, kdy hash, kontrolní součet nebo otisk kryptografické hašovací funkce přiřazuje stejný výstup různým vstupním datům. Kolizím se nelze vyhnout, protože nekonečně mnoho variant vstupních dat je redukováno na omezenou množinu výstupních hodnot (viz Dirichletův princip), což může způsobit potíže například při využití hašovací tabulky. Velký problém způsobují kolize v kryptografii, pokud je možné snadno najít adekvátní změnu ve vstupních datech tak, aby byl zachován požadovaný výstup, což je možné zneužít při falšování elektronického podpisu (viz kryptografický útok).

Bezpečnost kryptografických hašovacích funkcí[editovat | editovat zdroj]

Nalezení teoretického postupu (metody) hledání kolizí a nebo konkrétního příkladu kolizí degraduje bezpečnost použité hašovací funkce. Při existenci takovéhoto postupu, by bylo možné předložit dvě různé zprávy se stejným platným digitálním podpisem a nebo elektronickým podpisem.

Po zveřejnění rychlého, efektivního postupu hledání kolizí hovoříme o kryptografickém prolomení hašovací funkce a je potřebné hledat opatření na minimalizaci rizik - funkce není možno dále bezpečně používat.

Bezpečnost hašovací funkce závisí na složitosti algoritmu, který používá na transformaci vstupních dat na výstup (hash) a na samotné délce hashe. Bezpečný algoritmus musí používat řadu složených funkcí a hledání inverzních funkcí k nim je v současnosti těžkým matematickým problémem (faktorizace, diskrétní logaritmy). Délka hashe zvyšuje časovou složitost hledání kolize.

Klasifikace prolomení[editovat | editovat zdroj]

Kryptografická prolomení hašovacích funkcí je možné rozdělit následovně:[1]

Teoretické prolomení[editovat | editovat zdroj]

O teoretickém prolomení hovoříme pokud byl nalezen způsob hledání kolize s nižší složitostí než je odolnost hašovací funkce. Odolnost je vypočítána na základě předpokladu, že hašovací funkce se chová jako náhodné orákulum. Kryptografická odolnost je tedy rovná 2délka hashe. Při krátkém hashi je odolnost exponenciálně nižší. Dále teoretické prolomení znamená, že existuje takový algoritmus a taková výpočetní síla, která umožní najít kolizi v rozumném časovém úseku (distribuované výpočty).

Praktické prolomení[editovat | editovat zdroj]

Praktické prolomení představuje nalezení konkrétních kolizí. Složitost jejich hledání souvisí s narozeninovým paradoxem, který snižuje řád složitosti na polovinu. Tedy odolnost je v praxi rovna 2délka hashe/2. Při krátkém hashi je možné hledání kolize provést útokem hrubou silou – zkoušení všech možných kombinací.

Kolize v MD5[editovat | editovat zdroj]

Kryptografická hašovací funkce MD5 byla dávno teoreticky prolomena, v roce 2004 už i prakticky prolomena. Na podzim roku 2004 publikovala Wangová (Čína) konkrétní příklady kolizí. Brzy postup hledání kolizí zrychlil na řád hodin, potom jen sekund Vlastimil Klíma a publikoval je metodou tunelování[2]. Tedy MD5 se už definitivně nepovažuje za bezpečnou, kvůli možnosti najít kolize v řádech sekund na běžném počítači.

Příklad kontrolního součtu MD5[editovat | editovat zdroj]

Otisk 43 bajtového znakového řetězce (vyjádřený v hexadecimálním zápisu):

 MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6

Stačí malá změna vstupního řetězce, aby byl otisk úplně odlišný (např. změňme d na c):

 MD5("The quick brown fox jumps over the lazy cog") = 1055d3e698d289f2af8663725127bd4b

Už po nalezení chyb v algoritmu (teoretické prolomení) se doporučovalo MD5 nahradit bezpečnějšími funkcemi. Případně v systémech zavést paralelní výpočet hashe dalšími funkcemi. Existují upravené algoritmy, které odolávají postupu Wangové a Klímy, ale ty nejsou dostatečně rozšířené, tedy standardizované.

Kolize v SHA-1[editovat | editovat zdroj]

Kryptografická hašovací funkce SHA-1 je teoreticky prolomená. Snížení časové složitosti publikovala v únoru roku 2005 opět Wangová, z 280 na 269. V srpnu 2005 na konferenci CRYPTO 2005 Wangová, A. Yao a F. Yao už na 263. V prosinci roku 2007 důkaz tohoto prolomení poskytl Martin Cochran[3]. Více v Externích odkazech.

NIST v roce 2007 doporučil v dokumentu SP800-57[4] používat SHA-1 jen do roku 2010. V nových systémech ji doporučil už jen zpětně podporovat a nahradit bezpečnějšími kryptografickými hašovacími funkcemi. Například z rodiny funkcí SHA-2, které mají delší hash a několik opravných zásahů do algoritmů. NIST vyhlásil výběrový konkurz na kryptografickou hašovací funkci[5], který bude standardizovaný jako SHA-3 v roce 2012. V prosinci 2008 NIST zveřejnil 51 kandidátů do prvního výběrového kola, víc v Externích odkazech.

Reference[editovat | editovat 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]. Verze 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. NIST konkurz na kryptografickou hašovací funkci [online]. NIST, 2008 [cit. 2008-12-31].

Externí odkazy[editovat | editovat zdroj]