Являются ли коллизии хэшей с разными размерами файлов такими же вероятными, как и файлы одного размера?

Question

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

Или, в более общем плане: каждый файл с одинаковой вероятностью создает определенный хэш, независимо от размера исходного файла?

Answer 1

Хеш-функции обычно пишутся для равномерного распределения данных по всем сегментам результатов.

Если вы предполагаете, что ваши файлы равномерно распределены по фиксированному диапазону доступных размеров, допустим, что для ваших файлов существует только 1024 (2 ^ 10) равномерно распределенных разных размера. Хранение размера файла в лучшем случае только уменьшает вероятность коллизии на количество файлов разных размеров.

Примечание: мы могли бы предположить, что это 2 ^ 32 равномерно распределенных и отличных размеров, и это все еще не меняет остальную часть математики.

Общепринято, что общая вероятность столкновения на MD5 (например) равна 1/(2^128).

Если не существует чего-то, что специально встроено в хеш-функцию, которая говорит об обратном. Для любого действительного X, такого, что вероятность P(MD5(X) == MD5(X+1)) остается такой же, как и для любых двух случайных значений {Y, Z} То есть, P(MD5(Y) == MD5(Z)) = P(MD5(X) == MD5(X+1)) = 1/(2^128) для любых значений X, Y и Z.

Объединение этого с 2 ^ 10 различных файлов означает, что, сохраняя размер файла, вы максимально получаете дополнительные 10 битов, которые указывают, отличаются ли элементы или нет (опять же, это предполагает, что ваши файлы равномерно распределены по всем значениям) .

Таким образом, в лучшем случае все, что вы делаете, - это добавление еще N байтов памяти для уникальных значений на сумму <= N байтов (никогда не может быть> N). Поэтому гораздо лучше увеличивать количество байтов, возвращаемых вашей хеш-функцией, используя что-то вроде SHA-1/2, поскольку это с большей вероятностью даст вам равномерно распределенные данные значений хеш-функции, чем сохранение размера файла.

Короче говоря, если MD5 недостаточно хорош для коллизий, используйте более сильный хеш, если более сильные хеши слишком медленные, тогда используйте быстрый хеш с низкой вероятностью коллизий, таких как MD5, а затем используйте более медленный хеш, такой как SHA-1 или SHA256, чтобы уменьшить вероятность столкновения, но если SHA256 достаточно быстр и удвоенный пробел не является проблемой, вам, вероятно, следует использовать SHA256.

Answer 2

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

Answer 3

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

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

Answer 4

Размер хеша одинаков независимо от размера исходных данных. Поскольку существует только ограниченное количество возможных хэшей, теоретически возможно, что два файла с разными размерами могут иметь одинаковый хеш. Однако , это также означает, что два файла с одинаковым размером могут иметь одинаковый хэш.

Answer 5

Весь смысл семейства криптографических хэшей (MD5, SHA-x и т. Д.) Состоит в том, чтобы сделать столкновения невероятно маловероятными. Идея состоит в том, что официальные юридические процессы готовы зависеть от того, что нецелесообразно специально создавать столкновение. Так что, на самом деле, неправильно использовать пространство и процессорное время, чтобы добавить пояс к подтяжкам этих хэшей.