Jak funguje hashování?

Rychle, faktor 1081.

Nebo, chcete-li, odpovězte na tuto otázku: co je 23krát 47?

Který z nich je jednodušší? provést multiplikaci (stačí postupovat podle pravidel mechanicky), než obnovit operandy dané pouze produktu. Násobení. (To je mimochodem základ některých kryptografických algoritmů, jako je RSA .)

Kryptografické hashovací funkce mají různé matematické základy, ale mají stejnou vlastnost: jsou snadno vypočítatelné do budoucna (vypočítat H (x) vzhledem k x), ale prakticky nemožné vypočítat zpětné (vzhledem k y, vypočítat x tak, že H (x) = y). Ve skutečnosti je jedním ze znaků dobrého kryptografického hashu Funkce spočívá v tom, že neexistuje lepší způsob, jak najít x, než je všechny vyzkoušet a vypočítat H (x), dokud nenajdete shodu.

Další důležitou vlastností hash funkcí je, že dva různé vstupy mají různé hashe. pokud H (x ₁ ) = H (x ₂ ), můžeme dojít k závěru, že x ₁ = x ₂ Matematicky to není možné – pokud jsou vstupy delší než délka hash, musí dojít ke kolizím.Ale s dobrou kryptografickou hashovací funkcí neexistuje žádný známý způsob, jak najít kolizi se všemi výpočetními zdroji na světě.

Pokud se chcete dozvědět více o kryptografický hash , přečtěte si tuto odpověď Thomase Pornina . Pokračuj, já „počkám.

Všimněte si, že hashovací funkce není šifrovací funkce. Šifrování znamená, že můžete dešifrovat (pokud znáte klíč). S hashem neexistuje žádné magické číslo které vám umožní vrátit se zpět.

Mezi hlavní doporučené kryptografické hashovací funkce patří SHA-1 a SHA-2 rodina (která se dodává v několika výstupních velikostech, hlavně SHA-256 a SHA-512). MD5 je starší, nyní zastaralý, protože má známé kolize. Nakonec neexistuje žádný matematický důkaz, že jsou skutečně dobrými kryptografickými hashovacími funkcemi, jen rozšířená víra, protože mnoho profesionálních kryptografů strávilo roky svého života snahou a neúspěchem je rozbít.

Dobře, to “ Jedna část příběhu. hash hesla není přímo kryptografická hashovací funkce. Funkce hash hesla (PHF) bere dva vstupy: heslo a sůl. sůl je náhodně vygenerována, když si uživatel vybere své heslo, a je uloženo společně s hashovaným heslem PHF (heslo, sůl). (Důležité je, že dva různé účty mají vždy různé soli a náhodně generování dostatečně velké soli je dobrý způsob, jak tuto vlastnost mít s naprostou pravděpodobností.) Když se uživatel přihlásí znovu ověřovací systém načte sůl z databáze hesel, vypočítá PHF (heslo, sůl) a ověří, že výsledkem je to, co je uloženo v databázi.

Jde o to, že pokud někdo chce prolomit heslo, musí znát hash, než mohou začít , a musí zaútočit na každý účet zvlášť. Sůl znemožňuje předem provést hodně trhlin, např. vygenerováním duhové tabulky .

To odpovídá (2) a (3) – legitimní ověřovatel i útočník to zjistí ve stejném způsob, zda je heslo (zadané uživatelem nebo uhádnuté útočníkem) správné. Poslední bod příběhu: dobrá funkce hash hesla má další vlastnost, musí být pomalá. Legitimní server jej musí vypočítat pouze jednou za pokus o přihlášení, zatímco útočník to musí vypočítat jednou za odhad, takže pomalost útočníka více bolí (což je nutné, protože útočník má obvykle více specializovaného hardwaru).

Pokud někdy potřebujete hashovat hesla, nevymýšlejte vlastní metodu . Použijte jedno ze standardních metod : scrypt , bcrypt nebo PBKDF2 .  

Komentáře

