Vol.54 No (Sep. 2013) CAPTCHA CAPTCHA CAPTCHA (1) (2) (3) CAPTCHA Assira [3] CAPTCHA CAPTCHA [5], [6] Web [7] 1 CAPTCHA CAPTCHA Web n-gram

Size: px

Start display at page:

Download "Vol.54 No (Sep. 2013) CAPTCHA CAPTCHA CAPTCHA (1) (2) (3) CAPTCHA Assira [3] CAPTCHA CAPTCHA [5], [6] Web [7] 1 CAPTCHA CAPTCHA Web n-gram"

たつやとどろき
5 years ago
Views:

1 Vol.54 No (Sep. 2013) CAPTCHA 1,a) 2,b) , CAPTCHA OCR CAPTCHA CAPTCHA CAPTCHA Proposal of CAPTCHA Using Artificial Synthesis Sentences and Its Security Evaluation Yoshifumi Kamoshida 1,a) Hiroaki Kikuchi 2,b) Received: December 1, 2012, Accepted: June 14, 2013 Abstract: The CAPTCHA is a widely used technique to prevent malicious software, called bot, from obtaining false account. It uses an easy problem for human but difficult for machines to distinguish an input made by a program and one by human. We have proposed a new CAPTCHA testing sentences synthesized from the Markov chain model, called word salad, which is tolerant against malware with an OCR feature, or a crowd sourcing attack, called as relay attack. In this paper, we estimate the security against the attack using proof-reading tool to distinguish the synthesized sentences, and present an improved protocol for the attack. Moreover, we show an experimental result of some languages other than Japanese. Keywords: CAPTCHA, authentication, Marcov chain model, synthesize sentences 1. CAPTCHA [1] CAPTCHA 1 Graduate School of Engineering, Tokai University, Hiratsuka, Kanagawa , Japan 2 School of Interdisciplinary Mathematical Sciences, Meiji University, Nakano, Tokyo , Japan a) y.kamoshida2@gmail.com b) kikn@meiji.ac.jp CAPTCHA OCR [2], [4] [7] CAPTCHA Web 26 FSS2010 DICOMO2012 c 2013 Information Processing Society of Japan 2156

2 Vol.54 No (Sep. 2013) CAPTCHA CAPTCHA CAPTCHA (1) (2) (3) CAPTCHA Assira [3] CAPTCHA CAPTCHA [5], [6] Web [7] 1 CAPTCHA CAPTCHA Web n-gram n 1 1 (1) (2) (3) 1 Microsoft Word 1 Table 1 Samples of corrections for synthesized sentences, words salada CAPTCHA n n [8] n-gram i x i P (x i )=P (x i x i 1,x i 2,...,x i n ) n-gram n-gram n n n-gram n-gram n 1 n n (n + 1)-gram DICOMO c 2013 Information Processing Society of Japan 2157

3 Vol.54 No (Sep. 2013) n =1Microsoft Word CAPTCHA CAPTCHA 3.3 Web Web Web *1 *2 Web 3.4 CAPTCHA 3.5 CAPTCHA h s c = h + s *1 *2 Algorithm 1 1 n 2 h s c 3 c H S 4 k k θ k <θ h/c s/c k k θ CAPTCHA Brute force h s 1/ CAPTCHA Web CAPTCHA CAPTCHA [9], [10] [11], [12] X Y H S P (Y = H X = H) c 2013 Information Processing Society of Japan 2158

