POSH: a generalized captcha with security applications

ABSTRACT

A puzzle only solvable by humans, or POSH, is a prompt or question with three important properties: it can be generated by a computer, it can be answered consistently by a human, and a human answer cannot be efficiently predicted by a computer. In fact, unlike a CAPTCHA, a POSH does not necessarily have to be verifiable by a computer at all. One application of POSHes is a scheme proposed by Canetti et al.~that limits off-line dictionary attacks against password-protected local storage, without the use of any secure hardware or secret storage.

We explore the area of POSHes, implement several candidate POSHes and have users solve them, to evaluate their effectiveness. Given these data, we then implement the above scheme as an extension to the Mozilla Firefox web browser, where it is used to protect user certificates and saved passwords. In the course of doing so, we also define certain aspects of the threat model for our implementation (and the scheme) more precisely.

REFERENCES

• 1: Bank of America. How Bank of America SiteKey Works for Online Banking Security. http://www.bankofamerica.com/privacy/sitekey/.
• 2: R. Canetti and R. R. Dakdouk. Obfuscating point functions with multibit output. In EUROCRYPT, pages 489--508, 2008.
• 3: R. Canetti, S. Halevi, and M. Steiner. Mitigating dictionary attacks on password--protected local storage. In CRYPTO, pages 160--179, 2006.
• 4: W. Daher. Patch for Firefox. http://puzzles.mit.edu/firefox/patch.diff, April 2008.
• 5: Darren Davis , Fabian Monrose , Michael K. Reiter, On user choice in graphical password schemes, Proceedings of the 13th conference on USENIX Security Symposium, p.11-11, August 09-13, 2004, San Diego, CA
• 6: Rachna Dhamija , Adrian Perrig, Déjà Vu: a user study using images for authentication, Proceedings of the 9th conference on USENIX Security Symposium, p.4-4, August 14-17, 2000, Denver, Colorado
• 7: D. Engel. Pictionary (NES) FAQ by DEngel. http://www.gamefaqs.com/console/nes/file/587510/38806, April 2007. Section (E): Answer List.
• 8: H. T. Hall. Tracy Hall's Amazing Inkblot Generator. http://math.berkeley.edu/~hthall/ink.blots/, January 2001.
• 9: Ian Jermyn , Alain Mayer , Fabian Monrose , Michael K. Reiter , Aviel D. Rubin, The design and analysis of graphical passwords, Proceedings of the 8th conference on USENIX Security Symposium, p.1-1, August 23-26, 1999, Washington, D.C.
• 10: M. Naor. Verification of a human in the loop or Identification via the Turing Test. http://www.wisdom.weizmann.ac.il/~naor/PAPERS/human_abs.html, 1996.
• 11: H.-K. Nienhuys. HKCaptcha -- yet another PHP Captcha implementation. http://www.lagom.nl/linux/hkcaptcha/, February 2008.
• 12: Open Source Shakespeare. Shakespeare text statistics. http://www.opensourceshakespeare.org/stats/.
• 13: Benny Pinkas , Tomas Sander, Securing passwords against dictionary attacks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586133]
• 14: Stuart E. Schechter , Rachna Dhamija , Andy Ozment , Ian Fischer, The Emperor's New Security Indicators, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.51-65, May 20-23, 2007 [doi>10.1109/SP.2007.35]
• 15: P. Sinha, B. Balas, Y. Ostrovsky, and R. Russell. Face Recognition by Humans: Nineteen Results all Computer Vision Researchers Should Know About. In Proceedings of the IEEE, volume 94, pages 1948--1962, 2006.
• 16: A. Stubblefield and D. Simon. Inkblot authentication. Technical Report MSR-TR-2004-85, Microsoft Research, 2004.
• 17: Julie Thorpe , P. C. van Oorschot, Graphical dictionaries and the memorable space of graphical passwords, Proceedings of the 13th conference on USENIX Security Symposium, p.10-10, August 09-13, 2004, San Diego, CA
• 18: L. von Ahn. reCAPTCHA. http://www.recaptcha.net, 2007.
• 19: Luis von Ahn , Manuel Blum , John Langford, Telling humans and computers apart automatically, Communications of the ACM, v.47 n.2, p.56-60, February 2004 [doi>10.1145/966389.966390]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

Additional Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Unauthorized access (e.g., hacking, phreaking)

General Terms:
Experimentation, Human Factors, Security

Keywords:
password security, puzzles