A5 (Algorithmus)

Übersicht

A5 ist der in GSM-Mobilfunknetzen eingesetzte Algorithmus zur Verschlüsselung der Funkstrecke zwischen Handy und Sendemast. Es gibt den A5 klassischerweise in zwei ähnlichen Varianten - A5/1 und A5/2. Beide basieren auf der Verschaltung von linear rückegoppelten Schieberegistern (LFSR). A5/2 unterscheidet sich von A5/1 nur dahingehend, daß die enthaltenen Taktkontrollbits in ein viertes LFSR ausgelagert sind. Auf diese Weise wird der Algorithmus geschwächt. Diese Version des A5 kommt in Ländern mit Verschlüsselungsbeschränkungen zum Einsatz. A5 wurde unter strengster Geheimhaltung in den achtziger Jahren entwickelt. Die Spezifikation des Algorithmus wurde der Öffentlichkeit nie zur Verfügung gestellt. Allerdings wurde ungefähr zeitgleich mit der Entwicklung des Algorithmus auch die Diskussion über den internen Aufbau des A5 begonnen. So haben sich einige findige Mathematiker daran gemacht, den Algorithmus zu rekonstruieren. Im Sommer 1994 veröffentlichte R. Anderson die erste Annäherung an den geheimen A5 im Usenet. Fünf Jahre später wurde durch die Herren M. Bricenco, I. Goldberg und D.Wagner eine genaue Beschreibung des A5/1 veröffentlicht, die inzwischen auch allgemein als korrekt angesehen wird.

Im Herbst 2002 wurde die Spezifikation für einen neuen Standard mit dem Namen A5/3 angekündigt. Dieser unterscheided sich grundlegend vom ursprünglichen A5. So handelt es sich nun um eine Blockverschlüsselung. Der A5/3 wurde im Gegensatz zu seinen Vorgängern nicht unter strengster Geheimhaltung entwickelt, sondern von der Security Algorithms Group of Experts (SAGE), einer Abteilung des European Telecommunications Standards Institutes (ETSI), entworfen und veröffentlicht.

A5/1

Der Algorithmus A5/1 besteht aus drei Schieberegistern mit den Längen 19, 22 und 23 Bit, deren Ausgänge miteinander XOR-verknüpft werden, und liefert 328 pseudozufällige Bits pro Rahmen. Dazu kommt eine Taktsteuerung, die dynamisch eine Auswahl der zu taktenden Register trifft. Der Ausgang der drei LFSR wird Bitweise auf den Datenstrom des jeweiligen Rahmens addiert. Bevor die eigentliche Verschlüsselung stattfindet sind die drei Register zu initialisieren. Dabei findet die Taktkontrolle noch keine Verwendung! Die Initialisierung der LFSR sieht konkret wie folgt aus:

• Alle drei Register werden mit dem Nullvektor geladen.
• Anschließend wird der Sitzungsschlüssel Kc in jedes Register geladen. Jedes Register wird 64 mal getaktet, mit jedem Takt t wird das Bit t des Sitzungsschlüssel eingespeist. Hierbei findet also schon eine Vermischung statt - nach 8, 14 und 21 Takten »fängt der jeweilige LFSR an zu arbeiten«. Die Ausgabebits verfallen dabei ungenutzt.
• Als nächstes wird auf die selbe Weise die aktuelle Framenummer in jedes Register geladen.

Nun befindet sich der A5/1 im initialisierten Zustand S(0) und kann mit der Verschlüsselung beginnen. Mathematisch gesehen ist folgendes passiert:

Es wurden nacheinander die Werte Kc mit einer Länge von 64 Bit5 und Nf mit einer Länge von 22 Bit in jedes einzelne Register geschrieben. Das Ergebnis war der innere Zustand S(0). Es handelt sich also um eine lineare Abbildung

wobei

und

