Какой алгоритм хеширования можно использовать для проверки дублированного контента?

Question

У меня есть XML-файл, в котором мне нужно определить, является ли он дубликатом.

Я либо хеширую весь xml-файл, либо для его генерации будет использоваться определенный узел xml в xml-файле.

Подходит ли для этого md5?

Или что-то еще? Скорость создания хэша также довольно важна, но гарантия создания уникального хэша для уникальных данных имеет более важное значение.

Answer 1

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

---

Обратите внимание, что хеш-функции по своей природе не могут гарантировать уникальный хеш для каждого возможного ввода.Хеш-функции имеют ограниченную длину (например: MD5 имеет длину 128 битов, поэтому возможны 2 ¹²⁸ возможных хэшей).Вы не можете отобразить потенциально бесконечный домен в конечный совместный домен, это математически невозможно.

Однако, согласно парадоксу дня рождения , шансы на столкновение в хорошей хэш-функцииравен 1 в 2 ^{n / 2} , где n - длина в битах.(например: с 128-битным MD5 это будет 2 ⁶⁴ ).Это настолько статистически незначимо, что вам не нужно беспокоиться о случайном столкновении.

Answer 2

MD5 подходит и быстро.Однако обратите внимание, что одна разница в одном символе приведет к совершенно другому MD5.

Существует небольшая вероятность того, что MD5 выдаст одинаковый хэш для разных входов.Это будет довольно редко.Таким образом, в зависимости от вашего ввода (ожидаете ли вы много похожих XML-файлов или много разных?), Когда MD5 дает вам положительное совпадение, вы можете сравнить содержимое простой строки.

Answer 3

Если кто-то может хотя бы частично изменить содержимое некоторых файлов XML, и что у кого-то есть преимущество в том, чтобы вы объявляли два файла XML (или выдержки XML) идентичными, хотя на самом деле это не так, тогда вам необходимо криптографическибезопасная хеш-функция, а именно та, которая устойчива к столкновениям .Столкновение - это пара отдельных сообщений (последовательностей байтов), которые выдают одинаковый хэш-результат - именно то, чего вы хотели бы избежать.Поскольку хеш-функция принимает входные данные длиннее своего выходного сигнала, конфликты обязательно существуют;хеш-функция считается криптографически безопасной, когда никто на самом деле не может создать такую ​​коллизию.

Если хеш-функция выдает n бит, то можно ожидать, что коллизия найдетсяпосле хеширования около 2 ^{n / 2} различных сообщений.Безопасная хеш-функция - это хеш-функция, так что не известно ни одного метода, позволяющего получить столкновение быстрее, чем это.

Если нет проблемы безопасности (то есть никто не будет активно пытаться найти столкновение, вы просто боитесь столкновенияне повезло), тогда криптографически слабые хеш-функции являются опцией, при условии, что они имеют достаточно большой вывод, так что 2 ^{n / 2} остается намного больше, чем ожидаемое числоXML-файлы вы будете сравнивать.Для n = 128 (т. Е. 2 ^{n / 2} , близких к восемнадцати миллиардам миллиардов), MD5 отлично, быстро и широко поддерживается.Вы можете исследовать MD4 , который еще слабее, но немного быстрее.Если вы хотите больший n , попробуйте SHA-1 , который предлагает 160-битные выходы (также, слабые стороны SHA-1 все еще являются теоретическими на данный момент, поэтому SHA-1 намногоменее «криптографически взломан», чем MD5).

Если у вас есть, даже потенциально, проблемы с безопасностью, тогда выберите SHA-256 .В настоящее время для этой функции не известно ни одного криптографического недостатка в отношении столкновений.Если у вас возникают проблемы с производительностью (что довольно маловероятно: на базовом ПК SHA-256 может обрабатывать более 100 мегабайт данных в секунду, поэтому есть вероятность, что синтаксический анализ XML будет значительно дороже, чем хеширование), рассмотрим SHA-512., что несколько быстрее на платформах, которые предлагают 64-битные целочисленные типы (но довольно медленно на платформах, которые этого не делают).

Обратите внимание, что все эти хеш-функции относятся к последовательностям байтов.Один перевернутый бит меняет вывод.В мире XML данный документ может быть закодирован различными способами, которые семантически идентичны, но различаются в том, что касается битов на проводе (например, é и &#233 оба представляют один и тот же символ é).Вам решать, какое понятие равенства вы хотите использовать;см канонический XML .