C XOR Verschlüsselung entschlüsseln ohne den Key zu wissen?

O

ottofischer

Gast
Hallo zusammen, ich habe folgendes Problem.

Ich habe ein verschlüsselte Datei, die mit dem XOR verfahren "verschlüsselt" wurde.

Sprich wenn ich das Wort "Hallo" mit dem Key "abc" verschlüssel gehe ich so vor:
- H xor a
- a xor b
- l xor c
- l xor a
- o xor b
...

Meine Datei die ich habe wurde mit folgendem code "verschlüsselt".
Code:
# include <stdio.h>
# include <stdlib.h>
# include <string.h>

void crypt( char *in, char *out, unsigned char *passwort)
    {
    FILE *pin, *pout;
    int c;
    unsigned char *p;

    pin = fopen( in, "rb");
    pout = fopen( out, "wb");
    if( !pin)
        return;
    for( p = passwort; ; p++)
        {
        c = getc( pin);
        if( feof( pin))
            break;
        if( !*p)
            p = passwort;
        putc( c ^*p, pout);
        }
    fclose( pin);
    fclose( pout);
    }

void main()
    {
    char in[100];
    char out[100];
    unsigned char passwd[100];

    printf( "Eingabedatei: " );
    scanf( "%s", in);
    printf( "Ausgabedatei: " );
    scanf( "%s", out);
    printf( "Passwort: " );
    scanf( "%s", passwd);

    crypt( in, out, passwd);
    }

So wie man nun wieder entschlüsselt weiß ich, indem man das verschüsselte Wort wieder xor mit dem Key rechnet.

Meine Situatoin ist jetzt folgende:
Ich soll das Passwort rausfinden und den Text wieder entschlüsseln, ich kenne aber nicht das Passwort, dass zum verschlüsseln benutzt wurde. Ich besitze nur die verschlüsselte Datei und weiß, dass das benutze Passwort 4 Zeichen lang ist und das es sich bei dem verschlüsselten Text um einen deutschen Text handelt.

Wie komme ich jetzt nun an das Passwort? Ist es überhaupt möglich? Und hat jemand einen Lösungsansatz für mich ?
Wäre für Eure hilfe sehr dankbar!
 
Du kannst einfach alle möglichen Passwörter ausprobieren, das nennt sich Brute Force.
 
Liegt dir der entschlüsselte Text vor?
Ansonsten musst du alles durchprobieren. Wenn keine Sonderzeichen mit drin sind, sind es < 10 mio Möglichkeiten, das ist noch ertragbar.
 
Naja das Klassische Problem der Verschlüsselung ist: Kennst du das verfahren?
Ja: Dann nutze gezielt Schwachstellen in dem Verfahren aus.
Nein: Dann hilft nur Bruteforce oder Wörterbuchattacke.

Bei nahezu allen Verfahren werden gewisse Anfälligkeiten bewusst ausgenutzt was die Zeit des knackens verringert.

Ansonsten kannst du es auch so machen wie die Briten und Ami am Anfang gegen die Enigma.
Allen möglichen Blödsinn probieren und dann auf Sinnhaftigkeit überprüfen.

Wenn du also die Verschlüsselte Datei hast und weißt, dass das Passwort 4 Zeichen hat. Aber keine Ahnung hast ob sich dahinter nun ein Hash, AES, RSA, Caesar Shiffre etc. verschlüsselter Wert befindet gibts nur alles probieren und auf Sinnhaftigkeit überprüfen.
Die Frage ist also: Weißt du auch, dass die Datei XOR "Verschlüsselt" ist?
 
Nein ich weiß nicht was in dem Text drin steht.

Also müste ich alle 4-Zeichen-langen Möglichkeiten der Buchstaben a-z (groß und kleinschreibung) ausprobieren?
 
Falls nur Buchstaben drin vorkommen ja. Wenn alle möglichen Zeichen vorkommen können, hast du kaum eine Chance.
 
Wenn es ein deutscher Text gewisser Länger ist, würde ich einfach eine schleife bauen, die den encrypteten Text mit einem hochzählenden Passwort (es gibt nur 4.2 Mrd Möglichkeiten, dass ist schnell automatisiert) jedes mal decryptet und dann im Ergebnis-String nach häufigen deutschen Wörtern sucht, wie "und" oder den Artikeln (idealerweise sind diese Worte allerdings 4 Zeichen lang (z.B. "heit", "keit"), damit bei jeder PW-Änderung auch der String komplett anders wird). Wurden sie gefunden, landet das Passwort auf einer Liste der möglichen Passwörter. Diese Liste enthält dann einige tausend Passwörter (mit Glück auch weniger), die man mit gleichem Schema und anderen Suchwörtern verfeinern kann. Nach 3 oder 4 Runden (und effektiv vlt. 1 Minute Rechenzeit) ist die Passwort-Liste so kurz, die kannst du per Hand checken.

