Vigereere mit CBC-Mode und Teilklartext knacken?

Yellow · Feb 13, 2008

Guten Tag Leute!

Ich sitze nun seit ca 5 Wochen vor einem Verschlüsseltem Text der mit dem Vigeneere Algrorithmus verschlüsselt wurde. Doch um die Sache Komplizierter zu machen wurde das im CBC-Modus verschlüsselt.

Ein Teil des Plaintextes ist bekannt!

Meine Frage lautet nun: "Wie knacke ich am besten den Chipertext?".

Ich habe mich mit dem Vigeneere Algorithmus denke ich ganz gut vertraut gemacht. Das man eine reine Vigeneere mit einer Analyse knacken kann ist mir bekannt. Doch ich komme mit dem CBC einfach nicht zurecht!

Ich habe mich schon öfters hingesetzt und mit C und C++ versucht eine Brute and Force dafür zu schreiben. Doch irgendwie bin ich entweder zu dumm oder ich mache es mir einfach zu schwer!?

Kann mir bitte einer einen Rat geben wie ich sowas am besten knacke?

Liebe Grüße

Yellow

PS: Für die die gerne wissen wollen wofür das ist, kann ich nur sagen das ich nichts unmoralisches etc vor habe. Es handelt sich einfach nur um eine Übung die ich einfach nicht hinbekomme!

Elderan · Feb 14, 2008

Hallo,
wenn du einen Teil des Klartextes kennst, sollte das doch eigentlich kein Problem sein? Berechne einfach für diesen Abschnitt den Schlüssel, und wenn du eine ganze Schlüssellänge so zusammen bekommst, bist du doch schon fertig.

Wenn man keinen Plaintext kennt, ist das Vorgehen auch nicht viel schwerer.

Angenommen du kennst die Schlüssellänge, dann betrachtest du jeden Buchstaben der mit dem selben Schlüsselbuchstaben verschlüsselt wurde.
Diese kannst du dann analysieren, fängst beim 1. Buchstaben an, entschlüsselst diesen mit dem Geimtextbyte der vor diesem Stand usw..
Am Ende kannst du dann einfach die Buchstabenhäufigkeit ermitteln, verstellen um wieviel diese verschoben ist, fertig.

Denn der CBC Mouds lässt sich bei der polyalphabetischen Substitution sehr leicht entfernen.

Angenommen du hast den IV von 3, dann folgt:

Code:

  5 6 6  <= Plaintext
  1 2 3  <= Key
  6 8 9  <= Ohne CBC (Plaintext + Key)

3  5  6   6   <= IV + Plaintext
   8  15  23  <= Plaintext + letzter Geheimtext
   1  2   3 
3  9  17  26  <= Mit CBC


So nun die Umkehrung:
  9  17  26 
- 3   9  17
= 6   8   9 <= Geheimtext ohne CBC

Wenn du den CBC erstmal entfernt hast, ist der Rest ja bekannt

Yellow · Feb 14, 2008

Lieber Elderan!

Danke für deine Hilfestellung.

Doch muß ich gestehen das ich das verschlüsseln mit dem CBC nicht wirklich verstanden habe.

Ich kenne nur den Chipper und einen Teilplain. Kenne aber keinen IV.

Ich habe schon locker 8-10 PDF Dateien auf meinem Rechner die mir die Verschlüsselung mit Ceasar und Vigeneere erklären. Doch ich raffe die Berechnung mit dem IV nicht.

Es wird immer nur sehr sparsahm auf den IV eingegangen. Und ich komme leider mit den FORMELN wie diese immer erklärt sind nicht klar.

Ich wäre dir wirklich sehr sehr dankbar wenn du mir eine einführung in den CBC-Modus erleutern könntest. Ich habe Google und Co schon sooft benutzt das ich schon fast am aufgeben war. Doch dank deines Beitrages, sehe ich wieder etwas Hoffnung das ich das vieleicht doch nochmnal verstehen

Bist du so nett und gibst mir einen Einblick in den CBC-Modus und vieleicht auch mit einem Netten Beispiel?

Wenn nicht dann danke ich dir auf jedenfall schonmal für den bereits geschriebenen Beitrag.

Liebe grüße

Yellow

Elderan · Feb 14, 2008

Hallo,
hmm zum CBC gibts eigentlich nicht viel zu erzählen.

Du wählst einen meist zufälligen Initialisierungsvektor, bei der polyalphabetischen Substitution wäre dies dann eben 1 Buchstaben, bei AES o.ä. ein 128 Bit Block.

Wenn du nun einen Block verschlüsseln möchtest, machst du erst eine XOR Verknüpfung von dem Block mit dem letzten Geheimtext. Das Ergebnis wird dann verschlüsselt.

Der 1. Block, den man verschlüsselt wird XOR (o.ä.) Verknüpft mit dem IV.

Code:

Hast den Plaintext
1 2 3

Key:
4 5 6

Und den IV = 3, dann gehst du wie folgt vor:

1. Block + IV (bzw. meistens XOR)
1 + 3 = 4

Dann wird 4 verschlüsselt:
4 + 4 = 8 

Oder anders dargestellt:

  1  2  3  | Plaintext
  4        | Plaintext XOR/+ letzten Geheimtext
  4  5  6  | Key