Der Anschließend erzeugte Schlüsselstrom hat eine Länge von 328 Bit. Naiv betrachtet könnte man zu dem Schluß kommen, daß 2328 unterschiedliche Schlüsselströme möglich sind. Das trifft aber wegen der Initialisierung mit 264 Möglichkeiten nicht zu. Für die nun folgende Verschlüsselung der Rahmendaten wird die Taktkontrolle zugeschaltet. Ohne die Taktsteuerung wäre der A5 linear. Es würden lediglich die Ausgänge der drei Schieberegister miteinander verknüpft und man könnte durch Lösen eines linearen Gleichungssystems den Anfangszustand S(0) rekonstruieren. Mit Hilfe der Taktung werden die Schieberegister zu unterschiedlichen Zeitpunkten angesprochen. Man kann sich vorstellen, daß der Ausgangsstrom dadurch unlinearer wird. Zur Taktung der einzelnen Register dienen drei Taktkontrollbits τ, von denen je eines in jedem Register enthaltenist. Man geht davon aus, daß τ 1 = 11, τ 2 = 12 und τ 3 = 13 gilt. Die Ansteuerfunktion der LFSR läßt sich leicht wie folgt beschreiben:

• Wenn höchsten ein Taktkontrollbit den logischen Wert 1 hat, dann takte alle Register, deren Taktkontrollbits auf 0 stehen.
• Wenn mehr als ein Taktkontrollbit auf 1 steht, dann takte alle Register, deren

Taktkontrollbits auf 1 stehen.

Es werden also immer zwei respektive drei Register getaktet. Die Chance eines Register,getaktet zu werden, liegt bei 75%

Eine interessante Beobachtung ist, daß die Schlüssellänge nichts mit der Gesamtlänge der drei Register zu tun hat. Anderson stellte in seiner Publikation die Vermutung an,daß Kc auf die drei LFSR verteilt würde. Das hätte einen Angriff stark erleichtert.

Allerdings muß man dazu sagen, daß er parallel zu dieser Annahme davon ausging, daßdie Taktsteuerung bereits zur Einspeisung der Rahmennummer aktiviert würde. Dieses hätte wiederum zur Folge, daß sich aus dem bekannten Initialisierungswert der Register nicht unmittelbar der Sitzungsschlüssel Kc ableiten ließe. Aber auch diese Annahme trifft nicht zu.

Für die Verschlüsselung werden nicht alle 328 Bit benötigt; lediglich 114 Bit sollen in jeder Richtung übertragen werden. Es ergibt sich folgende Struktur:

• Die ersten 100 Bit verfallen ungenutzt.
• Nun folgen 114 Bit, die Bitweise auf den gesendeten Datenstrom6 addiert werden.
• Abschließend werden die 114 empfangenen Bits mit den restlichen Bits des A5

XOR-verknüpft.

Damit ist ein Rahmen abgewickelt worden und der A5 wird neu initialisiert. Eine Wiederholung des Bitstroms tritt erst nach etwa 209 Minuten ein.

A5/2

Der A5/2 unterscheidet sich vom A5/1 nur dahingehend, daß die Taktkontrollbits in ein viertes Register ausgelagert wurde. Das hat aber eine enorme Abschwächung des Algorithmus zur Folge. Das Problem des im vorhergehenden Abschnitt aufgeführten Angriff nach Anderson und Roe waren genau die Taktkontrollbits. Ohne diese ließe sich aus zwei beliebig gewählten Registern leicht der Inhalt des dritten ermitteln. Beim A5/2 ist das also prinzipiell möglich. es gibt allerdings noch eine bessere Möglichkeit.

Beim Angriff von S. Petrović, A. Fúster-Sabater werden nicht die drei Register analysiert,die den Schlüsselstrom liefern. Stattdessen wird das vierte Register analysiert.

Hierzu werden innere Zustände geraten und daraus abgeleitet, wie die ersten drei Register getaktet würden. Auf diesem Weg läßt sich wiederum der Inhalt der drei Register ermitteln.

Angriffe auf A5/1 und A5/2

