Kolize hashovací funkce

Kolize hašovací funkce jsou dva různé vstupní datové bloky a pro hašovací funkci takové, že $X$ $y$ $H$ $H(x)=H(y).$

Kolize existují u většiny hašovacích funkcí, ale u „dobrých“ hašovacích funkcí se frekvence jejich výskytu blíží teoretickému minimu. V některých speciálních případech, kdy je množina různých vstupních dat konečná , je možné definovat injektivní hašovací funkci, která podle definice nemá kolize. U hašovacích funkcí, které přebírají vstup s proměnnou délkou a vracejí haš s konstantní délkou (jako je MD5 ), však kolize musí existovat, protože pro alespoň jednu hodnotu hašovací funkce bude odpovídající sada vstupních dat ( úplný předobraz ) nekonečno - a libovolné dvě množiny dat z této množiny tvoří kolizi.

Příklad

Uvažujme jako příklad hashovací funkci definovanou na množině celých čísel . Jeho doména hodnot se skládá z 19 prvků ( zbytkové kruhy modulo 19) a její doména definice je nekonečná. Protože množina předobrazů je zjevně větší než množina hodnot, musí existovat kolize. $H(x)=x\ {\bmod \ }19$

Vytvořme kolizi pro tuto hašovací funkci pro vstupní hodnotu 38, jejíž hašovací součet je nula. Protože je funkce periodická s periodou 19, pro jakoukoli vstupní hodnotu y bude mít hodnota y + 19 stejný hash součet jako y . Konkrétně pro vstupní hodnotu 38 budou mít vstupní hodnoty 57, 76 atd. stejný hašovací součet. Dvojice vstupních hodnot (38.57), (38.76) tedy tvoří kolize hašovacích funkcí . $H(x)$ $H(x)$

Kolize kryptografických hašovacích funkcí

Vzhledem k tomu , že kryptografické hašovací funkce se používají k potvrzení neměnnosti původní informace, schopnost rychle pro ně najít kolizi se obvykle rovná diskreditaci . Pokud je například k vytvoření digitálního podpisu použita hašovací funkce , pak schopnost najít pro ni kolize je ve skutečnosti ekvivalentní schopnosti padělat digitální podpis. Měřítkem kryptografické síly hashovací funkce je tedy výpočetní složitost nalezení kolize. V ideálním případě by neměl existovat rychlejší způsob nalezení kolizí než hrubá síla . Pokud pro nějakou hashovací funkci existuje způsob, jak získat kolize, která je mnohem rychlejší než vyčerpávající vyhledávání, pak tato hashovací funkce již není považována za kryptoodolnou a již se nepoužívá pro přenos a ukládání tajných informací. Teoretické i praktické otázky hledání a využití kolizí jsou každoročně diskutovány v rámci mezinárodních konferencí (např. CRYPTO či ASIACRYPT ), na velkém množství internetových zdrojů a také v mnoha publikacích.

Vlastnosti kryptografických hašovacích funkcí

Aby byla hašovací funkce H považována za kryptograficky bezpečnou, musí splňovat tři základní požadavky, na kterých je založena většina aplikací hašovacích funkcí v kryptografii:

