Schlagwort-Archive: Kryptographie

Kryptographie, Teil 6: Asymmetrische Verschlüsselung

Die in den bisherigen Teilen behandelten Verfahren hatten alle eins gemein: Sender und Empfänger einer geheimen Nachricht mussten sich vor dem Versand auf einen gemeinsamen Schlüssel einigen, der auf einem sicheren Kanal übergeben werden musste. Es handelte sich um sogenannte symmetrische Verschlüsselungsverfahren.

Das funktioniert dann sehr gut, wenn wenige Personen, die zudem die Gelegenheit haben, Schlüssel persönlich zu tauschen, miteinander kommunizieren wollen. Im Internet dagegen funktioniert das so nicht. Wer eine verschlüsselte Webseite besucht, möchte Daten abhörsicher übetragen, hat aber normalerweise keine Gelegenheit dazu, mit dem Betreiber der Seite vor der eigentlichen Datenübertragung abhörsicher Schlüssel auszutauschen.

Kommunikation

Mit der Entdeckung der Public-Key-Kryptographie Ende der 1970er Jahre wurde hier ein Durchbruch erzielt. Sogenannte asymmetrische Verschlüsselungsverfahren arbeiten mit zweigeteilten Schlüsseln. Der Schlüssel, der zum Chiffrieren einer Nachricht verwendet wird, ist ein anderer als der, mit dem die Nachricht wieder entschlüsselt werden kann. Da es mit ersterem Schlüssel nicht möglich ist, einen Geheimtext wieder zu dechiffrieren, braucht er auch nicht geheim gehalten zu werden. Nur der zweite Schlüssel muss geheim gehalten werden und nur der Empfänger muss ihn kennen, der Sender nicht. Es entfällt also die Notwendigkeit, einen gemeinsamen Schlüssel über einen sicheren Kanal auszutauschen, denn der öffentliche Schlüssel, der zum Verschlüsseln ausreicht, ist eben öffentlich und kann somit über den selben unsicheren Kanal ausgetauscht werden wie der Geheimtext!

Doch wie ist das möglich? Es gibt in der Mathematik sogenannte Einwegfunktionen. Diese haben die Eigenschaft, dass sie sich leicht berechnen lassen, ihre Umkehr jedoch nicht. Ein Beispiel dafür ist die Multiplikation zweier großer Primzahlen (leicht) und als Umkehr die Zerlegung des Produkts in seine Primfaktoren (schwer). Oder kurz: n = p * q lässt sich leicht berechnen, aber p und q lassen sich nicht direkt berechnen, wenn nur n bekannt ist. Allerdings gibt es eine Hintertür: Wenn man nicht nur die Zahl n kennt, sondern auch q, kann man p wieder leicht berechnen. Und auf einer Erweiterung genau auf dieses Prinzips basiert der 1978 vorgestellte RSA-Algorithmus.

Der RSA-Algorithmus hat wegen seiner Asymmetrie eine hohe praktische Relevanz bis heute. Doch bevor wir zur praktischen Anwendung kommen, zunächst noch ein klein wenig zum Hintergrund, wie der RSA-Algorithmus funktioniert, denn im Grund ist es gar nicht so schwer. mod ist dabei der Modulo-Operator, also der Rest einer ganzzahligen Division.

RSA-Algorithmus

 

Vorbereitung:

1. Wähle zwei große Primzahlen p und q
2. Berechne n = p * q
3. Berechne ϕ(n) = (p-1)*(q-1)
4. Wähle e teilerfremd zu ϕ(n)
5. Bestimme d mit e*d mod ϕ(n) = 1

Öffentlicher Schlüssel: e und n
Privater Schlüssel: d

Verschlüsseln eines Klartextes m in Geheimtext c:
c = me mod n

Entschlüsseln eines Geheimtextes c in einen Klartext m:
m = cd mod n

 

Genauer kann man das noch unter anderem bei Beutelspacher [1] oder natürlich direkt bei den Entdeckern von RSA, den Herren Rivest, Shamir and Adleman, nachlesen [2]. Wie man erkennt, steht und fällt die Sicherheit dieses Verfahrens damit, dass man auch bei Kenntnis des Geheimtextes, des Klartextes und des öffentlichen Schlüssels nicht den privaten Schlüssel berechnen kann. Außerdem darf sich der Klartext nur mit Kenntnis des privaten Schlüssels aus dem Geheimtext berechnen lassen. Oder mathematisch gesagt: Auch, wenn man c, m, e und n kennt, kann man d nicht berechnen und wenn man c kennt, kann man m nur berechnen, wenn man auch d kennt. Wenn man jetzt noch etwas genauer schaut, dann sieht man, dass sich das alles berechnen ließe, könnte man die Zahl n, die ja Teil des öffentlichen Schlüssels ist, in ihre Primfaktoren p und q zerlegen. Sollte jemand also eine effektive Methode zur Primfaktorzerlegung großer Zahlen finden, wäre das RSA-Verfahren gebrochen.

Mit sogenannten Public-Key-Verschlüsselungen wie RSA ist es also nun kein Problem mehr, auch mit Unbekannten verschlüsselt und abhörsicher zu kommunizieren. Das Problem des vorherigen Schlüsselaustauschs, das bei den symmetrischen Verschlüsselungsverfahren besteht, ist nun keins mehr. Der Ablauf der Kommunikation ist nun ganz einfach. Anke und Andreas haben jeweils zwei Schlüssel, einen öffentlichen und einen privaten. Der öffentliche Schlüssel kann allgemein bekannt gegeben werden. Möchte nun Anke eine verschlüsselte Nachricht an Andreas schicken, muss sie sich zunächst seinen öffentlichen Schlüssel besorgen. Den findet sie zum Beispiel auf seiner Webseite oder aber in einem Schlüsselverzeichnis im Internet, einem sogenannten Keyserver, der ähnlich wie ein Telefonbuch für das Nachschlagen von Personen, Mailadressen und dem dazu passenden Public Key erlaubt. Wenn Anke den öffentlichen Schlüssel von Andreas besorgt hat, benutzt sie diesen Schlüssel, um die Nachricht an Andreas zu verschlüsseln. Die verschlüsselte Nachricht schickt sie ab und nur Andreas kann sie wieder in Klartext verwandeln, weil nur er den passenden privaten Schlüssel hat.

Public Key Kryptographie

Allerdings kommt nun ein anderes Problem neu hinzu: Wie kann Anke sicher sein, dass der öffentliche Schlüssel von Andreas wirklich ihm gehört und nicht heimlich von einem Bösewicht ersetzt wurde? Ein Angreifer, der in der Lage ist, sich zwischen die beiden zu schalten, könnte Anke seinen eigenen öffentlichen Schlüssel statt den von Andreas unterschieben, die Nachrichten mit seinem eigenen privaten Schlüssel entschlüsseln und mitlesen und zum Schluss mit Andreas‘ echtem öffentlichen Schlüssel wieder verschlüsseln und an ihn weiter schicken.

Diesen Angriff nennt man auch Man-in-the-Middle-Attack, weil der Angreifer zwischen den beiden legitimen Kommunikationspartnern sitzt. Doch warum ist dieser Angriff in der Praxis so gefährlich? Stellen wir uns vor, wir wollen Online-Banking betreiben und uns dabei einer verschlüsselten Verbindung bedienen. Wir können uns nun den öffentlichen Schlüssel der Bank besorgen und unsere Überweisungsdaten senden. Nur wer garantiert, dass wir wirklich mit der Bank direkt Verbindung aufgenommen haben und nicht mit einem Bösewicht, der uns vorgaukelt, die Bank zu sein? Um uns zu täuschen, könnte ein solcher Angreifer im Hintergrund unsere Anfrage an die Bank und die Antwort der Bank an uns durchleiten und nur mithören, um im entscheidenden Moment, wenn wir eine Überweisung tätigen, seine eigene Kontonummer und einen höheren Betrag einzusetzen.

Wir brauchen also eine Garantie, dass der öffentliche Schlüssel auch echt ist. Am einfachsten könnten Anke und Andreas diese Garantie bekommen, in dem sie über einen anderen Kanal, zum Beispiel am Telefon oder am besten persönlich, die öffentlichen Schlüssel (oder eine Prüfsumme davon, den sogenannten Fingerprint) vergleichen. Bei diesem Abgleich ist es nicht entscheidend, dass Anke und Andreas nicht abgehört werden, denn die dabei ausgetauschte Information ist ja nicht geheim. Es muss nur sichergestellt sein, dass ein Angreifer diese Information nicht verändern kann.

Man-in-the-Middle-Angriff
Man-in-the-Middle-Angriff

