SPATE: small-group PKI-less authenticated trust establishment

ABSTRACT

Establishing trust between a group of individuals remains a difficult problem. Prior works assume trusted infrastructure, require an individual to trust unknown entities, or provide relatively low probabilistic guarantees of authenticity (95% for realistic settings). This work presents SPATE, a primitive that allows users to establish trust via device mobility and physical interaction. Once the SPATE protocol runs to completion, its participants' mobile devices have authentic data that their applications can use to interact securely (i.e., the probability of a successful attack is 2^-24). For this work, we leverage SPATE as part of a larger system to facilitate efficient, secure, and user-friendly collaboration via email and file-sharing services. Our implementation of SPATE on Nokia N70 smartphones allows users to establish trust in small groups of up to eight users in less than one minute. The two example SPATE applications provide increased security with no overhead noticeable to users once keys are established.

REFERENCES

• 1: Abdalla, M., Bresson, E., Chevassut, O., and Pointcheval, D. Password-based group key exchange in a constant number of rounds. In Public Key Cryptography (PKC) (2006), pp. 427--442.
• 2: Asokan, N., and Ginzboorg, P. Key-agreement in ad-hoc networks. Computer Communications 23 17 (Nov. 2000), 1627--1637.
• 3: Balfanz, D., Smetters, D., Stewart, P., and Wong, H. Talking to strangers: Authentication in ad-hoc wireless networks. In Proceedings of the 9th Annual Network and Distributed System Security Symposium (NDSS)(2002)
• 4: Blum, M. Coin flipping by telephone. In Advances in Cryptography (August 1982), pp. 11--15.
• 5: Brennen, V. A. The keysigning party howto. http://cryptnet.net/fdp/crypto/keysigning_party/en/keysigning_party.html, Jan. 2008.
• 6: Mike Burmester , Yvo Desmedt, Efficient and Secure Conference-Key Distribution, Proceedings of the International Workshop on Security Protocols, p.119-129, April 10-12, 1996
• 7: Cagalj, M., Capkun, S., and Hubaux, J.-P. Key agreement in peer-to-peer wireless networks. IEEE (Special Issue on Cryptography) 94 (2006), 467--478.
• 8: Srdjan Čapkun , Jean-Pierre Hubaux , Levente Buttyán, Mobility helps security in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778422]
• 9: Claude Castelluccia , Pars Mutaf, Shake them up!: a movement-based pairing protocol for CPU-constrained devices, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067177]
• 10: Chia-Hsin Owen Chen , Chung-Wei Chen , Cynthia Kuo , Yan-Hao Lai , Jonathan M. McCune , Ahren Studer , Adrian Perrig , Bo-Yin Yang , Tzong-Chen Wu, GAnGS: gather, authenticate 'n group securely, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409957]
• 11: Cohen, B. Bittorrent. http://www.bittorrent.com Apr. 2001.
• 12: Cox, M. J., and Engelschall, R. S. Openssl:Open source toolkit implementing for ssl/tls. http://www.openssl.org/May 1999
• 13: Carl Ellison , Steve Dohrmann, Public-key support for group collaboration, ACM Transactions on Information and System Security (TISSEC), v.6 n.4, p.547-565, November 2003 [doi>10.1145/950191.950195]
• 14: S. N. Foley , J. Jacob, Specifying security for CSCW systems, Proceedings of the 8th IEEE workshop on Computer Security Foundations, p.136, March 13-15, 1995
• 15: Bryan Ford , Jacob Strauss , Chris Lesniewski-Laas , Sean Rhea , Frans Kaashoek , Robert Morris, Persistent personal names for globally connected mobile devices, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.17-17, November 06-08, 2006, Seattle, WA
• 16: Glasbey, C., van der Heijden, G., Toh, V. F. K., and Gray, A. Colour displays for categorical images. Color Research and Application 32 4 (June 2007), 304--309.
• 17: Nathaniel S. Good , Aaron Krekelberg, Usability and privacy: a study of Kazaa P2P file-sharing, Proceedings of the SIGCHI conference on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA [doi>10.1145/642611.642636]
• 18: Michael T. Goodrich , Michael Sirivianos , John Solis , Gene Tsudik , Ersin Uzun, Loud and Clear: Human-Verifiable Authentication Based on Audio, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.10, July 04-07, 2006 [doi>10.1109/ICDCS.2006.52]
• 19: 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
• 20: Houston, D., and Ferdowsi, A. Dropbox. https://www.getdropbox.com/Sept. 2008.
• 21: T. Howes , M. Smith , F. Dawson, A MIME Content-Type for Directory Information, RFC Editor, 1998
• 22: Jakobsson, M. Issues in security and privacy (lecture slides). http://www. informatics.indiana.edu/markus/i400/2006.
• 23: Mike Just , Serge Vaudenay, Authenticated Multi-Party Key Agreement, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.36-49, November 03-07, 1996
• 24: Yongdae Kim , Adrian Perrig , Gene Tsudik, Simple and fault-tolerant key agreement for dynamic collaborative groups, Proceedings of the 7th ACM conference on Computer and communications security, p.235-244, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352638]
• 25: Cynthia Kuo , Adrian Perrig, Reduction of end user errors in the design of scalable, secure communication, Carnegie Mellon University, Pittsburgh, PA, 2008
• 26: Laur, S., and Nyberg, K. Efficient mutual data authentication using manually authenticated strings. In Cryptology and Network Security (CANS) (2006), pp. 90--107.
• 27: Lester, J., Hannaford, B., and Gaetano, B. Are you with me?-using accelerometers to determine if two devices are carried by the same person. In Proceedings of Pervasive (2004).
• 28: Linksky, J. et al Simple Pairing Whitepaper, revision v10r00. http://www. bluetooth.com/NR/rdonlyres/0A0B3F36-D15F-4470-85A6-F2CCFA26F70F/0/SimplePairing_WP_V10r00.pdf August 2006.
• 29: Lortz, V., Roberts, D., Erdmann, B., Dawidowsky, F., Hayes, K., Yee, J. C., and Ishidoshiro, T. Wi-Fi Simple Config Specification, version 1. 0a. Now known as Wi-Fi Protected Setup, February 2006.
• 30: Jonathan M. McCune , Adrian Perrig , Michael K. Reiter, Seeing-Is-Believing: Using Camera Phones for Human-Verifiable Authentication, Proceedings of the 2005 IEEE Symposium on Security and Privacy, p.110-124, May 08-11, 2005 [doi>10.1109/SP.2005.19]
• 31: Mozilla Thunderbird 2. http://www.mozilla.com/en-US/thunderbird/Dec. 2008.
• 32: NFC Forum NFC Forum:Specifications. http://www.nfc-forum.org/specs/.
• 33: Perrig, A., and Song, D. Hash visualization:A new technique to improve real-world security. In International Workshop on Cryptographic Techniques and E-Commerce (CrypTEC '99) (July 1999), M. Blum and C. H. Lee, Eds., pp. 131--138.
• 34: Ramsdell, B. RFC 3851:Secure/multipurpose internet mail extensions (S/MIME)version 3. 1 message specification, July 2004.
• 35: Rohs, M., and Gfeller, B. Using camera-equipped mobile phones for interacting with real-world objects. Proceedings of Advances in Pervasive Computing (Apr. 2004), 265--271.
• 36: David Scott , Richard Sharp , Anil Madhavapeddy , Eben Upton, Using visual tags to bypass Bluetooth device discovery, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.1, January 2005 [doi>10.1145/1055959.1055965]
• 37: scponly. http://sublimation.org/scponly/2009.
• 38: Soriente, C., Tsudik, G., and Uzun, E. BEDA: Button-enabled device association. In International Workshop on Security for Spontaneous Interaction (IWSSI) (2007).
• 39: Claudio Soriente , Gene Tsudik , Ersin Uzun, HAPADEP: Human-Assisted Pure Audio Device Pairing, Proceedings of the 11th international conference on Information Security, September 15-18, 2008, Taipei, Taiwan [doi>10.1007/978-3-540-85886-7_27]
• 40: 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
• 41: D. G. Steer , L. Strawczynski , Whitfield Diffie , Michael J. Wiener, A Secure Audio Teleconference System, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.520-528, August 21-25, 1988
• 42: Michael Steiner , Gene Tsudik , Michael Waidner, Key Agreement in Dynamic Peer Groups, IEEE Transactions on Parallel and Distributed Systems, v.11 n.8, p.769-780, August 2000 [doi>10.1109/71.877936]
• 43: Szeredi, M. SSH filesystem. http://fuse.sourceforge.net/sshfs. html Jan. 2005.
• 44: Wen-Guey Tzeng , Zhi-Jia Tzeng, Round-Efficient Conference Key Agreement Protocols with Provable Security, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.614-628, December 03-07, 2000
• 45: Uzun, E., Karvonen, K., and Asokan, N. Usability analysis of secure pairing methods. In Usable Security (USEC) (Feb. 2007).
• 46: Valkonen, J., Asokan, N., and Nyberg, K. Ad hoc security associations for groups. In Security and Privacy in Ad-Hoc and Sensor Networks (ESAS) (2006), pp. 150--164.
• 47: Vaudenay, S. Secure communications over insecure channels based on short authenticated strings. In Advances in Cryptology (Crypto) (2005), pp. 309--326.
• 48: Whitten, A., and Tygar, J. Why Johnny can't encrypt. In USENIX Security (Aug. 1999).
• 49: Zennström, N., Friis, J., and Kasesalu, P. KaZaA media desktop. http://www. kazaa. com Mar. 2001.

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:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Modules and interfaces

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors

General Terms:
Design, Human Factors, Security

Keywords:
group protocol, implementation, key exchange, security