we mean that assumes the value that had before the assignment took place. For instance,
x = x + y + 3
means
(new value of x) becomes (old value of x) + (old value of y) + 3.
Bit/Byte ordering
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_{2}, …. So if we have a message:
0x0123456789ABCDEFFEDCBA98765432108654381AB594FC28786404C50A37…
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…
List of Symbols
= The assignment operator.
The bitwise exclusiveOR operation
 The concatenation of the two operands.
x The smallest integer greater than or equal to the real number x.
&_{n} The bitwise AND operation in an nbit register.
<<_{n} t tbit left shift in an nbit register.
>>_{n} t tbit right shift in an nbit register

BEARER the 5bit input to the UEA2 function.
CK the 128bit confidentiality key.
COUNT the 32bit time variant input to the UEA2 and UIA2 functions (COUNTC for UEA2 and COUNTI for UIA2)
DIRECTION the 1bit input to both the UEA2 and UIA2 functions indicating the direction of transmission (uplink or downlink).
FRESH the 32bit random input to the UIA2 function.
IBS the input bit stream to the UEA2 function.
IK the 128bit integrity key.
KS[i] the i^{th} bit of keystream produced by the keystream generator.
LENGTH the input to the UEA2 and UIA2 functions which specifies the number of bits in the input bitstream (12^{32}).
MACI the 32bit message authentication code (MAC) produced by the integrity function UIA2.
MESSAGE the input bitstream of LENGTH bits that is to be processed by the UIA2 function.
OBS the output bit stream from the UEA2 function.
z_{1}, z_{2}, … the 32bit words forming the keystream sequence of SNOW 3G. The word produced first is z_{1}, the next word z_{2} and so on.
3.CONFIDENTIALITY ALGORITHM UEA2
Introduction
The confidentiality algorithm UEA2 is a stream cipher that encrypts/decrypts blocks of data between 1 and 2^{32} bits in length.
Inputs and Outputs
The inputs to the algorithm are given in Table 1, the output in Table 2:
Parameter

Size (bits)

Comment

COUNTC

32

