Übung — AFB III (Verallgemeinern und Reflektieren)

Musterlösung: Das Verfahren ist unsicher. Mit nur \(26^{3}=17\,576\) möglichen Schlüsselwörtern ist schon Brute Force in Sekundenbruchteilen erledigt. Außerdem wiederholen sich in 3 000 Buchstaben Folgen wie „DER“ oder „UND“ oft an Stellen mit gleichem Schlüsselbuchstaben; der Kasiski-Test liefert die Länge 3. Jeder der drei Teiltexte hat dann etwa 1 000 Buchstaben — genug für eine sichere Häufigkeitsanalyse, die jeden Schlüsselbuchstaben einzeln liefert. Da der Schlüssel seit Jahren gleich ist, knackt ein einziger Angriff alle Protokolle. Sicher wäre ein modernes symmetrisches Verfahren (z. B. AES) mit zufälligem, langem Schlüssel.

Musterlösung: Die Zahlen stimmen, der Schluss nicht. Ein großer Schlüsselraum schützt nur vor Brute Force. Bei Vigenère findet der Kasiski-Test die Schlüssellänge 20; danach zerfällt der Geheimtext in 20 Caesar-verschlüsselte Teiltexte, die man einzeln per Häufigkeitsanalyse knackt — höchstens \(20\cdot26=520\) Versuche statt \(26^{20}\). Voraussetzung ist nur ein ausreichend langer Text (z. B. 2 000 Buchstaben, also 100 je Teiltext). Gegen moderne Verfahren ist dagegen kein Angriff bekannt, der wesentlich schneller ist als das Durchprobieren. Also ist Vigenère trotz größerem Schlüsselraum deutlich unsicherer.

Musterlösung: Mias Aussage ist falsch. An jeder Position addieren sich die Verschiebungen beider Schlüsselbuchstaben. Das Muster wiederholt sich erst, wenn beide Schlüssel gleichzeitig wieder am Anfang stehen — nach kgV\((4,6)=12\) Buchstaben. Die doppelte Verschlüsselung ist also eine einzige Vigenère-Verschlüsselung mit dem Schlüsselwort HAFVPRJDDSRU (L + W = H, A + A = A, N + S = F, …). Sie bleibt mit Kasiski-Test und Häufigkeitsanalyse angreifbar; der Gewinn an Sicherheit ist gering.

Musterlösung: Das Vorgehen ist abzulehnen. Mit einmal verwendetem, zufälligem Schlüssel ist das One-Time-Pad nicht zu knacken, weil jeder Klartext gleicher Länge gleich wahrscheinlich ist. Bei zweifacher Verwendung gilt aber buchstabenweise \(g_1-g_2=(p_1+s)-(p_2+s)=p_1-p_2\) (mod 26): Der Schlüssel fällt heraus. Aus der Differenz zweier sinnvoller deutscher Texte lassen sich mit häufigen Wörtern beide Klartexte schrittweise erraten; kennt der Angreifer eine Nachricht (z. B. eine Standardeinladung), erhält er sofort den Schlüssel und damit die zweite. Die Einsparung wiegt den Verlust der Sicherheit nicht auf.

def schluessel_finden(klartext, geheimtext):
    folge = ""
    for i in range(len(klartext)):
        p = klartext[i]
        c = geheimtext[i]
        if "A" <= p <= "Z":                # Leerzeichen überspringen
            folge += chr((ord(c) - ord(p)) % 26 + 65)
    for laenge in range(1, len(folge) + 1):
        kandidat = folge[:laenge]
        passt = True
        for j in range(len(folge)):
            if folge[j] != kandidat[j % laenge]:
                passt = False
        if passt:
            return kandidat                   # kürzeste Periode
    return folge

print(schluessel_finden("TREFFPUNKT MORGEN", "XLPJJJFRON XSVAPR"))   # EULE

Die Folge lautet EULEEULEEULEEULE; die kürzeste passende Länge ist 4, also EULE. Die Funktion zeigt, warum Vigenère schon bei bekanntem Klartext (known-plaintext) fällt: Ein paar Buchstaben Klartext genügen für den ganzen Schlüssel. Ist die Nachricht kürzer als eine Schlüsselperiode, liefert die Funktion nur den Anfang des Schlüssels — mehr gibt der Text dann auch nicht her.

Musterlösung: Festlegung: CBC mit einem zufälligen IV pro Datensatz. Im ECB-Modus wird „Kurs Inf-LK, Note 11“ bei jeder Schülerin und jedem Schüler zum selben Geheimtextblock. Ein Angreifer kann ohne Schlüssel zählen, wie oft jede Note vorkommt, und — sobald er einen einzigen Datensatz kennt (bekannter Klartext, z. B. die eigene Note) — alle gleichen Datensätze sofort zuordnen. Die Stärke von AES hilft dagegen nicht, weil der Angriff am Modus ansetzt. Der Vorteil des Dienstleisters bleibt auch mit CBC erhalten: Speichert man zu jedem Datensatz seinen eigenen zufälligen IV (der nicht geheim sein muss), lässt sich jeder Datensatz einzeln entschlüsseln, und gleiche Noten ergeben trotzdem verschiedene Geheimtexte. Der zusätzliche Speicher von 128 Bit je Datensatz ist ein geringer Preis.

