Dotaz: hashovaci funkce

[jenda]

Ahoj,

nevim jestli je tohle vhodne tema, ale pokud by se nekdo nasle kdo by mi to vysvetlil tak budu rad. Moc mi neni jasne k cemu je v kryptologii hashovani. Ja to teda pochopil tak, ze takhle zasifruji treba nejakou zpravu a vystupem mi je naprosto nesrozumitelna zprava. Ale podle toho co jsem si precetl pote neni mozne (nebo je velmi obtizne) ziskat originalni informace, ktere jsem predtim zahashoval. Jelikoz v (a)symetricke kryptografii opet ziskam puvodni data, trochu se ztracim, k cemu to tedy prakticky slouzi, kdyz uz neziskam data v puvodnim tvaru. Mozna jsem si to jenom spatne vylozil, ale pusobilo to na me jako bezklicova varianta (a)symetricke kryptografie. Diky moc, mejte se!

Odpovědi

[potato]

Hashování není šifrování,

Jde o to, že namísto zprávy se díváš pouze na její hash. Je-li hash kryptograficky silný, tak porovnání hashů v nějakém smyslu zastupuje porovnání celých zpráv.

[Jendа]

Hash se používá, když potřebuješ:

• Z dlouhých zpráv udělat nějaké hodnoty fixní kratší délky.
• Na zprávě udělat transformaci, její výsledek zveřejnit, ale nechceš, aby někdo znal původní zprávu. Později se pak třeba můžeš tou zprávou někomu prokázat a on udělá tu stejnou transformaci a porovná výsledky.

[:::]

Par pouziti je popsanych treba tady:

https://en.wikipedia.org/wiki/Cryptographic_hash_function#Applications

Potom se pouzivaji treba v generatorech nahodnych cisel (ktery jsou hodne dulezity v kryptografii):

https://www.schneier.com/paper-yarrow.html

To pouziti je tam asi takovy ze do entropy poolu si ukladas "low quality random data" a az jich mas dost tak spocitas jejich hash, cimz ziskas "high quality random data". Ty potom muzes pouzit primo, nebo jako seed.

Jeste bych doporucil:

https://www.coursera.org/course/crypto

https://www.coursera.org/course/crypto2

[Jendа]

Pozor! Kryptograficky bezpečná hashovací funkce automaticky neznamená, že výstup bude náhodný! Například funknce

def JHA(input):
  return "AAA"+SHA256(input)

je kryptograficky bezpečná (dokud je jen SHA256 bezpečná), ale zjevně její výstup není moc náhodný.

K extrakci entropie se používá entropy juicer.

[:::]

Ano znamena. Pokud ma byt hashovaci funkce bezpecna tak vystup by mel mit uniformni rozlozeni.

Jednotliva kryptograficka primitiva jsou prevoditelna, takze z bezpecne hashovaci funkce muzes udelat blokovou sifru, proudovou sifru, rng.

na dotaz "entropy juicer" jsem nasel jenom nesmysly tak nevim jestli se nejedna o vtip...

a ta funkce JHA je vtip celkem urcite

[Jendа]

Ano znamena. Pokud ma byt hashovaci funkce bezpecna tak vystup by mel mit uniformni rozlozeni.

Já chápu kryptograficky bezpečnou hashovací funkci tak, že garantuje, že ve výstupu bude alespoň n bitů entropie (přesněji, že spočítání kolize bude mít náročnost 2^n), ale že výstup může být klidně větší než n.

Například definice na Wikipedii pak o náhodnosti a uniformitě (celého) výstupu nemluví vůbec.

Ostatně, byly současně používané SHA designované with this in mind nebo je to jenom takový by-product?

[:::]

To je pravda ze pro nektery ucely by stacila omezena entropie ve vystupu.

Ale myslim ze v praxi to skonci na tom ze u digestu delky N se ocekava bezpecnost 2**N.

Treba u te funkce JHA(), kdyz odstranim ten prefix tak jsem v podstate vytvoril attack ktery snizi jeji bezpecnost o 24 bitu

[Jose]

Hasovaci funkce da vzdy pro stejna vstupni data stejny vystup, nepouziva se na kryptovani ale na podpisovani a overovani.

[:::]

Hasovaci funkce da vzdy pro stejna vstupni data stejny vystup,