• Sakra I přijďte na bezpečnostní stránky od všech ostatních a jedna věc, která je velmi jasná, je, že vy jste dali do šíleného množství práce s odpovědí. Nejen správně, ale velmi důkladně. Přál bych si vybrat dvě odpovědi, ale vaše byla mnohem spíš jako to, co Hledal jsem.
• @Griffin – Můžete však hlasovat pro oba. Nebo opravdu – když ‚ je více než t dvě odpovědi – hlasujte pro vše, co považujete za užitečné, i když můžete přijmout pouze jednu. Mnoho otázek zde má více než jednu dobrou odpověď a někdy ‚ se dokonce doporučuje přečíst si většinu odpovědí, abyste lépe porozuměli danému tématu. Ano, někdy i ti, kteří hlasovali proti. Svým hlasováním (v obou případech) také pomáháte budoucím čtenářům rozhodovat o platnosti odpovědí, zejména těm čtenářům, kteří se o určitém tématu stále učí. 😉
• Hlasoval jsem pro oba! Byly nesmírně užitečné.
• +1: Všechny odpovědi jsou dobré, ale tato je přibližně tak blízká dokonalé odpovědi, jako I ‚ kdy jsem viděl na Stack Exchange. Bylo by to +10, kdybych mohl.
• @IlmariKaronen To je důvod, proč sem ‚ chodím rád.

Kryptografické hashové funkce jsou matematické objekty, které lze popsat jako „velké míchání a kódování“ některých bitů „. Berou jako vstup posloupnost bitů (možná velmi dlouhou) a nabízejí výstup pevné velikosti. Zhruba řečeno, jsou tak zamotaní, že i když o nich není nic tajného (to je jen deterministický kód), nikdo nemůže přijít na to, jak je „invertovat“ (najít odpovídající vstup pro daný výstup), kromě základní metody zvané „luck“: zkuste náhodné vstupy, dokud nenajdete shodu.

Jak se může vědecky stát, že hašovací funkce vůbec mohou existovat, je dobrá otázka .

Hašování není šifrování . Neexistuje žádné tajemství, žádný klíč při hašování.

Hašovací funkce mají mnoho využití; jedním z nich je „uložení hesla“. Hašovací funkce vypadá jako dobrá věc pro ukládání hesel. Nechceme hesla ukládat přímo (jinak by mu příležitostné nahlédnutí do našich databází útočníkem poskytlo příliš mnoho informací; diskusi naleznete v tomto příspěvku na blogu ) ; chceme uložit tokeny pro ověření hesla : něco, co umožňuje ověření hesla (které uživatel předloží), ale samotné heslo neodhalí. Myšlenka tedy zní: Pojďme uložit hash hesla. Když má být heslo ověřeno, jednoduše spočítáme jeho hash a uvidíme, jestli odpovídá uložené hodnotě. Hádání hesla pouze z hash hodnoty je těžké, protože hashovací funkce je odolná proti „inverzi“ (viz výše).

Jelikož hesla jsou speciální druh dat (to jsou data, která si lidé mohou pamatovat), pro správnou bezpečnost potřebujeme „posílené“ hashovací funkce:

• Chceme velmi pomalou hashovací funkci.
• Nechceme jednu hashovací funkci, ale mnoho odlišných hash funkcí, takže každé heslo bude hashováno s vlastní hash funkcí; jde o odrazení paralelních útoků. Tento proces přeměny jedné hashovací funkce na mnoho variant se nazývá solení .

Viz tuto odpověď pro důkladné zacházení s tématem hašování hesel.

Komentáře

• Omlouvám se, ale zatímco vaše odpověď byla mimořádně důkladná a dobře sestavená, zjistil jsem druhá odpověď se více podobá tomu, co jsem hledal.

Hašování je funkce některých bitový řetězec (obvykle proměnná délka) na jiný bitový řetězec (obvykle menší a pevné délky).

Hashing se používá v databázích pro načítání dat a v datových strukturách v paměti nazývaných hash tabulky. Umožňuje nám redukovat libovolná data, jako je řetězec znaků nebo komplikovaný objekt s mnoha poli, na binární číslo, které pak lze použít přímo jako index do řídkého pole pro načtení přidružených dat (s některými podrobnostmi pro zpracování hash srážky).

