Состояние исследований по столкновительным атакам SHA-1

Безопасность SHA-1 обсуждалась с тех пор, как алгоритм обнаружения столкновений был впервые опубликован в CRYPTO 2004 и впоследствии был улучшен.

В Википедии перечислено несколько ссылок , однако, похоже, что последнее исследование, опубликованное (и позднее отозванное) по этому вопросу, было в 2009 году (Кэмерон Макдональд, Филип Хоукс и Джозеф Пепжик "Дифференциальный путь для SHA-1 со сложностью O (2 ^ 52)" ).

С тех пор был ли достигнут какой-либо значительный прогресс в снижении усилий для хэш-атаки на SHA-1?

Мы будем благодарны за ссылку на конкретное исследование, сопровождаемое кратким резюме.

cr.crypto-security hash-function cryptographic-attack Йоханнес Рудольф
источник

Вы можете проверить RFC6194 (март 2011 г.)

нетопе

Я знаю, что это старый, но если вы все еще заинтересованы: eprint.iacr.org/2012/440

mikeazo

Я знаю, что это старый, но если вы все еще заинтересованы, вы можете взглянуть на sites.google.com/site/itstheshappening .

бозон

Ответы:

SHA-1 был Разрушенные от Stevens и др . Они продемонстрировали, что столкновения в SHA-1 являются практичными. Они дают первый случай столкновения для SHA-1.

$p$ $s$

S H A - 1 (p ‖ m_{0} ‖ m_{1} ‖ s) = S H A - 1 (p ‖ m_{0}^{'} ‖ m_{1}^{'} ‖ s)

$\operatorname{SHA-1}(p \mathbin\Vert m_0 \mathbin\Vert m_1 \mathbin\Vert s) = \operatorname{SHA-1}(p \mathbin\Vert m'_0 \mathbin\Vert m'_1 \mathbin\Vert s)$

s

$s$

(m_{0}, m_{1}) \neq (m_{0}^{'}, m_{1}^{'})

$(m_0, m_1) \neq (m'_0, m'_1)$

Вычислительная потребность оценивается в $2^{63.1}$

Первый ближний столкновение первого блока был обнаружен после того, как он провел около 3583 основных лет, в результате чего было получено 180 711 частичных решений до этапа 61. Позднее был вычислен второй блок ближнего столкновения; потребовалось дополнительно 2987 лет и 148 975 частичных решений. ¹

kelalaka
источник