Wie überprüft man die Identität großer Dateien, wenn das Hashing an die CPU gebunden ist?

7

Für kleine Dateien ist Hashing nur in Ordnung, aber bei großen kann man leicht feststellen, dass md5sumdie CPU gebunden ist. Gibt es einen Hashing-Algorithmus, der auf mehrere Kerne skaliert werden kann? Problemumgehungen? Ideen? Etwas? :) :)

poige
quelle
1
Huges Ones ist Plural und kann auf mehrere Kerne skaliert werden, indem mehr als eine Datei gleichzeitig gehasht wird. Eine Möglichkeit, dies in der Shell zu tun, ist die Verwendung von GNU Parallel
Brian
Nach meiner Erfahrung mit Hashing ist gebundenes Festplatten-E / A. Zumindest für den Desktop. Außerdem können bei großen Aufgaben normalerweise viele Dateien gehasht werden. So können einige Dateien parallel gehasht werden.
mmv-ru
Haben Sie versucht, fciv.exe in Windows zu vergleichen, wenn es besser für Multicore-CPUs geeignet ist? ( support.microsoft.com/en-ca/kb/841290 )
yagmoth555
@ yagmoth555, nein. Ich benutze selten Windows, meistens benutze ich es nicht, würde ich sagen. Aus der Beschreibung geht hervor, dass es unwahrscheinlich ist, dass es auf SMP skaliert.
Poige

Antworten:

14

Meine derzeit beste Lösung ist:

parallel --block=512M --pipepart -a …HUGEFILE… --progress --recend '' \ -k -j …NUMofProcessesSay4… md5sum | md5sum

- Es sollte angemerkt werden, dass:

  1. Der resultierende md5-Hash ist nicht Teil der Datei, sondern der md5-Teile, aber Sie können trotzdem vergleichen, ob das Replikat mit dem Ursprung identisch ist
  2. Es funktioniert auch nicht sehr gut, insbesondere wenn Sie pipeals Eingabe keine Datei verwenden
  3. parallel‚s , --pipepartwie ich herausgefunden habe keine Unterstützung für Festplattenpartitionen

Also würde ich gerne auch andere Wege hören.

poige
quelle
3
Die Git-Version von GNU Parallel unterstützt jetzt Blockgeräte (zumindest unter GNU / Linux). Danke für die Idee.
Ole Tange
Dies hätte eher als Teil der Frage als als Antwort gestellt werden sollen.
mc0e
4

Leider ist MD5 ein linearer Prozess, bei dem sein Zustand von allen vorherigen Eingaben abhängt. Mit anderen Worten, Sie können es nicht wirklich parallelisieren. Außerdem sind mir keine echten Hash-Algen bekannt, die nicht auf diese Weise funktionieren.

Was Sie tun können (und basierend auf Ihrer Antwort, die Sie tun), ist, die Quelldateien zu teilen und gleichzeitig die md5sum jedes Chunks zu berechnen.

Wenn Sie das nicht können / wollen, mussten Sie eine schnellere Hash-Funktion wie xxHash , CityHash oder SpookyHash verwenden

Andere Idee (möglicherweise gilt dies für Ihre beabsichtigte Verwendung): Wenn Sie etwas schnelleres als MD5 benötigen (wenn auch mit einem Thread), können Sie CRC32 (das durch neuere CPUs hardwarebeschleunigt wird) für einen ersten schnellen Durchgang verwenden und auf MD5 zurückgreifen / SHA1 für einen zweiten Durchgang an scheinbar identischen Dateien.

Shodanshok
quelle
Der wertvollste Teil Ihrer Antwort (andere wiederholen sich nur langweilig) ist die Liste der möglicherweise schnelleren Hashes. Trotzdem danke.
Poige
Übrigens
poige
@poige Hast du die anderen Kommentare in dem von dir verlinkten Thread gelesen? Im Zusammenhang mit einem Hashing mit einem Eingang kann MD5 nicht parallelisiert werden, einfach weil es sich um einen linearen Prozess handelt (dh der aktuelle Zustand hängt von vorherigen Eingängen ab).
Shodanshok
Ich werde dies nicht als richtige Antwort betrachten. ;-P
poige
@shodanshok Das Problem beim zweiten Ansatz ist, dass für einen gültigen Abgleich eines großen Verzeichnisses mit vielen großen Dateien, wenn alle Dateien identisch sind, Sie viel Overhead hinzufügen und immer noch md5sum für jede Datei ausführen.
Jedi
2

