COMP128

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The COMP128 algorithms are implementations of the A3 and A8 algorithms defined in the GSM standard. The A3 algorithm is used to authenticate the mobile station to the network. The A8 algorithm is used to generate the session key used by A5 to encrypt the data transmitted between the mobile station and the BTS.

Currently there exist four versions of the COMP128 algorithms. The three first version were originally confidential. A partial description of the first version of COMP128 was leaked in 1997 and completed via reverse engineering. This led to a full publication in 1998.[1] The second and third version of COMP128 were obtained by means of reverse engineering software which verifies SIM card compliance.[2]

Introduction[edit]

For details on the way A3 and A8 are used see Authentication Center.

A3 and A8 both take a 128 bits key (Ki) and a 128 bits challenge (RAND) as inputs. A3 produces a 32 bits response (SRES) and A8 produces a 64 bits session key (Kc).

COMP128 combines the functionality of A3 and A8. COMP128-1 is built around a compression function with two 128 bits inputs and one 128 bits output. The function has eight rounds and is based on a butterfly structure with five stages.

COMP128 algorithms[edit]

Several COMP128 algorithms were designed:

  • COMP128-1 first algorithm with known weaknesses
  • COMP128-2 has replaced the COMP128-1, but still sets the 10 rightmost bits of the Kc to 0), deliberately weakening the A5 ciphering
  • COMP128-3 same as COMP128-2 algorithm, but all 64-bits of the Kc are generated
  • COMP128-4 based on the 3GPP (3rd Generation Partnership Project) algorithm ("Milenage"), which uses AES

COMP128-1 Description[edit]

T0[512], T1[256], T2[128], T3[64] and T4[32] are compression tables.

comp128 : RAND, Ki -> SRES, Kc
{
 x[32]:      array of bytes
 bit[128]:   array of bits
 m, n, y, z: integers

 x[16..31] := RAND
 for i := 1 to 8
   x[0..15] := Ki
   for j := 0 to 4
     for k := 0 to 2j-1
       for l := 0 to 24-j-1
         m := l + k * 25-j
         n := m + 24-j
         y := (x[m] + 2 * x[n]) mod 29-j
         z := (2 * x[m] + x[n]) mod 29-j
         x[m] := Tj[y]
         x[n] := Tj[z]    
   for j := 0 to 31
     for k := 0 to 3
       bit[4 * j + k] := x[j]3-k
   if i < 8  
     for j := 0 to 15
       for k := 0 to 7
         x[j + 16]7-k := bit[((8 * j + k) * 17) mod 128]
 SRES := bit[0..31]
 Kc := bit[74..127] \| 00000000002
}

COMP128-2/3 Description[edit]

The implementation of COMP128-2 and COMP128-3 is noticably more complex than COMP128-1. For a full description of the algorithm, the reader can view the OsmocomBB implementation. The COMP128-2 and COMP-128-3 are very similar. In fact, the COMP128-2 is identical to the COMP128-3 algorithm, except that at the end of the algorithm the 10 rightmost bits of the Kc are set to zero.

Security[edit]

The COMP128-1 hash function is considered weak because there is insufficient diffusion of small changes in the input.

Practical attacks have been demonstrated that can recover the subscriber key from the SIM. Replacements algorithms have since been developed.[3]

In addition the session key produced by COMP128 has only 54 bits of entropy. This significantly weakens A5,A6.

References[edit]

  1. ^ Briceno, Marc; Goldberg, Ian; Wagner, David (1998), Implementation of COMP128, archived from the original on 2009-03-18 
  2. ^ Hacking Projects (2013), Secrets of the SIM 
  3. ^ Brumley, Billy (2004), A3/A8 & COMP128 

External links[edit]

  • Briceno, Marc; Goldberg, Ian (1998), GSM Cloning 
  • Handschuh, Helena; Paillier, Pascal (2000), Reducing the Collision Probability of Alleged Comp128, CiteSeerX: 10.1.1.141.1033