Kann dieser Prüfsummenalgorithmus verbessert werden?

Question

Wir haben ein sehr altes, nicht unterstütztes Programm, das Dateien über SMB-Freigaben kopiert. Es verfügt über einen Prüfsummenalgorithmus, um festzustellen, ob sich der Dateiinhalt vor dem Kopieren geändert hat. Der Algorithmus scheint leicht zu täuschen - wir haben gerade ein Beispiel gefunden, bei dem zwei Dateien, die bis auf eine einzige "1" identisch sind und zu einer "2" wechseln, dieselbe Prüfsumme zurückgeben. Hier ist der Algorithmus:

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

Ich bin nicht viel von einem Programmierer (Ich bin ein Sysadmin), aber ich weiß, eine XOR-basierte Prüfsumme ziemlich roh sein wird. Wie hoch ist die Wahrscheinlichkeit, dass dieser Algorithmus dieselbe Prüfsumme für zwei Dateien derselben Größe mit unterschiedlichem Inhalt zurückgibt? (Ich erwarte keine genaue Antwort, "remote" oder "ziemlich wahrscheinlich" ist in Ordnung.)

Wie könnte es verbessert werden, ohne einen enormen Leistungseinbruch?

Zuletzt, was ist los mit der fread()? Ich hatte einen kurzen Scan der Dokumentation, aber ich konnte es nicht herausfinden. Wird Data der Reihe nach auf jedes Byte der Datei gesetzt? Edit: Okay, so liest es die Datei in unsigned long (nehmen wir ein 32-Bit-Betriebssystem hier) Chunks. Was enthält jeder Chunk? Wenn der Inhalt der Datei abcd ist, was ist der Wert von Data im ersten Durchgang? Ist es (in Perl):

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

Wenn a, b und c sind große Primzahlen, diese sollten gute Ergebnisse zurück:

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

Answer 1

Sie einfach den Algorithmus unter Verwendung einer Formel wie diese verbessern könnte . Danach wird das Rotieren (nicht Verschieben!) Der Bits der Prüfsumme diese ein wenig verbessern.

Mit Primes ist dies ein ähnlicher Algorithmus wie für Linear congruential generators - es garantiert lange Zeiträume und gute Verteilung.

Answer 2

Ich scheint wie Ihr Algorithmus keine Mühe macht, mit Dateien umzugehen, die kein genaues Vielfaches von 4 Bytes groß sind. Der Rückgabewert von fread ist kein Boolescher Wert, sondern die Anzahl der tatsächlich gelesenen Bytes, die sich im Falle eines EOF von 4 unterscheiden oder wenn ein Fehler aufgetreten ist. Sie werden auf keines überprüft, aber einfach davon ausgehen, dass, wenn es nicht 0 zurückgegeben hat, Sie 4 gültige Bytes in "Daten" haben, die Ihren Hash berechnen.

Wenn Sie wirklich einen Hash verwenden möchten, würde ich mehrere Dinge empfehlen. Verwenden Sie zunächst einen einfachen kryptografischen Hash wie MD5, nicht CRC32. CRC32 ist in Ordnung, um die Datengültigkeit zu überprüfen, aber um ein Dateisystem zu überspannen und keine Kollisionen zu gewährleisten, ist es wegen des Geburtstagsparadoxons, das in den Kommentaren an anderer Stelle erwähnt wird, nicht so ein großartiges Werkzeug. Zweitens, schreibe die Funktion nicht selbst. Suchen Sie nach einer vorhandenen Implementierung. Betrachten Sie schließlich einfach rsync, um Dateien zu replizieren, anstatt eine eigene Lösung zu erstellen.

Answer 3

Das fread Bit liest in der Datei einen Block nach dem anderen. Jeder Chunk hat die Größe eines Long (in c ist das keine gut definierte Größe, aber Sie können 32 oder 64 Bits annehmen). Je nachdem, wie es gepuffert wird, ist das nicht zu schlecht. OTOH, ein größerer Chunk in ein Array zu lesen und darüber zu schleifen könnte viel schneller sein.

Answer 4

MD5 wird häufig verwendet, um die Integrität von Übertragungsdateien zu überprüfen. Quellcode ist in C++ verfügbar. Es wird allgemein als ein schneller und genauer Algorithmus angesehen.

Siehe auch Robust and fast checksum algorithm?

Answer 5

Selbst „teuer“ verschlüsselte Hash-Funktionen erfordern in der Regel mehr Iterationen erhebliche Mengen an Zeit in Anspruch nehmen. Obwohl für kryptografische Zwecke, bei denen Benutzer bewusst versuchen würden, Kollisionen zu erzeugen, nicht mehr empfohlen werden, sind Funktionen wie SHA1 und MD5 weit verbreitet und für diesen Zweck geeignet.

Wenn ein kleinerer Hash-Wert benötigt wird, ist CRC in Ordnung, aber nicht groß. Ein n -Bit CRC wird einen kleinen Bruchteil der Änderungen, die länger als n Bits sind, nicht erkennen. Angenommen, nur ein einzelner Dollarbetrag in einer Datei wird von 12.345 $ auf 34.567 $ geändert. Ein 32-Bit-CRC könnte diese Änderung verpassen.

Das Verkürzen des Ergebnisses eines längeren kryptografischen Hashs erkennt Änderungen zuverlässiger als ein CRC.

Answer 6

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

Ich denke nicht, "++ Count" viel Arbeit. Der Code entspricht

{ 
    CheckSum ^= Data; 
} 

XORing eine Sequenz von Bytes ist nicht genug. Vor allem mit Textdateien.

Ich schlage vor, eine hash function zu verwenden.

Answer 7

Ich würde vorschlagen, Sie werfen einen Blick auf Fletcher's checksum, speziell Fletcher-32, die ziemlich schnell sein sollte, und erkennen verschiedene Dinge, die die aktuelle XOR-Kette nicht würde.

Answer 8

SHA-1 und (neuerdings SHA-2) bieten hervorragende Hash-Funktionen und ich glaube, MD5 aufgrund der besseren Hashing-Eigenschaften langsam verdrängt. Alle von ihnen (md2, sha, etc ...) haben effiziente Implementierungen und geben einen Hash eines Puffers zurück, der mehrere Zeichen lang ist (obwohl immer eine feste Länge). sind nachweisbar zuverlässiger als ein Hash auf eine ganze Zahl zu reduzieren. Wenn ich meine Fahrer hätte, würde ich SHA-2 benutzen. Folgen Sie this link für Bibliotheken, die SHA-Prüfsummen implementieren.

Wenn Sie nicht in diesen Bibliotheken kompilieren möchten, hat Linux (und wahrscheinlich Cygwin) die folgenden ausführbaren Dateien: md5sum, sha1sum, sha224sum, sha256sum, sha384sum, sha512sum; zu dem Sie Ihre Datei bereitstellen können und die Prüfsumme als hexadezimale Zeichenfolge ausdrucken. können Sie popen verwenden, um diese Programme auszuführen - mit etwas wie folgt aus:

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

Offensichtlich läuft ziemlich viel langsamer, aber macht für einen nützlichen ersten Durchgang. Wenn die Geschwindigkeit ein Problem ist, würde ich erwarten, dass alle diese Algorithmen etwa so schnell laufen, dass ein Hash ohne Hash erzeugt wird, da Hash-Operationen wie diese und I/O-Vorgänge (Speicher- und Festplattenzugriffe Engpässe) sind . Perl und Python kommen auch mit Implementierungen von MD5 SHA1 und SHA2 und werden wahrscheinlich so schnell wie in C/C++ laufen.