Oznámen vítěz SHA-3

NIST vybral vítěze SHA-3. Z pětice finalistů se jím stala funkce KECCAK. Mezi hlavní důvody výběru patří elegantní konstrukce algoritmu umožňující snadnou analýzu, rychlá hardwarová implementace a designová odlišnost od SHA-2.

3.10.2012 11:13 | CiV | Zajímavý projekt

Komentáře

[snajpa]

Co se mysli tou rychlou hardwarovou implementaci? Asi jsem to spatne pochopil, ale mel jsem za to, ze by prave spocitani hashe melo trvat dlouho, aby znesnadnovalo bruteforce utoky... nebo to chapu spatne/neuplne?

[Michal Kubeček]

Jenže na druhou stranu není praktické zdržovat normální aplikace, které hash používají např. pro autentizaci síťové komunikace. Takže je praktičtější mít rychlý algoritmus a brute force attack znesnadnit tím, že je hash delší, takže je (pokud není zásadní chyba v návrhu) potřeba víc pokusů.

Tam, kde je počet potřebných pokusů principiálně omezený, jako třeba u hashování hesel, se pak používají různé nadstavby. Jako třeba "MD5" jako formát v /etc/shadow není ve skutečnosti přímo MD5, ale komplikovanější algoritmus, který MD5 používá jako svůj základ.

[Luk]

Jako třeba "MD5" jako formát v /etc/shadow není ve skutečnosti přímo MD5, ale komplikovanější algoritmus, který MD5 používá jako svůj základ.

On ještě někdo používá v /etc/shadow algoritmus MD5, resp. jeho odvozeninu? Pokud vím, tak se zatraceně dlouho používá Blowfish, nové distribuce (např. openSUSE 12.x) používají SHA-512.

[Michal Kubeček]

Ta možnost tam pořád je, byl to jen příklad. Navíc i v případě SHA-256 nebo SHA-512 to funguje stejně: není to ten samotný hashovací algoritmus, ale komplikovanější funkce, která ho používá jako základ.

[radix]

Hashovaci funkce by mela byt rychla, aby slo rychle hashovat velke mnozstvi dat.

Pro brute force utoky jsou rychlosti hashovacich funkci mene podstatne, protoze obrovsky prostor reseni je neresitelny bez ohledu na rychlost. Daleko dulezitejsi je odolnost proti potencialnim utokum, ktere dokazi snizit asymptotickou slozitost reseni (nalezeni kolize apod.)

[Franta]

+1

[8an]

U slovníkových útoků na hashe hesel nebo na odposlechnutou WPA autentizaci na rychlosti výpočtu hashe záleží. Pro vyšší zabezpečení je možné hashování iterovat (třeba tisíckrát), ale pak je zase potřeba, aby se výsledek tísíce hashování nedal spočítat nějak rychleji.

[radix]

Rozumne solene hesla jsou proti slovnikovemu utoku odolne.

U hesel a podobnych veci je bohuzel brute force utok teoreticky mozny a proto je casto nutne vypocet zpomalit. Neni pak ale problem rychlou hashovaci funkci zkombinovat s nejakym proof-of-work algoritmem.

[8an]

Solená hesla jsou odolná jenom proti rainbow tables, ne proti klasickému slovníkovému útoku (kde se prostě pro každé heslo ze slovníku spočítá hash).

[radix]

Jo, sorry, popletl jsem to.

[j]

Pokud budu chtit poradat takovy utok tak nebudu ty hashe pocitat, ale pouziju rainbow table. Takze je mi zcela uprdele, jak rychle se hash jako takovy spocita. Vykon je podstatny prave proto, aby bylo mozny snadno a rychle hashovat hromadu dat.

[mykhal]

tady by se neměly používat obyčejné haše, ale KDF, jako třeba bcrypt, scrypt, PBKDF2, ..

[Adam]

A pride aj SHA-4 a SHA-5 lebo uz sa pracuje na paralelnych multiprocesorovych chipoch - napr. projekt Parallela (http://tinyurl.com/cm6yxee) slubuje od 99 dolarov 16 az 64 ARM procesorov v celkovej rychlosti az 45Ghz... :)

[j]

Jenom 64? Lecjaka grafarna zvladne zaroven pocitat mnohem vic ... ;D, na tyhle ulohy je totiz CPu zbytecne moc uni nastroj.

[ovoce]

"Celková rychlost 45 GHz"

Hahaha, já měl za to, že na tohle už dneska lidi neskočí. Muste odečíst overhead a škálování, a ono jedno jádor Cortexu A-9 není žádná výhra.

[Jendа]

A jak to s tím souvisí? Jako že by se to na takovém počítači hrubou silou cracklo? Jak dlouho by trval 256bitový hash, kdyby takové zařízení měl každý člověk na světě doma a v jednom hodinovém taktu by vyblilo třeba 64 (uvažujme bitslicing na 64b procesoru) individuálních výsledků?

Nebo ještě lépe Radeon HD5970, 2x1280 cores x 256 slices/core.

[mykhal]

tak teď bude trochu oříšek, jak SHA-3 utility pojmenovat, protože sha224sum sha256sum sha384sum sha512sum už má obsazené SHA-2 ..

[grim]

co třeba: shb224sum shb256sum shb384sum shb512sum

[tom]

sha256sum --sha3

[Michal Kubeček]

To spíš obráceně.

[mykhal]

takže sha256sum --sha2

a sha256sum by najednou házelo nové Keccak haše? :)

[radix]

sha3 --256

Spis takto (nebo podobne).

[Michal Kubeček]

Tak nějak. Spíš bych to ale viděl na něco jako

  sha3sum -h 256
  sha3sum --hash-length 256

[mykhal]

to by ale stále bylo SHA-3, že? což neřeší ten oříšek.

[mykhal]

.. anebo i řeší, nechal jsem se unést :)

[Šangala]

Dal bych sha3224sum sha3256sum sha3384sum sha3512sum - bude to super…

[maestR0]

lol

[Michal Kubeček]

Raději s nějakým odddělovačem, tj. např. sha3_256sum, jeden nikdy neví… :-)

[Šangala]

No když jsme už o návrhu standardu do budoucna doplnil bych to na sha3_00256sum :)

[Grunt]

Můj původní návrh byl: sha324sum a sha356sum