Co je to kolizní útok?

Kolizní útoky jsou významným problémem v oblasti kryptografie. Za určitých okolností je může útočník použít k podkopání zabezpečení, které poskytuje digitální podpisy , což jim umožňuje podvodně způsobit, že data budou vypadat, jako by byla ověřena jejich integrita a pravost. To znamená, že kolizní útoky mohou obejít bezpečnostní mechanismy, na které se spoléháme, abychom udrželi náš online svět v bezpečí.

Ale než to opravdu pochopíte co je to kolizní útok , musíte nejprve zabalit hlavu co je to vlastně srážka . Abychom toho dosáhli, musíme udělat ještě jeden krok zpět a přivést vás k rychlosti hašování .

Co je hashování?

Kryptografická hašovací funkce je algoritmus, který má řadu specifických vlastností které se ukázaly být neuvěřitelně užitečné ve světě kryptografie. Vezmou vstup, často nazývaný zpráva, který je pak spuštěn pomocí hashovací funkce, výsledkem je výstup, hash, který se také někdy nazývá výtah zprávy.

Existují také hašovací funkce, které nejsou kryptografické, což jsou jednodušší algoritmy, které se často používají při ukládání a získávání dat. Jedná se však o tečné útoky na kolize, takže se nebudeme obtěžovat jejich podrobnou diskuzí.

Mezi vlastnosti kryptografických hashovacích funkcí patří:

• Hashovací funkce jsou deterministické — Když stejný vstup prochází danou hashovací funkcí, výsledkem je vždy přesně stejný výstup, pokaždé.
• Hashovací funkce přebírají datové vstupy libovolné velikosti a vždy vydávají řetězec pevné délky — Hašovací funkce může přijímat data libovolné velikosti, od jednoho znaku až po encyklopedii plnou slov. Bez ohledu na to, jak dlouhý je vstup, výstup dané hashovací funkce je vždy stejně dlouhý.
• Hashovací funkce jsou jedním ze způsobů — Je snadné vzít vstup, spustit ho pomocí hashovací funkce a pak zjistit, jaký je pro tento vstup odpovídající hash. Je však nemožné vzít hash a pak zjistit, jaký byl původní vstup z hashe. Výrazem „jednosměrný“ máme na mysli, že je praktické vypočítat hashovací funkci pouze jedním směrem, nikoli druhým.
• Hashovací funkce lze vypočítat rychle — Aby byly hashovací funkce praktické, potřebujeme, aby byly schopny rychle přeměnit vstup zprávy na hash. Byly by mnohem méně užitečné, pokud by proces trval příliš dlouho a vyžadoval by značné množství výpočetních zdrojů.
• Drobné změny na vstupu mají za následek významné změny na výstupu — I když jsou dva vstupy identické s výjimkou jediného znaku, kryptografická hašovací funkce dodá haše, které vypadají, že nemají téměř nic společného.
• Není možné najít dva různé vstupy, které vedou ke stejnému výstupu — Aby byla zajištěna bezpečnost aplikací hashovacích funkcí, nesmí být pro útočníka možné najít dva různé vstupy, které produkují stejný hash. Když jsou nalezeny dva vstupy se stejným hashem, nazývá se to a kolize .

Takže kryptografické hašovací funkce mají všechny tyto magické vlastnosti, ale jak vlastně vypadají?

Poskytneme vám rychlou ukázku s online hash kalkulačka . Webový nástroj, který jsme propojili, přijímá vstupy a provádí je SHA-256 což je zlatá standardní hashovací funkce, a pak vám poskytne 256bitový hash.

Můžete to zkusit s libovolným vstupem, ale my si několik projdeme, abychom demonstrovali některé klíčové vlastnosti. Když spustíme 'Co je hash?' přes kalkulačku nám dává hash:

2da0ed1070f7e7306a23785422576c864bdec63a6032482badc26fc5102f9a9c

Hash je in hexadecimální , což je prostě jiný způsob počítání. Místo systému, na který jsme zvyklí, který má 10 různých čísel (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), má šestnáctková soustava 16 (0, 1, 2, 3, 4 5, 6, 7, 8, 9, a, b, c, d, e, f). Hash je dlouhý 64 znaků a v hexadecimálním zápisu má každý znak čtyři bity. Tohle znamená tamto hash je dlouhý 256 bitů .

Zkusme jiný vstup, jen jeden znak „a“. Když vypočítáme hash, dostaneme:

ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb

