Verschlüsselungen angreifen

Wie wir bereits gesehen haben, lässt sich die Sicherheit von so manchem Verschlüsselungsverfahren umgehen, sodass wir ohne Kenntnis des Schlüssels an den Klartext gelangen können. In diesem Artikel schauen wir uns einige gängige Angriffsmethoden an. Das Finden eines solchen Verfahrens ist das Thema der Kryptoanalyse. Es geht dabei aber nicht darum, in böser oder krimineller Absicht zu handeln. Vielmehr wollen wir überprüfen, ob bekannte Verschlüsselungsverfahren wirklich sicher sind. Denn nur wenn wir von der Sicherheit eines Verschlüsselungsverfahrens überzeugt sind, können wir damit mit gutem Gewissen unsere sensibelsten, vertraulichsten Daten schützen.

Brute-Force

Der einfachste, aber auch aufwändigste Weg, einen Geheimtext ohne Kenntnis des Schlüssels zu knacken, ist die Brute-Force-Methode. Dabei werden ganz einfach alle möglichen Schlüssel durchprobiert, bis wir einen verständlichen Text erhalten.

Im Zusammenhang mit dem 👉 Schlüsselraum haben wir bereits erwähnt, dass dies bei der Caesar-Verschlüsselung relativ schnell zum Ziel führt. Man muss dazu lediglich die 25 Schlüssel B bis Z durchprobieren, bis man einen verständlichen Text erhält.

Bei einem Schlüssel mit $1024$ Bit Länge (etwa $1.8 \cdot 10^{308}$ mögliche Schlüssel - eine über dreihundert-stellige Zahl!) ist das nicht in vernünftiger Zeit möglich. Angenommen, ein Computer könnte pro Mikrosekunde einen Schlüssel ausprobieren. Die Maschine bräuchte in dem Fall $5.7 \cdot 10^{294}$ Jahre, um alle möglichen Schlüssel durchzuprobieren. Man könnte natürlich sehr viele Computer gleichzeitig rechnen lassen, aber auch das würde wenig helfen.

Bei der allgemeinen monoalphabetischen Substitution haben wir einen Schlüsselraum von $26!$ möglichen Schlüsseln (ungefähr $88 Bit$) errechnet. Mit derselben theoretischen Rechenzeit von einem Schlüssel pro Mikrosekunde bräuchte ein Computer auch da bereits $9.8 \cdot 10^{12}$ (rund 10 Billionen) Jahre, um alle möglichen Schlüssel durchzuprobieren.

Dictionary Attack

Eine Sonderform der Brute-Force-Methode ist die sogenannte Dictionary Attack (dt.: Wörterbuch-Angriff). Dabei geht ein Angreifer nicht unbedingt durch alle möglichen Schlüssel, sondern beschränkt sich auf eine relativ kleine Anzahl häufig verwendeter Schlüssel. Beispielsweise probiert man dabei oft entweder ein Wörterbuch (dictionary), oder eine Liste der meistverwendeten Passwörter.

Die zehn meistverwendeten Passwörter gemäss Wikipedia sind¹:

1. 123456
2. password
3. 12345678
4. qwerty
5. 123456789
6. 12345
7. 1234
8. 111111
9. 1234567
10. dragon

Häufigkeitsanalyse

Die Brute-Force-Methode führt also nur dann zuverlässig zum Erfolg, wenn ein Verschlüsselungsverfahren einen relativ kleinen Schlüsselraum aufweist. Für viele Verschlüsselungsverfahren gibt es aber auch effizientere Möglichkeiten, um ohne Kenntnis des Schlüssels an den Geheimtext zu gelangen. Einige Verfahren sind anfällig auf die sogenannte Häufigkeitsanalyse.

Buchstabenhäufigkeit in der deutschen Sprache

