Content for TS 35.201 Word version: 17.0.0
This Technical Specification has been produced by the 3rd Generation Partnership Project (3GPP).
The 3GPP Confidentiality and Integrity Algorithms
f8 &
f9 have been developed through the collaborative efforts of the European Telecommunications Standards Institute (ETSI), the Association of Radio Industries and Businesses (ARIB), the Telecommunications Technology Association (TTA), the T1 Committee.
The
f8 &
f9 Algorithms Specifications may be used only for the development and operation of 3G Mobile Communications and services. Every Beneficiary must sign a Restricted Usage Undertaking with the Custodian and demonstrate that he fulfills the approval criteria specified in the Restricted Usage Undertaking.
Furthermore, Mitsubishi Electric Corporation holds essential patents on the Algorithms. The Beneficiary must get a separate IPR License Agreement from Mitsubishi Electronic Corporation Japan.
For details of licensing procedures, contact ETSI, ARIB, TTA or T1.
…
This specification has been prepared by the 3GPP Task Force, and gives a detailed specification of the 3GPP confidentiality algorithm
f8, and the 3GPP integrity algorithm
f9.
This document is the first of four, which between them form the entire specification of the 3GPP Confidentiality and Integrity Algorithms:

3GPP TS 35.201: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 1: f8 and f9 Specification".

3GPP TS 35.202: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 2: KASUMI Specification".

3GPP TS 35.203: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 3: Implementors' Test Data".

3GPP TS 35.204: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 4: Design Conformance Test Data".
The normative part of the specification of the
f8 (confidentiality) and
f9 (integrity) algorithms is in the main body of this document. The annexes to this document are purely informative.
Annex A.1 contains illustrations of functional elements of the algorithm, while
Annex A.2 contains an implementation program listing of the cryptographic algorithm specified in the main body of this document, written in the programming language C.
The normative part of the specification of the block cipher (KASUMI) on which they are based is in the main body of Document 2. The annexes of that document, and Documents 3 and 4 above, are purely informative.
This specification gives a detailed specification of the 3GPP confidentiality algorithm f8, and the 3GPP integrity algorithm f9.
Clause 1 introduces the algorithms and describes the notation used in the subsequent sections.
Clause 3 specifies the confidentiality algorithm f8.
Clause 4 specifies the integrity algorithm f9.
The following documents contain provisions which, through reference in this text, constitute provisions of the present document.

References are either specific (identified by date of publication, edition number, version number, etc.) or nonspecific.

For a specific reference, subsequent revisions do not apply.

For a nonspecific reference, the latest version applies. In the case of a reference to a 3GPP document (including a GSM document), a nonspecific reference implicitly refers to the latest version of that document in the same Release as the present document.
[1]
TS 33.102: version 3.2.0: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Security Architecture".
[2]
TS 33.105: version 3.1.0: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Cryptographic Algorithm Requirements".
[3]
TS 35.201: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 1: f8 and f9 Specification".
[4]
TS 35.202: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 2: KASUMI Specification".
[5]
TS 35.203: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 3: Implementors' Test Data".
[6]
TS 35.204: "3rd Generation Partnership Project; Technical Specification Group Services and System Aspects; 3G Security; Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 4: Design Conformance Test Data".
[7]
ISO/IEC 97971:1999: "Information technology  Security techniques  Message Authentication Codes (MACs)".
Within the security architecture of the 3GPP system there are two standardised algorithms: A confidentiality algorithm
f8, and an integrity algorithm
f9. These algorithms are fully specified here. Each of these algorithms is based on the
KASUMI algorithm that is specified in a companion document [4].
KASUMI is a block cipher that produces a 64bit output from a 64bit input under the control of a 128bit key.
The confidentiality algorithm
f8 is a stream cipher that is used to encrypt/decrypt blocks of data under a confidentiality key
CK. The block of data may be between 1 and 20000 bits long. The algorithm uses
KASUMI in a form of outputfeedback mode as a keystream generator.
The integrity algorithm
f9 computes a 32bit MAC (Message Authentication Code) of a given input message using an integrity key
IK. The approach adopted uses
KASUMI in a form of CBCMAC mode.
We use the prefix 0x to indicate hexadecimal numbers.
We use the assignment operator '=', as used in several programming languages. When we write

<variable> = <expression>
we mean that <variable> assumes the value that <expression> had before the assignment took place. For instance,
means
(new value of x) becomes (old value of x) + (old value of y) + 3.
All data variables in this specification are presented with the most significant bit (or byte) on the left hand side and the least significant bit (or byte) on the right hand side. Where a variable is broken down into a number of substrings, the left most (most significant) substring is numbered 0, the next most significant is numbered 1 and so on through to the least significant.
For example an nbit MESSAGE is subdivided into 64bit substrings MB
_{0}, MB
_{1}… MB
_{i} so if we have a message:

