Безопасно ли игнорировать возможность столкновений SHA на практике?

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

  • количество файлов
  • размер одного файла

Как далеко мы можем пойти игнорируя эту возможность, предполагая, что она равна нулю?

3 180
share hashset

3 ответа:

обычный ответ звучит так: какова вероятность того, что в течение следующей секунды на Землю упадет изгоев астероид, уничтожив цивилизацию, как мы ее знаем, и убив несколько миллиардов человек? Можно утверждать, что любое несчастливое событие с вероятностью ниже этой На самом деле не очень важно.

Если у нас есть "идеальная" хэш-функция с размером вывода n и мы p сообщения в хэш (длина отдельного сообщения не важна), затем вероятность столкновения составляет около p2/2n+1 (это приближение, которое справедливо для "малых"p, т. е. существенно меньше, чем 2n / 2). Например, с SHA-256 ( n=256) и один миллиард сообщений (p=109) тогда вероятность около 4.3*10-60.

массовый убийца космического рока происходит примерно раз в 30 в среднем миллион лет. Это приводит к вероятности возникновения такого события в следующую секунду примерно до 10-15. Это 45 на порядки более вероятно, чем столкновение SHA-256. Короче говоря, если вы находите столкновения SHA-256 страшными, то ваши приоритеты ошибочны.

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

конечно, все вышесказанное предполагает, что SHA-256 является "идеальной" хэш-функцией, что далеко не доказано. Тем не менее, SHA-256 кажется довольно надежным.

330

возможность коллизии не зависит от размера файлов, только от их количества.

Это пример парадокс дней рождения. Страница Википедии дает оценку вероятности столкновения. Если вы запустите числа, вы увидите, что все жесткие диски, когда-либо созданные на Земле, не могут содержать достаточно 1 МБ файлов, чтобы получить вероятность столкновения даже 0,01% для SHA-256.

в принципе, вы можете просто игнорировать эту возможность.

43

прежде всего,это не ноль, а очень близко к нулю.

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

также не забывайте, что вы программное обеспечение (или крошечная его часть) может быть развернуто и одновременно используется в миллионе компьютеров (некоторые крошечные встроенные микрокомпьютеры, которые почти везде в настоящее время включены). В таком случае вам нужно умножить полученную оценку на максимально возможное количество копий.

15