Algorithms	67

The stream cipher E0 is based on a direct design and uses a Bluetooth proprietary algorithm that has its roots in the so-called summation combiner stream cipher. This was a stream cipher that was proposed by Massey and Rueppel [3, 4] in the mid-1980s. Its strengths and weaknesses are well understood through the works of [5–7]. From that time to the time of writing, the most powerful attacks on this type of stream ciphers are the correlation attacks in combination with exhaustive search over a limited key space (this is sometimes also referred to as initial guessing). The original summation combiner design was modified to reduce the correlations that are used in the attacks by adding additional logic. In Section 4.1.2, we will describe this and its consequences in more detail. The works of Golic [7] and Hermelin and Nyberg [8] lead to the conclusion that a summation combiner type of stream cipher with a total state space of K bits (2K states) will provide only about K /2 bits in security when sufficient key stream data is available. As we will see later, more recent cryptanalysis shows that the E0 cipher is weaker than this. Therefore, the frequent rekeying in Bluetooth and the rather short generated key streams are essential for keeping the threat of (correlation) attacks at a safe distance.

4.2 SAFER+

The SAFER+ block cipher has its roots in the SAFER block cipher. The original SAFER cipher has been analyzed (see [9]), and apart from a correction in the original key scheduling, SAFER is still a safe algorithm, provided a sufficient number of rounds is used. SAFER is, however, a cipher working on 64-bit data blocks, which is too small for use in Bluetooth. SAFER+ uses a round construction similar to that of SAFER, consisting of pseudo-Hadamard transforms, substitution tables, and subkey insertion (see [1]). An important improvement in SAFER+ is the introduction of the so-called “Armenian Shuffle” permutation, which boosts the diffusion of single-bit modifications in the input data. In fact, the diffusion in SAFER+ is already very good after one round. This is a highly desirable property of any good block cipher. In [10], this property is proved along with other state-of-the-art cryptanalysis. For a recent summary of cryptanalytic results, see [11].

SAFER+ has two subsystems: the encryption subsystem and the key scheduling subsystem. It shares this setup with many other block cipher algorithms. Let us first have a look at key scheduling. See Figure 4.1. The task of key scheduling is to provide key material, called a round key, for each of the encryption rounds in the encryption subsystem. Each round key consists of two vectors of 16 octets. The key scheduling borrows ideas from the strengthened schedule of SAFER. See [9]. The last round key, K17, is a single vector of 16 octets that are

68	Bluetooth Security

K1		Select octets
		0,1,2, ..., 15

0 1 128-bit key grouped in 16 octets 15

Sum octets

bit by bit

mod 2

Cyclically rotate each octet by 3 bits

0		1		15		16

Cyclically rotate each octet by 3 bits

K2						Select octets
		+16						0		1	15 16
						1,2,3, ..., 16
		B2								Cyclically rotate each octet by 3 bits
K3
		+16				Select octets		0		1	15 16
						2,3,4, ..., 16,0
		B3
										Cyclically rotate each octet by 3 bits
K17
		+16				Select octets		0		1	15 16
						16,0,1,2, ..., 14
		B17

Figure 4.1 SAFER key scheduling.

“added” to the output of the last round. See Figure 4.2. Each of the 16-octet2 vectors Ki = (Ki[0]. Ki[1], . . ., Ki[15]), except K1, are offset by a bias Bi = (bi[0], bi[1], . . ., bi[15]), i = 2, 3, . . ., 17 using modulo 256 addition. The bias vectors are defined by

bi [ j ] =			( 4517 i + j + 1	mod 257)		mod 256		, for j = 0, 1,K, 15	(4.1)
			45		mod 257

2.We will here and in the following regard octets as being integer numbers 0, 1, . . ., 255 or as being eight-dimensional binary valued vectors, whichever is suitable in the context of usage. The binary vector representation corresponds to the radix-2 representation of the integer value of the octet; that is, the octet 131 is also written as 10000011.

Algorithms	69

The round keys are fed into SAFER+’s round mechanism where they are added into the round data. The addition is done by intertwined modulo 256 and XOR additions. See Figure 4.2. The SAFER+ uses two tables, referred to as E and L, that implement the mappings:

E ,L:

{0, 1,K, 255}→

{0, 1,K, 255}

(4.2)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

Only for A’r in round r = 3

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

A input [0, ..., 15]

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

+

K2r−1[0, ..., 15]

E L L E E L L E E L L E E L L E

+ + + + + + + + + + + + + + + +

PHT PHT PHT PHT PHT PHT PHT PHT

Permutation 8 11 12 15 2 1 6 5 10 9 14 13 0 7 4 3

PHT PHT PHT PHT PHT PHT PHT PHT

Permutation 8 11 12 15 2 1 6 5 10 9 14 13 0 7 4 3

PHT PHT PHT PHT PHT PHT PHT PHT

Permutation 8 11 12 15 2 1 6 5 10 9 14 13 0 7 4 3

PHT PHT PHT PHT PHT PHT PHT PHT

+ + + + + + + + + + + + + + + +

K2r[0, ..., 15]

Round r = 1, 2, ..., 8

Only after last round K17[0, ..., 15]

+Add octets modulo 256 PHT(x,y) (2x+y mod 256, x+y mod 256)

+XOR octets bit wise

