Machine learning attacks against the Asirra CAPTCHA

ABSTRACT

The Asirra CAPTCHA [EDHS2007], proposed at ACM CCS 2007, relies on the problem of distinguishing images of cats and dogs (a task that humans are very good at). The security of Asirra is based on the presumed difficulty of classifying these images automatically.

In this paper, we describe a classifier which is 82.7% accurate in telling apart the images of cats and dogs used in Asirra. This classifier is a combination of support-vector machine classifiers trained on color and texture features extracted from images. Our classifier allows us to solve a 12-image Asirra challenge automatically with probability 10.3%. This probability of success is significantly higher than the estimate of 0.2% given in [EDHS2007] for machine vision attacks. Our results suggest caution against deploying Asirra without safeguards.

We also investigate the impact of our attacks on the partial credit and token bucket algorithms proposed in [EDHS2007]. The partial credit algorithm weakens Asirra considerably and we recommend against its use. The token bucket algorithm helps mitigate the impact of our attacks and allows Asirra to be deployed in a way that maintains an appealing balance between usability and security. One contribution of our work is to inform the choice of safeguard parameters in Asirra deployments.

References

1. ASR Asirra: A Human Interactive Proof. On the Web at http://research.microsoft.com/asirra/
2. BotBarrier.com. On the web at http://www.botbarrier.com/
3. Chih-Chung Chang and Chih-Jen Lin. LIBSVM : a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm
4. . Chow, P. Golle, M. Jakobsson, X. Wang and L. Wang. Making CAPTCHAs Clickable. In Proc. of HotMobile 2008.
5. . Cortes and V. Vapnik. Support-vector network. Machine Learning 20, 273--297, 1995.
6. . Douceur and J. Elson. Private communication.
7. . Elson, J. Douceur, J. Howell and J. Saul. Asirra: a CAPTCHA that exploits interest-aligned manual image categorization. In Proc. of ACM CCS 2007, pp. 366--374.
8. . Golle and D. Wagner. Cryptanalysis of a Cognitive Authentication Scheme. In Proc. of the 2007 IEEE Symposium on Security and Privacy, pp.66--70. IEEE Computer Society
9. Google CAPTCHA. On the web at https://www.google.com/accounts/DisplayUnlockCaptcha
10. . Hastie, R. Tibshirani and J. Friedman. The Elements of Statistical Learning (Data Mining, Inference, and Prediction). Springer Series in Statistics, 2001.
11. . Kruizinga, N. Petkov and S.E. Grigorescu. Comparison of texture features based on Gabor filters. In Proc. of the 10th International Conference on Image Analysis and Processing (1999), pp. 142--147.
12. . Lopresti. Leveraging the CAPTCHA problem. In Proc. of the Second International Workshop on Human Interactive Proofs, pp. 97--110. Springer Verlag, 2005.
13. . Mironov and L. Zhang. Applications of SAT Solvers to Cryptanalysis of Hash Functions. In Theory and Applications of Satisfiability Testing -- SAT 2006, pp. 102--115, 2006.
14. . Mori and J. Malik. Recognizing objects in adversarial clutter: Breaking a visual CAPTCHA. In Proc. of the 2003 Conference on Computer Vision and Pattern Recognition, pp. 134--144. IEEE Computer Society, 2003.
15. SlashDot. Yahoo CAPTCHA Hacked (posted Jan 29, 2008). On the Web at http://it.slashdot.org/it/08/01/30/0037254.shtml
16. Websense Blog (posted Feb 22, 2008). Google's CAPTCHA busted in recent spammer tactics. On the web at http://securitylabs.websense.com/content/Blogs/2919.aspx
17. . Yan and A. El Ahmad. A Low-cost Attack on a Microsoft CAPTCHA. To appear in Proc. of ACM CCS 2008.

Index Terms

• Security and privacy

• Social and professional topics

  • Computing / technology policy

    • Computer crime