Co je Hash Collision?
Hash Collision nastane, když dva odlišné vstupy vytvoří přesně stejný hash. Představte si dva různé klíče, které nějak otevřou stejný digitální zámek. Vzácné, ale pokud se to stane u nevhodného algoritmu, může to způsobit problémy.
„Pokud existuje jedna kolize, všechno je rozbité.“ Není to tak jednoduché. Silné algoritmy jsou navrženy tak, aby praktická Hash Collision byla velmi nepravděpodobná, a moderní systémy přidávají vrstvy, aby jedna anomálie nesvrhla celý systém.
Jak Hash Collision funguje
Představte si hash jako malý štítek pro velká data. Krátká ukázka od vstupu až po problém.
- Vstup: Začínáte s libovolnou zprávou, souborem nebo transakcí.
- Hash: Funkce z rodiny kryptografických hashovacích funkcí přemění tento vstup na řetězec pevné délky.
- Srážka: Protože výstupy jsou omezené a vstupů je nekonečně mnoho, dva odlišné vstupy mohou vést ke stejnému výstupu.
- Útok: Závažná hrozba nastává, pokud někdo cíleně vytvoří dva odlišné vstupy, které kolidují, a poté jeden zamění za druhý.
- Obrana: Kvalitní algoritmy činí takové hledání astronomicky nákladným, takže náhodné hádání spotřebuje čas i peníze.
Ano, o tom to je.
Proč je Hash Collision důležitý
Proč by vás měl zajímat tento nenápadný aspekt matematiky a kódu?
- Výhoda: Silná odolnost udržuje označení vašich dat jedinečné, což zanechává méně prostoru pro skryté triky.
- Dopad: Kolize ohrožují integritu u věcí jako technologie blockchainu, aktualizací softwaru a ověřování souborů.
- Význam: Setkáte se s tím v peněženkách, směnárnách, důkazech a kontrolních nástrojích, které spoléhají na shodu hashů.
Když je taková možnost k dispozici, volte schémata, která vrství obranu, například dvojité hašování, a držte se algoritmů, které prošly širokou kontrolou a mají dlouhé výstupy.
Hlavní vlastnosti Hash Collision
Co dělá tento jev zvláštním a proč si ho stojí za to zapamatovat:
- Nevyhnutelné: Při omezeném počtu výstupů a neomezeném počtu vstupů některé dvojice musí kolidovat podle Dirichletova principu.
- Těžké: U moderních hashů je záměrné nalezení kolize navrženo tak, aby bylo výpočetně velmi náročné.
- Podpisy: Mnoho digitálních podpisů podepisuje hash, takže odolnost vůči kolizím chrání podepisující před podvodnou výměnou zpráv.
Jak se Hash Collision počítá?
Snahu lze odhadnout pomocí principu narozenin. Pro kbitový hash je počet náhodných pokusů potřebný pro přibližně padesátiprocentní pravděpodobnost některé kolize přibližně druhá odmocnina ze dvě na k, násobená asi 1,1774.
n_fifty_percent ≈ 1.1774 * sqrt(2^k) Příklad: pro k rovno 256 jsou požadované pokusy nepředstavitelně početné, a proto hrubou silou nedosáhnete kolize během víkendu.
Variace
Různé varianty se objevují ve výzkumu a při útocích:
- Kolize: Jakékoli dva odlišné vstupy sdílejí stejný hash.
- Druhý případ: Majíce jeden vstup, najít jiný, který dává stejný hash.
- Předobraz: Majíce hash, najít jakýkoli vstup, který se na něj mapuje.
- Prefix: Kolize s vybraným prefixem vytvoří dvě zprávy s odlišnými zvolenými začátky, které končí stejným hashem.
SHA two five six nemá veřejnou praktickou kolizi. Pokud někdo takovou kolizi tvrdí, očekávejte důkladnou recenzi a výsledky testů, než začnete panikařit nebo slavit.
Příklad
Kdyby útočník mohl vytvořit dvě různé transakce se stejným txid, mohl by se pokusit o trik dvojího utracení tím, že po vašem podpisu zamění jednu z dvojice.
Zajímavost
Kolize MD5 byly prokázány už před desetiletími a projekt SHAttered vytvořil veřejnou kolizi SHA one se dvěma různými PDF, což vedlo k vyřazení tohoto algoritmu z používání.
Shrnutí
Stručně řečeno, Hash Collision je vzácný případ, kdy dva různé vstupy sdílejí jeden digitální otisk, a moderní kryptografie se snaží tomu zabránit, aby to bylo víc než jen zajímavost.