it-swarm-eu.dev

Proč jsou hashovací funkce jednosměrné? Pokud algoritmus znám, proč z něj nemůžu vypočítat vstup?

Proč nemůže být hash hesla zpětně zkonstruován?

Díval jsem se na tento věk už dávno a četl jsem o něm hodně, ale nemohu najít vysvětlení, proč to nelze udělat. Příklad nám usnadní pochopení mé otázky a věci ulehčíme, založíme na hašovacím algoritmu, který nepoužívá sůl ( LanMan ).

Řekněte, že moje heslo je „Heslo“. LanMan to hash provede a uloží do databáze. Praskající programy je mohou brutálně vynutit hašováním hesel, které poskytujete. Potom porovná vygenerovaný hash s hash v databázi. Pokud existuje shoda, zjistí heslo.

Proč, pokud cracker na heslo zná algoritmus, který změní heslo z prostého textu na hash, nemůže to jen obrátit proces výpočtu hesla z hashe?

Tato otázka byla IT bezpečnostní otázka týdne.
Přečtěte si 24. února 2012 položka blog pro více informací nebo zadejte svůj vlastní Otázka týdne.

231
Mucker

Dovolte mi vymyslet jednoduchý „algoritmus hashování hesel“, který vám ukáže, jak to funguje. Na rozdíl od ostatních příkladů v tomto vlákně je tento skutečně životaschopný, pokud můžete žít s několika bizarními omezeními hesla. Vaše heslo jsou dvě velká prvočísla, x a y. Například :

x = 48112959837082048697
y = 54673257461630679457

