1. Security Architecture 2. Random Number Generation 3. Key Management 4. The establishment of the secure channel 4.1 Generating initialization key 4.2 Authentication 4.3 Link key generation and exchange 5. The encryption communication in Bluetooth 5.1 the generation of encryption key 5.2 the encryption of the communication data 6. the discussion and conclusion 6.1 the discussion of the key generation algorithm 6.2 Conclusion
1. Security Architecture Bluetooth is a short-range radio link intended to replace the cable(s) connecting portable and/or fixed electronic devices. So it is not a general purpose wireless solution. However, the security system is still worth discussing. Bluetooth provide security measures both at the application layer and the link layer. In order to fit in the peer environment, the security system (includeing authentication and encryption) is implemented in the same way in each Bluetooth unit. Basically, almost all security features are implemented in link layer, the whole security system is built on the top of link layer security. So I will focus on the discussion of link layer security features. To maintain the security, there are five entities are used: i ) BD_ADDR (48 bits): a public address for each Bluetooth unit; ii ) Secret key (128 bits) for authentication; also known as unit key; iii) Secret key (8-128 bits) for encryption which is derived from authentication key. iv ) Random Number (128 bits) which will change in each transaction; v ) PIN code (1-16 octets); Every security system can be reduced to the establishment of secure channel. In Bluetooth, it is done in this way: one unit will start a initialization procedure to authentication the communication peers, generateand exchange the link key, and generating the encryption key in each unit. Then the unit can go on with this secure channel. 2. Random Number Generation It is claimed by Bluetooth, their random numbers generator "be non-repeating and randomly generated". That means a random number is highly unlikely to repeat itself within the lifetime of the authentication key. And "randomly generated" means it is not possible to predict its vale with a chance that is significantly larger than 0 (e.g., greater than 1 / (2 exp L) for a key length of L bits). However, I didn't find any specification about such a great random number generator. No design principle, how to get seed and so on. I think Bluetooth just want to increase it security to some extent by keeping it secret. 3. Key Management There are 4 types of keys in Bluetooth: unit key, init key, encryption key, and link key. Actually, the first 2 keys can be used as the last one. The unit key is created when the unit is first time in use and (almost) never change. This unit key will be exchanged in the initalization procedure and used as link key, and furtherly used as one of inputs to create the encryption key. The init key is used as the link during the initialization process. It will protects the transfer of initialization parameters. The encryption key is derived from current link, a 96-bit ciphering offset number (COF), and a 128-bit random number. It will be re-generated each time the unit enters the encryption mode. The link key is a 128-bit random number which is shared between two or more parties and is the base for all secruity transactions between these parties. It will be used to generate encryption key and also used in authentication process. The lifetime of a link key is limited by the session which is the duration several units communicating with each other. Besides the key, as we ever mentioned above, there is another very important entity in the security system, the PIN code. The PIN code can be fixed, or be an arbitrary number which is entered in all units that have to be matched. Obviously, the latter is much more secure. And since the Bluetooth is aiming at the short range wireless communcation, this is a very reasonable assumption. 4. The establishment of secure channel Each time when two or more Bluetooth units need communicate secruely. (They can choose to communicate in plain text.) They will first set up the secure channel according following steps: 1) Generating an initialization key; 2) Authentication; 3) Generating the link key; 4) Link key exchange; 5) Generation encryption key in each unit; Now let's look at them one by one. 4.1 Generating initialization key The initialization key K(init) is derived by the E22 algorithm with the BD_ADDR of the claimant unit, a PIN code, the length of the PIN (in octets), and a random number IN_RANDa issued (and generated) by verifier. The Bluetooth specification only give the input and output specification of this algorithm. But it looks much samiliar to SAFER+ which is used in E1 (for authentication) as we will see. The 128-bit ouput of E22 will be used in key exchange during the generation of link key as well as the authenticaiton procedure, i.e., as the initialization key. E22 is the second mode of algorithm E2. The first mode of E2 is used to create the unit key. One thing I need point out is this algorithm E2 is not the AES candidate "E2". 4.2 Authentication After get the initialization key K(init), the next move is authentication which use a chanllenge-response scheme. The verifier will send the claimant a random number, say AU_RANDa, the claimant will use E1 algorithm to compute a result called SRES then send back SRES to the verifier, then the verifier will compare the value it compute by itself against with the send-back one. In this way, two units can make sure each share the same secret key, or link key. The authentication prodedure (E1) will produce an auxiliary parameter, the Authenticated Ciphering Offse (ACO), which will be used for encryption key generation as we will see. If the authentication fails, it is required to wait for a while to attempt next authentication. And for each authenticaiton failure with the same unit, the waiting interval will be increased exponentially. This mechanism can prevent attacker to repeat the authenticaiton procedure with a large number of different keys. And through keeping a list of each waiting intevals for each unit, it also can dewarf the denial-of-service attacks. The authentication algorithm E1 is computationally secure. It uses the encryption function called SAFER+ which is an enhance version of block cipher SAFER-SK128. We will give some discussion to this algorithm later since Bluetooth use this algorithm (or some of its components) a lot in its key generation and authentication algorithm. 4.3 Link key generation and exchange A link key could be any one of following: 1) the combination key K(AB); 2) the unit key Ka; 2) the tmeporary key Kmaster; 4) the initialization key K(init). We already saw what are the unit key and initilization key, so let's look at what are the combination key and temporary key. 4.3.1 the generation of combination key We can simply say the difference between using one unit key as link and using a combination key as link the latter need both peers' unit keys to generate the link instead of only one unit key. I will show the procedure as follow: A B LK_Ka=E21(LK_RANDa,BD_ADDRa) | | LK_Kb=E21(LK_RANDb,BD_ADDRb) Ca = LK_RANDa (+) K | | Cb = LK_RANDb (+) K | Ca | |----->| | | | Cb | |<-----| LK_RANDb = Cb (+) K | | LK_RANDa = Ca (+) K LK_Kb=E21(LK_RANDb,BD_ADDRb) | | LK_Ka=E21(LK_RANDa,BD_ADDRa) Kab = LK_Ka (+) LK_Kb | | Kba = LK_Ka (+) LK_Kb = Kab | | |Authen| |<---->| note: (+) means XOR, and Kab is the combination key. 4.3.2 the generation of master key The master key is mainly use in point-to-multipoint situation when the "point" want to use one uniform key for all of "multipoint". The master key is created in the Master, the "one point", by Kmaster = E22(RAND1, RAND2, 16). Then the master will send another random number to all slaves (multipoint) by current link key, following the XOR result of Kmaster and that random number. This is hardly useful. Because once somebody break the current link key, to exchange the Kmaster in such a tricky way is no more secure than send Kmaster directly using current link key, i.e. both ways' security strength is the same, but the method used by Bluetooth is much trouble and time-waste. 4.3.3 the exchange of link key The link will be send to the other party directly by using current link key, either a previous one, or an initilization key. 5. The encryption communication in Bluetooth Bluetooth don't use the link key to encrypt the data directly. Instead, it will generate a new encryption key each time it enter the encryption mode. 5.1 the generation of encryption key The encryption key is derived by an algorithm called E3 by Bluetooth. Actually, this E3 algorithm is constructed by using SAFER+ too. As we have seen, Bluetooth use SAFER+ very often in its key generation algorithms. I will discuss that algorithm later. To generate the encryption key Kc, the E3 need the current link key, a 96-bit Ciphering Offset number (COF), and a 128-bit random number. The COF is derived as follow: 1) if the link key is a master key, COF = BD_ADDR U BD_ADDR 2) otherwise, COF = ACO, ACO is produced when doing authentication One thing we should point out is the random number which is used to derive the encryption key is generated by the master before entering encryption mode, and sent to the other party in plain text. In my opinion, this make the random number become not so "random", lose much of its significance. 5.2 the encryption of the communication data The user data will be encrypted in packet payload by stream cipher. The packet header and access code will transfered in plain text. Bluetooth calls its stream cipher as E0. E0 include three parts: the first part will generate the payload key; the second part performs the generation of the key steam bits; the last part finish the encryption and decryption. The first and the third part is very simple. The first part just shuffle the input bits in certain order and shift them into the key stream genertor; the third part is just a XOR opration. So the most important part is the second one: the key stream generator. The key stream generator is derived from the summation stream cipher generator attributable to Massey adn Rueppel. The summation stream cipher generator has been thoroughly investaged, and it seems a good one. But it is known to be vulnerable to the correlation attacks. To overcome this attack, Bluetooth will re-sychronize the generator for each payload, and claim that such a high re-sychronization freqency will "disrupt" the attacks. 6. the discussion and conclusion 6.1 the discussion of the key generation algorithm: SAFER+ SAFER+ is one of the first round candidates for AES. First, J. Kelsey, B. Schneier, and D. Wagner point out "the poor diffusion of key material through the cipher when using SAFER+ with 256-bit keys" [KSW]. Schneier's paper expose the SAFER+ is vulnerable to the meet-in-the-middle attack and related-key attack. And at the same time, the AES' first round report also point out, besides the above mentioned problems, SAFER+'s performance is not satisfiable for large block ciphering, and in the smart card implentation, SAFER+ shows "Significant implicit weaknesses", and is "highly vulnerable to the attack (the equivalent of at least 50% of the master key can be recovered). " [AES1R] In the same paper, NIST concludes "Advantages: a.Good security margin. b.Well-suited to smart cards due to low RAM and ROM requirements. c.Supports on-the-fly subkey generation with subkeys computable in any order. Disadvantages: Very slow across platforms. Security gaps related to smart card implementations: a.Employs addition, which is somewhat difficult to defend against timing and power attacks. b.Very vulnerable to the attack in [CJRR]." Though there is a improving version SAFER+ [CWil] was submited, which "correct the minor key schedule deficiency", it was still not admited to round 2. I think the main reason should be the performance, but not the security strength it can supply. Though SAFER+ has some performace problem, but Bluetooth uses it only on key generation, so such problem is very trivial. And notice SAFER+ has very low requirement to RAM and ROM volume, it do be a good choice. 6.2 Conclusion The most important secret parameter in Bluetooth should be the PIN code, since all other key has to be derived from it to some extent (initialization key), or need it to exchange securely (all kinds of link key). This decides Bluetooth is not fit for a wide scale senario like WAN or Internet. However, since Bluetooth aims at the small scale "short range radio link", it should be secure satisfiable in most applications. [AES1R] J. Nechvatal, E. Barker, D. Dodson, etc., "STATUS REPORT ON THE FIRST ROUND OF THE DEVELOPMENT OF THE ADVANCED ENCRYPTION STANDARD", NIST's AES round 1 report, August 1999, this paper can be found on-line at http://csrc.nist.gov/encryption/aes/round1/r1report.htm [CJRR] S. Chari, C. Jutla, J. Rao, and R. Rohatgi, "A cautionary note regarding evaluation of AES candidates on smart cards", The Second AES Conference, March 22-23, 1999, pp 133-147. [CWil] C. Williams, Proposal for a "tweak" to Cylink's AES candidate SAFER+, proposed modification, submitted on May 14, 1999, available at http://www.nist.gov/aes [KSW] J. kelsey, B. Schneier, D. Wagner, "key Schedule Weaknesses in SAFER+", Second AES Candidate Conference, April 1999, this paper also available on-line at http://www.counterpane.com/safer.html