openPGP в России / Новости / 2008 / Обнаружены коллизии для хэш-функций SHA-2 с сокращённым числом шагов

11.03 // Обнаружены коллизии для хэш-функций SHA-2 с сокращённым числом шагов

Индийские исследователи Somitra Kumar Sanadhya и Palash Sarkar при содействии Министерства Информационных Технологий правительства Индии опубликовали первый результат
криптоанализа хэш-функций SHA-2: "22-Step Collisions for SHA-2". Им удалось создать метод нахождения коллизий с вероятностью 2^-5 – 2^-9, но только для
22 раундов хэш-функций SHA-256 и SHA-512.

Никаких подробностей пока не приводится, а опубликован только результат для проверки.
Напомним, что функция SHA-256 имеет 64 раунда, а SHA-512 – 80 раундов, так что атака на неполное число раундов имеет чисто теоретический характер, с другой стороны она движется по тому же пути, что и в случае с MD5 или SHA-1, коллизионная нестойкость которых была доказана в течении относительно короткого периода времени.

Источник: Cryptography and Security Archive

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

—	sentaus (11/03/2008 16:58) профиль/связь <#> комментариев: 1060 документов: 16 редакций: 32

Будем надеяться, что будущие реальные атаки будут далёкими от практической применимости...

—	*Гость* (11/03/2008 17:44) <#>

Заголовок вводит в заблуждение. Лучше, например, такой:

Обнаружены коллизии для хэш-функций "частичный SHA-2"

—	Другой_Гость (11/03/2008 18:38) <#>

("Частичные коллизии" == "предколлизии") != "коллизии в частичном алгоритме"

—	*Гость* (12/03/2008 01:15) <#>

Похожие результаты получены и другими исследователями:

We find 20 and 21-step collisions (collisions for the original initial value) with probabilities 1/3 and 2^-19 respectively. Also we were able to find a 23-step semi-free start collision (collisions for a specific initial value) with probability 2^-21. Our fnal result is a 25-step semi-free start near collision with Hamming distance of 15 bits and probability 2^-34.

Ivica Nikolic and Alex Biryukov. file

Collisions for step-reduced SHA-256

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

("Частичные коллизии" == "предколлизии") != "коллизии в частичном алгоритме"

Да, верно. Заголовок исправлен.

Тем не менее получается уже практически доказано – раундовая функция SHA-2 коллизионно нестойкая, гораздо меньший результат был получен Доббертином в середине 90-х для MD5, что дало основание скептически настроенным криптографам объявить MD5 нестойкой уже тогда (Шнайер призывал отказаться от MD5 ещё в своей "Красной Книге").

2 SATtva – когда исправляется заголовок, нельзя ли сделать автоматом исправление ссылки на документ?

—	Dmitry_Khovratovich (12/03/2008 16:10) <#>

>>Тем не менее получается уже практически доказано – раундовая функция SHA-2 коллизионно нестойкая.

Гыгыгы. Во всех этих атаках практически нет message scheduling, поэтому дифференциалы такие хорошие и получаются. При выходе за 25 раундов наступает жопа.

—	*Гость* (12/03/2008 23:31) <#>

Шнайер призывал отказаться от MD5 ещё в своей "Красной Книге"

Припоминая всё ещё то обсуждение, хочется добавить, что вся криптография есть скорее "мера нашего незнания" о математике :-D

—	Вадимус (04/07/2013 23:33) <#>

2013 год. Июль. Полет нормальный (не смотря на большую популярность сети Bitcoin)

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