Hashen großer Dateien

[hadez16]

Hallo,

ich würde gerne Hashwerte von sehr großen Dateien ( zweistellige Gigabyte) erstellen.

Das Problem ist

a) es dauert viel zu lange

b) das komplette File muss übers Netz (es liegt auf einem Share) eingelesen werden

Meine ersten Gehversuche mit C# brachten zu tage, dass die Implementierungen der MD5-Klasse wohl zum Glück so klug sind und nicht das ganze File in den Hauptspeicher laden und nur einzelne Chunks verarbeiten.

Mir geht es jetzt weniger um die programmiertechnische Umsetzung als viel mehr die richtige Taktik um nach hashwert-manier performant zwei große Files miteinander vergleichen zu können.

Meine Idee wäre einfach den ersten X byte großen Block, den mittleren und den letzten zu nehmen und darauf zu hashen bzw. zu vergleichen. Aber mag das sicher und repräsentativ sein um am Ende sagen zu können die Files sind wirklich gleich?

Ich hoffe ihr wisst was ich meine.

Den Hashalgo über das komplette File zu jagen ist aufgrund der Größe nicht wirklich eine Option denke ich.

Hat jemand Erfahrungen oder Ideen?

Danke!

[del_4901]

1. Vergleiche keine Bytes sondern nimm das Groesste was deine CPU Architektur hergibt int64 oder gar int128.
2. Achte dabei auf aligned reads/writes.
3. Prefetche die Daten in den cache wenn noetig.
4. Verwende einen Profiler um weitere Bottlenecks zu finden

[Shink]

Meine Idee wäre einfach den ersten X byte großen Block, den mittleren und den letzten zu nehmen und darauf zu hashen bzw. zu vergleichen. Aber mag das sicher und repräsentativ sein um am Ende sagen zu können die Files sind wirklich gleich?
Öh... ein Vergleich über den Hash sagt dir nie mit 100%iger Sicherheit ob 2 Dateien gleich sind.

Davon abgesehen: Was meinst du mit ersten, mittleren und letzten X Byte großen Block - sind da dann Lücken dazwischen?

Was ist dieser "Share" auf dem die Dateien liegen und könnte man dort ein Programm laufen lassen?

[hadez16]

Öh... ein Vergleich über den Hash sagt dir nie mit 100%iger Sicherheit ob 2 Dateien gleich sind.

Davon abgesehen: Was meinst du mit ersten, mittleren und letzten X Byte großen Block - sind da dann Lücken dazwischen?

Was ist dieser "Share" auf dem die Dateien liegen und könnte man dort ein Programm laufen lassen?

1) ach nein? Warum nicht? Ich dachte das ist primäre Sinn und Zweck von Hashes

2) ja da wären dann lücken - dann müsste ich aber nicht das ganze file einlesen

3) nein das ist leider nicht möglich - ein dummer Fileserver

[airbag]

Hashfunktionen sind idR doch nicht injektiv und daher nicht eindeutig.

[Shink]

1) ach nein? Warum nicht? Ich dachte das ist primäre Sinn und Zweck von Hashes
Dann könnte man es als Komprimieralgorithmus verwenden: Ich errate so lange einen Dateiinhalt bis ich den selben Hash habe. OK, das würde ewig lange dauern - aber immerhin könnte man so viele Terabyte in eine Datei komprimieren die ein paar Bytes groß ist.:freak:
Nö, das funktioniert so nicht. Die Hashes sind ganz gut in dem Sinn dass ähnliche Dateien sehr unterschiedliche Hashes erzeugen. Aber trotzdem können sehr viele Dateien den selben Hash haben. OK, es ist unglaublich unwahrscheinlich dass 2 Dateien mit Nutzinhalt den selben Hash haben aber möglich ist es und zumindest kann man immer Fälle konstruieren bei denen es so ist.

2) ja da wären dann lücken - dann müsste ich aber nicht das ganze file einlesen
Stell dir vor da drin wären irgendwelche Blöcke; z.B. aneinander gereihte Dateien. Wenn dann der erste, zweite und ein mittlerer Block gleich sind gehst du gleich davon aus dass die ganze Datei gleich ist? Die müssten ja nicht einmal die selbe Größe haben... Das könnte man machen wenn es verschlüsselte Dateien sind - da gilt auch dass sie sehr unterschiedlich sind wenn der Inhalt sehr ähnlich ist.

