Algorithms	79

4.5 Implementation aspects

When building a Bluetooth device, one has to decide how to implement the algorithms. A hardware implementation is the best alternative when speed and power consumption are important. Software implementations allow fast development and are flexible. In this section we discuss the implementation of SAFER+ and E0. Since the authentication process and KC derivation are not very time critical in most Bluetooth usage scenarios, a natural choice for SAFER+ is to implement it in software. Good software implementations can easily be found on various Web sites [14].

The implementation choice for E0 is not that obvious. Since E0 is always running when transmitting encrypted data, it is advantageous to implement E0 in hardware on devices that should have very low power consumption. Because encryption takes place at the physical layer in the communication stack, a hardware implementation fits well together with an implementation where other low-layer functionality is realized in hardware. The design of E0 allows for a further simplification that reduces the number of times one has to clock the four LFSRs. The reader might have observed the special structure of the feedback polynomials. These are so-called windmill polynomials, which have the property that one can construct a linear sequential machine that, provided it is correctly initialized, for each clock cycle generates four consecutive symbols of the sequence that the normal LFSR would generate (see also [15]).

The way a windmill construction works is best shown in Figure 4.9 using the example windmill polynomial t4 + t3 + 1. Shown first is a classical LFSR construction. The output at the third register element forms the maximum length, period 15 sequence starting with the symbols 00010011 . . . . Next is shown a windmill construction that generates the same sequence, but now three symbols for each tick of the clock.

It is now easy to see that the number of required clock cycles in a windmill realization of E0 is only a quarter of that of a direct LFSR implementation.

0			0			0					1			Xt	= 000100110...			0						0							0				1
																		0						0							0
																		1						0							0
																		1						1							0
																		…						…							…
																			X3t						X3t+1							X3t+2
					(a)																			(b)

Figure 4.9 A windmill construction using windmill polynomial t 4 + t 3 + 1.

80	Bluetooth Security

Hence it is possible to clock a windmill variant of E0 only at one-fourth of the clock frequency of a variant with direct LFSRs. The lower clock frequency reduces power consumption in most very large scale intergration (VLSI) implementations. The windmill implementation is also feasible in software.

References

[1]van Oorschot, P. C., A. J. Menezes, and S. A. Vanstone, Handbook of Applied Cryptography, Boca Raton, FL: CRC Press, 1997.

[2]SAGE, 3GPP TS 35.201, the 3GPP Confidentiality and Integrity Algorithms; Document 1: f8 and f9 specifications, Version 5.0.0, 3rd Generation Partnership Programme, 2002.

[3]Massey, J. L., and R. A. Rueppel, “Method of, and Apparatus for, Transforming a Digital Sequence into an Encoded Form,” U.S. Patent No. 4,797,922, 1989.

[4]Rueppel, R. A., “Correlation Immunity and the Summation Combiner,” Advances in Cryptology, Crypto 85, LNCS, Berlin: Springer-Verlag, 1986, pp. 260–272.

[5]Meier, W., and O. Staffelbach, “Correlation Properties of Combiners with Memory in Stream Ciphers,” J. Cryptology, Vol. 5, No. 1, 1992, pp. 67–86.

[6]Golic, J. Dj., “Computation of Low-Weight Parity-Check Polynomials,” Electronic Letters, Vol. 32, No. 21, October 1996, pp. 1981–1982.

[7]Salmasizadeh, M., J. Dj. Golic, and E. Dawson, “Fast Correlation Attacks on the Summation Combiner,” J. Cryptology, Vol. 13, No. 2, 2000, pp. 245–262.

[8]Hermelin, M., and K. Nyberg, “Correlation Properties of the Bluetooth Summation

Combiner,” in J. Song, ed., Proc. ICISC’99, 1999 International Conf. Information Security and Cryptography, No. 1787 in LNCS, Berlin: Springer-Verlag, December 2000,

pp.17–29.

[9]Knudsen, L. R., “A Detailed Analysis of Safer k,” J. Cryptology, Vol. 13, No. 4, 2000,

pp.417–436.

[10]Kuregian, M., G. H. Khachatrian, and J. L. Massey, “Differential Cryptanalysis of Safer+,” Technical Report, Cylink Corporation, Sunnyvale, CA, 20 April, 1999.

[11]ENS Ed, “Nessie Security Report,” Technical Report Version 1.0, NESSIE Project, IST-2000-12324, 2002.

[12]Lidl, R., and H. Niederreiter, Finite Fields, Encyclopedia of Mathematics and Its Applications, Reading, MA: Addison-Wesley, 1983.

[13]Gill, A., Linear Sequential Circuits: Analysis, Synthesis, and Applications, New York: McGraw-Hill, 1966.

[14]Safer+ Development Kit, Available at http://us.cryptosoft.de/html/safer.htm, accessed November 2003.

[15]Smeets, B., and W. G. Chambers, “On Windmill pn-Sequence Generators,” IEE Proc-E, Vol. 136, 1989, pp. 401–404.