openPGP в России / Новости / 2010 / Универсальная атака на хэш-функции MDx, SHA-1, SHA-2 и ряд кандидатов SHA-3

06.08 // Универсальная атака на хэш-функции MDx, SHA-1, SHA-2 и ряд кандидатов SHA-3

Исследователи Властимил Клима (независимый криптограф-консультант, известный практическими работами по оптимизированному взлому MD5; Чехия) и Данило Глигороски (сотрудник кафедры информационных технологий, математики и электротехники Института телематики, а также Норвежского Университета Науки и технологии, Трондхэйм) обнаружили теоретическое отличие в поведении множества хэш-функций от модели случайного оракула.

В своей работе Generic collision attacks on narrow-pipe hash functions faster than birthday paradox, applicable to MDx, SHA-1, SHA-2, and SHA-3 narrow-pipe candidates они пытаются доказать, что использование функции сжатия в режиме "Narrow-Pipe" (что используется в большинстве хэшей и в дизайне многих кандидатов конкурса SHA-3) позволяет найти коллизию не за 2^n/2 попыток, а при хэшировании сообщений существенно большой длины k за 2^n/2-k/2.

Результат пока не имеет практического значения, но может потенциально сделать недействительными многие доказательства протоколов в модели случайного оракула для существующих хэш-функций и заставить пересмотреть ход конкурса SHA-3.

Ранее авторы file давали оценку неидеальности "narrow-pipe" хэш-функциям SHA-3 кандидатов: BLAKE, Hamsi, SHAvite-3, Skein.

Источник: Cryptology ePrint Archive

Комментарии [скрыть комментарии/форму]

—	SATtva (06/08/2010 18:49) профиль/связь <#> комментариев: 11558 документов: 1036 редакций: 4118

Властимил Клима

Нам он запомнился и некоторыми другими исследованиями.

—	*Гость* (06/08/2010 23:14) <#>

Что-то неувязочка получется:
если от сообщения длиной скажем к=256 бит взят хеш длиной 128-бит, тогда 2^(n/2-k/2) = 2^(128/2-256/2)=2^(64-128)=2^(-64)?

—	Гость (08/08/2010 11:25) <#>

а при хэшировании сообщений существенно большой длины k

Что-то неувязочка получется:

неувязочка в том, что читать надо внимательнее...

—	unknown (09/08/2010 12:38) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

two parts A and B, i.e. M = A||B, where the part A consist of just one message block of 512 bits, and the number of 512-bit blocks in the part B is N = 2^35 (in case of current 2TByte HDD).

If we compute hash values for 2^111 different parts A (whereas the part B remains unchanged), we will obtain 2^111 hash values hN. According to the birthday paradox it is sufficient for finding a collision in the set of 1 these values with probability around 2. Cryptographically strong hash function H should require approximately 2^128 hash computations.

Речь идёт о том, что при хэшировании сообщений порядка двух терабайт (в виде двух составных частей A и B 2⁹ + 2³⁵), стойкость снижается до 2¹¹¹ в том случае, где должно быть 2¹²⁸.

Ваша оценка документа [показать результаты]