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

Question

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

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

Весь код находится на C#.

спасибо.

Update

Я читал, что даже 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 (или какого-либо другого произвольного, но достаточно маленького числа) и убедиться, что они совпадают, прежде чем работать со всем файлом.

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

Answer 2

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

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

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

Я что-то упустил? Что вы хотите купить в этом случае?

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 и, наконец, байтовое сравнение всего файла, если MD5 соответствовал, чтобы гарантировать, что содержимое было одинаковым.

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); 
      } 
     }