CAPTCHA is fundamentally broken

bulaohu

by a chink ;) 理论正确率为46.75%，完全可以认为是破解了

http://homepages.cs.ncl.ac.uk/jeff.yan/google.pdf

[ 本帖最后由 bulaohu 于 2011-10-13 06:49 编辑 ]

psaux

如果无噪，只是字母扭曲，理论上是可以自动电脑识别的。这让我想起读书时选修过一门Artificial Intelligence，在学到其中image processing章节时的一个assignment就是给你一张照片，背景纯白，里面有5个图钉随意摆放，写一个c程序，用fourier transform公式找到所有图钉盖的中心点。

bulaohu

扭曲的作用不大，现在最主要的对抗AI的技术是把字母连成一片，但这个中国人的研究基本上打破了这个，在更好的CAPTCHA出现之前，我们会看到大量的spam了

Limitless

足迹的gif也被我破了……识别率90%。在做一个新算法应该能到95%

google的这个破解被大规模应用之后，估计会开始用另外一种形式的captcha，计算机暂时还没办法的，比如，name 3 animals in this picture，但是随着人工智能的发展马上也要完蛋……像新浪的那种什么“晴天时天空是什么颜色？”之类的问题，iphone4的siri都能破解了……

[ 本帖最后由 Limitless 于 2011-10-15 23:50 编辑 ]

Limitless

看了一编，没用什么太复杂的东西，就是一些创新的算法用来分割，待会按照里面说的写一个出来试试，我感觉有提高识别率的潜力，里面很多地方可以改进算法。

混不到坑的萝卜

下一代可以搞那种鉴定色盲用的彩色不规则背景不？

不会游泳的鱼

还有人肉破解的呢，破1000个1美刀，据说很多阿三在做。

鱼羊鲜

道高一尺魔髙一丈

franknet

原帖由 bulaohu 于 2011-10-13 06:36 发表
by a chink ;) 理论正确率为46.75%，完全可以认为是破解了

http://homepages.cs.ncl.ac.uk/jeff.yan/google.pdf

那好像是三个人一起做的吧？！另两个是中东的吧。

kr2000

captcha为什么这么流行呢，我经常都看不清
一些puzzle的验证，比如给个简单的问题， 或者数学题之类的，挺好

heroxk

一点也不玄乎，其实有很多种方法可以做的。

比如，开始可以edge detection，image segmentation把target characters提取出来，然后用signal/image processing的方法比如wavelet，correlation，或者用pattern recognition/machine learning的方法比如Neural network, SVM什么的。

技术上面早就不成问题了，和手写签名识别一个道理，都是在有distortion（扭曲）的情况下做pattern recognition。识别没什么难的，主要就是False positive rate 和 false negtive rate，说白了就是识别率高和低的问题。其实错了也无所谓，多识别几次就是了。

只不过搞这个干啥子呢，现阶段有这个精力能力的人都去搞3d face recognition去了，开发个产品就有可能直接赚钱。

key

应该有一定难度吧。手写识别毕竟不是故意针对计算机做混淆

原帖由 heroxk 于 2011-10-23 12:44 发表
一点也不玄乎，其实有很多种方法可以做的。

比如，开始可以edge detection，image segmentation把target characters提取出来，然后用signal/image processing的方法比如wavelet，correlation，或者用pattern recognition/machin ...

heroxk

原帖由 key 于 2011-10-23 16:01 发表
应该有一定难度吧。手写识别毕竟不是故意针对计算机做混淆

签名的随机性更高，和心情(奋笔疾书还是慢慢写)，书写的介质（比如打滑的信用卡背面还是纸上）甚至是签名区域的大小都有关系。从原理上说，计算机的产生的随机性是可以用统计方法预测的，就像计算机产生的随机数，都是可以破的，只要知道seed就行了，所以计算机无法产生真正的随机数，都是pseudo-random number，所谓的伪随机序列本来就是deterministic的。

从人的角度来看，是通过signature来判断一个人是张三还是李四难，还是分辨CAPTCHA难？要想准确判断，前者一般都要有经验的人，最好是公安局的专家，而CAPTCHA几乎人人都可以肉眼辨别。所以human觉得越难判断，Machine learning等statistical方法也会觉得更难判断。

[ 本帖最后由 heroxk 于 2011-10-23 17:57 编辑 ]

Limitless

原帖由 heroxk 于 2011-10-23 12:44 发表
一点也不玄乎，其实有很多种方法可以做的。

比如，开始可以edge detection，image segmentation把target characters提取出来，然后用signal/image processing的方法比如wavelet，correlation，或者用pattern recognition/machin ...

