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

210

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

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

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

hash sha Христо Христов
источник

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

Моджуба

Да, в этом случае, если вы сравниваете размеры файлов, вероятность резко уменьшается. Вы также можете использовать два алгоритма хеширования и объединить результаты. Тогда вероятность столкновения обоих одновременно уменьшается еще больше. Но вопрос в том, насколько «достаточно» безопасно? Может быть, нам нужны формула и цифры.

Христо Христов

@ Христо Христов: если мы предположим, что хеш-ключ является псевдослучайным числом (что теоретически правильно), то один миллиард 128-битных ключей дает вероятность коллизии 2,9 * 10 ^ -30. Вы даже не можете назвать это «миниатюрным», это меньше, чем это;)

Моджуба

@mojuba: еще лучше, он спрашивает о 256-битном хэше.

Майкл Боргвардт

FWIW: система контроля версий GIT идентифицирует файлы по их содержанию SHA.

snemarch

Ответы:

385

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

Если у нас есть «идеальная» хэш - функция с выходными размером п , и мы имеем р сообщения в хэш (индивидуальная длина сообщения не имеет значения), то вероятность столкновения составляет около р ² /2 ^{п + 1} (это приближение , которое действителен для «малого» р , то есть существенно меньше, чем 2 ^{н / 2} ). Например, с SHA-256 ( n = 256 ) и одного миллиарда сообщений ( p = 10 ⁹ ) вероятность составляет около 4,3 * 10 ^-60. .

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

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

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

Томас Порнин
источник

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

Христо Христов

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

Роман Старков

foxnews.com/science/2013/02/11/… Я бы начал думать о SHA512.

Дастин Опря

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

AaronLS

Извините, вам не хватает так называемого «парадокса дня рождения». Лучше взгляните на «красивый стол», он не работает так, как вы думаете. Для цифр, которые я привожу в этой таблице, это будет значение «10 ^ 9» в столбце с надписью «4.3 * 10 ^ -60» и строке «128 бит» (но таблица не опускается ниже 10 ^ -18 ).

Томас Порнин

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

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

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

Майкл Боргвардт
источник

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

резкий сигнал

@sharptooth: нет, я не искажаю ситуацию. Вероятность того, что вы и все, кого вы знаете, погибнут в результате дорожно-транспортного происшествия в один и тот же день, очень мала, но это все же может произойти (и намного выше, чем при столкновении SHA-256). И все же вы игнорируете эту возможность.

Майкл Боргвардт

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

Майкл Боргвардт

@sharptooth: Нет, шансы не увеличиваются значительно, потому что число все еще абсолютно невелико из-за размера хеш-пространства SHA-256. Это единственное, что вы не учитываете должным образом - все факторы должны быть взвешены по их фактической величине, а не в равной степени. Если бы вы генерировали один миллиард хешей в секунду для каждого человека на Земле и делали это в течение тысячи лет, у вас все равно будет меньше 1% вероятности столкновения.

Майкл Боргвардт

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

Кристоф

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

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

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

Sharptooth
источник

... не по количеству копий, а по количеству наборов данных.

Андреас Шпиндлер

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

Дирк Бестер

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

Крис Миддлтон

'0' имеет свою площадь

Green Tree

@GreenTree То, на что вы ссылались, - это умышленное создание столкновений.

Sharp