Рейтинг:1

насколько высока вероятность возникновения хеш-коллизии в текстовых файлах?

флаг in

Просто для примера, допустим, я скачал «Приключения Тома Сойера» из Гутенберга в формате файла .txt и сохранил его на USB-накопителе.

И, как видите, USB-накопитель не является идеальным устройством для длительного хранения данных. Но если я настаиваю на его использовании, есть вероятность, что любые файлы в моем хранилище будут окончательно повреждены после долгого времени без включения питания.

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

Но проблема в том, что иногда хеш будет идентичным, даже если есть некоторые незначительные изменения, поскольку количество выходных хэшей всегда будет меньше, чем входных данных. Должен ли я беспокоиться о столкновении для моего варианта использования? А как насчет других типов файлов, включая pdf, jpg, exe, zip и т. д.? Являются ли они также уязвимыми для столкновения с хешем?

И, наконец, я знаю, что существует множество алгоритмов хеширования для одного файла от crc32 до md5, sha1 и т. д., и для моей цели (просто проверка достоверности данных), что бы вы порекомендовали и почему?

Заранее спасибо!

Рейтинг:2
флаг ng

При использовании $n$-битный хеш, вероятность того, что случайный изменение проходит незамеченным вот-вот $2^{-n}$ (для хэшей, которые даже слегка соответствуют своим целям дизайна).

Если кто-то использует эту технику один раз в секунду в течение 100 лет со 128-битным хэшем, таким как MD5, эта вероятность равна $36524\times86400\times2^{-128}\приблизительно2^{31,6-128}=2^{-96,4}$.

Мы знаем о 44 кратеры на Земле, вызванное столкновением с небесным телом, достаточно большим, чтобы нанести серьезный удар по нашей современной цивилизации, которое произошло в течение последних 2,3 млрд лет. Таким образом, вероятность разрушившего цивилизацию события в течение этих 100 лет составляет по крайней мере $44\times100/(2,3\times10^9)\приблизительно2^{-19}$ (и я настроен здесь оптимистично: рукотворное ядерное уничтожение, пожалуй, более вероятно). Таким образом, нет смысла беспокоиться о вероятности только $2^{-96.4}$.


Но в криптографии мы считаем противники которые активно пытаются победить нас. Если мы используем 128-битный хэш (например, MD5) и создаем много файлов (например, $2^{31.6}$ как указано выше, чьи хэши подходят для USB-накопителя емкостью 64 ГБ), и иметь сильных противников с такими же ресурсами, которые тратятся впустую при майнинге биткойнов¹, тогда вероятность того, что они найдут файл с таким же хэшем, как у одного из нас, становится значительной (хотя и не в этом суть). я бы побеспокоился).

Реальная и непосредственная опасность возникает, если мы предположим, что злоумышленникам удастся проникнуть в программное обеспечение, которое мы используем для сохранения наших (скажем, PDF) файлов, и мы достаточно глупы, чтобы использовать MD5 или SHA-1, чья устойчивость к коллизиям с выбранным префиксом нарушена. Теперь злоумышленники могут легко создавать файлы с теми же MD5 или SHA-1, что и у любого из наших файлов, которые выглядят именно так, как злоумышленники считают нужным при просмотре.


Для моей цели (просто проверка достоверности данных), что бы вы порекомендовали?

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

Вернемся к криптографии и ее состязательной модели: следует использовать непрерывные хэши, такие как семейства SHA-2 или SHA-3. Если не считать прорыва, которого мало кто ожидает, SHA-256 будет достаточно безопасным, по крайней мере, в течение десяти лет, SHA-512 навсегда (в человеческом масштабе), даже если мы предполагаем, что когда-либо получим Криптографически значимые квантовые компьютеры.


¹ Я говорю об общей электрической мощности и потраченных впустую интегральных схемах. Однако большая часть этого не будет предназначена для массового параллельного хэширования с помощью ASIC, как при майнинге биткойнов. Это было бы для быстрой памяти, организованной для поиска, поскольку вычисление хэшей MD5 имеет низкую стоимость по сравнению с сопоставлением их с $ 2 ^ {\ приблизительно 31,6} $ целевые хэши.

флаг in
Большое спасибо за ваш подробный ответ! Кстати, я бы не особо возражал против безопасности, потому что большинство моих файлов предназначены для справочных или развлекательных целей. Таким образом, для приведенного выше примера, если какое-либо из слов будет добавлено, удалено или заменено другим в 300-страничном романе в мягкой обложке из-за повреждения файла, вероятность того, что оно будет иметь идентичное значение хеш-функции исходному слову, ничтожно мала. 3 раза подряд или даже меньше, это правильно? Еще раз спасибо за спокойствие :) Ответ принят.
fgrieu avatar
флаг ng
@tadkov: да, с 128-битным хэшем вероятность того, что любой файл, хешируемый со скоростью 1 раз в секунду в течение 100 лет, _случайно_ будет поврежден без обнаружения, ниже (в 4000 раз), чем выигрыш Powerball три раза в трех ставках.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.