Hallo,

eine Frage zum Thema Verschlüsselungen: Man liest häufig darüber, wie viele Schlüssel pro Sekunde ein Rechner prüfen könnte, und davon ausgehend wie lange es dauern würde, bis mit Brute-Force eine Verschlüsselung geknackt wäre.

Das hört sich rechnerisch gut an, aber wie würde denn ein Brute-Force-Algorithmus entscheiden, ob der gerade geprüfte Schlüssel der richtige ist?
Das Ziel der Entschlüsselung ist es doch, an unbekannte Informationen zu gelangen, d.h. man hat vorher keine Ahnung, was der originale Inhalt ist.
Der Algorithmus müßte nun nach jeder Entschlüsselung prüfen, ob das Ergebnis korrekt ist. Aber wie könnte er das entscheiden, da ihm garnicht bekannt ist, nach was er denn eigentlich sucht?

Viele Grüße,
Holger


Moderiert von UGrohne: Topic aus Algorithmen, Optimierung und Assembler verschoben am Di 30.10.2007 um 07:40

Das stimmt so nicht ...

Wenn Du BruteForcen willst, handelt es sich i.d.R. um einen Known-Plaintext- oder Known-Chiffre-Text-Angriff, d.h. Du weißt, wonach du suchst.

Beispiel: Knacken eines Windows-Passwortes:
Gegeben: Ein Hash
Bekannt: Verfahren, diesen Hash zu berechnen
Gesucht: Die Eingabe, die das gewünschte Ergebnis liefert
Dauer: <3 Sekunden mit Rainbow-Table , Ansonsten etwa 7 Tage (mit moderater Heim-Hardware)