Hašovací funkce použité výše uvedeným způsobem jsou „bratranci“ kryptografických hashovacích funkcí. Jsou navrženy podle různých požadavků. Musí být rychle vypočítatelné a musí docházet k dobré distribuci.

V zabezpečených výpočtech se kryptografické hodnoty hash používají k trávení dat do některých reprezentativních malých bitstringů. Kryptografické funkce mají různé požadavky. Jsou navrženy tak, aby bylo možné je couvat obtížně (jako funkce „padacích dveří“ nebo „jednosměrné“). Nejen to, ale důležitým požadavkem je, že musí být obtížné najít pro danou hodnotu prostého textu a hodnoty hash další prostý text, který produkuje stejnou hodnotu hash.

Hashing lze použít nejen pro hesla, ale jako kontrolní součet pro ověření integrity dat a jako součást implementace digitálních podpisů. Chcete-li digitálně podepsat velký dokument, musíme dokument jednoduše hašovat, aby vytvořil „digest“ (název použitý pro výstup hashovací funkce, když je hašováno něco velmi dlouhého). Pak právě tento výtah prochází kryptosystémem veřejného klíče a vytvoří podpis. Vidíte tam slabost: co když se útočníkovi podaří vytvořit dokument, který má stejný výtah? Pak to vypadá, že původní podpis vytvořený na originálním dokumentu je ve skutečnosti podpisem padělaného dokumentu: padělek na přesazení podpisu byl skutečně spáchán.

Hašování hesel umožňuje systémům neukládat prostou textovou verzi heslo, ale umožňuje jim ověřit, zda uživatel, který se pokouší získat vstup, zná toto heslo. Nejen, že hash umožňuje systémům neukládat hesla v prostém textu (což by muselo být velmi pečlivě střeženo), ale také umožňuje možnost, že i když jsou hashe veřejně zpřístupněny, hesla jsou stále zabezpečená (podobně jako kryptoměna veřejného klíče systémy jsou schopné odhalit veřejné klíče). I když jsou hashe v praxi chráněny před veřejným přístupem: například /etc/shadow soubory v systémech podobných systému Unix, které doplňují světově čitelné /etc/passwd soubory .

Hašovací funkce není nic jiného než náhodná. Randomizace se však používá k zmaření útočníků, kteří vytvářejí velké slovníky hesel a hashů, které jim umožňují vyhledávat hash kód a získat odpovídající heslo.

Abychom bezpečněji hashovali heslo, můžeme jednoduše přidat některé náhodné bity se tomu říká „sůl“. Různé soli přidané ke stejnému heslu samozřejmě vedou k různým hashům (doufejme, že s malými nebo žádnými kolizemi).

Pokud je náhodná sůl, řekněme, 32 bitů široká, znamená to, že teoreticky může jedno heslo hashovat více než čtyřmi miliardami různými způsoby, takže je velmi nepraktické mít předpočítaný slovník všech možných hashů velkého počtu hesel.

Když je uživatel ověřován, samozřejmě o této soli nic neví. To je v pořádku, protože sůl je uložena společně s hodnotou hash v profilu uživatele (často v kombinaci s hodnotou hash do jediného kompaktního bitstringu). Když je ověřováno zadání hesla uživatele, sůl se přidá k jakémukoli heslu vstoupila, aby se hašování provedlo se správnou solí. Pokud je heslo správné, bude hash odpovídat, protože použitá sůl je také správná, protože byla stažena z profilu uživatele.

Takže takhle je náhoda začleněna do hashování hesla, zatímco stále umožňuje jeho fungování.

Co dělá hashe těžko prolomitelné, je to, že jsou vytvořeny z funkcí „padacích dveří“ nebo „jednosměrných“. V matematice existuje mnoho příkladů takových věcí. Například , jednoduchým sčítáním jsou padací dveře. Pokud k vytvoření součtu přidáme celá celá čísla, je nemožné obnovit původní čísla, protože budeme znát pouze součet.

Hesla hesel nejsou zašifrovaná hesla. Pokud má útočník hash a sůl hesla a náhodou heslo uhádne, pak to může snadno potvrdit, přesně tak, jak to dělá software pro ověřování přihlášení: spustí heslo plus sůl prostřednictvím funkce hash a uvidí, že správný objevuje se hash.