Was genau ist denn eigentlich der Anwendungsfall? Warum willst du einen Hash und was willst du vergleichen? Was ist der Inhalt der Dateien, was das Format?

[][immy]

1) ach nein? Warum nicht? Ich dachte das ist primäre Sinn und Zweck von Hashes

Ein Hashwert ist nicht eindeutig. Jedoch müssen die gleichen Daten den gleichen Hash-Wert haben. Bei einem ungleichen Hash weist du aber mit sicherheit das die Daten verschieden sind.
Das bedeutet, es kann eigentlich nur für ein schnelles Ausschlussverfahren genutzt werden (je nachdem wie sicher die Prüfung sein soll).

[Monger]

Hashwerte verwendet man üblicherweise als Schlüssel. Auch Schlüssel sind nicht einzigartig - nur idealerweise so gut verteilt, dass man mit dem eigenen Autoschlüssel auf dem selben Parkplatz kein zweites Auto findet. Aber einzigartig sind Hashwerte nicht zwingend.

[xxMuahdibxx]

Wenn HASH Werte (ein)eindeutig wären .... wieso braucht man dann die "normale" Datei noch ^^
nur mal so als Grundüberlegung .

[PatkIllA]

Ordentliches Netzwerk und schnellen Server. Dann kann man auch auf 2 stellige GB noch ganz gut warten.
Die Hashes taugen wie gesagt nur dazu, dass zwei Dateien nicht gleich sind. Vielleicht kannst du damit ja schon einiges ausschließen.

[Trap]

Meine Idee wäre einfach den ersten X byte großen Block, den mittleren und den letzten zu nehmen und darauf zu hashen bzw. zu vergleichen. Aber mag das sicher und repräsentativ sein um am Ende sagen zu können die Files sind wirklich gleich?
Natürlich nicht. Selbst wenn man keinen Angreifer annimmt, würde ich darauf nicht vertrauen. Schon bei einer Textdatei die jemand in der Mitte ändert ist das falsch...
Den Hashalgo über das komplette File zu jagen ist aufgrund der Größe nicht wirklich eine Option denke ich.
Wieso? Selbst über ein 10 MBit-Netzwerk dauern 100 Gigabyte nur einen Tag.

[Shink]

Selbst über ein 10 MBit-Netzwerk dauern 100 Gigabyte nur einen Tag.
Wenn das Teil tatsächlich so lahm angebunden ist würde ich den Hash eben etwas näher dran berechnen lassen. Ist ja etwas bescheuert 100GB übers Netzwerk schicken um einen kleinen Hash zu berechnen.

[Tesseract]

entweder du errechnest am server eine hash und schickst die übers netzwerk oder du schickst die komplette datei übers netzwerk. viele andere möglichkeiten hast du nicht.
eine "stichprobenüberprüfung" an irgendwelchen stellen innerhalb der datei ist pfusch, das kann gewaltig in die hose gehen.

Öh... ein Vergleich über den Hash sagt dir nie mit 100%iger Sicherheit ob 2 Dateien gleich sind.
nicht zu 100%, aber mit an sicherheit grenzender wahrscheinlichkeit - genau das ist ja der sinn einer hashfunction.
2 dateien mit der selben hash sind so grundverschieden, dass die zweite mit ziemlicher sicherheit ein reiner zeichensalat ohne zusammenhang ist auf den du, wenn du ihn nicht irgendwie künstlich als gegenstück errechnest, nicht treffen wirst.

[Trap]

