CRC32 Kollision

Es hängt ganz davon ab, was Sie "bedeutet " Nachricht". Wenn Sie anfügen können vier bytes Kauderwelsch auf eine der Nachrichten. (I. E. vier bytes, die keine Bedeutung haben, innerhalb des Kontextes der Nachricht.) Dann wird es trivial, im wahrsten Sinne des Wortes.

Denken in Bezug auf die bits bewegen sich durch die CRC32-state-Maschine.

CRC32 basiert auf einem galois-feedback shift register, jedes bit in seinem Zustand ersetzt werden, mit der Induktion von 32 bits der payload-Daten. Bei der Induktion der jedes bit, die Positionen angegeben, die durch das Polynom wird exklusiv ored mit der Sequenz beobachtet vom Ende der Schieberegister. Diese Sequenz wird nicht beeinflusst durch die Eingabe von Daten, bis das Schieberegister gefüllt worden.

Als ein Beispiel vorstellen, wir haben ein Schieberegister gefüllt mit Anfangszustand 10101110, Polynom 10000011, und füllen mit unbekannten bits, X.

Polynomial *     **  |feedback (End of SR.)
State      10101110     0
State      X1010111     1
State      XX101000     0
State      XXX10100     0
State      XXXX1010     0
State      XXXXX101     1
State      XXXXXX01     1
State      XXXXXXX1     1
State      XXXXXXXX     0

Das feedback nicht in Form von X-bis der SR wurde gefüllt!
Also, um zum erzeugen einer Nachricht mit einer vorgegebenen Prüfsumme, nehmen Sie Ihre neue Nachricht, generiert die CRC und arbeiten heraus, dass es die nächsten 32 bits von feedback. Dies können Sie tun in 32 Stufen der CRC-Funktion. Sie brauchen dann zur Berechnung der Wirkung dieser Rückmeldungen auf die Inhalte der Schieberegister.

Einen shortcut dafür ist die pad Ihre Nachricht mit vier null-bytes und betrachten Sie dann die Prüfsumme. (Prüfsumme ist der Zustand der SR am Ende, die, wenn Sie aufgefüllt mit vier null-bytes ist der Einfluss, den feedback und die leere bytes.)

Exklusiv-ODER, dass der Einfluss auf die Prüfsumme Wert, den Sie möchten, ersetzen Sie die vier-byte-trailer-mit diesem berechneten Wert und regenerieren die Prüfsumme. Man könnte dies mit einem Programm generiert eine CRC32 -, hex-editor und einem Taschenrechner, kann hex.

Wenn Sie möchten, erzeugen Sie zwei Nachrichten, die sowohl den vollen Sinn und enthalten nicht trailing garbage, werden die Dinge ein wenig härter. Identifizieren eine Anzahl von Abschnitte, die Sie schreiben können, plausible alternativen auf, mit exakt der gleichen Länge.

Mit englischen Prosa-als ein Beispiel.
"Ich denke, dass das funktionieren kann"
und
"Ich glaube, dass in diesem Ansatz"
Haben ähnliche Bedeutungen, und genau die gleiche Länge.

Ermittlung genug Beispiele in Ihrer Nachricht ist das knifflige bit (es sei denn, Sie wollen zu betrügen mit Leerzeichen!) CRC-32 ist linear, sofern die Daten den richtigen offset in der Nachricht. Also CRC([messagea][padding])^CRC([padding][messageb])=CRC([messagea][messageb])
Es gibt einige Vorsichtsmaßnahmen, mit word-alignment, die Sie benötigen, zu bewältigen, als ein allgemeiner Hinweis, den Sie erweitern möchten die Passagen in den "festen" Teil der Nachricht. Als eine Allgemeine Regel, die Sie haben wollen alternativen für die n*1.5 Passagen, wobei n die Größe des CRC.

Können Sie nun die Berechnung der CRC, dass die Skelett-Nachricht hat den Eindruck, dass jede alternative passage auf, und dann erstellt eine Tabelle zum Vergleich der Einfluss, den jede alternative für jeden Durchgang haben würde. Sie müssen dann wählen Sie alternativen, die sich ändern wird die Skelett-CRC zu entsprechen, die CRC, die Sie wollen. Das problem ist eigentlich ganz lustig zu lösen, erst mal alle finden alternativen, eindeutig zu wenig modifizieren, wenn Sie, dass etwas sich ändern muss für Ihren CRC, wählen Sie diese alternative und Falten Sie es Einfluss in die SFB, dann gehen Sie wieder rund. Das sollte reduzieren, die Lösung der Raum, den Sie dann suchen müssen.

Ist das schon eine schwierige Sache, um code, aber es würde generieren Ihre Kollisionen in einer sehr kurzen Zeitspanne.

InformationsquelleAutor scruffy_brit

Gehe ich davon aus, dass du meinst, "Nachricht" statt "Schlüssel".

Wenn Sie zulässig sind, wählen Sie " beide "Tasten", dann brute-force Recht schnell da eh den Geburtstag paradox. Pick zufällige Nachrichten, berechnen Sie Ihre CRC-Fehler, denken Sie daran, alle von Ihnen und der zugehörigen CRC-Fehler, und jeder neue hat mehr und mehr Chancen zu kollidieren mit einer bestehenden ein, wie Sie akkumulieren. Ehrlich gesagt, erwarte ich, dass dieser Ansatz schneller auf einem modernen computer als die Suche Ansätze bekannt zu machen CRC32 kollidieren.

InformationsquelleAutor Pascal Cuoq

Gerade gestern gab es diese Frage hier auf SO, ein paar von Zeigern erwähnt, kann es Ihnen helfen.

InformationsquelleAutor fvu

spoof macht genau das. Es erfordert keine brute-force.

InformationsquelleAutor Mark Adler