Nevratnost : Pro danou hašovací hodnotu m by mělo být prakticky nemožné najít blok dat, pro který . $X$ $H(X) = m$
Odolnost proti srážce prvního druhu : pro danou zprávu M by mělo být prakticky nemožné najít jinou zprávu N , pro kterou . $H(N)=H(M)$
Odolnost proti kolizi druhého druhu : mělo by být prakticky nemožné zachytit pár zpráv , které mají stejný hash. $(M,M')$

Použití kolizí k hackování

Jako příklad zvažte jednoduchý postup ověření uživatele :

při registraci do systému uživatel zadá své heslo, na které je aplikována nějaká hashovací funkce , jejíž hodnota je zaznamenána v databázi ;
pokaždé, když zadáte heslo, použije se na něj stejná hashovací funkce a výsledek se porovná s výsledkem zaznamenaným v databázi.

S tímto přístupem, i když útočník získá přístup k databázi, nebude schopen obnovit původní hesla uživatelů (za předpokladu, že použitá hashovací funkce je nevratná). Pokud však útočník ví, jak najít kolize pro použitou hashovací funkci, nebude pro něj těžké najít neoriginální heslo, které bude mít stejný hash součet jako heslo uživatele.

Kolize mohou být použity k padělání zpráv: například informace o devizových transakcích jsou často šifrovány pomocí hashovacích funkcí; útočník, který má metodu pro nalezení kolizí této hashovací funkce, může nahradit zprávu falešnou a ovlivnit tak průběh měnové transakce.

Podobně lze kolize použít k padělání digitálních podpisů a certifikátů .

Ochrana proti kolizi

Existuje řada metod ochrany proti hackingu , ochrany proti padělání hesel, podpisů a certifikátů , i když útočník zná metody pro konstrukci kolizí pro jakoukoli hashovací funkci .

Jednou z metod je přidání " salt ", tedy přidání nějaké sekvence znaků k hašovatelným datům, což se používá například při ukládání unixových hesel. V tomto případě je stejná "sůl" přidána také do výsledného hashe , což výrazně zvyšuje složitost současné konstrukce prvotřídních kolizí do skupiny hesel, protože každé z této skupiny musí začínat svým vlastním (unikátním) hodnotu "sůl". „Sůl“ však nekomplikuje útok na každé heslo jednotlivě .

Další populární, ale nefunkční metodou je zřetězení hashů ze dvou různých hashovacích funkcí. Předpokládá se, že v tomto případě, aby bylo možné vybrat kolize pro hashovací funkci , což je zřetězení hashovacích funkcí a , je nutné znát metody pro konstrukci kolizí jak pro , tak i . Zároveň existují studie, které ukazují, že použití hašovacích konkatenací mírně zvyšuje odolnost regulačního haše vůči kolizím a nezáleží na tom, jak moc se hašovací funkce od sebe liší [1] . Pokud je jedna z hašovacích funkcí dostatečně slabá, aby v ní našla kolizi, druhá nebude schopna výsledný haš posílit. $C(x)=y(x)\|z(x)$ $y(x)$ $z(x)$ $y(x)$ $z(x)$

Metody detekce kolize

Jednou z nejjednodušších a nejuniverzálnějších metod hledání kolizí je narozeninový útok . S tímto útokem bude nalezení kolize pro bitovou hašovací funkci vyžadovat v průměru asi operací. Proto je n - bitová hašovací funkce považována za bezpečnou, pokud se výpočetní složitost hledání kolizí pro ni blíží . $n$ $2^{{n{/2}}$ $2^{{n{/2}}$

Kromě toho existuje útok prodlužující zprávu , který při dané známé hodnotě umožňuje vypočítat , kde označuje zřetězení . Útok rozšíření pro některé hašovací funkce funguje i při zajištění odolnosti proti kolizi typu 1 , odolnosti proti kolizi typu 2 a vlastnosti nevratnosti . Rozumí se, že není nutné znát , ale stačí znát pouze jeho hash . Můžete tak například přidat další informace do zprávy někoho jiného. K zabránění tomuto útoku se používají různé metody: přidávají další kolo hašování , odlišné od předchozích; používat vícenásobné hashování; nebo použijte kombinaci předchozích dvou metod. $H(x)$ $H(x\|y)=H(H(x)\|y)$ $\|$ $X$

Útok rozšíření lze ale zvážit i z druhé strany: pokud máme nějakou zprávu a hašovací funkce je zranitelná vůči útoku rozšíření, pak je snadné najít kolizi prvního druhu: , , , tedy vlastnost odolnosti proti srážkám prvního druhu je porušena. $X$ $M_{1}=X\|Y$ $M_{2}=H(X)\|Y$ $H(M_{1})=H(M_{2})$

Většina moderních hashovacích funkcí má stejnou strukturu, založenou na rozdělení vstupního textu do bloků a následné iteraci, ve které se při každé iteraci používá nějaká funkce , kde x je další blok vstupního textu a y je výsledek předchozího úkon. Takové schéma však není dokonalé, protože se znalostí funkce je možné analyzovat data v intervalech mezi iteracemi , což usnadňuje hledání kolizí. $G(x,y)$ $G$

Nalezení kolizí hashovací funkce často předchází nalezení jejích pseudo- kolizí , tedy dvou různých hodnot počátečního bufferu, které pro stejnou zprávu dávají stejné hodnoty hash.

Kolize mezi hašovacími funkcemi MD4 a MD5

V roce 1996 Hans Dobbertin našel pseudokolize v MD5 pomocí určitých nestandardních inicializačních vektorů. Ukázalo se, že je možné sestavit druhou zprávu pro známou zprávu, a to takovou, že bude mít stejný hash jako ta původní. Z hlediska matematiky to znamená, že MD5(IV,L1) = MD5(IV,L2) , kde IV je počáteční hodnota bufferu a L1 a L2 jsou různé zprávy.

V roce 2004 čínští vědci Wang Xiaoyun Yu Hongbo oznámili zranitelnost, kterou objevili v algoritmu, který jim umožnila Lai Xuejia, Feng Dengguo, ), abyste našli kolize.

V roce 2005 výzkumníci Wang Xiaoyun a Yu Hongbo z univerzity Shandong v Číně zveřejnili algoritmus pro hledání kolizí v hashovací funkci MD5 a jejich metoda funguje pro jakýkoli inicializační vektor, nejen pro vektor používaný standardem. Použití této metody na MD4 vám umožní najít kolizi za méně než sekundu. Platí také pro další hashovací funkce, jako je RIPEMD a HAVAL .

V roce 2008 Alexander Sotirov, Marc Stevens a Jacob Appelbaum publikovali článek na 25. Chaos Communication Congress, který ukázal možnost generování falešných digitálních certifikátů na základě použití kolizí MD5.

Kolize hashovací funkce SHA-1

V lednu 2005 Vincent Rayman a Elisabeth Oswald publikovali útok na zkrácenou verzi SHA-1 (53 ran místo 80 ), který umožňuje nalézt kolize v méně než 280 operacích.

V únoru 2005 Wang Xiaoyun , Lisa Yin Yiqun a Yu Hongbo představili útok na plný SHA-1, který vyžaduje méně než 269 operací.

V srpnu 2005 na CRYPTO 2005 titíž odborníci představili vylepšenou verzi útoku na plnohodnotný SHA-1 s výpočetní náročností 263 operací. V prosinci 2007 byly podrobnosti tohoto zlepšení přezkoumány Martinem Cochranem.

Christophe de Kanier a Christian Rechberg později představili vylepšený útok na SHA-1, za který byli na konferenci ASIACRYPT v roce 2006 oceněni jako nejlepší článek . Představili kolizi dvou bloků na 64kolovém algoritmu s výpočetní složitostí asi 2 35 operací.

Vzhledem k tomu, že teoretické útoky na SHA-1 byly úspěšné, NIST plánuje zcela ukončit používání SHA-1 v digitálních podpisech .

Kolize s jinými hashovacími funkcemi

Hashovací funkce RIPEMD a HAVAL jsou také citlivé na kolizní algoritmus MD5 publikovaný Wang Xiaoyun, Feng Dengguo, Lai Xuejia a Yu Hongbo v roce 2004.

Pro druhou modifikaci hashovací funkce WHIRLPOOL , nazvanou Whirlpool-T, nejsou pro rok 2009 navrženy žádné algoritmy pro hledání kolizí nebo pseudokolizí; významným omezením pro jejich nalezení je složitost samotné funkce a velká délka (512 bitů) výstupního klíče.

Hašovací funkce GOST R 34.10-2001 z hlediska šifrovací síly se jen málo liší od GOST R 34.10-94 , hledání kolizí je redukováno na výpočet diskrétního logaritmu ve skupině bodů eliptické křivky s pravděpodobně exponenciální složitostí . Například pro 256bitové parametry bude diskrétní logaritmus pomocí ρ-metody nebo Pollardovy λ-metody vyžadovat asi 2 operace. ${10}^{{30}}$

Rozlišení kolize v hašovacích tabulkách

Kolize komplikují použití hašovacích tabulek , protože narušují vzájemnou shodu mezi hašovacími kódy a daty. Existují však speciální techniky, jak překonat vzniklé obtíže:

Metoda řetězení : Technologie řetězení prvků (chaining) spočívá v tom, že prvky množiny , které odpovídají stejné hash hodnotě, jsou spojeny v řetězci. Číslo pozice i ukládá ukazatel na začátek seznamu těch prvků, jejichž hash hodnota klíče je rovna i; pokud v množině žádné takové prvky nejsou, na pozici i se zapíše NULL .
Otevřené adresování : Na rozdíl od zřetězeného hašování u otevřeného adresování neexistují žádné seznamy a všechny položky jsou uloženy v samotné hashovací tabulce. Každá buňka tabulky obsahuje prvek dynamické sady nebo NULL.
Eliminace kolizí : Na rozdíl od předchozích dvou metod je přítomnost kolizí v hashovací tabulce eliminována ve fázi přidávání prvků. Hash kód adresovaného prvku je hash informace + náhodná hodnota. Pokud je hash kód již v tabulce, náhodná hodnota se vygeneruje a prvek s jiným hashem se znovu přidá do tabulky hash. Tím je vyloučena přítomnost kolizí a prvky lze nalézt podle jejich unikátních hashů, které je v hashovací tabulce jednoznačně oslovují.

Poznámky

↑ Antoine Joux . Získáno 3. října 2017. Archivováno z originálu 19. května 2017. (neurčitý)

Viz také

Odkazy

Bruce Schneier, MD5 a SHA kryptoanalýza
Cryptography Research , Hash Collision Q& A
Vytvoření podvodného certifikátu CA Alexander Sotirov , padělání certifikátu na základě MD5
Web Mezinárodní asociace pro kryptologický výzkum
Kolize pro hashovací funkce MD4, MD5, HAVAL-128 a RIPEMD , Xiaoyun Wang a Dengguo Feng a Xuejia Lai a Hongbo Yu ( (anglicky) )
Vylepšený Collision Attack na Hash Function MD5 , velmi technický
Komentáře NIST ke kryptoanalytickým útokům na SHA – 1
Tutor počítačových algoritmů

Literatura

Bruce Schneier , Applied Cryptography, 2. vydání, ISBN 0-471-11709-9 , kap.18, Jednosměrné hashovací funkce
Ross Anderson , bezpečnostní inženýrství , Wiley, ISBN 0-471-38922-6