Oder du machst dir für deine Analyse andere Dinge von Vorteil, etwa die Bereiche in denen im ASCII-Code die Buchstaben/Satzzeichen liegen. Und dass ein Text zu über 90% aus solchen Zeichen bestehen müsste, oder er ist Datenmüll wegen dem falschen Passwort etc.
 
Ok sowas in der Art habe ich mir schon gedacht :-/
Naja okay dann werde ich mal versuchen, das zu programmieren.
Ergänzung ()

Aber wie kommst du auf die 4.2 Mrd Möglichkeiten ?
 
Zuletzt bearbeitet von einem Moderator:
Du kannst einfach die Buchstabenhäufigkeit ausnutzen, solange es ein Sprachtext ist. Dafür musst du nur die Häufigkeit für jede Stelle es Passworts berechnen und kannst dann daraus wieder aus Passwort schließen.

z.B. für die erste Stelle es Passworts musst du alle Stellen zählen die Positon mod 4 = 0 sind. Dass wird einfach für alle Stellen gemacht.

Bei einem deutschen Text kommt z.B. das "e" am Häufigsten vor, dann kannst du einfach ("e" XOR c) = k, machen, wobei c gerade der häufigstvorkommende Buchstabe für die erste Stelle des Passworts k sind

("e" XOR ("e" XOR k)) = k, da sich die "e"s aufheben.


Damit musst du keine Bruteforce machen, sondern nur viermal die Häufigkeit berechnen, sowie vielleicht bissel ausprobieren mit den häufigsten Werten, statt paar Millionen/Milliarden hast du vielleicht 16 Versuche :)
 
255^4

255 mögliche Zeichen für jede Stelle (da ich davon ausgehe, dass nicht die ganze UTF-8-Codebase Verwendung findet sondern nur übliche Zeichen im Rahmen des Standard-ASCII-Zeichensatzes).
 
@Sondai Die Buchstabenverteilung wollte ich auch vorschlagen, da das "E" ja nun wirklich weit vor den anderen Zeichen liegt, könnte das mit großer Wahrscheinlichkeit schon zum Erfolg führen, evtl. halt noch N, I, S und R testen. Kleinbuchstaben sollten reichen, da diese ja die Majuskeln deutlich überwiegen dürften.

Edith meint, dass das Leerzeichen noch häufiger als ein kleines "E" sein dürfte.
 
Zuletzt bearbeitet:
Sondai schrieb:
z.B. für die erste Stelle es Passworts musst du alle Stellen zählen die Positon mod 4 = 0 sind.

Welche stellen muss ich denn alle zählen? So ganz bin ich noch nicht hinter das Verfahren gekommen :(
 
Na jede 4. Stelle, wobei du für die erste Stelle des Passworts bei der ersten Stelle des Textes anfängst, für die zweite Stelle des Passworts an der zweiten usw.
 
okay also so?
In verschluesselt[] steht der komplette Text Zeichen für Zeichen drin.

Code:
void pos_count(int verschluesselt[])
{
	int i,j;
	int max[4] = {0,0,0,0};

	for (i = 0; i < 4; i++)
	{
		for (j = i; j < 200; j = j + 4)
		{
			if ((verschluesselt[j] % 4) == 0)
				max[i]++;
		}
		printf("%d\n", max[i]);
	}
}
 
Nein. Du müsstest dir eine Tabelle anlegen, welches Zeichen wie oft (bzw. reicht auch nur welches eine Zeichen am häufigsten) vorkommt. Und dann über "passwort =' ' ^ häufigstes_zeichen" bzw. 'e' ^ häufigstes_zeichen das Passwort erhalten.
Über modulo solltest du nur an das jeweils vierte zeichen kommen, das machst du ja jetzt schon über die for-Schleife.
 
AndrewPoison schrieb:
Du meinst wohl 128^4. Wenn man die nicht druckbaren Zeichen abzieht, sind es nur noch 95^4, also ca 8,1 millionen Möglichkeiten.

Ob man bei so wenigen Zeichen mit einer Häufigkeitsanalyse schneller zum Ziel kommt ist fraglich. Bequemer dürfte hier aber auf jeden Fall die Brute-Force Methode sein.

@ottofischer
Für Häufigkeitsanalysen gibt es bereits genügend Tools. :)
 
