3rd Generation Partnership Project; Technical Specification Group Services and System Aspects

we mean that assumes the value that had before the assignment took place. For instance,

x = x + y + 3

means

3.3 Bit/Byte ordering

For example an n-bit STRING is subdivided into 64-bit substrings SB0,SB1…SBi so if we have a string:

0x0123456789ABCDEFFEDCBA987654321086545381AB594FC28786404C50A37…

we have:

SB1 = 0xFEDCBA9876543210

SB2 = 0x86545381AB594FC2

SB3 = 0x8786404C50A37…

In binary this would be:

000000010010001101000101011001111000100110101011110011011110111111111110…

with SB0 = 0000000100100011010001010110011110001001101010111100110111101111

SB1 = 1111111011011100101110101001100001110110010101000011001000010000

SB2 = 1000011001010100010100111000000110101011010110010100111111000010

SB3 = 1000011110000110010000000100110001010000101000110111…

3.4 List of Symbols

Å The bitwise exclusive-OR operation

|| The concatenation of the two operands.

KASUMI[x]k The output of the KASUMI algorithm applied to input value x

X[i] The ith bit of the variable X. (X = X[0] || X[1] || X[2] || ….. ).

Y{i} The ith octet of the variable Y. (Y = Y{0} || Y{1} || Y{2} || ….. ).

Zi The ith 64-bit block of the variable Z. (Z = Z0 || Z1 || Z2 || …. ).

3.5 List of Variables

BLKCNT a 64-bit counter used in the KGCORE function.

BLOCK1 a string of keystream bits output by the A5/4 algorithm - 114 bits for GSM, 348 bits for ECSD.

BLOCK2 a string of keystream bits output by the A5/4 algorithm - 114 bits for GSM, 348 bits for ECSD.

BLOCKS an integer variable indicating the number of successive applications of KASUMI that need to be performed.

CA an 8-bit input to the KGCORE function.

CB a 5-bit input to the KGCORE function.

CC a 32-bit input to the KGCORE function.

CD a 1-bit input to the KGCORE function.

CE a 16-bit input to the KGCORE function.

CK a 128-bit input to the KGCORE function.

CL an integer input to the KGCORE function, in the range 1…219 inclusive, specifying the number of output bits for KGCORE to produce.

CO the output bitstream (CL bits) from the KGCORE function.

COUNT a 22-bit frame dependent input to both the GSM and EDGE A5/4 algorithms.

DIRECTION a 1-bit input to the GEA4 algorithm, indicating the direction of transmission (uplink or downlink).

INPUT a 32-bit frame dependent input to the GEA4 algorithm.

KC the cipher key that is an input to each of the three cipher algorithms defined here. Although at the time of writing the standards specify that KC is 64 bits long, the algorithm specifications here allow it to be of any length between 64 and 128 inclusive, to allow for possible future enhancements to the standards.

KLEN the length of KC in bits, between 64 and 128 inclusive (see above).

KM a 128-bit constant that is used to modify a key. This is used in the KGCORE function.

KS[i] the ith bit of keystream produced by the keystream generator in the KGCORE function.

KSBi the ith block of keystream produced by the keystream generator in the KGCORE function. Each block of keystream comprises 64 bits.

M an input to the GEA4 algorithm, specifying the number of octets of output to produce.

OUTPUT the stream of output octets from the GEA4 algorithm.

4 Core function KGCORE

4.1 Introduction

4.2 Inputs and Outputs

NOTE 1: All the algorithms specified in this document assign a constant, all-zeroes value to CE.

More general use of CE is, however, available for possible future uses of KGCORE.

4.3 Components and Architecture

The function KGCORE is based on the block cipher KASUMI that is specified in TS 55.517 [2]. KASUMI is used in a form of output-feedback mode and generates the output bitstream in multiples of 64 bits.

The feedback data is modified by static data held in a 64-bit register A, and an (incrementing) 64 bit counter BLKCNT.

4.4 Initialisation

We set the 64-bit register A to CC || CB || CD || 0 0 || CA || CE, i.e.:

We set the key modifier KM to 0x55555555555555555555555555555555

We set KSB₀ to zero.

One operation of KASUMI is then applied to the register A, using a modified version of the confidentiality key.

4.5 Keystream Generation

