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

Question

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Answer 5

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

Если вы предполагаете, что ваши файлы распределены равномерно по фиксированному диапазону доступных размеров, скажем, что для ваших файлов равномерно распределены по размеру (равно 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.