Ich habe eine XML-Datei, in der ich feststellen muss, ob es ein Duplikat ist oder nicht.
Ich werde entweder die gesamte XML-Datei hashen, oder bestimmte xml-Knoten in der xml-Datei werden verwendet, um dann eine Art Hash zu erzeugen.
Ist md5 dafür geeignet?
Oder etwas anderes? Die Geschwindigkeit bei der Erzeugung des Hash ist ebenfalls ziemlich wichtig, aber die Garantie, einen eindeutigen Hash für eindeutige Daten zu erzeugen, ist von größerer Wichtigkeit.
MD5 ist kaputt (in dem Sinne, dass es möglich ist, absichtlich eine Hash-Kollision zu erzeugen), sollten Sie wahrscheinlich die SHA-Familie (zB: SHA-256 oder SHA-2) verwenden, wenn Sie sich um jemanden böswillig
Beachten Sie, dass Hash-Funktionen von Natur aus keinen eindeutigen Hash für jede mögliche Eingabe garantieren können. Hash-Funktionen haben eine begrenzte Länge (zB: MD5 ist 128 Bit lang, es gibt also 2 128 mögliche Hashes). Sie können eine potentiell unendliche Domäne nicht einer endlichen Ko-Domäne zuordnen, dies ist mathematisch unmöglich.
Jedoch, nach Geburtstagsparadox , ist die Wahrscheinlichkeit einer Kollision in einer guten Hash-Funktion 1 in 2 n / 2 , wobei n die Länge in Bits ist. (Bsp .: Mit 128-bit MD5 wäre das 2 64 ). Dies ist so statistisch unbedeutend, dass Sie sich keine Sorgen über eine zufällige Kollision machen müssen.
MD5 ist geeignet und schnell. Beachten Sie jedoch, dass ein einzelner Unterschied in einem Zeichen ein völlig anderes MD5 erzeugt.
Es gibt eine geringe Chance, dass MD5 den gleichen Hash für verschiedene Eingaben erzeugt. Das wird ziemlich selten sein. Also, abhängig von Ihrer Eingabe (erwarten Sie viele ähnliche XMLs oder viele verschiedene?), Wenn MD5 Ihnen eine positive Übereinstimmung gibt, können Sie die einfachen String-Inhalte vergleichen.
Wenn jemand den Inhalt einiger XML-Dateien zumindest teilweise ändern kann und jemand einen Vorteil darin hat, dass Sie zwei XML-Dateien (oder XML-Ausschnitte) als identisch deklarieren, obwohl dies tatsächlich nicht der Fall ist, benötigen Sie eine kryptographische Methode sichere Hash-Funktion, nämlich eine, die resistent gegen Kollisionen ist. Eine Kollision ist ein Paar unterschiedlicher Nachrichten (Sequenzen von Bytes), die die gleiche Hash-Ausgabe ergeben - genau das, was Sie vermeiden möchten. Da eine Hash-Funktion Eingaben akzeptiert, die länger als ihre Ausgabe sind, gibt es notwendigerweise Kollisionen; Eine Hash-Funktion gilt als kryptographisch sicher, wenn niemand eine solche Kollision tatsächlich erzeugen kann.
Wenn eine Hash-Funktion n Bits ausgibt, dann kann man nach dem Hashing von 2 n / 2 eindeutigen Nachrichten eine Kollision erwarten. Eine sichere Hash-Funktion ist eine Hash-Funktion, so dass keine Methode bekannt ist, um eine Kollision schneller zu bekommen.
Wenn es kein Sicherheitsproblem gibt (dh niemand wird aktiv versuchen, eine Kollision zu finden, befürchten Sie einfach eine Kollision aus Pech), dann sind kryptographisch schwache Hash-Funktionen eine Option, vorausgesetzt, sie haben eine ausreichend große Ausgabe Das 2 n / 2 bleibt viel größer als die erwartete Anzahl von XML-Dateien, die Sie vergleichen werden. Für n = 128 (d. H. 2 n / 2 nahe achtzehn Milliarden von Milliarden) ist MD5 in Ordnung, schnell und weit verbreitet. Vielleicht möchten Sie MD4 untersuchen, das sogar noch schwächer, aber auch etwas schneller ist. Wenn Sie ein größeres n möchten, versuchen Sie SHA-1 , das 160-Bit bietet Outputs (SHA-1 Schwächen sind im Moment noch theoretisch, daher ist SHA-1 viel weniger "kryptographisch gebrochen" als MD5).
Wenn Sie möglicherweise sogar Sicherheitsprobleme haben, gehen Sie zu SHA-256 . Derzeit ist für diese Funktion keine kryptographische Schwäche in Bezug auf Kollisionen bekannt. Wenn Sie Leistungsprobleme haben (was eher unwahrscheinlich ist: Auf einem Basis-PC kann SHA-256 mehr als 100 Megabytes an Daten pro Sekunde verarbeiten, also ist die Wahrscheinlichkeit, dass XML-Parsing weit teurer ist als Hashing), sollte SHA-512 in Betracht gezogen werden Dies ist etwas schneller auf Plattformen, die 64-Bit-Integer-Typen bieten (aber auf Plattformen, die dies nicht tun, langsamer).
Beachten Sie, dass all diese Hash-Funktionen sich auf Bytefolgen beziehen. Ein einzelnes geflipptes Bit ändert die Ausgabe. In der XML-Welt kann ein gegebenes Dokument auf verschiedene Arten kodiert werden, die semantisch identisch sind, aber so verschieden wie Bits auf dem Draht sind (z. B. é und é repräsentieren beide das gleiche Zeichen é ). Es liegt an Ihnen zu definieren, welchen Begriff der Gleichheit Sie verwenden möchten; siehe kanonisches XML .