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 COMP128. The first three were originally confidential. A partial description of the first version was leaked in 1997 and completed via reverse engineering. This led to a full publication in 1998.[1] The second and third versions were obtained via reverse engineering of software which verifies SIM cards compliance.[2]

Introduction[edit]

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

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

The COMP128 algorithms combine the functionality of A3 and A8.

COMP128 algorithms[edit]

Several COMP128 algorithms were designed:

  • COMP128-1 – original algorithm with known weaknesses
  • COMP128-2 – stronger algorithm which still clears the 10 rightmost bits of Kc
  • COMP128-3 – same algorithm as COMP128-2 with all 64 bits of Kc generated
  • COMP128-4 – based on the 3GPP (3rd Generation Partnership Project) algorithm "Milenage", which uses AES

COMP128-1 description[edit]

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.

// compression tables
const T0[512]: array of bytes
const T1[256]: array of bytes
const T2[128]: array of bytes
const T3[64] : array of bytes
const T4[32] : array of bytes

function comp128
    input RAND[128]: array of bits
    input Ki[128]   : array of bits

    output SRES[32]: array of bits
    output Kc[64]   : array of bits

    var x[32]     : array of bytes
    var bit[128]  : array of bits
    var 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]    
                end
            end
        end
        for j := 0 to 31
            for k := 0 to 3
                bit[4 * j + k] := x[j]3−k
            end
        end
        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]
                end
            end
        end
    end
    SRES := bit[0..31]
    Kc := bit[74..127]  00000000002
end

COMP128-2/3 description[edit]

The implementation of COMP128-2 and COMP128-3 is noticeably more complex than COMP128-1. For a full description of the algorithm, the reader can view the OsmocomBB implementation or FreeRADIUS implementation, both based on the Python code from the Secrets of Sim[2] article . COMP128-2 is identical to COMP128-3 except for the fact that at the end, it clears the 10 rightmost bits of Kc.

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.[3]

The session keys produced by COMP128-1 and COMP128-2 have only 54 bits of entropy. This significantly weakens the A5 or A6 encryption.

References[edit]

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

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.1033Freely accessible