74	Bluetooth Security

the constraint key, the initial state is determined by 26 bits of the current clock value, BD_ADDR, and a 128-bit random EN_RAND. As explained in Section 3.6.3, one first determines a payload key by running E0 for 200 clock cycles. One can regard this as a means of mixing the initial state data. Of the 200 generated output symbols (bits), the last 128 bits are retained and subsequently loaded back into E0 as its initial state for the process of generating the key stream symbols that are used for encryption (alternatively, for decryption) of the outgoing (incoming) data.

For the sake of exposition, we first describe the construction of E0 and will return to a description of the initialization steps after we have more knowledge of the construction.

4.4 Ciphering algorithm E0

The core of E0 is built around four independent linear feedback registers and a finite state machine as a combining circuitry. The latter is needed to introduce sufficient nonlinearity to make it difficult to recompute the initial state from observing key stream data. In Chapter 7 we will come back to the trade-offs that are involved here when we discuss the strengths and weaknesses in the Bluetooth security system. The four linear feedback registers LFSRi, i = 1, 2, 3, 4 are each fully characterized by the following four feedback polynomials [12]:

LFSR1 :	f 1 (t ) = t 25		+ t 20	+ t 12	+ t 8	+ 1	(4.23)
LFSR 2 :	f	2 (t ) = t 31	+ t 24	+ t 16	+ t 12	+ 1	(4.24)
LFSR 3 :	f	3 (t ) = t 33	+ t 28	+ t 24	+ t 4	+ 1	(4.25)
LFSR 4 :	f 4 (t ) = t 39		+ t 36	+ t 28	+ t 4	+ 1	(4.26)

Note that the sum of the degrees of these four polynomials is 128. The output sequence X1 = (x10, x11, . . .) of register 1, say, when assuming that we clock the register infinitely long, can be expressed by the formal power series:

X 1 (t ) = ∑∞	x1it i
i = 0

From the theory of linear feedback registers we know that we can write

Algorithms			75
X 1	(t ) =	g 1 (t )
		f 1 (t )

for some polynomial g1(t) (with binary coefficients) of degree less than the degree of f1(t). See, for example, [12]. The polynomial division is carried out by using ordinary polynomial arithmetic but using modulo 2 arithmetic in the coefficients. It is the linear feedback circuit that implements this division operation using delay elements to hold the coefficients and XOR gates to do the modulo 2 operations. Each of the four polynomials is a so-called maximum length polynomial, which means that the periods of the output sequences of LFSRs have periods 2 degreef i − 1, i = 1, 2, 3, 4 [12]. That is, we have

period X	1	:P	= 2 25	− 1	(4.27)
		1
period X 2		:P2	= 2 31	− 1	(4.28)
period X 3		:P3	= 2 33	− 1	(4.29)
period X 4		:P4	= 2 39	− 1	(4.30)

As we will see later, the polynomials are in fact maximum length windmill polynomials (see Section 4.5). The windmill property can be exploited in a hardware or software realization of the LFSR.

The four sequences X1, . . ., X4 are fed symbol by symbol into a so-called summation combiner which adds the four input symbols together as if they were natural numbers, adds the result to a number ct, depending on the summation combiner’s state, and obtains a sum st, t = 0, 1, . . . . Formally we have

st = x1t + x 2t + x 3t + x 4t + ct {0, 1,K, 7}

because ct takes on only the values 0, 1, 2, 3. The output symbol zt is the binary result obtained by setting

z t = st mod 2 = x1t x 2t x3t x 4t (ct mod 2)

The new value ct + 1 is obtained by rewriting3 first the result of the computation

3.The Bluetooth core specification defines the computation of the new state in a different manner using the finite field representation of the values of ct. The manner defined here is equivalent to the one in the core specification but avoids the use of finite fields.

76	Bluetooth Security
		st
	ut +1	=
		2

as a binary vector ut+1 (of dimension 2) and then setting

ct +1	c	0t +1		= ut +1	1
	=
	c1t +1				0

0		1	1
ct			ct −1	(4.31)
1		1	0

(computing modulo 2 in the coefficients), and, finally, defining the mapping:

↓ :ct = 2c1t + cot

(4.32)

A close inspection shows that (4.31) defines a linear infinite impulse response (IIR) filter that scrambles the state variables. We will later see that the IIR filter lowers the correlation factor that is an important parameter in the socalled correlation attack. In Figure 4.6 the core of E0 is shown schematically.

