Preimage útok - Preimage attack

V kryptografii se útok preimage na kryptografické hashovací funkce pokusí najít zprávu, která má konkrétní hodnotu hash. Kryptografická hashovací funkce by měla odolat útokům na její preimage (sada možných vstupů).

V kontextu útoku existují dva typy odporu preimage:

  • odpor preimage : pro v podstatě všechny předdefinované výstupy je výpočetně nemožné najít jakýkoli vstup, který má na tento výstup hash; tj. vzhledem k y je obtížné najít x takové, aby h ( x ) = y .
  • odpor druhé preimage : je výpočetně nemožné najít jakýkoli druhý vstup, který má stejný výstup jako výstup zadaného vstupu; tj. vzhledem k x je obtížné najít druhou preimage x ′ ≠ x takovou, že h ( x ) = h ( x ′) .

Ty lze srovnávat s kolizním odporem , ve kterém je výpočetně nemožné najít jakékoli dva odlišné vstupy x , x ′, které mají hash na stejný výstup; tj. takové, že h ( x ) = h ( x ′) .

Odolnost proti kolizi implikuje odpor druhé preimage, ale nezaručuje odolnost preimage. Naopak útok druhé preimage implikuje kolizní útok (triviálně, protože kromě x ′ je x známé již od začátku).

Aplikované preimage útoky

Podle definice je ideální hashovací funkce taková, že nejrychlejší způsob výpočtu první nebo druhé preimage je útokem hrubou silou . Pro n -bitový hash má tento útok časovou složitost 2 n , což je považováno za příliš vysoké pro typickou velikost výstupu n = 128 bitů. Pokud je taková složitost to nejlepší, čeho lze dosáhnout protivníkem, pak je hašovací funkce považována za preimage rezistentní. Existuje však obecný výsledek, že kvantové počítače provádějí útok strukturované preimage v √ 2 n = 2 n / 2 , což také znamená druhou preimage a tedy kolizní útok.

Rychlejší útoky na preimage lze najít dešifrováním určitých hashovacích funkcí a jsou specifické pro tuto funkci. Některé významné preimage útoky již byly objeveny, ale nejsou dosud praktické. Je-li objeven praktický útok na preimage, drasticky by to ovlivnilo mnoho internetových protokolů. V tomto případě „praktické“ znamená, že by jej mohl provést útočník s přiměřeným množstvím zdrojů. Například útok na předběžné zobrazení, který stojí biliony dolarů a trvá desítky let, než předimenzuje jednu požadovanou hodnotu hash nebo jednu zprávu, není praktický; ten, který stojí pár 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 a SHA-1 jsou kolizní útoky . Obecně platí, že kolizní útok je snazší připojit než útok preimage, protože není omezen žádnou nastavenou hodnotou (ke srážce lze použít libovolné dvě hodnoty). Časová složitost kolizního útoku hrubou silou je na rozdíl od útoku preimage pouze 2 n / 2 .

Omezené preimage vesmírné útoky

Výpočetní neproveditelnost prvního preimage útoku na ideální hashovací funkci předpokládá, že množina možných hashovacích vstupů je příliš velká pro hledání hrubou silou. Pokud je však známo, že daná hash hodnota byla vytvořena ze sady vstupů, která je relativně malá nebo je nějakým způsobem uspořádána podle pravděpodobnosti, pak může být efektivní vyhledávání hrubou silou. Praktičnost závisí na velikosti vstupní sady a rychlosti nebo nákladech na výpočet hashovací funkce.

Běžným příkladem je použití hashů k ukládání dat pro ověření hesla pro ověřování. Spíše než ukládat prostý text uživatelských hesel, systém řízení přístupu ukládá hash hesla. Když uživatel požaduje přístup, je heslo, které zadá, hašováno a porovnáno s uloženou hodnotou. Pokud dojde k odcizení uložených ověřovacích dat, bude mít zloděj pouze hodnoty hash, nikoli hesla. Většina uživatelů si však vybírá hesla předvídatelným způsobem a mnoho hesel je dostatečně krátkých na to, aby bylo možné testovat všechny možné kombinace, pokud se používají rychlé hashe, i když je hash hodnocen jako bezpečný proti útokům předběžného obrazu. Pro pomalé vyhledávání byly vytvořeny speciální hashe, které se nazývají funkce odvozování klíčů . Viz Prolomení hesla .

Viz také

  • Narozeninový útok
  • Kryptografická hashovací funkce
  • Shrnutí zabezpečení funkce hash
  • Duhový stůl
  • Náhodný věštec
  • RFC   4270 : Útoky na kryptografické hašování v internetových protokolech

Reference

  1. ^ a b c d e Rogaway, P .; Shrimpton, T. (2004). „Základy kryptografické hashovací funkce: Definice, důsledky a separace pro odpor obrazu, odpor druhého obrazu a odolnost proti kolizi“ (PDF) . Rychlé softwarové šifrování . Springer-Verlag . Vyvolány 17 November 2012 .
  2. ^ Daniel J. Bernstein (12.11.2010). „Kvantové útoky proti Blue Midnight Wish, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Shabal, SHAvite-3, SIMD a Skein“ (PDF) . University of Illinois v Chicagu . Citováno 2020-03-29 .
  3. ^ Bruce Morton, Clayton Smith (2014-01-30). "Proč musíme přejít na SHA-2" . Rada bezpečnosti certifikační autority . CS1 maint: používá parametr autorů ( odkaz )
  4. ^ „MD5 a perspektivy“ . 2009-01-01.
  5. ^ „Google Online Security Blog: Oznamujeme první kolizi SHA1“ . Citováno 2017-02-23 .
  6. ^ Goodin, Dan (2012-12-10). „Klastr 25 GPU prolomí každé standardní heslo systému Windows za <6 hodin“ . Ars Technica . Citováno 2020-11-23 .