Vlákno názorů k článku LastPass byl podruhé napaden, unikly hashe hesel od Honza - zaheslovaný rar??? proč ne :-) ale řekl bych, že...

No šifruje se hashovaným heslem. Ale z toho nijak neplyne, že když to heslo zahashuju dvakrát, tak je dvakrát těžší tu *šifru* prolomit.

Vtip je v tom, že prostor hodnot funkcí f a g, kde f je "100000xsha256" a g je "sha256" je stejný.

Nikoli, prostor hodnot f <= prostor hodnot g. Dokonce pokud by platila ta rovnost, bylo by to podle mne špatně, protože by sha256 byla do jisté míry předvídatelná.

Byl by důkaz?

Pokud by ty prostory byly stejné, znamenalo by to, že SHA256 mapuje každé z čísel 1 až 2²⁵⁶ na jiné číslo z rozsahu 1 až 2²⁵⁶. Což by samozřejmě platilo i opačně, tedy že ke každému SHA256 hashi existuje právě jedno "zdrojové" číslo v rozsahu od 1 do 2²⁵⁶. Zároveň byste dokázal - pokud byste někdy v budoucnosti měl tabulku všech hashů od 1 do 2²⁵⁶-1 - určit hodnotu SHA256 hashe 2²⁵⁶ bez použití SHA256 funkce. To není zrovna hezké chování na hashovací funkci.

Ano, ano, to je pravda. Udělal jsem chybu v tom slově "je stejný". Měl jsem napsat něco v tom stylu, že nevíme, jak je ten prostor pokrytý, takže je (za předpokladu téhle neznalosti) stejně pravděpodobné, že heslem pro AES bude cokoli z prostoru 0-2^256, čili jestli heslo proženu SHAčkem jednou nebo stotisíckrát, tak se tím nijak nezmění moje znalost o tom, co je heslem - pořád to (pro mě jako útočníka) může být cokoli z prostoru 0-2^256. Ve skutečnosti to některé z těch hodnot být nemůžou, čili prohnat heslo SHAčkem víc než jednou vede ke SLABŠÍ bezpečnosti, čili i tak se "hrk" zmýlil, akorát moje zdůvodnění nebylo přesné.

Resp. 1-2^256, ať učiníme chytání za slovíčka za dost :)

Ve své podstatě je to pro ukládání hesel workaround a jsou k dispozici funkce specializované na tenhle účel (kdf), které nejsou jenom iterace "univerzálního" hashe. Bcrypt, scrypt...

Záleží na tom, jak rychle to opakované hashování ten prostor možných kombinací zmenšuje – rád bych to někdy pro ideální hashovací funkci spočítal. Předpokládám, že vzhledem k poměru velikosti výstupní množiny SHA256 (2²⁵⁶) a počtu iterací (v tomto případě 1000) je to na aktuálním dostupném výkonu strojů stále bezpečné. Ale pokud by někdo dostal nápad, že použije nějaký krátký hash a zvýší počet iterací, posouvá se tím ke snížení bezpečnosti.

> Záleží na tom, jak rychle to opakované hashování ten prostor možných kombinací zmenšuje – rád bych to někdy pro ideální hashovací funkci spočítal.

To se obecně řešit nedá, ne? Záleží to na tom, kolik bude v té které iteraci kolizí, což by u dobré hashovací funkce mělo být náhodné číslo, ne? Nebo se na to dá vymyslet nějakej fígl - odhad, střední hodnota apod.?

Chtěl jsem to počítat pro ideální hashovací funkci, která pro libovolný vstup vrací náhodný výstup, kdy každá možná výstupní hodnota má stejnou pravděpodobnost. Pravděpodobnost kolize pak jde spočítat podle narozeninového paradoxu.

Jasně, tohle je dobrej fígl, to jsem is neuvědomil. Akorát teda je to čistě idealistický výpočet, který s realitou nemá moc společného ;)

