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, kdykoli nějaká množina vstupních dat je transformována na menší množinu výstupních hodnot (viz Dirichletův princip).

Kolize mohou způsobit potíže například při využití hašovací tabulky. Vážný problém způsobují kolize v kryptografii. Pokud je možné relativně snadno změnit vstupní data tak, aby byl zachován požadovaný výstup, je to možné využít například k falšování elektronického podpisu (viz kryptografický útok).

Kolize při různých použitích[editovat | editovat zdroj]

Kolize se vyskytují ve všech základních aplikačních oblastech hašovacích funkcí:

  1. hašovací tabulka
  2. kontrolní součet (otisk, signatura)
  3. kryptografická hašovací funkce

Při každé z těchto aplikací se mohou vyskytnout kolize, přičemž působí různé problémy. Hašovací funkce jsou pro různá použití navrhovány různými způsoby a proto mají i jiné charakteristiky vzhledem ke kolizím.

Kolize v hašovací tabulce[editovat | editovat zdroj]

Kolize způsobují nerovnoměrné rozložení dat, které následné prodlužuje doby operací. Kolize jsou obecně časté a implementace hašovacích tabulek s nimi počítají a mají různé záložní mechanismy. Existence kolizí taky vyžaduje, abychom v tabulce měli uložena i původní data (aspoň klíč, případně jeho část, nebo otisk dat), abychom mohli testovat, zda nalezená data odpovídají hledaným datům. Při návrhu funkcí chceme, aby podobná data byla hašována daleko od sebe[zdroj?], aby prostor indexů byl pokryt rovnoměrně a aby funkce byla rychlá.

Kolize v otisku[editovat | editovat zdroj]

Kolize v otisku je také nežádoucí. Pokud se spoléháme při porovnávání dat pouze na rovnost otisků, tak máme nesprávnou informaci, například falešný poplach u antiviru. Pokud otisky používáme pro předfiltraci dat, tak kolize způsobí nadbytečné vyvolání záchranných akcí, které jsou zpravidla drahé. Délka otisku (v bitech) je podstatná pro frekvenci náhodné shody - čím delší otisk, tím menší pravděpodobnost kolize. Jako otisku lze použít i kryptografické hašovací funkce, nebo její úvodní část, přičemž nevyužíváme kryptografické vlastnosti. Otisky se používají jako kontrolní součty při ochraně proti náhodným chybám při přenosu a ukládání dat. Při ochraně proti úmyslným chybám se používají jako otisky kryptografické funkce. Žádoucí vlastnost funkcí je, aby při malé změně dat (pouze několik bitů) byly otisky různé a tedy se na běžnou chybu vždy přišlo. To splňují např. CRC.

Kolize v kryptografii[editovat | editovat zdroj]

Stručně, řečeno, (něčí) schopnost systematicky nalézat kolize znamená, že funkce se považuje za prolomenou a dozrál čas na její nahrazení. Funkce se navrhují tak, aby měly požadované kryptografické vlastnosti, například odolnost proti nalezení kolize nebo odolnost proti nalezení klíče k danému výsledku. Funkce jsou výpočetně řádově náročnější než pro předcházející použití a často se v nich nějaký netriviální vnitřní výpočet několikrát opakuje.

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 zkracování hashe se odolnost exponenciálně snižuje.

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í.

Praktické prolomení znamená, že existuje takový algoritmus a taková výpočetní síla, která umožní najít klíč v rozumném časovém úseku (distribuované výpočty).

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.

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é.

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

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]