Všimněte si, že i když měly vstupy značné rozdíly ve velikosti, oba výstupy mají stejnou délku, 64 znaků nebo 256 bitů. Jak jsme řekli, jednou z vlastností kryptografické hašovací funkce je to, že přijímá vstupy libovolné délky a vždy poskytuje výstup s pevnou délkou. Můžete zkusit vložit celou knihu do SHA-256 a stejně byste skončili s 256bitovým hashem .Všimněte si, že to ve skutečnosti nebude fungovat v kalkulačce, kterou jsme propojili, protože tento konkrétní webový nástroj má omezený počet znaků, které přijme jako vstup. To je však způsobeno tím, jak byl SHA-256 implementován na webu, a nikoli omezením v rámci samotného SHA-256.

Nyní si ukážeme, jak i malá změna ve vstupu vede k výrazně odlišnému hash. Vezměme náš dřívější příspěvek „Co je hašování?“, ale změňte otazník na vykřičník „Co je hašování!“ Je to poměrně nepodstatná změna, že? No, podívejme se, co dostaneme, když to vyhodíme přes hashovací funkci:

02a3603765eb85b8aa96aa8c18df75675a0670b33eb2c306e54d13a2baabffa5

Pokud porovnáte tento hash s prvním, uvidíte, že tyto dva nemají v podstatě nic společného. Jedná se o důležitou součást kryptografických hašovacích funkcí a tato vlastnost je známá jako lavinový efekt .

Pokud jste sami vyzkoušeli kalkulačku, uvidíte, že tyto hashe jsou vypočítal rychle (pokud nemáte pomalý internet). Můžete také zkusit stejný vstup znovu a znovu a uvidíte, že hashovací funkce je také deterministický —pro daný vstup vždy dostanete stejný výsledek.

Je trochu těžší vám ukázat, že SHA-256 je jednosměrná funkce a že je téměř nemožné zjistit původní vstup, pokud máte pouze hash. Je také náročné ukázat vám, že ano není možné najít dva různé vstupy, jejichž výsledkem je stejný hash . Tyto vlastnosti nám budete muset důvěřovat, protože jsou základem procesu návrhu bezpečných kryptografických hašovacích funkcí.

Použití hashů

Teď už asi máte nějakou představu o tom, jak hašovací funkce vypadají a co dokážou, ale jaký má smysl přeměnit vstup na změť čísel a písmen?

No, ukázalo se, že všechny tyto vlastnosti jsou ve skutečnosti docela užitečné a hashe jsou implementovány v řadě větších systémů. Abychom dostatečně porozuměli nebezpečí kolizních útoků, je důležité pochopit, kde se kryptografický hash skutečně používá.

Digitální podpisy

Jedna běžná aplikace je in digitální podpisy . Pokud chce odesílatel zprávy prokázat, že skutečně přišla od nich a ne od podvodníka, a také, že zpráva nebyla po odeslání změněna, může tak učinit pomocí digitálního podpisu. Ty zahrnují certifikáty a algoritmy veřejného klíče jako RSA kromě hashování.

Krátká verze digitálních podpisů je taková pravost a integritu lze ověřit, pokud odesílatel spouští svou zprávu pomocí kryptografické hašovací funkce a poté jej spustí výpočtem spolu s jejich soukromým klíčem. Odesílatel pak odešle tento výsledek jako digitální podpis spolu se zprávou příjemci.

Když příjemce obdrží zprávu, může ověřit její integritu a pravost spuštěním zprávy pomocí hashovací funkce, aby získal hash zprávy. Poté vezmou digitální podpis, který obdrželi od odesílatele, a provedou na něm některé výpočty pomocí veřejného klíče odesílatele.

Tento výsledek pak mohou porovnat s hashem zprávy, který právě vypočítali. Pokud si přijatá zpráva zachovala integritu a autenticitu, měly by být tyto dvě hodnoty stejné .

Hašování hesel

Heslo klíčové slovo kódové slovo od Geralta s licencí pod licence pixabay .

Dalším příkladem je hašování hesel. Pokud společnost ukládá vaše heslo jako prostý text, jste trochu v háji, pokud se hacker vloupe a ukradne jejich databázi hesel. Hacker se může jen podívat do databáze a pomocí hesel v prostém textu se přihlásit k libovolnému účtu, který chce, včetně vašeho.

Tak ukládání hesel jako prostého textu je z hlediska bezpečnosti hrozné , protože nemůžeme zaručit, že dokážeme udržet databáze hesel mimo dosah hackerů.

Naštěstí nám kryptografické hašovací funkce poskytují mnohem lepší řešení. Umožňují vývojářům ověřovat hesla, aniž by museli heslo ukládat jako prostý text do databáze. Jak jsme zmínili, je v podstatě nemožné najít dva různé vstupy, které vedou ke stejnému hash a je také nemožné vzít hash a pak zjistit, jaký byl počáteční vstup.

To znamená, že když si nastavíte účet a zadáte své uživatelské jméno a heslo, vývojáři mohou vaše heslo okamžitě hashovat a uložit pouze hash, nikdy ne prostý text vašeho hesla . Kdykoli se jdete přihlásit, jednoduše zahašují vaše heslo, jakmile ho zadáte, a poté ho porovnají s hashem, který mají uložený v databázi.