0x0123456789ABCDEFFEDCBA987654321086545381AB594FC28786404C50A37…
we have:

MB_{0} = 0x0123456789ABCDEF

MB_{1} = 0xFEDCBA9876543210

MB_{2} = 0x86545381AB594FC2

MB_{3} = 0x8786404C50A37…
In binary this would be:

000000010010001101000101011001111000100110101011110011011110111111111110…
with

MB_{0} = 0000000100100011010001010110011110001001101010111100110111101111

MB_{1} = 1111111011011100101110101001100001110110010101000011001000010000

MB_{2} = 1000011001010100010100111000000110101011010110010100111111000010

MB_{3} = 1000011110000110010000000100110001010000101000110111…
=
The assignment operator.
⊕
The bitwise exclusiveOR operation.

The concatenation of the two operands.
KASUMI[x]k
The output of the KASUMI algorithm applied to input value x
using the key k.
X[i]
The ith bit of the variable X. (X = X[0]  X[1]  X[2]  ….. ).
Yi
The ith block of the variable Y. (Y = Y0  Y1  Y2  …. ).
A, B
are 64bit registers that are used within the f8 and f9 functions to hold intermediate values.
BEARER
a 5bit input to the f8 function.
BLKCNT
a 64bit counter used in the f8 function.
BLOCKS
an integer variable indicating the number of successive applications of KASUMI that need to be performed, for both the f8 and f9 functions.
CK
a 128bit confidentiality key.
COUNT
a 32bit time variant input to both the f8 and f9 functions.
DIRECTION
a 1bit input to both the f8 and f9 functions indicating the direction of transmission (uplink or downlink).
FRESH
a 32bit random input to the f9 function.
IBS
the input bit stream to the f8 function.
IK
a 128bit integrity key.
KM
a 128bit constant that is used to modify a key. This is used in both the f8 and f9 functions. (It takes a different value in each function).
KS[i]
is the ith bit of keystream produced by the keystream generator.
KSBi
is the ith block of keystream produced by the keystream generator. Each block of keystream comprises 64 bits.
LENGTH
is an input to the f8 and f9 functions. It specifies the number of bits in the input bitstream.
MACI
is the 32bit message authentication code (MAC) produced by the integrity function f9.
MESSAGE
is the input bitstream of LENGTH bits that is to be processed by the f9 function.
OBS
the output bit streams from the f8 function.
PS
is the input padded string processed by the f9 function.
REGISTER
is a 64bit value that is used within the f8 function.
The confidentiality algorithm f8 is a stream cipher that encrypts/decrypts blocks of data between 1 and 20000 bits in length.
The inputs to the algorithm are given in
Table 1, the output in
Table 2:
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  X18 (see Note 1)  The number of bits to be encrypted/decrypted (120000) 
IBS  120000  Input bit stream IBS[0]….IBS[LENGTH1] 
NOTE 1:
In the sample Ccode we treat LENGTH as a 32bit integer.