Jakykoli algoritmus da vzdy pro stejna vstupni data stejny vystup.

nepouziva se na kryptovani ale na podpisovani a overovani.

Nepouziva se na sifrovani, ale kryptograficka primitiva jsou prevoditelna, takze z bezpecne hash funkce muzes vytvorit PRF a z PRF sestavit blokovou sifru. Viz Luby-Rackoff theorem:

https://en.wikipedia.org/wiki/Feistel_cipher

[axel]

Jakykoli algoritmus da vzdy pro stejna vstupni data stejny vystup.

Odvazne tvrzeni

[Jose]

Hasovaci funkce da vzdy pro stejna vstupni data stejny vystup,

Jakykoli algoritmus da vzdy pro stejna vstupni data stejny vystup.

Plati jen pokud je PRN generator zavisly pouze na vstupnich datech algoritmu, coz ale pokladam za oslabeni sifry ( to plati samozrejmne jenom u sifrovacich algorimtu kde do sifrovaciho procesu vstupuje nahodne cislo )

[:::]

Vim ze je to trochu slovickareni, ale jakykoli nahodny data muzes povazovat za vstup algoritmu. Takze pokud bude dostavat stale stejny "nahodny" data tak by mel davat stejny vysledky.

[Sten]

Jakykoli algoritmus

Jakýkoliv deterministický algoritmus. Takové OpenSSL v Debianu by mohlo vyprávět.

[Jendа]

Pokud do „stejných vstupních dat“ zahrneme i seedy získané odjinud, tak to taky platí…

[axel]

Pokud za vstup budeme povazovat "vsechno", tak uz tvrzeni postrada smysl, protoze "vsechno" nelze definovat a tedy nelze zarucit (ani overit), ze pri dvou bezich algoritmu bude "vsechno" stejne. Ne kazdy stroj (ani realne existujici, natoz hypoteticky) ma vlastnosti topinkovace, na kterem jakoby zadny nedeterminismus neexistuje.

[:::]

Vsechny vstupy algoritmu se daji definovat snadno. Alo to uz se dostavame k filozoficky debate v ktery stejne nic nevyresime...

Ja osobne povazuju jakoukoli nahodnost za vstup algoritmu, ktery potom pracuje deterministicky.

[axel]

A ja osobne povazuju kolobezku za motorove vozidlo. Existuje obecne prijimany pohled na to, co je to algoritmus, jeho vstup a determinismus/nedeterminismus pri jeho provadeni. Pro nektere ucely se pak tyto pojmy zcela formalizuji (napr. zkoumani slozitosti algoritmu), jinak by se o nich nedalo premyslet, publikovat, komunikovat atd. Pohled ze "jakakoli nahodnost" je vstupem algoritmu je v tomto ohledu novatorsky, mozna se prosadi, mozna ne... Myslim si, ze spis ne.

[:::]

A ja osobne povazuju kolobezku za motorove vozidlo.

to hodne vysvetluje

Existuje obecne prijimany pohled na to, co je to algoritmus, jeho vstup a determinismus/nedeterminismus pri jeho provadeni.

nedeterminismus je neco jinyho nez nahodnost.

Pohled ze "jakakoli nahodnost" je vstupem algoritmu je v tomto ohledu novatorsky

diky za uznani. Jestli bych si to nemel patentovat...

Ale obavam se ze zas tak novatorsky to neni. Viz treba wikipedia:

A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input

[axel]

nedeterminismus je neco jinyho nez nahodnost

Vyborne. Plati tedy predchozi tvrzeni Jakykoli algoritmus da vzdy pro stejna vstupni data stejny vystup pro nedeterministicke algoritmy?

[:::]

Priznavam ze v tom tvrzeni jsem pod "algoritmus" mel na mysli deterministicky algoritmus, protoze to se tim vetsinou mysli.

Nicmene se to da zobecnit i na nedeterministicke. Kdyz napr. vezmu kvantovy pocitac jako typicky priklad nedeterministicke architektury, tak pri stejnych vstupech vzdy dostanu stejnou vyslednou vlnovou funkci. To ze tu funkci potom nejsem schopen primo zmerit a musim delat ruzny harakiri je uz jina vec...

[Šangala]

Jakykoli algoritmus da vzdy pro stejna vstupni data stejny vystup.