Pokud se obě shodují, vývojáři předpokládají, že jste v obou případech zadali stejné heslo, a že jste tedy stejný uživatel. Tak udělují vám přístup k vašemu účtu, aniž byste kdy věděli, jaké je vaše heslo .

Pokud hacker ukradne databázi hash hesel, je pro něj mnohem těžší je zneužít, než kdyby ukradl hesla v prostém textu. Vzhledem k povaze bezpečných kryptografických hašovacích funkcí a skutečnosti, že je tak nepravděpodobné, že by dva různé vstupy vedly ke stejnému hašování, se nemusíme příliš obávat, že by útočník zneužil systém a zadal nesprávné heslo, které stále vede. v odpovídajícím hash.

Další použití kryptografických hashů

Kryptografické hashe mají řadu dalších využití. Tyto zahrnují:

• Ověřovací kódy zpráv (MAC)
• Blockchain proof-of-work systémy
• Datové otisky prstů
• Kontrolní součty, které detekují poškození dat

Co je to kolize?

Nyní víme, že hashe jsou skutečně užitečné. V úvodu jsme také krátce zmínili, že v určitých scénářích, kde jsou implementovány kryptografické hashovací funkce, hrozí kolize. Ale co je to vlastně kolize?

Pamatujete si, jak jsme řekli, že by nemělo být proveditelné, aby dva různé vstupy v kryptografické hashovací funkci vedly ke stejnému hashu?

No... kolize je, když věci nejdou podle plánu a dva samostatné vstupy ve skutečnosti vedou ke stejné hashové hodnotě . Jak jsme řekli, nemělo by se to stát, a pokud ano, může to být neuvěřitelně problematické. Pokud jsou kolize praktické, umožňuje útočníkům zcela podkopat integritu a autentizační aspekty digitálních podpisů. To může vést ke všem druhům problémů, včetně podvodů a umožnění útočníkům proniknout kolem stávajících bezpečnostních systémů.

Prozradíme vám malé tajemství: Je ve skutečnosti nemožné, aby byla hašovací funkce navržena tak, aby se zcela vyhnula kolizím.

To je způsobeno tím princip rozškatulkování . V kontextu hashování v podstatě říká, že pokud existuje více vstupů, než je možných hashů, pak některé vstupy musí vést ke stejným hashům.

Jak jsme uvedli, hashe v SHA-256 jsou dlouhé 256 bitů. Tohle znamená tamto existuje maximální velikost, kterou může mít hash SHA-256 , stejným způsobem, jako pokud má počítadlo kilometrů na vašem voze pouze šest číslic, maximální hodnota, kterou může zobrazit, je 999 999. Pokud existuje maximální velikost hashe, znamená to také, že existuje omezený počet možných hashů.

Pro mnohé z nás je těžké si představit, jak velké je 256 bitů. Pokud byste měli spočítat všechny možné hexadecimální hashe SHA-256, došli byste k následujícímu číslu v desítkové soustavě:

115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,9193

Je to opravdu velké číslo, ale stále je to číslo, které můžeme zapsat a zobrazit na řádku nebo dvou.

Nyní se podívejme na všechny možné různé vstupy, které bychom mohli spustit prostřednictvím SHA-256. Cokoli od „0“ po „aardvark“ až po celý slovník nebo kompletní díla Shakespeara. Opravdu, možnosti jsou nekonečné . To nás přivádí k problematickému závěru: Infinity je mnohem větší než 256bitové číslo, které jsme napsali výše. Podle principu rozškatulkování, skutečnost, že máme nekonečné množství vstupů, ale omezený počet možných hashů, znamená, že každý jednotlivý hash musí mít ve skutečnosti mnoho různých vstupů, které ho mohou produkovat .

Znamená to, že vše, o čem jsme mluvili, je postaveno na slabém základě a že se to může každou chvíli zhroutit?

Ne nutně.

Určitě jste si všimli, že jsme nikdy neuvedli, že kryptografická hašovací funkce může nikdy mají dva samostatné vstupy, jejichž výsledkem je stejný výstup. Místo toho jsme uvedli, že ano neproveditelné (nebo v podstatě nemožné) najít dva různé vstupy, které vedou ke stejnému výstupu.

Nezáleží na tom, jestli existuje spousta různých hašovacích kolizí, které jsou teoreticky možné. Z důvodu bezpečnosti je opravdu důležité, že pro nikoho není praktické najít tyto hašovací kolize. Případné srážky se mohou v éteru vznášet, jak chtějí, ale nemohou nám způsobit žádné problémy, pokud je lidé nemohou skutečně najít.