Praktischerweise können Public-Key-Verschlüsselungsalgorithmen wie RSA so „zweckentfremdet“ werden, dass sie nicht verschlüsseln, sondern stattdessen die Echtheit einer Nachricht garantieren! Man muss dazu eine Nachricht (oder eine Prüfsumme davon) mit seinem privaten Schlüssel verschlüsseln. Ein Empfänger kann die Nachricht dann mit dem öffentlichen Schlüssel des Absenders entschlüsseln. Wenn dabei der Klartext herauskommt, ist garantiert, dass die Nachricht tatsächlich unverändert vom Absender kommt, denn nur der Absender hat Kenntnis seines privaten Schlüssels und nur wenn die Nachricht damit verschlüsselt wurde, wird mit dem öffentlichen Schlüssel wieder der Klartext sichtbar.

Die asymmetrische Kryptographie wurde also gar nicht zur Verschlüsselung, sondern zur digitalen Signatur eingesetzt, die wie eine handschriftliche Unterschrift die Echtheit einer Nachricht garantiert.

Das ist schon mal gut, man kann also mit digitalen Signaturen die Authentizität und Integrität von Nachrichten prüfen, aber noch haben wir das ursprüngliche Problem nicht gelöst, da wir ja die Authentizität des öffentlichen Schlüssels an sich prüfen müssen!

Die Lösung besteht darin, dass eine dritte Stelle, der sowohl Anke als auch Andreas vertrauen, den öffentlichen Schlüssel von Andreas digital signiert. Man spricht dann auch davon, dass diese dritte Stelle durch diese Signatur ein Zertifikat erstellt hat, das die Echtheit garantiert. Wenn Anke den öffentlichen Schlüssel der Zertifizierungsstelle kennt, kann sie nun mit dem Zertifikat die Echtheit des öffentlichen Schlüssels von Andreas prüfen. Damit das funktioniert, muss aber immer noch der öffentliche Schlüssel der Zertifizierungsstelle sicher übertragen werden. Außerdem müssen, wie schon geschrieben, Anke und Andreas der Zertifizierungsstelle vertrauen, deswegen nennt man diese auch Trust Center. Bis jetzt klingt das erst mal so, als hätten wir durch die Einführung des Trust Centers noch nicht viel gewonnen, da wir ja immer noch einen öffentlichen Schlüssel, den des Trust Centers, haben, den wir vor unerlaubter Veränderung geschützt verteilen müssen. Wenn wir aber dieses Problem auf das Internet übertragen, so sehen wir, dass tatsächlich eine Vereinfachung eingetreten ist: Wir müssen nicht mehr für jede beliebige Webseite selbst prüfen, ob der öffentliche Schlüssel stimmt, wenn diese ein Zertifikat eines Trust Centers vorweisen kann. Die öffentlichen Schlüssel des Trust Centers bekommen wir schon mit dem Browser oder dem Betriebssystem mitgeliefert! Das Gesamtsystem mit Zertifizierungsstellen und Schlüsselverteilung nennt man auch Public-Key-Infrastruktur.

Wenn man mal bei einer Webseite, die mit HTTPS beginnt, auf der Adresszeile des Browsers an die richtige Stelle klickt, bekommen wir die wichtigsten Informationen eines solchen Zertifikats direkt angezeigt, wie hier zum Beispiel von der Frankfurter Sparkasse, deren öffentlicher Schlüssel in seiner Echtheit von der VeriSign Inc. bestätigt wurde.

Frankfurter Sparkasse

Mit einem Klick auf „Weitere Informationen“ kann man noch viele Details erfahren, zum Beispiel welches genaue Verschlüsselungsverfahren verwendet wird, für welche Web-Adressen das Zertifikat genau gilt, wann es abläuft und so weiter. Es lohnt sich durchaus, sich das einmal genauer anzuschauen. Im übrigen wird die eigentliche Kommunikation symmetrisch verschlüsselt, mit dem asymmetrischen Verfahren wir nur ein temporärer Sitzungsschlüssel übertragen. Ein Grund dafür ist, dass Public-Key-Verfahren wie RSA sehr viel langsamer sind als symmetrische Verfahren wie das in der letzten Folge angesprochene AES. Außerdem sind sie anfälliger für bestimmte Arten von Angriffen. Man spricht von einem hybriden Kryptosystem, wenn symmetrische und asymmetrische Verfahren kombiniert werden.

Doch wo können wir nun Public-Key-Kryptographie einsetzen?

In der Praxis wird Public-Key-Kryptographie in der Variante wie beschrieben mit zentralen Zertifizierungsinstanzen (auch Certification Authority oder CA genannt) für sicheres Surfen im Web mit den Protokollen HTTPS bzw. SSL/TLS eingesetzt.

Für E-Mails gibt es das Protokoll S/MIME, das von den meisten Mailprogrammen unterstützt wird und ebenfalls auf von CAs signierte Zertfifikate setzt. Außerdem ist bei E-Mails das Protokoll PGP sehr weit verbreitet. Freie Implementierungen dieses Protokolls sind GnuPG bzw. Gpg4Win für Windows und GPGTools für den Mac. Wer Thunderbird als Mailprogramm verwendet, sollte sich das Plugin Enigmail anschauen. PGP basiert nicht auf zentralen CAs für die Echtheitsprüfung, stattdessen können Nutzer, die sich kennen, ihre öffentlichen Schlüssel gegenseitig signieren und somit selbst als Zertifizierungsinstanz für andere auftreten. Bei dieser dezentralen Public-Key-Infrastruktur spricht man vom Web-of-Trust.

Wer eine sichere Alternative zu SMS oder WhatsApp sucht, der sollte sich Threema anschauen. Anders als bei Apples iMessage, das laut Hersteller ebenfalls Ende-zu-Ende-Kryptographie verwendet, wird bei Threema der Schlüssel auf dem eigenen Endgerät erzeugt und nur der öffentliche Schlüssel zu einem Keyserver übertragen. Die Echtheit der Schlüssel kann bei einem persönlichen Kontakt über einen QR-Code verifiziert werden.

Ich kann nur jedem empfehlen, sich mit diesen Programmen zu beschäftigen und in Zukunft Mails und Kurznachrichten verschlüsselt zu versenden. Es tut nicht weh, ist innerhalb von ein paar Minuten eingerichtet und wer diesen Artikel bis hier gelesen hat, sollte die Grundprinzipien soweit verstanden haben.

Zum Abschluss in aller Kürze eine Zusammenfassung:

  • Es gibt asymmetrische Verschlüsselungsverfahren mit öffentlichen Schlüsseln zum Chiffrieren und privaten Schlüsseln zum Dechriffrieren.
  • Diese Systeme können auch für digitale Signaturen, also zur Prüfung von Authentizität und Integrität von Nachrichten, verwendet werden.
  • Die privaten Schlüssel darf man niemals herausgeben.
  • Bei öffentlichen Schlüsseln muss sichergestellt sein, dass sie wirklich zu dem Kommunikationspartner gehören, mit dem man Nachrichten austauschen möchte, sonst ist eine Man-in-the-Middle-Attack möglich. Die Prüfung kann durch von Zertifizierungsstellen ausgegebene Zertifikate geschehen.
  • Die Verbindung ist nur sicher, wenn die Nachricht beim Sender verschlüsselt und beim Empfänger wieder entschlüsselt wird, die Nachricht also auf der ganzen Strecke verschlüsselt bleibt. Man spricht dann von Ende-zu-Ende-Kryptographie.

Mit diesem Teil ist meine kleine Serie über Kryptographie abgeschlossen. Ich hoffe, es hat allen Lesern Spaß gemacht, mir von den alten Griechen bis in die Neuzeit zu folgen und ein wenig zum Verständnis beigetragen. Ich hoffe auch, dass ich vielleicht ein paar von Euch dazu motivieren kann, sich mit PGP zu beschäftigen und in Zukunft verschlüsselte Mails zu verschicken, damit es die NSA nicht all zu leicht hat. Ich freue mich über Feedback und verschlüsselte Mails, mein Public Key ist auf meiner Homepage und wer mag, kann mir auch eine Nachricht über Threema auf mein Smartphone schicken!

NSA hört nicht mit

Quellen und weiterführende Literatur:

[1] Albrecht Beutelspacher, Heike B. Neumann und Thomas Schwarzpaul: Kryptografie in Theorie und Praxis

[2] Ron L. Rivest, Adi Shamir und Leonard Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

NSA und der Angriff auf Verschlüsselung: Wie funktioniert das?

Die deutschen und internationalen Medien berichten heute darüber, dass die NSA die SSL-Verschlüsselung geknackt habe. Doch über die genaue Funktionsweise ist nicht viel bekannt, da die primären Quellen, der Guardian und die New York Times, einige Details, die sich in den Snowden-Dokumenten finden, absichtlich zurückhalten. Doch wenn man sich nur ein bisschen mit Kryptographie auskennt und Eins und Eins zusammenzählen kann, bleiben nicht viele Möglichkeiten übrig. Hier also eine kleine Auflistung der Angriffsmöglichkeiten und meine Spekulationen über das Wie und Warum der Vorgehensweise der NSA.