Eine bekannte Eigenschaft von natürlichen Sprachen ist, dass nicht alle Buchstaben des Alphabets mit gleicher Häufigkeit vorkommen. In der deutschen Sprache ist beispielsweise das E der häufigste Buchstabe. Wir können nun die Häufigkeit der einzelnen Buchstaben im Geheimtext analysieren. Wenn darin zum Beispiel der Buchstabe H als häufigster Buchstabe auftritt, kann unter der Annahme, dass der Klartext in Deutsch verfasst wurde, der Schlüssel abgeleitet werden. H ist im Alphabet 3 Stellen entfernt (E, F, G, H), also deutet das auf den Schlüssel 3 hin. Nachfolgend finden Sie eine Auflistung der 10. häufigsten Buchstaben der deutschen Sprache².

Rang	1	2	3	4	5	6	7	8	9	10
Buchstabe	E	N	I	S	R	A	T	D	H	U
Häufigkeit	$17.40\%$	$9.78\%$	$7.55\%$	$7.27\%$	$7.00\%$	$6.51\%$	$6.15/$	$5.08\%$	$4.76\%$	$4.35\%$

al-Kindī

Im neunten Jahrhundert hat der arabische Gelehrte Abū Ya'qūb ibn Ishāq al-Kindī³ (oder kurz al-Kindi) durch eine Analyse des Korans entdeckt, dass die einzelnen Zeichen der arabischen Schrift in bestimmten Häufigkeiten auftreten. In seiner Abhandlung über die Entzifferung kryptographischer Botschaften schrieb er Folgendes:

Eine Möglichkeit, eine verschlüsselte Botschaft zu entziffern, vorausgesetzt, wir kennen ihre Sprache, besteht darin, einen anderen Klartext in derselben Sprache zu finden, der lang genug ist, um ein oder zwei Blätter zu füllen, und dann zu zählen, wie oft jeder Buchstabe vorkommt. Wir nennen den häufigsten Buchstaben den «ersten», den zweithäufigsten den «zweiten», den folgenden den «dritten» und so weiter, bis wir alle Buchstaben in der Klartextprobe durchgezählt haben. Dann betrachten wir den Geheimtext, den wir entschlüsseln wollen, und ordnen auch seine Symbole. Wir finden das häufigste Symbol und geben ihm die Gestalt des «ersten» Buchstabens der Klartextprobe, das zweithäufigste Symbol wird zum «zweiten» Buchstaben, das dritthäufigste zum «dritten» Buchstaben und so weiter, bis wir alle Symbole des Kryptogramms, das wir entschlüsseln wollen, auf diese Weise zugeordnet haben.

Entschlüsselung durch Häufigkeitsanalyse

Durch die Häufigkeitsanalyse werden Geheimtexte, die durch eine monoalphabetische Substitution verschlüsselt worden sind, grundsätzlich entzifferbar. Das heisst, sie können ohne Kenntnis des Schlüssels entschlüsselt werden, indem eine Häufigkeitsanalyse vorgenommen wird.

Wir analysieren dazu die Buchstabenhäufigkeiten im Geheimtext und stellen sie den Buchstabenhäufigkeiten der Sprache des Klartexts gegenüber. Angenommen, wir wissen, dass der verschlüsselte Text in deutscher Sprache verfasst wurde. Nach der Analyse der Buchstabenhäufigkeiten im Geheimtext könnte ein Ausschnitt aus der Gegenüberstellung dieser Häufigkeiten wie folgt aussehen:

Rang	1	2	3	4	5	6	7	8	9	10
Deutsch	E	N	I	S	R	A	T	D	H	U
Geheimtext	T	G	Q	A	L	B	Z	K	O	N

Daraus können wir folgende Annahmen ableiten, dass E vermutlich zu T verschlüsselt wurde, N wurde vermutlich zu G verschlüsselt, und so weiter.

Aus diesen Erkenntnissen können wir bereits folgenden Teilschlüssel ableiten:

Alphabet	A	B	C	D	E	F	G	H	I	J
Schlüssel	B			K	T			O	Q

