Monday, June 11, 2007

The end of CAPTCHA? - hardly

The NYT has an article predicting the end of CAPTCHAs, or rather their replacement with a new type of test.

I don't think we have seen the end of the CAPTCHA. Like passwords they are easy to implement and have a high ratio of perceived security to cost. Designers like to sprinkle them liberally onto their Web sites as 'magical anti-bot pixie-dust'.

The problem with CAPTCHAs and their replacements is that the problems chosen are hard for computers to solve because until recently there was no incentive to solve them. Back in 2000 there was nobody who was spending their time trying to OCR on text that had been deliberately obfuscated with lines, distortion, etc. Today there are plenty of folk in Eastern Europe and Russia who have become experts at it.

Asking folk to pick out all the cats from a mixture of cats and dogs may appear hard today, but wait a couple of weeks after deployment and see if it is still so hard.

And there is also the systems attack. Methinks that Microsoft do not have a very large catalog of photographs to show to users, maybe a thousand, maybe a hundred thousand. The attackers don't need to build a machine to sort the pictures out, they can have people do that for them. They can use the man-in-the-middle porn site attack or just pay folk to do it for them. All they need to do once the pictures are sorted is to undo whatever obfustication is in place to prevent simple matching of the photographs.

Bruce Schneier often remarks that anyone can design an encryption scheme that they cannot break themselves. In the area of CAPTCHAs I can't do that. I can break every scheme I have seen and I can break every scheme I can think of.

Update: Welcome TPM visitors. Following Josh's link it turns out that the database of pet pictures has two million entries. More significant though is the rate of addition - 10,000 a day. This is an order of magnitude higher than my original guess, but I don't think it invalidates the suggested lines of attack.

The hard part is cataloging the original database - ten man years worth of effort. That is certainly going to cost more than the $5,000 the Kiev gang would charge for breaking a text CAPTCHA. Unfortunately certain organized crime rings have repeatedly demonstrated that they have the necessary level of resources to simply pay people to break the problems by brute force.

Once the main catalog is sorted it is quite easy to keep up as it turns out that Asirra has a 'tell'. If you have 90% of the catalog archived and the images are selected randomly the chances are that you will only be presented with one unknown image per test. Since Asirra requires the subject to be 100% correct a cataloging bot can tell whether the unknown image was a dog or a cat by whether it passed the test or not. A simple way to fix this tell would be to weaken the match criteria so that 9 out of 10 correct answers was sufficient, but this opens up the door to other attacks.

The other weakness I see in the approach is asking image recognition experts to estimate the difficulty of differentiating pictures of cats from pictures of dogs. It isn't the right test. The hidden assumption here is that the best attack is going to solve the problem the way a human would. Thats not the way internet criminals think. Ants solve similar problems every day with 100,000 total neurons.

Update 2: it appears that the code as implemented, as opposed to the documentation allows one wrong answer out of 12. Turns out that it does not defeat the automatic cataloging attack described earlier as I assumed. In order to use the automatic cataloging trick the attacker would have to present ten correct tries, and one deliberately wrong try together with the unknown picture.

88 comments:

Tim said...

I saw an interesting technique on a blog the other day that did away with images all together. It simply prompted the user to answer a question: 'What color is an orange?' Seems like it might be difficult to design something capable of overcoming a shifting series of simple questions like that. Especially if, instead of a pre-set database of questions, the administrator simply came up with a sufficiently random question off the top of his head every so often, which doesn't seem too demanding.

Fel said...

wow, cool post, dood.

The Eagle of Evanston said...

Microsoft is claiming over 2 million photos. That doesn't invalidate your point, but Microsoft at least is making the bar a little higher than you mention.

DaveBH said...
This comment has been removed by a blog administrator.
Nicholas Weaver said...

What everyone seems to miss is the subtitle of the original CAPTCHA paper: "How Lazy Cryptographers Do AI".