1. Zugriff auf die privaten Schlüssel der Zertifizierungsstellen

Die in SSL verwendete Public-Key-Infrastruktur setzt darauf, dass Zertifizierungsstellen die Echtheit der öffentlichen Schlüssel der Gegenstellen zertifizieren und somit bestätigen, dass der Kommunikationspartner auch der ist, der er zu sein vorgibt. Damit das funktioniert, müssen die öffentlichen Schlüssel der Zertifierungsstellen (auch Trust Center genannt) auf einem sicheren Weg auf die an der eigentlichen Kommunikation beteiligten Rechner übermittelt werden. Dies geschieht dadurch, dass in gängigen Browser oder auch im Betriebssystem selbst diese Schlüssel bereits mitgeliefert werden.

Hat nun jemand Zugriff auf die privaten Schlüssel der Zertifierungsstelle, kann dieser Angreifer selbst ein Zertifikat erstellen, das die Echtheit der öffentlichen Schlüssel eines Dritten bestätigt. Dadurch werden Man-in-the-Middle-Angriffe, die vom Angegriffenen nicht bemerkt werden, möglich, sofern der Angreifer in der Lage ist, in den Kommunikationsweg zwischen Sender und Empfänger entsprechend einzugreifen. Von letzterem muss man ausgehen, denn schließlich ist der Sinn und Zweck einer jeden Verschlüsselung, die Sicherheit in genau diesem Fall immer noch zu gewährleisten. Von dem, was vor den heutigen Veröffentlichungen schon bekannt war, muss man auch davon ausgehen, dass die US-amerikanischen und britischen Geheimdienste dies können.

Bewertung

Diese Art des Angriffs ist meiner Ansicht nach die wahrscheinlichste. Es genügt rein theoretisch, dass die Geheimdienste Zugriff auf den privaten Schlüssel einer einzigen Zertifizierungsstelle haben, um das System zu kompromittieren. Da sich ein guter Teil dieser Stellen in den USA befinden und von den früheren Berichten bereits bekannt ist, dass an Firmen wie Microsoft und Google Geld gezahlt wurde, um Hintertüren einzubauen, muss man wohl davon ausgehen, dass auch Zertifizierungsstellen betroffen sind. Damit der Angriff möglichst nicht auffällt, sollten natürlich aus Sicht des Angreifers möglichst viele Zertifizierungsstellen infiltriert werden, da die Angegriffenen bemerken könnten, dass der öffentliche Schlüssel seines Kommunikationspartners auf einmal von einem anderen Trust Center verifiziert wurde.

Vorteile

Für den Angreifer hat dieses Vorgehen den Vorteil, dass es bei Zugriff sowohl auf die Netzinfrastruktur als auch auf die Zertifizierungsstellen – beides ist bei den Geheimdiensten gegeben! – sehr leicht durchzuführen und vom Angegriffenen nur schwer bis gar nicht zu bemerken ist. Außerdem ermöglicht es eine weitreichende oder gar flächendeckende Überwachung, wie sie mit einem Angriff auf die Rechner einzelner Ziele nicht möglich wäre. Bei der Zertifizierungsstelle müssen außerdem nicht viele Personen eingeweiht sein, es reicht im Prinzip eine einzige Person, die Zugriff auf den Private Key hat.

Nachteile

Für den Angreifer eigentlich keine, außer dass die Gefahr besteht, dass beim Trust Center oder dem Geheimdienst jemand die sprichwörtliche Pfeife bläst.

Gegenmaßnahmen

Zertifizerungsstellen, die kompromittiert sind, nicht vertrauen. Leider ist derzeit nicht bekannt, welche das sind. Es wäre wohl davon auszugehen, dass die meisten, wenn nicht alle, Trust Center in den USA und wahrscheinlich auch solche aus Kanada, Australien und dem Vereinigten Königreich betroffen sind.

2. Angriff auf die Algorithmen

Bekannte Public-Key-Algorithmen, die im SSL-Protokoll verwendet werden, sind RSA und Diffie-Hellman. Die Sicherheit dieser Verfahren basiert darauf, dass keine schnellen Verfahren bekannt sind, den diskreten Logarithmus einer großen Zahl zu berechnen.

Bewertung

Es ist mathematisch nicht bewiesen, dass es keinen Algorithmus zur Berechnung des diskreten Logarithmus in polynomialer Laufzeit geben kann. In der Forschung hat es vor kurzem Fortschritte zur Entwicklung eines solchen Algorithmus gegeben. Es gibt Stimmen, die davon ausgehen, dass schon in vier bis fünf Jahren RSA nicht mehr sicher ist. Sollte man bei der NSA schon weiter sein als die internationale Forschungsgemeinschaft und ein schneller Algorithmus zur Berechnung des diskreten Logarithmus bekannt sein, wäre der Verschlüsselungsalgorithmus an sich gebrochen. Kryptographie mit elliptischen Kurven gilt aber derzeit noch als bedeutend sicherer als RSA, da das Problem des diskreten Logarithmus auf elliptischen Kurven schwerer zu lösen ist.

Insgesamt muss man aber sagen, dass es zumindest unklar und nicht unbedingt wahrscheinlich ist, dass es wirklich einen effizienten Algorithmus zur Berechnung des diskreten Logarithmus gibt, der der Öffentlichkeit noch nicht bekannt ist und dass die NSA oder ein anderer Geheimdienst das geschafft hat, was Heerscharen von Mathematikern öffentlich versuchen.

Andererseits war es ja auch schon bei DES so, dass nachweislich differentielle Kryptanalyse bei der NSA und bei IBM schon lange bekannt war, bevor diese Angriffsmethode öffentlich wurde.

Vorteile

Hätte die NSA die Algorithmen an sich gebrochen, wäre auch jedes Protokoll, dass auf diesen Algorithmen basiert, unsicher, selbst wenn das Protokoll keine Hintertüren hat.

Nachteile

Auch wenn es effizientere Verfahren als die derzeit bekannten gibt, um den diskreten Logarithmus zu berechnen, wäre vermutlich immer noch ein riesiger Rechenaufwand nötig, um den Geheimtext zu entschlüsseln. Das wäre aber nicht praktikabel für eine flächendeckende Überwachung, allenfalls für das Abhören einzelner Ziele.

Gegenmaßnahmen

Keine. Nach derzeitigem Stand sind Elliptische Kurven und Diffie-Hellman sicherer als RSA (auch wegen der Forward Secrecy bei Diffie-Hellman), aber wenn das mathematische Problem gelöst ist, wären auch diese betroffen.

3. Angriff auf die Endstellen

Ein direkter Angriff auf die Endstellen der Kommunikation, sprich die Rechner der Angegriffenen, ist natürlich auch denkbar, denn dann besteht Zugriff auf den Klartext. Das hat dann aber nichts mehr mit SSL oder irgend einem Protokoll zu tun.

Bewertung

Ein Angriff auf die Endstellen, oder zumindest der Versuch, im Stil eines „Staatstrojaners“ oder gar einer systematischen Hintertüren in Betriebssystem, Browsern oder anderer Software ist natürlich möglich, hat aber vermutlich nichts mit der aktuellen Berichterstattung zu tun.

Vorteile

Zugriff auf den unverschlüsselten Klartext.

Nachteile

Nicht für flächendeckende Überwachung geeignet. Außerdem könnte die Existenz von Hintertüren oder allgemein eines solchen Angriffs im Vergleich zu den anderen Methoden relativ leicht bemerkt werden.

Gegenmaßnahmen

Das eigene System möglichst gegen Angriffe von außen sichern, was eigentlich sowieso „best practice“ ist. Außerdem Software einsetzen, die wahrscheinlich keine Hintertüren hat, also am besten Open Source Software, die man selber kompiliert.

Schlussbetrachtung

Wahrscheinlich geht es bei der heutigen Berichterstattung, auch wenn keine technischen Details genannt wurden, um Variante 1.

Was sollte man davon als Internetnutzer ableiten? Man sollte jedenfalls nicht auf die Idee kommen, auf SSL zu verzichten. Ein Angriff in diesem Stil setzt Möglichkeiten voraus, die ein Geheimdienst hat, aber ein x-beliebiger Krimineller nicht. Also muss man davon ausgehen, dass SSL immer noch genügend Schutz bietet, das eigene Homebanking gegen kriminelle Machenschaften zu sichern, aber nicht dazu, vertrauliche Kommunikation vor Geheimdiensten geheim zu halten. Das heißt insbesondere, dass solche Werbeversprechen wie die von deutschen E-Mail-Anbietern neulich, SSL zur Kommunikation zwischen den Betreibern einzusetzen, Augenwischerei sind, zumal die Mails dann sowieso auf den Servern der Anbieter unverschlüsselt vorliegen.

