Kryptografie
Willemers Informatik-Ecke

Ziele

Verschlüsselung

Kerckhoffs-Prinzip: Eine Geheimhaltung des Verfahrens ist nicht sicher und unpraktisch. Da ein Verschlüsselungsverfahren in der Regel häufiger eingesetzt wird, wird es irgendwann eine undichte Stelle geben, die das Verfahren bekannt macht. Sicherheit entsteht also nur durch einen geheimen Schlüssel, der jederzeit gewechselt werden kann.

Caesar

Der Legende nach soll Caesar bereits dieses Verschlüsselungsverfahren verwendet haben. In der einfachsten Form wird jeder Buchstabe durch den nächsten Buchstaben im Alphabet ersetzt. Der Empfänger muss dies nur entsprechend rückgängig machen. Etwas komplizierter wird das Verfahren, wenn nicht der nächste, sondern der übernächste Buchstabe verwendet. Duch die 26 Buchstaben des Alphabets sind damit 26 verschiedene Verschlüsselungen möglich, von denen allerdings einer der Klartext ist.

Die Differenz wird nicht in Zahlen, sondern in Buchstaben formuliert, wobei A=0, B=1, C=2 usw. gilt. Das Wort ZAESAR wird mit der einfachen Caesar-Verschlüsselung zu ABFTBS, da das Z einfach wieder vorn anfängt.

  ZAESAR
+ BBBBBB
= ABFTBS
Eine besondere Form des Caesars ist Rot13: Der Buchstabe wird um 13 Positionen weitergerollt. Durch eine erneute Anwendung von Rot13 erscheint wieder der Klartext.

Das Problem von Caesar ist:

Vigenère

Statt einer Verschiebung durch einen Buchstaben wie beispielsweise B über den gesamten Klartext, kann die Verschiebung über ein geheimes Wort geschehen, beispielsweise BAD.
  ZAESAR
+ BADBAD
= AAHTAU
Auf diese Methode greifen statistische Methoden ins Leere.

Weiß der Angreifer, dass das Schlüsselwort drei Buchstaben hat, kann er alle drei Buchstaben 26 Buchstaben durchrotieren und kann dann den Klartext raten. Kennt er darüber hinaus einen Buchstaben des Klartextes, kennt er ein Drittel des Schlüssels.

Vernam

Der Schlüssel ist so lang wie der Klartext, wird nur einmal verwendet und ist komplett zufällig.

Damit ist er perfekt sicher, leider aber in den meisten Fällen nicht praktikabel.

C. Shannon: Ein Verschlüsselungsverfahren ist perfekt sicher, wenn es so viele Schlüssel wie Klartexte gibt, alle Schlüssel gleich wahrscheinlich sind und für jeden Klartext und jedem Geheimtext genau einen Schlüssel gibt, der den Klartext in den Geheimtext verschlüsselt.

Prinzipien der Verschleierung nach Claude Shannon

Konfusion: Statistische Häufigkeiten eines Buchstaben werden nicht auf den Geheimtext übertragen. Die Übertragung ist also nichtlinear.

Diffusion: Eine Änderung an einer Stelle im Klartext führt zu einer Veränderung des Geheimtexts an mehreren Stellen.

Asymetrische Verschlüsselung

Für die asymetrische Verschlüsselung werden zwei Schlüssel verwendet: Einen Schlüssel behält man privat unter Verschluss, den anderen verteilt man großzügig an alle Freunde (oder Feinde).

Dabei gilt, dass das, was der eine Schlüssel verschlüsselt, nur durch den anderen Schlüssel entschlüsselt werden kann.

Als Bild: Der öffentliche Schlüssel kann ein Schloß genau eine Drehung nach links drehen. Der private Schlüssel kann dieses Schloss genau eine Drehung nach rechts drehen. Was der öffentliche Schlüssel verschließt, kann nur der private Schlüssel öffnen, was der private Schlüssel verschließt, kann nur der öffentliche Schlüssel öffnen.

Bekanntes Schlüsselverfahren heißt RSA nach Rivest, Shamir und Adleman.

Geheimtext = Klartext encryptKey mod grossKey

Klartext = GeheimtextdecryptKey mod grossKey

Diffusion: Die Änderung eines Zeichens im Klartext verändert mehrere Zeichen im Geheimtext.

Schlüsselvereinbarung nach Diffie-Hellman

