COMP128

aus Wikipedia, der freien Enzyklopädie

COMP128 ist eine Implementierung der für das GSM-Netz spezifizierten Algorithmen A3 und A8. A3 wird zur Authentifierung der Mobilstation am Netz bzw. AuC (Authentication Center) benötigt, während A8 dazu dient, einen Session Key für die verschlüsselte Übertragung zwischen Mobilstation/Handy und der BTS zu generieren.

Technische Details der ursprünglich vertraulichen Implementierung gelangten 1998 durch Reverse Engineering an die Öffentlichkeit.

COMP128 arbeitet mit 9 Runden, wobei der zentrale Kern des Algorithmus eine Hash-Funktion ist. Diese Hash-Funktion liefert einen 128-Bit-Hashwert für 256 Bit Eingabe. Sie basiert auf einer Butterfly-Struktur. Die Ausgabe des Algorithmus enthält die für die Authentisierung verwendete Antwort und den Session Key für die A5-Stromchiffrierung, welche zur Verschlüsselung des Sprachtransfers eingesetzt wird.

Sei X[0..31] die 32 Byte große Eingabe der Hash-Funktion, mit K := X[0..15] dem Schlüssel der Ziel-SIM-Karte und X[16..31] die durch die Station gesendete Challenge. Seien weiterhin die Tabellen T0[0..511], T1[0..255], T2[0..127], T3[0..63] und T4[0..31] die geheimen Permutationstabellen. Dann durchläuft die Eingabe zunächst 8 Mal die folgende Kompression (nach [HP00], siehe Weblinks):

For i=0 to 4 do:
  For j=0 to 2ⁱ-1 do:
    For k=0 to 2^4-i-1 do:
      s = k + j*2^5-i
      t = s + 2^4-i
      x = (X[s] + 2X[t]) mod 2^9-i)
      y = (2X[s] + X[t]) mod 2^9-i)
      X[s] = Ti[x]
      X[t] = Ti[y]

Nach jeder Permutation werden die 16 Bytes Ausgabe in X[16..31] und K erneut in X[0..15] gespeichert.

COMP128 gilt als unsicher, da der Hash kleine Veränderungen in der Eingabe nicht hinreichend streut. Aufgrund des Geburtstagsproblems lässt sich dies in einem Chosen Challenge-Angriff dergestalt ausnutzen, dass innerhalb von $\mathcal{O}(2^{17.5})$ Abfragen der SIM-Karte der gesamte Schlüssel extrahiert werden kann.