Musterlösung: Für die Aussage spricht: Ein Wert nahe 1/26 ≈ 0,0385 zeigt, dass die Buchstabenhäufigkeiten des Klartexts verwischt sind; eine einfache Häufigkeitsanalyse und monoalphabetische Verfahren scheiden aus. Dagegen spricht: Der Koinzidenzindex prüft nur eine notwendige Bedingung. Auch ein Vigenère-Text mit langem Schlüssel oder ein One-Time-Pad mit mehrfach verwendetem Schlüssel kommen nahe an diesen Wert und sind trotzdem angreifbar. Nichts ist über Angriffe mit bekanntem oder gewähltem Klartext, über den Schlüsselraum (Brute Force erst ab etwa \(2^{128}\) Schlüsseln aussichtslos) oder über Fehler in der Implementierung gesagt. Dass das Verfahren geheim gehalten wird, widerspricht dem Prinzip von Kerckhoffs: Es konnte nicht öffentlich geprüft werden. Ergebnis: Die Werbeaussage ist nicht haltbar — „zufällig aussehend“ heißt nicht „sicher“. Vertrauenswürdig wäre ein offen geprüftes Standardverfahren wie AES mit 128-Bit-Schlüssel.

Musterlösung: Für Linas Vorschlag spricht, dass nur öffentliche Schlüssel übertragen werden müssen; ein geheimer Vorab-Austausch entfällt, und pro Person genügt ein Schlüsselpaar. Dagegen spricht, dass asymmetrische Verfahren um Größenordnungen langsamer sind als symmetrische — bei Fotos und Videos würde das Ver- und Entschlüsseln spürbar dauern und den Akku belasten. Außerdem bleibt das Echtheitsproblem der öffentlichen Schlüssel bestehen. Ergebnis: Ein hybrides Verfahren verbindet beide Vorteile — die Daten werden symmetrisch mit einem zufälligen Sitzungsschlüssel verschlüsselt, nur dieser kurze Schlüssel asymmetrisch mit dem öffentlichen Schlüssel des Empfängers.

1. Schule und Eltern besitzen Schlüsselpaare; ihre öffentlichen Schlüssel sind durch Zertifikate einer Zertifizierungsstelle bestätigt.
2. Die Schule bildet den Hashwert der E-Mail und verschlüsselt ihn mit ihrem privaten Schlüssel — das ist die Signatur.
3. Die Schule erzeugt einen zufälligen Sitzungsschlüssel, verschlüsselt E-Mail und Signatur damit symmetrisch und den Sitzungsschlüssel mit dem öffentlichen Schlüssel der Eltern (hybrid).
4. Die Eltern entschlüsseln den Sitzungsschlüssel mit ihrem privaten Schlüssel, damit E-Mail und Signatur.
5. Sie entschlüsseln die Signatur mit dem öffentlichen Schlüssel der Schule (aus deren Zertifikat), berechnen selbst den Hashwert der E-Mail und vergleichen. Gleich → echt und unverändert.

def vigenere(text, schluessel, richtung=1):
    ergebnis = ""
    i = 0                                   # Position im Schlüssel
    for zeichen in text:
        if "A" <= zeichen <= "Z":
            k = ord(schluessel[i % len(schluessel)]) - ord("A")
            neu = (ord(zeichen) - ord("A") + richtung * k) % 26
            ergebnis += chr(neu + ord("A"))
            i += 1                          # nur bei Buchstaben weiter
        else:
            ergebnis += zeichen             # Leerzeichen, Ziffern bleiben
    return ergebnis

print(vigenere("ABI 2027", "KEY"))          # KFG 2027
print(vigenere("KFG 2027", "KEY", -1))      # ABI 2027

Da Python bei % auch für negative Zahlen ein Ergebnis zwischen 0 und 25 liefert, funktioniert das Entschlüsseln mit richtung = -1 ohne Sonderfall.

Musterlösung: Mallory fängt Bobs Antwort ab und schickt Alice stattdessen ihren eigenen öffentlichen Schlüssel. Alice verschlüsselt nun mit Mallorys Schlüssel. Mallory entschlüsselt mit ihrem privaten Schlüssel, liest (oder ändert) die Nachricht, verschlüsselt sie mit Bobs echtem öffentlichem Schlüssel und leitet sie weiter. Bob kann normal entschlüsseln — niemand bemerkt etwas (Man-in-the-Middle-Angriff). Gegenmaßnahme: Alice muss prüfen, dass der Schlüssel wirklich Bob gehört, z. B. über ein Zertifikat einer vertrauenswürdigen Zertifizierungsstelle, die Bobs Identität und Schlüssel mit ihrer Signatur bestätigt, oder durch persönlichen Vergleich des Schlüssel-Fingerabdrucks.

Musterlösung: Toms Vorgehen ist wertlos. Bobs öffentlicher Schlüssel steht jedem zur Verfügung; jeder Angreifer kann eine geänderte Nachricht hashen und ebenfalls mit Bobs öffentlichem Schlüssel verschlüsseln. Bob kann also nicht erkennen, ob die Nachricht von Tom stammt — weder Authentizität noch Nichtabstreitbarkeit sind gegeben. Richtig ist: Tom verschlüsselt den Hashwert mit seinem privaten Schlüssel, den nur er besitzt; Bob prüft mit Toms öffentlichem Schlüssel.

Musterlösung: \(t=\frac{2^{64}}{10^{11}\,/\text{s}}\approx1{,}84\cdot10^{8}\text{ s}\approx5{,}8\text{ Jahre}\), im Mittel etwa die Hälfte. Mit mehr Rechnern oder schnellerer Technik schrumpft das auf Monate — 64 Bit sind nicht mehr ausreichend. Bei 128 Bit wächst der Schlüsselraum um den Faktor \(2^{64}\approx1{,}8\cdot10^{19}\): rund \(10^{20}\) Jahre, weit mehr als das Alter des Universums (etwa \(1{,}4\cdot10^{10}\) Jahre). Brute Force ist dann aussichtslos.