Nowy atak na funkcje skrótu z rodziny SHA-2

28 września br. japońscy naukowcy Yu Sasaki, Kazumaro Aoki (pracujący dla NTT - Nippon Telegraph and Telephone) oraz Lei Wang (z jednego z tokijskich uniwersytetów) opublikowali swoje wyniki badań na stronach Cryptology ePrint Archive.

Dokonali oni kryptoanalizy dwóch funkcji skrótu z rodziny SHA-2: SHA-256 i SHA-512. Wykorzystanie tych funkcji w zastosowaniach kryptograficznych jest zalecane, przynajmniej dopóki nie zostanie opublikowany standard SHA-3.

W opublikowanym artykule dokonano ataku przeciwobrazowego na wspomniane funkcje haszujące. Jest to atak rodzaju "meet in the middle" (nie mylić z "man in the middle" ;)). Autorzy wykorzystali w nim wcześniej opracowaną technikę częściowego ustalania (partial-fixing).

Kryptoanalizę wykonano dla 41-rundowej wersji SHA-256 i 46-rundowej wersji SHA-512. Dla przypomnienia, wersje oryginalne mają odpowiednio 64 i 80 rund, a najlepsze dotychczasowe ataki kolizyjne i przeciwobrazowe (z 2008 roku) dotyczyły wersji 24-rundowych. Jak widać ilość złamanych rund wzrosła niemal dwukrotnie. Ciekawy jest fakt, że SHA-512 wydaje się bardziej podatna na atak od SHA-256.

Atak Sasakiego et al. na SHA-256 ma złożoność tylko 10 000 razy większą od dotychczas znanego najlepszego (a mówimy o liczbach rzędu 10⁷²). Atak na SHA-512 trwa już 10⁹ razy dłużej (złożoność rzędu 10¹⁵⁴)

Oczywiście Cryptology ePrint Archive prezentuje artykuły nie podlegające procesowi recenzowania, ale jednocześnie autorzy zgłosili ten artykuł na ASIACRYPT 2009 i nie robią tego anonimowo - a to już skłania do myślenia. Zwłaszcza, że funkcje skrótu to najczęściej najsłabsze ogniwa w systemach kryptograficznych.

Więcej: http://eprint.iacr.org/2009/479


Krótko o autorach:
Kazumaro Aoki publikuje artykuły kryptograficzne od 1994 roku, od 1995 jako reprezentant NTT Laboratories.
Yu Sasaki publikuje od 2005 roku. Od 2008 roku, kiedy to dołączył do NTT Laboratories większość artykułów publikuje razem z Aoki.
Lei Wang jest od 2009 roku doktorantem na tokijskim University of Electro-Communications - ten uniwersytet reprezentował przed 2008 rokiem Sasaki.

Przy okazji - jakie badania kryptograficzne sponsoruje Telekomunikacja Polska S.A.? Albo jakiekolwiek inne badania?