Являются ли коллизии хэшей с разными размерами файлов такими же вероятными, как и файлы одного размера?
Я хэширую большое количество файлов, и чтобы избежать коллизий хешей, я также сохраняю исходный размер файла - таким образом, даже если есть коллизия хешей, крайне маловероятно, что размеры файлов также будут одинаковыми. Является ли этот звук (хеш-коллизия с одинаковой вероятностью любого размера), или мне нужна другая часть информации (если коллизия, скорее всего, будет той же длины, что и оригинал).
Или, в более общем плане: каждый файл с одинаковой вероятностью создает определенный хэш, независимо от исходного размера файла?
5 ответов
Зависит от вашей хеш-функции, но, как правило, файлы одинакового размера, но разного содержимого с меньшей вероятностью будут создавать такой же хеш-код, что и файлы разного размера. Тем не менее, было бы, вероятно, проще использовать проверенный временем хэш с большим пространством (например, MD5 вместо CRC32 или SHA1 вместо MD5), чем делать ставку на собственные решения, такие как хранение размера файла.
Хеш-функции, как правило, пишутся для равномерного распределения данных по всем сегментам результатов.
Если вы предполагаете, что ваши файлы равномерно распределены по фиксированному диапазону доступных размеров, допустим, что для ваших файлов существует только 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.
Размер хеша одинаков независимо от размера исходных данных. Поскольку существует только ограниченное число возможных хэшей, теоретически возможно, что два файла с разными размерами могут иметь одинаковый хэш. Однако это означает, что также возможно, что два файла одинакового размера могут иметь одинаковый хэш.
Хэш-функции спроектированы так, что столкновение очень трудно получить, иначе они не будут эффективными.
Если у вас есть коллизия хешей, которая абсолютно невероятна, примерно 1: number_of_possible_hashes вероятность, которая ничего не говорит о размере файла.
Если вы действительно хотите быть уверены в коллизиях хэшей, вы можете рассчитать два разных хэша для одного и того же файла - это будет менее подвержено ошибкам, чем сохранение хэша + размер файла.
Весь смысл семейства криптографических хэшей (MD5, SHA-x и т. Д.) Состоит в том, чтобы сделать столкновения невероятно маловероятными. Идея состоит в том, что официальные юридические процессы готовы зависеть от того, что нецелесообразно специально создавать столкновение. Так что, на самом деле, неправильно использовать пространство и процессорное время, чтобы добавить пояс к подвескам этих хэшей.