Missing in Figure 4.6 are the initialization parts which will be described in the next sections. Before we discuss the initialization, we want to point out that the sequence V = (v0, v1, . . .) with

vt = x1t x 2t

x3t

x 4 t

11

2

10

Ct-1

Ct

2

2

2

2

Ct

Ut+1

X1t

LFSR1

Σ

St

ZL

X2t

Xit

LFSR2

X3t

LFSR3

X4t

LFSR4

Figure 4.6 The schematics of the E0 core engine.

Algorithms	77

has period P = (P1P2P3P4)/7 and not P1P2P3P4 due to the fact that the periods P3 and P4 have 7 as their greatest common divisor. Hence, if we assume that none

of the LFSRs is initialized with an all zero state, there are 7 cycles of length P ≈ 2125.2 [13].

4.4.1Initialization

The initialization of E0 prior to the payload key computation is rather involved. The key stream generator needs to be loaded with the initial values for the four LFSRs (altogether 128 bits) and the 4 bits that specify the values of c0 and c-1. This 132-bit initial value is derived from four inputs: the constraint key K C′ , a BD_ADDR value, and a clock CLK value by using the key stream generator itself. The length of K C′ is 128 bits. With the generator, 200 stream cipher bits are generated, of which the last 128 bits are fed back into the key stream generator as the initial values of the four LFSRs. The values of c0 and c-1 are kept. The details of the initialization are as follows:

1.Shift in the three inputs K C′ , the BD_ADDR address, the clock CLK bits, and the 6-bit (decimal) constant 113 (208 bits total).

a.Open all switches shown in Figure 4.7.

b.Arrange input bits as shown in Figure 4.7. ADR[i] denotes the bytes of BD_ADDR, and similarly CLK[i] denotes the relevant bytes of the clock.

c.Set the initial states of the LFSRs to zero (t = 0).

d.Start to shift in the input bits.

				49 bits										Close after 25
														8	12	20
		ADR[2]C[1]K’C[12]K’C[8]K’C[4]K’C[0]CL24																				X1t
														Close after 31		24
				55 bits
															12	16	24					X2t
ADR[3]ADR[0]K’C[13]K’C[9]K’C[5]K’C[1]CL[0]L001
														Close after 33		24
				49 bits													28
														4		24						X3t
ADR[4]CL[2]K’C[14]K’C[10]K’C[6]K’C[2]CL25
														Close after 39			32
				55 bits												28
														4			36					X4t
ADR[5]ADR[1]K’C[15]K’C[11]K’C[7]K’C[3]CL[0]U111

32

CL[0]L=CL3, ..., CL0

CL[0]U=CL7, ..., CL4

Figure 4.7 First loading of the four LFSRs.

78	Bluetooth Security

e.Close feedback switch of LFSR1 after 25 clock instants, that of LFSR2 after 31 clock instants, that of LFSR3 after 33 clock instants, and that of LFSR4 after 39 clock instants.

f.At t = 39, set bits c39 = 0 and c38 = 0.

g.Continue to shift in remaining inputs bits. Note: When finished,

LFSR1 has effectively clocked 30 times with feedback closed. LFSR2 24 times, LFSR3 22 times, and LFSR4 16 times.

2.Continue to clock until 200 symbols have been produced (to mix initial data).

3.Keep ct and ct−1 and load the last 128 generated bits into the four LFSRs.

In Figure 4.7 all bits are shifted in starting always with the least significant bit (LSB)4 first; for example, from the third byte of the address, ADR[2], first ADR16 is entered, followed by ADR17, and so on. Finally, the last generated 128 bits denoted here conveniently by Z[0], . . ., Z[15] are fed back into the feedback registers as shown in Figure 4.8.

The incoming and outgoing payloads are treated separately and payload keys are generated for each of them. Figure 2.4 shows the timing of the encryption and decryption processes.

				Z[12]0
	Z[0]	Z[4]	Z[8]
			24	X1t
	Z [1]	Z[5]	Z[9]	Z[12]7-1
			24	2
				X t
Z [2]	Z[6]	Z[10]	Z[13]	Z[15]0
			32	3
				X t
Z[3]	Z[7]	Z[11]	Z[14]	Z[15]7-1
			32	4
				X t

Figure 4.8 Second loading of the LFSRs with the payload key.

4.The LSB of X[i] corresponds to bit 8i of the sequence X, and the most significant bit (MSB) of X[i] to 8i + 7.