Noch was anderes: MD5 ist keine kryptographisch sichere Hashfunktion mehr, wenn das wichtig ist, sollte man SHA-384 oder SHA-512 nehmen (oder direkt einen der SHA-3 Kandidaten wie http://en.wikipedia.org/wiki/Skein_%28hash_function%29).

[Shink]

entweder du errechnest am server eine hash und schickst die übers netzwerk oder du schickst die komplette datei übers netzwerk. viele andere möglichkeiten hast du nicht.
eine "stichprobenüberprüfung" an irgendwelchen stelln innerhalb der datei ist pfusch, das kann gewaltig in die hose gehen.


nicht zu 100%, aber mit an sicherheit grenzender wahrscheinlichkeit - genau das ist ja der sinn einer hashfunction.
2 dateien mit der selben hash sind so grundverschieden, dass die zweite mit ziemlicher sicherheit ein reiner zeichensalat ohne zusammenhang ist auf den du, wenn du ihn nicht irgendwie künstlich als gegenstück errechnest, nicht treffen wirst.
Irgendwie ist das doch genau das was ich geschrieben hab, oder?

[Tesseract]

Irgendwie ist das doch genau das was ich geschrieben hab, oder?
den post habe ich total übersehen, warum auch immer. :eek:

[hadez16]

danke für die antworten...

ich muss mich nur wundern wie schnell ihr vom praktischen anwendungsfall abweicht und euch in informatische theoretika verliert.

Ich habe 1 File. Da jage ich eine Hashfunktion drüber, ob es MD5 sein soll oder was anderes sei jetzt mal egal. Dieses File durchwandert dann gewisse HSM systeme zur archivierung. Tape-Roboter, usw.

Irgendwann kommt mein File zu mir zurück. Und ich würde gerne sicherstellen, dass das File noch exakt das ist, was ich zu Anfang hatte.

Ich weiß jetzt wird kommen "wenn das HSM bits umkippt hast du ein ganz anderes Problem" usw.

Da die Server auf denen die Hashfunktion laufen wird nur eine 1 Gbit Anbindung zum Storage der Files haben, ist den Hash auf dem kompletten File keine Option. Weil dauert einfach zu lange.

Es handelt sich um Videofiles.

Wenn es nun keine andere tricky Methode gibt um sowas "relativ genau" sicher zu stellen dann muss sich halt die Anbindung ändern um es auf dem ganzen File machen zu lassen.

[Shink]

ich muss mich nur wundern wie schnell ihr vom praktischen anwendungsfall abweicht und euch in informatische theoretika verliert.
Sehr lustig. Du hast uns auch so gut wie alle Details zum Anwendungsfall verschwiegen.

Wenn es nun keine andere tricky Methode gibt um sowas "relativ genau" sicher zu stellen dann muss sich halt die Anbindung ändern um es auf dem ganzen File machen zu lassen.
Ohne die ganze Datei zu lesen - no way. Du weißt ja nicht wo die Datei kaputt sein könnte. Wenn du den Bereich zufällig "übersiehst" funktioniert das nunmal nicht.

Ach ja: "Nur 1 GigaBit" - das ist ungefähr so schnell wie der PCI Bus. Viel schneller wird das nicht werden. Welche Transferrate bekommt denn die Festplatte zusammen?

[Trap]

Ich habe 1 File. Da jage ich eine Hashfunktion drüber, ob es MD5 sein soll oder was anderes sei jetzt mal egal. Dieses File durchwandert dann gewisse HSM systeme zur archivierung. Tape-Roboter, usw.

Irgendwann kommt mein File zu mir zurück. Und ich würde gerne sicherstellen, dass das File noch exakt das ist, was ich zu Anfang hatte.
Sinnvollerweise macht man die Integritätsprüfung auf dem Gerät, dass die Daten wieder einliest. Da muss man die Daten sowieso komplett lesen und wenn man die Prüfung sofort macht, kann man sich keine Probleme mit den noch ungeprüften Daten einfangen.

Wozu machst du das ganze eigentlich? Bis jetzt hast du noch nicht erwähnt welchen Nutzen die Anwendung haben soll...

[][immy]

danke für die antworten...

ich muss mich nur wundern wie schnell ihr vom praktischen anwendungsfall abweicht und euch in informatische theoretika verliert.

Ich habe 1 File. Da jage ich eine Hashfunktion drüber, ob es MD5 sein soll oder was anderes sei jetzt mal egal. Dieses File durchwandert dann gewisse HSM systeme zur archivierung. Tape-Roboter, usw.

Irgendwann kommt mein File zu mir zurück. Und ich würde gerne sicherstellen, dass das File noch exakt das ist, was ich zu Anfang hatte.

Ich weiß jetzt wird kommen "wenn das HSM bits umkippt hast du ein ganz anderes Problem" usw.

Da die Server auf denen die Hashfunktion laufen wird nur eine 1 Gbit Anbindung zum Storage der Files haben, ist den Hash auf dem kompletten File keine Option. Weil dauert einfach zu lange.

Es handelt sich um Videofiles.

Wenn es nun keine andere tricky Methode gibt um sowas "relativ genau" sicher zu stellen dann muss sich halt die Anbindung ändern um es auf dem ganzen File machen zu lassen.

du kannst natürlich auch erst mal andere Werte zurückgeben. Z.b. Dateigröße, name, ...
alles das was als auschlusskriterium gelten könnte. dann bräuchtest du im ersten schritt noch keine Hash bilden und damit die gesamte datei lesen.
dann gäbe es noch die möglichkeit z.b. durch das vergleichen der ersten paar kb (am besten verteilt über bestimmte punkte) zu nutzen um eine übereinstimmung auszuschließen.
dann müsstest du aber wieder eine intensivere prüfung durchführen wenn die prüfung eine übereinstimmung feststellt. hier kannst du dann wieder versuchen zu trixen und z.b. dann eine etwas intensiveren hash bilden und das von mal zu mal steigern.

im besten fall würdest du dann direkt am anfang (z.b. anhand der dateigröße) direkt ausschließen können, das es sich um die datei handelt. jedoch wirst du besonders bei der archivierung von dateien am ende immer einen 1:1 abgleich machen müssen, weil hash-codes hier nur begrenzte sicherheit geben.

mehr als diese vorhergehenden ausschlussverfahren wird es hier nicht geben können. denn wie oben schon geschrieben wurde, hashes sind nicht eindeutig. die chance ist zwar gering das man (je nach verfahren) noch mal den gleichen hashwert bekommt aber um 100% sicher zu gehen, musst du am ende einen 1:1 vergleich nutzen.
Ungleicher Hash = Daten sind unterschiedlich
Gleicher Hash = Daten sind vielleicht gleich

übrigens, da sich die daten bereits auf einem storage-system befinden (so wie ich es verstanden habe), hier sollte das storage-system normalerweise bereits in einer datenbank bereits den hash-wert haben (zumindest die storage-system-anbindungen die ich kenne machen das so). dieser sollte bei der ablage auf das storage-system gebildet werden um z.b. dubletten-speicherung zu vermeiden. ob die anbindung an das system diese hash-wert über die api jedoch raus gibt, ist natürlich eine andere frage.

[Birdman]

Irgendwann kommt mein File zu mir zurück. Und ich würde gerne sicherstellen, dass das File noch exakt das ist, was ich zu Anfang hatte.

Dazu reicht es doch, einfach mal ein paar wenig Bytes zu vergleichen.
Sind die hashes davon nicht identisch hast Du schon gewonnen. Sind sie gleich, dann holst halt ein paar Bytes mehr und vergleichst nochmals. Das ganze kannst dann einige male durchführen bis Du entweder die ganze Datei hast oder zumindest eine für dich representative Menge.

[PatkIllA]

Video/Audio Codecs und Container haben üblicherweise auch noch Fehlerkorrekturdaten an denen man Fehler erkennen kann.
Ich hätte statt des unbemerkten Umkippen von Bits eher die Befürchtung, dass Sektoren aufgrund von Plattenfehlern nicht mehr lesbar sind.

[hadez16]

so, ich habe jetzt einen praktikablen weg gefunden um wenigstens die Geschwindigkeit beim kompletten Einlesen des Files zu erhöhen:

Statt bei der MD5CryptoServiceProvider (http://msdn.microsoft.com/en-us/library/system.security.cryptography.md5cryptoserviceprovider.aspx)-Klasse die ComputeHash-Methode zu verwenden, die 4k-Chunks benutzt, diese erst verarbeitet und dann weiter ausliest, verwende ich die TransformBlock/TransformFinalBlock-Methode um gleich, soweit es der RAM zulässt, ganze dreistelligen Megabyte-Blöcke einzulesen.

Das machts ein gutes Stück flotter.

[Gast]

Ich habe bei meinem Sicherungsskript fast das gleiche Problem gehabt: Es wird mit .NET per MD5 Key verglichen, ob die Datei gleich ist und wenn nicht, dann wird sie eindeutig gesichert (jede Datei mit gleichem MD5 Key nur einmal, egal wo sie liegt und wie sie heißt).

Der Algorithmus funktioniert ca. so (Client = Rechner der gesichert wird, Server = Sicherungsserver):

1.) Vergleichen, ob die Datei vorher schon existiert hat bzw. ob sich das Dateidatum geändert hat. Falls nein, dann überspringen.

2.) Falls die Datei unter einem Grenzwert liegt, der in den RAM passt (z.B. 10MB), so wird diese am Client auf einmal in den RAM geladen, der MD5 Key berechnet und dann dieser gesendet. Der Server prüft, ob die Datei schon vorhanden ist und wenn nein, dann wird sie übers Netzwerk versendet.
Diese Optimierung funktioniert jedoch nur, wenn der Clientrechner ein Windows System ist, auf dem du ein .NET Programm laufen lassen kannst. Ansonsten muss alles zwingend über das Netzwerk.

