Benutzer:Nobbipunktcom/A5 (Algorithmus)

A5 ist eine Familie von Verschlüsselungsverfahren, die in GSM-Mobilfunknetzen zur Verschlüsselung der Kommunikation zwischen Mobiltelefon und Basisstation eingesetzt werden.

Allgemeines

Zusammenhang zwischen A3, A5 und A8

A5 gg. A3 und A8 Ablauf im Endgerät gg. SIM-Karte Zeitschema A5/1 bis 4

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 veröffentlichten M. Bricenco, I. Goldberg und D. Wagner eine genaue Beschreibung des A5/1, die inzwischen auch allgemein als korrekt angesehen wird.

A5/2 wurde aufgrund seiner Schwächen ab 3GPP Release 6 aus dem Standard herausgenommen.

Im Herbst 2002 wurde die Spezifikation für einen neuen Standard mit dem Namen A5/3 angekündigt. Dieser unterscheidet 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 Europäischen Instituts für Telekommunikationsnormen (ETSI), entworfen und veröffentlicht.

Varianten

A5/0

Der Funkverkehr zwischen Mobiltelefon und Mobilfunkbasisstation kann unverschlüsselt erfolgen. Dieser Modus ist unter dem Namen A5/0 bekannt. Er wird in Frankreich, Libyen und einigen weiteren Ländern eingesetzt und deshalb auch französischer Modus genannt.

A5/1

Struktur des A5/1 Algorithmus

Der Algorithmus A5/1 basiert auf drei 19, 22 und 23 Bit langen Schieberegistern die untereinander XOR-verknüpft sind. , 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 (linear feedback shift register) 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 K_c 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 dieselbe Weise eine aus der aktuelle Framenummer berechnete Zahl COUNT N_f 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 K_c mit einer Länge von 64 Bit und N_f 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 $f:(K_{c},N_{f})\longrightarrow S(0)$, wobei $\sharp (K_{c},N_{f})=2^{64+22}=2^{86}$ und $\sharp S(0)=2^{19+22+23}=2^{64}$. Der anschließend erzeugte Schlüsselstrom hat eine Länge von 328 Bit. Naiv betrachtet könnte man zu dem Schluss kommen, dass 2³²⁸ unterschiedliche Schlüsselströme möglich sind. Das trifft aber wegen der Initialisierung mit 2⁶⁴ 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, dass der Ausgangsstrom dadurch unlinearer wird. Zur Taktung der einzelnen Register dienen drei Taktkontrollbits τ, von denen je eines in jedem Register enthalten ist. Man geht davon aus, dass τ ₁=11, τ₂=12 und τ₃=13 gilt. Die Ansteuerfunktion der LFSR lässt sich leicht wie folgt beschreiben:

• Wenn höchstens 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, dass die Schlüssellänge nichts mit der Gesamtlänge der drei Register zu tun hat. Anderson stellte in seiner Publikation die Vermutung an, dass K_c auf die drei LFSR verteilt würde. Das hätte einen Angriff stark erleichtert. Allerdings muss man dazu sagen, dass er parallel zu dieser Annahme davon ausging, dass die Taktsteuerung bereits zur Einspeisung der Rahmennummer aktiviert würde. Dieses hätte wiederum zur Folge, dass sich aus dem bekannten Initialisierungswert der Register nicht unmittelbar der Sitzungsschlüssel K_c 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 Datenstrom addiert werden.
• Abschließend werden die 114 empfangenen Bits mit den restlichen Bits des A5/1 XOR-verknüpft.

Damit ist ein Rahmen abgewickelt worden und der A5/1 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 darin, dass die Taktkontrollbits in ein viertes Register ausgelagert wurden. Das hat aber eine enorme Abschwächung des Algorithmus zur Folge. Das Problem des im vorhergehenden Abschnitt aufgeführten Angriffs 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 wurden. Auf diesem Weg lässt sich wiederum der Inhalt der drei Register ermitteln.

A5/2 wird beispielsweise in Australien eingesetzt.

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. A5/3 und der in UMTS-Netzen verwendete KASUMI-Algorithmus sind identisch. Beide stammen vom MISTY-Algorithmus ab, welcher von Mitsubishi erfunden wurde, und bedeuten übersetzt aus dem Japanischen bzw. Englischen das gleiche.

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, dass die beiden aufgerufenen Funktionen wiederum Unterfunktionen aufrufen. Für eine genauere Betrachtung des Algorithmus sei auf die Spezifikation verwiesen.

Angriffe auf A5/1 und A5/2

Das Grundprinzip für einen Angriff auf die Stromchiffre A5 sieht üblicherweise so aus, dass man versucht den Weg vom Initialisierungstupel (K_c, N_f) zu den 328 ausgegebenen Bits rückwärts abzugehen. Man spricht dann auch von einem Inversionsangriff. Die Schwierigkeit eines solchen Angriffs besteht darin, S(0) zu bestimmen. Das Tupel (K_c, N_f) lässt 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 muss 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üsselung 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 K_c 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
• Time-Memory-Tradeoff Angriff auf A5/1 von Barkan, Biham und Keller
• Brute-Force-Angriff mittels der Spezialwardware Copacobana
• Vorberechnung von Rainbow Tables in einem Projekt von Karsten Nohl

Quellenangaben

• 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
• Technische Spezifikation zum Kasumi-Algorithmus, http://www.etsi.org/website/document/algorithms/ts_135202v070000p.pdf
• Philipp Südmeyer: Die Stromchiffre A5, Seminararbeit, http://www.suedmeyer.net/inhalte/pdf/a5_thesis.pdf