BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 161 of 1082
`
`Base-band Specification
`
`14.3.2 Encryption modes
`
`ifa slave has a semi-permanent link key (ie. a combination key or a unit key),
`it can only accept encryption on slots individually addressed to itself (and, of
`course, in the reverse direction to the master). in particular, it will assume that
`broadcast messages are not encrypted. The possible traffic modes are
`described in
`14.2. When an entry in the table refers to a link key. it
`means that the encryptionidecryption engine uses the encryption key derived
`from that link key.
`
`Broadcast traffic
`
`Individually addressed traffic
`
`No encryption
`
`No encryption
`
`No encryption
`
`Encryption. Semi-permanent link key
`
`Tabie 14.2.’ Possibie traffic modes for a slave using a semi-pennanentiink key
`
`if the slave has received a master key, there are three possible combinations
`as defined in Tania 34.3 on page tat. in this case, all units in the piconet uses
`a common link key, K,,mm,,.. Since the master uses encryption keys derived
`
`from this link key for all secure trafflc on the piconet, it is possible to avoid
`ambiguity in the participating slaves on which encryption key to use. Also in
`this case the default mode is that broadcast messages are not encrypted. A
`specific LM-command is required to activate encryption — both for broadcast
`and for individually addressed traffic.
`
`Broadcast traffic
`
`Individually addressed traffic
`
`No encryption
`
`N0 9"C"YPti0"
`
`No encryption
`
`Encryption. KtN(i'Si{’i“
`
`Encryption. K
`
`J‘N|'.'i.§'I£F"
`
`Encryption. K
`
`]?J‘05f|’.’l"
`
`Tabie 14.3: Possible encryption modes for a siave in possession of a master key:
`
`The master can issue an LM-command to the slaves telling them to fall back to
`their previous semi-permanent link key. Then, regardless of the previous mode
`they were in, they will end up in the first row of “facts 14.2 on page 16?; i.e. no
`encryption.
`
`14.3.3 Encryption concept
`
`For the encryption routine. a stream cipher algorithm will be used in which
`ciphering bits are bit-wise modulo-2 added to the data stream to be sent over
`the air interface. The payload is ciphered after the CRC bits are appended. but.
`prior to the FEC encoding.
`
`Blustooth Security
`
`29 November 1999
`
`AFFLT02933B9
`
`Samsung Ex. 1119 p. 161
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 8
`
`page 162 of €882
`
`Baseband Specification
`
`Each packet payload is ciphered separately. The cipher algorithm ED uses the
`
`master Bluetooth address, 26 bits of the master realtirne clock (CLK 254) and
`
`the encryption key K(_. as input, see Figs..=n=.= 14.5 on page ‘$52 (where it is
`
`assumed that unit A is the master).
`
`The encryption key KC is derived from the current link key, COF, and a random
`
`number, EN_RAN DA (see Secison 14.5.4 on page t'E"?). The random number is
`
`issued by the master before entering encryption mode. Note that EN_RAN DA
`is publicly known since it is transmitted as plain text over the air.
`
`Within the E0 algorithm, the encryption key K(. is modified into another key
`
`denoted K} . The maximum effective size of this key is factory preset and
`may be set to any multiple of eight between one and sixteen (8-128 bits). The
`procedure for denying the key is described in Section M.3.£':3 on page 155.
`
`The real-time clock is incremented for each slot. The Er, algorithm is re-initia|-
`
`ized at the start of each new packet (i.e. for Master-to-Slave as well as for
`Slave-to-Master transmission). By using CLK264 at least one bit is changed
`between two transmissions. Thus, a new keystream is generated after each re-
`initialization. For packets covering more than a single slot, the Bluetooth clock
`as found in the first slot is being used for the entire packet.
`
`The encryption algorithm Eu generates a binary keystream, Kt.,P,,t,,.. which is
`modulo-2 added to the data to be encrypted. The cipher is symmetric; decryp-
`tion is performed in exactly the same way using the same key as used for
`encryption.
`
`UNIT A {master}
`
`EO
`
`K _
`
`|
`
`Figure 14.5: Funclionai description of the encryption procedure
`
`29 November 1999
`
`Bluetooth Security
`
`AFFLT0293390
`
`Samsung Ex. 1119 p. 162
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 163 of 1082
`
`Base-band Specification
`
`14.3.4 Encryption algorithm
`
`The system uses linear feedback shift registers (LFSRS) whose output is com-
`bined by a simple finite state machine (called the summation combiner) with 16
`states. The output of this state machine is the key stream sequence, or, during
`initialization phase, the randomized initial start value. The algorithm is pre-
`
`sented with an encryption key Kw an 48-bit Bluetooth address, the master
`
`clock bits CLK254, and a 128-bit RAND value. Figure 14.5 on page 163 shows
`the setup.
`
`There are four LFSRs (LFSR1,...,LFSR4) of lengths L] = 25, L2 = 31, L3 = 33,
`
`and, L4 = 39, with feedback polynomials as specified in Tania 14.4 on page
`
`164. The total length of the registers is 128. These polynomials are all primi-
`tive. The Hamming weight of all the feedback polynomials is chosen to be five
`— a reasonable trade-off between reducing the number of required XOR gates
`in the hardware realization and obtaining good statistical properties of the gen-
`erated sequences.
`
`. . §9.”.‘f'??5‘.°.'! .‘§9.'E‘.“1*5‘."i'.‘:?.9!‘F_ _
`
`E
`
`Encryption Stream 2,
`
`inan
`Eto>
`
`E2
`
`.7:.
`
`Figure 14.6: Concept of the encryption engine.
`
`Blustooih Security
`
`29 November 1999
`
`AFFLT0293391
`
`Samsung Ex. 1119 p. 163
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 8
`
`page 164 of €882
`
`Baseband Specification
`
`Bluetooth.
`
`feedback f,(r)
`
`:3-‘+:1"+i'3+i"+1
`
`i-‘l+i3*l+r““+i'1+I
`
`r33+i33+:3*+i'l+1
`
`i39+i35+r33+i4+1
`
`Table 14.4: The four primitive feedback poiynomiais.
`
`Let xi denote the it“ symbol of LSFRi. From the four-tuple xi, ...,x;l we derive
`
`the value _v, as
`
`(E0 26}
`
`where the sum is over the integers. Thus y, can take the values 0,1.2,3, or 4.
`
`The output of the summation generator is now given by the following equations
`
`2, = A',1@.r,3®.\',3®.\‘f®c'PE {(1, 1},
`
`5,4 = {s}. 1.55% 1) = ['v‘:c"Je {0, 1,2,3}.
`
`:1
`
`cl,
`
`,r.
`= {c‘,',1,c°_ I} = S“ |®1"1[c',I@T3[c,_]|,
`
`(no 27}
`
`(1-.028}
`
`(15029)
`
`where T,[.] and T3[.| are two different linear bijections over GF(4). Suppose
`
`GF(4) is generated by the irreducible polynomial x3 -1-
`
`.1‘ + I
`
`, and let 0: be a zero
`
`of this polynomial in GF(4). The mappings T1 and T2 are now defined as
`
`T]: GF{4) —> GF(4)
`
`.r |—>x
`
`T3: GF(4) —> GF(4)
`
`.r |—>(u l
`
`l)x.
`
`We can write the elements of GF(4) as binary vectors. This is summarized in
`"table ‘s/-1.5.
`
`Since the mappings are linear. we can realize them using XOR gates; i.e.
`
`29 November 1999
`
`Biuetooth Security
`
`AFFLT0293392
`
`Samsung Ex. 1119 p. 164
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 165 of 1082
`
`Base-band Specification
`
`Bluetooth.
`
`Table 14.5: The mappings T1 and T3.
`
`T13
`
`T3:
`
`(xi:-‘firgil i"(—"1sx[})-
`
`(II, In} |—)(.‘ru, I163 Jr“).
`
`14.3.4.1 The ogeration of the cigher
`
`page "185 gives an overview of the operation in time. The
`.3-‘figure '34.?‘
`encryption algorithm shall run through the initialization phase before the start of
`transmitting or receiving a new packet. Thus, for multislot packets the cipher is
`initialized using the ciock value of the first slot in the multislot sequence.
`
`Master—> Stave
`
`Steve —> Master
`
`Init
`
`Encrypt;’Decrypt
`
`mat
`
`Encryptz‘Decrypt
`
`an
`
`clock cycles (time)
`
`Figure 14.17.‘ Overview of the operation of the encryption engine. Between each start of a packet
`(TX or RX). the LFSRS are re-initiaiized.
`
`14.3.5 LFSR initialization
`
`The key stream generator needs to be loaded with an initial value for the four
`
`LFSRs (in total 128 bits) and the 4 bits that specify the values of cfland c 1.
`
`The 132 bit initial value is derived from four inputs by using the key stream gen-
`erator itself. The input parameters are the key Kr, a 128-bit random number
`
`RAND, a 48-bit Bluetooth address, and the 26 master clock bits CLK254.
`
`The effective length of the encryption key can vary between 8 and 128 bits.
`Note that the actual key length as obtained from E3 is 128 bits. Then, within 1:“ ,
`
`the key length is reduced by a moduto operation between KC and a polynomial
`
`of desired degree. After reduction, the result is encoded with a block code in
`
`Bluetooth Security
`
`29 November 1999
`
`AFFLT0293393
`
`Samsung Ex. 1119 p. 165
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 8
`
`page 166 of €882
`
`Baseband Specification
`
`Bluetooth-
`
`order to distribute the starting states more uniformly. The operation is defined
`in (E0 30).
`
`When the encryption key has been created the LFSRs are loaded with their ini-
`tial values. Then, 200 stream cipher bits are created by operating the genera-
`tor. Of these bits, the last 128 are fed back into the key stream generator as an
`
`initial value of the four LFSRs. The values of C! and c,
`
`, are kept. From this
`
`point on, when clocked the generator produces the encryption (decryption)
`sequence which is bitwise XORed to the transmitted (received) payload data.
`
`In the following, we will denote octet I of a binary sequence X by the notation
`X] I] . We define bit 0 of X to be the LSB. Then, the LSB of X151 corresponds to
`
`hit 8:‘ of the sequence X, the MSB ofX1r] is bit Sil 7 ofX. Forinstance, bit 24
`of the Bluetooth address is the LS8 of ADR[3].
`
`The details of the initialization are as follows:
`
`1.
`
`Create the encryption key to use from the 128-bit secret key K(. and
`the 128-bit publicly known EN_RAND. Let L,
`I 3 L 3 I6, be the
`effective key length in number of octets. The resulting encryption key
`will be denoted K‘._«_-:
`
`K‘.-{.0 = ggM(1')(K{-(3') mod g“("’(x)),
`
`(1~:Q3o)
`
`where deg-,(g‘,"’(;l-}} = 8L and deg(g‘;"’[.r}} g [28 — SL. The polynomials
`are defined in Tehie 14.6.
`
`Shift in the 3 inputs K}-, the Bluetooth address, the clock, and the six-
`bit constant 111001 into the LFSRs. In total 208 bits are shifted in.
`
`a) Open all switches shown in Figure "M8 on page 158;
`
`b) Arrange inputs hits as shown in i"-lgcrte 14.8; Set the content of all
`shift register elements to zero. Set r = I).
`
`c) Start shifting bits into the LFSRs. The rightmost bit at each level of
`i:'E§_.‘;t.i.?‘€‘ 14.8 is the first bit to enter the corresponding LFSR.
`
`d) When the first input bit at level i reaches the rightmost position of
`LFSRi, close the switch of this LFSR.
`
`e) At r = 39 (when the switch of LFSR4 is closed), reset both blend
`registers «-3., = c3.,_1 = 0; Up to this point, the content of c, and
`c,
`1 has been of no concern. However, from this moment forward
`their content will be used in computing the output sequence.
`
`f) From now on output symbols are generated. The remaining input
`bits are oontinuously shifted into their corresponding shift register.
`When the last bit has been shifted in, the shift register is clocked
`with input = 0;
`
`Note: When finished, LFSR1 has effectively clocked 30 times
`with feedback closed, LFSR2 has clocked 24 times. LFSR3 has
`
`29 November 1999
`
`Bluetooth Security
`
`AFFLT0293394
`
`Samsung Ex. 1119 p. 166
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 187 of 1032
`
`Baseband Speolficallon
`
`clocked 22 times, and LFSR4 has effectively clocked 16 times
`with feedback closed.
`
`To mix initial data, continue to clock until 200 symbols have been
`produced with all switches closed (r = 239);
`
`. make a parallel load of the last 128
`Keep blend registers a, and c, _ ,
`generated bits into the LFSRS according to Figure ‘$4.9 at r = 240;
`
`After the parallel load in item 4, the blend register contents will be updated for
`each subsequent clock.
`:
`{Ll
`[Li
`8|
`32
`00227530 aizlfidii Cf923b9b bf6l'_'hDBf
`
`L
`
`den;
`[3]
`
`00000000 00000000 00000000 000001111
`
`deg
`[119]
`
`[16]
`
`[241
`
`[32]
`
`I40)
`
`E43]
`
`[56]
`
`[54]
`
`l?2l
`
`[so]
`
`[39]
`
`oooooooo ooonoono oooooooo 00010035
`
`cuooooao oonooooo oooooooo otoooodb
`
`00000000 oooooooo 00000001 ooooooat
`
`oooooouo oooooooo 00000100 oooaooze
`
`00000000 00000000 00010000 00000291
`
`00000000 00000000 01000000 00000095
`
`00000000 00000001 oooooooo oooooo1b
`
`00000000 00000100 oooooooo oooooeoe
`
`00000000 00010000 00000090 00000215
`
`00000000 01000000 oooooooo O000013b
`
`00000001 oonooooo oaoooooo ooooooed
`
`oooooloo oacooooo ouoooono oooooded
`
`00010000 oooooooo oooooooo 00000145
`
`01000000 00000000 00000000 00000097
`
`[1121
`
`[1041
`
`[96]
`
`[es]
`
`[71]
`
`[71]
`
`E63]
`
`[491
`
`E42]
`
`[35]
`
`[23]
`
`I21}
`
`:14}
`
`[71
`
`0O01e3fS 3d7659b3 ?fl3E2E8 ctrserefi
`
`Uoooolbe EG6c6c3a b1030A5a 1915aosb
`
`00000001 6abB9969 delTd6Tf d3736ad9
`
`oooooooo 01530532 91da5Dec 55715247
`
`00000000 00002c93 szaascco 54468311
`
`00000000 000000133 E7EffCC2 79E3ul073
`
`oooooooo ooonoooo a1ah815b c7ecso25
`
`oooooooo oooooooo 0002c980 lidshodd
`
`00000000 00000000 onooosae 2dE9AIbb
`
`oooooooo oooooooo oooooooc a76024d7
`
`00000000 oooooooo oooooooo lc9c26b9
`
`ouoooooo oooooono oooooooo 0O26d9e3
`
`oaoooona nuonaooo ouoooooo oooo4317
`
`00000000 00000000 00000000 00000039
`
`[123]
`
`1 00000000 00000000 00000000 00000000
`
`00000000 00000000 00000000 00000001
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`Table 14.6: Polynomials used when creating K}.
`All polynomials are in hexadeolmal notation. The l_SB is in the rlghtinosfposltlon.
`
`In Figure ta-3.8, all bits are shifted into the LFSRS. starting with the least signifi-
`cant bit (LSB). For instance, from the third octet of the address. ADR[2], first
`ADR15 is entered, followed by ADR17, etc. Furthermore, CLO corresponds to
`
`CLK1,..., CL25 corresponds to CLK25.
`
`Note that the output symbols .1-j,:' = I,
`
`4 are taken from the positions 24, 24,
`
`32, and 32 for LFSR1, LFSR2,LFSR3, and LFSR4, respectively (counting the
`leftmost position as number 1).
`
`Blueloolh Security
`
`29 November 1999
`
`AFFLT0293395
`
`Samsung Ex. 1119 p. 167
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 8
`
`page 158 of €882
`
`Baseband Specification
`
`Bluetooth.
`
`AD|t[-t[t‘l_[1]I\Lc‘[l4]1(c'[!i.I|Kc'[fi]Kt-‘[2] £1.25
`
`AJJll]:"| .-\l)R[l| Kc'[]i] Kc'[l I |Ki:'[‘.'| K4213]
`
`(.‘.|.[I'.I]_]
`
`I
`
`I
`
`‘ =1’
`
`Figure 14.8: Arranging the input to the i_FSRs.
`
`In Figure 14.9, the 128 binary output symbols Z0,..., Z127 are arranged in octets
`denoted Z[O],.... Z[15]. The LSB of Z[0] corresponds to the first of these sym-
`bols, the MSB of Z[15] is the latest output from the generator. These bits shall
`be loaded into the LFSRs according to the figure. It is a parallel load and no
`update of the blend registers is done. The first output symbol is generated at
`the same time. The octets are written into the registers with the LS8 in the left-
`most position (i.e. the opposite of before). For example, 224 is loaded into posi-
`
`tion 1 of LFSR4.
`
`z[4]
`
`PET
`
`In
`
`::[5]
`
`-vi’
`
`z[m]
`
`.7
`z[3]
`
`z[9]
`
`-=7
`z[13]
`
`z[1]
`
`|
`
`-T
`”‘
`z[2]
`
`Z[6]
`
`Figure 14.9.’ Distribution of the 128 test generated output symbois within the LFSRS.
`
`14.3.6 Key stream sequence
`
`When the initialization is finished, the output from the summation combiner is
`used for encryptionidecryption. The first bit to use is the one produced at the
`
`parallel load, i.e. at r = 240. The circuit is run for the entire length of the current
`payload. Then, before the reverse direction is started. the entire initialization
`process is repeated with updated values on the input parameters.
`
`29 November 1999
`
`Bluetooth Security
`
`AFFLT0293396
`
`Samsung Ex. 1119 p. 168
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 169 of 1082
`
`Base-band Specification
`
`Sample data of the encryption output sequence can be found in “.&\pper‘.déx l‘v""'
`on page
`Encryption Sample Data. A necessary, but not sufficient, condi-
`tion for all Bluetooth-compliant implementations is to produce these encryption
`streams for identical initialization values.
`
`14.4 AUTHENTICATION
`
`The entity authentication used in Bluetooth uses a challenge-response scheme
`in which a claimant's knowledge of a secret key is checked through a 2-move
`protocol using symmetric secret keys. The latter implies that a correct claimant!
`verifier pair share the same secret key. for example K. In the challenge-
`response scheme the verifier challenges the claimant to authenticate a random
`input (the challenge), denoted by AU_RANDA, with an authentication oode,
`
`denoted by E] , and return the result SRES to the verifier, see
`
`14.30 on
`
`page ‘$59. This figure shows also that in Bluetooth the input to E1 consists of
`
`the tuple AU_RAN DA and the Bluetooth device address (BD_ADDR) of the
`claimant. The use of this address prevents a simple reflection attack‘. The
`secret K shared by units A and B is the current link key.
`
`Verifier (Unit A}
`
`Claimant (Unit B)
`
`AU R/‘NBA
`
`AU RAND“
`
`AU RANDA
`
`BD ADDRB
`
`Link key
`
`Figure 14.10: Chaiienge-response for the Biuetooth.
`
`The challenge-response scheme for symmetric keys used in the Bluetooth is
`depicted in i3'§g=..=r'e 14.1? on page ’§‘}’tJ.
`
`1. The reflection attack actually forms no threat in Bluetooth because all service requests are
`dealt with on a FIFO bases. When pre-emption is introduced, this attack is potentially dan-
`gerous.
`
`Bluetooth Security
`
`29 November 1999
`
`AFFLT0293397
`
`Samsung Ex. 1119 p. 169
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 8
`
`page 170 of €882
`
`Baseband Specification
`
`Bluetooth-
`
`Verifier
`(User Al
`
`Claimant
`{Uscr B. with identity {DB}
`
`SRES — Eikcy. IDB. RAND]
`
`SRES' = Eikuy. IDB, RAND":
`
`Check: SRES‘ — SRES
`
`Figure 14. ‘ii: Chaiienge-response for symmetric key systems.
`
`In the Bluetooth. the verifier is not necessarily the master. The application indi-
`cates who has to be authenticated by whom. Certain appiications only require
`a one-way authentication. However, in some peer-to-peer communications.
`one might prefer a mutual authentication in which each unit is subsequently the
`challenger (verifier) in two authentication procedures. The LM coordinates the
`indicated authentication preferences by the application to determine in which
`direction(s) the authentication(s) has to take place. For mutual authentication
`with the units of i~"tg-are 14.18 on page ‘Z59, after unit A has successfully
`authenticated unit B, unit B could authenticate unit A by Sending a AU_RAND3
`
`(different from the AU_RAN DA that unit A issued) to unit A, and deriving the
`
`SRES and SRES‘ from the new AU_RANDB, the address of unit A, and the link
`
`key KAB.
`
`If an authentication is successful the value of ACO as produced by E, should
`be retained.
`
`14.4.1 Repeated attempts
`
`When the authentication attempt faiis, a certain waiting interval must pass
`before a new authentication attempt can be made. For each subsequent
`authentication failure with the same Bluetooth address, the waiting interval
`shall be increased exponentially. That is. after each failure, the waiting interval
`before a new attempt can be made, for example. twice as long as the waiting
`interval prior to the previous attempt1. The waiting interval shalt be limited to a
`maximum. The maximum waiting interval depends on the implementation. The
`waiting time shall exponentially decrease to a minimum when no new failed
`attempts are being made during a certain time period. This procedure prevents
`an intruder to repeat the authentication procedure with a large number of differ-
`ent keys.
`
`1. An other appropriate value larger than 1 may be used.
`
`1?0
`
`29 November 1999
`
`Bluetooth Security
`
`AFFLT029339B
`
`Samsung Ex. 1119 p. 170
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 171 of 1082
`
`Base-band Specification
`
`To make the system somewhat less vulnerable to denial-of-service attacks, the
`Bluetooth units should keep a list of individual waiting intervais for each unit it
`has established contact with. Clearly, the size of this list must be restricted only
`to contain the N units with which the most recent contact has been made. The
`
`number N can vary for different units depending on available memory size and
`user environment.
`
`14.5 THE AUTHENTICATION AND KEY-GENERATING
`
`FUNCTIONS
`
`This section describes the algorithmic means for supporting the Bluetooth
`security requirements on authentication and key generation.
`
`14.5.1 The authentication function E1
`
`The authentication function E] proposed for the Bluetooth is a computationally
`
`secure authentication code, or often called a MAC. E, uses the encryption
`
`function called SAFER+. The atgorithm is an enhanced version‘ of an existing
`64-bit block cipher SAFER-SK128, and it is freely available. In the sequel the
`
`block cipher will be denoted as the function A, which maps under a 128-bit key.
`
`a 128-bit input to a 128-bit output, i.e.
`
`123
`
`123
`‘
`><{0,[} —){0,l}
`A,.. {0,l}
`(k x x] i—> r.
`
`123
`
`(E031)
`
`The details of A, are given in the next section. The function E:
`
`is constructed
`
`using A,. as follows
`
`E :
`.i
`
`0‘ I
`
`133
`
`}
`
`0,
`
`I
`
`12:4
`
`33
`43
`}><{
`i—>l
`><l
`l
`><{
`(K, RAND, address) l—>(SRES, ACO),
`
`0’ I
`
`0‘ I
`
`0,
`
`9:5
`
`I
`
`}
`
`(mm
`
`where SRES = Hr:s:'1[K, RAND,addrcss, 6)[U,
`function defined asz.
`
`3], where Hash is a keyed hash
`
`Hasi:r:{0, I }'2“x to. llmx in. 1}“""‘x is, 12} —> {(1.
`
`I :33“
`
`(K. I], «'3. L) i—>.4‘.-tlif]. [E02, L) +1‘, <A,.U<. Il)<+3u,!l)1),
`
`and where
`
`1. It is presently one of the contenders for the Advanced Encryption Standard (AE8) submitted
`by Cylinlc, Corp. Sunnyvale, USA
`
`2. The operator +15 denotes bytewise addition mod 256 of the 16 octets. and the operator 69,5
`denotes bytewise XORing of the 16 octets.
`
`Bluetooth Security
`
`29 November 1999
`
`AFFLT0293399
`
`Samsung Ex. 1119 p. 171
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 8
`
`page 172 of €882
`
`Baseband Specification
`
`Eziu,1}*""‘x{6,12_:--+{u,1}*"“°
`
`(X[0,....L l],L) |—>(X[i(modL-)] fori=0...l5),
`
`Bluetooth.
`
`(17-Q 34}
`
`is an expansion of the L octet word X into a 128-bit word. Thus we see that we
`
`have to evaluate the function A, twice for each evaluation of El . The key I? for
`
`the second use of .4, (actually A',.) is offseted from K as follows‘
`
`K10] =u<[0] l 233) mod 256, K[l]=K[l]Ei-D229,
`
`R12] =(K[2] : 223)
`
`rnod256, K[3]=K[3]EB 193,
`
`iq41=(K[4]+179) mod256, K[5]=K|5]®l6'i,
`
`R16] =(K[6] l 149) mod 256, K[7]=K[?]EBl3l,
`
`.?<[s]=K[8]e233,
`
`iC[9]=(K[9] : 229) mod 256,
`
`icnoi =1<[:o]@223,
`
`k[n1=u<[111+193)mod256,
`
`k[12]=K[z2]ea179.
`
`i<[13]=u<[13] u 16?) mod 256,
`
`i<[I41=K[I4is) I49.
`
`f<[15]=(K[15] u 131) n1od256.
`
`A data flowchart of the computation of El
`
`is depicted in Figure ‘$4.12 on page
`
`'3 7'3. E,
`
`is also used to deliver the parameter ACO (Authenticated Ciphering
`
`Offset) that is used in the generation of the ciphering key by E_,_ , see equations
`
`EEG 23} and {EC} 43}. The value of ACO is formed by the octets 4 through 15 of
`the output of the hash function defined in (EC? 33'}. i.e.
`
`ACO = H(:s!z(K, RAND,address, 6)]-4, ..., I5].
`
`(EQ 36}
`
`1. The constants are the first largest primes below 257 for which 10 is a primitive root.
`
`1?2
`
`29 November 1999
`
`Biuetooth Security
`
`AFFLT0293400
`
`Samsung Ex. 1119 p. 172
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 173 of 1082
`
`Base-band Specification
`
`Bluetooth.
`
`xor :16 8-bit xor-ings
`
`add: 16 8-bit additions mod 256
`
`Figure 14.12: Fiow ofdara for the computation of E 1
`
`.
`
`14.5.2 The functions A, and A’,
`
`The function A, is identical to SAFER-I». It consists of a set of8 layers, (each
`
`layer is called a round) and a parallel mechanism for generating the sub keys
`KP[_,i], p = I, 2, ..., 1?, the so-called round keys to be used in each round. The
`function will produce a 128-bit result from a 128-bit "random" input string and a
`128-bit “key". Besides the function .4,_. a slightly modified version referred to as
`
`A’, is used in which the input of round 1 is added to the input of the 3rd round.
`
`This is done to make the modified version non-invertible and prevents the use
`
`of A’, (especially in E1, ) as an encryption function. See §’§gure M-f3 on page
`‘ii’-4 for details.
`
`14.5.2.1 The round computations
`
`The computations in each round are a composition of encryption with a round
`key. substitution, encryption with the next round key, and, finally. a Pseudo
`Hadamard Transform (PHT). The computations in a round are shown in Fig:..=re
`14.1.’: on page ‘Jet-. The sub keys for round r, r = l, 2,
`8 are denoted
`
`Bluetooth Security
`
`29 November 1999
`
`AFFLT0293401
`
`Samsung Ex. 1119 p. 173
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 174 of €082
`
`Baseband Specification
`
`K3,.
`
`][j]. K3,.[,il,,«' = 0, 1,
`
`15.Afterthe last round knl,-‘|
`
`is applied in a similar
`
`fashion as all previous odd numbered keys.
`
`14.5.2.2 The substitution boxes ‘'9'’ and “i”
`
`In Figure 1.4.113 on page tit: two boxes occur, marked “e" and "I". These boxes
`implement the same substitutions as used in SAFER+; i.e. they implement
`
`e.i
`
`e
`
`I
`
`:
`
`:
`
`:
`
`{0,...,255}—>{0,...,255},
`
`i
`
`|—>(45*' (mod 257)) (mod 256),
`
`1‘
`
`l—>j s.t. i = e(i}.
`
`Their role, as in the SAFER+ algorithm, is to introduce non-linearity.
`
`
`
`.-I-...____'..—n=-u-—'_‘—¢-'—a2-.-—.-u—
`
`
`
`
`
`
`
`15-.'-..—es-...-
`
`lJr:l_\- lur .-\’r in romul 3
`
`I.“ A In pu|[fl..I5!
`
`IE
`
`.
`. 1\m|n..1s|
`
`..
`
`III
`
`Kzr|fl..l5]
`
`.:'-u'-41-.I:'-I‘$6I:
`
`
`
`.§..._'—f.--12-_'-u'sea..
`
`'._-uIL.'9.4
`
`T-u
`
`
`
`11-4as-I-"-o'_3-ow-43-_I-w-w-n
`
`I
`
`R(‘Jl.‘NDr.I-1.2....“
`
`PUT
`
`.Y
`
`.'I'
`
`Y
`'I'..
`.'l'
`..
`I
`'l'
`Mr: I
`PIIT
`I PHT I
`I PIl1'
`l
`i
`_
`I’
`I
`I
`'I'
`I
`I
`I
`'I'
`I‘ERMl‘T'E:8ll I2l52I65IEl9I-il.![|T-i]
`I
`I
`I
`_L__.t
`.l_.l. _I._L _I._t..
`.I_1
`_i_.I _i_t.
`I PH1'I
`I PHTI
`PHT
`“HT
`I PIITI
`PHT_I
`PHT
`.i
`Z
`l
`!
`L
`_'I_
`..I'
`.'l
`1.
`._I.
`I'..
`.1.
`.I
`..I_
`.I.
`I.
`'l'
`l‘ERMl."[‘I'-_':8lII2l52|65I£I9I4l.Hl7-£3
`
`._l
`
`L.
`I|_I
`_I
`I
`L_
`PHTI
`I'H'l'_IPH'l'LIIPHTI
`I
`I‘
`I‘
`'I'.
`I
`1'
`I
`Pl-‘.RMl‘TE:8IIl2I52l65Iil9I-II.HI74.!
`
`"iii
`.! Ll
`1:
`IPll'I'
`PHTI
`
`I
`
`I -I
`I
`
`|.I
`
`r:_i I._II I‘
`1.:.
`
`rm
`PH'l':IPHTIIl‘HTI
`
`r
`
`....
`53¢:
`
`£_
`
`.
`
`.:
`
`;_
`
`.
`
`3‘ ndllltlon mod :56
`
`hllvtlse xon
`"’f'
`PIlTIx.5'>- E2x+3- mm! 1515. n+_\- mm] 256!
`
`Figure 14.13: One round in .4, and A3. . The permuatetion boxes show how input byte indices are
`mapped onto output byte indioes. Thus, position 0 (ieiimosf) is mapped on position 8. position 1 is
`mapped on position 11, etcetera.
`
`1?4
`
`29 November 1999
`
`Bluetooih Security
`
`AFFLT0293402
`
`Samsung Ex. 1119 p. 174
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 175 of 1082
`
`Base-band Specification
`
`14.5.2.3 Kegscheduiing
`
`In each round, 2 batches of 16 octet-wide keys are needed. These so-called
`round keys are derived as specified by the key scheduling in SAFER+. Figiire
`‘l-if-t on page 1.75 gives an overview of how the round keys K,,|J'| are deter-
`mined. The bias vectors B2, B3, ..., B17 are computed according to following
`equation:
`
`app] = ((45“
`
`5-"”""' mod25
`
`T’ mod 25?) mod 256), rm: = 0,
`
`15.
`
`128 bit Key group-ed in [6 uclels
`
`sum oclcls
`hit-by-hit
`modulo lwn
`
`Sol:-cl aclels
`
`I), I ,2,....,l-1,15
`
`SI:'[I:'I‘.'l nctels
`
`1.2.3»--«.l5,lfI
`
`I
`ll
`
` -
`--
`1
`14
`I5
`16
`
`2..1,4....,l6,l!
`
`figure 14.14: Key scheduiingin A,..
`
`14.5.3 E2-Key generation function for authentication
`
`The key used for authentication is derived through a procedure that is shown in
`§3§QL§!'&‘:' 14. t
`on page 17?‘. The figure shows two different modes of operation
`
`for the algorithm. In the first mode, the function E; should produce on input ofa
`
`128-bit RAND value and a 48-bit address, a 128-bit link key K. This mode is
`utilized when creating unit keys and combination keys. In the second mode the
`
`function E: should produce, on input of a 128-bit RAND value and an L octet
`
`user PIN. a 128-bit link key K. The second mode is used to create the initializa-
`tion key, and also whenever a master key is to be generated.
`
`Bluetooth Security
`
`29 November 1999
`
`AFFLT0293403
`
`Samsung Ex. 1119 p. 175
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 8
`
`page 176 of €882
`
`Baseband Specification
`
`Bluetooth-
`
`When the initialization key is generated, the PIN is augmented with the
`BD_ADDR of the ciaimant unit. The augmentation always starts with the least
`significant octet of the address immediately following the most significant octet
`of the PIN. Since the maximum length of the PIN used in the algorithm cannot
`exceed 16 octets, it is possihie that not all octets of BD_ADDR will be used.
`
`This key generating algorithm again exploits the cryptographic function. For-
`
`mally E: can be expressed for mode 1 (denoted E21 ) as
`
`53,:
`
`{(1,
`
`I }”“x {(1, 1}”-> {(1, 1}”
`
`(RAND, address] i—>A‘,{X, )0
`
`where (for mode 1)
`
`X = RANDIO... I4] LJ(RAND[ [5] ‘P3 6)
`in
`
`Y = Q adclrcssli (mod 6}]
`i=0
`
`Ii
`( Q
`
`39
`
`)
`
`Let L be the number of octets in the user PIN. The augmenting is defined by
`
`PIN[U...L -- |iuBD ADDR,,|(i...1nin{5, I5 - L}],
`
`L< ,6
`
`PIN‘ ={
`
`P[N[U...L 11,
`
`’
`
`L = '6»
`
`(EQ40)
`
`where it is assumed that unit B is the claimant. Then, in mode 2. E3 (denoted
`
`E33 ) can be expressed as
`
`16} —) {0, 1;-""
`E32: {0, 1}“"’x{0, i}”“x{1,2,
`(PIN', RAND, L’) l—>.4',.(X, Y)
`
`an 4”
`
`i5
`
`X = L) PiN'[r' (mod L’)],
`i=0
`
`Y = R/-\ND[0...I4] L.=(R/-\ND[lS](-BL‘),
`
`and L‘ = min-{ 16, L + 6} is the number of octets in PIN‘.
`
`29 November 1999
`
`Biuetooth Security
`
`AFFLT0293404
`
`Samsung Ex. 1119 p. 176
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 177 of 1082
`
`Baseband Specification
`
`Bluetooth.
`
`BD_/\DDR
`
`43
`
`Figure 14. 15: Key generating aigoril‘i1m E2 and its two modes. Mode 1 is used for unit and
`
`combination keys, white mode 2 is used for KM, and Km_m,_, .
`
`14.5.4 E3-Key generation function for encryption
`
`The cipnering key Kr used by E“ is generated by E3. The function E3 is con-
`
`structed using A',.as follows
`
`E3: {n,1}‘3“x{o,|}”"x{0.I}
`
`_){n’l}1z:<
`
`on
`
`(K, RAND, cor) 1—>Hasi1(K, RAND, cor, :2)
`
`(HQ 43}
`
`where Hash is the hash function as defined by i_ EC: I33}. Note that the produced
`
`key length is 128 bits. However, before use within E”, the encryption key I((.
`
`will be shortened to the correct encryption key length, as described in Section
`
`14.3.5 on page ‘.555. A block scheme of E3 is depicted in :-”-figure 14.16.
`
`The value of COF is determined as specified by equation {EQ 333}.
`
`EN RAND
`
`COP
`
`Link key
`
`128
`
`96
`
`Figure 14.16: Generation of the enoryption key:
`
`Bluelooih Security
`
`29 November 1999
`
`AFFLT0293405
`
`Samsung Ex. 1119 p. 177
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 8
`
`page 178 of €332
`
`Baseband Specification
`
`29 November 1999
`
`Bluetooth Security
`
`AFFLT0293406
`
`Samsung Ex. 1119 p. 178
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`Base-band Spedficarion
`
`15 LIST OF FIGURES
`
`page 179 of 1032
`
`Bluetouth.
`
`Figure 1.1:
`iiigure 1.2:
`
`Different fiinciicmai biiacke in iiie E?:§i.i£¥T0{3ii‘i system ................. ..¢i~‘i
`
`Piccneis with e eingie sieve er:-ereiicin {e}, a muiii--sieve
`epereiion {is} and a eeetiereei eperetian {Lt}.
`
`iiigure 2.1:
`
`ifigure 2,2:
`
`T30 8i'it'§‘I§i1'ii!":§} ....................................................................... ..
`!\;i=..=iti-sieipackete
`
`634
`
`44
`
`figure 4.1:
`
`Figure 4.2:
`
`i-"ig1.:re 4.3:
`Figure «$.42
`
`Figure 4.5:
`Figure 4.8:
`
`Figure 43?:
`Figure 4.8:
`
`Sieriiiarci packet former. .......................................................... ..4'i’
`Ameee cede fermat
`
`Preembie ................................................................................. ..49
`
`sync were is if {a}, end when PASS
`Treiier in CA0 when M38
`of S}'E’!i'_‘. worrri is ‘i {in}.
`............................................................... .59
`rieeder format.
`......................................................................... .51
`
`Format of the
`{N pacisei fermai
`
`peyicad ..................................................... .136
`...
`
`Peyieed header format fer singie-eiet packets. ....................... ..62
`
`Figure 4.9:
`
`Peyieezi header format for niuiii—sE0: packers. ......................... ..62
`
`Bit»:-eipeiiiion ericciciing scheme. .............................................. ..E~3?‘
`
`Li"-SR generating the {'1.£i,1{}'i shortened Hamming cede.
`
`.
`
`.......E‘>8
`
`Receive protocoi for detei'rnining_3 the ARQN bii.
`
`.’i.
`
`5 5
`
`",2:
`«>
`Figure -).e.J:
`
`:v”v'igLire 5.4:
`
`Figure 5.5‘.
`
`Reireesrnit fiiieririg for packets wi‘ii"‘= CR8.
`Breedrgasst repeiiéien Scheme
`
`a"~"iQure 5.8:
`
`The LFSR icircruii generating Erie wee.
`
`.............................. ..7‘i
`
`Figure 57!:
`
`initiei state efthe HEC generating circuit.
`
`-
`
`Figure
`
`HE-C1 generation and checking.
`
`figure 5.9:
`
`The E.F'SR circuii generatirig Erie CREE.
`
`Figure 5.10:
`
`initia! state of {he CRC generating circuii.
`
`Figure 5.11:
`
`CRC. generation and checkirug ................................................ ..
`
`."-‘figure 731:
`
`Data whitening LFSFR.
`
`Figure 8.1:
`Figme 8.2:
`
`Figure €5.32
`Figure 8.4‘.
`
`i”-figure 9.1:
`
`figure
`
`9.2:
`
`Functienei diagram 0f'¥'X buffer-ing.
`Furictionei diagram of RX brifierirg ......................................... ..
`
`'
`
`Header bit r3roc:e5:ees.'
`
`Payiead bit moceesee.
`
`R><:"T>é cycie of Biueteoih master transceiver in nizrmai mode fear
`eingie-eioi packets.
`
`RXHX cycie of Biueieeth sieve tre_ris»::eiver in rimrrzei merje for
`siriggieeiet perskeis. .................................................................. ..88
`
`Figure 9.3:
`
`RX tizriireg ef siave retiirnirig fmm mid sieie.
`
`List of Figures
`
`29 November 1999
`
`AFFLTD293407
`
`Samsung Ex. 1119 p. 179
`
`

`
`BLUETOOTH SPECIFICATION Version 1.0 B
`
`page 130 of 1082
`
`Baseband Specification
`
`R><:'?X cycie of Biueteoiri trerisceiver in PAGE mode.
`Figure 9.4:
`Figure 9.5: Timing