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

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

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

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

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

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

Answer 1

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

См. Также Надежный и быстрый алгоритм контрольной суммы?

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

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

{
  CheckSum ^= Data;
}

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

Я предлагаю использовать хеш-функцию .

Answer 6

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

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

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

Answer 7

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

Answer 8

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

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