Frame dependent input COUNTC[0]…COUNTC[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

Unspecified

The number of bits to be encrypted/decrypted

IBS

LENGTH

Input bit stream IBS[0]….IBS[LENGTH1]

Table 1. UEA2 inputs
Parameter

Size (bits)

Comment

OBS

LENGTH

Output bit stream OBS[0]….OBS[LENGTH1]

Table 2. UEA2 output

The keystream generator is based on SNOW 3G that is specified in [5]. SNOW 3G is a word oriented stream cipher and generates a keystream in multiples of 32bits.
Initialisation
In this section we define how the keystream generator is initialised with the key variables before the generation of keystream bits.
All variables have length 32 and are presented with the most significant bit on the left hand side and the least significant bit on the right hand side.
K_{3} = CK[0]  CK[1]  CK[2]  …  CK[31]
K_{2} = CK[32]  CK[33]  CK[34]  …  CK[63]
K_{1} = CK[64]  CK[65]  CK[66]  …  CK[95]
K_{0} = CK[96]  CK[97]  CK[98]  …  CK[127]
IV_{3} = COUNTC[0]  COUNTC[1]  COUNTC[2]  …  COUNTC[31]
IV_{2} = BEARER[0]  BEARER[1]  …  BEARER[4]  DIRECTION[0]  0  …  0
IV_{1} = COUNTC[0]  COUNTC[1]  COUNTC[2]  …  COUNTC[31]
IV_{0} = BEARER[0]  BEARER[1]  …  BEARER[4]  DIRECTION[0]  0  …  0
SNOW 3G is initialised as described in document [5].
Keystream Generation
Set L = LENGTH / 32.
SNOW 3G is run as described in document [5] to produce the keystream consisting of the 32bit words z_{1} … z_{L}. The word produced first is z_{1}, the next word z_{2} and so on.
The sequence of keystream bits is KS[0] … KS[LENGTH1], where KS[0] is the most significant bit and KS[31] is the least significant bit of z_{1}, KS[32] is the most significant bit of z_{2} and so on.
Encryption/Decryption
Encryption/decryption operations are identical operations 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:
OBS[i] = IBS[i] KS[i].
4.INTEGRITY ALGORITHM UIA2
Introduction
The integrity algorithm UIA2 computes a Message Authentication Code (MAC) on an input message under an integrity key IK. The message may be between 1 and 2^{32} bits in length.
For ease of implementation the algorithm is based on the same stream cipher (SNOW 3G) as is used by the confidentiality algorithm UEA2.
Inputs and Outputs
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

64

The number of bits to be ‘MAC’d

MESSAGE

LENGTH

Input bit stream

Table 3. UIA2 inputs
Parameter

Size (bits)

Comment

MACI

32

Message authentication code MACI[0]…MACI[31]

Table 4. UIA2 output
Components and Architecture
SNOW 3G
The integrity function uses SNOW 3G that is specified in [5]. SNOW 3G is a word oriented stream cipher and generates from the key and an initialisation variable five 32bitwords z_{1}, z_{2,} z_{3}, z_{4} and z_{5}.
MULx
MULx maps 128 bits to 64 bits. Let V and c be 64bit input values. Then MULx is defined:
If the leftmost (i.e. the most significant) bit of V equals 1, then
MULx(V, c) = (V <<_{64} 1) c,
else
MULx(V, c) = V <<_{64} 1.
MULxPOW
MULxPOW maps 128 bits and a positive integer i to 64 bit. Let V and c be 64bit input values, then MULxPOW(V, i, c) is recursively defined:
If i equals 0, then
MULxPOW(V, i, c) = V,
else
MULxPOW(V, i, c) = MULx(MULxPOW(V, i – 1, c), c).
MUL
MUL maps 192 bits to 64 bit. Let V, P and c be 64bit input values.
Then the 64bit output result of MUL(V, P, c) is computed as follows:

result = 0.

for i = 0 to 63 inclusive

if (P >>_{64} i) &_{64} 0x01 equals 0x01, then
result = result MULxPOW(V, i, c).
Initialisation
In this section we define how the keystream generator is initialised with the key and initialisation variables before the generation of keystream bits.
All variables have length 32 bits and are presented with the most significant bit on the left hand side and the least significant bit on the right hand side.

K_{3}

=

IK[0]



IK[1]



IK[2]



…



IK[31]



K_{2}

=

IK[32]



IK[33]



IK[34]



…



IK[63]



K_{1}

=

IK[64]



IK[65]



IK[66]



…



IK[95]



K_{0}

=

IK[96]



IK[97]



IK[98]



…



IK[127]


IV_{3}

=

COUNTI[0]  COUNTI[1]  COUNTI[2]  …  COUNTI[31]

IV_{2}

=

FRESH[0]  FRESH[1]  FRESH[2]  …  FRESH[31]

IV_{1}

=

DIRECTION[0] COUNTI[0]  COUNTI[1]  COUNTI[2]  …  COUNTI[31]

IV_{0}

=

FRESH[0]  FRESH[1]  …  FRESH[15]  FRESH[16] DIRECTION[0]  FRESH[17]  …  FRESH[31]

SNOW 3G is initialised as described in document [5].
Calculation
Set D = LENGTH / 64 + 1.
SNOW 3G is run as described in document [5] in order to produce 5 keystream words z_{1}, z_{2}, z_{3}, z_{4}, z_{5}.
Set P = z_{1}  z_{2}
and Q = z_{3}  z_{4}.
Let OTP[0], OTP[1], OTP[2], …, OTP[31] be bitvariables such that
z_{5} = OTP[0]  OTP[1] …  OTP[31]_{,}
i.e._{ }OTP[0] is the most and OTP[31] the least significant bit of z_{5}.
For 0 ≤ i ≤ D  3 set
M_{i}_{ }= MESSAGE[64i]  MESSAGE[64i+1] ... MESSAGE[64i+63].
Set
M_{D}_{2} = MESSAGE[64(D2)]  …  MESSAGE[LENGTH1]  0…0.
Let LENGTH[0], LENGTH[1], …, LENGTH[63] be the bits of the 64bit representation of LENGTH, where LENGTH[0] is the most and LENGTH[63] is the least significant bit.
Set M_{D}_{1} = LENGTH[0]  LENGTH[1]  …  LENGTH[63].
Compute the function Eval_M:

Set the 64bit variable EVAL = 0.

for i = 0 to D – 2 inclusive:

EVAL = Mul(EVAL M_{i}, P, 0x000000000000001b ).
Set EVAL = EVAL M_{D  1}
Now we multiply EVAL by Q:
EVAL = Mul(EVAL, Q, 0x000000000000001b).
Let EVAL = e_{0}  e_{1}  …  e_{63} with e_{0} the most and e_{63} the least significant bit.
For 0 ≤ i ≤ 31, set
MACI[i] = e_{i} OTP[i].
The bits e_{32}, …, e_{63} are discarded.
INFORMATIVE SECTION
This part of the document is purely informative and does not form part of the normative specification of the Confidentiality and Integrity algorithms.
Remarks about the mathematical background of some operations of the UIA2 Algorithm
The function EVAL_M
The first part (the function EVAL_M) of the calculations for the UIA2 algorithm corresponds to the evaluation of a polynomial at a secret point: From the bits and the length of MESSAGE a polynomial MGF(2^{64})[X] is defined. This polynomial is evaluated at the point P GF(2^{64}) defined by z_{1}z_{2}.
This can be seen as follows:
Consider the Galois Field GF(2^{64}) where elements of the field are represented as polynomials over GF(2) modulo the irreducible polynomial x^{64} + x^{4} + x^{3} + x + 1.
Variables consisting of 64 bits can be mapped to this field by interpreting the bits as the coefficients of the corresponding polynomial.
For example for 0 ≤ i ≤ D3 the variable
M_{i}_{ }= MESSAGE[64i]  MESSAGE[64i+1] ... MESSAGE[64i+62]  MESSAGE[64i+63] is interpreted as
MESSAGE[64i]x^{63}+ MESSAGE[64i+1]x^{62 }+ ... + MESSAGE[64i+62]x + MESSAGE[64i+63].
Construct the polynomial M of degree D1 in GF(2^{64})[X] as
M(X) = M_{0}X^{D}^{1} + M_{1}X^{D}^{2}+ … + M_{D}_{2}X + M_{D}_{1}.
Evaluate the polynomial M at the point P, i.e. compute
M(P) = M_{0}P^{D}^{1} + M_{1}P^{D}^{2} + … + M_{D}_{2}P + M_{D}_{1}= (…(M_{0}P + M_{1})P + M_{2})P + … + M_{D}_{2})P + M_{D}_{1}.
This is done in the function Eval_M in 1.14.
The function MUL(V, P, c)
The function MUL(V, P, c) (see 1.12.4) corresponds to a multiplication of V by P in GF(2^{64}). Here GF(2^{64}) is described as GF(2)() where is a root of the GF(2)[x] polynomial x^{64} + c_{0}x^{63}+ … + c_{62}x +c_{63 }and c = c_{0}  c_{1}  …  c_{63}.
Implementation options for some operations of the UIA2 Algorithm
The function MUL (see 1.12.4) can be implemented using table lookups. This might accelerate execution of the function EVAL_M, as for the evaluation of the polynomial only multiplication by a constant factor P is needed.
There are different possible sizes for the tables. Here we use 8 tables with 256 entries, but for example it is also possible to use 16 tables with 16 entries.
In order to execute MUL by tablelookups first Pre_Mul_P (see 2.1) is executed, which generates the tables. Then in MUL_P (see 2.2) the multiplication is performed by 8 tablelookups and an xor of the results.
Hence in 1.14 instead of EVAL = Mul(EVAL M_{i}, P, 0x1b ) we can use EVAL = Mul_P(EVAL M_{i}).
Procedure Pre_Mul_P
In order to be able to compute Mul_P (see 2.2) the procedure Pre_Mul_P is executed once before the first call of Mul_P.
Pre_Mul_P computes from the 64bit input P eight tables PM[0], PM[1], …, PM[7]. Each of these tables contains 256 entries PM[j][0], PM[j][1], …, PM[j][255] with 64 bits.
For 0 j 7 and 0 X 255 the value PM[j][X] corresponds to X P x^{8j}.
Let r be the 64bit value 0x000000000000001b.