Knacken von RSA (BruteForcen des Privaten Schlüssels
Gegeben: Public Key
Bekannt: X^Pub^Priv = X mod N
Gesucht: Priv
Dauer: ~1 Jahr bei 1024-Bit-Schlüsseln (Bei Nutzung von ~500 Rechnern im Verbund)

Man brauch also lediglich seine Abbruchbedingung auf den Fall zu eichen, in dem eine Bekannte Eigenschaft des zu knackenden Krypto-Systems zutrifft. Wenn Du also bei einem Passwort-Hash dessen Gleichheit mit einem weiteren (ggf. hardcodierten*) Schlüssel prüfen willst, prüfst Du lediglich mit XOR von deinem gesuchten Schlüssel mit deinem letzten Ergebnis ab.

*Das Hardcodieren in den ASM-Source kann man zur Code-Optimierung nutzen und damit Rechenzeit einsparen.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Hallo,

das heißt aber, daß Brute-Force nur für einen kleinen Bereich des Entschlüsselns sinnvoll ist.
Es sind viele Vorkenntnisse notwendig, um zum Erfolg zu kommen.

Eine wie auch immer geartete Datendatei, die mit irgendeinem Algorithmus verschlüsselt wurde, sollte dann ein fast unlösbares Problem darstellen. Denn wenn man nicht einmal weiß, ob es sich um eine Textdatei, eine Zip-Datei, ein Word-Dokument, usw. handelt, weiß man auch nicht, wonach man suchen muß für das Abbruchkriterium.
Und auf alle bekannten und unbekannten Dateiformate zu prüfen ist nicht möglich.

Wie würde denn ein Kryptologe an so eine Aufgabe rangehen?

Viele Grüße,
Holger

Holgerwa hat folgendes geschrieben:

Und auf alle bekannten und unbekannten Dateiformate zu prüfen ist nicht möglich.

Wenn man nur die ersten 100 Bytes der Datei entschlüsselt und in alle häufig vorkommenden Dateiheader sucht, stellt das sicher kein so großes Problem dar.

Wenn man weiß, dass es sich um einen Text handelt, kann man auch abbrechen, wenn z.b. keine Sonderzeichen (außer Punkt, Komma, etc) im entschlüsselten Text auftauchen.

Hallo,

aber das weiß doch auch derjenige, der ursprünglich verschlüsselt hat. Und wenn dem an der Sicherheit der Daten gelegen ist, wird er kein Standard-Dateiformat nehmen, auf das ein "normaler" Entschlüsseler prüfen würde.
Abgesehen davon, daß auch der Algorithmus nicht bekannt wäre, also zusätzlich mit jedem bekannten Algorithmus geprüft werden müßte um herauszufinden, welcher verwendet wurde.

Für jeden auszuprobierenden Schlüssel müßte also mit jedem bekannten Algorithmus auf jeden Dateiheader geprüft werden, also benötigt jeder Schlüssel AnzahlAlgorithmen * AnzahlHeader Versuche um festzustellen, daß er nicht der richtige ist.
Und das in dem Glauben, daß zufälligerweise ein Dateiformat für die ursprüngliche Datei verwendet wurde, auf das auch geprüft wird.

Ist das nicht ziemlich aussichtslos, um nicht zu sagen sinnlos? Von Zufallstreffern abgesehen.

Viele Grüße,
Holger

Holgerwa hat folgendes geschrieben:

aber das weiß doch auch derjenige, der ursprünglich verschlüsselt hat. Und wenn dem an der Sicherheit der Daten gelegen ist, wird er kein Standard-Dateiformat nehmen, auf das ein "normaler" Entschlüsseler prüfen würde.

Also das glaube ich nicht. Wenn ich ein JPG-Bild verschlüsseln wollen würde, dann wandel ich es ja vorher nicht erst in ECW (so'n unbekanntes Grafikformat) um, nur damit jemand, der eventl. versucht, die Datei zu knacken, es schwerer haben wird. Ich gehe ja davon aus, dass die Verschlüsselung sicher ist.

Holgerwa hat folgendes geschrieben:

Abgesehen davon, daß auch der Algorithmus nicht bekannt wäre, also zusätzlich mit jedem bekannten Algorithmus geprüft werden müßte um herauszufinden, welcher verwendet wurde.

Fast alle Verschlüsselungsprogramme (inkl. alle Packerprogramme mit Verschlüsselungsoption) verwenden eigene Dateiendungen oder zumindest einen Header, der immer gleich ist. Das stellt glaub ich kein wirkliches Problem dar.

Hallo,

da stimme ich zu, wenn ich mal eben schnell was verschlüsseln will, dann mache ich das auch so.

Ich dachte mehr an jemanden, der etwas so schützen will, daß es so sicher wie möglich ist; der sich also im Vorfeld Gedanken darüber macht, weil die Daten sehr wichtig sind.

Es würde ja schon genügen, ein eigenes Dateiformat zu kreieren, und das Ganze wäre gegen solche Entschlüsselungsversuche 100% immun.

Aber das kann es doch nicht sein, denn auf diese Idee würde dann wohl jeder kommen, der absolut verhindern will, daß die Daten entschlüsselt werden.

Viele Grüße,
Holger

Wenn aber dein Dateiformat irgendwie bekannt wird, dann ist das wieder umsonst. Eine Verschlüsselung gilt in der Regel nur dann als halbwegs sicher, wenn sie auch dann Angriffen standhält, wenn der Angreifer das Verfahren kennt. Security by obscurity ist in der Regel keine so gute Idee. Daher findet man solche einfachen Versuche, die Sicherheit zu erhöhen, auch recht selten - sie bringen einfach nichts .

Holgerwa hat folgendes geschrieben:

Eine wie auch immer geartete Datendatei, die mit irgendeinem Algorithmus verschlüsselt wurde, sollte dann ein fast unlösbares Problem darstellen. Denn wenn man nicht einmal weiß, ob es sich um eine Textdatei, eine Zip-Datei, ein Word-Dokument, usw. handelt, weiß man auch nicht, wonach man suchen muß für das Abbruchkriterium. Und auf alle bekannten und unbekannten Dateiformate zu prüfen ist nicht möglich. Wie würde denn ein Kryptologe an so eine Aufgabe rangehen?

Wenn man in den verschlüsselten Daten keine Muster irgendeiner Art kennt, wird es sehr schwierig bis unmöglich. Die meisten Dateiformate enthalten jedoch wiederkehrende Muster, z.B. einen Header, der das Format anzeigt und in der Praxis kann der Kryptologe schon meistens Vermutungen anstellen, worum es sich handeln könnte.
Ein Beispiel aus der historischen Praxis: Die britischen Kryptologen, die während des 2. Weltkriegs den Funkverkehr der deutschen U-Boote entschlüsselt haben, haben sich an in Funkmeldungen häufig wiederkehrende Begriffe wie Positionsangaben oder Wetterberichte gehalten.

Stefan

In meinem Verschlüsselungsprogramm läuft standartmäßig vor dem verschlüsseln eine spezielle zip Kompression über die Daten die einen 8 Byte Header ohne jegliche visuelle Auffälligkeiten erzeugt. Die Verschlüsselung selber ist eine Weiterentwicklung des OTP (One-Time-Pad).
Ich gehe bisher davon aus das Daten die ich damit verschlüssele recht gut aufgehoben sind.
Ist natürlich relativ, denn auch XOR sieht auf den ersten Blick erstmal ganz fein aus.

aber mit burteforce kommt man doch auch nicht weit, wenn die daten doppelt verschlüsselt wurden, oder ? ich denke, dass das dann nicht ganz so einfach wird.

mfg

Das würde mich auch interessieren... Denn wenn man mit einem Programm wie Truecrypt 2 Mal verschlüsselt kann ja nicht geprüft werden ob ein Header stimmt, da dieser garnicht auftritt.

Aber eine merfache Verschlüsselung ist doch auch nichts anderes, als eine andere Verschlüsselung. D.h. eine zweifache Verschlüsselung ist nichts anderes als eine unbekannte Verschlüsselung. Und eine unbekannte Verschlüsselung bringt nicht viel mehr Sicherheit, als eine bekannte.

Gausi hat folgendes geschrieben:

Wenn aber dein Dateiformat irgendwie bekannt wird, dann ist das wieder umsonst. Eine Verschlüsselung gilt in der Regel nur dann als halbwegs sicher, wenn sie auch dann Angriffen standhält, wenn der Angreifer das Verfahren kennt. Security by obscurity ist in der Regel keine so gute Idee. Daher findet man solche einfachen Versuche, die Sicherheit zu erhöhen, auch recht selten - sie bringen einfach nichts .