Once the keystream generator has been initialised in the manner defined in section 4.4, it is ready to be used to generate keystream bits. The keystream generator produces bits in blocks of 64 at a time, but the number CL of output bits to produce may not be a multiple of 64; between 0 and 63 of the least significant bits are therefore discarded from the last block, depending on the total number of bits specified by CL.

So let BLOCKS be equal to (CL/64) rounded up to the nearest integer. (For instance, if CL = 128 then BLOCKS = 2; if CL = 129 then BLOCKS = 3.)

To generate each keystream block (KSB) we perform the following operation:

For each integer n with 1 ≤ n ≤ BLOCKS we define:

KSB_n = KASUMI[ A  BLKCNT  KSB_n-1]_CK

where BLKCNT = n-1

The individual bits of the output are extracted from KSB₁ to KSB_BLOCKS in turn, most significant bit first, by applying the operation:

- For n = 1 to BLOCKS, and for each integer i with 0  i  63 we define:

CO[((n-1)*64)+i] = KSB_n[i]

5 A5/4 algorithm for GSM encryption

5.1 Introduction

The GSM A5/4 algorithm produces two 114-bit keystream strings, one of which is used for uplink encryption/decryption and the other for downlink encryption/decryption.

We define this algorithm in terms of the core function KGCORE.

5.2 Inputs and Outputs

The inputs to the algorithm are given in table 3, the output in table 4:

Table 3: GSM A5/4 inputs

Parameter	Size (bits)	Comment
COUNT	22	Frame dependent input COUNT[0]…COUNT[21]
KC	KLEN	Cipher key KC[0]… KC[KLEN-1], where KLEN is in the range 64…128 inclusive (see Notes 1 and 2 below)

Table 4: GSM A5/4 outputs

Parameter	Size (bits)	Comment
BLOCK1	114	Keystream bits BLOCK1[0]…BLOCK1[113]
BLOCK2	114	Keystream bits BLOCK2[0]…BLOCK2[113]

NOTE 1: The specification of the A5/4 algorithm only allows KLEN to be of value 128.

NOTE 2: t must be assumed that K_C is unstructured data — it must not be assumed, for instance, that any bits of K_C have predetermined values.

5.3 Function Definition

(See figure B.2 in Annex B).

We define the function by mapping the GSM A5/4 inputs onto the inputs of the core function KGCORE, and mapping the output of KGCORE onto the outputs of GSM A5/4.

So we define:

CA[0]…CA[7] = 0 0 0 0 1 1 1 1

CB[0]…CB[4] = 0 0 0 0 0

CC[0]…CC[9] = 0 0 0 0 0 0 0 0 0 0

CC[10]…CC[31] = COUNT[0]…COUNT[21]

CD[0] = 0

CE[0]…CE[15] = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

CK[0]…CK[KLEN-1] = K_C[0]…K_C[KLEN-1]

If KLEN < 128 then

- CK[KLEN]…CK[127] = K_C[0]…K_C[127 – KLEN]

(So in particular if KLEN = 128 then CK = K_C)

CL = 228

Apply KGCORE to these inputs to derive the output CO[0]…CO[227].

Then define:

BLOCK1[0]…BLOCK1[113] = CO[0]…CO[113]

BLOCK2[0]…BLOCK2[113] = CO[114]…CO[227]

6 A5/4 algorithm for ECSD encryption

6.1 Introduction

The A5/4 algorithm for ECSD produces two 348-bit keystream strings, one of which is used for uplink encryption/decryption and the other for downlink encryption/decryption.

We define this algorithm in terms of the core function KGCORE.

6.2 Inputs and Outputs

The inputs to the algorithm are given in table 5, the output in table 6:

Table 5: ECSD A5/4 inputs

Parameter	Size (bits)	Comment
COUNT	22	Frame dependent input COUNT[0]…COUNT[21]
KC	KLEN	Cipher key KC[0]… KC[KLEN-1], where KLEN is in the range 64…128 inclusive (see Notes 1 and 2 below)

Table 6: ECSD A5/4 outputs

Parameter	Size (bits)	Comment
BLOCK1	348	Keystream bits BLOCK1[0]…BLOCK1[347]
BLOCK2	348	Keystream bits BLOCK2[0]…BLOCK2[347]

NOTE 1: The specification of the A5/4 algorithm only allows KLEN to be of value 128

