Abhoeren nuetzt nichts Wie man einen unangreifbaren geheimen Schluessel generiert

10.03.1995

Ein wirklich geheimer Chiffrierschluessel ist einer, den nur der Sender und Empfaenger der chiffrierten Nachricht kennen; allfaellige weitere "Interessenten" haben keine Information ueber den Schluessel und koennen ihn auch nicht ausrechnen oder durch Probieren herausfinden - selbst wenn ihnen dazu unendliche Computerressourcen zur Verfuegung staenden.

Bis vor kurzem waren sogar Fachleute ueberzeugt, dass ein Schluessel nur dann geheim bleibt, wenn ihn Sender und Empfaenger entweder bei einem persoenlichen Treffen oder ueber einen absolut zuverlaessigen Kurier austauschen. Das ist oft sehr muehsam oder gar unmoeglich.

Seit kurzem weiss man nun, dass ein solcher Schluesselaustausch gar nicht unbedingt noetig ist: Sender und Empfaenger - nennen wir sie A und B - koennen sich naemlich ihren Chiffrierschluessel zu Hause im stillen Kaemmerlein konstruieren, indem sie eine oeffentlich zugaengliche Datenquelle anzapfen. Damit A und B beim gleichen Schluessel landen, muessen sie natuerlich miteinander kommunizieren.

Einzige Bedingung: gestoerter Empfang

Das Verblueffende ist nun, dass ein Aussenstehender - nennen wir ihn Feind F - diesen Schluessel auf gar keinen Fall herausfinden kann, selbst wenn er die gleiche Datenquelle anzapft und auch noch die ganze Kommunikation zwischen A und B abhoert! Einzige Bedingung fuer die scheinbare Zauberei: F darf die Datenquelle nicht fehlerfrei empfangen.

Der Einwand, bei diesem Handicap von F sei es wohl klar, dass er gegen A und B keine Chancen habe, ist zwar richtig, aber irrelevant: Das System funktioniert naemlich auch dann, wenn A und B die Datenquelle nicht einwandfrei empfangen. Ihre Fehlerrate darf dabei sogar bedeutend groesser (zum Beispiel 1000mal groesser) sein als jene von Feind F.

Wie realisiert man dieses System nun in der Praxis? Als Datenquelle nimmt man am besten einen Satelliten, der eine Folge von Zufallszahlen ausstrahlt, und stellt die Sendestaerke so ein, dass der Empfang auf der Erde auch mit einer riesigen Antenne fehlerbehaftet ist.

Codierung mit Zufallszahlen

A und B empfangen also zur gleichen Zeit zwei wohl unterschiedliche Folgen von Zufallszahlen, aus denen sie sich dann durch Kommunikation einen gemeinsamen Chiffrierschluessel konstruieren. Wie, zeigt das folgende Beispiel.

Nehmen wir an, der Satellit sende die folgenden Zahlen:

10 01 11 00 10 11 11 01 10 01 01 01 11 10 10 11 00 00 00 10 11 01 11 00

(In der Praxis wuerde die Zahlenfolge nicht abreissen; A und B wuerden ihre Laenge aber so waehlen, dass sie daraus einen Schluessel extrahieren koennten, der gleich lang ist wie die geheime Nachricht, die A verschicken will.)

Nehmen wir weiter an, A empfange vom Satelliten die Zahlenfolge

10 00 11 00 11 11 01 01 10 00 01 01 11 10 10 01 00 10 00 10 11 01 01 00

Die fettgedruckten Zahlen deuten Empfangsfehler an. Die von A empfangene Reihe weicht also an sieben Stellen von dem ab, was der Satellit ausgesandt hat. A teilt die empfangene Folge in Zweierpakete und errechnet von jedem Paket den Exclusive- Operations-Research-(XOR-)Wert. Die XOR-Operation macht aus zwei gleichen Zahlen eine 0 und aus zwei unterschiedlichen eine 1. Das ergibt eine neue Folge, die pro urspruenglich empfangenem Zweierblock nur noch eine Ziffer enthaelt:

1 0 0 0 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 0

Dieses Resultat schickt A ueber einen oeffentlichen, das heisst abhoerbaren Kanal an B. Das ist kein Sicherheitsrisiko, denn die zweite Folge von A verraet weder die Zahlen, die er wirklich empfangen hat, noch die urspruenglichen, vom Satelliten gesendeten Zeichen - die kennt A wegen des schlechten Empfangs ja nicht einmal selber.