From the academic/crypto viewpoint, people breaking CAPTCHAs is good becasue the goal is to force them to solve an otherwise hard and annoying problem (eg, character recognition when things are really distorted).

PHB said...

I just turned CAPTCHA on for posting comments, could not resist the irony.

I had not seen the final paper How Lazy Cryptographers do AI but it is worth a read and as is often the case the inventors of the scheme are more than aware of the weaknesses that later deployments blithely ignore.

The problem here is that the CAPTCHA technology was designed before professional Internet crime was widely acknowledged as a problem. Any CAPTCHA test is certainly sufficient to block vote fraud, stopping crime is quite a different matter. Whoever is paying $5,000 to break CAPTCHAs is creating one heck of a lot of accounts somewhere.

An amusing side note: if you have read Doonesbury you will know that Alex went to MIT after an online poll where the MIT students proved to be better at stuffing the ballot than CMU.

Josh Yelon said...

Actually, it's much harder to solve than you think. I'm using this captcha on our forums:

http://panda3d.org/phpbb2/

Click on the "register" link to see the captcha. The forum admin is expected to drop in their own photographs. This is as simple as copying them from your digital camera into the image directory. Furthermore, the forum admin can choose any two kinds of objects, not just cats and dogs. If you give the forum admin this range of choice, then effectively, every website has its own custom captcha.

Gadfly said...

How much more, or less, secure than capchas are things such as my one Senator's website uses, where you have to choose word No. 5, or whatever, from a list of eight, and the count varies whether top-down or bottom-up?

PHB said...

In response to Gadfly, schemes like that are perfectly secure until they are used widely enough to provide an incentive to an attacker.

drfu said...

given a large collection of search terms, couldn't this image CAPTCHA be implemented through Google images? This could save you a hell of a lot in storage, bandwidth and cataloging -- no need to index the damned things, let Google do it for you... send two queries to Google image search ('cat' and 'dog'), cache the top 5 of the resulting images to your local server, present the images, then ask the user to pick one of the images that is of a cat. No need to obfuscate the image, since the odds of you using it again are quite slight.

I think that with the image labeling business Google Image Labeler you could get even better assurance that what you present really does have something to do with your search.

PHB said...

DrFu

Google images tends to be a counter-example. What Google can do automatically the attackers can do automatically.

The cost to the attacker is proportional to the cost to the defender here, there is no exponential leverage.

Anonymous said...

Web Art Sense a web design company is here for a purpose to make art and design of your imagination alive and real on the web platform. After several months of hunting of the best talent and struggling for the name of their design company they finally reached a vertical which engages their vision of togetherness. The best talented people in web designs have joined hands to compete and provide innovative, unique concepts to users/clients all across the globe. Web Art Sense is not any design company; they take real care of having your brands be presented that invokes your revelation to others who see it.

Web Art Sense has their sales offices in London, New Jersey and New Delhi are heading towards marketing themselves to main continents of Europe, Australia and America. Web art sense already has ground foundation and is providing web based design development and SEO Services in countries like USA, UK, Australia and Italy. Web Art Sense has been growing above hundred percent every financial year since its foundation.
Web Design Company

Web Art Sense a leading web design company, affordable web design, web development, ecommerce, XHTML Services. Web Design Company offers a complete collection of web design solutions for business. Web Art Sense team of professionals with proven knowledge in the field of web design & development are skilled of providing high quality, e commerce websites, development and website redesign & maintenance solutions.

Ray Creations said...

Thank you for this nice post. Website Hosting | windows hosting

Ray Creations said...

Thanks for such an informative post.
Web Developer  |   Web Design

Anonymous said...

Captchas are sometimes really irritating. Especially for the fact that they are at times so difficult to read. Why can't they be made for easier human reading? Web Designer Web Hosting

Niya said...

Quite informative post! Thanks!!

Regards,
photoshop masking

vishal said...

Earning money has online never been this easy and transparent. You would find great tips on how to make that dream amount every month. So go ahead and click here for more details and open floodgates to your online income. All the best.
Thanks.

