Romeo, Juliet, Diffie & Hellman

Als Whitfield Diffie und Martin Hellman 1976 ihr Papier mit dem Titel “New Directions in Cryptography” veröffentlichten, waren sie von der Idee getrieben, geheime Informationen über einen öffentlichen Kanal auszutauschen. Und das ohne vorher über einen sicheren Kanal irgendwelche Absprachen getroffen zu haben. Mehr noch, die Absicherung des Geheimnisses sollte vollständig mit öffentlich bekannten Techniken erfolgen. In diesem Teil der Reihe “Asymmetrische Kryptographie” soll der Schlüsselaustausch nach Diffie und Hellman im Mittelpunkt stehen.

Die Schlüssel generieren

Solange Romeo im Exil lebt, kann er mit Juliet nur über Briefe Kontakt halten. Die beiden müssen ihre Kommunikation aber geheim halten. Von den Fluchtplänen Juliets darf unter keinen Umständen ein Dritter erfahren. Also drängt Juliet darauf, dass die beiden ihre Kommunikation verschlüsseln. Nun haben sie aber keinen Boten, dem sie beide ausreichend genug vertrauen, dass er einen Schlüssel von Juliet zu Romeo transportieren könnte. Und die Familie Capulet fängt alle verschlossenen Briefe an Juliet ab, öffnet sie und liest deren Inhalt. Die beiden Schmachtenden einigen sich kurzfristig darauf, es mit einer asymmetrischen Variante der Schlüsselerzeugung zu probieren. Romeo hat einen Faible für Primzahlen. Er denkt sich eine  besonders hohe aus (nennen wir sie p) und schickt diese unverschlüsselt an Juliet. Die wiederum denkt sich eine beliebige natürliche Zahl g aus und sendet diese als Antwort an Romeo. Im zweiten Schritt denk Romeo sich eine geheime Zahl r aus, die kleiner als p ist. Mit dieser Zahl berechnet er seinen öffentlichen Schlüssel kr durch die Gleichung

kr = gr mod p

Juliet tut es ihrem Liebsten gleich, denkt sich eine geheime Zahl j < p aus und berechnet kj durch

kj = gj mod p

Romeo und seine Juliet tauschen ihre öffentlichen Schlüssel. Romeo berechnet jetzt im Geheimen

K = (kj)r mod p

und Juliet ihrerseits

K = (kr)j mod p

K ist bei beiden die gleiche Zahl und wird von hier ab als Schlüssel für eine symmetrische Verschlüsselung verwendet.

Mögliche Angriffe
Paris

Von der Angst getrieben, um seine Braut betrogen zu werden, lässt Paris sich über alle Briefe informieren. Er erfährt Romeos Primzahl p und Juliets Zahl g sowie die beiden öffentlichen Schlüssel kr und kj. Außerdem weiß er, wie das Verfahren funktioniert, das die Liebenden einsetzen und so weiß er auch, wie er an die geheimen Informationen r oder j kommen kann. Dafür muss Paris nur den Logarithmus eines öffentlichen Schlüssels zur Basis g berechnen und dabei den Modul beachten.

Also

r = logg kr mod p

Hat er r einmal berechnet, kann Paris seinerseits einfach

K = (kj)r mod p

berechnen und die weitere Kommunikation zwischen Romeo und Juliet verfolgen, als wäre sie unverschlüsselt.

An dieser Stelle greift ein Sicherheitsmechanismus, welcher sich “Einwegfunktion” nennt. Ich werde darauf in einem anderen Artikel genauer eingehen. Kurz sei gesagt, dass die Berechnung der Potenz gr mod p deutlich einfacher ist, als deren logarithmische Umkehrfunktion. Sind die Zahlen groß genug gewählt, wird dieser Angriff praktisch nicht mehr durchführbar.

Lady Capulet

Aber keiner hat mit der Durchtriebenheit der Lady Capulet gerechnet. Sie nimmt versteckt an den Gesprächen zwischen Romeo und Juliet Teil. Als die Beiden sich gegenseitig ihre öffentlichen Schlüssel zusenden, fängt Lady Capulet beide Schlüssel ab. Sie berechnet im Geheimen zwei eigene öffentliche Schlüssel kc1 und kc2. Den Ersten schickt sie an Romeo, der ihn für den öffentlichen Schlüssel von Juliet hält. Den Zweiten sendet sie ihrer eigenen Tochter, die wiederum glaubt, er stamme von Romeo. Nun berechnen alle drei wiederum ein K, nur dass Romeo und Juliet jetzt unterschiedliche Schlüssel K haben, nämlich K1 und K2, die aus

K1 = (kc1)r mod p

und

K2 = (kc2)j mod p

resultieren.

Jetzt teilen sich Romeo und Juliet jeweils einen symmetrischen Schlüssel mit der Lady Capulet. Die muss nun ihrerseits jede einzelne Nachricht abfangen, entschlüsseln, neu verschlüsseln und weiter senden. Zwischen den Schritten des Entschlüsselns und Verschlüsselns kann die Capulet die Nachrichten lesen und verändern und so der Liebschaft schnell ein Ende bereiten.

Fazit

Besonders der letzte Angriff macht das Verfahren untauglich. Doch handelt es sich hierbei um die ersten Ideen von Whitfield Diffie und Martin Hellman. Die beiden waren sich der Problematik vollkommen bewusst und haben in ihrem Papier über Möglichkeiten der Senderverifikation ausgelassen. Aber das soll Thema eines anderen Artikels sein.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s