3.) Ist die Datei größer als 10MB, so wird sie zuerst an den Server gesendet, dieser berechnet beim Empfangen den MD5 Key und speichert diese unter einer tempöreren Datei parallel ab. Zum Schluss wird überprüft, ob der MD5 Key neu ist. Wenn ja, dann wird die Datei umbenannt, ansonsten wird sie gelöscht.

Verwendet habe ich wie du Methoden TranformBlock und TransformFinalBlock, wobei ich nur die TransformBlock Methode mit Daten aufrufe und die TransformFinalBlock Methode ohne Daten eigentlich nur Teil des Close Vorganges ist.

Grundsätzlich solltest du folgendes beachten:

1.) Das Öffnen von Dateien zum Lesen ist nicht immer ungefährlich, wenn eine andere Software die Dateien zum Schreiben öffnen will. Ein SQL Server, der auf seine Datenbankdateien nicht zugreifen kann, wertet das als IO Fehler und setzt die ganze Datenbank inaktiv. Ein Outlook, wird mit einer Fehlermeldung starten, wenn es nicht auf seine .pst oder .ost Datei zugreifen kann. Access wird auch eine Fehlermeldung werfen, wenn du die Datei zum Lesen öffnest usw. Bei normalen Shares ist das kein Problem, bei Systemdateien aber eventuell schon.