Tak cílem bezpečné kryptografické hašovací funkce je nebýt zcela bez kolizí . Byl by to hloupý úkol, protože princip rozškatulkování dokazuje, že je to matematicky nemožné. Místo toho chceme, aby kryptografické hašovací funkce jako SHA-256 byly odolné proti kolizím, takže je pro každého neuvěřitelně těžké tyto kolize najít.

Narozeninový paradox

Narozeninový dort se svíčkami od Annie Spratt s licencí pod CC0 1,0 .

Abychom mohli určit, jak bezpečný je hashovací algoritmus, potřebujeme porozumět tomu, jak pravděpodobné jsou kolize. Jednou z hlavních komplikací je, že jsou ve skutečnosti mnohem pravděpodobnější, než by vám říkala vaše intuice. Nejlepší ukázkou toho je narozeninový paradox .

Řekněme, že si vyberete náhodný vzorek lidí a máte zájem najít v tomto vzorku lidi, kteří mají stejné narozeniny. Pravděpodobně byste jich potřebovali více než sto, abyste měli šanci na zápas, že? Vždyť rok má 365 dní.

Ani náhodou, s pouhými 23 lidmi již máte více než 50% pravděpodobnost, že dva lidé ve skupině budou sdílet narozeniny .

Ale jak to může být?

Pravděpodobně o tom přemýšlíte stejně jako většina z nás, takže přemýšlíte o nalezení shody pro konkrétní datum nebo konkrétního jednotlivce ve vzorku, spíše než se na to dívat, abyste zjistili, zda jsou ve vzorku nějací dva lidé sdílet narozeniny.

Pojďme si ukázat rozdíl mezi těmito dvěma různými způsoby pohledu na věc. Pokud se Jason narodil 1. ledna a vy jste chtěli vytvořit vzorek dostatečně velký, aby byla větší než 50procentní šance, že někdo bude sdílet jeho narozeniny 1. ledna, pak je vaše intuice správná. Chtěli byste v tomto vzorku asi 183 lidí, aby byla 50procentní šance na shodu.

Ale nehledáme a charakteristický zápas v narozeninovém paradoxu, hledáme žádný zápas . S 23 jednotlivci máme ve skutečnosti spoustu různých možných zápasů. Nejen, že zjišťujeme, zda má Jason stejné narozeniny jako kterýkoli z ostatních 22 lidí, ale také zda každý z nich sdílí stejné narozeniny jako kterýkoli jiný člověk ve skupině. Když čísla skutečně rozdrtíte, dospějete k následujícímu:

(23 x 22)/2 = 253

To je 253 zápasů ze skupiny 23 lidí. Vzhledem k tomu, že rok má pouze 365 dní, tento počet zápasů nás přivádí k šanci, která je mnohem větší než 50 procent .

Jistě, narozeninový paradox nezaručuje, že kdokoli bude mít shodné narozeniny, ale šance, že nastanou shodné narozeniny, jsou mnohem vyšší, než jsme si intuitivně mysleli.

Ne, nešli jsme jen na náhodnou tangentu, protože jsme nadšenci narozeninových oslav. Narozeninový paradox přímo souvisí s pravděpodobností hašovacích kolizí.

Pokud si s metaforou trochu zatřesete a zamyslíte se nad pravděpodobnostmi výskytu shodných hashů spíše než shodami narozenin, uvědomíme si, že šance na nalezení kolize v SHA-256 není 1/115,792,089,237,316,195,423,570,985,008,685,487,96 ,039,457,584,007,913,129,639,936 (naše 256bitové číslo v desítkové soustavě) jak jsme mohli očekávat.

Šance je ve skutečnosti mnohem vyšší, protože hledáme případnou kolizi , nejen konkrétní kolize pro určitý hash.

Jaká je tedy šance?

Bez narozeninového paradoxu bychom očekávali, že po projetí 50 procent celkových kombinací narazíme na odpovídající hash. Ve zkratce je to po pokusu 2²⁵⁵hash.

S narozeninovým útokem můžeme použít následující vzorec, abychom zhruba zjistili, kolik hashů bychom museli projít, než se dostaneme se stejnou pravděpodobností nalezení shody:

dva^(m/2)

Kde m = bitová velikost hashe.

Když tedy spustíme čísla pro 256bitovou hašovací délku SHA-256, dostaneme:

dva^(256/2)

dva⁽¹²⁸⁾

Takže v SHA-256 narozeninový útok snížil počet hashů, které se mají procházet, ze 2²⁵⁵do 2¹²⁸. Pokud nejste příliš obeznámeni s tímto typem matematiky, je snadné si myslet, že narozeninový útok ji zkrátí jen na polovinu. Ve skutečnosti je rozdíl mnohem větší.

Následující číslo je 2²⁵⁵psáno v desítkové soustavě:

57,896,044,618,658,097,711,785,492,504,343,953,926,634,992,332,820,282,019,728,792,003,956,596,88

A následující je 2¹²⁸

340,282,366,920,938,463,463,374,607,431,768,211,456

Jak vidíte, mezi těmito dvěma čísly jsou velké rozdíly, takže narozeninový útok výrazně usnadňuje útočníkovi najít odpovídající hash, než jste možná čekali .

S ohledem na to platí pravidlo, že 256bitový hash, jako je SHA-256, je snížen na 128 bitů, když se uvažuje o narozeninových útocích spíše než o hrubé síle. Stejně, MD5 128 bitů je sníženo na 64 bitů proti narozeninovým útokům.

Co je to kolizní útok?

Kolizní útok je jednoduše, když útočník najde jednu z těchto kolizí a použije ji k podkopání zabezpečení, které má hash poskytovat.

Příklady kolizních útoků

Zde jsou některé běžné příklady kolizních útoků:

Freestart kolizní útoky

Útoky kolizí Freestart jsou možné v hashovacích funkcích, které jsou založeny na Konstrukce Merkle Damgard . Tohle znamená tamto MD5 , SHA-1 a SHA-2 jsou zranitelné, ale ne SHA-3, která je místo toho navržena s houbovou konstrukcí.

za normálních podmínek , v prvním kole Merkle-Damgard hash funkce, vstupy jsou sada předdefinovaných inicializačních vektorů , stejně jako první blok dat zprávy. Možná budete chtít odkazovat na tento článek na Algoritmus MD5 pokud potřebujete další informace o tom, jak fungují hashovací funkce.

Kolize při volném startu je jiná, protože zahrnuje umožňující útočníkovi zvolit si vlastní inicializační vektory . To jim umožňuje snížit zabezpečení hashovací funkce. Proč by to někdo dělal? Výzkumníci to dělají v laboratoři, protože jim to umožňuje hrát si s hashovacími funkcemi a dává jim to větší vhled do jejich slabin.

Toto nejsou praktické útoky proti implementaci zabezpečené hashovací funkce , protože ve skutečnosti si útočník nemůže vybrat inicializační vektory. Jsou však důležité pro pochopení nedostatků dané hašovací funkce a pro vývoj lepších kryptografických hašovacích funkcí v budoucnu.

Klasický kolizní útok

V klasickém kolizním útoku je cílem najít dvě různé zprávy, které mají za následek stejný hash. Pokud si chceme udělat fantazii a napsat to matematicky:

• Zpráva 1: x
• Zpráva 2: a
• H(): hash ()

Klasický kolizní útok tedy spočívá v tom, že útočník najde dvě zprávy kde zpráva x nerovná se zpráva a , ale hash x rovná se hash y . Jinými slovy:

x ≠ y

Ale:

H(x) = H(y)

Šance na úspěšný kolizní útok nezávisí pouze na velikosti hashe, ale také na případných slabinách kryptografické hashovací funkce. Jak jsme diskutovali, i když hashovací funkce nemá žádné známé slabiny, stále se musíme obávat narozeninových útoků, spíše než jen útoky hrubou silou, které jsou mnohem obtížnější, protože vyžadují, aby útočník systematicky procházel každou jednotlivou kombinací, dokud nenajde kolizi .

Důsledky klasických kolizních útoků

Když se podíváme na rovnici H(x) = H(y), může být těžké zjistit, co to vlastně znamená pro bezpečnost. Pojďme to konkrétněji uvést příkladem.

Řekněme, že Jane pracuje ve společnosti a chce rychle zbohatnout. Řekněme, že každý týden dostává výplatní pásky za 1 000 $ jako PDF. Každý týden její šéf digitálně podepisuje výplatní pásky, aby výplatní páska věděla, že jsou legitimní.

Digitální podpis šéfa bude založen na hash pdf výplatní pásky . Jane tedy vezme dokument za svou výplatní pásku 1000 dolarů a začne si s ním hrát. Nejprve změní 1 000 $ na 1 000 000 $. Ale když hashuje tento dokument, hash již nebude odpovídat digitálnímu podpisu, protože dokument se změnil . Pokud se pokusí získat výplatní pásku, aby ji vyplatila, když půjdou ověřit podpis, uvidí, že se neshoduje a že výplatní páska je nelegitimní.

Ale Jane je příliš chytrá na to, aby její lest byla takto proražena, a tak se vrátí k pohrávání si s dokumentem. Začne experimentovat s různými fonty, různými velikostmi, změnou okrajů, změnou barvy, přehozením textu a tisíci dalších drobných změn. Dokument opakovaně hashuje, aby zjistila, zda jí změny přinesou shodu. Nakonec se po nesčetných změnách a velké kávě stane zázrak a hash je úplně stejný jako hash původní výplatní pásky za 1000 dolarů.

