MD5 Kollisionen

[ComFreek]

Bin hier kein Kryptograph, aber was hälst du von der Idee, zwei Hash-Algorithmen einzusetzen?
Beispielsweise MD5 und SHA-256?
Bei der Überprüfung vergleichst du dann immer beide Hash-Werte.

Sollte das nicht die Wahrscheinlichkeit einer zufälligen Kollision erheblich senken?

 

[fugyl]

Aber Algorithmen wie SHA2 sind für die nächsten paar Jahre vermutlich unknackbar

Klar, aber es geht ja auch nicht ums knacken oder nicht knacken, sondern nur darum festzustellen ob eine Änderung in einer Datei bzw. einem Dateisegment vorgenommen wurde.

Würde mir lieber Gedanken um andere Blickwinkel der Sachen machen.
Um etwas triviales zu nennen: Wenn die Hashes bei den Daten dabei sind,
was hindert mich daran, einfach alles samt Hashes zu ersetzen?
Ergebnis ist auch gültig, nur eben nicht das, was vorher drin war.

Okay, ich sehe ein, dass es evtl. sinnvoll sein könnte das Problem, das ich versuche mit dem Algo zu lösen, einfach mal zu beschreiben

Mir passiert es häufiger (besonders bei großen Dateien >=2GByte), dass ich plötzlich korrupte Daten habe. Dies ist zwar nicht ganz so wild, weil es nur auf meinen ext. HDDs auftritt, aber trotzdem nervig. Kleine Dateien werden davon btw. nicht oder kaum betroffen.

Meine Idee war es, Wiederherstellungsinformationen für jede Datei zu speichern, um sie evtl zu reparieren.
Um nicht die Datei einfach neu zu speichern, will ich nur einen gewissen Prozentsatz (sagen wir 10%) an Bytes für eine Datei speichern, die ich dann auch wieder herstellen kann. Dazu teile ich die Datei in (z. B. 10) Segmente, XOR-e alle diese Segmente und speichere das Ergebnis und den Hash für jedes Segment ab. Ist die Datei hübsch von einem User geändert worden, sieht man das unter anderem an der Dateigröße, dann ists okay, wenn allerdings einfach mal so pauschal nen Datenverlust auftritt, kann man das so erkennen und auch reparieren (solange die Datei nicht mehr als 10% Daten verloren hat). Dumm wäre jetzt allerdings, wenn es einen Datenverlust gibt, mein Algo das allerdings nicht erkennt.

Ich hoffe ihr könnt mir folgen.

Natürlich ist es - gelinde gesagt - "eher" unwahrscheinlich, dass mein Algo Datenverlust nicht erkennt, selbst mit MD5, aber möglich bleibt möglich

Und wenn du auf die Idee kommst, deine Wiederherstellungsinformationen zu ändern... von mir aus
Daher ist Sicherheit ein - für dieses Problem - unwichtiger Punkt. Wer Zugriff auf die Originaldaten hat, kann auch Zugriff auf die W.-Infos haben.

Lieben Gruß
Fugyl

[EDIT]

Bin hier kein Kryptograph, aber was hälst du von der Idee, zwei Hash-Algorithmen einzusetzen?
Beispielsweise MD5 und SHA-256?
Bei der Überprüfung vergleichst du dann immer beide Hash-Werte.

Sollte das nicht die Wahrscheinlichkeit einer zufälligen Kollision erheblich senken?

Oh, nicht gesehen dass du auch noch was geschrieben hattest
Ja, da hab ich dran gedacht, wäre ja im Grunde genau die Lösung des Konkatenierens.

Wäre etwas damit gewonnen, zwei unterschiedliche Hash-Algorithmen zu benutzen und die resultierenden Hashs einfach zu konkatenieren?

[/EDIT]

 

[sheel]