4 Vol.54 No (Sep. 2013) P (X = H) = h c P (X = S) = s c =1 h c CAPTCHA P (Y = H, X = H) =P (Y = H X = H)P (X = H) P (Y = S, X = H) =P (Y = S X = H)P (X = H) P (Y = H, X = S) =P (Y = H X = S)P (X = S) P (Y = S, X = S) =P (Y = S X = S)P (X = S) CAPTCHA 2 CAPTCHA P q = P (Y = S, X = H)+P (Y = H, X = S) CAPTCHA k<θ FRR False human Rejection Rate CAPTCHA P m k θ FAR False machine Acception Rate FRR FAR P q P m c ( ) c FRR = P k q (1 P q ) c k k k=θ θ 1 ( ) c = (1 P q ) c k k P q k k=0 c ( ) c FAR = P k m (1 P m ) c k k k=θ FRR = FAR EER Equal Error Rate CAPTCHA h s 1 P mb 1/2 k FAR ) c = h + s =15 θ = k c k=θ ( c k FAR 0.37% W W = t P (W = t) P (W = t) P (W = t) =P (W = t, X = S)+P (W = t, X = H) = P (W = t X = S)P (X = S) (1) + P (W = t X = H)P (X = H) P (X = S W = t) P (X = S W = t) = P (W = t X = S)P (X = S) P (W = t) (2) W = t P (W = f) P (W = f) P (W = f) =P (W = f,x = S)+P (W = f,x = H) = P (W = f X = S)P (X = S) (3) + P (W = f X = H)P (X = H) P (X = H W = f) = P (W = f X = H)P (X = H) P (W = f) (4) Y w W = t S w./p. P (X = S W = t) Y w = (5) H w./p. P (X = H W = t) W = f S w./p. P (X = S W = f) Y w = H w./p. P (X = H W = f) P (Y w = S, X = S) P (Y w = H, X = H) 2 1 CAPTCHA (6) P mw = P (Y w = S, X = S)+P (Y w = H, X = H) (7) P (Y w = S, X = S) (8) = P (Y w = S W = t)p (W = t X = S) + P (Y w = S W = f)p (W = f X = S) P (Y w = H, X = H) (9) = P (Y w = H W = t)p (W = t X = H) + P (Y w = H W = f)p (W = f X = H) c 2013 Information Processing Society of Japan 2159

5 Vol.54 No (Sep. 2013) n =1,...,5 5, s =50 h = h =5 s =10 15 P (Y = H X = H) P (Y = S X = S) Microsoft Word 2007 P (W = t X = S) CAPTCHA , n P (Y = S X = S) P (Y = H X = H) Fig. 1 Probabilities of correct answers with respect to order n, P (Y = S X = S) (detection rate of Spam) and P (Y = X X = H) (accuracy of natural sentence), respectively. 2 n [s] [s] Fig. 2 Response time with respect to order n for synthesized and natural sentences. Wikipedia *3 () MeCab [13] ICTCLAS [14] P (Y = S X = S) P (Y = H X = H) n Order n native foreign Standard Deviation ham *3 Wikipedia, c 2013 Information Processing Society of Japan 2160

6 Vol.54 No (Sep. 2013) 2 P (Y = S X = S) P (Y = H X = H) Table 2 Probabilities of correct answers P (Y = S X = S) and P (Y = H X = H). n =1 n =2 n =3 X = H X = S [ ] Table 3 Response time [second]. n =1 n =2 n =3 X = H X = S P (Y X) 1 n =1 Table 4 Conditional probabilities of answer Y given input X(one sentence, order n =1). 3 θ FRR FAR s =5 h =15 Fig. 3 Security for brute-force attack Distributions of FRR and FAR with respect to theta against brute-force attack. \ Y = H Y = S X = H X = S P (W = t X = S) Table 5 Conditional probabilities of sentence to be corrected given X = S, P (W = t X = S). n =1 n =2 n =3 P (W = t X = S) P (Y = S X = S) Table 6 Detection rates of synthesized sentence for some languages. n =1 n =2 n = n =1 2 P (Y = S X = S) P (Y = H X = H) 2 3 n = n = % n = n 4 ROC Fig. 4 ROC curve against brute-force attack P m =1/2 n =1,...,3 h =5 s =15 θ FRR FAR 3 3 n =1 h =15 s =5 EER θ θ =15 s FRR FAR 4 CAPTCHA FRR EER 3% CAPTCHA Microsoft Word 2007 P (W = t X = S) =0.24 P (W = t X = H) =0 s =15 h =5 c 2013 Information Processing Society of Japan 2161

7 Vol.54 No (Sep. 2013) 7 Y w P (Y w X) Table 7 Conditional probabilities of Spam detection machine Y w given input X. \ Y w = H Y w = S X = H X = S ROC Fig. 6 ROC curves for several attacks. Fig. 5 5 FAR Distributions of FAR for several attacks. H P (X = H) =0.75 S P (X = S) =0.25 (1) 1 P (W = t) =0.06 P (W = f) =0.94 (4) P (X = H W = f) =0.60 P (X = S W = f) =0.40 Y w = H Y w = S P mw 7 P (Y w X) P mw = P (Y = H X = H) =0.5 1 CAPTCHA P mc =0.725 FAR n =1 s =5 h =15 c =20 θ 3 FAR FRR 5 ROC 6 7 P (X = S) P mw P mr Fig. 7 Improvement of accuracy given known probability of Spam P (X = S). EER 23% θ =17 FRR = 24% FAR = 22% θ =18 FRR = 36% FAR = 34% CAPTCHA c =20s h CAPTCHA P mr = P (Y = S, X = S)+P (Y = H, X = H) = P (Y = S)P (X = S)+P (Y = H)P (X = H) ( s ) 2 ( ) 2 h = + c c (7) P mw P mw P mr P (X = S) = s/c 7 7 P w s h P (X = S) =0.55 s h c 2013 Information Processing Society of Japan 2162

8 Vol.54 No (Sep. 2013) 4.5 :5.5 1 CAPTCHA P q EER c =20 s =9 EER = n 5 n =1 EER θ θ = CAPTCHA 8 h s EER 12% 15% Microsoft Word * P (Y = H X = H) *4 8 P (Y = S X = S) Table 8 Comparison of accuracy between with or without detection machine P (Y = S X = S). n =1 W = t W = f P (Y = S X = S) P (Y = H X = H) Table 9 Comparison of accuracies in terms of number of subjects. n =2 n = Wikipedia 10, n =1 Microsoft Word c 2013 Information Processing Society of Japan 2163

9 Vol.54 No (Sep. 2013) 10 Table 10 Detection rate made by attacker without knowledge of language of test sentence. n =1 n =2 n = n n =1 P (Y = S X = S) %5.6 1 CAPTCHA P mc 75% CAPTCHA 1 8 Fig. 8 User interface to improve performance Web 6. CAPTCHA 3 c 2013 Information Processing Society of Japan 2164

10 Vol.54 No (Sep. 2013) [1] The Official CAPTCHA Site, available from [2] Yan, J. and Ahmad, A.S.E.: Breaking Visual CAPTCHAs with Naive Pattern Recognition Algorithms, 2007 Computer Security Applications Conference, pp (2007). [3] Elson, J., Douceur, J., Howell, J. and Saul, J.: Asirra: A CAPTCHA that exploit interest-aligned manual image categorization, ACM CSS 2007, pp (2007). [4] Golle, P.: Machine Learning Attacks Against the ASIRRA CAPTCHA, 2008 ACM CSS, pp (2008). [5] Tygar, J.D. CAPTCHA CSEC-46 No.37 (2009). [6] Tygar, J.D. CAPTCHA pp (2009). [7] CAPTCHA CSEC-48, No.16 (2010). [8] Geyer, J.: Practical Markov Chain Monte Carlo Charles, SCI 1992, Vol.7, No.4, pp (1992). [9] Issac, B.: Improved Bayesian Anti-Spam Filter Implementation and Analysis on Independent Spam Corpuses, ICCET 2009, Vol.2, pp (2009). [10] Zaragoza, H., Gallinari, P. and Rajman, M. (Eds.): Learning to Filter Spam A Comparison of a Naive Bayesian and a Memory-Based Approach, PKDD 2000, pp.1 13 (2000). [11] Larvergne, T. et al.: Detecting Fake Content with Relatine Entropy Scoring, CEVR, Vol.377, pp (2008). [12] N-gram DBS-148, No.24, pp.1 8 (2009). [13] MeCab: Yet Another Part-of-Speech and Morphological Analyzer, available from [14] ICTCLAS, available from Microsoft Word Microsft Word 2007 Microsoft Corporation A.1 5 Table A 1 n 1 3 A 1 5 Sample sentences in English and Japanese used in Experiment 5. Japanese GDP Hum n English With the vast bulk of Englishmen and the Louisiana territory separated from the Southwest, which states were organized on September 17, 1 the 100th century, has been described. In 1507, German cartographer Martin Waldseemuller produced a world map on which he named lands of the Western Hemisphere America after Italian explorer 3 and cartographer Amerigo Vespucci. The United States of Americasis a federal constitutional republic comprising fifty Hum states and a federal district. A 2 5 Table A 2 Sample sentence in Chinese used in Experiment 5. CAPTCHA Microsoft Word c 2013 Information Processing Society of Japan 2165

2000 2006 2008 1997 2013 WIDE FJPEM ICAT IPA 1990 1993 1996 SCIS 2010

11 Vol.54 No (Sep. 2013) TOKAI 2012 DICOMO WIDE FJPEM ICAT IPA SCIS 2010 JIP Outstanding Paper Award 2013 IEEE AINA Best Paper Award IEEE ACM c 2013 Information Processing Society of Japan 2166

IPSJ SIG Technical Report Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for

IPSJ SIG Technical Report Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for 1 2 3 3 1 Secret Tap Secret Tap Secret Flick 1 An Examination of Icon-based User Authentication Method Using Flick Input for Mobile Terminals Kaoru Wasai 1 Fumio Sugai 2 Yosihiro Kita 3 Mi RangPark 3 Naonobu