Hidden credential retrieval from a reusable password

ABSTRACT

We revisit the venerable question of access credentials management, which concerns the techniques that we, humans with limited memory, must employ to safeguard our various access keys and tokens in a connected world. Although many existing solutions can be employed to protect a long secret using a short password, those solutions typically require certain assumptions on the distribution of the secret and/or the password, and are helpful against only a subset of the possible attackers.

After briefly reviewing a variety of approaches, we propose a user-centric comprehensive model to capture the possible threats posed by online and offline attackers, from the outside and the inside, against the security of both the plaintext and the password. We then propose a few very simple protocols, adapted from the Ford-Kaliski server-assisted password generator and the Boldyreva unique blind signature in particular, that provide the best protection against all kinds of threats, for all distributions of secrets. We also quantify the concrete security of our approach in terms of online and offline password guesses made by outsiders and insiders, in the random-oracle model.

The main contribution of this paper lies not in the technical novelty of the proposed solution, but in the identification of the problem and its model. Our results have an immediate and practical application for the real world: they show how to implement single-sign-on stateless roaming authentication for the internet, in a ad-hoc user-driven fashion that requires no change to protocols or infrastructure.

REFERENCES

• 1: Michel Abdalla, Mihir Bellare, Dario Catalano, Eike Kiltz, Tadayoshi Kohno, Tanja Lange, John Malone Lee, Gregory Neven, Pascal Paillier, and Haixia Shi. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. In Advances in Cryptology---CRYPTO 2005, pages 205--22, 2005.
• 2: Mihir Bellare , Silvio Micali, Non-Interactive Oblivious Transfer and Spplications, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.547-557, August 20-24, 1989
• 3: Mihir Bellare, David Pointcheval, and Philip Rogaway. Authenticated key exchange secure against dictionary attacks. In Advances in Cryptology---EUROCRYPT 2000, pages 139--55, 2000.
• 4: Steven M. Bellovin , Michael Merritt, Encrypted Key Exchange: Password-Based Protocols SecureAgainst Dictionary Attacks, Proceedings of the 1992 IEEE Symposium on Security and Privacy, p.72, May 04-06, 1992
• 5: Steven M. Bellovin , Michael Merritt, Augmented encrypted key exchange: a password-based protocol secure against dictionary attacks and password file compromise, Proceedings of the 1st ACM conference on Computer and communications security, p.244-250, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168618]
• 6: Charles H. Bennett , Gilles Brassard , Claude Crépeau , Marie-Hélène Skubiszewska, Practical Quantum Oblivious Transfer, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.351-366, August 11-15, 1991
• 7: I. Blake , G. Seroussi , N. Smart , J. W. S. Cassels, Advances in Elliptic Curve Cryptography (London Mathematical Society Lecture Note Series), Cambridge University Press, New York, NY, 2005
• 8: Simon Blake-Wilson , Don Johnson , Alfred Menezes, Key Agreement Protocols and Their Security Analysis, Proceedings of the 6th IMA International Conference on Cryptography and Coding, p.30-45, December 17-19, 1997
• 9: Alexandra Boldyreva, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.31-46, January 06-08, 2003
• 10: Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. Public key encryption with keyword search. In Advances in Cryptology---EUROCRYPT 2004, pages 506--22, 2004.
• 11: Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, and W. Skeith. Public key encryption that allows PIR queries. In Advances in Cryptology---CRYPTO 2007, pages 50--67, 2007.
• 12: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 13: Xavier Boyen, Halting password puzzles: hard-to-break encryption from human-memorable keys, Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, p.1-16, August 06-10, 2007, Boston, MA
• 14: Xavier Boyen and Brent Waters. Anonymous hierarchical identity-based encryption (without random oracles). In Advances in Cryptology---CRYPTO 2006, pages 290--307, 2006.
• 15: Victor Boyko, Philip MacKenzie, and Sarvar Patel. Provably secure password-authenticated key exchange using Diffie-Hellman. In Advances in Cryptology---EUROCRYPT 2000, 2000.
• 16: Gilles Brassard , Claude Crépeau , Jean-Marc Robert, All-or-nothing disclosure of secrets, Proceedings on Advances in cryptology---CRYPTO '86, p.234-238, January 1987, Santa Barbara, California, United States
• 17: Christian Cachin, Silvio Micali, and Michael Stadler. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology---EUROCRYPT 1999, pages 402--14, 1999.
• 18: Jan Camenisch , Gregory Neven , Abhi Shelat, Simulatable Adaptive Oblivious Transfer, Proceedings of the 26th annual international conference on Advances in Cryptology, p.573-590, May 20-24, 2007, Barcelona, Spain [doi>10.1007/978-3-540-72540-4_33]
• 19: Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell, and Philip MacKenzie. Universally composable password-based key exchange. In Advances in Cryptology---EUROCRYPT 2005, pages 404--21, 2005.
• 20: Ran Canetti , Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.453-474, May 06-10, 2001
• 21: David Chaum. Blind signatures for untraceable payments. In Advances in Cryptology---CRYPTO 1982, pages 199--203, 1982.
• 22: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.41, October 23-25, 1995
• 23: Yevgeniy Dodis and Adam Smith. Entropic security and the encryption of high-entropy messages. In Theory of Cryptography Conference---TCC 2005, 2005.
• 24: Shimon Even, Oded Goldreich, and Abraham Lempel. A randomized protocol for signing contracts. In Advances in Cryptology---CRYPTO 1982, pages 205--10, 1982.
• 25: Dinei Florencio , Cormac Herley, KLASSP: Entering Passwords on a Spyware Infected Machine Using a Shared-Secret Proxy, Proceedings of the 22nd Annual Computer Security Applications Conference, p.67-76, December 11-15, 2006 [doi>10.1109/ACSAC.2006.32]
• 26: Warwick Ford , Burton S. Kaliski, Jr., Server-Assisted Generation of a Strong Secret from a Password, Proceedings of the 9th IEEE International Workshops on Enabling Technologies: Infrastructure for Collaborative Enterprises, p.176-180, June 04-16, 2000
• 27: Steven Galbraith, Kenneth Paterson, and Nigel Smart. Pairings for cryptographers. Cryptology ePrint Archive, Report 2006/165, 2006.
• 28: Craig Gentry , Philip Mackenzie , Zulfikar Ramzan, Password authenticated key exchange using hidden smooth subgroups, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102160]
• 29: Craig Gentry, Philip MacKenzie, and Zulfikar Ramzan. A method for making password-based key exchange resilient to server compromise. In Advances in Cryptology---CRYPTO 2006, LNCS, pages 142--59. Springer-Verlag, 2006.
• 30: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 31: Matthew Green and Susan Hohenberger. Blind identity-based encryption and simulatable oblivious transfer. In Advances in Cryptology---ASIACRYPT 2007, 2007.
• 32: Shai Halevi and Yael Tauman Kalai. Smooth projective hashing and two-message oblivious transfer. Cryptology ePrint Archive, Report 2007/118, 2007.
• 33: Shai Halevi , Hugo Krawczyk, Public-key cryptography and password protocols, Proceedings of the 5th ACM conference on Computer and communications security, p.122-131, November 02-05, 1998, San Francisco, California, United States [doi>10.1145/288090.288118]
• 34: D. N. Hoover and B. N. Kausik. Software smart cards via cryptographic camouflage. In IEEE Symposium on Security and Privacy---SP 1999, 1999.
• 35: Jonathan Katz and Rafail Ostrovsky. Round-optimal secure two-party computation. In Advances in Cryptology---CRYPTO 2004, pages 335--54, 2004.
• 36: Jonathan Katz , Rafail Ostrovsky , Moti Yung, Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.475-494, May 06-10, 2001
• 37: Joe Kilian, Founding crytpography on oblivious transfer, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.20-31, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62215]
• 38: Wakaha Ogata , Kaoru Kurosawa, Oblivious keyword search, Journal of Complexity, v.20 n.2-3, p.356-371, April/June 2004 [doi>10.1016/j.jco.2003.08.023]
• 39: Helger Lipmaa. An oblivious transfer protocol with log-squared communication. Cryptology ePrint Archive, Report 2004/063, 2004.
• 40: Moni Naor , Benny Pinkas, Oblivious Transfer with Adaptive Queries, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.573-590, August 15-19, 1999
• 41: Moni Naor , Benny Pinkas, Efficient oblivious transfer protocols, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.448-457, January 07-09, 2001, Washington, D.C., United States
• 42: Andreas Pashalidis. http://www.kyps.net, 2007.
• 43: Andreas Pashalidis and Chris J. Mitchell. Impostor: a single sign-on system for use from untrusted devices. In Proc. IEEE Globecom 2004, 2004.
• 44: Michael Rabin. How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard University, Aiken Computation Laboratory, 1981.
• 45: Alexander Russell , Hong Wang, How to Fool an Unbounded Adversary with a Short Key, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.133-148, May 02, 2002
• 46: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science, p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

General Terms:
Algorithms, Human Factors, Security

Keywords:
online authentication, partially trusted servers, reusable passwords, stateless roaming credentials