Čo je Hash Collision?
Hash Collision nastane vtedy, keď dva odlišné vstupy produkujú presne ten istý hash výstup. Predstavte si dva odlišné kľúče, ktoré nejako otvoria ten istý digitálny zámok. Zriedkavé, ale ak sa stane s nesprávnym algoritmom, drama.
„Ak existuje jedna kolízia, všetko je rozbité.“ Nie úplne. Silné algoritmy sú navrhnuté tak, aby akákoľvek praktická Hash Collision bola mimoriadne nepravdepodobná a moderne systémy pridávajú vrstvy, aby jedna zvláštnosť nezakolísala domom.
Ako Hash Collision funguje
Predstavte si hash ako malý štítok pre veľké dáta. Tu je krátka jazda od vstupu k oops.
- Vstup: Začínate s akoukoľvek správou, súborom alebo transakciou.
- Hash: Funkcia z rodiny cryptographic hash functions zmení tento vstup na reťazec pevnej dĺžky.
- Collision: Pretože výstupy sú obmedzené, ale vstupy nekonečné, dva odlišné vstupy môžu mapovať na ten istý výstup.
- Útok: Závažná hrozba nastáva, keď niekto dokáže úmyselne vytvoriť dva odlišné vstupy, ktoré kolidujú, a potom vymeniť jeden za druhý.
- Obrana: Dobré algoritmy robia takéto vyhľadávanie astronomicky nákladným, takže náhodné hádanie šetrí čas a peniaze.
Hej, to je nápad.
Prečo Hash Collision má význam
Prečo by vás mala zaujímať táto tichá oblasť matematiky a kódu?
- Výhoda: Silný odpor udržuje vaše štítky dát jedinečné, čo znamená menej priestoru pre tajné triky.
- Perspektíva: Kolízie ohrozujú integritu pre veci ako blockchain technology, softvérové aktualizácie a overovanie súborov.
- Relevantnosť: Stretnete ich vo walletoch, výmenách, dôkazoch a audítorských nástrojoch, ktoré dôverujú rovnosti hashov.
Keď táto možnosť existuje, vyberajte schémy, ktoré vrstvíjú obranu ako Double Hashing, a držte sa široko preskúmaných algoritmov s dlhými výstupmi.
Kľúčové charakteristiky Hash Collision
Čo robí tento jav výnimočným a stojí za poznámku:
- Nepravidelnosť: S obmedzenými výstupmi a neobmedzenými vstupmi sa nejaký pár stretne kolíziou podľa Pigeonhole princípu.
- Tíživý: Pre moderné hash-y sa nájdenie kolízie zámerne navrhuje byť výpočtovo brutálne.
- Podpisy: Mnoho digitálnych podpisov podpisuje hash, takže odolnosť voči kolícii chráni podpisujúcich pred falošnými správami.
Ako sa vypočítava Hash Collision?
Môžete odhadovať snahu pomocou myšlienky s narodeninami. Pre hash s k-bitmi je počet náhodných pokusov potrebných na približne 50% šancu na kolíziu približne druhá odmocnina z 2 na mocnina k, vynásobená približne jednou a siedmimi desatinami.
n_fifty_percent ≈ 1.1774 * sqrt(2^k) Príklad: pri k = 256 sú potrebné pokusy neuveriteľne veľké, čo je dôvod, prečo pre násilné nájdenie kolízie cez brutálnu silu nie je víkendový projekt.
Variácie
Rôzne odrody sa objavujú vo výskume a útokoch:
- Kolízia: Akékoľvek dve odlišné vstupy zdieľajú ten istý hash.
- Druhá: Dané jeden vstup, nájsť ďalší, ktorý zodpovedá jeho hash.
- Preimage: Daný hash nájsť akýkoľvek vstup, ktorý mu zodpovedá.
- Prefix: Zvolená kolízia prefixu vytvorí dve správy s odlišnými začiatkami, ktoré končia rovnakým hashom.
SHA dva päť šest nemá verejnú, praktickú kolíziu. Ak niekto tvrdi, že ju má, očakávajte hlučnú revíziu komunity a výsledky testov predtým, ako zbesilíte alebo oslavujete.
Príklad
Ak by útočník dokázal vytvoriť dve odlišné transakcie so rovnakým txid, mohol by skúsiť trik Dvojité míňanie výmenou blizna po tom, čo podpíšete.
Zaujímavosť
Kolízie MD5 boli ukázané už pred desaťročiami a projekt SHAttered priniesol verejné SHA jedna kolíziu so dvoma odlišnými PDF súbormi, mic drop, ktorý prinútil odchod z tohto štandardu.
Záver
V jednej vete, Hash Collision je zriedkavý prípad, keď dva odlišné vstupy zdieľajú jeden digitálny otlačok, a moderná kryptografia tvrdo pracuje na tom, aby sa to nestalo viac než trivia.