cheapcallstophone said...

Great Post.Web Design Company India

zcocorporation said...
This comment has been removed by the author.
Sameer said...

nice post....web designing company noida

cheapcallstophone said...

Very nice and informative article thanks for sharing

SEO UK

Unknown said...

Really looking forward to the next few days when people start properly aggregating this information.Will be interesting to see if what Google reports seem to match the studies we have done on the basis of your experiments for our Seo Company India website

seouk1 said...
This comment has been removed by the author.
Unknown said...

for that awesome posting. It saved MUCH time :-)
------------------------------
numerology predictions

Steave said...

Thanks for taking this opportunity to discuss this, I feel fervently about this and I like learning about this subject.
------------------------
Sarrell Dental Center

Anonymous said...

It's hard to find quality writing like yours these days. I really appreciate people like you! Take care and see you soon
Printing Services

Unknown said...

Outstanding job! The comprehensive data delivered was very useful. I am hoping that you keep up the good job succesfully done.
Locksmith San Jose CA

SEO Services Consultants said...

Hello! I just would like to give a huge thumbs up for the great info you have here on this post. I will be coming back to your blog for more soon.

Uk Ties

SEO Services Consultants said...

This is a GREAT post! I hope you not mind.I published an excerpt on the site and linked back to your own blog for people to read the full version. Thanks for your advice.strumpfhosen

Harry Seo said...

Forniamo ai nostri clienti servizi di sviluppo di siti web e servizi di web design.Realizzazione Sito

Harry Seo said...

ESG Appliance is an appliance repair and service company operating in the Los Angeles and Orange counties and providing Installation, Service and Maintenance for appliances like Ice Maker, Microwave Oven, Washer Dryer.Washer Dryer

SEO Services Consultants said...

I just wanted to add a comment here to mention thanks for you very nice ideas. Blogs are troublesome to run and time consuming thus I appreciate when I see well written material. Your time isn’t going to waste with your posts. Thanks so much and stick with it No doubt you will definitely reach your goals! have a great day!


virtual assistant

SEO Services Consultants said...

This is a GREAT post! I hope you not mind.I published an excerpt on the site and linked back to your own blog for people to read the full version. Thanks for your advice.
Price trades

SEO Services Consultants said...

This is a good common sense article. Very helpful to one who is just finding the resources about this part. It will certainly help educate me.

Virtual Administrative Assistant

tango tango said...

Wow, Fantastic article, it’s so helpful to me, and your blog is very good,

Tango i oslo

biditcheap said...

Wow, Fantastic article, it’s so helpful to me, and your blog is very good,

Online auctions sites

SEO Services Consultants said...

Thank you for another fantastic blog. Where else could I get this kind of information written in such an incite full way? I have a project that I am just now working on, and I have been looking for such information… Regards…
Deep Cycle Battery

Unknown said...

Nice Blog
Pantyhose

Unknown said...

Great Post
Pantyhose

Unknown said...

I found your website perfect for my needs. It contains wonderful and helpful posts. I have read most of them and learned a lot from them. You are doing some great work. Thank you for making such a nice websiteSEO Services

sjflksd said...

Thank you for sharing this site with us..It’s a great help for those who wants to make their website successful..application development

Steave Brooke said...

I completely agreed with you.I liked your post a lot.
Thanks a ton for this lovely information..........
SEO services London

Anonymous said...

you did a great job ink cartridges printer like you working ,keep it up

webdesign said...

Thanks good idea SEO company India

sem said...

good post keep it up thanks for sharing web design company India

Fabian Smith said...

Thanks for the nice information. I am sure, I will tweet this to my twitter account. This will help a lot of users.

Local Map Optimization Video

Anonymous said...

Thanks for this great informative information shared with great thoughts and ideas.
web designing company

Fabian Smith said...

Thanks for this article. It's just what I was searching for. I am always interested in this subject.

Building Logo

Office Furniture in West Palm Beach said...