The tables are computed as follows:
PM[0][0] = PM[1][0] = PM[2][0] = PM[3][0] = PM[4][0] = PM[5][0] = PM[6][0] = PM[7][0] = 0.

PM[0][1] = P.

for i = 1 to 63 inclusive:

PM[i >>_{8} 3][1 <<_{8} (i &_{8} 0x07)] = PM[(i – 1) >>_{8} 3][1 <<_{8} ((i – 1) &_{8} 0x07)] <<_{64} 1.

if the leftmost bit of PM[(i – 1) >>_{8} 3][1 << ((i – 1) &_{8} 0x07)] equals 1, then
PM[i >>_{8} 3][1 <<_{8} (i &_{8} 0x07)] = PM[i >>_{8} 3][1 << (i &_{8} 0x07)] r.

for i = 0 to 7 inclusive

for j = 1 to 7 inclusive

for k = 1 to (1 <<_{8} j) – 1 inclusive

PM[i][(1 <<_{8} j) + k] = PM[i][1 <<_{8} j] PM[i][k].
Function Mul_P
The function Mul_P maps a 64bit input X to a 64bit output.
Let X = X_{0}  X_{1}  X_{2}  X_{3}  X_{4} X_{5}  X_{6} X_{7}, with X_{0} the most and X_{7} the least significant byte.
Compute Mul_P(X) as
Mul_P(X) = PM[0][X_{7}] PM[1][X_{6}] PM[2][X_{5}] PM[3][X_{4}] PM[4][X_{3}]
PM[5][X_{2}] PM[6][X_{1}] PM[7][X_{0}].
Figures of the UEA2 and UIA2 Algorithms
COUNTC



