Kollision in einer reduzierten SHA1 erzeugen

17.12.2014, 16:21

Shalec

Kollision in einer reduzierten SHA1 erzeugen

Hallo Allerseits,

Ich habe hier zwei eMails. Das Original hat 355 Zeichen, die zur Kollision zu erzeugende eMail ~357 Zeichen.

Beide Mails sind nahezu identisch. Es geht dabei um einen Kaufpreis. Dieser wird 2x in der Mail erwähnt und unterscheidet sich in einer 10er Potenz.

Die einzige Stelle, an der Änderungen vorgenommen werden können, ist dieser Eintrag:

" > ESMTP id o3NDN2so002931711259325\n",

Der Rest würde sofort auffallen.

Dabei habe ich mich allerdings erstmal nur dieser Sequenz gewidmet:
002931711259325

Und mittels Geburtstagsparadoxon und BruteForce ein Ergebnis erhofft.

(Anhand meiner Angaben ist es unmöglich die Aufgabe zu reproduzieren, aber ich hoffe, dass man eine kleine Ahnung erhält, worum es ungefähr geht)

Nun zur reduzierten SHA1: (Magma)

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

SHA1Light := function(s)
	//
	// 	Eingabe:
	//		s:	Klartext
	// 	Ausgabe: 
        //             TextToHex(s) -> Hexadezimalwert des Strings s
	//		SubString(String, 1,7) -> ersten sieben Stellen des Strings
        //             SHA1(string) -> Hashwert vom string mittels SHA-1
	//
      return Substring(SHA1(TextToHex(s)), 1, 7);
end function;

Es gibt also nur $\begin{eqnarray*} 7^{16} \end{eqnarray*}$ Möglichkeiten. Nach dem Geburtstagsparadoxon würden schon $\begin{eqnarray*} 1.18\cdot \sqrt{16^{7}} \end{eqnarray*}$ Tests genügen, um mit hoher Wahrscheinlichkeit eine Kollision zu erhalten.

Aber das Ziel zu Bruteforcen dauert mir zu lange und ist auch sehr Speicherlastig.
Welche Methoden gibt es denn, um einen solchen SHA-1 auszuhebeln? Kann mir da jemand ein paar Tipps geben?

Viele Grüße und vielen Dank im Voraus.

Edit://
Ich vermute, dass selbst ein Meet-In-The-Middle-Angriff ins leere laufen könnte, da der Text zu lang ist. Laut einem Skript muss man dazu die Kompressionsfunktion invertieren können. D.h. die substring() Funktion, vermutlich.

Neue Frage »

Antworten »

Kollision in einer reduzierten SHA1 erzeugen

Verwandte Themen