Komentáře

• Vynikající psaní a opravdu snadné Rozumět odpovědi, která je ve skutečnosti správná, přesto řeší všechny body a zachovává k ní přirozený tok, který ji činí mnohem komplexnější. To ‚ není snadný výkon, moc vám děkuji za odpověď!
• velmi informativní. Zahrnuli jste všechny aspekty.

Jedním z klíčů k hašování je, že zahodí informace. Hašování nemůžete „obrátit, protože potřebné znalosti jsou pryč. Zde je několik příkladů funkčních (ale docela bezcenných) hashovacích funkcí. Pokud mi dáte heslo, mohu udělat něco jako jedno z následujících:

• Spočítejte počet samohlásek
• Vezměte kód ASCII pro každé písmeno a všechny XOR dohromady
• Vezměte kontrolní součet CRC32 binární reprezentace hesla (toto je ve skutečnosti skutečný hash, jen ne kryptografický)

V každém z těchto případů nemohu tento proces zvrátit. Místo toho musím proces znovu spustit, když mi později sdělíš heslo, abych zjistil, zda se shoduje výpočet, který jsem spustil.

Pro příklad: Pokud mi zpočátku dáte heslo „opice“, mohl bych uložit číslo 3 (3 samohlásky). Pak, později, když se pokusím ověřit heslo „drak“, znovu spustím stejnou kontrolu a vymyslím 2, které neodpovídá 3. Takže vím, že jste mi dali špatné heslo. Pokud mi ale dáte heslo „melissa“, nesprávně bych předpokládal, že jste zadali správné heslo. Toto je hash kolize .

Sada pravidel, která použijete, abyste přišli s číslem, které představuje dané heslo je vaše hash funkce . Tyto funkce jsou považovány za „jednosměrné“, protože byste je neměli mít možnost zvrátit. Vysoce kvalitní hash funkce jsou navrženy tak, aby omezovaly počet možných kolizí, takže si nemusíte dělat starosti s tímto problémem. O krok dále jsou kryptografické hashovací funkce navrženy tak, aby bylo obtížné přijít s řetězcem, který by mohl odpovídat danému výstupu ( a možná záměrně vytvářet kolize). Jsou také navrženy tak, aby omezovaly množství informací, které můžete shromáždit o daném vstupu pouze z hash výstupu.

Takže jediným způsobem, jak zjistit, jaké heslo odpovídá danému kryptografickému hash, je vyzkoušet všechny možnosti, dokud nenarazíte na ten, který funguje. Další protiopatření (sůl, BPKDF2 atd.) Tento proces hádání ještě ztěžují tím, že způsobí, že osoba hádající heslo bude při každém pokusu skákat přes další obruče.

Všimněte si, že jsem úplně přečetl, jak to dělá kryptografická hash funkce je obtížné přijít s fungujícím heslem (i když to není původní). Tomu se říká „ preimage útok „. V triviálním příkladu výše je příkladem takového útoku vymýšlení„ melissa „jako hesla kandidáta obsahujícího 3 samohlásky.

Kryptografické hashovací funkce to obvykle provádějí spuštěním vstupu, i když jich je několik.“ kola daného procesu, kde se výstup každého kola stane součástí vstupu do dalšího.Chcete-li zjistit vstup prvního kola, musíte zjistit vstup druhého kola, což zase vyžaduje zjistit vstup třetího kola atd., Což znamená, že každý odhad každé komponenty musí být zkontrolováno pomocí dlouhé a složité sady výpočtů. Thomas Pornin má docela vyčerpávající vysvětlení toho, jak tento odpor funguje; docela užitečné čtení, pokud chcete opravdu pochopte to.