NOTE 2: It must be assumed that K_C is unstructured data — it must not be assumed, for instance, that any bits of K_C have predetermined values.

6.3 Function Definition

(See figure B.3 in Annex B).

We define the function by mapping the ECSD A5/4 inputs onto the inputs of the core function KGCORE, and mapping the output of KGCORE onto the outputs of ECSD A5/4.

So we define:

CA[0]…CA[7] = 1 1 1 1 0 0 0 0

CB[0]…CB[4] = 0 0 0 0 0

CC[0]…CC[9] = 0 0 0 0 0 0 0 0 0 0

CC[10]…CC[31] = COUNT[0]…COUNT[21]

CD[0] = 0

CE[0]…CE[15] = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

CK[0]…CK[KLEN-1] = K_C[0]…K_C[KLEN-1]

If KLEN < 128 then

CK[KLEN]…CK[127] = K_C[0]…K_C[127 – KLEN]

(So in particular if KLEN = 128 then CK = K_C)

CL = 696

Apply KGCORE to these inputs to derive the output CO[0]…CO[695].

Then define:

BLOCK1[0]…BLOCK1[347] = CO[0]…CO[347]

BLOCK2[0]…BLOCK2[347] = CO[348]…CO[695]

7 GEA4 algorithm for GPRS encryption

7.1 Introduction

The GPRS GEA4 algorithm produces an M-byte keystream string. M can vary; in this specification we assume that M will never exceed 2¹⁶ = 65536.

We define this algorithm in terms of the core function KGCORE.

7.2 Inputs and Outputs

The inputs to the algorithm are given in table 7, the output in table 8:

Table 7: GEA4 inputs

Parameter	Size (bits)	Comment
INPUT	32	Frame dependent input INPUT[0]…INPUT[31]
DIRECTION	1	Direction of transmission indicator DIRECTION[0]
KC	KLEN	Cipher key KC[0]… KC[KLEN-1], where KLEN is in the range 64…128 inclusive (see Notes 1 and 2 below)
M		Number of octets of output required, in the range 1 to 65536 inclusive

Table 8: GEA4 outputs

Parameter	Size (bits)	Comment
OUTPUT	8M	Keystream octets OUTPUT{0}…OUTPUT{M-1}

NOTE 1: The specification of the GEA4 algorithm only allows KLEN to be of value 128.

NOTE 2: It must be assumed that K_C is unstructured data — it must not be assumed, for instance, that any bits of K_C have predetermined values.

7.3 Function Definition

(See figure B.4 in Annex B).

We define the function by mapping the GEA4 inputs onto the inputs of the core function KGCORE, and mapping the output of KGCORE onto the outputs of GEA4.

So we define:

CA[0]…CA[7] = 1 1 1 1 1 1 1 1

CB[0]…CB[4] = 0 0 0 0 0

CC[0]…CC[31] = INPUT[0]…INPUT[31]

CD[0] = DIRECTION[0]

CE[0]…CE[15] = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

CK[0]…CK[KLEN-1] = K_C[0]…K_C[KLEN-1]

If KLEN < 128 then

CK[KLEN]…CK[127] = K_C[0]…K_C[127 – KLEN]

(So in particular when KLEN = 128 then CK = K_C)

CL = 8M

Apply KGCORE to these inputs to derive the output CO[0]…CO[8M-1].

Then for 0  i  M-1 define:

OUTPUT{i} = CO[8i]…CO[8i + 7]

where CO[8i] is the most significant bit of the octet.

Annex A (informative):
Specification of the 3GPP confidentiality algorithm f8

A.1 Introduction

The algorithms defined in this specification have been designed to have much in common with the 3GPP confidentiality algorithm, to ease simultaneous implementation of multiple algorithms. To clarify this, a specification of f8 is given here in terms of the core function KGCORE. For the definitive specification of f8, the reader is referred to TS 35.202 [5].

A.2 Inputs and Outputs

The inputs to the algorithm are given in table A.1, the output in table A.2.

Table A.1: f8 inputs

Parameter	Size (bits)	Comment
COUNT	32	Frame dependent input COUNT[0]…COUNT[31]
BEARER	5	Bearer identity BEARER[0]…BEARER[4]
DIRECTION	1	Direction of transmission DIRECTION[0]
CK	128	Confidentiality key CK[0]…CK[127]
LENGTH		The number of bits to be encrypted/decrypted (1-20000)

