При изучении такой проблемы криптографы уподобляют криптографический хэш $Ч$ к случайная функция или же случайный оракул (или же случайное отображение хотя это немного устарело) это повторяется. Вероятности вычисляются по набору всех возможных хэшей. Это приближение, но если бы фактические результаты заметно отличались, это был бы способ отличить хэш от случайной функции, таким образом, разрыв хеша с современными определениями. Следовательно, указанное приближение является удовлетворительным и лучшим, что может быть для непрерывного криптографического хэша.
Будут ли короткие циклы?
Вероятно, и тем более, что мы ослабляем определение короткого. Но (за исключением очень маленьких хэшей) маловероятно, что короткий цикл будет достигнут из случайной начальной точки. $А$; и (для стандартных криптографических хэшей с достаточно большим выходом, чтобы они были устойчивыми к коллизиям) маловероятно, что мы могли бы продемонстрировать какой-либо цикл, независимо от его размера.
Существуют ли значения $А$ такой, что $Ч(А)=А$ (цикл 1)
Если целевой набор хеша имеет размер $n$ (куда $n=2^b$ для $b$-битный хеш, например. $n=2^{256}$ для SHA-256), то вероятность существования цикла размера 1 легко вычисляется как дополнение к вероятности того, что ни один из $n$ указывает хэши на себя, т.е. $p_1(n)=1-(1-1/n)^n$. Это начинается с $p_1(1)=1$, $p_1(2)=3/4=0,75$, $p_1(3)=19/27\приблизительно 0,7037$, и $p_1$ быстро сходится к $1-1/е\ок.0,6321$.
Таким образом, существует вероятность> 63,2%, что существует цикл размера 1 в данном криптографическом хеше, таком как SHA-256, SHA-384 или SHA-512. И мы не можем сказать лучше ни для одного из этих хэшей.
Я не знаю, как правильно сделать то же самое для циклов размера 2, но не сомневаюсь, что это осуществимо, и вероятность значительна для $n\ge2$.
Можно вычислить ожидаемое значение многих характеристик циклов для итерированной случайной функции/хэша. В частности, для больших $n$, ожидаемое количество шагов до достижения предыдущего значения, начиная со случайной точки, равно $\приблизительно\sqrt{\pi\,n/2}$, а ожидаемая длина достигнутого цикла вдвое меньше. Классический пример - Филипп Флажоле и Эндрю М. Одлызко. Статистика случайного сопоставления, в разбирательства Eurocrypt 1989, и Отчет об исследовании RR-1114, INRIA, 1989 г..
Есть ли способ доказать, что для данного хеша таких циклов не существует, или установить нижнюю границу кратчайшего цикла.
Нет, для неразорванного криптографического хэша достаточно большого выходного размера, который устойчив к коллизиям (т. е. $\кв.п$ настолько велико, что это количество хэшей не может быть вычислено); скажем, любой непрерывный хеш 256-бит или шире. Что касается части вопроса, можно ли доказать, что такого цикла не существует, нам даже нужно вычислить $n$ хэши (до последнего мы не можем быть уверены, что нет цикла размером 1), поэтому подойдет любой неразрывный хеш 128-бит или шире.
Так как же (повторяющаяся конструкция Дугласа Хофштадтера) связана с криптографией?
Похожая техника используется при атаке на некоторые криптосистемы. Мы создаем функцию, итерируем ее до тех пор, пока не найдем цикл (который, таким образом, короткий, иначе мы не смогли бы его найти), и точка входа в цикл дает коллизию, и коллизия решает проблему, потому что функция была построена с этим явным цель. Это сердце Ро Полларда метод решения проблемы дискретного логарифма, который является лучшей теоретической атакой, которую мы имеем для этой проблемы в некоторых группах, используемых в криптографии.
Обратите внимание, что ни функция, описанная выше, ни функция, созданная Дугласом Хофштадтером, не представляют собой безопасный криптографический хэш. Это потому, что мы не можем найти цикл и решить проблему под рукой.