> Ano, nějak takhle se bude ideální hashovací funkce chovat.

Ideální možná - pokud si takhle ideál nadefinuju. Každá reálná hashovací funkce má nějaké kolize, čím by mělo být dáno, že by neměly existovat kolize ausgerechnet při vstupu 1-2^256?

No a to byla právě pointa - prostor hesel (P0) je (dejme tomu) nekonečný, po prvním průchodu hashfunkcí se namapuje na prostor P1, po druhém na P2, po třetím na P3 atd. Zaručeně platí, že |Pn-1| <= |Pn|. Podle mě u dobré hashfunkci se nedá obecně nic říct o tom, co Pn obsahuje - měla by to být náhodná množina, takže i ke zmenšování prostorů by mělo dojít náhodně "někdy". Jedinou jistotou, kterou máme, je, že když k tomu zmenšení dojde, tak už se to nikdy "nedožene", nikdy už ten prostor nenaroste. Takže čistě statisticky se zvyšováním počtu iterací se *nějak* ten prostor zmenšuje. Akorátže útočník stejně neví jak a není schopný to hrubou silou vyzkoušet, takže mu to stejně nedá žádnou informaci, kterou by mohl v útoku využít.

Sorry, překlep.

Zaručeně platí, že |Pn-1| >= |Pn|.

Ano, nějak takhle se bude ideální hashovací funkce chovat.
Ne, nebude. Ideální hashovací funkce vrací pro vstupní hodnotu náhodnou hodnotu z oboru výstupních hodnot, přičemž pravděpodobnost výběru kterékoli hodnoty je stejná – takže například nijak nezávisí na tom, zda daná výstupní hodnota je nebo není výstupní hodnotou také pro jiný vstup.

Představte si to třeba na hashovacích funkcích, které vrací pouze 0 a 1. Ideální hashovací funkce vrací pro jakoukoli vstupní hodnotu 0 s pravděpodobností 50 % a 1 také s pravděpodobností 50 %. (Ideální hashovací funkce se bude chovat tak, jako by měla nekonečnou paměť a ideální generátor náhodných čísel. Pro každý vstup se nejprve podívá do paměti, zda už pro něj nemá známý výsledek. Pokud ne, náhodným generátorem vybere jeden z možných výstupů a zároveň si ho uloží do paměti.) Mnou popsaná funkce, která pro obor vstupních hodnot shodný s oborem oborem potenciálních výstupních hodnot pokryje všechny možné výstupní hodnoty (tedy např. funkce identita), by tedy pro vstup 0 vrátila výstup např. 0, a tím pádem by pro vstup 1 už zbyla jediná možná hodnota, tedy 1.

Pro ideální hashovací funkci s oborem hodnot 2¹ tedy platí, že s pravděpodobností 50 % zůstane po jedné iteraci obor hodnot stejný a s pravděpodobností 50 % se zmenší na polovinu.

> Odpověd asi bude že ne, a budou to spíše nějaké cykly, velmi dlouhé..

To by mě teda dost zajímalo, kdo a proč tohle tvrdil. Ne že by to nemohla být pravda, jenom by mě zajímalo, jak k tomuhle dospět - jestli nějakou detailní analýzou konstrukce té konkrétní hashfunkce nebo jak...

Myslím si, že rychlost zmenšování je zanedbatelná vzhledem k tomu, kolik iterací jsme dnes reálně schopni udělat. Ale jak jsem psal jinde, než si to jen tak bůhvíproč myslet, radši bych to spočítal :-)

Jasně, zpomalování je korektní argument (narozdíl od předchozího). Jenom by mě zajímalo, jaké zpomalení to reálně může být proti odhodlanému a movitému útočníkovi. Jestliže jsou k dispozici bitcoinové asicy s výkonem v řádu GHash/s...

Problém je v tom, že to zpomalování zároveň způsobuje zmenšování prostoru. A jde o to, aby to zmenšování prostoru nakonec nemělo větší efekt, než zpomalování.