Update: Als ich noch einmal darüber nachdachte, fand ich eine Methode, mit der eine Datei mit einem eigenen MD5 viel schneller erstellt werden kann als ursprünglich erklärt. Die neuen Kosten sollten ungefähr 2 65 Elementaraufrufe von MD5 betragen, d. H. Viel weniger als die 2 119, über die ich gesprochen habe; es wäre sogar technologisch machbar (mit einem Budget in Millionen von Dollar - aber nicht in Milliardenhöhe). Eine Beschreibung der neuen Methode finden Sie am Ende.
Ursprüngliche Antwort:
Nehmen wir an, MD5 ist ein "perfekter" Hash Funktion, die als zufälliges Orakel modelliert werden kann. Ein zufälliges Orakel ist eine Funktion, für die Sie nichts über die Ausgabe einer bestimmten Eingabe wissen, bevor Sie sie einmal ausprobieren. Für ein zufälliges Orakel ist die beste Methode, um das zu erreichen, wonach Sie suchen, die Hoffnung: Sie versuchen es mit zufälligen Eingabenachrichten, bis Sie eine finden, die einen eigenen Hash enthält. Die Frage ist dann: Welche Größe von Eingabenachrichten sollten Sie verwenden?
MD5 verarbeitet Daten durch Hinzufügen einiger Auffüllbits (mindestens 65, höchstens 576), sodass die Länge ein Vielfaches von 512 beträgt. Dann werden die Daten in 512-Bit-Blöcke aufgeteilt. Die Kosten für das Hashing einer Nachricht sind direkt proportional zur Anzahl solcher Blöcke. Das heißt, Für eine n -Bit-Nachricht betragen die Kosten Ceil ((n + 65) / 512) . Eine n -Bit-Nachricht bietet andererseits n-127 Teilsequenzen von 128 Bit. Längere Nachrichten machen es wahrscheinlicher, dass jede Nachricht (linear) erfolgreich ist, die Verarbeitung kostet jedoch mehr (auch linear). Die Nachrichtenlänge ist also größtenteils neutral, mit der Ausnahme, dass der durch das Auffüllen implizierte Overhead bei Verwendung von Kurznachrichten größer ist. Insgesamt finden Sie bei ausreichend großen Zufallsnachrichten (z. B. 8 kB) eine Nachricht, die ein eigenes MD5 enthält, dessen durchschnittliche Kosten etwa 2 119 sup> MD5-Elementarbewertung betragen. Eine elementare Auswertung von MD5 verwendet einige hundert Taktzyklen auf einer neueren CPU, und 2 sup> ist mit der heutigen Technologie (und auch mit der Technologie von morgen) völlig unerreichbar. P. >
(Die "große Datei mit allen 128-Bit-Sequenzen", von der Graham Lee spricht, ist nur ein Sonderfall dieser generischen Methode mit einer einzigen sehr großen Nachricht.)
Jetzt ist MD5 Es ist allgemein bekannt, dass kein zufälliges Orakel ist - schon allein deshalb, weil Kollisionen auf MD5 effizient berechnet werden können, was mit einem zufälligen Orakel nicht möglich ist. Es ist daher denkbar, dass Verknüpfungen vorhanden sind, die Schwachstellen in der MD5-Struktur ausnutzen. Mir ist jedoch kein Angriff bekannt, der zu einer Nachricht führt, die ein eigenes MD5 enthält. Dies scheint ein Problem in der Nähe des Vorbildwiderstands zu sein, was als wesentlich schwieriger angesehen wird als Kollisionen.
Neue Methode:
MD5 wird wie die meisten (wenn nicht alle) Hash-Funktionen gestreamt : Wenn eine lange Eingabe verarbeitet wird, erfolgt dies in einem Durchgang, wobei ein kleiner Betriebszustand mit fester Größe beibehalten wird. Speziell für MD5 hat der Betriebszustand eine Größe von 128 Bit (16 Byte), und Daten werden in Blöcken von 512 Bit (64 Byte) verarbeitet. Eine wichtige Konsequenz ist die folgende: Wenn Sie Eingaben m und m || x haben ("||" bedeutet Verkettung) und Sie beide MD5 ( m ) und MD5 ( m || x ), dann sind die zusätzlichen Kosten, die zur Berechnung des zweiten erforderlich sind, proportional zur Größe von x , jedoch NICHT auf die Größe von m . Mit anderen Worten, wenn Sie eine 1-Gigabyte-Eingabe m haben, berechnen Sie MD5 ( m ) und möchten dann die MD5 von m berechnen Durch einen 20-Byte-Trailer x kann dieser zweite MD5 einen Großteil der für den ersten geleisteten Arbeit wiederverwenden und ist nahezu kostenlos.
Dies führt zu dem folgenden Algorithmus So finden Sie eine Nachricht m , die ein eigenes MD5 enthält:
- Beginnen Sie mit einem Wert m .
- Berechnen Sie MD5 ( m ). Wenn es Teil von m ist, beenden Sie (wir haben unsere Nachricht gefunden).
- Ersetzen Sie m durch m || x wobei x so ist, dass die Sequenz der letzten 128 Bits von m || x nirgendwo in m erscheint.
- Schleife zu 2.
ol> Das Finden des richtigen " x " - Werts bei jedem Schritt kann mithilfe einer De Bruijn-Sequenz a erfolgen >. Verwenden Sie B (2, 128) als Basissequenz, wenn jedes x ein einzelnes Bit ist. Wenn Sie eine byteorientierte Lösung wünschen (die Nachricht m muss aus einer ganzzahligen Anzahl von Bytes bestehen, und MD5 ( m ) muss in m em erscheinen > an einer Bytegrenze), verwenden Sie dann B (256, 16) .
Um die durchschnittliche Anzahl von Iterationen zu berechnen, die zum Auffinden eines Treffers erforderlich sind, müssen Sie berücksichtigen, dass bei der Iteration n die Nachricht m n unterschiedliche Teilsequenzen enthält von 128 Bits (oder 16 Bytes), so dass die akkumulierte Gesamtzahl der Vergleiche n ( n +1) / 2 beträgt. Unter der Annahme, dass MD5 ein zufälliges Orakel ist, hat jeder Vergleich die Wahrscheinlichkeit 2 , ein Treffer zu sein, so dass n im Durchschnitt so sein muss, dass n ( n +1) / 2 = 2 sup> 128 sup> - was zu n = 2 64,5 sup> -Iterationen führt.
Bei jeder Iteration wird jedoch ein MD5 ( m || x ) berechnet, wobei x sehr klein ist (ein Bit oder ein Byte) ) und MD5 ( m ) wurde berechnet; Dies erfordert normalerweise nur eine zusätzliche elementare MD5-Berechnung (Verarbeitung eines einzelnen 64-Byte-Blocks). (Wenn x Bits sind, muss für nur eine Iteration in 512 zwei Blöcke verarbeitet werden. Wenn x Bytes sind, wird dies zu einer Iteration in 64. )
In jedem Fall wird der schwierige Teil die Suche sein. Um alle Teilsequenzen in einem Index zu erhalten, der für eine schnelle Suche geeignet sortiert ist, ist eine Menge schneller RAM erforderlich, was wahrscheinlich viel teurer wäre als die Berechnung des 2 sup> 64,5 sup> MD5. Einige De Bruijn-Sequenzen ermöglichen jedoch eine schnelle, speicherfreie Dekodierung. Daher können wir mit diesem Algorithmus eine Nachricht m finden, die ihre eigene MD5 enthält, und zwar zu Kosten nahe 2 65 sup> -Berechnungen von MD5. Die resultierende Nachricht hat eine Länge von ungefähr 3,3 * 10 sup> 18 sup> Bytes, dh ungefähr eine Million moderner Festplatten (achtmal so viel, wenn wir eine byteorientierte Lösung wünschen).
Es Es kann angemerkt werden, dass der Algorithmus mit einer beliebigen Nachricht m beliebiger Größe gestartet werden kann. Dieser Startpunkt wird am Anfang der vom Algorithmus erzeugten Self-MD5-Datei angezeigt.
(In meiner ursprünglichen Antwort war der Fehler in diesem Satz: "Längere Nachrichten machen es wahrscheinlicher, dass jede Nachricht (linear) erfolgreich ist, die Verarbeitung kostet jedoch mehr (auch linear)." Wie oben erläutert, länger Nachrichten können immer noch sehr effizient verarbeitet werden, solange wir sie durch Wiederverwendung eines gemeinsamen Präfixes wie in meinem neuen Algorithmus generieren.)