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.

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

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