Všechny tyto změny byly relativně malé. Dokonce i věci, které jen okrajově změní vzhled dokumentu, budou mít za následek úplně jiné hashe dokázala vytvořit dokument, který se zdá být legitimní, ale ve skutečnosti není .

Jediné, co musí Jane udělat, je vzít tuto verzi své výplatní pásky v hodnotě 1 000 000 $ na výplatní pásku spolu s originálním digitálním podpisem. Výplatní listina může zvednout obočí, ale když jdou zkontrolovat digitální podpis, všechno funguje. Připadá jim to legitimní a nejsou dostatečně placeni, aby se obtěžovali kladením otázek, takže schvalují výplatu Jane v milionech dolarů. Než účetní oddělení přijde na Janin mazaný podvod, už je na pláži a popíjí mojito v zemi, kde se nevydává.

Je to trochu přehnaný příklad, ale ukazuje základní hrozbu klasických kolizních útoků. Když jsou možné, umožňují útočníkovi podkopat integritu a autenticitu digitálních podpisů , což jim umožňuje způsobovat nejrůznější problémy, jako je páchání podvodů. To je důvod, proč naše kryptografické hašovací algoritmy musí být odolné vůči kolizím.

Útoky na kolize se zvolenými prefixy

Útoky na kolize se zvolenými prefixy jsou dalším typem kolize, na které jsou hashovací funkce Merkle-Damgard zranitelné. Jsou výrazně náročnější, ale za okolností, kdy jsou možné, představují mnohem větší hrozbu než klasické kolizní útoky .

Na rozdíl od klasických útoků na kolize, které jsme popsali výše, kolize se zvoleným prefixem zahrnuje další omezení. Útočník musí být schopen najít kolize, které zahrnují dvě předem specifikované předpony, než aby byl schopen pouze najít případné kolize.

Protivníkovi jsou přiděleny dvě předpony zpráv, což v podstatě znamená, že jsou mu přiděleny dva samostatné řetězce dat. Protivník je poté vyzván, aby našel samostatnou zprávu pro každou předponu, kde kombinace předpon a zpráv sdílejí stejný hash. Nebudeme si lhát, pokud se nezabýváte kryptografií, může to být trochu těžké zamotat si hlavu.

Ve formálnější notaci jsou předpony P a P‘, zatímco zprávy jsou M a M‘. Takže vzhledem k P a P' musí hacker najít zprávy M a M', kde:

H(P || M) = H(P’ || M’)

Ve výše uvedené rovnici || představuje zřetězení , což v podstatě znamená, že předpona a zpráva jsou vzájemně spojeny.

Důsledky útoků s kolizí se zvolenými prefixy

Výsledek útoku s kolizí se zvolenou předponou je velmi podobný jako u klasických kolizních útoků. Útočník může v zásadě podkopat opatření pro ověřování a integritu, což mu umožňuje páchat podvody a podvody, stejně jako jsme to ukázali v Důsledky klasických kolizních útoků sekce.

Hlavním rozdílem je, že kvůli dalším omezením je mnohem těžší dosáhnout kolizí se zvolenými předponami. Pokud jsou však možné, je pro útočníka mnohem snazší vytvořit dokumenty, které produkují odpovídající hodnoty hash.

Útočníci se nemusí snažit provádět nekonečné změny v naději, že nakonec přijdou s jiným dokumentem, který vytvoří stejný hash. Místo toho mohou pouze vytvořit dva různé dokumenty, podložit je tak, aby měly stejnou délku, a pak přidat specificky vypočítaný řetězec dat, jehož výsledkem jsou stejné hodnoty hash pro oba dokumenty. Díky tomu je výrazně jednodušší vytvářet různé dokumenty, které mají stále odpovídající hodnoty hash.

Předobrazové útoky

Preimage útoky souvisejí s kolizními útoky, ale zahrnují snahu najít zprávy, které vedou ke konkrétním hashům. V budoucím článku se na ně ponoříme hlouběji, ale prozatím byste si měli uvědomit, že:

• Předobrazový útok — Zahrnuje převzetí daného hashe a následné zjištění počátečního vstupu, který jej vytvořil.
• Druhý předobrazový útok — Zahrnuje převzetí daného vstupu a nalezení dalšího vstupu, kde oba vstupy vedou ke stejnému hash.

Srážky v MD5

MD5 je stará hashovací funkce, která již není pro mnoho aplikací považována za bezpečnou. Výsledkem jsou 128bitové haše, které když se berou v úvahu narozeninové útoky, ve skutečnosti to znamená, že má pouze 64 bitů zabezpečení .

V devadesátých letech byla objevena jak pseudosrážka, tak polokolize při volném startu samostatných výzkumníků . I když to byla znepokojivá obvinění ohledně budoucí bezpečnosti MD5, ani pravé kolize nebyly .