Yep, these Internet conditions haunt most of the people like us who live and earn their life on the Internet. I am an Internet developer for ages now and I dont seem to see good progress or awareness in this sector through the years.

British Luxury Watch

Unknown said...

Great Site, your plugins are very useful and save me a tonne of time. Cheap Essay Writing

Unknown said...

Great informative post and i really likes your information, most of the peoples are likes your blog because its having the good knowledge. thanks for your good informative post. Thesis Paper Writing

Unknown said...

Great to read about that. I was just searching for this. Well, I love the design of your website, I will be waiting for further updates. Essay Writing Services

Allen Perry said...

Best wishes for display rather good informations. Your search engines is great.I am impressed by the info that you've on this blog. It exhibits how effectively you understand this subject. Bookmarked this method page, will come back again for additional. You, my friend, amazing! I found just the details I previously explored all over the place and just can't come across. What a perfect site. Such as this web site your web-site is one of my new most liked.I similar to this information shown and it has provided me some sort of motivation to possess good results for some reason, so maintain up the decent do the job!
Sigma Writers | custom essay writing

Unknown said...

Great informative post and I really likes your information, most of the peoples are likes your blog because its having the good knowledge. thanks for your good informative post. Paper Writing Services
Thesis Paper Writing
Research Paper Writing
Letter Writing Services

Unknown said...

Thanks for your excellent posting. I really enjoyed reading this blog.
Cheap Essays

Unknown said...

such a nice work! Happy to find this great work keep it up. Thanks for shearing.
Search Strings

Unknown said...

This was a great and interesting article to read. I found many interesting things from this site.
SEO Company

Unknown said...

Good work by the blog writter! such a nice and informative article keep shearing more articles.
Google Adwords

Unknown said...

such an informative article. Thanks to blogger who shear this brillient article with us.
Cheap Essay

Unknown said...

This was a great and interesting article to read. I found many interesting things from this site.
Social Media

Unknown said...

Good to see this blog really informative.
Conversion Optimization

Rajinder Singh said...

I really appreciate your idea. Capcha is Such a boring in this days..


Web Design Company in India

Unknown said...

free business listing sites USA
website design company in USA
website design company in Hyderabad
website design company in Delhi
website design company in Mumbai
free classified site list UAE
website design company in Gurgaon

Unknown said...

The blog was absolutely fantastic! Lot of information is helpful in some or the other way. Keep updating the blog, looking forward for more content...Great job, keep it up.
Commercial appliances repair in Abu Dhabi

William said...

The entire information is really good and some good insights available. Looking forward to do more clicks. Affordable web design

Ancy merina said...
This comment has been removed by the author.
Zinavo-Web Design | Web Development | SEO | Mobile Apps | ERP/CRM said...

That's wonderful stuff you've written up here. Been searching for it all around. Great blogWeb Designing Company Bangalore | Website Design Company Bangalore

OGEN Infosystem (P) Limited said...

Thank you so much. This blog is really helpful for me, I’m lucky to find out this informative blog.
Top 5 Web Design Company in India

ProPlus Logics said...


Such an awesome blog thanks for sharing an useful information to us. SEO company in coimbatore
seo company in coimbatore |
best seo company in coimbatore

Web Design and Web Development Company said...

Nice blog.
web design in coimbatore

Unknown said...

Thanks for sharing such a wonderful blog with us, admin. The IT Company has many services for business development. These services are in demand at the present time.

Website Development Company in Lucknow | Software Company in Lucknow

Augurs Technologies Pvt Ltd. said...

Chatbot Development Services USA,
Chatbot Developers UK,
Hire Best Chatbot Development Company in UK,
Chatbot Developers Hong Kong,
Hire Best Chatbot Development Company in Hong Kong,
ChatBots Development Services in Lucknow India,

deepak ogen said...