Um private Kommunikation zu sichern, sollte man auf End-zu-End-Protokolle wie PGP setzen. Dann bleiben als Angriffsmöglichkeiten, auch für Geheimdienste, nur die Varianten 2 und 3. Zumindest kann man sich so einer flächendeckenden Überwachung entziehen, aber es schützt vermutlich nur unzureichend, wenn man Ziel einer direkten Beobachtung wird.

Einen Schutz gegen alle Angriffe bietet eigentlich nur folgendes: Der Klartext wird nur auf einem Rechner betrachtet, der nicht mit dem Internet verbunden ist und das in Zukunft auch niemals wird. Dort wird auch verschlüsselt, und zwar mit einem sicheren, symmetrischen Algorithmus, dessen Schlüssel auf einem sicheren Weg – das heißt durch persönliche Übergabe – übetragen wird, vielleicht sogar mit einem One-Time-Pad (oder auch lieber ohne One-Time-Pad, wie Schneier meint?). Der Transfer des Geheimtextes von diesem Rechner zur Außenwelt, also über einen Rechner, der mit dem Internet verbunden ist, geschieht ausschließlich über physische Datenträger. Kein Kabel! Ein USB-Stick, Disketten, CD-ROMs oder vielleicht sogar auf einem Blatt Papier, das ausgedruckt und eingescannt wird. Oder durch Abtippen des Geheimtextes. Aber ob man in der Praxis so weit gehen will…?

Wer mir verschlüsselte E-Mails schicken will, kann dazu meinen PGP Public Key verwenden, der auf meiner Homepage veröffentlicht ist. Außerdem benutze ich Threema.

Kryptographie, Teil 5: Moderne Blockchiffren

In den Teilen 1 bis 4 waren historische Verschlüsselungsverfahren bis hin schreibmaschinenartigen, mechanischen Rotormaschinen, die etwa ab den 1920er Jahren im Einsatz waren, Thema. Dabei wurde aufgezeigt, dass zwar die besprochenen Verfahren (bis auf das One-Time-Pad) nicht sicher sind, aber viele Grundsätze heute noch Gültigkeit haben.

Zunächst wurden zwar mechanische Verschlüsselungsapparate noch bis in die 1970 Jahre eingesetzt und sogar für sicher gehalten, nicht zuletzt, weil von den Briten lange geheim gehalten wurde, dass die Enigma-Verschlüsselung gebrochen war. Aber natürlich mussten mit Aufkommen der Computertechnik neue Methoden gefunden werden. So wurde in den 1970er Jahren bei IBM die Entwicklung von Verschlüsselungsverfahren gestartet. Ein wichtiges Zwischenergebnis waren die von IBM-Mitarbeiter Horst Feistel entwickelten Feistel-Netzwerke.

Feistel-Netzwerk
Feistel-Netzwerk

Bei einem Feistel-Netzwerk werden Blöcke von Bits über mehrere Runden hinweg nach folgendem Schema verschlüsselt: Zunächst wird eine Bitfolge in einen linken und rechten Halb-Block geteilt. Der rechte Halbblock wird direkt zum linken Halbblock der folgenden Runde. Außerdem dient der rechte Halbblock als Eingabe für eine Funktion, die vom Schlüssel und einem sogenannten Rundenschlüssel abhängt. Das Ergebnis dieser Funktion wird mit dem linken Halbblock exklusiv-oder-verknüpft und zum neuen rechten Halbblock. Diese Berechnung wird über mehrere Runden hinweg wiederholt. Die Rundenschlüssel sind für jede Runde verschieden und werden aus dem Schlüssel berechnet. Durch die Struktur des Netzwerks an sich ist sichergestellt, dass aus einem Geheimtext-Block mit Kenntnis des Schlüssels auch umgekehrt wieder der zugehörige Klartext-Block berechnet werden kann.

Ein Feistel-Netzwerk ist die Basis für den im Jahr 1976 veröffentlichen Data Encryption Standard (DES). Der DES-Algorithmus verschlüsselt Blöcke von 64 Bit Länge in 16 Runden mit Hilfe eines 56 Bit langen Schlüssels.

Die eigentliche Verschlüsselungsfunktion F (siehe Diagramm oben) ist etwas komplexer und basiert unter anderem auf einer fest definierten Substitution von Bitfolgen nach sogenannten S-Boxen, die in Abhängigkeit eines aus dem Schlüssel berechneten Rundenschlüssels ausgewählt werden. Eine genauere Beschreibung würde den Rahmen dieses Artikels sprengen, kann aber in der einschlägigen Literatur (siehe unten) oder auch im Wikipedia-Artikel zum Data Encrpytion Standard nachgelesen werden, denn wie alle guten Algorithmen ist auch der DES komplett offengelegt. Auch für die modernen Verfahren gilt nämlich selbstverständlich der Grundsatz, dass es keine Sicherheit durch Geheimhaltung des Verfahrens gibt („security through obscurity“), sondern dass nur der Schlüssel (und selbstverständlich der Klartext) geheim gehalten werden müssen.

Bei der Entwicklung war interessanterweise auch der heutzutage aus den Schlagzeilen bekannte US-Geheimdienst NSA beteiligt. Die NSA wollte eine kürzere Schlüssellänge, was ein Knacken der Verschlüsselung durch simples Ausprobieren aller möglichen Schlüssel („brute-force-Angriff“) natürlich vereinfacht. Aber abgesehen davon muss man davon ausgehen, dass die NSA nicht etwa versucht hat, durch Einflussnahme den Algorithmus zu schwächen. Vielmehr ist es so, dass die NSA bei den S-Boxen sogar die Resistenz gegen eine damals noch nicht öffentlich, wohl aber IBM und der NSA bekannte Art von Angriffen, der differentiellen Kryptanalyse, gesteigert hat.

NSA

DES gilt heute insbesondere wegen der für heutige Verhältnisse recht kurzen Schlüssellänge und der Weiterentwicklung der Technik nicht mehr als ausreichend sicher, allerdings wird die Variante „Triple-DES“ mit 112 Bit langen Schlüsseln noch stellenweise verwendet.

Der aktuelle Standard heißt AES, Advanced Encryption Standard. Der Algorithmus wurde 1998 unter dem Namen Rijndael (nach den Nachnamen seiner Entwickler Joan Daemen und Vincent Rijmen) entwickelt, setzte sich im Rahmen eines Wettbewerbs durch und wurde 2000 vom US National Institute of Standards and Technology (NIST). AES ist anders als DES kein Feistel-Netzwerk, sondern ein sogenanntes Substitutions-Permutations-Netzwerk. Der grundlegende Ablauf ist aber ähnlich: Es wird ein Block über mehrere Runden hinweg verschlüsselt und dabei S-Boxen (Substitution) und bei AES noch sogenannte P-Boxen (Permutation) verwendet.

AES verschlüsselt 128 Bit lange Blöcke, die Schlüssellänge beträgt 128, 192 oder 256 Bit und die Anzahl der Runden ist abhängig von der Schlüssellänge 10, 12 oder 14. Wie DES ist auch AES offengelegt, über einen langen Zeitraum hinweg von Wissenschaftlern öffentlich diskutiert, analysiert und für sicher befunden worden.

Da DES und AES jeweils Klartext-Blöcke verschlüsseln, spricht man auch von Blockchiffren. Streng genommen handelt es sich also dabei um eine monoalphabetische Substitution, nur dass nicht einzelne Zeichen (oder sagen wir 8 Bit-Blöcke), sondern längere Blöcke subsitutiert werden. Wird eine Blockchiffre so verwendet, spricht man vom ECB– oder Electronic-Codebook-Modus.

Tatsächlich ist es nun so, dass zwar statistische Angriffe, wie sie im zweiten und dritten Teil dieser Serie genannt wurden, zwar durch die längere Blockgröße (oder sagen wir das größere Alphabet) deutlich erschwert werden, aber je nach Klartext nicht völlig unmöglich gemacht werden. Insbesondere bei der Verschlüsselung von unkomprimierten Bilddateien werden Muster nur unzureichend verwischt, wie das Bildbeispiel bei Wikipedia eindrücklich zeigt.

Um diese Schwäche zu vermeiden, setzt man verkettete Verschlüsselungsmodi ein.

Cipher Block Chaining
Cipher Block Chaining

Vor der eigentlichen Verschlüsselung mit der Blockchiffre (also z.B. AES) wird der Klartext-Block mit dem vorhergehenden Geheimtext-Block exklusiv-oder-verknüpft. Da es beim ersten Block noch keinen vorhergehenden Geheimtext-Block gibt, wird stattdessen ein sogenannter Initialisierungsvektor verwendet, der als zusätzlicher Teil des Schlüssels aufgefasst werden kann. Diese Art der verketteten Verschlüsselung nennt man Cipher Block Chaining Mode oder kurz CBC.

Eine solche Verkettung kann auch auf andere Arten geschehen. Besondere Beachtung verdient dabei noch der Output Feedback Mode, kurz OFB.

