Рассмотрим, что означает выражение «парадокс дня рождения»:
Защита: Предположим, что длина дайджеста равна N. Сколько сообщений и релевантных дайджестов нужно создать на стороне атакующего, чтобы найти два сообщения с одинаковыми дайджестами (происходит коллизия) с вероятностью нахождения этих двух сообщений выше 50% ?
Ответ $ c*\sqrt{N} $. Это означает, что злоумышленник должен собрать как минимум $ c*\sqrt{N} $ количество сообщений среди N сообщений, чтобы найти два одинаковых дайджеста и найти коллизию. Более четко, в $ c*\sqrt{N} $ количество сообщений, должно быть два сообщения m и $ \ острый {м} $ что H(m) = H($ \ острый {м} $), где вероятность найти эти два сообщения составляет примерно 50% (что является приемлемой вероятностью). В этой формуле $с$ является постоянной величиной, приблизительно равной 1,2, и в большинстве работ и расчетов игнорируется. Кроме того, эта статистика верна только для теоретических хеш-функций, которые спроектированы правильно и безупречны. В данном случае мы просто находим эти два сообщения только методом грубой силы, а не какими-либо другими атаками, поскольку хеш-функция безупречна и разработана на основе чистой теоретической математики.
Если мы хотим привести простой пример, поясняющий это, предположим, что U = {0,1} 128 длина дайджеста, то количество сообщений, которое атакующий должен выбрать из U, чтобы найти два одинаковых дайджеста и обнаружить коллизию (вероятность этого инцидента почти 50%), должно быть:
$$ 1.2 * \sqrt{2^{128}} \cong 1.2 * (2^{64} ) \cong 2^{64} $$
Это верхняя граница устойчивости к коллизиям, основанная на проверенном парадоксе математической вероятности, и она верна только в том случае, если разработанная хеш-функция верна теоретически и математически. Если мы хотим найти столкновения в количестве меньшем, чем $2^{64}$ сообщений, исходя из этой теории, вероятность снижается до менее 50%, другими словами, меньше вероятность найти два сообщения с одинаковыми дайджестами.
Теперь, если я хочу ответить на вопрос о «более простом методе, чем атака грубой силой», это произойдет, если мы сможем найти недостаток в конструкции хеш-функции, которую злоумышленник использует для поиска двух сообщений, которые имеют идентичные дайджесты. в нижнем ряду $ c*\sqrt{N} $ Сообщения. Как я упоминал выше, исходя из парадокса дня рождения, мы должны, по крайней мере, проверить $ c*\sqrt{N} $ количество сообщений для поиска коллизии (при таком количестве тестов вероятность найти коллизию примерно равна 50%). Однако, если в конструкции хэш-функции есть недостаток, злоумышленник использует этот недостаток и никогда не применяет грубую силу для обнаружения коллизии. Более того, здесь «более простой метод» — это тип атаки, который может быть применен к хеш-функциям, а не к атаке методом полного перебора.
Криптографы разрабатывают свои схемы на основе вычислительной безопасности, а не совершенной безопасности; то есть они доказывают безопасность своей схемы на основе вычислительных мощностей. С другой стороны, разработанные схемы без прочной математической основы, которые не могли противостоять обычным теоретическим атакам, вообще неприемлемы. В настоящее время безопасные хеш-функции вычислительно устойчивы к обычным вычислительным атакам, а их надежность математически доказана. Теоретически можно спроектировать безопасную хеш-функцию, но на практике на разработанную схему влияет множество факторов, таких как реализация.