Až v roce 2004 byly týmem akademiků publikovány úplné kolize MD5. Na IBM P690 byli schopni najít kolize MD5 za méně než hodinu. To ukázalo, že MD5 je skutečně rozbité a svět se musel rychle vzdálit od MD5, aby zabránil kolizním útokům, aby se rozšířily v reálném světě.

Útok na kolizi s vybranou předponou byl poprvé ukázán proti MD5 in 2007 . Výzkumníci toho dosáhli s očekávanými náklady dva^padesáti . To funguje někam do říše tisíc bilionů pokusů než se očekává kolize. V té době však byly praktické aplikace útoku omezené.

Vědci také zkoumali klasické srážky v MD5 a zjistili to slabiny v hashovací funkci jim umožnily zkonstruovat dva certifikáty X.509 se stejným podpisem . To znamenalo důležité důsledky v reálném světě, protože to znamenalo, že jsme již nemohli důvěřovat pravosti certifikátů X.509, které používaly hash MD5.

Došlo k řadě dalších kolizí proti MD5, jak teoretických, tak praktických. Protože je však algoritmus již dobře a skutečně pro mnoho účelů rozbitý, nemá cenu se do nich pouštět.

Kolize v SHA-1

SHA-1 vytváří hashe o délce 160 bitů, což mu v praxi poskytuje 80bitové zabezpečení proti narozeninovým útokům. V roce 2005 jeden tým akademiků nalezené kolize ve zmenšené verzi SHA-1 na 53 kol. Full SHA-1 má ve skutečnosti 80 kol, což je v podstatě počet, kolikrát jsou vstupy promíchány algoritmem. I když srážka z 53 ran je významná, ke srážce na 80 ran má stále daleko.

Také ten rok navrhl samostatný tým výzkumníků útok, který zjištěné kolize za méně než dva⁶⁹operace (to je 590,295,810,35 8,705,651,712 pokusů) , což bylo výrazné zlepšení útoků hrubou silou. Jejich přístup byl postaven na diferenciálním útoku spolu s modifikací zpráv a víceblokovými kolizemi.

Do srpna 2005 byl útok vylepšen do bodu, kdy bylo možné nalézt kolize v SHA-1 v dva⁶³operace .

V roce 2006 došlo k výraznému zlepšení kolizí pro zmenšené kolo SHA-1, přičemž výzkumník zveřejnil zjištění kolize pro 64 kol . V roce 2010 došlo k dalšímu skoku, k němuž se přidal další výzkumník 73 kol . To bylo jen další znamení, že dny SHA-1 byly sečteny.

V roce 2011, NIST zastaral SHA-1 , což naznačuje, že by již neměl být implementován. V roce 2012 Marc Stevens odhadl, že jde o diferenciální útok mohl zlomit jeden hash SHA-1 za cenu 2,77 milionu dolarů .

První kolize při volném startu proti SHA-1 byl nalezen v roce 2015. Útok, přezdívaný s kreativním názvem SHAppening , trvalo pouze 10 dní na clusteru s 64 GPU.

Následovalo SHAppening Roztříštěný , pokračující v trendu kryptografických hříček. K SHAttered došlo v roce 2017 a byla to první klasická kolize objevená pro SHA-1. S tak jasně demonstrovanou plnou srážkou to bylo nadmíru jasné SHA-1 již nemohl zaručit integritu a autentizaci souborů nebo digitálních podpisů .

V roce 2020 akademici zveřejnili útok na kolizi s vybranou předponou proti SHA-1. Název listu potvrdil nově zavedenou tradici a SHA-1 je Shambles ukázal, že nyní bylo pro útočníky ještě snazší podkopat integritu a autentizační opatření. Ačkoli byl SHA-1 dlouho považován za nejistý, toto byla první veřejně odhalená kolize se zvoleným prefixem.

Ačkoli SHA-1 není bezpečné pro použití ve věcech, jako jsou digitální podpisy, je stále v pořádku, aby byl implementován do autentizačního kódu zprávy založeného na hash (HMAC).

Srážky v SHA-2

SHA-2 je v současnosti považován za zlatý standard v kryptografických algoritmech a je široce implementován v našem digitálním světě.

Skutečnost, že je stále považována za bezpečnou, by vám měla naznačovat, že kolize proti ní v této fázi příliš nezasáhly. Pokud by byly nalezeny klasické kolize nebo kolize se zvolenými prefixy, museli bychom se všichni extrémně obávat o naši online bezpečnost.

I když je to stále považováno za bezpečné, kryptografové usilovně pracovali na jeho prolomení. SHA-256 je 256bitový algoritmus, který mu poskytuje 128bitové zabezpečení proti narozeninovým útokům . SHA-512 má dvojnásobnou bitovou délku, což mu dává 256 bitů zabezpečení proti narozeninovým útokům.

