Важность коллизии хэш-функции

Предположим, что в некоторой хэш-функции обнаружена коллизия, такое, что H(x1) = H(x2)

Тем не менее, x1 и x2 представляют собой, по-видимому, «случайный» набор битов, которые не передают связного сообщения и не могут быть последовательно интерпретированы.

Делает ли это столкновение хэш-функцию H небезопасной? если да, то как его можно использовать, даже если известное столкновение не передает последовательного сообщения? Благодарность

Я предпочитаю думать о криптографии как об инфраструктуре. Мы должны стремиться развивать инфраструктуру, которая сводит к минимуму количество предостережений при использовании.Задача криптографии не в том, чтобы определять, что является «значащими» сообщениями в вашем приложении. Можете ли вы посмотреть на конкретное столкновение $м_1, м_2$ и с уверенностью сказать, что нет применение хеш-функции будет Когда-либо придать этим значениям $m_1$ и $m_2$?

Какую хэш-функцию вы бы предпочли использовать, с гарантией «трудно найти Любые столкновения» или с гарантией «трудно найти столкновение, кроме как иногда среди строк, которые представляют собой JPG песчанок и gzip-файлы Шекспира»? Я бы не хотел водить машину с предупреждающей наклейкой, которая гласила: «Машина может взорваться, вы едете со скоростью 88,1 мили в час с включенным левым указателем поворота и радио, настроенным на 88,1 FM», даже если бы это предупреждение было правильно узким, и я бы никогда не стал делать эти 3 вещи одновременно.

Вот почему определения криптографической безопасности считают коллизию Любые два сообщения, которые удовлетворяют $ Н (х_1) = Н (х_2) $, подделка подписи Любые сообщение является атакой, шифрование Любые открытый текст должен выглядеть неразличимым и т. д. Если вы хотите, чтобы ваша криптография использовалась, убедитесь, что вы стремитесь к гарантии безопасности, которая ставит каждый вольно.

Вторая практическая причина для беспокойства по поводу «неструктурированного» столкновения в $Ч$, заключается в том, что, когда он найден, расширение методов для поиска «структурированных» столкновений часто является вопросом времени. Например, поиск структурированных коллизий в случайной функции (используя классическую атаку коллизий Юваля) примерно такой же сложности, как и поиск неструктурированных коллизий (используя стандартный перебор и привязку к дню рождения).

H будет небезопасным тогда и только тогда, когда при заданном x1 можно будет алгоритмически получить другой x2 с тем же хэшем. Поскольку хеш-пространство намного меньше пространства данных, всегда будут потенциальные коллизии, вопрос в том, сможем ли мы их найти.

Даже если коллизия совершенно неструктурирована и возникла в результате двух совершенно независимых вычислений, она все равно будет серьезной проблемой для современной хеш-функции. В криптографических конструкциях мы обычно предполагаем, что выходные данные хеш-функции распределяются равномерно случайным образом. Для хеш-функций, таких как SHA256 для этого нет доказательств, и мы не знаем, например, даже все ли выходы возможны.

Теперь учтите, что даже для SHA256 (вероятно, самой оцененной хэш-функции всех времен) я все равно оцениваю это меньше чем $2^{90}$ выходы были рассчитаны (и большая часть этих значений отброшена). Для хеш-функции, которая равномерно и случайным образом выдает 256-битные выходные данные, чтобы вызвать коллизию в $2^{90}$ выходы Об $2^{-77}$ событие. Мы должны были бы сделать вывод, что либо SHA256 ведет себя не так, как мы надеялись, либо нам невероятно не повезло (а так не повезло никому).

Такое событие, если оно произошло, следует рассматривать как доказательство того, что SHA256 значительно меньше энтропия столкновения чем мы предполагали, и что при значительно меньшей вычислительной мощности, чем мы предполагали, люди смогут сталкивать интересные значения данных, просто добавляя случайные блоки. В таком гипотетическом случае его следует воспринимать как признак того, что с хеш-функцией что-то не так, но мы не знаем, почему.