Higher Institute for Applied Science and Technology
Telecommunication department
Fifth year
A3-A5-A8
Algorithms
By: ALI ALAmmori
Supervisor: Dr. Nizar Zarka
Outlines:
▪ GSM Authentication
▪ A3 Authentication
▪ A8 Key Generator
▪ Comp128
▪ A5-encryption
Ali Alammori & Dr. Nizar Zarka
GSM Authentication
▪ the MS will send either an IMSI or a TMSI to the BSS.
▪ The BSS forwards the MSC/VLR
▪ The MSC/VLR forwards the IMSI to the HLR and requests verification
of the IMSI as well as Authentication Triplets.
▪ The HLR will forward the IMSI to the Authentication Center (AUC)
and request authentication triplets.
▪ The AUC generates the triplets and sends them along with the IMSI,
back to the HLR.
Ali Alammori & Dr. Nizar Zarka
GSM Authentication
▪ The HLR validates the IMSI by ensuring it is allowed on the network
and is allowed subscriber services. It then forwards the IMSI and
Triplets to the MSC/VLR.
▪ The MSC/VLR stores the SRES and the Kc and forwards the RAND to
the BSS and orders the BSS to authenticate the MS
▪ The MS uses the RAND to calculate the SRES and sends the SRES
back to the BSS
Ali Alammori & Dr. Nizar Zarka
GSM Authentication
▪ The BSS forwards the SRES up to the MSC/VLR.
▪ The MSC/VLR compares the SRES generated by the AUC with the
SRES generated by the MS. If they match, then authentication is
completed successfully
Ali Alammori & Dr. Nizar Zarka
Ali Alammori & Dr. Nizar Zarka
A3- Authentication
A3 Input:
o 128-bit RAND random
Ki
o Ki 128-bit private key
RAND
SRES
A3 Output: Ki A3
o 32-bit SRES signed response
Ali Alammori & Dr. Nizar Zarka
A8 Key Generator
A8 Input:
o 128-bit RAND random
o Ki 128-bit private key
RAND
Kc
A8 Output: Ki A8
o 64-bit Kc Cipher Key
Ali Alammori & Dr. Nizar Zarka
Comp128
Comp128 Input:
o 128-bit RAND random
o Ki 128-bit private key
RAND
Comp128 Output: SRES
o 128-bit : Ki A3 kc
the first 32-bit SERS
the last 54-bit used as Kc after adding 10 zeros
Ali Alammori & Dr. Nizar Zarka
Comp128
▪ Comp 128 is MAC function (Message Authentication Codes)
▪ We have 5 secret tables T0-512 Byte,T1-256 Byte,T2-128 Byte,T3-64 Byte
and T4 -32 Byte
▪ Then there are 8 loops of the following compression function :
Apply 5 rounds of table lookups and substitution using table T0 to T4.
Perform a permutation on the 128 output bits before next loop ,except in
the last loop.
Ali Alammori & Dr. Nizar Zarka
Comp128
The pseudocode for the 5 rounds of substitutions : With X -32 byte
for j := 0 to 4 X[0..15]=Ki
for k := 0 to 2j-1 X[16 ..31]=RAND
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 Ali Alammori & Dr. Nizar Zarka
Ali Alammori & Dr. Nizar Zarka
comp128
FormBitsFromBytes
for j := 0 to 31 With B -128 bit
for k := 0 to 3
B[4 * j + k] := x[j]3-k
end
end
pseudocode for permutation:
if i < 8
for j := 0 to 15
for k := 0 to 7
x[j + 16]7-k := B[((8 * j + k) * 17) mod 128]
end
end
end
Ali Alammori & Dr. Nizar Zarka
comp128
▪ After 8 loop we can extract SRES and Kc
SRES := B[0..31]
Kc := B[74..127] |00000000002
Comp128 algorithm stored in SIM
Ali Alammori & Dr. Nizar Zarka
A5-encryption
A5 Input:
o Kc 64-bit session key
Fn 22-bit Frame counter
A5 is a stream
cipher
A5 Output:
o cipher text
Ali Alammori & Dr. Nizar Zarka
A5-encryption
Step 1
Kc ▪ Composed of 3 Linear Feedback Shift Registers (LFSRs)
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 LFSR1
8 13 16 17 18
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 LFSR2
10 20 21
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 LFSR3
7 10 20 21 22
Ali Alammori & Dr. Nizar Zarka
A5-encryption
fn Step 2
1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1
8 13 16 17 18
1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 1 0 LFSR2
10 20 21
0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 1 0 0 0 LFSR3
7 10 20 21 22
Ali Alammori & Dr. Nizar Zarka
A5-encryption
Step 3
0 1 0 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 1 LFSR1
8 13 16 17 18
M Function
1 0 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 LFSR2
10 20 21
0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 1 1 0 1 LFSR3
7 10 20 21 22
Ali Alammori & Dr. Nizar Zarka
A5-encryption
Step 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
8 13 16 17 18
M
Function 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
10 20 21
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
7 10 20 21 22
Ali Alammori & Dr. Nizar Zarka 228 –bit stream key
A5-encryption
Step 5
▪ Plan text XOR Key Stream =Cipher text
Ali Alammori & Dr. Nizar Zarka
Ali Alammori & Dr. Nizar Zarka