Alice und Bob wollen einen gemeinsamen Schlüssel verwenden. Da sie sich nie begegnen, bleibt zum Austausch nur das angreifbare Netz.

Öffentlich werden die Zahlen g und p ausgetauscht, dabei gilt

1 < g < p-1
p muss eine Primzahl sein.

Alice Angreifer Bob
Alice wählt eine zufällige Zahl u.
und berechnet a = gu mod p.
Angreifer kann g und p ablauschen. Bob wählt eine zufällige Zahl v.
und berechnet b = gv mod p.
Alice sendet a sichtbar an Bob. Angreifer kennt nun a und b. Bob sendet b sichtbar an Alice.
key = bu mod p key = av mod p

Der Grund, warum es funktioniert:
guv mod p = bu mod p = av mod p

Eine Angriffsmöglichkeit besteht darin, dass sich der Angreifer gegenüber Alice als Bob und gegenüber Bob als Alice ausgibt und die Nachrichten weiterleitet. Das kann verhindert werden, wenn sich Alice und Bob gegenseitig authentifizieren.

Verschlüsselung nach ElGamal

ElGamal verwendet das Diffie-Hellman-Protokoll, um den gemeinsamen Schlüssel key zu ermitteln und sendet auf dessen Basis eine verschlüsselte Nachricht.
Alice Angreifer Bob
geheim = key * klar mod p
klar = key-1 * geheim mod p

Shamir ohne gemeinsamen Schlüssel

Auch hier bleibt die Möglichkeit eines Man-In-The-Middle-Angriffs.

Symmetrische Verschlüsselung mit AES

DES (56 Bit Schlüssellänge) wurde durch AES (128 Bit Schlüssellänge) abgelöst. AES wird beispielsweise bei WPA2 für WLAN eingesetzt.

Der Klartext wird in Häppchen zu 16 Bytes in einer 4x4-Matrix angeordnet.

  1. Key Expansion: Mache aus dem Schlüssel k elf neue Schlüssel k0 bis k10, die sogenannten Rundenschlüssel.
  2. Add Round Key: Bitweise XOR-Verknüpfung zwischen dem Block und dem nullten Rundenschlüssel.
  3. Wiederhole für i=1 bis 10:
    • Substitude Bytes: Ersetzt jedes Byte anhand einer Substitutionsbox von 256 Bytes, die als Konstante gespeichert oder dynamisch berechnet wird, je nachdem, ob man Speicher oder Rechenzeit sparen will.
    • Shift Rows: Die Zeilen der 4x4-Matrix werden nach links durchrotiert: Zeile 0 um 0 Positionen, Zeile 1 um eine Position usw..
    • Mix Columns: Nun werden die Spalten der Matrix durch Multiplikation mit einer anderen Matrix vermischt.
    • Add Round Key: Bitweise XOR-Verknüpfung zwischen dem Block und dem aktuellen Rundenschlüssel.
Die Entschlüsselung erfolgt durch rückwärtige Ausführung mit den inversen Methoden.

Links zu AES

Kryptografische Hashfunktion

Hashfunktionen werden für die Sicherung der Datenintegrität verwendet oder um Passwörter zu speichern. Sie sind Falltüralgorithmen. Beispielsweise würde die Quersumme aller Buchstaben einer Datei eine Änderung an der Datei vermutlich entdecken. Würde die Quersumme eines Passworts gespeichert und bei einem Anmeldeversuch ein Passwort mit einer anderen Quersumme eingegeben, ist das Passwort offensichtlich nicht korrekt. Fällt die Quersumme in die Hände eines Angreifers, kann er daraus das Passwort aber nicht ermitteln.

Das Problem ist aber, dass man leicht zwei Dokumente oder Passwörter mit der gleichen Quersumme finden kann. Man spricht von einer Kollision der Hashfunktion. Ideal wäre also eine Hashfunktion, die möglichst kollisionsfrei ist.

SHA-1 (Secure Hash Algorithm) verwendet 160 Bit. Es gibt Nachfolger SHA-2 und SHA-3 mit nun 512 Bit.

Insbesondere für das Speichern von Passwörtern wurde das Verfahren MD5 verwendet. Dieses gilt aber als unsicher. MD5 findet heute noch Anwendung, um sicherzustellen, dass ein Download störungsfrei verlaufen ist.

Angriffstechniken

Literatur