Более быстрая альтернатива MD5?

Question

Я работаю над программой, которая ищет целые диски для данного файла. В данный момент я вычисляю хеш MD5 для известного файла, а затем рекурсивно сканирую все файлы в поисках совпадения.

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

Весь код в C #.

Спасибо.

Обновление

Я читал, что даже MD5 может быть довольно быстрым и что дисковый ввод-вывод должен быть ограничивающим фактором. Это приводит меня к мысли, что мой код может быть неоптимальным. Есть ли проблемы с этим подходом?

        MD5 md5 = MD5.Create();
        StringBuilder sb = new StringBuilder();
        try
        {
            using (FileStream fs = File.Open(fileName, FileMode.Open, FileAccess.Read))
            {
                foreach (byte b in md5.ComputeHash(fs))
                    sb.Append(b.ToString("X2"));
            }
            return sb.ToString();
        }
        catch (Exception)
        {
            return "";
        }

Answer 1

Я надеюсь, что вы проверяете соответствие MD5, только если размер файла уже совпадает.

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

Конечно, все это предполагает, что вы просто ищете решение о совпадении / совпадении для определенного файла.

Answer 2

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

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

Answer 3

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

Answer 4

Существует одна небольшая проблема с использованием MD5 для сравнения файлов: существуют известные пары файлов, которые отличаются , но имеют то же самое MD5.

Это означает, что вы можете использовать MD5, чтобы определить, являются ли файлы разными (если MD5 отличается, файлы должны отличаться), но вы не можете использовать MD5, чтобы определить, являются ли файлы равно (если файлы равны, MD5 должен быть одинаковым, но если MD5 равен, файлы могут или не могут быть равны).

Вы должны либо использовать хеш-функцию, которая еще не была нарушена (например, SHA-1), либо (как упоминалось в @SoapBox) использовать MD5 только как быстрый способ найти кандидатов для более глубокого сравнения.

Ссылки:

• http://www.win.tue.nl/hashclash/SoftIntCodeSign/

Answer 5

просто прочитать файл линейно? Кажется довольно бессмысленным читать весь файл, вычислять хэш md5, а затем сравнивать хеш.

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

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

Я что-то здесь упускаю? Что хешинг покупает в этом случае?

Answer 6

Использовать MD5CryptoServiceProvider и BufferedStream

        using (FileStream stream = File.OpenRead(filePath))
        {
            using (var bufferedStream = new BufferedStream(stream, 1024 * 32))
            {
                var sha = new MD5CryptoServiceProvider();
                byte[] checksum = sha.ComputeHash(bufferedStream);
                return BitConverter.ToString(checksum).Replace("-", String.Empty);
            }
        }