V roce 2008 byl nejlepší redukovaný kruhový útok, jaký mohl najít kolize ve 24 z 80 ran SHA-256 a 24 z 80 ran SHA-512. V roce 2011 byl schopen způsobit diferenciální útok vyššího řádu pseudosrážky na 33 ze 64 ran SHA-256.

A papír v roce 2013 předvedl kolize proti 31 nábojům SHA-256 a kolize semi-freestart proti 38 kolům. V roce 2014 a sondování papíru SHA-512 použil heuristiku větvení při hledání diferenciálních kolizí, což vedlo k pseudo kolizi ve 38 z 80 kol.

V roce 2016 výzkumníci analyzoval jak SHA-256, tak SHA-512 . Našli praktické kolize proti 28 z 64 ran SHA-256 a kolize proti 27 z 80 ran SHA-512 . Našli také pseudosrážku proti 39 nábojům SHA-512.

Každý z těchto útoků má stále ještě daleko k tomu, aby představoval smysluplnou hrozbu pro bezpečnost SHA-2. V této fázi se nemusíme příliš obávat kolizí s SHA-2. Pro výzkumníky je však stále klíčové, aby pokračovali ve zkoumání SHA-2 a hledali slabiny. Pokud to neudělají, národní státy a organizovaní zločinci stále budou a neřeknou nám, kdy se jim podaří najít proveditelné kolize.

Srážky v SHA-3

SHA-3 je nejnovější v řadě Secure Hash Algorithms. SHA-3 není implementováno příliš často, protože SHA-2 je stále považováno za bezpečné a v této fázi nemá smysl vynakládat úsilí na přesun.

Přestože je novější, nemusí být nutně bezpečnější než SHA-2. Oba se vyznačují dramaticky odlišným vnitřním designem a SHA-3 nebyl studován tolik jako SHA-2 kvůli jeho relativní aktuálnosti . Spíše než o upgradu na SHA-2 je lepší o něm uvažovat jako o náhradním, protože opravdu nevíme, který algoritmus obstojí ve zkoušce času.

Výhodou dvou zcela odlišných kryptografických hashovacích algoritmů je však to, že pokud je nalezen útok proti jednomu z nich, předpokládá se, že druhý bude stále odolný. To znamená, že v případě potřeby můžeme rychle přejít na jiný.

Nyní, když chápete roli SHA-3, můžeme se podívat na některé z nejlepších útoků proti němu. V roce 2012 a byl vydán papír který ukázal kolize až v pěti kolech algoritmu který by se stal SHA-3. Výzkumníci použili zobecněné vnitřní diferenciály k cílení na několik verzí algoritmu, známého jako Keccak.

Vědci našli kolize pro tříkolové verze Keccak-384 a Keccak-512. Našli také útok, který byl 2^{Čtyři. Pět}krát rychlejší než narozeninový útok proti 4kolovému Keccaku-384. Proti Keccaku-256 se jim podařilo najít kolize na pět kol . Tyto pokusy však zdaleka nepředstavovaly hrozbu pro algoritmy, z nichž každý má 24 kol.

Do roku 2019 byl dokončen algoritmus SHA-3 a skupina akademiků zveřejnil další článek na útocích proti němu. Rozdíly mezi Keccakem a finální verzí SHA-3 jsou tak marginální, že tyto dvě bezpečnostní analýzy zkoumaly v podstatě totéž.

Tento druhý článek byl postaven na práci dřívějších výzkumníků a tentokrát akademiků schopný dosáhnout kolizí proti šesti kolům SHA-3 . I když tento skok ukázal určitý pokrok, je stále daleko od toho, aby představoval hrozbu pro celých 24 kol SHA-3.

Zabezpečení vašich systémů proti útokům kolize

Průměrný Joe nemůže udělat příliš mnoho pro to, aby se zajistil proti kolizím, kromě základních věcí, jako je aktualizace na nejnovější verze aby se ujistili, že nepoužívají zranitelný software z roku 2002.

Vývojáři se musí ujistit, že používají pouze kryptografické hashovací algoritmy, které jsou pro svůj účel bezpečné . V případě věcí, jako jsou digitální podpisy, musí používat algoritmy jako SHA-2 nebo SHA-3, aby bylo zajištěno, že podpisům lze důvěřovat z hlediska integrity a ověřování.

Kromě toho se vývojáři musí každých pár let kontrolovat, aby udrželi krok se stavem zabezpečení jakéhokoli algoritmu, který používají. Pokud jsou útoky proti jimi implementovanému hashovacímu algoritmu stále závažnější, musí začít proces přepínání. Pokud tak neučiní, jejich systémy by mohly být zranitelné vůči kolizním útokům a podvodům, které je obklopují.