Programoval si někdy?

[:::]

Taky uz jsem se setkal s programama ktery fungujou jenom ve ctvrtek a za uplnku.

Moje soukroma teorije je ze algoritmus je sice deterministicky, ale muj PC si uvedomil sam sebe a zacal v nem skodolibe delat male tezko odhalitelne zmeny...

[xkucf03]

Problém je spíš v tom, že uživatel si není vědom¹ všech vstupů – proto mu výstup může někdy přijít náhodný a program nedeterministický.

_{[1] což nemusí být úplně jeho vina – program může být napsaný dost záludně, tak, že některé vstupy nejsou na první pohled vidět, nedají se intuitivně odhadnout nebo jsou úplně nesmyslné}

[Filip Jirsák]

Jak už psali ostatní, hashování není šifrování. V souvislosti s bezpečností ale někdy nepotřebujete celou zprávu, ale stačí něco kratšího jednoznačně vytvořeného z původní zprávy. Důležité je akorát to, aby k existujícímu hashi nebylo možné snadno zkonstruovat (libovolnou) zdrojovou zprávu (zdrojových zpráv je nekonečně mnoho, hashů je omezená množina, takže existuje nekonečně mnoho zpráv, které vedou na jeden a ten samý hash). Hash se používá tak, že se spočítá dvakrát ze dvou různých zpráv nebo ve dvou různých časech. Pokud jsou oba hashe shodné, je vysoká pravděpodobnost (u každé kryptografické hashovací funkce je ta pravděpodobnost známá), že i ty dvě původní zprávy jsou shodné. Hodí se to např. v těchto případech:

• Potřebujete něco elektronicky podepsat, což je forma asymetrického šifrování. Asymetrické šifry jsou pomalé a pracují většinou s blokem dat – musel byste tedy text rozdělit na bloky a každý blok (pomalu) zašifrovat. Když použijete otisk (hash), zašifrujete jenom jeden blok.
• Časová razítka. Ten, kdo vystavuje časové razítko, vůbec nezná původní zprávu (takže to může být klidně něco tajného).
• Ověřování hesel, aniž by ověřovatel musel to původní heslo znát. Např. web může mít uložen jenom hash vašeho hesla, takže pokud stejné heslo používáte i jinde, správce (nebo útočník, který hash získá), se vaším heslem nemůže přihlásit někam jinam. Tady je potřeba dát pozor na to, že pro často používaná hesla (ne jen typu 1234, ale třeba desítky nebo stovky tisíc hesel) už existují seznamy s předpočítanými hashy (říká se jim duhové tabulky), takže při jednoduchém použití stačí správci nebo útočníkovi zkusit najít hash vašeho hesla v takovémhle seznamu. Proto se v tomto případě hesla před hashováním tzv. solí, tj. přidá se k nim něco, co je např. u každého webu jiné. Pak i když budete používat na dvou webech stejné heslo, hash bude jiný, a nebude možné ani předpočítat univerzální duhovou tabulku.
• Ověření toho, že nějaká zpráva je nezměněná (třeba že nedošlo k chybě při přenosu přes síť). Když získáte nějakým spolehlivým způsobem třeba hash souboru, můžete ověřit, že při přenosu přes síť nedošlo k chybě (a změně souboru), nebo že ten soubor někdo nezměnil záměrně.

[ikar]

je tedy crc hash?

[Filip Jirsák]

V obecném smyslu je to hash. Ale není to kryptografický hash, protože je velmi jednoduché pro daný CRC vytvořit nějakou zdrojovou zprávu.

[Sten]

Je, i když není kryptograficky bezpečný

[Jendа]

Pak i když budete používat na dvou webech stejné heslo, hash bude jiný, a nebude možné ani předpočítat univerzální duhovou tabulku.

Nutno podotknout, že to sice zabrání útoku při ukradení databáze, ale heslo je pořád vidět v okamžiku, kdy ho uživatel posílá - když se přihlašuje. A v ten okamžik si ho může správce nebo útočník někam bokem poznamenat. Protokoly na prokázání se, při kterých se heslo protistrana nedozví nikdy, existují, ale jsou podstatně složitější.

[Filip Jirsák]

