Preimage attack

V kryptografii , útok preimage je klasifikace útoků na hašovací funkce pro nalezení zprávu , která má specifickou hodnotu hash.

Existují dva typy nalezení vzoru útoků:

• (První) preimage útok : stejně hash h , najít zprávu m (preimage) takové, žehash (m) = h .

• Druhý-preimage útok : stejně pevnou zprávu m1 , najít jiný zprávu m2 (druhý preimage) takové, že hash (m2) = hash (m1) .

Ty mohou být ve srovnání s kolizní útok , který zahrnuje nalezení dvou libovolně různé zprávy m1 a m2 taková, že hash (m2) = hash (m1) .

[ upravit překlad ]Aplikovaná preimage útočí

Podle definice, ideální hashovací funkce je taková, že nejrychlejší způsob, jak vypočítat první nebo druhé preimage je přes hrubou silou . Pro n-bitové hash, tento útok má časovou složitost  , která je považována za příliš vysoká pro typický výstupní velikosti n = 160 bitů. Je-li takový složitost je nejlepší, že lze dosáhnout protivníkem, pak funkce mřížky je považován preimage odolný.

Rychlejší nalezení vzoru útoky lze nalézt cryptanalysing určité hash funkce, a jsou specifické pro tuto funkci. Některé významné preimage útoky již byly objeveny, ale dosud nejsou praktické. Pokud praktický preimage útok je objeven, bylo by to výrazně ovlivnit mnoho internetových protokolů. V tomto případě, "praktická" znamená, že by to mohlo být vykonán útočníkem smysluplným množství času pro smysluplné množství peněz. Preimaging útok, který stojí biliony dolarů a trvá desítky let preimage jednu požadovanou hodnotu hash nebo jedna zpráva není praktické, který stojí několik tisíc dolarů a trvá několik týdnů může být velmi praktické.

Všechny aktuálně známé praktické nebo téměř praktické útoky na MD5 aSHA-1 jsou kolize . Obecně platí, že kolize útok je jednodušší montáž než útok preimage, jako jeho není omezena nějakým nastavenou hodnotu (nějaké dvě hodnoty mohou být použity k srazí). Časová složitost kolizní útok, naopak je