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) позволяет найти коллизию не за 2n/2 попыток, а при хэшировании сообщений существенно большой длины k за 2n/2-k/2.
Результат пока не имеет практического значения, но может потенциально сделать недействительными многие доказательства протоколов в модели случайного оракула для существующих хэш-функций и заставить пересмотреть ход конкурса SHA-3.
Ранее авторы давали оценку неидеальности "narrow-pipe" хэш-функциям SHA-3 кандидатов: BLAKE, Hamsi, SHAvite-3, Skein.
Источник: Cryptology ePrint Archive
комментариев: 11558 документов: 1036 редакций: 4118
Нам он запомнился и некоторыми другими исследованиями.
если от сообщения длиной скажем к=256 бит взят хеш длиной 128-бит, тогда 2^(n/2-k/2) = 2^(128/2-256/2)=2^(64-128)=2^(-64)?
неувязочка в том, что читать надо внимательнее...
комментариев: 9796 документов: 488 редакций: 5664
Речь идёт о том, что при хэшировании сообщений порядка двух терабайт (в виде двух составных частей A и B 29 + 235), стойкость снижается до 2111 в том случае, где должно быть 2128.