it-swarm-eu.dev

Proč se AES nepoužívá pro bezpečné hašování namísto SHA-x?

Pokud vím, AES je považována za extrémně bezpečnou. (Někde jsem četl, že by to v příštích 20 letech rozhodně nebylo přerušeno, ale stále si nejsem jistý, zda byl autor vážný.)

DES není stále tak špatný pro starého cyphera a 3DES se stále používá (možná ne tolik, ale alespoň vidím 3DES asi v: config ve Firefoxu).

Vypadá to, že (dobré) blokové cyphery jsou důvěryhodnou komunitou krypto.

OTOH je objeveno mnoho problémů s kryptografickými hashovacími funkcemi.

Z pohledu nešifrovaného specialisty: hashovací funkce a symetrické cyphery jsou opravdu to samé: „náhodná“ funkce (s různými vstupy a výstupy).

Proč tedy pro hašování nepoužívat jen AES? Zdá se, že je zřejmé, že je třeba udělat silnou bezpečnost AES při hašování. Mohou jako bonus pomoci hardwarové implementace AES?

Existuje jednoduché vysvětlení skutečného rozdílu mezi hashovými funkcemi a symetrickými cypry?

46
curiousguy

Bloková šifra má klíč; tajemství klíče je to, na čem staví zabezpečení šifry. Na druhé straně hashovací funkce nemá vůbec žádný klíč a neexistují žádná „tajná data“, na kterých má být zabudováno zabezpečení hašovací funkce.

Bloková šifra je reverzibilní: Pokud znáte klíč, můžete dešifrovat, co bylo šifrováno. Technicky je pro daný klíč bloková šifra permutace prostoru možných hodnot bloku. Hašovací funkce jsou zamýšleny jako nevratné a v žádném případě to nejsou permutace.

Bloková šifra pracuje na blocích pevné velikosti (128bitové bloky pro AES), jak pro vstup, tak pro výstup. Hašovací funkce má pevný výstup, ale měla by přijímat libovolně velké vstupy.

Blokové šifry a hašovací funkce jsou tedy opravdu jiná zvířata; spíše než se snažit je rozlišit, je snazší pochopit, co mají společného: jmenovitě to, že lidé, kteří vědí, jak navrhnout blokovou šifru, jsou také přiměřeně dobří při navrhování hašovacích funkcí, protože matematické nástroje analýzy jsou podobné (docela hodně lineární algebry a booleovských funkcí, opravdu).

Pojďme pro více formálních definic:

Bloková šifra je rodina permutací vybraných klíčem. Uvažujeme prostor B z n - bitové bloky pro nějakou pevnou hodnotu n; velikost B je pak 2n. Klíče jsou hodnoty z mezery K , obvykle další mezera sekvencí m bitů (m je nemusí se nutně rovnat n). Klávesa k vybere permutaci mezi 2n! možné permutace B .

Bloková šifra je považována za bezpečnou, pokud je výpočetně nerozeznatelná od permutace, která byla vybrána jednotně a náhodně mezi 2n! možné permutace. Pro modelování této situace si představte situaci, kdy je útočníkovi umožněn přístup ke dvěma černým rámečkům, jeden implementující blokovou šifru pomocí klíče, který útočník nezná, a druhý je skutečně náhodná permutace. Cílem útočníka je říct, která je která. Může mít každý box zašifrovat nebo dešifrovat jakákoli data, která si přeje. Při možném útoku je vyzkoušet všechny možné klíče (existují 2m takové klíče) je nalezen pouze jeden, který dává stejné hodnoty jako jedno z polí; to má průměrné náklady 2m-1 vyvolání šifry. Bloková šifra secure je taková, že tento obecný útok je nejlepším možným útokem.

AES je definován přes 128-bitové bloky (n = 128) a 128-, 192- a 256-bitové klíče.

A hašovací funkce je jednoduchá, plně definovaná, vypočítatelná funkce, která bere jako vstupní bitové sekvence libovolnou délku a vydává hodnoty pevné délky r (např. r = 256 bitů pro SHA-256). Neexistuje žádný klíč, žádná rodina funkcí, pouze jedinečná funkce, kterou může kdokoli vypočítat.

