Moderately hard, memory-bound functions

ABSTRACT

A resource may be abused if its users incur little or no cost. For example, e-mail abuse is rampant because sending an e-mail has negligible cost for the sender. It has been suggested that such abuse may be discouraged by introducing an artificial cost in the form of a moderately expensive computation. Thus, the sender of an e-mail might be required to pay by computing for a few seconds before the e-mail is accepted. Unfortunately, because of sharp disparities across computer systems, this approach may be ineffective against malicious users with high-end systems, prohibitively slow for legitimate users with low-end systems, or both. Starting from this observation, we research moderately hard functions that most recent systems will evaluate at about the same speed. For this purpose, we rely on memory-bound computations. We describe and analyze a family of moderately hard, memory-bound functions, and we explain how to use them for protecting against abuses.

REFERENCES

• 1: Abadi, M., Birrell, A., Burrows, M., Dabek, F., and Wobber, T. 2003a. Bankable postage for network services. In Asian 2003. Lecture Notes in Computer Science, vol. 2896. Springer, 72--90.
• 2: Abadi, M., Burrows, M., Manasse, M., and Wobber, T. 2003b. Moderately hard, memory-bound functions. In Proceedings of NDSS 2003 (Networks and Distributed Systems Security). 25--39.
• 3: Abadi, M., Lomas, T. M. A., and Needham, R. 1997. Strengthening passwords. SRC Technical Note 1997--033, Digital Equipment Corporation, Systems Research Center. September/December.
• 4: A. Aggarwal , B. Alpern , A. Chandra , M. Snir, A model for hierarchical memory, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.305-314, January 1987, New York, New York, United States [doi>10.1145/28395.28428]
• 5: Ahn, L., Blum, M., Hopper, N. J., and Langford, J. 2003. CAPTCHA: Using hard AI problems for security. In Advances in Cryptology---EUROCRYPT 2003. Lecture Notes in Computer Science, vol. 2656. Springer, 294--311.
• 6: Astley, M. R. 2001. Repost of private mail re: No free spam. Posting available on the web at URL www.camram.org/mhonarc/spam/msg00030.html.
• 7: Back, A. 1997. HashCash. Available on the web at URL www.cypherspace.org/~adam/hashcash.
• 8: CAMRAM 2002. Welcome to CAMRAM. Available on the web at URL www.camram.org.
• 9: Lorrie Faith Cranor , Brian A. LaMacchia, Spam!, Communications of the ACM, v.41 n.8, p.74-83, Aug. 1998 [doi>10.1145/280324.280336]
• 10: Dwork, C., Goldberg, A., and Naor, M. 2003. On memory-bound functions for fighting spam. In Advances in Cryptology---CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729. Springer, 426--444.
• 11: Cynthia Dwork , Moni Naor, Pricing via Processing or Combatting Junk Mail, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.139-147, August 16-20, 1992
• 12: Amos Fiat , Moni Naor, Rigorous Time/Space Trade-offs for Inverting Functions, SIAM Journal on Computing, v.29 n.3, p.790-803, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795280512]
• 13: Philippe Flajolet , Andrew M. Odlyzko, Random mapping statistics, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.329-354, November 1990, Houthalen, Belgium
• 14: Eran Gabber , Markus Jakobsson , Yossi Matias , Alain J. Mayer, Curbing Junk E-Mail via Secure Classification, Proceedings of the Second International Conference on Financial Cryptography, p.198-213, February 23-25, 1998
• 15: Hellman, M. E. 1980. A cryptanalytic time-memory trade off. IEEE Trans. Info. Theory IT-26, 4, 401--406.
• 16: Markus Jakobsson , Ari Juels, Proofs of Work and Bread Pudding Protocols, Proceedings of the IFIP TC6/TC11 Joint Working Conference on Secure Information Networks: Communications and Multimedia Security, p.258-272, September 20-21, 1999
• 17: Juels, A. and Brainard, J. 1999. Client puzzles: A cryptographic defense against connection depletion. In Proceedings of NDSS '99 (Networks and Distributed Systems Security). 151--165.
• 18: Manber, U. 1996. A simple scheme to make passwords based on one-way functions much harder to crack. Computers & Security 15, 2, 171--176.
• 19: May, T. C. 1993. Timed-release crypto. Unpublished manuscript.
• 20: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 21: Ralph C. Merkle, Secure communications over insecure channels, Communications of the ACM, v.21 n.4, p.294-299, April 1978 [doi>10.1145/359460.359473]
• 22: Oechslin, P. 2003. Making a faster cryptanalytic time-memory trade-off. In Advances in Cryptology---CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729. Springer, 617--630.
• 23: Francois-Xavier Standaert , Gael Rouvroy , Jean-Jacques Quisquater , Jean-Didier Legat, A Time-Memory Tradeoff Using Distinguished Points: New Analysis & FPGA Results, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.593-609, August 13-15, 2002
• 24: R. L. Rivest , A. Shamir , D. A. Wagner, Time-lock Puzzles and Timed-release Crypto, Massachusetts Institute of Technology, Cambridge, MA, 1996

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:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Electronic mail

General Terms:
Algorithms, Security

Keywords:
Spam