Output Feedback
Output Feedback

Das Bemerkenswerte hier ist, dass der Klartext gar nicht mit der Blockchiffre verschlüsselt wird! Schaut man sich das Schema einmal genauer an, stellt man fest, dass der eigentliche Verschlüsselungsalgorithmus ausschließlich dazu benutzt wird, eine Pseudo-Zufallszahlenfolge zu erzeugen, die dann mit dem Klartext exklusiv-oder-verknüpft wird. Dieses Vorgehen sollte aus dem dritten und vierten Teil dieser Serie bekannt vorkommen: Aus einem kurzen Schlüssel wird ein langer erzeugt, die eigentliche Verschlüsselung ist dann im Stil eines One-Time-Pads. Im Gegensatz zum echten One-Time-Pad ist aber keine absolute Sicherheit gegeben, da die erzeugte Bit-Folge ja nicht echt zufällig, sondern nur pseudo-zufällig ist.

Beachtenswert ist auch, dass zum Entschlüsseln eines mit einer Blockchiffre im OFB-Modus verschlüsselten Textes die Entschlüsselung der Blockchiffre gar nicht benötigt wird, sondern nur die Verschlüsselung. Die Blockchiffre dient schließlich nur dazu, eine Zufalls-Bitfolge zu erzeugen, die den Schlüssel für die eigentliche Ver- bzw. Entschlüsselung bildet.

Eine kleine Abwandlung des OFB ist der Cipher Feedback Mode CFB.

Cipher Feedback
Cipher Feedback

Vergleichen wir die drei bisher gezeigten Feedback-Modi, so stellt man folgendes fest: Beim OFB und beim CFB kommt der Klartext gar nicht mit dem eigentlichen Chiffrieralgorithmus in Berührung. Der Chiffrieralgorithmus dient in diesen Fällen nur dazu, eine Zufallszahlenfolge zu erzeugen und braucht auch gar nicht zu entschlüsseln. Es kann also statt einer echten Blockchiffre auch eine andere Einwegfunktion verwendet werden.

Beim CBC und CFB wird der Geheimtext als Feedback benutzt. Dies ist dann entscheidend, wenn auf dem Weg vom Sender zum Empfänger Datenblöcke verloren gehen. Beim OFB muss der Empfänger genau wissen, der wievielte Block gerade entschlüsselt werden soll. Beim CBC und CFB reicht es aus, den vorausgegangenen Geheimtextblock zu kennen, um ab diesem Punkt die Nachricht weiter entschlüsseln zu können.

Als letztes betrachten wir noch den Counter Mode (CTR).

Counter
Counter

Statt eines Feedbacks wird dem Initialisierungsvektor (Nonce) lediglich ein Zähler hinzugefügt, aber wie beim CFB und OFB wird die Blockchiffre nur zur Erzeugung des eigentlichen Schlüssels verwendet. Der Vorteil gegenüber den anderen Verkettungsmodi besteht darin, dass alle Blöcke parallel verarbeitet werden können und entsprechend auch komplett unabhängig voneinander wieder dechiffriert werden können, wenn bekannt ist, um welchen Block es sich handelt.

Um den heutigen Artikel noch kurz zusammenzufassen: Die standardisierten Verschlüsselungsverfahren DES und der moderne AES sind sogenannte Blockchiffren, die Blöcke einer bestimmten Länge verschlüsseln und dafür mehrere Runden benötigen. Blockchiffren können entweder direkt blockweise im Electronic-Codebook-Modus verwendet werden, was aber nicht empfehlenswert ist, da Muster im Klartext ähnlich wie bei einer monoalphabetischen Chiffre nur unzureichend verwischt werden. Besser ist, einen verketteten Modus wie die hier gezeigten CBC, CFB, OFB oder CTR zu verwenden.

Die bisher gezeigten Verfahren haben alle die Eigenschaft, dass Sender und Empfänger einer verschlüsselten Nachricht vorher einen gemeinsamen Schlüssel getauscht haben müssen und nur mit Kenntnis des geheimen Schlüssels sowohl ver- als auch entschlüsselt werden kann. Wie man verschlüsselt kommunizieren kann, auch ohne dass man vorher persönlich einen Schlüssel ausgetauscht haben muss, werden wir in der nächsten Folge betrachten.

Quellen und weiterführende Literatur:

[1] Reinhard Wobst: “Abenteuer Kryptologie”

Kryptographie, Teil 4: Enigma

Im dritten Teil der Serie über Kryptographie wurde unter anderem die Vigenère-Chiffre besprochen. Die große Gefahr und die Anfälligkeit dieses Algorithmus für Angriffe, bei denen ein Teil des Klartextets bekannt ist, begründeten sich durch die verhältnismäßig kurze Schlüssellänge. Bei der One-Time-Pad-Verschlüsselung wird das Problem dadurch umgangen, dass der Schlüssel genau so lang wie der Klartext gewählt wird. Bei allen damit verbundenen praktischen Problemen ist dies jedoch in den meisten Fällen kein anwendbares Verfahren.

Enigma
Detailaufnahme einer Enigma-Maschine mit Tastatur, Ausgabe-Lämpchen und Steckbrett

Ein Lösungsansatz ist der Versuch, vereinfacht gesprochen aus einem kurzen Schlüssel einen langen zu machen. Das One-Time-Pad ist deswegen sicher, weil eine lange Folge von Zufallswerten als Schlüssel dient. Ein praxistaugliches Verschlüsselungsverfahren nach diesem Prinzip muss also darauf basieren, aus einem kurzen Schlüssel eine lange Folge von Pseudo-Zufallszahlen zu generieren. Diese müssen sich deterministisch aus dem Schlüssel ergeben, sonst wäre auch mit Kenntnis des Schlüssels ein Dechiffrieren unmöglich.

Anfang des 20. Jahrhunderts gab es erste Entwicklungen, dieses Problem elektromechanisch zu lösen. Bei diesen elektrisch betriebenen Maschinen wurde über eine Schreibmaschinentastatur der Klartext eingegeben und über Lämpchen bei jedem Tastendruck der entsprechende Buchstabe des Geheimtexts angezeigt. Die Maschinen sind mit elektrisch betriebenen Walzen, sogenannten Rotoren, ausgestattet, die sich bei jedem Tastendruck weiter drehen, bei jeder Stellung eine andere Verdrahtung haben und somit für jeden Tastendruck eine andere Zuordnung von Klartext- zu Geheimtext-Buchstaben hervorrufen. In Abhängigkeit von der Stellung der Rotoren vor Beginn des Verschlüsselungsvorgangs ergibt sich bei diesen Rotormaschinen eine verschiedene, sehr lange Folge von unterschiedlichen Verdrahtungen. Aus einem kurzen Schlüssel, nämlich der Grundstellung der Rotoren, ergibt sich quasi eine Vigenère-Verschlüsselung mit einem sehr langen Schlüssel.

Engima
Zwei Varianten der Enigma-Maschine im Museum für Kommunikation in Frankfurt am Main

Eine Vertreterin dieser Klasse ist die 1918 entwickelte Enigma-Maschine, die ihre große Bekanntheit ihrer Verwendung durch die deutsche Wehrmacht, insbesondere der Marine, im 2. Weltkrieg verdankt. Die Enigma wurde in mehreren Varianten mit 3 oder 4 Rotoren und einer zusätzlichen Verwürfelung über die freie Verkabelung eines Steckbretts eingesetzt.

Schon bei der Ausführung mit 3 Rotoren erzeugt die Enigma eine Verschlüsselung, die sich erst nach über 17.000 Zeichen wiederholt. Dies stellt einen erheblichen Sicherheitsgewinn gegenüber einer simplen Vigenère-Chiffre dar. Dennoch konnte die Enigma-Verschlüsselung durch die Briten (nach Vorarbeit durch Polen) unter Führung des Mathematikers Alan Turing gebrochen werden.

Skulptur Alan Turings
Skulptur Alan Turings, Foto von Jon Callas, CC BY 2.0

Die Enigma hatte einige Schwächen, die für Angriffe ausgenutzt werden konnten. So wurde zum Beispiel niemals ein Klartext-Buchstabe im Geheimtext auf den selben Buchstaben abgebildet, also ein „A“ im Klartext wurde niemals ein „A“ im Geheimtext, ein „B“ niemals ein „B“, und so weiter. Was auf den ersten Blick wie eine gute Idee aussieht, ermöglicht in Wahrheit einen Angriff über eine sogenannte negative Mustersuche. Ist beispielsweise bekannt, dass das Wort „UBOOT“ irgendwo im Klartext stehen muss, kann man versuchen, die Stelle im Geheimtext zu bestimmten, an der dieses Wort steht. Man muss dazu wie im folgenden Beispiel nach Übereinstimmungen von Klartext- und Geheimtext-Buchstaben suchen und kann bestimmte Positionen ausschließen.

 Geheimtext: NVGOXUBNKSLTPT