3 8        | Ausgabe/Geheimtext

So, wenn du nun 1+3=4 verschlüsselt hast, gehst du zum nächsten Block, also 2 und verknüpfst diesen mit dem letzten Geheimtext, also 8

   1   2   3  | Plaintext
   4  10      | Plaintext XOR/+ letzten Geheimtext
   4   5   6  | Key
3  8  15      | Geheimtext


Dies machst du immer so weiter

Oder z.B. als PHP Code:

PHP:

<?php
$key = array(1,2,3,4);
$plaintext = array(5, 6, 7, 8, 9, 10, 11, 12);
$iv = 3;
$geheimtext = array($iv);

$letzter_geheimtext = $iv;
for($i=0;$i<count($plaintext);$i++) {
   //CBC 'anwenden', also aktueller Plaintext XOR (oder +) des letzten Geheimtextes
   $cbc_anwenden = $plaintext[$i] + $letzter_geheimtext;
  
   //Eingabe normal verschluesseln
   $verschluesselt = $cbc_anwenden + $key[$i%count($key)];

   //Ergebnis zur Ausgabe hinzufuegen
   $geheimtext[] = $verschluesselt;

   //Letzer Geheimtext = aktueller Geheimtext
   $letzter_geheimtext = $verschluesselt;
}

echo "<pre>";
print_r($geheimtext);
?>

Normalerweise verwendet man eine XOR Verknüpfung (dieses Plus mit Kreis in der Grafik von Wikipedia), hängt aber eben von der Implementierung von Vigen?re ab (wobei ich noch nie von einem CBC für Vigen?re gehört habe, der auch nicht viel bringt).

Der IV ist meistens der erste Geheimtextblock, hängt aber alles von der Implementierung ab

Yellow · Feb 14, 2008

Lieber Elderan!

Ich kann dir garnicht ausdrücken wie sehr ich mich über deine Beiträge freue *schleim*. Es ist sehr hilfreich. Besonders noch der PHP code

Wenn ich von dir jetzt nicht zu viel verlange: "Wie kann ich das jetzt wieder entschlüsseln wenn ich den IV nicht kenne?".

Hey auf jedenfall erstmal ein Dickes danke. Dieser Beitrag wird bestimmt auch vielen Anderen Helfen die mal diese Frage haben sollten

Yellow

Elderan · Feb 14, 2008

Hallo,
den IV brauchst du nur für die Entschlüsselung des 1. Geheimtextblock, alle anderen kannst du ohne IV entschlüsseln.
Schau dir mal das Bild bei Wikipedia für die entschlüsselung an, evt. hilft dir das weiter. Hab keine Zeit mehr mehr zu schreiben

Yellow · Feb 14, 2008

Ich danke dir jetzt erstmal für deine Mühen!

Wenn ich nicht weiterkomme, werde ich mich einfach nochmal melden !

Danke Elderan!

Elderan · Feb 15, 2008

Hallo,
das freut mich, ansonsten hier der (ungeteste) Code zum entschlüsseln:

PHP:

<?php
$key = array(1,2,3,4);
$plaintext = array(5, 6, 7, 8, 9, 10, 11, 12);
$iv = 3;
$geheimtext = array($iv);

$letzter_geheimtext = $iv;
for($i=0;$i<count($plaintext);$i++) {
   //CBC 'anwenden', also aktueller Plaintext XOR (oder +) des letzten Geheimtextes
   $cbc_anwenden = $plaintext[$i] + $letzter_geheimtext;
  
   //Eingabe normal verschluesseln
   $verschluesselt = $cbc_anwenden + $key[$i%count($key)];

   //Ergebnis zur Ausgabe hinzufuegen
   $geheimtext[] = $verschluesselt;

   //Letzer Geheimtext = aktueller Geheimtext
   $letzter_geheimtext = $verschluesselt;
}

echo "<pre>";
print_r($geheimtext);

//Entschluesseln:
$iv = $geheimtext[0];
$letzter_geheimtext = $iv;

$plaintext = array();

for($i=1;$i<count($geheimtext);$i++) {
  $klartext = $geheimtext[$i] - $key[ ($i-1)%count($key) ]; //Entschluessen, $i-1 da $i hier bei 1 anfängt
  $plaintext[] = $klartext - $letzter_geheimtext; //CBC rückgängig machen
  $letzter_geheimtext = $geheimtext[$i];
}

print_r($plaintext);

?>

Den CBC könnte man auch ohne die Entschlüsselung löschen, in etwa so:

PHP:

<?php

$geheimtext = array(...Wie Oben...);
$geheimtext_ohne_cbc = array();
for($i=1;$i<count($geheimtext);$i++)
  $geheimtext_ohne_cbc[] = $geheimtext[$i]-$geheimtext[$i-1];

?>

Ist aber alles ungetestet, aber so in etwa würde es aussehen.

Yellow · Feb 15, 2008

Ich weiß nicht was ich sagen soll Elderan, außer vieleicht ein dickes...

DANKE SCHÖN

Werde den Code in C++ umschreiben !

PS: Wenn ich fertig bin mit dem Proggy, sage ich bescheid. Kann dann gerne den Source rausgeben