Also es geht nicht um boswillige Angriffe, sondern HW-Fehler
(wie wäre eine neue Festplatte :suspekt

Und meiner Einschätzung nach ist es da vollkommen ausreichend, SHA1 etc. zu verwenden.
Zumindest als Prüfmaßnahme.
Festplatten machen keine jahrelange Forschung, wie sie dir am besten schaden
Die Wahrscheinlichkeit, dass eine sterbende HDD zufällig eine Hashkollision liest,
ist zumindest für unsere Lebenszeit zu vernachlässigen

Zu dem XOR-Wiederherstellungsverfahren:
Bin mir nicht sicher, ob ich dein Vorhaben richtig verstehe, aber 10% geht so gar nicht
Für einen einigermaßen guten, einfachen, bewährten, aber leider auch grauenhaft langsamen Algo
für Reparierinfos siehe Reed-Solomon-Codes.
Hätte das auch irgendwo implementiert, kanns bei Gelegenheit eigentlich online stellen
(es gibt einige Implementierungen im Netz, aber irgendie immer entweder noch viel langsamer,
kostenpflichtig, oder komplett überladen mit Müll, den keiner braucht)

edit: Jaja, dann ist noch eine nutzlose Implementierung mehr im Netz

 

[fugyl]

Also es geht nicht um boswillige Angriffe, sondern HW-Fehler
(wie wäre eine neue Festplatte :suspekt

Leider nicht meine erste die das hat. Entweder ich bin ein Pechvogel oder ich gehe mit HDDs nicht so um wie normale Menschen

Und meiner Einschätzung nach ist es da vollkommen ausreichend, SHA1 etc. zu verwenden.
Zumindest als Prüfmaßnahme.
Die Wahrscheinlichkeit, dass eine sterbende HDD zufällig eine Hashkollision liest,
ist zumindest für unsere Lebenszeit zu vernachlässigen

Ja schon klar, wie gesagt: Ich wäre auch aus rein theoretischem Interesse an 100% Sicherheit interessiert.

Festplatten machen keine jahrelange Forschung, wie sie dir am besten schaden

Du kennst meine Festplattenhistorie nicht. Die widersetzt sich jedem Naturgesetz. Da ist eine Wahrscheinlichkeit von (10^-15)% immernoch ein "sicheres Ereignis"

Zu dem XOR-Wiederherstellungsverfahren:
Bin mir nicht sicher, ob ich dein Vorhaben richtig verstehe, aber 10% geht so gar nicht
Für einen einigermaßen guten, einfachen, bewährten, aber leider auch grauenhaft langsamen Algo
für Reparierinfos siehe Reed-Solomon-Codes.
Hätte das auch irgendwo implementiert, kanns bei Gelegenheit eigentlich online stellen
(es gibt einige Implementierungen im Netz, aber irgendiwe immer entweder noch viel langsamer, kostenpflichtig, oder komplett überladen mit Müll, den keiner braucht)

Ich sehe das Problem da nicht, muss ich gestehen. Und natürlich gibts dafür Tools, aber selbst ist der Mann

Ich kanns ja mal an nem Beispiel zeigen, wie ich das meine:

10010 10010 10001 ist jetzt meine "riesige" Datei

Ich will pauschal 20% Wiederherstellungsinfos speichern, also Teile ich in:

100 101 001 010 001 auf.

Ver-XOR-t man alles ergibt das 011 (wenn ich mich nicht irre), also speichere ich 011 ab. Zusätzlich speichere ich für jede dieser "3-Bit-Segmente" einen Hash ab.

So, böse Sachen passieren und ich habe plötzlich folgendes:

101 101 001 010 001

Das erkenne ich natürlich (mehr oder weniger) sofort daran, dass mein Hashwert fürs erste Segment ein anderer ist. Also versuche ich zu reparieren und gehe dafür von rechts nach links:

zzz XOR 001 = 011 => zzz = 010
yyy XOR 010 = 010 => yyy = 000
xxx XOR 001 = 000 => xxx = 001
vvv XOR 101 = 001 => vvv = 100 <-- Tadaa!

(Wenn sich die Datei nicht perfekt aufteilen lässt, dann füg ich halt am Ende noch nullen hinzu oder sowas, damit hab ich mich noch nicht beschäftigt.)

Lieben Gruß
Fugyl

[edit]
Ich "will" 10% speichern, tu ich aber nicht
Ich speicher also 20% in dem Beispiel, sorry für die Verwirrung
[/edit]

 

[sheel]

Du hast 5*3bit Daten und dazu 3bit Wiederherstellungsinfos.
=20% Wied.Info statt 10%
Unabhängig davon:

Bei deinem Beispiel ist alles ok, was das Korrigieren betrifft.
Es könnten sogar alle 3bit vom ersten Block falsch sein.
=20% korrigierbar bei 20% Wied.Info. Sehr schön soweit

Was aber, wenn 2 (oder auch drei) bit falsch sind,
die nicht alle im selben Block sind?
Deine Hashes sagen, dass zwei (oder mehr) Blöcke falsch sind,
und schon ist gar nichts mehr korrigierbar
...
Ausgeweitet auf Blöcke zu 8192bit (1KB), wieder mit xy% Wiederherstellungsblocken dazwischen
kannst du im Idealfall bis zu 8192bit verbessern,
in den meisten Situationen aber nur 1 oder gar nichts.
Bei 10% Wiederherstellungsblöcken wären ~0.00125% Fehler in den Daten korrigierbar


Wenn die Fehler wirklich nur so sind, dass ab und zu ein HDD-Block und sonst nichts falsch ist
(und deine XOR-Blöcke gleich groß wie die HDD-Blöcke sind)
kann das so schon sehr gut gehen. Aber sonst...


Trotzdem macht mir deine HW Sorgen.
Festplatten haben hardwaremäßig schon Prüf/Korrigierzeug eingebaut
(nichts starkes wie SHA2 oder so, aufgrund Geschwindigkeit,
bei dem "schwachen" Steuerwerk in der Platte,
nur zB. ein CRC, bei dem schon Kollisionen auftreten können.
Trotzdem...)

Bei erkennbaren Fehlern, die nicht korrigiert werden können,
sollte man Meldungen bekommen, dass es Lesefehler gab usw.
Wenn es so kaputte Blöcke gibt, dass die Prüfung versagt
sollten doch auch welche dabei sein, bei denen die Fehler noch erkennbar sind,
und diese Meldungen produzieren.

Sonst ist vllt. dein Ram/Prozessor/Mainboard kaputt, statt der Festplatte?

 

[fugyl]

Bei deinem Beispiel ist alles ok, was das Korrigieren betrifft.
Es könnten sogar alle 3bit vom ersten Block falsch sein.
=20% korrigierbar bei 20% Wied.Info. Sehr schön soweit

Was aber, wenn 2 (oder auch drei) bit falsch sind,
die nicht alle im selben Block sind?
Deine Hashes sagen, dass zwei (oder mehr) Blöcke falsch sind,
und schon ist gar nichts mehr korrigierbar

Good point, gar nicht dran gedacht. Aber...

Wenn die Fehler wirklich nur so sind, dass ab und zu ein HDD-Block und sonst nichts falsch ist
(und deine XOR-Blöcke gleich groß wie die HDD-Blöcke sind)
kann das so schon sehr gut gehen. Aber sonst...

Weiß nicht... wie groß ist ein HDD-"Block"? Schätze aber mal stark dass die Wh.-Infos größer werden, also sollte das weniger ein Problem darstellen. Mit 10% von 20Gb hat man ja immerhin noch 2GB an Daten...

Vielleicht kann ich da ja noch tricksen, wer weiß

Die Idee stammt nicht wirklich von mir, die habe ich vor vielen Jahren mal in einem Forenbeitrag in den Untiefen des Internets gefunden, auf die Frage, wie WinRAR Wiederherstellungsarchive realisiert.

Trotzdem macht mir deine HW Sorgen.[...]

Das ist nett von dir, aber unbegründet
Dass die Platte von allein CRC-Checks durchführt, wäre mir neu, würde mich auch wundern, da ich halt so ein Problem schon öfters hatte und die Platte mir nie was gemeldet hat. Fehlerhafte Sektoren hab ich auch keine (extra nochmal grade chkdsk angeworfen )

Mit meiner restlichen Hardware kann das nicht zusammen hängen, weil die sich oft ändert. Grad n paar Monate ist mein Rechner alt und das Problem mit Datenverlust hab ich seit Jahren. Es sind auch immer die gleichen Dateien: Windows-ISOs wenn man sie grade mal dringend braucht, oder Spiele, die man nach vielen Jahren doch mal dringend nochmal zocken will und ähnliches...

Lieben Gruß
Fugyl

 

[sheel]

Die Idee stammt nicht wirklich von mir, die habe ich vor vielen Jahren mal in einem Forenbeitrag in den Untiefen des Internets gefunden, auf die Frage, wie WinRAR Wiederherstellungsarchive realisiert.

Inzwischen auch mit Reed-Solomon
(allerdings mit einer sehr optimierten = Assemblerlastigen Variante
Das nachprogrammieren dürfte etwas dauern, dafür dann eben schneller)

Dass die Platte von allein CRC-Checks durchführt, wäre mir neu

Hmm...

Modern drives make extensive use of error correction codes (ECCs), particularly Reed–Solomon error correction.

Sorry

(Sogar da steht Reed-Solomon, aber dann ists wohl mit spezieller Hardare so extrem optimiert,
dass ein einzelner Programmierer davon sowieso nur träumen kann.
Mit meiner In-einem-Tag-gemacht-Implementierung komm ich jedenfalls auf keine
SSD-Geschwindigkeiten bei der Verarbeitung, auch nicht HDD,
obwohl die ganze Haupt-CPU statt nur der Plattencontroller rechnet.
Na gut, kein SSE/Intel-SIMD/..., keine GPU, nur normales C)

PS: Typische HDD-Blockgrößen sind 512 oder 4096 Byte

 

[fugyl]

Wieder was gelernt

Ich werde mir auf jeden Fall mal den Reed-Solomon-Algo zu Gemüte führen, aber wenn der wirklich so langsam ist wie du behauptest, bleibe ich beim XOR

Da ich - als Student - eigentlich eh nur mehr oder weniger sinnfreien Müll programmiere, kann ich das ja mal probieren. Und da ich - wie bereits erwähnt - eher der Theoretiker bin, bin ich auch dran intressiert einen neuen Algo fürs Wiederherstellen zu finden... wer weiß?

Warum ich trotzdem haufenweise Fehler in meinen Dateien habe, bleibt mir schleierhaft. Es ist aber definitiv Datenverlust da, habs selbst mal getestet, indem ich nen MD5-Hash von ner Win7-ISO in ner Textdatei gespeichert hatte und den nach einigen Monaten verglichen hab: Unterschiedlich (Die Datei war dementsprechend unbenutzbar)

Bei wichtigen, kleinen Dateien benutze ich (natürlich abgesehen von regelm. Backups) WinRAR + Wiederherstellungsarchiv... ist aber nicht wirklich Sinn der Sache, deswegen mein Anliegen solch ein Programm zu schreiben^^

Wenn ich das wirklich mit meiner Methode des XOR-ens implementieren will, dürfte die Implementation in Asm ja nicht so schwer werden. Auf jeden Fall habt ihr mir sehr geholfen, vielen lieben Dank

Lieben Gruß
Fugyl

 

[sheel]

Zum Selbstmachen:
Folgendes erklärt sehr ausführlich, mit Beispielen usw.
http://downloads.bbc.co.uk/rd/pubs/whp/whp-pdf-files/WHP031.pdf

Da ich - als Student - eigentlich eh nur mehr oder weniger sinnfreien Müll programmiere, kann ich das ja mal probieren. Und da ich - wie bereits erwähnt - eher der Theoretiker bin, bin ich auch dran intressiert einen neuen Algo fürs Wiederherstellen zu finden... wer weiß?

Viel Glück dabei
In dem Gebiet ist noch lang nicht fertiggeforscht,
es gibt noch immer großes Potenzial für Verbesserungen

 

[ComFreek]

Vor allem wenn du programmierst würde ich dir ein Versionskontrollsystem sehr empfehlen!
In Kombination mit einem externen "Gitarchiv" ist Datenverlust - regelmäßige Commits und Pushs vorausgesetzt - ausgeschlossen.

Da bieten sich beispielsweise GitHub oder Bitbucket an. Bei GitHub musst du für private Repositories zahlen, bei Bitbucket allerdings nicht (allerdings dann die Anzahl der erlaubten Teammitglieder). Alternativ könntest du auch eine Cloudanbindung nutzen - es existieren ja mittlerweile sehr viele kostenfreie Cloudanbieter.