Можно ли улучшить алгоритм контрольной суммы?

Question

У нас есть очень старая, неподдерживаемая программа, которая копирует файлы через общие ресурсы SMB. У этого есть алгоритм контрольной суммы, чтобы определить, изменилось ли содержимое файла перед копированием. Алгоритм кажется легко обманутым - мы только что нашли пример, когда два файла, идентичные, за исключением одного «1», меняющегося на «2», возвращают ту же контрольную сумму. Вот алгоритм:

unsigned long GetFileCheckSum(CString PathFilename) 
{ 
     FILE* File; 
     unsigned long CheckSum = 0; 
     unsigned long Data = 0; 
     unsigned long Count = 0; 

     if ((File = fopen(PathFilename, "rb")) != NULL) 
     { 
       while (fread(&Data, 1, sizeof(unsigned long), File) != FALSE) 
       { 
         CheckSum ^= Data + ++Count; 
         Data = 0; 
       } 
       fclose(File); 
     } 
     return CheckSum; 
} 

Я не так много программиста (я сисадмин), но я знаю, исключающее на основе контрольной суммы будет довольно сырой. Какова вероятность того, что этот алгоритм вернет ту же контрольную сумму для двух файлов одного размера с другим содержимым? (Я не ожидаю точного ответа, «удаленный» или «вполне вероятный» в порядке.)

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

И наконец, что происходит с fread()? Я быстро просмотрел документацию, но я не мог понять. Устанавливается ли Data каждому байту файла? Редактировать: хорошо, поэтому он читает файл в unsigned long (предположим, что здесь 32-битная ОС) куски. Что содержит каждый кусок? Если содержимое файла abcd, то каково значение Data на первом проходе? Является ли это (в Perl):

(ord('a') << 24) & (ord('b') << 16) & (ord('c') << 8) & ord('d') 

Answer 1

Вы можете легко улучшить алгоритм, используя формулу, как это одна:

Checksum = (Checksum * a + Data * b) + c; 

Если, б и большие простые числа, это должно возвращать хорошие результаты , После этого вращение (не сдвигание!) Бит контрольной суммы еще немного улучшит его.

Использование простых чисел, это аналогичный алгоритм, используемый для Linear congruential generators - он гарантирует длительные периоды и хорошее распределение.

Answer 2

Кажется, что ваш алгоритм не прилагает никаких усилий для работы с файлами, которые не являются точными кратными 4 байтам. Возвращаемое значение fread не является логическим, а количество фактически прочитанных байтов, которое будет отличаться от 4 в случае EOF или если произошла ошибка. Вы не проверяетесь ни на одно, но просто считаете, что если он не вернул 0, у вас есть 4 действительных байта в «данных», которые будут вычислять ваш хэш.

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

Answer 3

fread бит читает в файле по одному куску за раз. Каждый кусок - это размер длинного (в c это не определенный размер, но вы можете принять 32 или 64 бита). В зависимости от того, как он буферизуется, это может быть не плохо. OTOH, читая больший кусок в массив и зацикливаясь на нем, может быть намного быстрее.

Answer 4

MD5 обычно используется для проверки целостности передаваемых файлов. Исходный код легко доступен в C++. Он широко считается быстрым и точным алгоритмом.

Смотрите также Robust and fast checksum algorithm?

Answer 5

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

Если требуется меньшее значение хэша, CRC в порядке, но не очень. A n -бит CRC не сможет обнаружить небольшую часть изменений, длина которых больше n бит. Например, предположим, что только одна долларовая сумма в файле изменилась с 12 345 до 34 567 долларов. 32-битный CRC может пропустить это изменение.

Усечение результата более длинного криптографического хеша будет определять изменения более надежно, чем CRC.

Answer 6

{ 
    CheckSum ^= Data + ++Count; 
    Data = 0; 
} 

Я не думаю, что «++ Count» много работает. Код эквивалентен с

{ 
    CheckSum ^= Data; 
} 

XORing последовательность байтов недостаточно. Особенно с текстовыми файлами.

Предлагаю использовать hash function.

Answer 7

Я предлагаю вам взглянуть на Fletcher's checksum, в частности, fletcher-32, который должен быть довольно быстрым и обнаруживать различные вещи, которые не существовала бы в текущей цепочке XOR.

Answer 8

SHA-1 и (совсем недавно SHA-2) обеспечивают отличные функции хеширования, и я считаю, что медленно вытесняет MD5 из-за лучших свойств хэширования. Все из них (md2, sha и т. Д.) Имеют эффективные реализации и возвращают хэш буфера длиной несколько символов (хотя всегда фиксированная длина). доказуемо более надежны, чем сокращение хеша до целого числа. Если бы у меня были мои барабанщики, я бы использовал SHA-2. Следуйте за this link для библиотек, которые реализуют контрольные суммы SHA.

Если вы не хотите компилировать в этих библиотеках, Linux (и, возможно, cygwin) имеет следующие исполняемые файлы: md5sum, sha1sum, sha224sum, sha256sum, sha384sum, sha512sum; к которому вы можете предоставить свой файл, и они распечатывают контрольную сумму в виде шестнадцатеричной строки. Вы можете использовать POPEN для выполнения этих программ - с чем-то вроде этого:

const int maxBuf=1024; 
char buf[maxBuf]; 
FILE* f = popen("sha224sum myfile", "w"); 
int bytesRead = f.read(buf, maxBuf); 
fclose(f); 

Очевидно, что это будет работать довольно много медленнее, но делает для полезного первого прохода. Если скорость является проблемой, учитывая, что такие операции хэширования файлов, как это, и привязка ввода-вывода (память и доступ к диску будут вам узкими местами), я ожидал бы, что все эти алгоритмы будут выполняться так же быстро, как и для unsigned int , Perl и Python также поставляются с реализациями MD5 SHA1 и SHA2 и, вероятно, будут работать так же быстро, как в C/C++.