Wahrscheinliches Wort: UBOOT
 UBOOT 
  UBOOT 
   UBOOT 
    UBOOT 
     UBOOT 
      UBOOT 
       UBOOT 
        UBOOT 
         UBOOT

Nur an den bestimmten Stellen, hier kursiv dargestellt, kann das Wort „UBOOT“ im Klartext stehen, an den anderen Stellen gibt es mindestens eine Übereinstimmung eines Klartext- mit einem Geheimtextbuchstaben, was bei der Konstruktion der Enigma aber nicht vorkommen kann.

Durch diese Schwachstelle allein kann die Verschlüsselung der Enigma noch nicht gebrochen werden, allerdings kann, wenn die Position eines Wortes erst einmal bekannt ist, mit anderen Angriffen fortgefahren werden, zum Beispiel mit der im 3. Teil gezeigten known-plaintext-Angriff. Dieser gestaltet sich immer noch schwieriger als bei Vigenère, da sich, wie schon gesagt, der Schlüssel erst nach über 17.000 Zeichen wiederholt, aber da die Erzeugung der Verschlüsselung über die Rotoren auch wieder bestimmten Gesetzmäßigkeiten unterliegt, konnte sich die Gruppe um Turing Schritt für Schritt zur Entschlüsselung vorarbeiten. Turing konstruierte zur vollständigen Entschlüsselung des Geheimtextes elektromechanische Maschinen, die einen Schlüsselraum systematisch durchsuchten. Diese Maschinen wurden wegen ihres charakteristischen Tickens auch als Turing-Bomben bezeichnet. Die Menge der auszuprobierenden Schlüssel konnte durch Analysen wie die eben beschrieben negative Mustersuche stark eingeschränkt werden, was ein effektives Brechen der Verschlüsselung erst ermöglichte.

Enigma mit drei Walzen
Detail einer Enigma-Maschine mit drei Rotoren

Übrigens wurden teilweise von den Allierten sogar gezielt Maßnahmen durchgeführt, um bestimmte Funksprüche auszulösen, die dann einen bekannten Klartext beinhalteten, der dann für Angriffe wie die oben beschriebenen ausgenutzt wurde. So wird berichtet, dass gezielt Leuchtbojen bombardiert wurden, um Funksprüche wie „Leuchttonne ist erloschen“ zu provozieren. [1] [2] Ein solches Vorgehen führt zu einem in der Kryptologie auch als chosen plaintext attack bezeichneten Angriff; also ein Angriff basierend auf durch den Angreifer ausgesuchten Klartext.

Doch was können wir aus diesen Betrachtungen über Rotormaschinen wie die Enigma für heute ableiten? Folgende Punkte haben nach wie vor Gültigkeit:

  • Viele Verschlüsselsalgorithmen basieren darauf, aus einem relativ kurzen Schlüssel eine lange Folge von Pseudo-Zufallszahlen zu erzeugen.
  • Nicht jede vermeintliche Verbesserung führt tatsächlich zu einer Erhöhung der Sicherheit, sondern manchmal sogar zu einer Verschlechterung.
  • Ein Verschlüsselungsalgorithmus ist schlecht, wenn es Angriffe gibt, die bedeutend effektiver sind als ein banales Ausprobieren aller möglichen Schlüssel. Gute Verschlüsselungsverfahren müssen gegen viele Arten von Angriffen resistent sein, darunter auch chosen plaintext attacks.

Wegen des zweiten Punktes gelten aktuelle Verschlüsselungsalgorithmen nur dann als sicher, wenn sie offengelegt sind und jahrelang von Wissenschaftlern auf mögliche Schwachstellen untersucht wurden.

In den kommenden Folgen werden wir uns neueren Verschlüsselungsverfahren der Gegenwart widmen.

Quellen und weiterführende Literatur:

[1] Reinhard Wobst: „Abenteuer Kryptologie“

[2] Friedrich L. Bauer: „Kryptologie : Methoden und Maximen“

 

Kryptographie, Teil 3: Vigenère und One-Time-Pad

In der vorherigen Folge haben wir uns zunächst mit Chiffren beschäftigt, bei denen die Buchstaben der Klartext-Nachricht nicht geändert, sondern lediglich anders angeordnet wurden: den Transpositionschiffren. Außerdem ging es um klassische Geheimschriften, bei denen die Buchstaben des Klartextes durch andere Zeichen ersetzt wurden: Substitutionschiffren.

Bei der Substitution, die bisher betrachtet wurde, handelt es sich um eine eingeschränkte Form: Jedes bestimmte Zeichen des Klartexts wird im Geheimtext stets durch das selbe Geheim-Zeichen ersetzt. Aus „A“ wird immer „C“, aus „B“ wird immer „D“ und so weiter. Man spricht daher von einer monoalphabetischen Substitution. Wie bereits besprochen, lässt sich eine solche Chiffre leicht durch eine statistische Analyse aushebeln.

Verschlüsselung
Ein verschlüsselter Rechner

Eine Verbesserung lässt sich nun dadurch erreichen, dass ein Klar-Zeichen nicht immer durch das gleiche, sondern durch verschiedene Geheim-Zeichen ersetzt wird. Man spricht dann von einer polyalphabetischen Substitution. Die einfachste Variante ist, häufig vorkommenden Buchstaben wie dem „E“ oder anderen Vokalen mehr als nur ein Geheimzeichen zuzuordnen und nach dem Zufallsprinzip mal das eine und mal das andere zu verwenden. Ziel ist es, eine all zu einfache statistische Analyse auszuhebeln. Dieses Verfahren wird homophone Chiffre genannt. Aber auch mit diesem Verfahren gibt es immer noch genügend Möglichkeiten, allein durch eine statistische Analyse des Geheimtextes den Klartext wiederherzustellen. Es gibt schließlich nicht nur eine Statistik über die Häufigkeit einzelner Buchstaben, man kann auch Buchstabenpaare, Besonderheiten am Wortanfang oder -ende und häufig vorkommende Worte oder Phrasen zur Analyse heranziehen.

Ein Weg, der etwas mehr bringt, ist in Abhängigkeit von der Position eines Klartextzeichens jeweils ein anderes Geheimtextzeichen zu verwenden. Beim Vigenère-Verfahren, benannt nach Blaise de Vigenère (1523–1596), wird in Abhängigkeit eines Passworts für jeden Buchstaben des Klartexts eine andere Caesar-Chiffre verwendet. Ist der Klartext länger als das Passwort, wird das Passwort wiederholt. Am deutlichsten wird das anhand eines Beispiels:

Klartext:   UND DAS WAR ES WORUEBER SIE SPRACHEN
Passwort:   HANSHANSHANSHANSHANSHANSHANSHANSHANS
Geheimtext: COR LBW EBF MT PWSIXJFF AJS AQPTKISG

Zu jedem Klartext-Buchstaben wird beim Verschlüsseln sozusagen ein Buchstabe des Passworts addiert, zum Entschlüsseln geht man umgekehrt vor.

Besonders sicher ist dieser Algorithmus aber immer noch nicht. Der Geheimtext lässt sich nämlich immer noch statistisch analysieren. Ist erst einmal die Länge des Passworts bekannt, ist das sogar sehr leicht, denn dann folgen alle Zeichen, die mit dem selben Passwort-Buchstaben verschlüsselt wurden (im Beispiel also jeder vierte Buchstabe), wieder der selben charakteristischen Häufigkeitsverteilung. Die Länge des Passworts lässt sich durch andere statistische Verfahren, die hier aber nicht erklärt werden sollen (wer möchte, kann nachschlagen, zum Beispiel in dem bereits in der letzten Folge erwähnten Buch von Beutelspacher), oder ganz simpel durch Ausprobieren herausbekommen.

Ein anderer Angriff ist jedoch viel gefährlicher und führt einen Bösewicht, der eine verschlüsselte Nachricht abfangen will, auf einem viel schnelleren Weg zum Ziel. In der Praxis ist es nämlich oft so, dass einem Angreifer Teile des Klartextes schon bekannt sind. Vielleicht ist es der Name eines Ortes oder einer Person oder sonst irgendein Wort, das im Text vorkommt. Hält man sich noch einmal vor Augen, wie beim Vigenère-Verfahren der Geheimtext aus Klartext und Passwort berechnet wird, so wird klar, dass sich umgekehrt aus Geheim- und Klartext auch das Passwort trivial durch Subtraktion berechnen lässt. Im folgenden Beispiel sind die dem Angreifer bisher unbekannten Zeichen des Klartexts noch Fragezeichen, ein Wort und der dazugehörige Geheimtext sind ihm aber bekannt. Das Passwort kann dann an der fraglichen Stelle leicht zurückberechnet werden:

