Ütközési ellenállás
Az ütközési ellenállás a kriptográfiai hash függvények tulajdonsága : a H kriptográfiai hash függvény ütközésálló, ha nehéz két bemenetet találni, amelyek ugyanazt a hash értéket adják ; azaz két A és B bemenet, amelyek :, és A ≠ B
Egy hash függvénynek, amelynek több bemenete van, mint kimenete, szükségszerűen ütközéseket kell generálnia. Vegyünk egy hash függvényt, mint például az SHA-256 , amely tetszőleges hosszúságú bemenetből 256 bites kimenetet állít elő. Mivel a függvénynek a 2256 kimenet egyikét kell generálnia egy sokkal nagyobb bemeneti készlet minden tagjára, a fiók elve biztosítja, hogy egyes bemenetek azonos hash értékkel rendelkezzenek. Az ütközési ellenállás nem azt jelenti, hogy nincsenek ütközések, csak azt, hogy az ütközéseket nehéz megtalálni.
A születésnapi paradoxon szemlélteti az ütközési ellenállás felső határát: ha egy hash függvény N kimeneti bitet eredményez, akkor a támadó, aki 2 N / 2 (vagy ) hash műveletet tesztel véletlenszerű bemeneteken, valószínűleg két azonos kimenetet talál. Ha van egy egyszerűbb módszer, mint ez a durva erő támadása két azonos kimenet megtalálásához, akkor a kivonatolási funkció nem megfelelő, hogy kriptográfiai kivonatoló funkcióként szolgáljon.
A kriptográfiai kivonatoló funkciókat általában ütközésállónak tervezik. Azonban sok hash funkció, amelyet vélhetően ütközésállónak tartanak, megtört. Például a durva erőnél hatékonyabb technikák ismerik az MD5 és az SHA-1 hash funkciók ütközéseit . Másrészt vannak matematikai bizonyítékok arra vonatkozóan, hogy egyes hash függvények esetében az ütközések megtalálása legalább olyan nehéz, mint néhány nehéz matematikai probléma, például a faktorizálás vagy a diszkrét logaritmus . Állítólag ezek a funkciók biztonságosnak bizonyultak .
használat
Ütközési ellenállás több esetben is kívánatos:
- egyes digitális aláírási rendszerekben a hatóság a dokumentum hitelességét azáltal igazolja, hogy nyilvános kulcsú aláírást tesz közzé a dokumentum hash értékén; ha lehetséges két azonos kivonatértékű dokumentum előállítása, a támadó megszerezheti az egyik hatóság hitelességét egy dokumentumon, majd azt állíthatja, hogy a hatóság tanúsította egy másik dokumentum hitelességét;
- a munka egyes igazolásaiban a felhasználók hash ütközéseket adnak meg annak bizonyítékaként, hogy jelentős mennyiségű számítást végeztek; ha az ütközések megtalálása egyszerűbb, mint a durva erő , a felhasználók jelentős mennyiségű számítás elvégzése nélkül is megtalálhatják az ütközéseket;
- egyes elosztott fájlrendszerekben a felek összehasonlítják a fájlok kivonatolási értékeit, hogy megbizonyosodjanak arról, hogy a fájl azonos verziója van; egy támadó, aki két azonos hash értékkel rendelkező fájlt képes előállítani, elhitetheti a felhasználókat, hogy azt higgyék, ugyanaz a fájl verziójuk, amikor valójában különböző fájljaik vannak.
Megjegyzések és hivatkozások
(fr) Ez a cikk részben vagy egészben venni a Wikipedia cikket angolul című „ ütközés ellenállása ” ( lásd a szerzők listáját ) .- Goldwasser és Bellare 2008 , p. 136.
- Goldwasser és Bellare 2008 , p. 143.
- Pass, R. "21. előadás: Ütközésálló hash funkciók és általános digitális aláírási séma" . Titkosítási tanfolyam, Cornell Egyetem, 2009.
- Xiaoyun Wang és Hongbo Yu, " Hogyan lehet megtörni az MD5 és más hash funkciókat " (megtekintés : 2009. december 21. )
- Xiaoyun Wang, Yiquin Lisa Yin, Hongobo Yu, „ Ütközések megtalálása a teljes SHA-1-ben ” .
- Galbraith 2012 .
Függelékek
Bibliográfia
- (en) Shafi Goldwasser és Mihir Bellare , „ Előadási jegyzetek a rejtjelezésről ” [PDF] ,2008. július(megtekintés : 2016. február 6. ) .
- [Galbraith 2012] (en) Steven Galbraith, nyilvános kulcsú rejtjelezés matematikája , Cambridge-i egyetemi sajtó,2012( olvassa el online [PDF] ) , „3.5 Számelméleti kivonatolási funkciók”