Das Grundprinzip für einen Angriff auf die Stromchiffre A5 sieht üblicherweise so aus, daß man versucht den Weg vom Initialisierungstupel (Kc, Nf) zu den 328 ausgegebenen Bis rückwärts abzugehen. Man spricht dann auch von einem Inversionsangriff. Die Schwierigkeit eines solchen Angriffs besteht darin, S(0) zu bestimmen. Das Tupel (Kc, Nf) läßt sich aus S(0) relativ leicht berechnen. Die andere Alternative, also das Ausprobieren von verschiedenen Schlüsseln, wird als Vorwärtsangriff bezeichnet. Die Voraussetzung für einen Angriff ist üblicherweise das Vorhandensein von einigen Klartextstücken mit den zugehörigen Chiffraten. Wenn der Klartext überhaupt nicht bekannt ist, dann wird die Schlüsselsuche verkompliziert - das System muß eine sinnvolle von einer Schlechten Lösung unterscheiden können. Da im GSM eine Komprimierung der Sprachdaten vorgesehen ist, kann man eine sinnvolle Lösung aber relativ leicht anhand der spezifischen Eigenschaften des Kompressionsverfahrens erkennen. Die hier bekannten Angriffe führen den Angreifer nicht zum Zustand S(0). Lediglich der Zustand vor Beginn der Verschlüssellung wird erreicht. Es fehlen also noch die 100 verworfenen Bits. Diese lassen sich durch statistische Auswertungen und auch durch bestimmte Vorberechnungen relativ leicht ermitteln. Aus S(0) den geheimen Sitzungsschlüssel Kc zu ermitteln ist dann auch kein großes Problem mehr.

Hier nur eine kurze Auflistung der "populären" Vorschläge möglicher Angriffe:

• Vollständige Suche, von M. Briceno, I.Goldberg und D. Wagner
• Rekursiver Angriff, von R. Anderson und M. Roe
• Time-Memory-Tradeoff, J. Golić
• "Verbesserung des TMT", von A. Biryukov, A. Shamir und D. Wagner
• Divide and Conquer-Verfahren, von J. Golić
• Kollisionen in den Schieberegistern, von G. Gong

Für genauere Informationen zu den Angriffen sei auf die jeweilige Veröffentlichung verwiesen (vergleiche Quellenangaben).

A5/3

Der A5/3 unterscheidet sich völlig von den beiden anderen Versionen. Zum einen handelt es sich hierbei nicht mehr um eine Strom- sondern um eine Blockchiffre. Außerdem wurde der A5/3 im Gegensatz zu seinen Vorgängern nicht geheim entwickelt. Statt dessen kann sich jeder Interessent die Spezifikationen im Internet herunterladen (vergleiche [10]). A5/3 und der in UMTS-Netzen verwendete KASUMI Algorithmus sind identisch. Beide stammen vom Misty-Algorithmus ab, welcher von Mitsubishi erfunden wurde. Der A5/3 wurde durch die ETSI unter dem Markenzeichen 3GPP8 veröffentlicht. Diese Bezeichnung soll die Zusammenarbeit zwischen Industrie und Forschung bei der Entwicklung neuer Algorithmen für die Mobilfunknetze der dritten Generation hervorheben. A5/3 verschlüsselt immer einen 64 Bit Block mit Hilfe eines 128 Bit langen Schlüssels. Der Algorithmus wurde als Feistelchiffre mit 8 Runden entworfen. Im A5/3 kommen zwei S-Boxen zum Einsatz. Insgesamt finden pro Runde 2 Funktionsaufrufe und 12 Substitutionen statt. Hierbei ist zu bemerken, daß die beiden aufgerufenen Funktionen wiederum Unterfunktionen aufrufen.

Für eine genauere Betrachtung des Algorithmus sei auf die Spezifikation verwiesen.

Quellenangaben

• Alex Biryukov, Adi Shamir, David Wagner: Real Time Cryptanalysis of A5/1 on a PC, The Weizmann Institute, Israel, University of California, USA
• Erik Zenner: Kryptographische Protokolle im GSM-Standard: Beschreibung und Kryptanalyse, Diplomarbeit, Professur für theoretische Informatik, Universität Mannheim, 1999
• Marc Briceno, Ian Goldberg, David Wagner: A pedagogical implementation of A5/1, http://www.scard.org/gsm/a51.html
• Jovan Dj. Golić: Cryptanalysis of Alleged A5 Stream Cypher, proceedings of EUROCRYPT'97, LNCS 1233, S. 239-255, Springer 1997, http://downloads.securityfocus.com/library/a5-hack.html
• 3rd Generation Partnership Project: Technische Spezifikation zum Kasumi-Algorithmus, http://www.3gpp.org/TB/other/algorithms/35202-311.pdf