2.) Das Lesen von großen Dateien über das Netzwerk kann das System, von dem gelesen wird ganz schön in die Knie zwingen, als besser nicht im Hintergrund, solange es jemand benötigt. Willst du im Hintergrund sichern, so würde ich zwischen den Lesebefehlen mit z.B. 32KB immer ein sleep einbauen.

3.) Nur weil ein Teil der Daten gleich ist, heißt das noch lange nicht, dass die Dateien ident sind. Wenn eine Datei nicht zur Gänze neu gespeichert wird, sondern nur zum Teil neu beschrieben wird (Datenbanksystem, .pst Datei, in die immer neue Emails exportiert werden, Festplatten Image, das in der Mitte geändert wird usw., dann wirst du eventuell nur in der Mitte Änderungen haben. Bitmaps, die die gleiche Größe haben und oben bzw. unten den gleichen Inhalt haben (und sei es nur ein schwarzer Rand), werden sich auch nur in der Mitte unterscheiden. Andere Dateiformate haben auch nur einen ziemlich großen Header ohne Prüfsumme und sind hinten mit 0ern gepaddet. Da fällt es auch nicht auf. Die Zuverlässigkeit der Anfang und Ende Methode hängt immer von der Art der Datei ab. Das Problem mit gänzlich fehlenden Blöcken und deshalb ungültigen Daten lasse ich einmal außen vor.

4.) Ein MD5 Key schützt beim Vergleich von zufälligen Änderungen von Dateien, selbst wenn diese gewissen Mustern folgen (siehe Punkt 3), nicht jedoch vor absichtlichen Fälschungen. Es ist heute ohne Probleme möglich eine MD5 Datei der gleichen Größe mit dem selben Key zu erzeugen. Teilweise kann man hier sogar nicht nur Fälschungen mit beliebigem Binärsalat erzeugen, sondern sogar den Inhalt mitbestimmen. Für das Abspeichern von Dateien in einer Virendatenbank, ist das also nicht mehr zeitgemäß.

5.) In der Praxis wirst du nicht den Fall haben, dass zwei verschiedene Dateien den gleichen MD5 Key haben, sondern viel öfter wirst du den Fall haben, dass der MD5 Key gleich ist, jedoch die Datei nicht mehr, weil während dem Auslesen bzw. der Berechnung irgendein Schreibzugriff auf die Datei passiert. Ich schmeiße immer wieder ein paar Dateien aus meinem Sicherungsskript raus, die zwar den selben MD5 Key haben, jedoch eine verschiedene Größe. Solange das nur die Sicherung von ein paar Netzlaufwerken ist, ist das keine Dramatik, wenn einmal ein paar Logdateien oder ein paar Thumbs.db Dateien nicht mitgenommen werden. Für die sichere Ablage von Dateien würde ich jedoch nicht auf handgeschriebene Tools vertrauen. Da kann viel schiefgehen.