Нет, нарушение свойства коллизии SHA-256 не требует каких-либо близких к $2^{128}$ пространство. Мы знаем, как показать столкновение в любом $n$-битный хэш $Ч$ с $\mathcal O(2^{n/2})$ хеш-оценки и $\mathcal O(n)$ пространство.
Самый простой подходящий способ Нахождение цикла Флойда, который будет демонстрировать с ненулевой вероятностью два различных $n$битовые строки $г$ и $s$ с $Ч(г)=Ч(с)$, на орбите заданная начальная точка $t$ при повторении $Ч$
- $m\gets\lceil\,2^{n/2+1}\,\rceil$ (увеличение $+1$ уменьшает количество неудач).
- $и\получает Н(т)$ .
- $ г \ получает ты $; $s\получает H(u)$ .
- пока $r\ne s$ :Â (найти цикл)
- если $м=0$ затем остановка в отказе (длинная орбита, редко).
- $m\получает m-1$ .
- $r\получает H(r)$; $s\получает H(H(s))$ .
- если $т=с$ то останавливаться в неудаче($t$ в цикле, исчезающе редко).
- $s\получает H(s)$ .
- пока $r\ne s$ :Â (смещение $u$ за один цикл)
- пока $t\ne u$:Â (найти столкновение)
- $ г \ получает т $; $s\получает тебя$ .
- $т\получает Н(т)$; $и\получает Н(и)$ .
- вывод $(р,с)$ и остановиться на успехе.
Попробуйте онлайн! за коллизию 24-битного хеша (первый $к=3$ байт SHA-256). Пожалуйста, будьте любезны запустить этот код Python на вашем компьютере, если вы увеличиваете $к$.
В методе используется то, что орбита $t$, определяемый как $u$ достигается повторением $и\получает Н(и)$ начиная с $и=т$, имеет тенденцию циклироваться в пределах $\mathcal\Тета(2^{n/2})$ шаги. Алгоритм обнаруживает, что цикл достигнут, находит $u$ через столько же шагов от $t$ в качестве длины цикла, то где вводится цикл, что приводит к столкновению. Можно показать, что для случайной функции $H:\{0,1\}^*\mapsto\{0,1\}^n$ и кроме очень мелких $n$, вероятность успеха этого алгоритма из любой начальной точки $t$ по крайней мере $3/4$ (отказы из-за слишком длинной орбиты $t$, или когда $t$ принадлежит циклу).
В случае сбоя часто бывает достаточно перезапуститься с другой случайной точки.Это обычно хорошо работает для обычных криптографических хэшей. $Ч$, но даже для них может случиться так, что большинство начальных точек приводят к слишком большому циклу, который невозможно найти. В общем случае мы хотим перейти к использованию алгоритма с $H'$ определяется $Н'(х)=Н(F(х))$ для подходящей случайной эффективно вычислимой и обратимой инъекции $F$ выбирается в начале алгоритма. Это так демонстрирует столкновение для $H'$ использование алгоритма демонстрирует коллизию для $Ч$, но $H'$ может иметь различную структуру цикла. Для большинства $n$-битный хэш $Ч$ подходит для криптографического использования, $F$ может быть XOR с фиксированным $n$битовая строка или добавление фиксированного префикса и/или суффикса. Это не показано в приведенном выше псевдокоде и связанном коде Python.
Можно распределить работу на множество машин, работающих параллельно, каждая с небольшим объемом памяти, умеренным обменом данными и умеренной дополнительной работой. См. Пола С. ван Оршота и Майкла Дж. Винера, Параллельный поиск столкновений с помощью криптоаналитических приложений, в Журнал криптологии, 1999 г..