Wenn wir dieses Verfahren für die komplette Gegenüberstellung der Buchstabenhäufigkeiten umsetzen, so erhalten wir einen relativ guten ersten Schlüssel, mit dem wir versuchen können, den Geheimtext zu entschlüsseln. Es ist allerdings unwahrscheinlich, dass der ursprüngliche Klartext ganz genau die Buchstabenhäufigkeiten der deutschen Sprache aufweist. Dieser erste Schlüssel wird deshalb in den wenigsten Fällen ganz korrekt sein. Dennoch lassen sich oft bereits einige Wörter erahnen, sodass wir den Schlüssel entweder manuell oder mithilfe von fortgeschritteneren Verfahren weiter verfeinern können.

Sonderform: Caesar-Chiffre

Für die Entzifferung einer Caesar-Chiffre genügt es, mithilfe der Häufigkeitsanalyse den häufigsten Buchstaben zu identifizieren. Wir können dann davon ausgehen, dass E (der häufigste Buchstabe in der deutschen Sprache) vermutlich zu diesem Buchstaben verschlüsselt wurde. Damit müssen wir lediglich noch das Geheimtextalphabet so dem Klartextalphabet entlang verschieben, dass der häufigste Schlüsselbuchstabe unter dem Klartextbuchstaben E steht. Der Schlüssel ist dann der erste Buchstabe des Geheimtextalphabets.

Häufigkeitsanalyse durchführen

Häufigkeitsanalyse ausprobieren

Der folgende Text wurde mit der 👉 Caesar-Chiffre verschlüsselt. Nutzen Sie das nachstehende Tool zur Häufigkeitsanalyse, um den Text zu entschlüsseln.

RYFWAVSVNPL PZA KPL SLOYL KLZ CLYIVYNLULU. KPL RYFWAVSVNPL BTMHZZA KPL MVSNLUKLU GDLP ALPSNLIPLAL: RYFWAVNYHWOPL BUK RYFWAVHUHSFZL. RYFWAVNYHWOPL ILGLPJOULA KPL RBUZA KLZ CLYZJOSBLZZLSUZ, DHLOYLUK ZPJO KPL RYFWAVHUHSFZL KHTPA ILZJOHLMAPNA, HBZ CLYZJOSBLZZLSALU IVAZJOHMALU PUMVYTHAPVULU GB NLDPUULU, ZWYPJO, ZPL GB RUHJRLU.

Beantworten Sie anschliessend die folgenden Fragen und kontrollieren Sie Ihre Antwort.

Wie lautet der Schlüssel?

Wie lautet der erste Satz des Klartexts?

Häufigkeitsanalyse

Klartext

Hallo

Sortiere alphabetisch

Alle Zeichen

Platzhalter für vorkommende Buchstaben

Stark oder schwach?

Die Verschlüsselungsverfahren, die Sie bisher kennengelernt haben, gelten allesamt als schwache Verschlüsselungen. Das bedeutet, dass für sie jeweils ein Verfahren bekannt ist, mit dem man einen Geheimtext mit vernünftigem Aufwand entschlüsseln kann, ohne dabei den Schlüssel zu kennen. Ein solches Verfahren bezeichnen wir auch als effizient. Ist für eine Verschlüsselung kein effizientes Verfahren bekannt, so sprechen wir von einer starken Verschlüsselung.

Ein Verschlüsselungsverfahren gilt so lange als stark, bis wir ein effizientes kryptoanalytisches Verfahren finden, das die Verschlüsselung durchbricht. Wenn ein Verschlüsselungsverfahren einen genug grossen Schlüsselraum aufweist (wobei der Begriff genug gross hier nicht scharf definiert ist), dann gilt die Brute-Force-Methode nicht als effizientes Verfahren. Anders ist das bei der Caesar-Verschlüsselung, wo wir auch mit der Brute-Force-Methode lediglich 25 Schlüssel durchprobieren müssen.

Footnotes

1. Quelle: 👉 10,000 most common passwords (Wikipedia). ↩

2. Quelle: 👉 Buchstabenhäufigkeit (Wikipedia). ↩

3. Quelle: 👉 al-Kindī (Wikipedia). ↩