Parameter 
Size (bits) 
Comment 
OBS  120000  Output bit stream OBS[0]….OBS[LENGTH1] 
(See
Figure 1 in
Annex A.1)
The keystream generator is based on the block cipher
KASUMI that is specified in
TS 35.202.
KASUMI is used in a form of outputfeedback mode and generates the output keystream in multiples of 64bits.
The feedback data is modified by static data held in a 64bit register A, and an (incrementing) 64bit counter
BLKCNT.
In this section we define how the keystream generator is initialised with the key variables before the generation of keystream bits.
We set the 64bit register A to COUNT  BEARER  DIRECTION  0…0
(left justified with the right most 26 bits set to 0).
i.e. A = COUNT[0]…COUNT[31] BEARER[0]…BEARER[4] DIRECTION[0] 0…0
We set counter BLKCNT to zero.
We set the key modifier KM to 0x55555555555555555555555555555555
We set KSB0 to zero.
One operation of KASUMI is then applied to the register A, using a modified version of the confidentiality key.
Once the keystream generator has been initialised in the manner defined in section 3.4, it is ready to be used to generate keystream bits. The plaintext/ciphertext to be encrypted/decrypted consists of LENGTH bits (120000) whilst the keystream generator produces keystream bits in multiples of 64 bits. Between 0 and 63 of the least significant bits are discarded from the last block depending on the total number of bits required by LENGTH.
So let BLOCKS be equal to (LENGTH/64) rounded up to the nearest integer. (For instance, if LENGTH = 128 then BLOCKS = 2; if LENGTH = 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:
KSBn = KASUMI[ A ⊕ BLKCNT ⊕ KSBn1]CK
where BLKCNT = n1
The individual bits of the keystream are extracted from KSB1 to KSBBLOCKS 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:
KS[((n1)*64)+i] = KSBn[i]
Encryption/decryption operations are identical and are performed by the exclusiveOR of the input data (IBS) with the generated keystream (KS).
For each integer i with 0 ≤ i ≤ LENGTH1 we define:
The integrity algorithm
f9 computes a Message Authentication Code (MAC) on an input message under an integrity key IK. There is no limitation on the input message length of the
f9 algorithm.
For ease of implementation the algorithm is based on the same block cipher (KASUMI) as is used by the confidentiality algorithm
f8.
The inputs to the algorithm are given in
Table 3, the output in
Table 4:
Parameter 
Size (bits) 
Comment 
COUNTI  32  Frame dependent input COUNTI[0]…COUNTI[31] 
FRESH  32  Random number FRESH[0]…FRESH[31] 
DIRECTION  1  Direction of transmission DIRECTION[0] 
IK  128  Integrity key IK[0]…IK[127] 
LENGTH  X19  The number of bits to be 'MAC'd 
MESSAGE  LENGTH  Input bit stream 
NOTE 1:
In the sample Ccode we treat LENGTH as a 32bit integer.

Parameter 
Size (bits) 
Comment 
MACI  32  Message authentication code MACI[0]…MACI[31] 
(See
Figure 2 in
Annex A.1)
The integrity function is based on the block cipher KASUMI that is specified in
TS 35.202. KASUMI is used in a chained mode to generate a 64bit digest of the message input. Finally the leftmost 32bits of the digest are taken as the output value MACI.
In this section we define how the integrity function is initialised with the key variables before the calculation commences.
We set the working variables: A = 0 and B = 0
We set the key modifier KM to 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
We concatenate COUNT, FRESH, MESSAGE and DIRECTION. We then append a single '1' bit, followed by between 0 and 63 '0' bits so that the total length of the resulting string PS (padded string) is an integral multiple of 64 bits, i.e.:
PS = COUNT[0]…COUNT[31] FRESH[0]…FRESH[31] MESSAGE[0]… MESSAGE[LENGTH1] DIRECTION[0] 1 0*
Where 0* indicates between 0 and 63 '0' bits.
We split the padded string PS into 64bit blocks PSi where:
PS = PS0  PS1  PS2  ….  PSBLOCKS1
We perform the following operations for each integer n with 0 ≤ n ≤ BLOCKS1:
A = KASUMI[ A ⊕ PSn ]IK
B = B ⊕ A
Finally we perform one more application of KASUMI using a modified form of the integrity key IK.
The 32bit MACI comprises the leftmost 32 bits of the result.
i.e. For each integer i with 0 ≤ i ≤ 31 we define:
MACI[i] = B[i].
Bits B[32]…B[63] are discarded.
This part of the document is purely informative and does not form part of the normative specification of KASUMI.
A ⊕ BLKCNT ⊕ KSBn1 where all operands are of the same size. In a practical implementation where the key stream generator is required to produce no more than 5114 bits (80 keystream blocks) only the least significant 7 bits of the counter need to be realised.
Header file
/*
* Kasumi.h
**/
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned long u32;
/* a 64bit structure to help with endian issues */
typedef union {
u32 b32[2];
u16 b16[4];
u8 b8[8];
} REGISTER64;
/* prototypes */
void KeySchedule( u8 *key );
void Kasumi( u8 *data );
u8 * f9( u8 *key,int count,int fresh, int dir,u8 *data,int length );
void f8( u8 *key,int count,int bearer,int dir,u8 *data,int length );
Function f8
/*
* F8  Confidentiality Algorithm
*
*
* A sample implementation of f8, the 3GPP Confidentiality algorithm.
*
* This has been coded for clarity, not necessarily for efficiency.
*
* This will compile and run correctly on both Intel (little endian)
* and Sparc (big endian) machines. (Compilers used supported 32bit ints)
*
* Version 1.0 05 November 1999
*
**/
#include "kasumi.h"
#include <stdio.h>
/*
* f8()
* Given key, count, bearer, direction, data,
* and bit length encrypt the bit stream
**/
void f8( u8 *key, int count, int bearer, int dir, u8 *data, int length )
{
REGISTER64 A; /* the modifier */
REGISTER64 temp; /* The working register */
int i, n;
u8 ModKey[16]; /* Modified key */
u16 blkcnt; /* The block counter */
/* Start by building our global modifier */
temp.b32[0] = temp.b32[1] = 0;
A.b32[0] = A.b32[1] = 0;
/* initialise register in an endian correct manner*/
A.b8[0] = (u8) (count>>24);
A.b8[1] = (u8) (count>>16);
A.b8[2] = (u8) (count>>8);
A.b8[3] = (u8) (count);
A.b8[4] = (u8) (bearer<<3);
A.b8[4] = (u8) (dir<<2);
/* Construct the modified key and then "kasumi" A */
for( n=0; n<16; ++n )
ModKey[n] = (u8)(key[n] ^ 0x55);
KeySchedule( ModKey );
Kasumi( A.b8 ); /* First encryption to create modifier */
/* Final initialisation steps */
blkcnt = 0;
KeySchedule( key );
/* Now run the block cipher */
while( length > 0 )
{
/* First we calculate the next 64bits of keystream */
/* XOR in A and BLKCNT to last value */
temp.b32[0] ^= A.b32[0];
temp.b32[1] ^= A.b32[1];
temp.b8[7] ^= (u8) blkcnt;
temp.b8[6] ^= (u8) (blkcnt>>8);
/* KASUMI it to produce the next block of keystream */
Kasumi( temp.b8 );
/* Set <n> to the number of bytes of input data *
* we have to modify. (=8 if length <= 64) */
if( length >= 64 )
n = 8;
else
n = (length+7)/8;
/* XOR the keystream with the input data stream */
for( i=0; i<n; ++i )
*data++ ^= temp.b8[i];
length = 64; /* done another 64 bits */
++blkcnt; /* increment BLKCNT */
}
}
/*
* e n d o f f 8 . c
**/
Function f9
/*
* F9  Integrity Algorithm
*
*
* A sample implementation of f9, the 3GPP Integrity algorithm.
*
* This has been coded for clarity, not necessarily for efficiency.
*
* This will compile and run correctly on both Intel (little endian)
* and Sparc (big endian) machines. (Compilers used supported 32bit ints)
*
* Version 1.1 05 September 2000
*
**/
#include "kasumi.h"
#include <stdio.h>
/*
* f9()
* Given key, count, fresh, direction, data,
* and message length, calculate the hash value
**/
u8 *f9( u8 *key, int count, int fresh, int dir, u8 *data, int length )
{
REGISTER64 A; /* Holds the CBC chained data */
REGISTER64 B; /* Holds the XOR of all KASUMI outputs */
u8 FinalBit[8] = {0x80, 0x40, 0x20, 0x10, 8,4,2,1};
u8 ModKey[16];
static u8 mac_i[4]; /* static memory for the result */
int i, n;
/* Start by initialising the block cipher */
KeySchedule( key );
/* Next initialise the MAC chain. Make sure we *
* have the data in the right byte order. *
* <A> holds our chaining value... *
* <B> is the running XOR of all KASUMI o/ps */
for( n=0; n<4; ++n )
{
A.b8[n] = (u8)(count>>(24(n*8)));
A.b8[n+4] = (u8)(fresh>>(24(n*8)));
}
Kasumi( A.b8 );
B.b32[0] = A.b32[0];
B.b32[1] = A.b32[1];
/* Now run the blocks until we reach the last block */
while( length >= 64 )
{
for( n=0; n<8; ++n )
A.b8[n] ^= *data++;
Kasumi( A.b8 );
length = 64;
B.b32[0] ^= A.b32[0]; /* running XOR across */
B.b32[1] ^= A.b32[1]; /* the block outputs */
}
/* Process whole bytes in the last block */
n = 0;
while( length >=8 )
{
A.b8[n++] ^= *data++;
length = 8;
}
/* Now add the direction bit to the input bit stream *
* If length (which holds the # of data bits in the *
* last byte) is nonzero we add it in, otherwise *
* it has to start a new byte. */
if( length )
{
i = *data;
if( dir )
i = FinalBit[length];
}
else
i = dir ? 0x80 : 0;
A.b8[n++] ^= (u8)i;
/* Now add in the final '1' bit. The problem here *
* is if the message length happens to be n*641. *
* If so we need to process this block and then *
* create a new input block of 0x8000000000000000. */
if( (length==7) && (n==8 ) ) /* then we've filled the block */
{
Kasumi( A.b8 );
B.b32[0] ^= A.b32[0]; /* running XOR across */
B.b32[1] ^= A.b32[1]; /* the block outputs */
A.b8[0] ^= 0x80; /* toggle first bit */
i = 0x80;
n = 1;
}
else
{
if( length == 7 ) /* we finished off the last byte */
A.b8[n] ^= 0x80; /* so start a new one..... */
else
A.b8[n1] ^= FinalBit[length+1];
}
Kasumi( A.b8 );
B.b32[0] ^= A.b32[0]; /* running XOR across */
B.b32[1] ^= A.b32[1]; /* the block outputs */
/* Final step is to KASUMI what we have using the *
* key XORd with 0xAAAA..... */
for( n=0; n<16; ++n )
ModKey[n] = (u8)*key++ ^ 0xAA;
KeySchedule( ModKey );
Kasumi( B.b8 );
/* We return the leftmost 32bits of the result */
for( n=0; n<4; ++n )
mac_i[n] = B.b8[n];
return( mac_i );
}
/*
* e n d o f f 9 . c
**/