Můžete snadno napsat počítačový program pro výpočet xy v O ( [~ # ~] n [~ # ~ ] ^ 2) čas, kde [~ # ~] n [~ # ~] je počet číslic v x a y. (V podstatě to znamená, že to trvá čtyřikrát pokud jsou čísla dvakrát tak dlouhá. Existují rychlejší algoritmy, ale to je irelevantní.) Uložte xy do databáze hesel.

x*y = 2630492240413883318777134293253671517529

Na tuto odpověď by mohlo přijít dítě v páté třídě, které dostalo dostatek papíru na škrábání. Jak to ale zvrátíte? Existuje mnoho algoritmů, které lidé vymysleli pro faktoring velkých čísel, ale i ty nejlepší algoritmy jsou pomalé ve srovnání s tím, jak rychle se můžete vynásobit x pomocí y. A žádný z těchto algoritmů nemohl být proveden pátým srovnávačem, pokud čísla nebyla velmi malá (např. x = 3, y = 5).

To je klíčová vlastnost: výpočet je mnohem jednodušší jít dopředu než dozadu. Pro mnoho problémů musíte vymyslet zcela nový algoritmus pro obrácení výpočtu.

Toto nemá nic společného s injekčními nebo bijjektivními funkcemi. Když crackujete heslo, nezáleží často na tom, jestli dostanete stejné heslo nebo pokud dostanete jiné heslo se stejným hashem. Funkce hash je navržena tak, že je těžké ji zvrátit a získat jakoukoli odpověď, dokonce i jiné heslo se stejným hashem. V kryptologii: hashova funkce náchylná k útoku na obraz je naprosto bezcenné. (Algoritmus hashování hesel výše je injektivní, pokud máte pravidlo, že x < y. )

Co dělají experti na kryptografii? Někdy se snaží vymyslet nové algoritmy pro obrácení hashovací funkce (předobraz). Dělají přesně to, co říkáte: analyzují algoritmus a snaží se jej obrátit. Některé algoritmy byly již dříve obráceny, jiné ne.

Cvičení pro čtenáře: Předpokládejme, že databáze hesel obsahuje následující položku:

3521851118865011044136429217528930691441965435121409905222808922963363310303627

Jaké je heslo? (Tento počítač není ve skutečnosti pro počítač příliš obtížný.)

poznámka pod čarou: Vzhledem k malému počtu hesel, které si lidé v praxi volí, není dobré vypočítat heslo jen obtížně spočítat zpět, ale také časově náročné počítat vpřed, zpomalit slovní útoky. Jako další vrstva ochrany, randomizovaná sůl zabraňuje použití předem vypočtených útočných tabulek (jako jsou "Rainbow tabulky").

poznámka pod čarou 2: Jak víme, že je těžké zvrátit hašovací funkci? Bohužel ne. Prostě nevíme žádné snadné způsoby, jak zvrátit hašovací funkce. Vytváření hašovací funkce, u níž je prokazatelně obtížné zvrátit, je svatý grál designu hašovací funkce a dosud nebyl dosažen (snad se to nikdy nestane).

235
Dietrich Epp

Nyní je to dobrá otázka.

Nejprve musíme uvést přesnost: mnoho jednosměrných funkcí, zejména hašovací funkce běžně používaná v kryptografii, přijímá vstupy z prostoru, který je mnohem větší než prostor výstupních hodnot. Například SHA-256 je definován pro vstupy, které jsou řetězce až 18446744073709551615 bitů; existují 218446744073709551616-1 možné vstupy, ale protože výstupem je vždy sekvence 256 bitů, existuje pouze 2256 možné výstupy pro SHA-256. Některé odlišné vstupy nutně poskytují stejný výstup. Proto pro daný výstup SHA-256 není možné jednoznačně obnovit the vstup, který byl použit, ale možná by bylo možné vypočítat an vstup což dává danou výstupní hodnotu. Preimage odpor je o tom: obtížnost nalezení odpovídajícího vstupu pro výstup (bez ohledu na to, jak byl tento výstup získán na prvním místě).

Mluvíme tedy o funkci, kterou si každý může spočítat na jakémkoli vstupu (pomocí veřejně známého programu, bez tajné hodnoty - nemluvíme o šifrování).


Co říkají akademici

Není jasné, zda jednosměrné funkce mohou skutečně existovat. Právě teď máme mnoho funkcí, které nikdo neví, jak invertovat; ale to neznamená, že jsou nemožné invertovat, v matematickém smyslu. Všimněte si však, že není prokázáno, že jednosměrné funkce nemoho, proto zůstává naděje. Někteří lidé mají podezření, že zda jednosměrné funkce mohou existovat nebo ne, mohou být jedním z těchto nepříjemných matematických tvrzení, která nemohou být dokázána ani vyvrácena ( Gödelova věta dokazuje, že takové věci musí existovat). Ale o tom není ani důkaz.

Neexistuje tedy žádný důkaz, že jakákoli daná hashovací funkce je skutečně odolná předobrazům.

Existují některé funkce, které lze spojit se známými obtížnými problémy. Například pokud n je produkt dvou velkých prvočísel, pak funkce xx2 mod n je obtížné invertovat: schopnost vypočítat druhé odmocniny modulo non-prvočíslo n (obecně) je ekvivalentní tomu, že - faktor n a je známo, že tento problém je obtížný. Ne prokázáno být tvrdý, nevadí ti; pouze to, že se matematici pokusili efektivně zohlednit velká celá čísla (alespoň) za posledních 2500 let, a ačkoli bylo dosaženo určitého pokroku, žádný z těchto inteligentních lidí nenalezl pro tento algoritmus skutečně vrah. Světový rekord pro faktorizaci "RSA modulu" (součin dvou náhodně vybraných velkých prvočísel podobné délky) je 768-bitové celé číslo .

Byly navrženy některé hashovací funkce založené na takových „těžkých problémech“; viz například MASH-1 a MASH-2 (o problém RSA ) a ECOH ( s eliptickými křivkami). Existuje jen několik takových funkcí, protože:

  • Proměnit „těžký problém“ v bezpečnou hashovací funkci není snadné; existuje spousta složitých otázek. Například při extrahování druhých kořenů modulo non-prvočíslo n je obvykle těžké, existují hodnoty, pro které je těžba druhé odmocniny snadná.

  • Výkon takových hash funkcí bývá, řekněme, suboptimální. Jako by byl 100x pomalejší než běžně používaný SHA-1.

Více "standardní" způsob vytváření hašovací funkce je spojit kryptografy a nechat je nahlodat některé navržené návrhy; funkce, které přežívají kryptoanalytické pokusy po několik let, jsou pak považovány za „pravděpodobně robustní“. soutěž SHA- je takové úsilí; vítěz by měl být vyhlášen koncem tohoto roku. Na 51 uchazečích (těch, kteří uspěli ve správním kroku) bylo 14 uchováno pro „2. kolo“ a těchto 14 bylo poměrně pečlivě prozkoumáno mnoha kryptografy a žádný z nich nenašel nic, co by stálo za to říci o funkcích. Seznam byl snížen na 5 a bude dále redukován na 1 "brzy", ale ne z bezpečnostních důvodů (většina skutečných dat se týkala výkonu, nikoli odporu).


Proč je obtížné invertovat MD5

Protože nevíme, jak dokázat, že funkce je obtížné invertovat, nejlepší, co můžeme udělat, je vyzkoušet si konkrétní funkci, abychom získali „intuici“ toho, jak funkce dosahuje svého zdánlivého odporu.

Vyberu MD5 , což je dobře známo. Ano, MD5 je "zlomený" , ale to je pro kolize, ne preimages. Existuje je známý preimage útok což je, přinejmenším teoreticky, rychlejší než obecný způsob („obecný způsob“ je „štěstí“, tj. Zkouší vstupy, dokud není zápas zjištěno, za průměrnou cenu 2128 vyhodnocení, protože MD5 má 128bitový výstup; útok Sasaki-Aoki má cenu 2123,4, což je nižší, ale stále příliš vysoké na to, aby to bylo možné vyzkoušet, takže výsledek je stále teoretický). MD5 je však relativně jednoduchý a po dlouhou dobu odolává útokům, takže je to zajímavý příklad.

MD5 spočívá v řadě vyhodnocení "komprimační funkce" přes datové bloky. Vstupní zpráva je nejprve vycpaná, takže její délka se stává násobkem 512 bitů. Poté je rozdělen na 512bitové bloky. 128bitový provozní stav (držený ve čtyřech 32bitových proměnných nazvaný A , B , C a D ) se inicializuje na konvenční hodnotu a poté se zpracuje s funkce komprese. Funkce komprese přebírá provozní stav a jeden 512bitový blok zpráv a mísí je do nové hodnoty pro provozní stav. Po zpracování všech bloků zpráv je konečnou hodnotou běžícího stavu hashový výstup.

Zaměřme se tedy na kompresní funkci. Funguje to takto:

  • Vstupy: provozní stav (A B C D) a blok zpráv M . Blok zpráv je 512 bitů; rozdělili jsme ji na 16 32bitových slov M, M1, M2, ... M15.
  • Výstup: nová hodnota provozního stavu.
  • Zpracovává se:

    1. Uložte aktuální stav do některých proměnných: A → A ', B → B', C → C ' a D → D '
    2. Proveďte 64 kol, která vypadají takto:
      • Vypočítat T = B + ((A + fi(B, C, D) + Mk + Xi) <<< si). Toto zní takto: vypočítáme danou funkci fi (jednoduchá bitová funkce, která závisí na čísle kola i) přes B , [~ ~ # ~] c [~ # ~] a D . K tomu přidejte hodnotu A , jedna zpráva Word Mk a konstanta Xi (přidávání se provádí modulo 232). Otočte výsledek o několik bitů doleva (velikost posunu závisí také na kole). Nakonec přidejte B : výsledkem je T .
      • Otočte stavová slova: D → A, C → D, B → C, T → B.
    3. Přidejte uložené hodnoty stavu do aktuálních stavových proměnných: A + A '→ A, B + B' → B, C + C '→ C, D + D '→ D.

Důležité je, že existuje 64 kol, ale pouze 16 zpráv. To znamená, že každá zpráva Word zadá zpracování čtyřikrát . Píšu to tučně, protože je to ústřední bod; odolnost vůči předběžným snímkům vychází z této charakteristiky. Která zpráva Word se používá v každém kole, je popsána ve specifikaci MD5 (RFC 1321); specifikace také popisuje funkce fi, počet otáček se počítá si a 32bitové konstanty Xi.

Předpokládejme, že se pokoušíte "invertovat" MD5; začnete od výstupu a pomalu pracujete s kompresní funkcí. Nejprve musíte rozhodnout ​​výstup kola 64. Výstupem komprimační funkce je skutečně součet výstupu kola 64 a uloženého stavu (A 'B' C 'D'). Nemáte ani jeden, takže si musíte vybrat. Vaše naděje je, že budete moci najít hodnoty pro slova zpráv, která vám umožní získat pro zadání kola 1 některé hodnoty, které jsou v souladu s vaším libovolným rozhodnutím o A ' a jeho bratrech.

Podívejme se, jak to vypadá, když chodíte kompresní funkcí vzad. Máte výstup kola (proměnné A , B , C a D po kole) a chcete zkompilujte vstup tohoto kola. Již znáte předchozí hodnoty B , C a D , ale pro A a Mk máte spoustu možností: každá 32bitová hodnota je možná pro A a každá má odpovídající Mk. Nejprve jste z toho rádi; kdo by odhodlal takovou svobodu? Stačí si vybrat náhodný Mk, a tím získáte odpovídající A s několika operacemi (zkuste to!).

Ale poté, co jste obrátili tímto způsobem 16 kol (kola 49 až 64, protože pracujete vzad), svoboda zmizí. Vybrali jste hodnoty všech slov zprávy. Při pokusu o převrácení kola 48 byste chtěli přepočítat hodnotu A těsně před tímto kolem; podle specifikace MD5 zpráva Word M2 se používá v kole 48 a už jste vybrali hodnotu M2 (při převrácení kola 63). Takže existuje pouze jedna volba pro A . Tak co, řekl byste. Jedna volba je dostatečná pro pokračování v chůzi dozadu. Takže pokračujte.

Nyní jste na začátku funkce komprese. Nezapomeňte, že jste zpočátku svévolně vybrali hodnoty A 'B' C 'D': To vám umožnilo spočítat výstup z kola 64 a začít chodit dozadu. Nyní jste získali vstup do 1. kola, který by měl být totožný s A 'B' C 'D' ... a neshoduje se. To je zcela normální: zvolili jste A 'B' C 'D' libovolně a také jste zvolili slova zprávy Mk libovolně, takže lze očekávat, že to nebude fungovat většinu času. Takže se pokusíte opravit ​​výpočet tím, že retrospektivně změníte buď počáteční výběr A 'B' C 'D', nebo jednu nebo několik náhodných voleb pro - Mk. Ale každá modifikace jakéhokoli Mk předpokládá úpravy jinde, protože každý Mk se používá čtyřikrát. Chcete-li zrušit ty ostatní, potřebujete další úpravy atd. ...

V tom okamžiku začnete chápat problém invertování MD5: pokaždé, když se dotknete jediného kousku, vyvolá v algoritmu hroznou spoustu modifikací, které musíte zrušit dotykem dalších bitů, a existuje jen příliš mnoho interakcí . V podstatě žonglujete s 2128 koule současně, a to je příliš mnoho na to, abyste je všechny mohli sledovat.

Pokud byl každý blok zpráv dlouhý 2048 bitů, rozdělený do 64 slov a každá zpráva Word byla použita pouze jednou v MD5, můžete ji snadno převrátit. Proveďte výše uvedené: libovolný výběr A 'B' C 'D', libovolný výběr slov zprávy pro kola 64 až 5; a pro první čtyři kola vezmete v úvahu pouze hodnotu, kterou chcete získat pro zadání kola (hodnota, která odpovídá vaší libovolné volbě A ', B', - C ' nebo D') a vypracujte odpovídající zprávu Word. Snadné jako koláč. MD5 však nezpracovává data podle 2048bitových bloků, ale podle 512bitových bloků a každá zpráva Word se používá čtyřikrát.


Některé další zvraty

Struktura kompresní funkce MD5 je ve skutečnosti zobecněním Feistelova šifra . Na Feistelově šifře jsou data rozdělena do dvou polovin a pro každé kolo změníme jednu polovinu přidáním/xorací na střední hodnotu, která se vypočítá z druhé poloviny a z klíče; a pak vyměníme dvě poloviny. Rozšiřte toto schéma na rozdělení na čtyři části a získáte stejnou strukturu jako kola MD5 - s otočením o 90 °: MD5 vypadá jako šifrování současný stav pomocí bloku zpráv jako - klíč (a navíc je přidán výstup kola 64 s uloženým stavem, který odchyluje MD5 od otáčené šifry).

Takže možná můžeme sestavit hashovací funkce z blokových šifer? Opravdu můžeme: o tom je Whirlpool . Hašovací funkce postavená na otočené šifře bloku (klíčem je blok zprávy); bloková šifra Whirlpoolu je „W“, derivát Rijndaela, lépe známý jako AES . Ale W má větší bloky (512 bitů namísto 128 bitů) a posílený rozvrh klíčů.

Když provedete hašovací funkci mimo rotovanou blokovou šifru, pak útoky na předběžné obrázky na hašovací funkci jsou poněkud rovnocenné útokům na rekonstrukci klíče na blokové šifře; takže existuje určitá naděje, že pokud je bloková šifra bezpečná, je to také hashovací funkce. Znovu tam jsou zavalité detaily. Také pro takovou strukturu kolize na hašovací funkci jsou jako útoky související s klíčem na blokové šifře; útoky související s klíčovými klíči jsou obvykle považovány za nezávažné a často jsou ignorovány (například nebyly součástí hodnotících kritérií pro soutěž AES a Rijndael je v tomto ohledu pokládán trochu šupinatě, což je důvod, proč má W zcela nový klíč) plán).

Některé novější návrhy jsou postaveny na blokové šifře, která je ne otáčena, takže bezpečnost hašovací funkce může být odvozena přímo z bezpečnosti blokové šifry; viz například kandidát SHA-3 Skein , definovaný na blokové šifře zvané Threefish.

Naopak by se člověk mohl pokusit vyrobit blokovou šifru z hašovací funkce. Viz například SHACAL , což je SHA-1 „nastavený vzpřímeně“. A na druhou stranu, SHACAL má některé související klíčové slabosti, které jsou docela podobné známým slabinám SHA-1, pokud jde o kolize (nebyla vypočtena žádná skutečná kolize, ale máme metodu, která by měla být téměř milionkrát rychlejší než obecný algoritmus pro vyhledávání kolizí).

Proto, na rozdíl od toho, co jsem řekl v úvodu tohoto příspěvku, mluvili jsme šifrování po celou dob. Stále existuje mnoho toho, co je třeba objevovat a studovat o souvislostech mezi hashovacími funkcemi a symetrickým šifrováním.


TL; DR: není žádná TL; DR pro tuto zprávu. Přečtěte si to celé, nebo ztratil.

128
Thomas Pornin

Prvním krokem k odpovědi na tuto otázku je ukázka příkladů funkcí, jako je Nice z @ Dietrich, funkcí, které je mnohem obtížnější provozovat v jednom směru než inverzní, a odolaly mnoha pokusům najít průlom v rychlosti. Ale problém je složitý, takže se ho pokusím podrobit ještě více.

Spousta lidí se zdá, že padají do pasti (heh) myšlení, že hash funkce jsou vlastně nějak magické - že jsou skutečně absolutními „jednosměrnými funkcemi“, které matematicky nelze spustit zpět vůbec jen proto, že se jim říká hashe. Toto není zdravý způsob, jak o tom přemýšlet na fóru zabezpečení. V praxi je to často špatně. A teoreticky je to vždy špatně, vzhledem k základní matematické definici funkce jako mapování z domény na obrázek .

V zásadě lze všechny hashovat obráceně. Může to být chaotický a brutální (jako v hrubé síle), může to trvat neprakticky dlouhou dobu s dnešním hardwarem a může to dokonce trvat déle, ale matematicky je to prostě otázka času. Jak @mucker poznamenal, všechny informace jsou k nalezení původního hesla (nebo alespoň hesla, které funguje). Pokud na to zapomeneme, zapomínáme na to, že chytré heuristiky hrozí vybíráním pravděpodobných hesel, díky nimž se zprávy pravidelně objevují. Hašování je technický problém a hlavní výzvou je efektivita - jak dražší najít heslo pro hash. Jedním z hlavních výsledků tohoto druhu myšlení je důležitost pomalého hašování hesel

A věda a matematika hashování se jen pomalu zlepšují. Opravdu neexistují žádné důkazy o tom, že by hashe byly opravdu těžké. @ Dietrichova odpověď je pěkný způsob, jak ilustrovat, jak jsou ideální hashovací funkce možná. Jen se ale podívejme na skutečné odborníky popisující, jak nemáme důkazy o žádném z nejlepších kryptografických algoritmů: Jaký je matematický model za bezpečnostními požadavky symetrických šifrů a algoritmů výtisků?

Skutečnost, že LanMan byl citován v otázce, je ještě více důkazem, že se musíme vyhnout idealizaci hashe. LanMan je něco jiného než ideální hašovací funkce, snadno poražená kombinací trochu analýzy a trochu brutálního násilí. Další populární příklad hrozné hašovací funkce viz MySQL OLD_PASSWORD kryptoanalýza? .

Takže se vraťte z pasti - do ní nemusí být jednosměrná cesta. Uvědomte si, že hashe jsou reverzibilní, a udržujte toto důvěryhodné bezpečnostní myšlení aktivní, když hledáte nejlepší způsob, jak je zvrátit. To je často ten nejlepší způsob, jak najít ty, které je opravdu těžké obrátit. Nesnažím se vrhnout aspersions na nejlepší postupy tam, jako je bcrypt nebo PBKDF2 nebo scrypt. Je však zřejmé, že i ti dobrí programátoři to dokazují příliš často. takže buďte opatrní s tím, jak je používáte a nesnažte se vymýšlet své vlastní.

17
nealmcb

Protože takto fungují kryptografické hašovací funkce, jedná se o jednosměrné matematické funkce (od jednoduchého po hash). Algoritmy jsou vytvářeny a testovány speciálně, aby se tomu zabránilo, a také aby nedocházelo ke kolizím (2 různé prosté texty vytvářejí stejný hash).

Můžete si přečíst více na wikipedii , ale hlavním bodem článku je:

Ideální kryptografická hashovací funkce má čtyři hlavní nebo významné vlastnosti:

  • je snadné (ale ne nutně rychlé) vypočítat hodnotu hash pro každou danou zprávu
  • je nemožné vygenerovat zprávu, která má daný hash
  • je nemožné upravit zprávu beze změny hash
  • je nemožné najít dvě různé zprávy se stejným hashem

Většina útoků na hašovací funkce je založena na nalezení kolizí (takže 2 různé prosté texty budou odpovídat stejnému hašiši) nebo předběžně generují miliony hashů a porovnávají je, dokud nenajdete planetu, která ji vygenerovala.

Dlouhá historie je krátká: pokud je hashovací algoritmus reverzně upravitelný nebo pokud jej lze zaútočit, nejedná se o dobrý hashovací algoritmus.

U hesel má vyšetřování pomocí BCrypt tento příspěvek spoustu informací.

12
coredump

Představte si hašovací funkci, která pro hash používá jediný bit. Vaše hash tedy může být 0 nebo 1.

A řekněme, že hash funkce sčítá každý bajt dat a pokud byla data sudá, hash hodnota je 0. Pokud byla data lichá, hash je 1.

Vidíte, proč jste nemohli obnovit vaše data pomocí reverzního inženýrství, které má hašovací funkci?

Je to stejné pro skutečné algoritmy hash, pouze vzorce jsou výrazně lepší než funkce, kterou jsem právě popsal.

Vaše potíž může být v tom, že uvažujete o hašování, pokud jde o jejich použití pro hesla. Není zřejmé, proč nemůžete obnovit 8místné heslo ze 128bitového hashe. Tato hashovací funkce, kterou používáte pro hesla, však lze také použít pro výpočet hashe celého terabajtu dat a hash bude stále brát jen 128 bitů dat. Je zřejmé, že nemůžete zpětně analyzovat 128bitový hash a obnovit váš terabajt dat.

Za předpokladu, že byste měli každou možnou permutaci jediného terabajtu dat, by tedy existovalo obrovské množství různých dat, která generují stejný hash. Koneckonců, pokud máte více než 2 ^ 127 různých permutací dat, pravděpodobně narazíte na dvě různá data, která mají stejné hash.

8
user1068775

Existují algoritmy, které jsou neodmyslitelně nevratné; změní vstup A na výstup B tak, že i když znáte přesné kroky algoritmu, nemůžete obnovit A z B.

Velmi jednoduchý příklad: převeďte každý znak v hesle na jeho hodnotu ASCII hodnota a sečtěte všechny hodnoty. Neexistuje způsob, jak obnovit původní heslo z výsledku.

4
Massimo

Existuje jeden aspekt problému, který lidem v předchozích odpovědích chybí. To je mnohonásobná povaha hashových funkcí. Protože (většina) hašovacích funkcí je výstup s pevnou délkou (např. 256 bitů), existuje technicky nekonečně mnoho řetězců, které všechny hashují na stejnou hodnotu.

Pokud například vezmete všech 512 bitových řetězců (z nichž je 2 ^ 512). Existuje pouze 2 ^ 256 výstupů hašovací funkce. Pro každý výstup hashovací funkce tedy existuje zhruba 2 ^ 256 512 bitových řetězců, které hash této hodnotě. Říkám zhruba proto, že nevíme, jestli hashovací funkce je ve skutečnosti náhodná funkce, mohla by mít mírné zkreslení.

Tudíž, vzhledem k přehledu, existuje mnoho řetězců, které hashují stejnou hodnotu. Pokud tedy jako výstup uživatelského hesla definujete „obrácení hashovací funkce“, jak se vaše reverzní funkce vypořádá s potenciálně nekonečným počtem řetězců, které mají za následek daný výtah?

2
mikeazo

Ptáte se „proč je důležité, aby hashovací funkce byly jednosměrné?“ Je to bezpečnostní vlastnost.

V současné době se běžně používají dva druhy „hash“ (nebo „přehled zpráv“, jak se říká). Jedním z nich je prostý přehled zpráv, který můžete znát jako algoritmus kontrolního součtu, například CRC32. Algoritmus je navržen tak, aby jediná bitová změna ve vstupu poskytla jinou hodnotu digestu. Hlavním účelem je zajistit, aby zpráva nebyla poškozena náhodou. Kontrolní součty CRC32 jsou přítomny na každém paketu TCP/IP a chybná shoda má za následek opakovaný přenos k opravě chyby.

Přehledy zpráv se často používají v kryptografii jako součást „podepisování“ zprávy. Zprávu zašifruje odesílatel svým soukromým klíčem a veřejný klíč může kdokoli ověřit, zda byla šifrována pouze odesílatelem. Kryptografie veřejného klíče RSA však může šifrovat pouze zprávy menší než velikost klíče (256 bajtů), které jsou mnohem kratší než nejužitečnější zprávy. Algoritmy digest zprávy vytvářejí hodnoty menší než klíče RSA. Šifrováním výčtu namísto zprávy lze tedy použít signatury RSA v jakékoli velikosti zprávy.

Proti útočníkovi však není běžný přehled zpráv bezpečný. Zvažte velmi jednoduchý kontrolní součet, který pouze sčítá hodnoty znaků. Pokud jste podepsali takový kontrolní součet, mohl bych vyměnit jakoukoli jinou zprávu, která poskytne stejný kontrolní součet, a podpisy by se shodovaly a oklamaly oběť.

Dalším běžným využitím pro přehledy zpráv je ochrana heslem během ukládání. Pokud zašifrujete hesla před jejich uložením do systému, může je dešifrovat všechna správce systému, který zná klíč. (Možná jste si tento problém všimli nedávno, když byly některé webové stránky napadeny hackery.)

Abychom těmto problémům zabránili, je zapotřebí jiný druh hashe, který je „kryptograficky bezpečný“. Algoritmus zabezpečeného hash má dvě další vlastnosti, odolnost proti kolizi a nevratnost.

Odolnost proti kolizi znamená, že bych neměl být schopen najít zprávu, která produkuje stejný přehled. Tímto způsobem nemůžu zaměnit svou zlou zprávu za vaši dobrou zprávu.

Vlastnost nevratnosti znamená, že nemůžu změnit výtah zpět na prostý text, takže nemůžu dešifrovat původní zprávu, například heslo uživatele.

Vytvoření přehledu je velmi podobný problém jako šifrování, protože musíte data zašifrovat tak, aby neunikly žádné informace o původních datech. Je to ještě těžší, protože stejná matematika nemusí dávat žádné stopy o tom, jak úspěšně vytvořit kolizi.

1
John Deters

Myslím, že existuje mnoho důvodů, ale jeden je zřejmý: výtah produkovaný hašovací funkcí nemůže nikdy obsahovat nekonečné informace, protože výtah má konečné bity. Funkce hash však lze použít k hašování vstupů nekonečných informací. Vstup může být ve skutečnosti cokoli.

Těžko najít kolizi není odpověď. Skutečné potíže dokazují, že vaše původní data jsou ve skutečnosti jediným možným vstupem, který odpovídá určitému přehledu. Myslím, že byste nikdy neměli spočítat jeden vstup a tvrdit, že je to jediná odpověď na výtah.

0

Jiní vysvětlili, proč je dobré kryptografické hašovací funkce obtížně zvrátit - ale podle tento článek na Wikipedii je LanMan špatně navržen a lze jej poměrně snadno převrátit:

Ačkoli je založen na DES, dobře promyšlené blokové šifře, LM hash není skutečná jednosměrná funkce, protože heslo lze určit z hash kvůli několika slabinám v jeho implementaci ... Připojením útoku brutální síly na každé polovině samostatně mohou moderní stolní počítače prasknout alfanumerické hashování LM za pár hodin ... V roce 2003 byla zveřejněna implementace techniky tabulky Rainbow Ophcrack. Konkrétně se zaměřuje na slabiny šifrování LM a zahrnuje předem vypočtená data dostatečná pro rozbití prakticky všech alfanumerických hashů LM během několika sekund.

0
James