1. Určete konstantní hodnotu z splňující tuto rovnici: xy ^ 7 + yz ^ 5 + x ^ 3z = 0. Potřebujete pomoc? OK, x = 32. Stále to nemůžete vyřešit? Pak byste na prvním místě neměli znát odpověď.

   Hodnota y, která ji sníží na jedinou proměnnou rovnici, takže řešení pro tuto jedinou proměnnou bude triviální jakémukoli žákovi 6. ročníku (možná Potřebuji kalkulačku), je tajemství, které jsem sdílel pouze s lidmi, kterým důvěřuji. Bez něj by z mohlo být cokoli; jeho hodnota závisí na y, a proto jej nelze uspokojivě vyřešit bez stálého známého y. Pokud ne Neznám vaši hodnotu, je to proto, že jsem vám nedůvěřoval natolik, abych vám ji mohl dát soukromě.

   Toto je základní princip kryptografie; matematický vzorec nebo jiný deterministický proces je dobrý -documented a jedna nebo více z možných proměnných vzorce je také povoleno být veřejně známých, což umožňuje oběma stranám dohodnout se na způsobu, jak nastavit jejich šifry, aby každá mohla dešifrovat to, co druhá šifruje. Nicméně dvě proměnné zůstaňte v tajnosti; pokud jedno znáte, můžete objevit druhé. Ten, který byste měli vědět, je klíč, a ten, který vy s klíčem je zpráva.

   U hodnoty hash je to trochu jiné. Hash nevyžaduje, aby bylo jedno tajemství uchováno, aby bylo možné uchovat další. Místo toho hash pracuje na základě nevratné matematické transformace; pro jakoukoli H (x) = y neexistuje žádná známá H ^-1 (y) = x až na to, že zkusíme H (x) pro všechna možná x, dokud nedostaneme y. Obvykle je to proto, že několik průběžných výsledků rovnice je nejednoznačných; například výpočet druhé odmocniny kladného čísla technicky vyprodukuje obojí pozitivní a negativní výsledek, protože k vytvoření výsledku lze libovolně znásobit libovolné číslo. Inverzní hodnota modulu je podobně nejednoznačná; číslo 1, které vyprodukuje x mod 3, by mohlo vyprodukovat libovolné x = 3k + 1. Tyto typy „jednosměrných“ transformací jsou kombinovány takovým způsobem, že pokus o výpočet inverzní hashovací funkce generuje nekonečné možnosti; nejjednodušší (nejjednodušší) způsob, jak je vyřešit, je proto jednoduše vyzkoušet všechny možné vstupy, dokud se neshoduje jeden výstup. stále trvá dlouho.

2. Haše nejsou náhodné. Jak jsem již dříve uvedl, hodnoty hash jsou výsledkem nevratné matematické operace. Tato operace musí být stále deterministická; s konstantním vstupem je výstup konstantní bez ohledu na to, kolikrát operaci provedete. Neexistuje žádná náhodná součást.

   Možná jste byli zmateni v pojmu, co simuluje hash, což je náhodný věštec . Představte si černou skříňku, ve které je malý muž s fotografickou pamětí a mystickou metodou generování dokonale náhodných čísel. Napíšete něco na kousek papíru a zasunete to otvorem, kde to muž dostane. Přečte to a stane se jedna ze dvou věcí. Buď to dříve nečetl, v takovém případě vygeneruje nové náhodné číslo a dá vám ho, přičemž vaši zprávu i číslo odevzdá do paměti. Nebo přečetl tento přesný údaj zpráva dříve, v takovém případě si zapamatuje číslo, které vygeneroval při prvním čtení, a poskytne vám číslo tht. Generátor náhodných čísel nikdy nevygeneruje číslo, které již vygeneroval, má nekonečnou možnou velikost a malý muž paměť je neomezená a neomylná. Malý človíček si proto nikdy nebude myslet, že si přečetl zprávu dříve, pokud ji nemá, nikdy nezapomene, že si přečetl zprávu dříve, a proto nikdy nevytvoří dvě různá čísla pro přesně stejnou zprávu ani stejnou číslo pro dvě různé zprávy.

   To se snaží simulovat hashovací funkce. Nemohou modelovat tohoto malého muže s fotografickou pamětí, protože by to vyžadovalo nekonečný úložný prostor a neomezenou univerzální dostupnost, dokonce zařízení, která nejsou připojena k žádnému jinému zařízení jakýmkoli jiným způsobem. Místo toho se spoléhají na deterministický, ale náhodný vypadající výpočet, který zprávu „rozdělí“ na hodnotu hash. Stejná funkce hash, vzhledem ke stejné zprávě bude produkovat stejný výtah; tyto funkce jsou však omezeny počtem hodnot hash, které mohou vrátit. Tím se vytváří možnost toho, co nazýváme hashovacími kolizemi; existuje více možných zpráv než hodnot hash, takže dříve nebo později (doufejme, že později), dva různé já ssages bude produkovat stejný hash.