Es gibt so gut wie kein Umgehen bei der Verarbeitung der gesamten Datei. MD4 oder CRC32 sind wahrscheinlich die besten Wetten für einen weit verbreiteten und schnellen Algorithmus (obwohl CRC32 weitaus weniger effektiv sein wird als MD4).

Das Testen verschiedener Implementierungen des Algorithmus Ihrer Wahl hilft dabei. Wenn Sie eine gut getestete asm-Implementierung finden, wird dies wahrscheinlich die Leistung der C / C ++ - Cousins ​​verbessern.

Wenn Sie sich nicht wirklich für die Interoperabilität interessieren, können Sie das Hashing über mehrere Kerne hinweg problemlos durchführen, indem Sie die Datei in Blöcke aufteilen (muss nicht auf der Festplatte erfolgen, sondern nur von bestimmten Offsets lesen) und jeden Block separat verarbeiten (Dies führt jedoch zu einem ernsthaften Festplatten-Thrashing, was die Leistung beeinträchtigt, insbesondere bei mechanischen Festplatten.) Am Ende erhalten Sie separate Hashes für jeden Block (obwohl dies andere Vorteile hat, z. B. das Zeigen auf den kaputten Block), aber Sie können sie immer zusammen für einen endgültigen Wert hashen.

Dieser Kern könnte ein guter Anfang für etwas in Python sein.

Gary
quelle
splitkommt einem zwar in den Sinn, aber leider ist es keine Option, wenn wir über riesige Dateien sprechen (wie wir es tun).
Poige
@poige Wie gesagt, Sie würden es nicht auf der Festplatte tun, sondern nur die Datei von bestimmten Offsets aus hashen und am Anfang des nächsten Blocks anhalten.
Gary
Ja, aber das ist die Theorie, die ziemlich offensichtlich ist; etwas praktisches?
Poige
@poige Aufgrund Ihrer Frage kann ich nicht erraten, warum dieser Ansatz unpraktisch wäre. Vielleicht gibt es eine Einschränkung, die Sie vergessen haben?
Gary
2
Ich habe nicht gesagt, dass es unpraktisch ist; Aber es ist nicht praktisch, weil Ihre Antwort nichts enthält, was sofort verwendet werden kann. Zum Beispiel: Dies ist eine praktische Antwort: serverfault.com/questions/488486/…
poige
0

Die meisten Antworten hier haben sich mit der linearen Natur der meisten Hashing-Algorithmen befasst. Obwohl ich sicher bin, dass es einige wirklich skalierbare Hashing-Algorithmen gibt, besteht eine einfachere Lösung darin, die Daten einfach in kleinere Teile aufzuteilen und jeweils einzeln zu hashen.

Betrachten Sie den BitTorrent-Ansatz: Wenn ein Torrent erstellt wird, werden alle Dateien in 'Blöcke' aufgeteilt, jeder Block einzeln gehasht und jeder dieser Hashes in der .torrent-Datei aufgezeichnet. Auf diese Weise kann ein Peer eingehende Daten schrittweise überprüfen, ohne warten zu müssen, bis die gesamte Datei zuerst heruntergeladen wurde. Fehler können auch blockweise korrigiert werden, anstatt dass die gesamte Datei erneut übertragen werden muss. Abgesehen von den logistischen Vorteilen ermöglicht dieser Ansatz auch das Skalieren von Hashing über mehrere Kerne hinweg. Wenn 8 Kerne verfügbar sind, können 8 Blöcke gleichzeitig gehasht werden.

Wenn Sie Ihren Überprüfungsprozess so gestalten, dass er mit einer Teilmenge der Daten arbeitet, z. B. mit Blöcken fester Größe, können Sie jeden Block auf einem separaten Kern hashen, wodurch eine große Verzögerung in der Pipeline vermieden wird. Offensichtlich hat dieser Ansatz einen kleinen Kompromiss zwischen Zeit und Speicher: Mit jeder zusätzlichen Hashing-Instanz ist ein gewisser Overhead verbunden, hauptsächlich in Form von Speicher, obwohl dies minimal ist, es sei denn, Sie führen Hunderte von Instanzen aus.

tfrederick74656
quelle
0