Nehmen wir weiter an, B habe gleichzeitig mit A vom Satelliten folgende Zahlenfolge empfangen:

10 01 10 00 10 11 01 00 01 01 00 01 11 10 00 11 10 00 00 10 11 01 10 00

B teilt die empfangene Zahlenfolge ebenfalls in Zweierpakete und errechnet von jedem Paket den XOR-Wert. Das ergibt bei ihm:

1 1 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 1 0 1 1 0

B vergleicht nun seine zweite Folge mit jener, die er von A erhalten hat, und meldet diesem - hier durch Kreuze angezeigt - umgehend, wo Uebereinstimmung herrscht:

x x x x x x x x x x x x x x

Reduktion auf identische Zweierbloecke

A und B betrachten jetzt nur noch jene Zweierbloecke ihrer urspruenglich empfangenen Folgen, deren XOR-Werte uebereinstimmen.

Von jedem dieser Zweierbloecke nehmen sie nun das erste Bit, das sie vom Satelliten empfangen haben.

Aus der Folge, die A direkt vom Satelliten bekommen hat (siehe oben), nimmt er also lediglich folgende Zweierbloecke:

10 00 11 01 10 01 11 10 00 10 11 01 01 00

und von diesen das erste Bit, was als dritte Folge ergibt:

1 0 1 0 1 0 1 1 0 1 1 0 0 0

B tut dasselbe: Er nimmt von der vom Satelliten erhaltenen Folge (siehe oben) die Zweierbloecke

10 00 11 01 01 01 11 10 00 10 11 01 10 00

und von diesen das erste Bit, was bei ihm folgende dritte Reihe ergibt:

1 0 1 0 0 0 1 1 0 1 1 0 1 0

Man sieht: Die beiderseitigen dritten Folgen stimmen bereits recht weitgehend ueberein; Diskrepanzen zeigen sich nur noch an zwei Stellen, die hier zur Verdeutlichung fettgedruckt sind.

Die Kommunikationspartner wiederholen das Verfahren. A teilt seine dritte Folge (siehe oben) wieder in Zweierpakete und errechnet von jedem Paket den XOR-Wert. Die vierte Folge sieht bei A so aus:

1 1 1 0 1 1 0

A schickt sie ueber den oeffentlichen Kanal an B. B teilt seine dritte Folge (siehe oben) ebenfalls in Zweierpakete, ermittelt von jedem Paket den XOR-Wert und erhaelt als vierte Folge

1 1 0 0 1 1 1

B vergleicht dann seine vierte Folge mit jener von A und teilt diesem mit, an welchen Stellen Uebereinstimmung herrscht:

x x x x x

Der Schluessel ist tatsaechlich geheim

Als fuenfte Folge (man nehme das erste Bit jener Zweierbloecke, wo Uebereinstimmung herrscht) bekommt A

1 1 1 0 1

B erhaelt das gleiche Resultat 2. Damit sind die beiden fast am Ziel: Sie haben jetzt eine uebereinstimmende Folge, ueber die

alle Abhoerer hoechstens unvollstaendige Informationen besitzen.

Warum kann nun ein Feind F die gemeinsame Folge von A und B nicht ebenfalls eruieren? Nehmen wir an, F hoere das Satellitensignal ebenfalls, und zwar besser als A und B (weniger Fehler). Er empfaengt dann zum Beispiel die Folge

10 01 11 01 10 11 11 01 10 01 01 01 11 00 10 11 00 00 00 11 01 01 11 00

Wenn F nach dem gleichen Rezept vorgeht wie A und B, lautet seine zweite Folge (XOR-Werte bilden)

1 1 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0

F kann die zweite Folge von A (siehe oben) auf dem oeffentlichen Kanal abhoeren und dabei folgende Uebereinstimmungen mit seiner eigenen zweiten Folge feststellen:

x x x x x x x x x x x x x

Der Nutzen dieser Rechnung fuer F ist allerdings klein, denn A und B haben ganz andere Uebereinstimmungen:

x x x x x x x x x x x x x x

F erhaelt keine richtige Reihe