Figure 4.2 One round of SAFER+ with Bluetooth adoptions. The permutation maps output 0 to input 8, output 1 to input 11, and so on.

70 Bluetooth Security

E :	x a	(	)	mod 256	(4.3)
		45x mod 257
L:	x a y such that x = E (y )				(4.4)

These two mappings introduce nonlinearity. Figure 4.2 also shows the modification of SAFER+ used in the Bluetooth Ar′ algorithm. Ar′ is SAFER+ with the modification that the original input to the algorithm is also added to the input of the third round. This makes Ar′ into a noninvertible mapping. This modification was made in order to prevent the algorithm from being used for encryption and avoid problems with export regulations.

4.2.1Authentication algorithm E1

We recall from Chapter 3 that algorithm E1 is the Bluetooth authentication algorithm. It is called a message authentication code (MAC) algorithm. The algorithm E1 is built around SAFER+, which for convenience is denoted by Ar and defined as

		r	{ }			{ }		{ }
		A :	0, 1	128 ×		0, 1	128→	0, 1	128			(4.5)
		(k, x ) a y = SAFER+ (key = k,input = x)										(4.6)
Now we define E1 in a few steps. First let								{ }		{ }
1	{ } { } { }						48		32		96
E : 0, 1		128	× 0, 1	128	×	0, 1		0, 1 ×		0, 1		(4.7)
							→
		(K ,RAND,address) a (SRES, ACO)										(4.8)

Here SRES and ACO are obtained from 16-octet vector hash (K, RAND, address, 6) as the first 4 octets and last 12 octets, respectively. Here hash is the function defined by

hash: {0, 1}128 × {0, 1}128× {0, 1}8× L×			{6, 12→}		({0, 1}8 )16				(4.9)
(K ,I 1,I 2,L ) a A′		~	16 [	A (K ,I 1)			I 1	(4.10)
	K , E (I 2,L ) +					16
r	(			r			])

where E(I2, L) is an expansion of the L octet vector I2 into a 16-octet (128 bits) vector, defined by

				Algorithms						71
		E :	{0, 1}8× L ×		{6, 12}→			({0, 1}8 )16		(4.11)
(	X	[	]	)	a	(	[		])	(4.12)
		0,K, L − 1 ,L					X i modL;i =		0,K, 15

The function hash is also used by the algorithm E3, where L = 12 is used. For E1, L is always 6 octets. The SAFER+ algorithm is used twice: once as defined, that is, Ar, and a second time slightly modified by adding the input

octets into the input of the third round. The latter is referred to as algorithm Ar′ .
The observant reader has of course noticed that the key K to A′ is not the same
as the key K that is used for Ar. The key				~		r
				K is derived from an offset of K. The
offset is defined as follows:
~	[0] = (K [0] + 233)mod 256,		~	[1] = (K [1]		229)
K			K
~	[2] = (K [2] + 233)mod 256,		~	[3] = (K [3]		193)
K			K
~	[4] = (K [4] + 179)mod 256,		~	[5] = (K [5]		167)
K			K
~	[6] = (K [6] + 149)mod 256,		~	[7] = (K [7]		131)
K			K				(4.13)
~	[0] = (K [0]	233),	~	[1]=	(K [1]+	229)mod 256
K			K
~	[2] = (K [2]	223),	~	[3]=	(K [3] + 193)mod 256
K			K
~	[4] = (K [4]	179),	~	[5]=	(K [5]+	167)mod 256
K			K
~	[6] = (K [6]	149),	~	[7] = (K [7] + 131)mod 256
K			K

Figure 4.3 summarizes the steps that form the algorithm E1. The figure also shows how the output of the hash function is split into two parts. The first 4 octets form the response SRES and the remaining 12 octets form the authentication offset ACO.

4.2.2Unit key algorithm E21

The algorithm E21 used for the unit key derivation is built around Ar′ . See Figure 4.4(a). Formally it is specified as

	21	{ }	{ }	48→	{ }
E		: 0, 1 128 ×	0, 1		0, 1 128		(4.14)
(RAND,address) a Ar′ (RAND[0..14]				(RAND[15]		6),Q )	(4.15)
where Q = i15= 0 address [i mod6]

Because Ar′ is used instead of the original SAFER+, algorithm E21 cannot be used directly as an invertible encryption algorithm.

72	Bluetooth Security

K	RAND	Address
		L
128
	Ar	E(xpand)
	128
Offset		16 octets XOR addition
~		16 octets mod 256 addition
K
	A’r

96	32
ACO	SRES

Figure 4.3 The structure of E1.

4.2.3Initial key algorithm E22

The algorithm E22 used for the initial key derivation is also built around Ar′ but differs slightly from E22. See Figure 4.4(b). Let N denote the pass-key length. Formally, E22 is specified as

E 22 : ({0, 1}8 )N ′ ×

{0, 1}128× {1, 2,K, 16}→

{0, 1}128 (4.16)

(PKEY ′, RAND, N ′) a Ar′ (X ,Y )

(4.17)

X =

i15= 0 PKEY '[i modN ′]

(4.18)

PKEY’

RAND

128

8x N’

E21

RAND

E22

Address

128

128

128

N’

48

4

(a)

(b)

Figure 4.4 Block diagrams of (a) E21, and (b) E22.