Klartext:   ??? ??? ??? ?? WORUEBER ??? ????????
Passwort:                  SHANSHAN 
Geheimtext: COR LBW EBF MT PWSIXJFF AJS AQPTKISG

Da das Passwort üblicherweise kürzer als der Klartext ist, kann man schon an der entscheidenen Stelle erkennen, dass es sich hier wiederholt. Ist dem Angreifer das Passwort erst einmal bekannt, kann er natürlich jetzt auch den Rest des Geheimtextes entziffern.

Diese Art des Angriffs, bei der dem Angreifer ein Teil des Klartexts bekannt ist, nennt man known plaintext attack. Im Gegensatz dazu heißt ein Angriff, bei dem nur der Geheimtext abgefangen wurde, known ciphertext attack oder auch ciphertext only attack. Bis hier können wir also zusammenfassen, dass sich die einfache monoalphabetische Codierung bereits mit einem known ciphertext-Angriff auf Basis von Statistik sehr leicht brechen lässt. Auch die Vigenère-Chiffre ist anfällig für einen solchen statistischen Angriff, wenn er auch etwas schwieriger durchzuführen ist. Bei einem known plaintext-Angriff dagegen bricht die Sicherheit beider Verfahren direkt zusammen.

Würde man eine Vigenère-Chiffre heutzutage einsetzen und dabei ganze Dateien verschlüsseln, haben wir übrigens geradezu trivialerweise eine known plaintext-Situation vorliegen: Dateien vieler bekannter Dateiformate starten mit sogenannten magic numbers oder sonstigen Zeichenfolgen, die die Art der Datei oder die Versionsnummer des Formats oder ähnliches beschreiben. Ist das Dateiformat der zu entschlüsselnden Datei bekannt, ist also sofort auch ein Teil des Klartextes bekannt und das Vigenère-Verfahren somit völlig wertlos.

Doch warum sind die bisher besprochenen Angriffe bei der Vigenère-Chiffre so gefährlich? Wie bereits erwähnt, besteht die Gefahr darin, dass das Passwort, also der Schlüssel, im Vergleich zum Klartext recht kurz ist und sich daher wiederholen muss. Nur durch die Wiederholung konnten die statistische Analyse und auch der oben gezeigte known plaintext-Angriff überhaupt erst erfolgreich sein: Ist der Schlüssel an einer Stelle berechnet, kann er an allen anderen Stellen eingesetzt werden.

Blaise de Vigenère
Blaise de Vigenère

Doch was wäre, wenn sich das Schlüsselwort nicht wiederholt, wenn also der Schlüssel genau so lang wie der Klartext ist?

In diesem Fall hätten wir durch unsere obigen Angriffe rein gar nichts gewonnen! Eine statistische Analyse wäre nicht möglich, da die einzelnen Zeichen im Geheimtext keiner Häufigkeitsverteilung mehr folgen und eine Zurückberechnung des Schlüsselworts an einer Stelle wie beim known plaintext-Angriff würde zu nichts führen, eben weil sich der Schlüssel ja nirgends wiederholt!

Auf diese Art wird aus dem unsicheren Vigenère-Algorithmus das einzige Verschlüsselungsverfahren, das wirklich unknackbar ist, was man sogar mathematisch beweisen kann: Das One-Time-Pad!

Damit die Sicherheit des One-Time-Pads gewährleistet ist, müssen aber einige Bedinungen erfüllt sein: Zunächst einmal muss der Schlüssel mindestens genau so lang wie der Klartext sein, damit an keiner Stelle eine Wiederholung auftritt. Der Schlüssel selbst sollte außerdem kein Wort oder natürlicher Text sein. Der Grund ist simpel: Die Buchstaben eines Textes folgen ja wie schon bereits besprochen einer statistischen Verteilung und die kann man für einen Angriff ausnutzen.

Der Schlüssel muss also zufällig erzeugt werden. Das ist gar nicht so leicht, wie es sich auf den ersten Blick anhört. Denn wie erzeugt man eine so große Menge an Zufallswerten? Wer etwas programmieren kann, könnte vielleicht auf die Idee kommen, den Zufallsgenerator des Computers in der favorisierten Programmiersprache zu benutzen. Aber Vorsicht: Die Zahlen, die dieser ausspuckt, sind alles andere als zufällig. Sie wiederholen sich irgendwann und folgen einem – wenn auch auf den ersten Blick schwer zu durchschauenden – Muster, sind also für ein Verschlüsselungsverfahren nicht geeignet. Der einzige Weg, echte Zufallszahlen zu erzeugen, ist, sich physikalische Effekte zu nutze zu machen. Man könnte zum Beispiel das Rauschen eines Wasserfalls aufnehmen.

Und der entscheidende Punkt ist: Der Schlüssel des One-Time-Pads darf nur ein einziges Mal verwendet werden! Daher kommt schließlich auch das „One Time“ im Namen des Algorithmus. Das Verfahren hat einen Einmalschlüssel.

Hat man endlich einen Schlüssel, der den Anforderungen entspricht, muss man diesen zu guter letzt noch vor der eigentlichen Kommunikation dem Gesprächspartner zukommen lassen. Das muss über einen sicheren Kanal geschehen, es muss absolut ausgeschlossen sein, dass ein Angreifer eine Kopie des Schlüssels anfertigen kann. Es führt also kein Weg daran vorbei, den Schlüssel vor Ort und persönlich zu übergeben.

Diese vier Anforderungen, die erfüllt sein müssen, um die Sicherheit zu gewährleisten, zeigen eines: Nachweisbar unknackbare Verschlüsselung ist zwar in der Theorie nicht kompliziert, aber in der Durchführung ausgesprochen unhandlich. Und das ist auch der Grund, warum die One-Time-Pad-Verschlüsselung im Internet so gut wie keine Rolle spielt: Sie ist in der Praxis kaum durchführbar. Es gibt allerdings Ausnahmen, nämlich im militärischen Hochsicherheitsbereich. So war zum Beispiel das „rote Telefon“ zwischen den USA und den UdSSR zu Zeiten des kalten Krieges mit einem One-Time-Pad gesichert.

Das grüne Telefon
Das rote Telefon (Abbildung ähnlich)

Trotz der bekannten Unsicherheiten des Vigenère-Verfahrens wurden übrigens Abwandlungen davon noch sehr lange eingesetzt, zum Beispiel Ende der 1990er-Jahre im populären Textverarbeitungsprogramm WordPerfect. Und wahrscheinlich gibt es auch heute noch die ein oder andere von Ahnungslosen geschriebene Software, die diese „Verschlüsselung“ nutzt. Natürlich gibt es heutzutage besseres, aber dazu kommen wir in einer der nächsten Folgen.

Die wichtigsten Punkte der heutigen Folge noch einmal zusammengefasst:

  • Es gibt sogenannte polyalphabetische Verschlüsselungen, zu denen das Vigenère-Verfahren gehört.
  • In der Praxis spielen known plaintext-Angriffe eine große Rolle.
  • Die Vigenère-Chiffre ist äußerst unsicher gegen known plaintext-Angriffe.
  • Das One-Time-Pad oder Einmalschlüssel-Verfahren ist das einzige beweisbar sichere Verfahren, aber in der Praxis nur schwer durchzuführen.

In den nächsten Folgen werden wir uns immer weiter in Richtung Gegenwart bewegen und dabei auch das interessante Thema der Verschlüsselung zu Zeiten des zweiten Weltkriegs betrachten.

 

Kryptographie, Teil 2: Griechisch-Römisch

Was bedeutet eigentlich Kryptographie? Das Wort kommt aus dem griechischen und bedeutet „geheim schreiben“. Geheimschriften im Schein der Lampe sind also angesagt. Schon die alten Griechen haben sich damit beschäftigt, wie man Nachrichten so verschlüsseln kann, dass ein Feind, dem diese Nachricht in die Hände fällt, nichts damit anfangen kann. Bei den alten Griechen soll auch dieser Artikel anfangen, denn tatsächlich sind einige Grundbegriffe und Prinzipien immer noch die selben, auch wenn sich selbstverständlich die Methoden bedeutend verändert haben.

Doch nun zu dem, was die alten Griechen seinerzeit getan haben, um geheim zu schreiben. Diese benutzten das älteste bekannte Verschlüsselungsinstrument: Die sogenannte „Skytale„. Eine Skytale ist letztlich nichts anderes als ein Stab, allerdings mit einem genau definierten Durchmesser. Auf diesen Stab wurde nun spiralförmig ein Pergamentstreifen aufgezogen. Auf den Streifen auf der Rolle wurde nun von links nach rechts der zu verschlüsselnde Text geschrieben, so dass auf jeder Streifenbahn jeweils ein Buchstabe des zu verschlüsselnden Textes stand. Die Abbildung illustriert eine solche Skytale, auf deren Pergament „Dieser Text …“ geschrieben wurde.

Skytale
Eine Skytale

