Abstract
Forgery and counterfeiting are emerging as serious security risks in low-cost pervasive computing devices. These devices lack the computational, storage, power, and communication resources necessary for most cryptographic authentication schemes. Surprisingly, low-cost pervasive devices like Radio Frequency Identification (RFID) tags share similar capabilities with another weak computing device: people.
These similarities motivate the adoption of techniques from human-computer security to the pervasive computing setting. This paper analyzes a particular human-to-computer authentication protocol designed by Hopper and Blum (HB), and shows it to be practical for low-cost pervasive devices. We offer an improved, concrete proof of security for the HB protocol against passive adversaries.
This paper also offers a new, augmented version of the HB protocol, named HB + , that is secure against active adversaries. The HB + protocol is a novel, symmetric authentication protocol with a simple, low-cost implementation. We prove the security of the HB + protocol against active adversaries based on the hardness of the Learning Parity with Noise (LPN) problem.
Chapter PDF
Similar content being viewed by others
References
Anderson, R., Kuhn, M.: Low Cost Attacks on Tamper Resistant Devices. In: Christianson, B., Lomas, M. (eds.) Security Protocols 1997. LNCS, vol. 1361, pp. 125–136. Springer, Heidelberg (1998)
Berlekamp, E.R., McEliece, R.J., Tilborg, V.: On the Inherent Intractability of Certain Coding Problems. IEEE Transactions on Information Theory 24, 384–386 (1978)
Blum, A., Furst, M., Kearns, M., Lipton, R.J.: Cryptographic Primitives Based on Hard Learning Problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994)
Blum, A., Kalai, A., Wasserman, H.: Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model. Journal of the ACM 50(4), 506–519 (2003)
Blum, M., Luby, M., Rubinfeld, R.: Self-Testing/Correcting with Applications to Numerical Problems. In: Symposium on Theory of Computation, pp. 73–83 (1990)
Bono, S., Green, M., Stubblefield, A., Juels, A., Rubin, A., Szydlo, M.: Security Analysis of a Cryptographically-Enabled RFID Device. In: USENIX Security (2005) (to appear), Available at http://rfidanalysis.org/
Chabaud, F.: On the Security of Some Cryptosystems Based on Error-Correcting Codes. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 131–139. Springer, Heidelberg (1995)
Courtois, N., Finiasz, M., Sendrier, N.: How to Achieve a McEliece-based Digital Signature Scheme. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 157–174. Springer, Heidelberg (2001)
Crawford, J.M., Kearns, M.J., Shapire, R.E.: The Minimal Disagreement Parity Problem as a Hard Satisfiability Problem. Tech. rep., Computational Intelligence Research Laboratory and AT&T Bell Labs (February 1994)
EPCglobal (2005), Website http://www.epcglobalinc.org/
Feldhofer, M., Dominikus, S., Wolkerstorfer, J.: Strong Authentication for RFID Systems using the AES Algorithm. In: Cryptographic Hardware in Embedded Systems, CHES (2004)
Floerkemeier, C., Lampe, M.: Issues with RFID Usage in Ubiquitous Computing Applications. In: Ferscha, A., Mattern, F. (eds.) PERVASIVE 2004. LNCS, vol. 3001, pp. 188–193. Springer, Heidelberg (2004)
Food and Drug Administration. Combating counterfeit drugs. Tech. rep., US Department of Health and Human Services, Rockville, Maryland (Februrary 2004)
Håstad, J.: Some Optimal Inapproximability Results. In: Symposium on Theory of Computing, pp. 1–10 (1997)
Henrici, D., Müller, P.: Hash-based Enhancement of Location Privacy for Radio-Frequency Identification Devices using Varying Identifiers. In: Pervasive Computing and Communications (PerCom), pp. 149–153. IEEE Computer Society, Los Alamitos (2004)
Hopper, N., Blum, M.: A Secure Human-Computer Authentication Scheme. Tech. Rep. CMU-CS-00-139, Carnegie Mellon University (2000)
Hopper, N.J., Blum, M.: Secure Human Identification Protocols. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 52–66. Springer, Heidelberg (2001)
Juels, A.: Minimalist Cryptography for RFID Tags. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 149–164. Springer, Heidelberg (2005)
Juels, A.: ”Yoking Proofs” for RFID Tags. In: Pervasive Computing and Communications Workshop. IEEE Press, Los Alamitos (2004)
Juels, A., Pappu, R.: Squealing Euros: Privacy Protection in RFID-Enabled Banknotes. In: Wright, R.N. (ed.) FC 2003. LNCS, vol. 2742, pp. 103–121. Springer, Heidelberg (2003)
Juels, A., Rivest, R.L., Szydlo, M.: The blocker tag: selective blocking of RFID tags for consumer privacy. In: Proceedings of the 10th ACM conference on Computer and communication security, pp. 103–111. ACM Press, New York (2003)
Kearns, M.: Efficient Noise-Tolerant Learning from Statistical Queries. Journal of the ACM 45(6), 983–1006 (1998)
MacWilliams, F., Sloane, N.: The Theory of Error-Correcting Codes. North-Holland, Amsterdam (1977)
Mandel, J., Roach, A., Winstein, K.: MIT Proximity Card Vulnerabilities. Tech. rep., Massachusetts Institute of Technology (March 2004)
Matsumoto, T.: Human-computer Cryptography: An Attempt. In: Computer and Communications Security, pp. 68–75. ACM Press, New York (1996)
Matsumoto, T., Imai, H.: Human Identification through Insecure Channel. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 409–421. Springer, Heidelberg (1991)
McEliece, R.J.: DSN Progress Report. Tech. Rep., JPL-Caltech, 42–44 (1978)
Miller, G.A.: The Magical Number Seven, Plus or Minus Two: Some Limits on Our Capacity for Processing Information. Psychological Review 63, 81–97 (1956)
Molnar, D., Wagner, D.: Privacy and Security in Library RFID: Issues, Practices, and Architectures. In: Pfitzmann, B., McDaniel, P. (eds.) Computer and Communications Security, pp. 210–219. ACM, New York (2004)
Naor, M., Pinkas, B.: Visual Authentication and Identification. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 322–336. Springer, Heidelberg (1997)
Niederreiter, H.: Knapsack-Type Cryptosystems and Algebraic Coding Theory. Problems of Control and Information Theory 15(2), 159–166 (1986)
Ohkubo, M., Suzuki, K., Kinoshita, S.: Efficient Hash-Chain Based RFID Privacy Protection Scheme. In: Ubiquitous Computing (UBICOMP) (September 2004)
Sarma, S.E., Weis, S.A., Engels, D.W.: RFID Systems and Security and Privacy Implications. In: Kaliski Jr., B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 454–469. Springer, Heidelberg (2003)
Shamos, M.I.: Paper v. Electronic Voting Records - An Assessment. Paper written to accompany panel presentation at Computers, Freedom, and Privacy Conference (2004), Available at http://euro.ecom.cmu.edu/people/faculty/mshamos/paper.htm
Stern, J.: A New Paradigm for Public Key Identification. IEEE Transactions on Information Theory 42(6), 1757–1768 (1996)
Vajda, I., Buttyan, L.: Lightweight Authentication Protocols for Low-Cost RFID Tags. In: Ubiquitious Computing, UBICOMP (2003)
Verichip (2005) Website, http://www.4verichip.com/
Wang, C.-H., Hwang, T., Tsai, J.-J.: On the Matsumoto and Imai’s Human Identification Scheme. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol. 921, pp. 382–392. Springer, Heidelberg (1995)
Weis, S.A., Sarma, S.E., Rivest, R.L., Engels, D.W.: Security and Privacy Aspects of Low-Cost Radio Frequency Identification Systems. In: Hutter, D., Müller, G., Stephan, W., Ullmann, M. (eds.) Security in Pervasive Computing. LNCS, vol. 2802, pp. 201–212. Springer, Heidelberg (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Juels, A., Weis, S.A. (2005). Authenticating Pervasive Devices with Human Protocols. In: Shoup, V. (eds) Advances in Cryptology – CRYPTO 2005. CRYPTO 2005. Lecture Notes in Computer Science, vol 3621. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11535218_18
Download citation
DOI: https://doi.org/10.1007/11535218_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28114-6
Online ISBN: 978-3-540-31870-5
eBook Packages: Computer ScienceComputer Science (R0)