Heslo při posílání může být vidět a nemusí. Protokoly jako NTLM nebo HTTP Digest mi nepřipadají podstatně složitější -- stejně někdo musí z hesla správným způsobem udělat hash, akorát jde o to, zda to udělá klient nebo server.

[rastos]

Odporúčam Cryptography I.

[lofcek]

Ja to skusim len kratko: Hashovacia funkcia je taka funkcia, ktora vypocita zo vstupnych dat lubovolnej dlzky vystup pevnej dlzky (zvycajne 192, 256, 512 bitov) a to tak, aby bolo mimoriadne narocne (prakticky nemozne) najst take dve vstupne spravy, ktore maju rovnaky vystup.

To sa potom pouziva pri podpisovani. Okrem ineho aj pri podpisovani certifikatu. A to je to miesto kde stretavaju asymetricke sifry s hasovacimi funkciami.

[xkucf03]

Někteří lidé bohužel považují hashování za druh šifrování – říkají např. „to heslo je zašifrované pomocí MD5“ – a pak to vede k těmto zmatkům. Někdy se říká „jednosměrná šifra“ což je ale stále zavádějící a podle mého špatně.

Hashování je jednosměrná funkce. Jejím definičním oborem (vstupem) je pole bajtů o libovolné délce. Jejím oborem hodnot (výstupem) je pole bajtů¹ s fixní (a malou) délkou.

Je logické, že to nemůže být prostá funkce – pro různé vstupy může být výstupem stejná hodnota (hash). Tyto kolize z principu musí existovat.

Dobré hashovací funkce se vyznačují tím, že je tyto kolize velmi náročné najít. Když znáš hash, mělo by být prakticky nemožné najít původní vstup – mělo by to být tak výpočetně náročné, že to se současnou technikou nikdo nedokáže. A i kdyby (jednou) dokázal, z principu najde jen jeden z mnoha možných vstupů – nemá jistotu, že je to ten původní, ze kterého byl hash vypočten. (proto „jednosměrná funkce“).

Další dobrou vlastností je to, že když se vstup změní byť jen nepatrně (třeba o jediný znak/bajt), hodnota hashe se změní zásadně a je to vidět na první pohled (např. c105364f1a847c07860ad7bd9d23eef0 vs. 03f02c6d299c70dcc8d23d14d0c8466d).

Praktické využití:

• kontrolní součty – stáhneš si odněkud obraz CD nebo instalační balíček, spočítáš jeho hash a zkontroluješ, že je stejný s otiskem, který zveřejnil jeho autor, kterému věříš. Pokud hash odpovídá, můžeš si být celkem jistý tím, že data mezi tím nikdo neupravil nebo se nepoškodila chybou při přenosu.
• utajení původní hodnoty při zachování možnosti kontroly – uložíme si zahashované heslo, takže k němu nemáme² přímý a snadný přístup, ale stále máme možnost ověřit, že heslo zadané uživatelem je správné – vypočteme jeho hash a porovnáme s tím uloženým (viz také solení hesel, salt, rainbow tables)
• elektronický podpis – asymetricky stačí podepsat krátký hash místo celé dlouhé původní zprávy
• krátký a unifikovaný identifikátor dat – můžeš snadno vyhledávat duplicity nebo můžeš mít třeba systém do kterého pošleš dotaz typu „sháním soubor s otiskem d27a7f038b715e0b8a438a09704e3102150a4158a7f1372bb6e0e658c00e7c0a“ a zpátky ti přijde odpověď: „má ho ten a ten, stáhni si ho od něj“ (zatímco, kdybys používal jako identifikátor název souborů, bude problém to, že jeden soubor může být pojmenovaný různě a naopak soubory s různým obsahem si mohou dva lidé pojmenovat stejně)
• různé protokoly založené na tom, že někomu pošleš náhodná data, on k nim přidá určitou hodnotu a zpátky pošle hash
• distribuované verzovací systémy
• …

_{[1] někdy chceš mít vstup textový (např. heslo) a výstup taky (např. aby to šlo vytisknout – Base64, Hex), takže musíš hashování obalit funkcemi na převod mezi textem a bajty – ale to nic nemění na tom, že samotná hashovací funkce pracuje jen a pouze s bajty, nějaká textová reprezentace se jí netýká
[2] my nebo útočník, který by ukradl naši databázi}