Nimmt man nun den Streifen wieder von der Skytale ab, kann man den Text nicht mehr lesen, sondern sieht nur eine auf den ersten Blick unsinnige Buchstabenfolge, die von oben nach unten verläuft. Nur wenn der Streifen wieder auf eine Skytale mit genau dem selben Durchmesser aufgezogen wird, kann man die Nachricht wieder von links nach rechts ablesen. Schon kleinere Abweichungen führen dazu, dass zusammengehörige Buchstaben auf der Rolle nicht mehr nebeneinander stehen. Ein Versuch unter Verwendung neuzeitlicher Klopapierrollen als Skytale verdeutlicht das Prinzip: Rollen verschiedener Marken haben einen unterschiedlichen Durchmesser, mit Hakle kann man keinen Charmin-Code entschlüsseln und mit Zewa schon gar nicht. Der Durchmesser ist der Schlüssel!

Eine moderne Skytale
Eine Klopapierrolle neuzeitliche Skytale

Und damit haben wir auch schon gleich einen der Grundbegriffe genannt, nämlich eben diesen Schlüssel. Nur mit Kenntnis des Schlüssels können wir verschlüsseln und nur mit Kenntnis des Schlüssels können wir einen verschlüsselten Text, den Geheimtext also, entschlüsseln und wieder zurück in Klartext umwandeln.

Kryptosystem
Ein allgemeines Kryptosystem mit Klartext, Schlüssel und Geheimtext

Was genau hat man also jetzt mit der Verschlüsselung gewonnen? Die Skytale versetzte die alten Griechen in die Lage, Nachrichten über unsichere Kanäle auszutauschen. Fällt die übermittelte Nachricht dem Feind in die Hände, so kann dieser nichts damit anfangen, da er den Schlüssel nicht kennt. Anders als der Name vielleicht nahelegt braucht der Geheimtext, auch Kryptogramm genannt, nämlich gerade nicht geheim gehalten zu werden! Ebenso wenig geheim sollte das verwendete Verschlüsselungsverfahren sein. Man sollte als jemand, der Nachrichten verschlüsselt verschicken will, stets davon ausgehen, dass einem Angreifer das verwendete Verfahren bekannt ist oder dass es zumindest irgendwann bekannt wird. Fanden die Feinde der alten Griechen bei einem abgefangenen Reiter einen Pergamentstreifen, so konnten sie wohl wissen, dass es sich um einen mit einer Skytale verschlüsselten Geheimtext handelte. Ohne Kenntnis des Schlüssels nutzte ihnen das dennoch nichts. Dieser Grundsatz hat sich bis heute gehalten: Es gibt keine „security through obscurity“! Ein vernünftiges Kryptosystem darf seine Sicherheit nicht darauf aufbauen, dass das genaue Verfahren unbekannt ist.

Doch gehen wir erst mal wieder zurück in die Antike und schauen uns an, was wir da eigentlich gerade mit unserem Klartext gemacht haben und was es noch so gibt. So geheim haben wir doch eigentlich gar nicht geschrieben: Die Buchstaben im Geheimtext sind immer noch die selben, sie sind nur durch das Abrollen von der Skytale auf eine andere Position gerutscht. Man spricht also bei solchen Verfahren wie der Skytale von einer Transpositionschiffre: Die Buchstaben bleiben was sie sind, sie bleiben nur nicht, wo sie sind. Viel einfacher als mit einer Skytale kann man übrigens eine Transpositionschiffre auch aufbauen, indem man einen Klartext auf einem Blatt Papier einfach mal von oben nach unten aufschreibt und dann von links nach rechts überträgt. Genau das haben wir hier gemacht. Der Schlüssel ist dabei die Anzahl der Zeilen. Alles klar?

Adsrepdesaek
lisq,eir d n
seeu re FeSa
 Se kt iastd
stürleRhh re
irbtanärrwil
eaetp dericn

Aber nicht nur die Griechen, auch die Römer haben natürlich fleißig verschlüsselt. Und einem der bekanntesten Römer wird eins der bekanntesten und simpelsten Verschlüsselungsverfahren zugeschrieben.

Gaius Iulius Caesar
Büste von Gaius Iulius Caesar, Altes Museum Berlin

Beim Caesar-Code handelt es sich um eine Substitutionschiffre: Jeder Buchstabe wird durch einen anderen ersetzt! Beim original Caesar-Code wird einfach das Alphabet um drei Buchstaben verschoben: Aus A wird C, aus B wird D, aus C wird E und so weiter. Der schöne Satz von oben mit den Stricknadeln würde dann mit dieser Ersetzungstabelle verschlüsselt werden:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B

Das Ergebnis lautet dann:

Cnu ukg fkg Uvtcuug wgdgtswgtvgp, mncrrgtgp
fkg Tcgfgt kjtgu Hcjttcfgt ykg Uvtkempcfgnp.

Natürlich ist man nicht gezwungen, diese Ersetzung genau so vorzunehmen, ist es ist auch möglich, die Buchstaben irgendwie anders zu tauschen oder gleich ganz andere Zeichen zu verwenden. Dann haben wir eine ganz klassische Geheimschrift. Der Schlüssel dieses Kryptosystems ist die jeweilige Ersetzungsvorschrift.

Geheimschrift
Eine Geheimschrift

Wirklich sicher ist das ganze aber nicht. Wenn man weiß, dass der meist verwendete Buchstabe das „E“ ist, kommt man schon recht schnell darauf, welchem Zeichen das wohl entsprechen muss. Überhaupt folgt jede Sprache einer ganz charakteristischen Buchstabenverteilung. Auch Buchstabenpaare wie „en“ am Wortende oder dergleichen kommen häufig vor und können zur Entschlüsselung ausgenutzt werden.

Bevor wir uns in der nächsten Folge etwas moderneren Verfahren zuwenden, seien hier noch einmal die wichtigsten Grundsätze zusammengefasst, die sich seit der Antike nicht geändert haben:

  • Ein Kryptosystem besteht aus dem Klartext, dem Geheimtext, dem Schlüssel und dem Verschlüsselungsverfahren.
  • Nur der Klartext und der Schlüssel sind geheim, das verwendete Verfahren nicht (keine „security through obscurity“).

Wer sich bis zur nächsten Folge weiterbilden will, dem sei das Buch „Kryptologie: eine Einführung in die Wissenschaft vom Verschlüsseln, Verbergen und Verheimlichen; ohne alle Geheimniskrämerei, aber nicht ohne hinterlistigen Schalk, dargestellt zum Nutzen und Ergötzen des allgemeinen Publikums“ von Albrecht Beutelspacher ans Herz gelegt.

Kryptographie, Teil 1

Verschlüsselte Kommunikation spielt heute eine große Rolle. Im Internet benutzen wir sie allerorten, oft ohne dass wir uns überhaupt Gedanken darüber machen und manchmal auch ohne dass wir uns dessen überhaupt bewusst sind. Im Homebanking-Bereich wird noch am ehesten für Jedermann sichtbar, wie wichtig verschlüsselte Kommunikation ist, denn niemand möchte seine Bankzugangsdaten der Gefahr des Missbrauchs aussetzen. Aber auch sonst sollten wir uns überlegen, ob es eine gute Idee ist, Passwörter über eine unsichere Verbindung zu übermitteln. Nicht zuletzt im aktuellen Kontext der Ausspähaffären ist gelegentlich von Verschlüsselung als einem Werkzeug des Schutzes gegen Abhören und Mitlesen die Rede. Dennoch beschäftigen sich nur sehr wenige Internetnutzer mit der Verschlüsselung von privater Kommunikation und noch sehr viel weniger haben ein Verständnis davon, was dabei eigentlich vor sich geht. Mit der kommenden Serie von Artikeln soll versucht werden, das zu ändern! Dabei sollen folgende Fragen beantwortet werden:

  • Was ist überhaupt Kryptographie?
  • Wie kann man die verschiedenen Verfahren grob einteilen und
    welche Bedeutung hat dies für die heutige Praxis?
  • Wie kann man sichere von unsicheren Verfahren
    auseinanderhalten und wo bestehen Angriffsmöglichkeiten?
  • Welche Verfahren und welche Software kann man konkret zum Schutz
    der Privatsphäre einsetzen?

Geraffel2w

Damit dabei der Spaß nicht zu kurz kommt, wird es auch ein kleines Rätsel und ein wenig historisches Hintergrundwissen geben. Mit letzterem soll es heute los gehen, ganz nebenbei werden dabei auch noch ein paar Grundbegriffe erklärt. Diese Artikelreihe basiert zum Teil auf einer Vorlesung, die ich im Rahmen der Erstsemesterveranstaltung „Einführung in die Wirtschaftsinformatik“ zuletzt im Wintersemester 2012/2013 gehalten habe sowie auf einer Seminararbeit, die ich 1998 verfasst habe, als mein Platz im Hörsaal noch auf der anderen Seite war.