Я слышал, что при создании хэша возможно, что если используются небольшие файлы или количества данных, получаемый хэш, скорее всего, пострадает от столкновения. Если это так, существует ли минимальное "безопасное" количество данных, которое должно использоваться для обеспечения того, чтобы этого не произошло?
Я думаю, этот вопрос можно было бы также сформулировать так:
Каков минимальный объем данных, которые можно безопасно и безопасно испортить?
Хеш-функция принимает входы произвольной (или, по крайней мере, очень высокой) длины и производит выход фиксированной длины. Есть более возможные входные данные, чем возможные выходы, поэтому столкновения должны существовать. Весь смысл безопасной хеш-функции состоит в том, что она "устойчива к столкновению", а это означает, что, хотя столкновения должны математически существовать, очень сложно их вычислить. Таким образом, для SHA-256 и SHA-512 не существует известных столкновений, и наиболее известные методы их вычисления (делая это специально) настолько смехотворно дороги, что они не будут применяться в ближайшее время (весь федеральный бюджет США для век купил бы только смехотворно небольшую часть задачи).
Итак, если это невозможно осуществить реалистично, вы можете ожидать, что не ударите столкновение (неудачную) удачу.
Кроме того, если вы ограничиваете себя очень короткими входами, есть вероятность, что столкновения вообще нет. Например, если вы считаете 12-байтовые входы: существует 2 96 возможных последовательностей из 12 байтов. Это огромное (больше, чем можно перечислить с сегодняшней технологией). Тем не менее, SHA-256 будет отображать каждый вход в 256-битное значение, то есть значения в гораздо более широком пространстве (размером 2 256). Мы не можем доказать это формально, но есть вероятность, что все эти хеш-значения 2 96 отличаются друг от друга. Обратите внимание, что это не имеет практического значения: нет никакой измеримой разницы между не обнаруживанием столкновения, потому что его нет, и не обнаруживается столкновение, потому что крайне маловероятно поразить его.
Просто, чтобы проиллюстрировать, как низкие риски столкновения с SHA-256: рассмотрите свои риски из-за того, что вас избила горилла, убежавшая из локального зоопарка или частного владельца. Вряд ли? Да, но это все равно может случиться: кажется, что горилла скрылась от того же зоопарка в 2010 году. Предполагая, что каждые шесть лет на всей Земле (не только в районе Далласа) есть только одна неистовая горилла, и вы оказались неудачливым парнем, который находится на его пути, из человеческого населения в 6,5 миллиарда человек, тогда риски тяжких -босно-вред-на-горилла можно оценить примерно в 1 в 2 43,7 в день. Теперь возьмите 10 тысяч ПК и попросите их найти столкновение для SHA-256. Шансы попасть в столкновение близки к 1 в 2 75 в день - более чем на миллиард меньше вероятностей, чем у гневной обезьяны. Вывод состоит в том, что, если вы боитесь столкновения SHA-256, но не держите с собой заряженное дробовик во все времена, вы неправильно ставите свои приоритеты. Кроме того, не связывайтесь с Техасом.
Нет, длина сообщения не влияет на вероятность столкновения.
Если это так, алгоритм разбивается.
Вы можете попробовать самостоятельно, запустив SHA для всех однобайтовых входов, а затем для всех двухбайтовых входов и т.д. и посмотрите, получилось ли вы столкновение. Наверное, нет, потому что никто никогда не нашел столкновения для SHA-256 или SHA-512 (или, по крайней мере, они не скрывали от Википедии)
Нет минимального размера ввода. Алгоритм SHA-256 является фактически случайным отображением, и вероятность столкновения не зависит от длины ввода. Даже 1-битный вход "безопасен".
Обратите внимание, что вход дополнен до 512 бит (64 байта) для SHA-256 (кратное 1024 для SHA-512). Принимая 12-байтовый ввод (как Томас использовал в своем примере), при использовании SHA-256 существует 2 ^ 96 возможных последовательностей длиной 64 байта.
В качестве примера, 12-байтовый ввод Hello There! (0x48656c6c6f20546865726521) будет дополняться одним битом, за которым следует 351 нулевой бит, за которым следует 64-битное представление длины ввода в битах, которое составляет 0x0000000000000060, чтобы сформировать 512-битное заполненное сообщение. Это 512-битное сообщение используется как вход для вычисления хэша.
Более подробную информацию можно найти в RFC: 4634 "US Secure Hash Algorithms (SHA и HMAC-SHA)", http://www.ietf.org/rfc/rfc4634.txt
. Хэш имеет длину 256 бит, есть столкновение для чего-либо длиннее 256 бит.
Вы не можете сжимать что-то в меньшую вещь, не имея столкновений, свою бросающую вызов математику.
Да, из-за алгоритма и 2 к силе 256 существует много разных хэшей, но они не являются беспорядочными, что невозможно.
В значительной степени зависит от вашего приложения: если вы просто хэшировали строки "ДА" и "НЕТ" для отправки по сети, чтобы указать, следует ли мне дать кредит в размере 100 000 долларов, это будет довольно большой провал - домен ответов не может быть настолько большим, чтобы кто-то мог легко проверить наблюдаемые хэши на проводе на базе данных хэш-выходов "малый вход".
Если вы должны были указать дату, время, мое имя, мой идентификатор налога, запрошенную сумму, количество хэшируемых данных, вероятно, не будет значительным, но вероятность того, что эти данные находятся в предварительно вычисленных хеш-таблицах, довольно тонкий.
Но я не знаю ни одного исследования, чтобы указать вам на мои инстинкты. К сожалению.