Kolize (funkce)

Kolize je v matematice situace, kdy pro různé vstupní hodnoty funkce přiřazuje stejné výstupní hodnoty. Kolize je nežádoucí například u hašovací funkce nebo u kryptografické hašovací funkce, kde v informatice způsobuje potíže, které je nutné dále řešit.

Hašovací funkce

Protože má hašovací funkce vždy stejně dlouhý výstup, zatímco její vstup může být libovolný, nelze se kolizím vyhnout (je-li libovolná množina vstupních dat transformována na menší množinu výstupních hodnot – viz Dirichletův princip).

Kolize se vyskytuje 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

Malý telefonní seznam jako hashovací tabulka

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

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 antivirového programu. 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ňuje např. cyklický redundantní součet (CRC).

Kolize v kryptografii

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.

Prolomení hašovací funkce

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

Teoretické prolomení

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á 2^{délka hashe}. Při zkracování hashe se odolnost exponenciálně snižuje.

Praktické prolomení

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 2^{dé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

Kryptografická hašovací funkce MD5 byla nejprve prolomena teoreticky a v roce 2004 i prakticky. Na podzim roku 2004 publikovala Wangová (Čína) konkrétní příklady kolizí. Brzy postup hledání kolizí zrychlil na řádově hodiny, potom jen sekundy český kryptoanalytik Vlastimil Klíma a publikoval tzv. metodou tunelování. Proto už není MD5 považována za bezpečnou.

Už po nalezení chyb v algoritmu (teoretické prolomení) bylo doporučováno nahradit MD5 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é a standardizované.

Příklad kontrolního součtu MD5

Otisk 43bajtové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

Kryptografická hašovací funkce SHA-1 je teoreticky prolomená. Snížení časové složitosti publikovala v únoru roku 2005 opět Wangová, z 2⁸⁰ na 2⁶⁹. V srpnu 2005 na konferenci CRYPTO 2005 publikovali Wangová, Andrew Yao a Frances Yao snížení složitosti na 2⁶³. V prosinci roku 2007 poskytl důkaz tohoto prolomení Martin Cochran (více v odkazech níže).

Institut NIST doporučil v roce 2007 v dokumentu SP800-57 používat SHA-1 jen do roku 2010. V nových systémech doporučil MD5 už podporovat jen kvůli zpětné kompatibilitě a nahradit ji 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ů. Institut NIST vyhlásil v roce 2012 výběrový konkurz na kryptografickou hašovací funkci, která bude standardizována jako SHA-3. V prosinci 2008 NIST zveřejnil 51 kandidátů do prvního výběrového kola (více v odkazech níže).

Externí odkazy

• Bezpečné délky kryptografických klíčů - web shrnuje do přehledné tabulkové formy doporučení různých organizací, pro klíče symetrických i asymetrických šifer
• Průběh NIST konkurzu na SHA-3 (anglicky) - průběh, kandidáti a přesnější reference ke konkurzu NIST na kryptografickou hašovací funkci