openPGP в России

04.06 // Опубликована работа по нахождению коллизий в SHA-1 за 2⁵² шагов

После краткого анонса на конференции Eurocrypt-2009 Cameron McDonald, Philip Hawkes и Josef Pieprzyk опубликовали работу Differential Path for SHA-1 with complexity $O(2^{52})$^[link1].

Рассмотрев все известные ранее способы нахождения коллизий и применив комплексный подход, объединяющий обычный дифференциальный анализ с его разновидностью в виде бумеранг-атак, ранее применявшихся только для блочных шифров, авторам удалось найти атаку на нахождение коллизии в SHA-1 за время O(2⁵²).

Напомним, что теоретический предел стойкости SHA-1 к нахождению коллизий 2⁸⁰, а продемонстрированная ранее самая успешная атака имела сложность 2⁶³. Такое снижение времени нахождения коллизий является существенным прогрессом в криптоанализе и приближает к возможному осуществлению практических атак на SHA-1


Источник: Cryptology ePrint Archive^[link1]