3. Hashes lze prolomit ze tří základních důvodů.Zaprvé, protože jsou deterministickým matematickým odvozením jejich zprávy, matematici (a tedy útočníci) nakonec najdou matematický vztah mezi zprávou a jejím hashem nebo mezi dvěma zprávami a jejich výslednými hashe. To, co kdysi vypadalo náhodně, už tomu tak není. To by umožnilo řadu útoků založených na povaze zjištěné slabosti; pokud existuje algoritmický způsob, jak danou zprávu a její hash vygenerovat kolidující zprávu, je to problém. Pokud existuje způsob, jak manipulovat se zprávou a předvídat výsledný hash, jedná se o jiný problém. Pokud ve skutečnosti existuje způsob, jak zvrátit hash, vytvořit zprávu z hash, která při opětovném hašování produkuje stejný hash, že „je vážný problém.

   Zadruhé, protože hashe mají omezenou velikost souhrnu, dříve nebo později budou dvě zprávy produkovat stejný hash. To znamená, že útočník nemusí najít zprávu, kterou používáte k vytvoření určitého hash ; vše, co musí udělat, je najít a zprávu, která produkuje stejný hash. Šance na to jsou malé, teoreticky jedna šance z mnoha možných hashů, ale stále lepší než jedna v nekonečnu.

   A konečně, i když existuje spousta možných zpráv, existuje mnohem menší počet pravděpodobných zpráv. Zprávy, které obvykle dáváme hashovacím funkcím, mají obvykle nějakou strukturu (na základě jazyka, obsahu, elektronického formátování a účelu), což znamená, že vzhledem k určité části zprávy můžeme přesněji odhadnout další části zprávy. To znamená, z hlediska informační vědy, že zprávy, které jsou převedeny na hashe, mají často nižší entropii než samotná hash funkce; jednoduše řečeno, hash funkce, která produkuje 256-bitové digesty, může teoreticky vytvořit jakoukoli permutaci těchto bitů, 2 ^ 256. Pokud však existuje, řekněme, pouze 10 000 možných zpráv, které by někdy mohly být vloženy do této hashovací funkce systémem studovaným na útok, pak bude vidět pouze 10 000 z 2 ^ 256 možných hodnot hash, a co je důležitější, Útočník by v nejhorším případě musel vyzkoušet všech 10 000 možných vstupů, aby našel ten, který vytváří hodnotu hash, kterou hledá.

Komentáře

• A tohle …. proto miluji IT security ‚ s webem pro výměnu zásobníku.
• Také vaše vysvětlení z # 1 je přesně to, co jsem potřeboval. Mám však otázku. Zdá se, že “ hash “ jsou jako číselné verze pro danou věc (v tomto případě hesla). Takže pokud mám web a zaregistruje se 100 000 lidí. Potom 50% použije heslo “ heslo “ jsem schopen ušetřit spoustu místa pouhým uložením hodnoty hash “ heslo “ místo hesla mnohokrát?
• Pokud tedy ‚ znovu používá zabezpečený hash (> = 256bitová velikost digestu) a poté uloží hašovanou hodnotu “ hesla “ zvýší velikost vašeho úložiště. Pokud navíc útočník uvidí, že 50% uživatelských účtů má stejný hash hesla, ‚ ví, že vše, co ‚ musí udělat prolomení jednoho hesla a má přístup k 50% uživatelských účtů. Měli byste “ solit “ hodnoty hash hesla; existuje celá řada metod, ale konečným výsledkem je, že stejné heslo hašované stejným algoritmem vytváří jiný výtah kvůli další jedinečné hodnotě soli pro každý účet.