BEARER  DIRECTION  0 ... 0



COUNTC



BEARER  DIRECTION  0 ... 0

IV_{3}



IV_{2}



IV_{1}



IV_{0}


Figure 1: UEA2 Keystream Generator
Figure 2: UIA2 Integrity function, part 1
Figure 3: UIA2 Integrity function, part 2

UEAII
Header File
/*
* f8.h
**/
#ifndef F8_H_
#define F8_H_
#include "SNOW_3G.h"
/* f8.
* Input key: 128 bit Confidentiality Key.
* Input count:32bit Count, Frame dependent input.
* Input bearer: 5bit Bearer identity (in the LSB side).
* Input dir:1 bit, direction of transmission.
* Input data: length number of bits, input bit stream.
* Input length: 32 bit Length, i.e., the number of bits to be encrypted or
* decrypted.
* Output data: Output bit stream. Assumes data is suitably memory
* allocated.
* Encrypts/decrypts blocks of data between 1 and 2^32 bits in length as
* defined in Section 3.
*/
void f8( u8 *key, u32 count, u32 bearer, u32 dir, u8 *data, u32 length );
#endif
Code
/*
* f8.c
**/
#include "f8.h"
#include
#include
#include
/* f8.
* Input key: 128 bit Confidentiality Key.
* Input count:32bit Count, Frame dependent input.
* Input bearer: 5bit Bearer identity (in the LSB side).
* Input dir:1 bit, direction of transmission.
* Input data: length number of bits, input bit stream.
* Input length: 32 bit Length, i.e., the number of bits to be encrypted or
* decrypted.
* Output data: Output bit stream. Assumes data is suitably memory
* allocated.
* Encrypts/decrypts blocks of data between 1 and 2^32 bits in length as
* defined in Section 3.
*/
void f8( u8 *key, u32 count, u32 bearer, u32 dir, u8 *data, u32 length )
{
u32 K[4],IV[4];
int n = ( length + 31 ) / 32;
int i=0;
u32 *KS;
/*Initialisation*/
/* Load the confidentiality key for SNOW 3G initialization as in section 3.4. */
for (i=0; i<4; i++)
K[3i] = (key[4*i] << 24) ^ (key[4*i+1] << 16) ^ (key[4*i+2] << 8) ^ (key[4*i+3]);
/* Prepare the initialization vector (IV) for SNOW 3G initialization as in section 3.4. */
IV[3] = count;
IV[2] = (bearer << 27)  ((dir & 0x1) << 26);
IV[1] = IV[3];
IV[0] = IV[2];
/* Run SNOW 3G algorithm to generate sequence of key stream bits KS*/
Initialize(K,IV);
KS = (u32 *)malloc(4*n);
GenerateKeystream(n,(u32*)KS);
/* ExclusiveOR the input data with keystream to generate the output bit stream */
for (i=0; i
{
data[4*i+0] ^= (u8) (KS[i] >> 24) & 0xff;
data[4*i+1] ^= (u8) (KS[i] >> 16) & 0xff;
data[4*i+2] ^= (u8) (KS[i] >> 8) & 0xff;
data[4*i+3] ^= (u8) (KS[i] ) & 0xff;
}
free(KS);
}
/* End of f8.c */
UIAII
Header File
/*
* f9.h
**/
#ifndef F9_H_
#define F9_H_
#include "SNOW_3G.h"
/* f9.
* Input key: 128 bit Integrity Key.
* Input count:32bit Count, Frame dependent input.
* Input fresh: 32bit Random number.
* Input dir:1 bit, direction of transmission (in the LSB).
* Input data: length number of bits, input bit stream.
* Input length: 64 bit Length, i.e., the number of bits to be MAC'd.
* Output : 32 bit block used as MAC
* Generates 32bit MAC using UIA2 algorithm as defined in Section 4.
*/
u8* f9( u8* key, u32 count, u32 fresh, u32 dir, u8 *data, u64 length);
#endif
Code
/*
* f9.c
**/
#include "f9.h"
#include
#include
#include
/* MUL64x.
* Input V: a 64bit input.
* Input c: a 64bit input.
* Output : a 64bit output.
* A 64bit memory is allocated which is to be freed by the calling
* function.
* See section 4.3.2 for details.
*/
u64 MUL64x(u64 V, u64 c)
{
if ( V & 0x8000000000000000 )
return (V << 1) ^ c;
else
return V << 1;
}
/* MUL64xPOW.
* Input V: a 64bit input.
* Input i: a positive integer.
* Input c: a 64bit input.
* Output : a 64bit output.
* A 64bit memory is allocated which is to be freed by the calling function.
* See section 4.3.3 for details.
*/
u64 MUL64xPOW(u64 V, u8 i, u64 c)
{
if ( i == 0)
return V;
else
return MUL64x( MUL64xPOW(V,i1,c) , c);
}
/* MUL64.
* Input V: a 64bit input.
* Input P: a 64bit input.
* Input c: a 64bit input.
* Output : a 64bit output.
* A 64bit memory is allocated which is to be freed by the calling
* function.
* See section 4.3.4 for details.
*/
u64 MUL64(u64 V, u64 P, u64 c)
{
u64 result = 0;
int i = 0;
for ( i=0; i<64; i++)
{
if( ( P>>i ) & 0x1 )
result ^= MUL64xPOW(V,i,c);
}
return result;
}
/* mask8bit.
* Input n: an integer in 17.
* Output : an 8 bit mask.
* Prepares an 8 bit mask with required number of 1 bits on the MSB side.
*/
u8 mask8bit(int n)
{
return 0xFF ^ ((1<<(8n))  1);
}
/* f9.
* Input key: 128 bit Integrity Key.
* Input count:32bit Count, Frame dependent input.
* Input fresh: 32bit Random number.
* Input dir:1 bit, direction of transmission (in the LSB).
* Input data: length number of bits, input bit stream.
* Input length: 64 bit Length, i.e., the number of bits to be MAC'd.
* Output : 32 bit block used as MAC
* Generates 32bit MAC using UIA2 algorithm as defined in Section 4.
*/
u8* f9( u8* key, u32 count, u32 fresh, u32 dir, u8 *data, u64 length)
{
u32 K[4],IV[4], z[5];
u32 i=0,D;
static u8 MAC_I[4] = {0,0,0,0}; /* static memory for the result */
u64 EVAL;
u64 V;
u64 P;
u64 Q;
u64 c;
u64 M_D_2;
int rem_bits = 0;
/* Load the Integrity Key for SNOW3G initialization as in section 4.4. */
for (i=0; i<4; i++)
K[3i] = (key[4*i] << 24) ^ (key[4*i+1] << 16) ^ (key[4*i+2] << 8) ^ (key[4*i+3]);
/* Prepare the Initialization Vector (IV) for SNOW3G initialization as in section 4.4. */
IV[3] = count;
IV[2] = fresh;
IV[1] = count ^ ( dir << 31 ) ;
IV[0] = fresh ^ (dir << 15);
z[0] = z[1] = z[2] = z[3] = z[4] = 0;
/* Run SNOW 3G to produce 5 keystream words z_1, z_2, z_3, z_4 and z_5. */
Initialize(K,IV);
GenerateKeystream(5,z);
P = (u64)z[0] << 32  (u64)z[1];
Q = (u64)z[2] << 32  (u64)z[3];
/* Calculation */
if ((length % 64) == 0)
D = (length>>6) + 1;
else
D = (length>>6) + 2;
EVAL = 0;
c = 0x1b;
/* for 0 <= i <= D3 */
for (i=0;i
{
V = EVAL ^ ( (u64)data[8*i ]<<56  (u64)data[8*i+1]<<48  (u64)data[8*i+2]<<40  (u64)data[8*i+3]<<32 
(u64)data[8*i+4]<<24  (u64)data[8*i+5]<<16  (u64)data[8*i+6]<< 8  (u64)data[8*i+7] );
EVAL = MUL64(V,P,c);
}
/* for D2 */
rem_bits = length % 64;
if (rem_bits == 0)
rem_bits = 64;
M_D_2 = 0;
i = 0;
while (rem_bits > 7)
{
M_D_2 = (u64)data[8*(D2)+i] << (8*(7i));
rem_bits = 8;
i++;
}
if (rem_bits > 0)
M_D_2 = (u64)(data[8*(D2)+i] & mask8bit(rem_bits)) << (8*(7i));
V = EVAL ^ M_D_2;
EVAL = MUL64(V,P,c);
/* for D1 */
EVAL ^= length;
/* Multiply by Q */
EVAL = MUL64(EVAL,Q,c);
for (i=0; i<4; i++)
MAC_I[i] = (mac32 >> (8*(3i))) & 0xff;
return MAC_I;
}
/* End of f9.c */
/**/