Однако ответ не прост, хорошая отправная точка Статья Флорана Шабо и Антуана Жу о SHA-0 и SHA-1
Простое введение
В MD4, SHA-0, SHA-1 и SHA-2 есть функция сжатия. $$C:\{0,1\}^\ell \to :\{0,1\}^n$$ куда $n$ выходной размер и $\ell$ длина блока для обработки.
Функция сжатия $С$ можно рассматривать как блочный шифр, где ключом является сообщение, это имеет смысл, поскольку единственной частью является вход.И SHACAL называется блочным шифром SHA-1 и аналогично SHACAL-2 для SHA-2.
Теперь у нас есть блочный шифр и входные данные (начальные значения $H_i$s и выходное значение (хэш - дайджест). Нам нужно найти ключ. Если мы сможем найти ключ, у нас будут атаки и коллизии прообразов. Это может привести к мысли, что мы атакуем так же, как и при дифференциальных атаках, не совсем так, но похожим образом.
Авторы сначала начали с ослабленного SHA-1 (SHI1), где входное расширение не учитывается, а ADD преобразуется в X-or, чтобы не было нелинейной части. С однобитовым возмущением и поправками на входах они показали нахождение коллизий с маской.
Позже только преобразовал ADD в X-или (SHI2) для расширения атаки. Они находят дифференциальная маска $\mathcal{M}$ который можно применить к открытому тексту (вводу) для поиска коллизий.
lookRandomCollision(ч, блок):
m = ramdom_message (1-блок).
ч = Хэш (м)
м' = маска (м)
ч' = Хэш (м')
Если ч=ч':
возвращение (м)
еще:
возврат -1
пока (1):
успех lookRandomCollision(SHA-1, 512)
если секцесс != -1:
print("Пара коллизий - ", m, mask(m))
Успех атаки - это вероятность успеха маски $\mathcal{M}$ ввести коллизии. Если вероятность успеха маски $1/т$ затем вокруг $c\cdot т$ случайные пары найдут столкновение.
После этого они смотрят на настоящие SHA-0 и SHA-1, чтобы найти такую маску. Они находят один для SHA-0 с $2^{61}$- время сложности. Маска, которую они нашли для SHA-1, не имеет хорошей сложности, чем общая коллизия, т.е. она имеет сложность $> 2^{80}$.
Статья хорошо написана с точки зрения понимания атаки от функции сжатия низкого уровня (без нелинейной части) до функции более высокого уровня, которая включает нелинейность.
И, с большой вероятностью, АНБ знало об этом, поэтому они модифицировали входное расширение SHA-0 на SHA-1, введя ротацию.
Почему это опасно
Рассмотрим случай, когда SHA-1 сломан, у нас есть блок (ы) префикса. $P$ и Блок(и) суффикса $S$ и мы ищем столкновения
$$Hash(P\mathbin\| m \mathbin\|S) = Hash(P\mathbin\| m' \mathbin\|S)$$
Если мы сможем найти хорошую дифференциальную маску $\mathcal{M}$ с хорошей вероятностью мы можем провести атаку на блок $м$. Если часть файла является частью избыточности, как в файлах PDF, то можно создать два разных PDF-файла с одинаковыми значениями хеш-функции. Настоящая опасность, конечно, требует большего. Изменение в $м'$ имеет преимущество для подписавшего. Это тоже можно сделать.
