Hallo, zur Abwechslung mal keine Frage, sondern eine Info, falls sie
jemand gebrauchen kann.
Ich berechne zu jeder Datei beim Backup einen Hash-Wert.
Mal angenommen, es sind 10 Millionen Dateien und es soll keine
Kollisionen geben. Im Bild: Egal, 128 Bits reichen: 1,469367E-25
collision probability; Berechnet mit:
http://davidjohnstone.net/pages/hash-collision-probability
Zur Geschwindigkeit: Ich habe einmal parallel und einmal
nacheinander gerechnet:
1
bool_IsParallel=false;
2
bool_IsParallel=true;
Hier der Code:
https://gist.github.com/TorstenC/e16e6c798fa4a5e1c650b7234de9c790
Spalte F (relativ) im Bild ist ein logarithmisches Produkt aus
Rechenzeit, Speicherbedarf und "collision probability". Was auffällt:
Bei RIPEMD160 und SHA384 ist trotz höherer Rechenzeit keine Verbesserung
zu sehen (rot).
Mein Ergebnis (mein Sohn Jonas hatte recht): Für den genannten Zweck
(Eindeutiger Hash-Wert für jede Datei-Version) reicht MD5 allemal aus
und ist die schnellste Funktion von allen.
Auch wenn dieser Thread keine Frage ist, sondern eine Info: Hinweise auf
Denkfehler sind natürlich willkommen.
VG Torsten
Hallo,
interessante Info.
Spontan hätte ich einen CRC Hash mit erwartet. Hat dies einen
technischen Hintergrund, oder hast du ihn einfach nicht getestet?
Nach meinem Verständnis unterscheiden sich der Punkt Kollision nicht bei
den Algorithmen sondern nur die Sicherheit (Umkehrbarkeit) der Hashes.
Gruß Kai
PS: Sorry, falls es eine dumme Frage ist.
Eine Frage, wie hoch man die Kollisionswahrscheinlichkeit haben
moechte..
ein 32Bit CRC bringt eben, wegen den 32 bit, nur 10^9.
Wenn ich manipulationen ausschliessen moechte, muss ich den 128bit Wert
nehmen, wenn ich nur Speicherfehler ausschliessen moechte, genuegen 32
Bit.
Kai S. schrieb:> Nach meinem Verständnis unterscheiden sich der Punkt Kollision nicht bei> den Algorithmen sondern nur die Sicherheit (Umkehrbarkeit) der Hashes.
Richtig (vorausgesetzt der Output der Algorithmen ist uniform), nur
liegt die Wahrscheinlichkeit für eine zufällige Kollision bei CRC32
(oder irgendwas anderem was nur 32-Bit ausspuckt) schon nach nur etwa
77000 gehashten Dateien/Nachrichten bei 50%
Bei einem 64-Bit Hash dagegen erst nach etwa 5 Mrd Dateien, bei 128-Bit,
wie bei MD5, sind's 2.2*10^10
https://en.wikipedia.org/wiki/Birthday_attack
Trotzdem würde ich hier nicht unbedingt MD5 einsetzen, wenn man sicher
sein will, dass bspw. die Datei im Backup auch tatsächlich die ist, die
man gebackuped hat...
https://en.wikipedia.org/wiki/MD5#Security
Arc N. schrieb:> Trotzdem würde ich hier nicht unbedingt MD5 einsetzen
Hmmm, auch zum Thema Manipulationen^^: Wer sollte unbemerkt ein Backup
manipulieren wollen und sich deshalb die Mühe machen, nach der
Manipulation den gleichen Hash zu gewährleisten? Für einen Virus eine
spannende Aufgabe. ;)
Es gibt kein Szenario, bei dem die Security für diesen Anwendungsfall
relevant wäre, behaupte ich.
Speicherfehler^^: Darum geht es mir nicht primär.
Beispiel: Die Datei wurde umbenannt und die Länge stimmt überein. Wenn
der Hash auch gleich ist, wird es wohl die gleiche Datei sein, unter
einem anderen Dateinamen, z.B. in einem anderen Verzeichnis und/oder
z.B. in einem ZIP-File oder auf einer Archiv-Festplatte. Auch wenn das
Datei-Datum unterschiedlich ist.
Kai S. schrieb:> Spontan hätte ich einen CRC Hash mit erwartet. Hat dies einen> technischen Hintergrund, oder hast du ihn einfach nicht getestet?
Wie Arc N. (arc) auch schon meinte:
Bereits bei 77163 Dateien und CRC32 sagt der Rechner:
"There is a 0.4999978 chance of a hash collision."
http://davidjohnstone.net/pages/hash-collision-probability
Professioneller Googler schrieb:> ich hab ja gewusst, dass .NET eine fette langsam Sau ist, aber diese> Werte sind einfach katastrophal.
850 MB in 2,5 Sekunden halte ich nicht für katastrophal, zumal ich hier
keine Angabe der CPU sehe.
Einzig die >30 Sec für SHA384 fallen aus dem Raster - SHA512 mit 13
Sekunden ist deutlich schneller...
OK, die Info fehlte. Sorry, siehe Anlage.
BTW: Im RELEASE- statt im DEBUG-Mode ändert sich quasi nix.
0,5..3% Streuung sind eh in den Ergebnissen drin.
Jim M. schrieb:> 850 MB in 2,5 Sekunden halte ich nicht für katastrophal, zumal ich hier> keine Angabe der CPU sehe.
Die Zeiten für MD5 und SHA1 sind vllt. nicht katastrophal, aber die
Zeiten für die anderen Algos schon. md5sum=1,4 sha1sum=1,5 sha256sum=3,1
sha384sum=2,0 sha512sum=2,0 jeweils in Sekunden für eine 870MB Datei.
Hättest du ein paar Vergleichszahlen zu der von dir bevorzugten
Programmiersprache?
Logischerweise müsstest du auch einen Durchlauf mit dem oben verlinkten
C# auf deinem PC machen, sonst wäre der Vergleich sinnlos.
Strawberry schrieb:> Hättest du ein paar Vergleichszahlen zu der von dir bevorzugten> Programmiersprache?> Logischerweise müsstest du auch einen Durchlauf mit dem oben verlinkten> C# auf deinem PC machen, sonst wäre der Vergleich sinnlos.
Ich habe die angegebenen Programme (md5sum, sha1sum, ...) genutzt. Ich
habe es nicht nachgeprüft, bin mir aber reltiv sicher, dass sie in c
geschrieben sind.
Das obige C# Programm kann ich auf meinem PC "leider" nicht laufen
lassen.
1
HashTestTemp.cs(2,17): error CS0234: The type or namespace name 'VisualStudio' does not exist in the namespace 'Microsoft' (are you missing an assembly reference?)
2
HashTestTemp.cs(10,6): error CS0246: The type or namespace name 'TestClassAttribute' could not be found (are you missing a using directive or an assembly reference?)
3
HashTestTemp.cs(10,6): error CS0246: The type or namespace name 'TestClass' could not be found (are you missing a using directive or an assembly reference?)
4
HashTestTemp.cs(17,10): error CS0246: The type or namespace name 'TestMethodAttribute' could not be found (are you missing a using directive or an assembly reference?)
5
HashTestTemp.cs(17,10): error CS0246: The type or namespace name 'TestMethod' could not be found (are you missing a using directive or an assembly reference?)
Strawberry schrieb:> Hättest du ein paar Vergleichszahlen zu der von dir bevorzugten> Programmiersprache?> Logischerweise müsstest du auch einen Durchlauf mit dem oben verlinkten> C# auf deinem PC machen, sonst wäre der Vergleich sinnlos.
Die Wahl der Programmiersprache sollte da keine große Auswirkung haben.
Alles eine Frage der Implementierung ;-)
Thread beobachten
Seitenaufteilung abschalten