Shake them up!: a movement-based pairing protocol for CPU-constrained devices

ABSTRACT

This paper presents a new pairing protocol that allows two CPU-constrained wireless devices Alice and Bob to establish a shared secret at a very low cost. To our knowledge, this is the first software pairing scheme that does not rely on expensive public-key cryptography, out-of-band channels (such as a keyboard or a display) or specific hardware, making it inexpensive and suitable for CPU-constrained devices such as sensors.

In the described protocol, Alice can send the secret bit 1 to Bob by broadcasting an (empty) packet with the source field set to Alice. Similarly, Alice can send the secret bit 0 to Bob by broadcasting an (empty) packet with the source field set to Bob. Only Bob can identify the real source of the packet (since it did not send it, the source is Alice), and can recover the secret bit (1 if the source is set to Alice or 0 otherwise). An eavesdropper cannot retrieve the secret bit since it cannot figure out whether the packet was actually sent by Alice or Bob. By randomly generating n such packets Alice and Bob can agree on an n-bit secret key.

Our scheme requires that the devices being paired, Alice and Bob, are shaken during the key exchange protocol. This is to guarantee that an eavesdropper cannot identify the packets sent by Alice from those sent by Bob using data from the RSSI (Received Signal Strength Indicator) registers available in commercial wireless cards. The proposed protocol works with off-the-shelf 802.11 wireless cards and is secure against eavesdropping attacks that use power analysis. It requires, however, some firmware changes to protect against attacks that attempt to identify the source of packets from their transmission frequency.

REFERENCES

• 1: Fundamentals of Quartz Oscillators. HP Application Note 200-2.
• 2: http://www.telluriantech.com. Specialty Crystals, Quartz Crystals.
• 3: Alpern, B., and Schneider, F. Key exchange using "Keyless Cryptography". Information processing letters 16, 2 (February 1983), 79--82.
• 4: Chayat, N. 802.11a PHY Overview. Slides available at: http://www.nwest.nist.gov/mtg3/papers/chayat.pdf.
• 5: Dai, W. Speed benchmarks for various ciphers and hash functions. URL:http://www.eskimo.com/~weidai/.
• 6: Diffie, W., and Hellman, M. New directions in cryptography. IEEE Transactions on Information Theory IT-22, 6 (1976), 644--654.
• 7: Gehrmann, C., and Nyberg, K. Enhancements to bluetooth baseband security. In Nordsec'01 (Kopenhagen, Denmark, November 2001).
• 8: Goldwasser, S., and Bellare, M. Lectures notes in cryptography. URL:http://www.cs.ucsd.edu/users/mihir/papers/gb.html.
• 9: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 10: Hoepman, J.-H. Ephemeral pairing in anonymous networks. Available at: http://www.cs.kun.nl/~jhh/publications/anonpairing.pdf.
• 11: Hoepman, J.-H. The ephemeral pairing problem. In 8th Int. Conf. Financial Cryptography (Key West, Florida, February 9-12 2004), pp. 212--226.
• 12: Lars Erik Holmquist , Friedemann Mattern , Bernt Schiele , Petteri Alahuhta , Michael Beigl , Hans-Werner Gellersen, Smart-Its Friends: A Technique for Users to Easily Establish Connections between Smart Artefacts, Proceedings of the 3rd international conference on Ubiquitous Computing, p.116-122, September 30-October 02, 2001, Atlanta, Georgia, USA
• 13: Chris Karlof , Naveen Sastry , David Wagner, TinySec: a link layer security architecture for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031515]
• 14: Lenstra, A. K., and Verheul, E. R. Selecting cryptographic key sizes. Journal of Cryptology: the journal of the International Association for Cryptologic Research 14, 4 (2001), 255--293.
• 15: Lester, J., Hannaford, B., and G., B. "Are You with Me? - Using Accelerometers to Determine If Two Devices Are Carried by the Same Person". In Pervasive 2004 (Vienna, Austria, April 21-23 2004).
• 16: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 17: Ogilvie, B. Clock Solutions for WiFi (IEEE 802.11). Saronix(tm) application note, 2003.
• 18: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 19: Frank Stajano , Ross J. Anderson, The Resurrecting Duckling: Security Issues for Ad-hoc Wireless Networks, Proceedings of the 7th International Workshop on Security Protocols, p.172-194, April 19-21, 1999
• 20: Vig, J., and Ballato, A. Frequency Control Devices. Reprinted from Ultrasonic Instruments and Devices, Academic Press, 1999.
• 21: Roy Want , Trevor Pering, New Horizons for Mobile Computing, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.3, March 23-26, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Signal processing systems

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Security