Самый быстрый способ рассчитать хэш файла?

Question

В базе данных будет храниться множество файлов, и мне нужно, чтобы хеши файлов были уникальными, чтобы определить, что файл не был изменен. (В общем, будет использоваться в качестве компонента Windows Personal Firewall)

Answer 1

Это, конечно же, невозможно вообще. Многие люди все еще используют хэширование для этой цели, а MD5 - популярный алгоритм, который дает 128-битную «подпись» для файла с высокой вероятностью изменения при изменении содержимого файла.

В общем случае вам нужно посмотреть каждый бит файла, чтобы включить его в хэш, и производительность, вероятно, будет ограничена I/O. Это последовательная развертка по всем данным в файле, обновляющая состояние любого алгоритма хеширования, который вы используете для каждого нового байта. На современном процессоре последняя будет быстрее, чем первая. This rather old analysis показывает около ~ 45 МБ/с на процессоре Pentium 90 МГц.

Answer 2

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

Существует успешная атака на алгоритм MD5, который позволяет найти другое сообщение, которое создает такой же хеш с относительно небольшой работой (по сравнению с грубой силой). Эта атака , использованная для, не имеет реального подшипника, например. когда MD5 использовался для хеш-паролей или таких. В то же время были обнаружены новые атаки, поэтому и MD5, и SHA-1 можно хэшировать/сталкиваться с ужасной скоростью, а взломать все базы данных «правильно соленых» и однодольных паролей пользователей с этими «пожилыми» хэшами не только полностью выполнимо, но уже продемонстрировано.
Тем не менее, в конкретном приложении «убедитесь, что этот файл не был взломан», такой тип атаки всегда был проблемой, не только недавно. MD5 вполне безопасно обнаруживает небольшую ошибку или модификацию, но вредоносное ПО, пытающееся обойти ваш личный файловый сервер, скорее всего может обойти всю вашу безопасность, обнаружив столкновение зараженного двоичного файла, чтобы хэш совпадал с оригиналом.

Вы должны использовать SHA-256 для этого случая [Update: в то же время, SHA-3 выходит, и пока я лично не согласен с выбором NIST в победителя (или неясные критерии для правящей из очень хороших круглых 2 кандидатов), это гораздо безопаснее выбор для использования SHA-3 (Keccak) или, альтернативно, одного из финалистов SHA-3. Все финалисты были тщательно разработаны опытными командами, были тщательно проанализированы, и до сих пор ни у кого нет реалистичной атаки или известной проблемы, которая могла бы привести к реалистичной атаке, и все они тоже имеют «больше бит» (который сам по себе не означает многого, но больше бит не болит)].

Кроме того, не забудьте сохранить длину файла в дополнение к хешу, это значительно упрочит даже плохой хеш по невыгодной цене. Если можно, вычислите два разных хэша. Это much для злоумышленника легко найти сообщение, которое вызывает коллизию на , а не нахожу сообщение, которое вызывает коллизию и имеет точно такую ​​же длину, или даже сообщение, которое сталкивается на двух разных хэшей и имеет одинаковую длину.
Поскольку пропускная способность (как диск, так и память) является неотрицательным фактором при вычислении хэша, возможно даже, что вычисление одного хеша или двух хэшей одновременно выполняется со сравнимой скоростью.
Я наблюдал такой эффект при вычислении CRC и последующем шифровании тех же блоков блочным шифрованием. Независимо от того, вычислялся ли CRC, разница в общей продолжительности работы составляла менее 1%, поэтому в основном это была бесплатная операция.

Если вы считаете, что у вас есть веская причина не использовать общеизвестный стандартный хэш (ограничения производительности?), Вы можете создать собственный безопасный хеш. Используя конструкцию Merkle-Damgård (или совсем недавно HAIFA), вы можете превратить любой защищенный блочный шифр в безопасную хэш-функцию. Например, зашифруйте каждый входной блок с помощью AES с помощью фиксированного ключа, а xor - выход в следующий блок, прежде чем шифровать его. Результат после последнего блока - ваше значение хеша.

Хотя «создать свой собственный», как правило, не очень хорошая идея, в этом случае действительно могут быть веские причины, так как AES быстро и поддерживается аппаратными средствами в самых последних процессорах. На моей машине AES работает со скоростью примерно 130 МБ/с. На i7 (у которого есть аппаратная поддержка), он сообщает около 570 МБ/с в Интернете.

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

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