Hašovací funkce h se považuje za bezpečnou, pokud:

  • Je výpočtově nemožné najít preimages: vzhledem k r - bitová hodnota x, není možné najít m tak, že h (m) = x.
  • Je výpočtově nemožné najít druhé předobrazy: vzhledem k m není možné najít m ' odlišný od m, takže h (m) = h (m ').
  • Je výpočtově nemožné najít srážky: není možné najít m a m ', navzájem odlišné, takže h (m) = h (m ').

Existují obecné útoky, které mohou najít předběžné snímky, druhé předběžné snímky nebo srážky, s náklady, respektive 2r, 2r a 2r/2. Skutečné bezpečnosti tedy lze dosáhnout pouze tehdy, je-li r dostatečně velké, aby 2r/2 je ohromně obrovské náklady. V praxi to znamená, že r = 128 (128bitová hashovací funkce, jako je MD5) je nestačí.

Neformálním způsobem je dobré, pokud hashovací funkce „vypadá“, že byla vybrána náhodně a jednotně mezi možnými funkcemi, které akceptují stejné vstupy. Ale je to špatně definovaná vlastnost, protože mluvíme o jedinečné funkci (pravděpodobnosti jsou vždy implicitně o průměrech a opakovaných zkušenostech; nemůžete mít opravdu pravděpodobnosti s jedinou funkcí). Také být náhodná funkce není úplně stejná jako odolnost vůči kolizím a předobrazům; toto je debata o Random Oracle Model .


Přesto je možné sestavit hašovací funkci z blokové šifry. To je konstrukce Merkle-Damgård . To znamená použití vstupní zprávy jako klíč blokové šifry; bloková šifra se tedy vůbec nepoužívá tak, jak měla. U společnosti AES je to zklamáním:

  • Výsledkem je hašovací funkce se 128bitovým výstupem, což je příliš malé pro zabezpečení proti technologii dostupné v roce 2011.
  • Zabezpečení hašovací funkce se pak spoléhá na nepřítomnost útoků souvisejících klíčů na blokové šifře. Útoky s příbuznými klíči nemají na blokové šifře při použití pro šifrování žádný praktický význam; AES tedy nebyl navržen tak, aby odolával těmto útokům, a ve skutečnosti AES a několik slabých stránek v tomto ohledu - nejde o obavy z šifrování, ale o velké obavy, pokud AES se používá v konstrukci Merkle-Damgård.
  • Výkon nebude dobrý.

Hašovací funkce Whirlpool je design, který vychází z blokové šifry inspirované od AES - nikoli skutečné. Tato bloková šifra má mnohem vylepšený (a těžší) klíčový plán, který odolává útokům souvisejících klíčů a činí jej použitelným jako jádro hašovací funkce. Tato bloková šifra funguje také na 512bitových blocích, nikoli na 128bitových blocích. Whirlpool je považován za bezpečný. Whirlpool je znám jako velmi pomalý, takže ho nikdo nepoužívá.

Některé novější návrhy hashových funkcí se pokusily znovu použít části AES - abych byl přesný, použít interní operaci, která dobře mapuje AES-NI instrukce, které byly nedávno Funkce procesorů Intel a AMD. Viz například ECHO a SHAvite- ; tyto dvě funkce obě dostaly docela trochu expozice v rámci SHA-3 konkurence a jsou považovány za "přiměřeně bezpečné". Na procesorech Intel a AMD je velmi rychlý vývoj. Na jiných slabších architekturách, pokud má výkon hashových funkcí šanci skutečně na tom záležet, jsou tyto funkce poměrně pomalé.

Existují i ​​jiné konstrukce, které mohou dělat hashovací funkci z blokové šifry, např. ten použitý v Skein ; ale také mají tendenci vyžadovat větší bloky, než co je definováno AES.

Shrnutí: nejenže jsou blokové šifry a hashovací funkce zcela odlišné; ale myšlenka vybudování hašovací funkce z AES se ukazuje jako sporná platnost. Není to snadné a omezená velikost bloku AES je hlavní překážkou.

70
Thomas Pornin

Základní odpovědí je, že se jedná o různé typy algoritmů. AES je algoritmus symetrického klíče. Nemůžete jej použít ve stejné roli jako RSA (algoritmus veřejného klíče) nebo SHA-256 (hashovací algoritmus). Jsou to různé systémy navržené s velmi odlišnými vlastnostmi a slabostmi.