Table A.2: f8 output

Parameter	Size (bits)	Comment
KS	1-20000	Keystream bits KS[0]…KS[LENGTH-1]

NOTE: The definitive specification of f8 includes a bitstream IBS amongst the inputs, and gives the output as a bitstream OBS; both of these bitstreams are LENGTH bits long. OBS is obtained by the bitwise exclusive-or of IBS and KS. We present just the keystream generator part of f8 here, for closer comparison with A5/4 and GEA4.

A.3 Function Definition

(See fig 5 Annex B)

We define the function by mapping the f8 inputs onto the inputs of the core function KGCORE, and mapping the output of KGCORE onto the outputs of f8.

So we define:

CA[0]…CA[7] = 0 0 0 0 0 0 0 0

CB[0]…CB[4] = BEARER[0]…BEARER[4]

CC[0]…CC[31] = COUNT[0]…COUNT[31]

CD[0] = DIRECTION[0]

CE[0]…CE[15] = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

CK[0]…CK[127] = CK[0]…CK[127]

CL = LENGTH

Apply KGCORE to these inputs to derive the output CO[0]…CO[LENGTH-1].

Then define:

KS[0]…KS[LENGTH-1] = CO[0]…CO[LENGTH-1]

Annex B (informative):
Figures of the algorithms

NOTE: BLKCNT is specified as a 64-bit counter so there is no ambiguity in the expression

A  BLKCNT  KSB_n-1 where all operands are of the same size. In a practical implementation, where the keystream generator is required to produce no more than a certain number of bits, only the least significant few bits of the counter need to be realised.
Figure B.1: KGCORE Core Keystream Generator Function



Figure B.2: GSM A5/4 Keystream Generator Function



Figure B.3: ECSDA5/4 Keystream Generator Function



Figure B.4: GEA4 Keystream Generator Function



Figure B.5: 3GPP f8 Keystream Generator Function

Table B.1: GSM A5/4, ECSD A5/4, GEA4 and f8 in terms of KGCORE

	GSM A5/4	ECSD A5/4	GEA4	f8
CA	0 0 0 0 1 1 1 1	1 1 1 1 0 0 0 0	1 1 1 1 1 1 1 1	0 0 0 0 0 0 0 0
CB	0 0 0 0 0	0 0 0 0 0	0 0 0 0 0	BEARER
CC	0...0||COUNT	0...0||COUNT	INPUT	COUNT
CD	0	0	DIRECTION	DIRECTION
CE	0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
CK	KC 128 bits			CK
CO	BLOCK1||BLOCK2	BLOCK1||BLOCK2	OUTPUT	KS

NOTE: The values for A5/4 are the same as for A5/3.

The values for ECSD A5/4 are the same as for ECSD A5/3
The values for GEA4 are the same as for GEA3

Annex C (informative):
Simulation program listings

For coding example of the algorithms see Annex C in TS 55.216 [1]: Specification of the A5/3 Encryption Algorithms for GSM and ECSD, and the GEA3 Encryption Algorithm for GPRS; Document 1: A5/3 and GEA3 Specifications.

Annex D (informative):
Test data

Test data for the algorithms are to be found in:

TS 55.517 [2]: Specification of the A5/3 Encryption Algorithms for GSM and ECSD, and the GEA3Encryption Algorithm for GPRS; Document 2: Implementors' Test Data.

TS 55.518 [3]: Specification of the A5/3 Encryption Algorithms for GSM and ECSD, and the GEA3 Encryption Algorithm for GPRS; Document 3: Design Conformance Test Data.

Both documents contain examples where KLEN is set to be 128 bits.

Annex E (informative):
Change history

Change history
Date	TSG #	TSG Doc.	CR	Rev	Subject/Comment	Old	New
02-2004	-	-	-	-	Draft presented to SA WG3 for agreement	---	0.1.0
03-2004	SA_23	SP-040170	-	-	Draft provided to TSG SA for information	0.1.0	1.0.0
09-2009	SA_45	SP-090647	-	-	Draft provided to TSG SA for approval	1.0.0	2.0.0
09-2009	SA_45	SP-090647	-	-	Approval at SA#45 and placement under CR control Technical content split from placeholder TS 55.226.	2.0.0	9.0.0