Harvesting verifiable challenges from oblivious online sources

ABSTRACT

Several important security protocols require parties to perform computations based on random challenges. Traditionally, proving that the challenges were randomly chosen has required interactive communication among the parties or the existence of a trusted server. We offer an alternative solution where challenges are harvested from oblivious servers on the Internet. This paper describes a framework for deriving "harvested challenges" by mixing data from various pre-existing online sources. While individual sources may become predictable or fall under adversarial control, we provide a policy language that allows application developers to specify combinations of sources that meet their security needs. Participants can then convince each other that their challenges were formed freshly and in accordance with the policy. We present Combine, an open source implementation of our framework, and show how it can be applied to a variety of applications, including remote storage auditing and non-interactive client puzzles.

REFERENCES

• 1: Tuomas Aura , Pekka Nikander , Jussipekka Leiwo, DOS-Resistant Authentication with Client Puzzles, Revised Papers from the 8th International Workshop on Security Protocols, p.170-177, April 03-05, 2000
• 2: Adam Back. Hashcash - a denial of service counter-measure. http://www.hashcash.org/hashcash.pdf, 2002.
• 3: Mihir Bellare , Sara K. Miner, A Forward-Secure Digital Signature Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.431-448, August 15-19, 1999
• 4: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 5: Nikita Borisov, Computational Puzzles as Sybil Defenses, Proceedings of the Sixth IEEE International Conference on Peer-to-Peer Computing, p.171-176, September 06-June 08, 2006 [doi>10.1109/P2P.2006.10]
• 6: Giovanni Di Crescenzo, Richard J. Lipton, and Shabsi Walfish. Perfectly secure password protocols in the bounded retrieval model. In TCC, pages 225--244, 2006.
• 7: Drew Dean , Adam Stubblefield, Using client puzzles to protect TLS, Proceedings of the 10th conference on USENIX Security Symposium, p.1-1, August 13-17, 2001, Washington, D.C.
• 8: Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, and Ran Raz. Improved randomness extraction from two independent sources. In APPROX-RANDOM, pages 334--344, 2004.
• 9: John R. Douceur, The Sybil Attack, Revised Papers from the First International Workshop on Peer-to-Peer Systems, p.251-260, March 07-08, 2002
• 10: 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
• 11: J. Galvin , S. Murphy , S. Crocker , N. Freed, Security Multiparts for MIME: Multipart/Signed and Multipart/Encrypted, RFC Editor, 1995
• 12: Ari Juels and John G. Brainard. Client puzzles: A cryptographic countermeasure against connection depletion attacks. In NDSS, 1999.
• 13: Martijn Koster. A standard for robot exclusion. http://www.robotstxt.org/wc/norobots.html, 1994.
• 14: Ramakrishna Kotla , Lorenzo Alvisi , Mike Dahlin, SafeStore: a durable and practical storage system, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
• 15: National Solar Observatory/Sacramento Peak. Images and current data. http://nsosp.nso.edu/data/.
• 16: USGS Earthquake Hazards Program. Latest earthquakes in the world - past 7 days. http://earthquake.usgs.gov/eqcenter/recenteqsww/Quakes/quakes all.php.
• 17: RSS 2.0 specification. http://blogs.law.harvard.edu/tech/rss, 2003.
• 18: Technorati: About us. http://www.technorati.com/about/, 2007.
• 19: XiaoFeng Wang , Michael K. Reiter, Defending Against Denial-of-Service Attacks with Puzzle Auctions, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.78, May 11-14, 2003
• 20: Brent Waters , Ari Juels , J. Alex Halderman , Edward W. Felten, New client puzzle outsourcing techniques for DoS resistance, Proceedings of the 11th ACM conference on Computer and communications security, October 25-29, 2004, Washington DC, USA [doi>10.1145/1030083.1030117]

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:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Design, Security