Přesto jsem se zastavil, ačkoli vážně, o tomto nápadu, abych mu to vysvětlil kromě toho, že jsem řekl: „Je to tak.“ Koneckonců, hash v univerzálním smyslu je opakovatelná reprezentace dat v pevné nebo zmenšené velikosti. AES to může zajistit prostřednictvím režimu CBC. Přesto existuje více vlastností pro bezpečné hash než jednoduché snížení.

Algoritmus bezpečného hašování je jednosměrný systém. AES šifruje a dešifruje stejným způsobem (symetrická šifra) a pro každý blok můžete provést mapování 1-1, co se stane s daným klíčem. Pokud nejsou data zřetězena a tedy ztracena, můžete jednoduše dešifrovat „hash“ AES do zdrojových dat.

Jeden nemůže rozumně zvrátit proces SHA), než jen vyzkoušet různá vstupní data. Z důvodů, proč nemůžete použít SHA-x k zašifrování něčeho, nemůžete použít AES k hash něco.

11
Jeff Ferland

Existuje jednoduché vysvětlení skutečného rozdílu mezi hashovými funkcemi a symetrickými cypry?

  • Šifra je reverzibilní, hashova funkce není
  • Délka výstupu šifry závisí na délce vstupu; hash funkce produkuje výstup stejné délky bez ohledu na vstup
  • Jediná bitová změna kdekoli ve kryptografické hašovací funkci vytváří kaskádovou (dramatickou) změnu hašovacího výstupu. Toto pravidlo zpravidla neplatí pro šifry.
  • Šifra vyžaduje klíč, hash ne

Konstrukce a účel těchto dvou jsou zásadně odlišné a nejsou vzájemně zaměnitelné.

9
tylerl

V podstatě můžete libovolnou blokovou šifru přeměnit na hašovací funkci pomocí konstrukce Merkle-Damgard a v podstatě můžete libovolnou hašovací funkci proměnit na blokovou šifru pomocí sítí Feistel, pokud definujete Feistelovu funkci F následujícím způsobem.

F(half_block, round_key) = hash(concatenate(half_block, round_key))

Ale je to docela neefektivní (výpočet trvá dlouho), protože výpočet F je již drahý (iterační algoritmus používá např. 80 interních "kol" v případě SHA-512) a pro strukturu Feistel je samotný F iterován několikrát. Řekněme, že máte 20-stupňovou Feistel síť s 80-ti kulatými funkcemi F, provedete 1600 SHA-2 "kol" na blok. To také vede k poměrně velkým velikostem bloků (dvojnásobek velikosti výstupu hashovací funkce), např. G. 1024-bitová bloková šifra, pokud byste měli používat SHA-512 jako hashovací funkci.

Ale prakticky to není nutně „nejisté“. Je to jen to, že snadno dostupné „blokové šifry“ (spíše pseudonáhodné permutace - nikoli permutace jako v permutaci bitů/bajtů, ale permutace ve smyslu bijektivního mapování mezi „všemi možnými vstupními bloky“ a „všemi možnými výstupními bloky“) jsou mnohem více. efektivní, široce používané a proto důkladněji analyzované vlastnosti dobrých pseudonáhodných permutací. Pokud máte výpočtovou sílu na plýtvání, použijte SHA-512 v Feistel síti jako blokovou šifru. Šance jsou přinejmenším to nebude méně bezpečné než AES (za předpokladu, že přidáte dobrý plán klíčů pro odvození "kulatých klíčů"), ale zpracování zpracování bloku bude trvat šarže CPU cyklů.

3
no.human.being

M. Abel má pravdu. Dalším příkladem AES používaným jako hash je AES-CBC nebo AES-PCBC.

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Propagating_Cipher_Block_Chaining_.28PCBC.29

Pokud je CBC nebo PCBC nebo dokonce CFB spuštěno v „souboru“ s chybou a bez chyby, bude konečný blok jiný.

Je to neefektivní, ale lze to udělat. Logika zní: „Pokud máte jen kladivo, všechno vypadá jako hřebík.“ Totéž platí pro AES. Mohou existovat lepší způsoby hašování, ale pokud máte pouze AES. . .

0
aesuser