Diese Information hat F ebenfalls, denn er kann ja mithoeren, wenn B die Uebereinstimmungen an A durchgibt. Nur nuetzt auch sie ihm herzlich wenig: Verfaehrt F nach dem gleichen Rezept wie A und B (erstes Bit der angekreuzten Bloecke), so destilliert er aus seinem Empfangssignal (siehe oben) als dritte Folge

1 0 1 1 1 0 1 0 0 1 0 0 1 0

In diesem Beispiel hat F mehrere Diskrepanzen gegenueber den Zahlenreihen sowohl von A als auch von B.

Damit ist er auch bei einer hartnaeckigen Fortsetzung seiner Abhoeraktion auf dem Holzweg: Wenn F naemlich von seiner dritten Folge (siehe oben) jene Bloekke auswaehlt, die B an A als uebereinstimmend meldet:

x x x x x

und an diesen Stellen jeweils sein erstes Bit nimmt, so erhaelt F am Ende

1 1 1 0 0

und damit eine andere Folge als A und B (sie haben als letzte Zahl eine 1).

Wer findet, die Uebereinstimmung der Schlussfolgen (11100 bei F und 11101 bei A und B) sei fuer eine unangreifbare Chiffrierung noch zu gross, hat natuerlich recht. Er darf aber beruhigt sein: A und B koennen diese Uebereinstimmung gaenzlich aus dem Weg raeumen, indem sie ein Verfahren anwenden, das in der Fachsprache "Privacy Amplification Against Probabilistic Information" heisst. Diese Geheimhaltungsverstaerkung fuehrt dazu, dass die Fehlerrate bei F statistisch zunimmt und schliesslich 50 Prozent betraegt. Der Feind F hat dann ueberhaupt keine Information mehr ueber die Folge, die A und B konstruiert haben - er koennte geradesogut versuchen, diese mit Muenzwuerfen zu eruieren, die ebenfalls eine Fehlerrate von 50 Prozent produzieren.

Zweiter Durchgang beim XOR-Verfahren

In unserem einfachen Beispiel 3 koennten A und B dies wie folgt erreichen: Sie verarbeiten ihre gemeinsam konstruierte Folge 11101 weiter, indem sie zufaellig gewaehlte Untermengen davon nach dem XOR-Verfahren zu einer neuen Zahlenfolge verrechnen. So koennten sie als erste Untermenge die erste, zweite und fuenfte Zahl nehmen (also die Zahlen 111), als zweite Untermenge die zweite und dritte Zahl (11) und als dritte Untermenge die zweite, dritte, vierte und fuenfte Zahl (1101). A und B wuerden als Resultat dieser Privacy Amplification folgende Zahlen erhalten: 1 (= XOR von 111), 0 (=XOR von 11) und 1 (= XOR von 1101).

Wenn Feind F durch Abhoeren der Konversation von A und B auch diese Regel kennen und sie auf sein Resultat 11100 anwenden wuerde, wuerde er die Ziffernfolge 0 (= XOR von 110), 0 (= XOR von 11), 0 (= XOR von 1100) erhalten. Diese hat nun auch statistisch gesehen mit jener von A und B ueberhaupt nichts mehr zu tun, und zwar aus folgendem Grund: Wenn sich die Zahlenfolgen von A und B beziehungsweise F vor der Privacy Amplification auch nur an einer Stelle unterscheiden (in unserem Beispiel: bei der fuenften Zahl), so betraegt die Wahrscheinlichkeit, dass diese Zahl in einer der zufaellig gewaehlten Untermengen vorkommt (und damit bei A und B beziehungsweise F einen unterschiedlichen XOR-Wert liefert), 50 Prozent, denn entweder gehoert diese Zahl zur Untermenge oder eben nicht. Mit andern Worten: Statistisch gesehen, liefert die Privacy Amplification bei A und B beziehungsweise F bei jeder Verrechnung und damit bei jeder Zahl der neuen Folge mit 50 Prozent Wahrscheinlichkeit einen unterschiedlichen Wert.

F hat also keine Moeglichkeit, sich durch Entschluesselungsverfahren nach Prinzipien von Statistik und Wahrscheinlichkeitsrechnung systematisch an den geheimen Code heranzuarbeiten. Die Mathematik hilft ihm auch hier nicht weiter als der beliebig oft wiederholte Muenzenwurf.