是这样的没错，很多验证码过于纠结于干扰文字的识别，比如加一堆干扰线，用很复杂的背景，我本来走了很多弯路，用各种算法把什么干扰线背景去掉，现在发现只要用一个算法把文字突出，其余的去掉就好。google的验证码就比较聪明，背景就是白色的，主要难度在于分割。理论上来说，电脑对于captcha的识别率可以等于人的识别率，并且在速度上无上限。关键在于算法。

bulaohu

原帖由 kr2000 于 2011-10-23 12:08 发表
captcha为什么这么流行呢，我经常都看不清
一些puzzle的验证，比如给个简单的问题， 或者数学题之类的，挺好

有了Wolfram Alpha之类的computational engine，那种CAPTCHA变得很容易破解

heroxk

原帖由 Limitless 于 2011-10-23 17:32 发表


是这样的没错，很多验证码过于纠结于干扰文字的识别，比如加一堆干扰线，用很复杂的背景，我本来走了很多弯路，用各种算法把什么干扰线背景去掉，现在发现只要用一个算法把文字突出，其余的去掉就好。google的验证码就比较聪明，背景就是白色的，主要难度在于分割。理论上来说，电脑对于captcha的识别率可以等于人的识别率，并且在速度上无上限。关键在于算法。

这位老兄说的挺有意思的。我不是搞这个的，也对这没啥兴趣，所以也就简单说说 my intuitive solutions

比如加一堆干扰线，用很复杂的背景，我本来走了很多弯路，用各种算法把什么干扰线背景去掉，现在发现只要用一个算法把文字突出，其余的去掉就好。
这种比较简单，有的甚至可以单用颜色RGB就可以分割，抠出字了后，如果distortion不严重，用training好的字母的template套一套就好了。

google的验证码就比较聪明，背景就是白色的，主要难度在于分割。
google的这种是带distortion的，假设transformation的方程/模型是F(x)=y，那么设法找到反函数F(y)=x，也就是反变换。从transformed domain （变形域）回到 original domain（原始域）
还有一种方法是从feature的角度出发，找稳定的特征，比如字母各个比划之间的连通性，比如O和C，O是封闭的。再比如L和O，I的质心在笔画上，而O的质心不在笔画上。
形状再怎么扭曲，连通性、质心等一些特征肯定不会变，否则，人也识别不出来了。

kane2001

原帖由 kr2000 于 2011-10-23 12:08 发表
captcha为什么这么流行呢，我经常都看不清
一些puzzle的验证，比如给个简单的问题， 或者数学题之类的，挺好

比如这个网站的?

http://random.irb.hr/signup.php

[ 本帖最后由 kane2001 于 2011-10-23 23:30 编辑 ]

heroxk

原帖由 kane2001 于 2011-10-23 23:28 发表

比如这个网站的?
469700
http://random.irb.hr/signup.php

这让没学过calculus的鬼佬们情何以堪。

key

手写识别与签名识是不一样的，用的是不同的算法。

原帖由 heroxk 于 2011-10-23 16:26 发表


签名的随机性更高，和心情(奋笔疾书还是慢慢写)，书写的介质（比如打滑的信用卡背面还是纸上）甚至是签名区域的大小都有关系。从原理上说，计算机的产生的随机性是可以用统计方法预测的，就像计算机产生的随机数，都是可以破的，只 ...

黑山老妖

原帖由 kane2001 于 23/10/2011 23:28 发表

比如这个网站的?
469700
http://random.irb.hr/signup.php

我早就把大学的东西还给教授了。
到了这个网站我都不是人了。。。情何以堪啊。。。

Limitless

原帖由 kane2001 于 2011-10-23 23:28 发表

比如这个网站的?
469700
http://random.irb.hr/signup.php

这种其实挺好办的，因为没有任何干扰，可以100%的把每种符号都ocr出来，然后用程序转换成可以给电脑计算的算式，比如把平方换成^之类的，之后就简单了，matlab或者干脆WoflramAlpha……

kr2000

关键是你不知道对方出神马类型的题
各种puzzle混在一起的题库，出题容易，解题难

原帖由 Limitless 于 2011-10-24 18:20 发表


这种其实挺好办的，因为没有任何干扰，可以100%的把每种符号都ocr出来，然后用程序转换成可以给电脑计算的算式，比如把平方换成^之类的，之后就简单了，matlab或者干脆WoflramAlpha……

Limitless

原帖由 kr2000 于 2011-10-24 22:16 发表
关键是你不知道对方出神马类型的题
各种puzzle混在一起的题库，出题容易，解题难

根据出现概率来找，专门针对出现概率高并且题目容易的类型就好了，难的直接刷新换个新的。