[Datenschleuder] [63]    GSM: Security by obscurity

GSM: Security by obscurity Wie die Datenschleuder berichtete, hatte sich das GSM MoU (Memorandum of Understanding, ein Industriekonsortium, das den GSM-Standard entwickelt und vorantreibt) entschlossen, die für die Authentifizierung und Verschlüsselung im GSM verwendeten Algorithmen geheimzuhalten. Der für die Verschlüsselung verwendete Algorithmus A5 ist (in zwei Varianten, A5/1 mit ein bisschen Sicherheit, A5/2 mit noch weniger Sicherheit) bei allen Netzwerken und Telefonen im GSM identisch, eine fast korrekte Implementation kursiert seit Jahren im Internet. Für die Authentifizierung und die Festlegung des Session-Keys für die Luftschnittstellen-Verschlüsselung werden die Algorithmen A3 und A8 verwendet. Das GSM MoU hat sich dabei nicht auf einen Algorithmus festgelegt, es steht jedem Hersteller frei, eine eigene Implementation zu verwenden. Interoperabilität ist nicht notwendig, da sich auch beim Roaming alle verschlüsselungsrelevanten Vorgänge entweder auf der Chipkarte oder im HLR des Netzbetreibers abspielen, der die Karte ausgegeben hat. Jetzt begab es sich aber, dass das MoU eine Referenzimplementation von A3/A8 namens COMP128 für seine Mitglieder bereitstellte. Das führte dazu, dass eine Vielzahl von Netzwerk-Operatoren diesen Algorithmus ungeprüft einsetzte, da sie davon ausgingen, das MoU wisse schon, was es da tut. Wusste es aber nicht. Da COMP128 nie veröffentlich wurde, gab es keine unabhängige Sicherheitsüberprüfung durch außenstehende Kryptografen, wie sie bei allen heute gängigen Algorithmen wie RSA, IDEA oder Blowfish durchgeführt wurde. Ein Algorithmus gilt dann als relativ sicher, wenn er mehrere Jahre veröffentlich ist und niemand eine praktische oder realistisch erscheinende theoretische Attacke veröffentlicht hat. Und es begab sich, daß der Smart Card Developer Association (http://www.scard.org) ein Satz von Schulungsunterlagen in die Hände fiel, in dem COMP128 größtenteils erklärt wurde. In diesen Schulungsunterlagen gab es einige offenkundige Weglassungen und Fehlinformationen, die durch "manuelle" Forschung identifiziert und berichtigt werden konnten. Durch längeres Studieren einer GSM-Testkarte, bei der der geheime Schlüssel Ki frei gewählt werden konnte, wurden die restlichen Details rekonstruiert. Marc Briceno von der SDA hat die Sourcen des COMP128 dann an Ian Goldberg und Dave Wagner geschickt. Die beiden bilden das Kernteam einer Sicherheitsforschungsgruppe an der Uni in Berkeley. Und sie haben dann auch nach nur sehr kurzer Zeit eine Sicherheitslücke in COMP128 entdeckt. Das Problem ist, daß es beim COMP128 verschiedene Inputs gibt, die denselben Output erzeugen, sogenannte Kollisionen. Diese Kollisionen treten bereits nach der zweiten Runde der Berechnung auf. Zu diesem Zeitpunkt sind die Bits des Inputs noch nicht besonders gut über den gesamten Buffer verteilt, was zur Folge hat, dass diese Kollisionen nur von 32 der insgesamt 256 Input-Bits abhängig sind. Der Input von COMP128 sind 16 Byte Challenge-Daten vom Netz (RAND), und 16 Byte geheimer Schlüssel (Ki) in der Karte. Die 32 Bit, die für die Kollision entscheidend sind, sind jeweils das i-te und i+8-te Byte von RAND und Ki. Der erste Schritt, um den Ki aus der Karte zu extrahieren, ist jetzt, Kollisionen zu finden. Ki kann man naturgemäß nicht variieren, RAND jedoch schon. Man nimmt jetzt also die Karte, wählt sich einen RAND, schickt RAND an die Karte, und schaut dann in einer Tabelle nach, ob man die Antwort schon gesehen hat. Da die Kollision ja nur von 2 Bytes in RAND abhängig ist, ist es egal, wie der Rest der Bytes von RAND aussieht, wir setzen also alles auf 0, ausser den Bytes, in denen uns die Kollision interessiert. Wenn wir mit i=0 anfangen, zählen wir jetzt alle Kombinationen von Byte 0 und Byte 8 von RAND durch, bis wir ein Paar von RAND-Werten mit einer Kollision finden. Da die Kollision ja nur von Bytes 0 und 8 von Ki abhängig ist, können wir jetzt in einer Simulation der Karte (einer Software, die den COMP128 enthält), beginnend mit einem Ki von 0, alle Werte von Byte 0 und 8 durchprobieren, bis wir mit diesem Ki eine Kollision für dasselbe Paar von RANDs wie bei der Karte sehen. Und schon haben wir 16 Bit von Ki. Durch Wiederholen dieses Prozesses für i von 1 bis 7 können wir den gesamten Key rekonstruieren. Notwendig für diesen Prozeß ist natürlich ein Kartenleser, eine Software, die eine Anfrage an die SIM-Karte schickt, und eine COMP128-Implementation, um die Keys durchzuprobieren. Einen Linux-Source für das entsprechende Programm, der mit dem UniProg oder dem Dumbmouse-Interface läuft, gibt's auf ftp://www.ccc.de. Der Zeitaufwand zur Extraktion des Ki hängt massiv von der Geschwindigkeit ab, mit der die Karte die Challenges abarbeitet. Erfahrungsgemäß zieht sich das ganze etwa acht Stunden hin, gelgentlich auch länger. Durch einige Optimierung im Ablauf und elektronische Massnahmen dürfte eine deutliche Reduzierung dieser Zeit möglich sein. andreas@ccc.de / frank@ccc.de

[Datenschleuder] [63]    GSM: Security by obscurity