Jaký je rozdíl mezi funkcí hash a kryptografickou funkcí hash?

Question

Myslím, je to jen otázka „jak obtížné je obrátit funkci se současnou technologií“?

Nebo existuje matematický koncept nebo vlastnost, která je činí odlišnými?

Pokud je to otázka „jak obtížné je obrátit funkci“, pak je správné říci, že s postupem technologie přestávají být některé kryptografické hašovací funkce kryptografické jen pro hašovací funkce? Stalo se to, co se stalo s MD5?

CodesInChaos · Accepted Answer

Každá kryptografická hašovací funkce je hašovací funkce. Ale ne každá hashovací funkce je kryptografický hash.

Cílem kryptografické hašovací funkce je zaručit řadu bezpečnostních vlastností. Nejdůležitější je, že je těžké najít kolize nebo předběžné obrazy a že výstup se zdá být náhodný. (Existuje několik dalších vlastností a "tvrdý" má v tomto kontextu dobře definované hranice, ale to zde není důležité.)

Nekryptografické hašovací funkce se snaží zabránit kolizím pro vstup, který není škodlivý. Někteří si kladou za cíl odhalit náhodné změny v datech (CRC), jiní se snaží umístit objekty do různých kbelíků v hašovací tabulce s co nejmenším počtem kolizí.

Výměnou za slabší záruky jsou obvykle (mnohem) rychlejší.

Stále bych nazval MD5 kryptografickou hašovací funkcí, protože jejím cílem bylo zajistit bezpečnost. Ale je to rozbité, a proto už není použitelné jako kryptografické hash. Na druhou stranu, pokud máte nekryptografickou hashovací funkci, nemůžete ji opravdu nazvat „zlomenou“, protože se nikdy vůbec nepokusila o bezpečí.

jupp0r · Answer

Existují některé vlastnosti, které kryptograficky zabezpečené hashovací funkce silně vyžadují, které nejsou pro kryptograficky zabezpečené hashovací funkce vyžadovány:

odolnost předimage (vzhledem k hash h musí být obtížné najít zprávu m, která při hašování vydá h
slabý kolizní odpor (na základě zprávy m1 musí být obtížné najít jinou zprávu m2 aby m1 a m2 dát stejný hash)
silný kolizní odpor (mělo by být obtížné najít jakékoli zprávy m1 a m2, které poskytují stejný hash)

V těchto bodech vidíte hodně obtížné, což je kvalitativní míra namísto kvantitativní. Nejlepší odpovědí je proveditelnost: existuje nejasná čára, když se něco stane proveditelným a tyto čáry se pohybují v průběhu času (protože výpočetní schopnosti rostou exponenciálně podle Mooreova zákona, jakmile váš mobilní telefon může nyní vyřešit obtížné problémy).

Obecně je dobré předpokládat, že obtížné znamená, že čas k dosažení určitého cíle je NP-kompletní. To znamená, že čas potřebný k přerušení hašování silně roste se zvyšováním délky hashe.

Dalším bodem je to, že kryptograficky bezpečný hashovací algoritmus může být užitečný v některých aplikacích, ale ne v jiných. Závisí to na modelu vašeho útočníka, povaze informací, které chcete chránit, a na věcech, jako jsou požadavky na výkon (obecně platí, že čím lepší jsou kryptografické vlastnosti hashe, tím horší je běhové chování).

Luis Casillas · Answer

Řekl bych, že dvě klíčové věci, kterým je třeba porozumět, jsou:

Termín „hash function“ je nejasný - nebo přesněji polysemous: má „rodinu“ významů, které jsou úzce spjaty, ale zřetelné. Pokud někdo označí funkci jako „hashovací funkci“, štítek vám jednoduše neřekne, jaké vlastnosti musí tato funkce mít. Musíte prozkoumat kontext, ve kterém se termín používá, a požadavky tohoto kontextu.
Termín „kryptografická hashovací funkce“ je mírně nesprávné pojmenování - vypadá to jako popis, ale má zahrnutou technickou definici, kterou samotný termín ve skutečnosti nepopisuje. Jednoduše řečeno, existují funkce jako autentizační kódy zpráv (MAC), které jsou často označeny jako hashovací funkce a nabízejí určitou formu kryptografické bezpečnosti, ale v konvenčních konvencích „kryptografické hashovací funkce“ nejsou definice.

Termín „kryptografická hashovací funkce“ se běžně používá k označení toho, co by mohlo být lépe označeno jako hašovací funkce odolné proti kolizi , které jsou veřejné funkce ("public" = nevyžadují tajný klíč), které musí mít tyto tři vlastnosti:

Druhý odpor předimage: Pro náhodnou hodnotu m1 Vybranou čestnou stranou je pro útočníka velmi nákladné najít jakoukoli hodnotu m2 ≠ m1 Takový, že hash(m1) = hash(m2).
Preimage odpor: Pro náhodnou hodnotu h vybranou čestnou stranou je pro útočníka velmi nákladné najít jakoukoli hodnotu m takové, že hash(m) = h.
Odolnost proti kolizi: Útočník je velmi nákladný najít jakoukoli dvojici hodnot m1 ≠ m2 Tak, aby hash(m1) = hash(m2).

Čtvrtá vlastnost, kterou starší kryptografické hashovací funkce triviálně selhávají, ale které novější jako SHA-3 a Blake2 jsou navrženy tak, aby dosáhly:

Náhodná lhostejnost společnosti Oracle: Toto je stručně vysvětleno, ale nemůžeme to vysvětlit stručně: ale je velmi nákladné, aby útočník našel jakékoli jiné - korelace mezi výstupy vstupů podle jejich výběru.

Náhodná vlastnost Oracle (pokud je správně formulována) znamená tři předchozí vlastnosti, stejně jako další, jako je absence účinných útoky s prodloužením délky . (Rozšíření délky jsou nejzřetelnějším důvodem, proč starší hashovací funkce, jako jsou SHA-256 a SHA-512, selhávají v náhodné vlastnosti Oracle.)