Abstract
We introduce a formal model, which we call the Bounded Retrieval Model, for the design and analysis of cryptographic protocols remaining secure against intruders that can retrieve a limited amount of parties’ private memory. The underlying model assumption on the intruders’ behavior is supported by real-life physical and logical considerations, such as the inherent superiority of a party’s local data bus over a remote intruder’s bandwidth-limited channel, or the detectability of voluminous resource access by any local intruder. More specifically, we assume a fixed upper bound on the amount of a party’s storage retrieved by the adversary. Our model could be considered a non-trivial variation of the well-studied Bounded Storage Model, which postulates a bound on the amount of storage available to an adversary attacking a given system.
In this model we study perhaps the simplest among cryptographic tasks: user authentication via a password protocol. Specifically, we study the problem of constructing efficient password protocols that remain secure against offline dictionary attacks even when a large (but bounded) part of the storage of the server responsible for password verification is retrieved by an intruder through a remote or local connection. We show password protocols having satisfactory performance on both efficiency (in terms of the server’s running time) and provable security (making the offline dictionary attack not significantly stronger than the online attack). We also study the tradeoffs between efficiency, quantitative and qualitative security in these protocols. All our schemes achieve perfect security (security against computationally-unbounded adversaries). Our main schemes achieve the interesting efficiency property of the server’s lookup complexity being much smaller than the adversary’s retrieval bound.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-540-32732-5_32
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Axelsson, S.: Research in Intrusion-Detection systems: A Survey, in Technical Report 98–17, Dept. of Comp. Eng., Chalmers, Univ. of Technology, Goteborg, Sweden (1998), http://citeseer.ist.psu.edu/axelsson98research.html
Bellovin, S., Merrit, M.: Encrypted Key Exchange. In: Proc. of the 1992 Internet Society Network and Distributed System Security Symposium (1992)
Bellovin, S., Merrit, M.: Augmented Encrypted Key Exchange. In: Proc. of the 1st ACM Conference on Computer and Communication Security, pp. 224–250
Blakley, G.R.: Safeguarding cryptographic keys. In: Proc. of the National Computer Conference, vol. 48, pp. 242–268 (1979)
Di Crescenzo, G., Ghosh, A., Talpade, R.: Towards a Theory of Intrusion Detection. In: di Vimercati, S.d.C., Syverson, P.F., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 267–286. Springer, Heidelberg (2005)
Dodis, Y., Sahai, A., Smith, A.: On Perfect and Adaptive Security in Exposure- Resilient Cryptography. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 301–324. Springer, Heidelberg (2001)
Password Protocols provably secure in the Bounded Retrieval Model, first public version of this work, unpublished draft (April 2005)
Feldmeier, D.C., Karn, P.R.: UNIX Password Security - Ten Years Later. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 44–63. Springer, Heidelberg (1990)
Halevi, S., Krawczyk, H.: Public-key Cryptography and Password Protocols. In: Proc. of the 5th annual ACM conference on Computer and Communications Security, pp. 122–131 (1998)
Kelsey, J., Schneier, B.: Authenticating Secure Tokens Using Slow Memory Access. In: USENIX Workshop on Smart Card Technology, pp. 101–106. USENIX Press (1999)
Lu, C.-J.: Encryption against storage-bounded adversaries from on-line strong extractors. Journal of Cryptology 17(1), 27–42 (2004)
Dziembowski, S., Maurer, U.: Optimal Randomizer Efficiency in the Bounded-Storage Model. Journal of Cryptology 17(1), 5–26
Maurer, U.: Conditionally-Perfect Secrecy and a Provably-Secure Randomized Cipher. Journal of Cryptology 5(1), 53–66 (1992)
Moran, T., Shaltiel, R., Ta-Shma, A.: Non-interactive Timestamping in the Bounded Storage Model. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 460–476. Springer, Heidelberg (2004)
Morris, R., Thompson, K.: Password Security: A Case History. Communications of the ACM 22(11), 594–597 (1979)
Nisan, N., Ta-Shma, A.: Extracting Randomness: A Survey and New Constructions. Journal of Computer and System Sciences 58(1), 148–173 (February 1999)
Nisan, N., Zuckerman, D.: More Deterministic Simulation in Logspace. In: Proc. of ACM STOC 1993 (1993)
Patel, S.: Number theoretic attacks on secure password schemes. In: Proc. of the 1997 IEEE Symposium on Security and Privacy (1997)
Pinkas, B., Sander, T.: Securing Passwords Against Dictionary Attacks. ACM CCS-9: Computer and Communications Security (November 2002)
Provos, N., Mazieres, D.: A Future-Adaptable Password Scheme. In: Proceedings of the Annual USENIX Technical Conference (1999)
Reingold, O., Vadhan, S., Wigderson, A.: Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. In: Electronic Colloquium on Computational Complexity TR01-018; other versions in Proceedings of FOCS 2000 and Annals of Mathematics, vol. 155, pp. 157–187 (2002)
Shamir, A.: How to Share a Secret. Communications of the ACM 22(11) (November 1979)
Shaltiel, R.: Recent developments in Explicit Constructions of Extractors. Bulletin of the EATCS 77, 67–95 (2002)
Sipser, M.: Randomness and Time vs. Space. Journal of Computer and System Sciences 36 (1988)
Vadhan, S.P.: On constructing locally computable extractors and cryptosystems in the bounded storage model. Journal of Cryptology 17(1), 43–77 (2004)
Wu, T.: The secure remote password protocol. In: Proc. of the 1998 Internet Society Network and Distributed System Security Symposium (1998)
http://www.detnews.com/2005/technology/0506/18/tech-219662.htm
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Crescenzo, G., Lipton, R., Walfish, S. (2006). Perfectly Secure Password Protocols in the Bounded Retrieval Model. In: Halevi, S., Rabin, T. (eds) Theory of Cryptography. TCC 2006. Lecture Notes in Computer Science, vol 3876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11681878_12
Download citation
DOI: https://doi.org/10.1007/11681878_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32731-8
Online ISBN: 978-3-540-32732-5
eBook Packages: Computer ScienceComputer Science (R0)