Ich arbeite an einem Tree-Hashing-Projekt, das genau für dieses Problem entwickelt wurde: paralleles Hashing großer Dateien von der Stange. Es funktioniert jetzt, obwohl es noch nicht überprüft wurde, und es besteht eine gute Chance, dass Änderungen gegenüber der Überprüfung zu Änderungen am endgültigen Digest führen. Das heißt, es ist sehr schnell: https://github.com/oconnor663/bao

Jack O'Connor
quelle
-1

Sie können hierfür md5deep und für andere Hashes Hashdeep verwenden. Es unterstützt Multithreading mit dem -jFlag. Standardmäßig wird für jeden Kern ein Hashing-Thread erstellt. Es hat auch ein Flag, um Dateien vor dem Hashing in Teile zu zerlegen, verwendet jedoch nicht mehrere Threads für eine einzelne Datei. Ich habe dies verwendet, um sha256 von einer halben Million Dateien zu erhalten, und es hat großartig funktioniert. Es hat auch einen rekursiven Flash, der die Handhabung großer Verzeichnisbäume erleichtert.

Hier ist die Manpage dafür http://md5deep.sourceforge.net/md5deep.html und Git Repo https://github.com/jessek/hashdeep

Der Paketname in Ubuntu und Debian lautet md5deep und enthält Hashdeep.

Jason
quelle
Von der Manpage würde ich erwarten -j, dass Thread für jede angegebene Datei unterstützt wird, nicht für ihre Teile.
Poige
-1

Es ist einfach, einen Hashing-Algorithmus zu entwerfen, der über mehrere Kerne skalierbar ist. Die bekanntesten Hashing-Algorithmen wurden nur speziell entwickelt, um dies zu verhindern, damit Aufgaben wie das Auffinden von Hash-Kollisionen so langsam wie möglich ausgeführt werden.

Hashing-Funktionen, die keine serielle Verarbeitung erzwingen, passen möglicherweise zu Ihnen, aber das hängt davon ab, welche Eigenschaften Sie von Ihrer Hashing-Funktion erwarten. Daher glaube ich nicht, dass Sie genug Informationen gegeben haben, um eine gute Empfehlung abzugeben.

Wie andere vorgeschlagen haben, können Sie eine Hashing-Funktion als Hash der verketteten Hashes jedes der Blöcke einer bestimmten Größe im Original erstellen. Solange die Blockgröße groß genug ist, um das Umkehren der Hashes einzelner Blöcke zu erschweren, funktioniert dies für die meisten Zwecke wahrscheinlich gut genug. Wie groß das sein sollte, hängt davon ab, wie vorhersehbar der Inhalt dieser Blöcke ist. Wenn Sie in der Lage sind, die Entropie zu schätzen und eine Blockgröße so zu wählen, dass Sie mehr als 128 Entropiebits pro Block erhalten, sollte dies für die meisten Zwecke ausreichen (und für viele, bei denen die Sicherheit nicht das Hauptanliegen ist, ein Overkill sein).

Aus Sicherheitsgründen sind Sie besorgt über den Entropiegrad auf Blockebene, da andernfalls das Auffinden einer Kollision für einen einzelnen Block ausreicht, um es einem böswilligen Akteur zu ermöglichen, einen Teil des Inhalts zu ersetzen und denselben endgültigen Hash zu erhalten.

Es ist vielleicht erwähnenswert, dass eine feste Blockgröße bedeutet, dass die Hauptschwäche von MD5s irrelevant ist - der Hacker kann keine zusätzlichen Daten an den Block anhängen.

Wenn es bei Ihren Anforderungen darum geht, natürlich vorkommende Hash-Kollisionen im Gegensatz zu böswilligen zu verhindern, können Sie es sich zweifellos leisten, eine viel schnellere Prüfsummenfunktion zu verwenden. Kryptografisch sichere Hashes sind in der Regel langsam zu berechnen.

Eine Funktion aus der Strangfunktionsgruppe, die den optionalen Hash-Baum-Modus verwendet, passt möglicherweise zu Ihnen. Andererseits könnte CRC32 alles sein, was Sie brauchen.

mc0e
quelle
Ich könnte ein paar Sachen über die Kontroverse um SHA-3 (ieKeccak) einwerfen, wenn Sie möchten, aber vielleicht sollten Sie es einfach auf Wikipedia lesen.
mc0e