Weißt du denn, wie lange der Text ist? Alles was ich hier rausgelesen habe, war, dass es sich "bei dem verschlüsselten Text um einen deutschen Text handelt."

Man muss sich dann halt nicht so viele Kandidaten für das Passwort anschauen, da bei einem deutschen Text (ab gewisser Länge) mit großer Wahrscheinlichkeit entweder 'e' oder ' ' am häufigsten vorkommt.
 
Da komme ich nach hause und was muss ich lesen? Erschöpfende Suche für XOR-"Verschlüsselung"? Wenn das die richtige Antwort wäre, warum gibt es dann AES oder RSA und wasweißichnoch?

Hier die Lösung, auf die jeder Fünftklässler hätte kommen müssen:

XOR ist seine eigene Umkehrung. A XOR B XOR A ergibt wieder B. Wenn man den Chiffretext um die Länge des Schlüssels verschiebt und mit sich selbst XORT, hat man den Schlüssel komplett aus den Daten entfernt und es bleibt nur noch der Klartext übrig, der mit sich selbst um n Bytes verschoben XOR-verknüpft ist.

Jetzt rät man die ersten Zeichen, die man im Klartext vermutet und XORt sie auf den erhaltenen Text. Wenn dabei ein sinnvolles Wort herausfällt, hat man vermutlich richtig geraten. Das neue Wort schiebt man dann weiter und "entschlüsselt" damit die nächsten Bytes und wiederholt das, bis man den Klartext hat.

Ein Beispiel mit an der Hand führen:
Gegeben sei der Chiffretext "09 03 0f 0d 0d 0f 08 07 01 04 01 0c 0c 12 16 15 07 11 05 03 16 03 03 10 04" (hexadezimal).

1. Man rät die Länge des Passworts. Sagen wir mal, könnte ja 4 sein. Der Chiffretext wird um 4 verschoben mit sich selbst XOR verknüpft:
Code:
DATA: 09 03 0f 0d 0d 0f 08 07 01 04 01 0c 0c 12 16 15 07 11 05 03 16 03 03 10 04
XOR:  0d 0f 08 07 01 04 01 0c 0c 12 16 15 07 11 05 03 16 03 03 10 04
=     04 0c 07 0a 0c 0b 09 0b 0d 16 17 19 0b 03 13 16 11 12 06 13 12
2. Man rät den Anfang des Klartextes. Könnte mit "HALLO" anfangen, also probieren wir das mal aus. Wir haben um 4 Bytes verschoben, also probieren wir es mit den ersten 4 Bytes und gucken, was herauskommt:
Code:
    04 0c 07 0a
XOR 48 41 4c 4c
=   4c 4d 4b 46
Die Bytes in ASCII ergeben "LKMF". Macht nicht so Sinn. Vielleicht war die geratene Passwortlänge ja falsch. Probieren wir mal mit 3:
Code:
DATA: 09 03 0f 0d 0d 0f 08 07 01 04 01 0c 0c 12 16 15 07 11 05 03 16 03 03 10 04
XOR:  0f 0d 0f 08 07 01 04 01 0c 0c 12 16 15 07 11 05 03 16 03 03 10 04
=     04 0e 00 05 0a 0e 0c 06 0d 08 13 1a 19 15 07 10 04 07 06 00 06 07
Probieren wieder "HALLO" aus. Diesmal die ersten 3 Buchstaben ("HAL"):
Code:
    04 0e 00
XOR 48 41 4c
=   4c 4f 4c
Das ergibt in ASCII die Zeichen "LOL". Das geratene "HAL" und das zusammengesetzte "LOL" ergeben zusammen "HALLOL". DAS SIEHT JA VIELVERSPRECHEND AUS!
Das "LOL" was aus dem ersten Versuch herausgefallen ist XOREN wir mit den nächsten 3 Bytes:
Code:
05 0a 0e ^ 4c 4f 4c = 49 45 42
ergiebt "IEB". Kompletter Klartext bisher: "HALLOLIEB". So macht man dann weiter und stellt fest, dass man den Schlüssel nie gebraucht hat. Man musste nur 3 Zeichen des Klartext richtig erraten.

Ende.

€: Zugabe! Wenn man den nur teilweise richtig rät, bekommt man regelmäßig "Lücken" im generierten Klartext, aus denen man den Fehler beim geratenen Schnipsel korrigieren kann. Wenn man die Länge falsch rät, kann man das auch mit Frequenzanalyse korrigieren, ist aber bei so kurzen "Schlüsseln" aufwändiger, als einfach 2-3 Längen auszuprobieren und zu sehen, ob der richtige Klartext rausfällt.
 
Zuletzt bearbeitet:

Ähnliche Themen

Zurück
Oben