Awesome article, I will never comment on other blog, but I will deeply read your article and I am collect many information with your article, thank you so much for share this valuable information with us, I really like to read this type blog, keep sharing like this type useful information am suggest to my all dear friend to visit this blog and get collect this great information, thank you so much for read my comment, if any one searching the website designing and also PPC company in India please come on my website ogeninfo system we are completed all type digital marketing in cheap rate.
Web Designing Company in Delhi

Unknown said...

I feel happy to say this I will deeply learning your blog and it’s really useful for me, keep sharing like this type valuable information regularly, I like to thanks for sharing this superb blog I hope I see you soon again time, thank you so much for read my comment, if any one searching the shipping company in India please visit my website yhcargoindia, we are shift your all type product with care in cheap rate.
Sea Freight Company in India

Small Business IT Support London said...

Nice Blog, Keep sharing your ideas and information.I would like more information about this, because it is very nice...Thanks for sharing. Thanks a lot
Small Business IT Support London
managed it support
cloud hosting services
projects consultancy
cyber security continuity

OGEN Infosystem (P) Limited said...

Thanks for sharing this knowledgeable things by your blog. If you need website designing services, visit our website at Ogen Infosystem and get a responsive website design for you. We also provide digital marketing services, like- PPC, SEO, Facebook Marketing etc.
SEO Service in Delhi

Mutual Fundwala said...
This comment has been removed by the author.
Mutual Fundwala said...

Awesome blog, Get the best Mutual Fund Advisor and Best Performing Mutual Funds Company by Mutualfundwala in Delhi, India.
Mutual Fund Agent

Chiến SEOCAM said...

İyi bir makale ve birçok faydalı bilgi

bán chó corgi con giá rẻ

chỗ bán chó corgi

ở đâu bán chó corgi

bán chó corgi thuần chủng

Phối chó bull pháp

Chiến SEOCAM said...

Makale çok anlamlı. Paylaştığın için teşekkür ederim

bon mat xa

máy ngâm chân giải độc

bồn matxa chân

bồn mát xa chân

bồn massage chân

Maketting SEO said...

Jede Person kann( máy xông tinh dầu ) unterschiedliche Gründe( máy khuếch tán tinh dầu ) haben, um ihr eigenes Leben( máy khuếch tán tinh dầu tphcm ) zu führen. Sie können nicht( máy phun tinh dầu ) alle Gründe erfassen, die gleich sind

Kala Kutir said...

Thank you so much for sharing such an amazing blog with us. Visit lifestyle magazine for creative events.
Lifestyle Magazine

Maketting SEO said...

Дээд чанар бол зүгээр л( đá ruby thiên nhiên ) санаатай биш юм. Энэ нь өндөр( đá ruby nam phi ) түвшний төвлөрөл, тусгай хүчин( Đá Sapphire ) чармайлт, ухаалаг ( đá sapphire hợp mệnh gì )чиг баримжаа, чадварлаг туршлага, ( đá ruby đỏ )саад тотгорыг даван туулах( bán đá sapphire thô ) боломжийг хардаг.

Just Info said...

Thanks for this informative blog, visit Kalakutir Pvt Ltd for School Bus Painting and Warehouse Zebra Painting.
School Bus Painting

Sam said...

Great site and a great topic as well I really get amazed to read this. It's really good Local SEO consultants

Edvin Berg said...

"I want to commend the author for their exceptional writing style. Each sentence flows seamlessly, making the reading experience not only informative but also enjoyable. The ability to convey complex ideas with clarity and eloquence is a true talent."
who became one of the richest men in hungary thanks to a toy he developed.

Kuldeep said...

Superb Post!

Empowering Digital Dreams: We are an innovative app development company dedicated to turning ideas into immersive and functional mobile experiences. Best application developers in pune With a passion for cutting-edge technology, we craft solutions that redefine user engagement and drive businesses forward.

Aatif Anjum said...

Visual Realism: Jewelry Rendering involves the creation of highly realistic digital images that showcase intricate details, materials, and lighting, providing a lifelike representation of jewelry designs.