Cenzic 232 Patent
Paid Advertising
web application security lab

KittenAuth CAPTCHA

I was thinking about the KittenAuth CAPTCHA since I messed with it over the weekend a little. As I said, the number one issue with that particular system is the low order of possible solutions. It’s not about finding the right kittens, necessarily, but it’s also about the probability of getting the right answer. If you just guess an answer, the probability is 3 over 9 times 2 over 8 times 1 over 7 = 6:504 odds (given 3 correct values in a set of 9), compared to a normal CAPTCHA of say 6 numbers would be 1:999999 (just a tad worse odds there). The other problem with it is that it has such a small set of photos.

I did some cursory research on Yahoo images and Google images, and I found that Yahoo had a far superior data set of actual kitten images than Google, although Google reported half the data set of images it was also less accurate in what it was finding for the first 20-30 pages. If you were to use Yahoo’s data set there would be very little pruning needed, where if you used Google’s image search you’d be removing things like a band named “Atomic Kitten” and some Melborne based transvestite named “Kitten”. The point being, even if you could gather such a set, and prune it, then you’d still be at the mercy of a robot who could accurately gather all of the images off the internet with the name “Kitten” and get such a large data set to compare against that it would be broken again. But that’s leaving out Bayesean heuristics.

There’s a company called MessageLabs that uses something beyond pixel by pixel comparison and even beyond pixel color densities to determine if something is porn (those are the most common method of content filtering and also very flawed). MessageLabs also verify what is in the photo. For instance they can tell what a hand is, or what a car is or what a sky is, so they are less likely to see something like a flesh colored door or a baby picture or something more grey area like a swimsuit photo at the beach as porn. Using something like this against KittenAuth could prove to completely break their system - as if it weren’t already broken enough the way it is today.

22 Responses to “KittenAuth CAPTCHA”

  1. Oli Says:

    The main strength in KittenAuth is the power to switch between different sets of “correct” images automatically and change which groups are shown when you feel like it.

    With text captchas you have one of two choices… You go simple and usable and get hacked after 10 minutes or you go completely impossible for a human to read but secure.

    I feel (although I would, being its author) that kittenauth bridges the gap between security and usability quite well.

  2. RSnake Says:

    Oli, thank you for the post. It’s good to hear from the author’s perspective. I’ve got to say, you are up against a very complicated problem. I was chatting this over with Jeremiah Grossman the other day. He has even more experience with CAPTCHAs than I do, but collectively I think we have a lot of unique experiences in breaking and creating interesting anti-robot techniques.

    His idea, which I came up with before on my own as well, was to involve something that would force a user to click. The problem is there are robots that can mimic user interaction (even something as complex as a game). There was a banner advertizer once that attempted to use image maps to calculate where a user was clicking to attempt to detect robots. Well, of course that took about ten seconds for the bad guys to figure out (randomize the X and Y axis). At the end of the day we were re-inventing KittenAuth (that should be a compliment).

    The point being, you cannot actually stop robot detection of any kind with predictable data. Worse yet, is the porn replay problem I discussed in a previous post, that completely gets around this. Not that I’m saying your idea is bad, it’s just proven to be broken (I’ve worked for a company that has seen this happen first hand, so I’m not making this up).

    In the end I think CAPTCHAs _do_ work but only because most of the time bad guys are just attempting to post something and it is simply easier to post elsewhere than inventing a methodology to break a CAPTCHA. It’s the case of “not running faster than the bear but running faster than the guy next to you” and in that case I think KittenAuth is a fine device.

  3. GigoIt Says:

    GigoIt’s HumanAuth is based off the ideas presented by KittenAuth.com. HumanAuth supports ADA (Americans with Disabilities Act) and Section 508 requirements, increased security and includes watermarked images with random positioning. HumanAuth ensures that an actual human is using your site without forcing them to read distorted CAPTCHA text.

    http://www.gigoit.org/humanauth/

  4. RSnake Says:

    Thanks GigoIt. This does appear to have all the basic problems that KittenAuth does though. The question you are asking is sufficiently vague enough that that could represent a different kind of problem. However, these are in the problems I see with the demo (in no particular order):

    1) HumanAuth uses JavaScript - if I don’t have it turned on in a normal browser, it doesn’t work.
    2) HumanAuth has inline text for text based readers that could easily be scraped by spiders to automatically click on photos
    3) HumanAuth suffers from a very small amount of possible combinations (if I just randomly guess, I have a one in three chance of getting the right answer since order of what I select is not important).
    4) It requires people to know English
    5) HumanAuth may suffer from the same Baysean analysis that KittenAuth does if the question is static.

    I’m sure there are other problems, but this was just the first things I noticed.

  5. GigoIt Says:

    Thanks for the follow-up. I do agree with a few of your points. This application is currently limited by its requirement of JavaScript. English is the only language HumanAuth is offered in. This can be easily fixed, as there is a large development community that almost always has someone willing to translate a project if the application is worth while.

    (POINT #2) The inline text for screen readers as well as the mouse over text and the alt tags are all generated dynamically based off the file name. The problem spiders will have when attempting to click on any of our images is that computers can not currently compare words to an “idea” as this application is requesting. This is known as a Turing test (http://en.wikipedia.org/wiki/Turing_test). This basically says that a computer can not answer something like:

    Which of the following items are considered “HARD” items?

    1. Rock
    2. Water
    3. Ice
    4. Feather
    5. Table

    The answer, of course, is 1, 3 & 5. This is currently difficult (if not impossible) for current computers since they can not compare the idea of “HARD” to the items in the list.

    Since it is hoped that users will use there own unique images with their own unique challenges (ours is to click pictures of Nature, you can have it be whatever you want) it will be very difficult for a bot/spider to do anything except guess the answer. The script is set up to only allow three incorrect guesses then you are kicked off that page to whatever page you have set up in your config file.

    (POINT #3) There is only a 1/84 chance of getting it right by merely guessing the images. The math for this can be determined with the formula for “combinations without repetition” (http://en.wikipedia.org/wiki/Combinations_and_permutations):

    n! / r!(n-r)!
    n= 9, r=3
    9! = 362880
    3! = 6

    362880 / 6(9-3)!
    = 362880 / 6(6)!
    = 362880 / 6(720)
    = 362880 / 4320
    = 84 Combinations

    However, the script redirects the user to a defined URL after three incorrect attempts.

    (POINT #5) I am not confident that Bayesian Analysis (http://en.wikipedia.org/wiki/Bayesian_filtering) would work in this case since the words being used with the image alt tags and descriptions are being compared by an idea. This is where a lot of debate comes in as this is basically an example of Bayesian Analysis vs the Turing Test.

    Thank you again for taking the time to think of these issues. I would be interested to hear other weaknesses in our application and, more importantly, possible solutions for correcting them.

  6. RSnake Says:

    Oops, you are absolutely right about the 84 combinations (I actually had the math right in my blog post, I don’t know why I said 1 in 3 in my reply). But one in 84 chances really isn’t that hard, and the fact that you give them three chances actually makes it better odds that they’ll get it (it costs nothing for a robot to try three times). I’m sure you plan to block based on IP or something similar, so they’ll need to use a proxy and change around their environmental variables, etc…. A few hundred requests and they are statistically garanteed to break it. Increasing the number of images would help with that, by orders of magnitude, but the usability decreases substantially with that. In fact, I could probably even use XSS to help me defeat it (it would take some work, but I’m fairly confident I could).

    Regarding the baysean analysis, as I said, that would only work if the question was static. If you changed the question on each request, that would not work, as you pointed out. In your demo it was a static question, and thefore vulnerable since I know what an idea is and can feed that into the algorythm. Even with extremely complex subjects it would still be easier to do exclusion and baysean learning unless the amount of images were so enormous that it would be computationally infeasable for it to do so.

    I’m familiar with Turing test, as I’ve built them in the past, but this does not represent a perfect turing test, as it only verifies that the user (robot or not) is incapable of correlating the idea that you have chosen to the images that correspond. One example of where some confusion for humans may lie is one of your photos of “nature” was of a fishbowl, and that is anything but natural to some people.

    It likens itself to an SAT test that is skewed towards the people who have studied the topics in question, rather than testing overall intelligence. In this case you are testing the user’s ability to correlate an idea with photographs (which btw, might represent a problem for the color-blind, which make up about 10% of males). We have to make an assumption that whomever came up with that association was correct and made the same assumptions that all users of that application would and will given their abilities (a tough job).

    Lastly, one thing I didn’t mention, of course, was the porn site replay attack. There may be ways around that, but they are complex, and probably outside of what I’d want to be talking about on the blog.

  7. GigoIt Says:

    I agree with everything you said. HumanAuth is not a perfect solution. I’m the first to admit it. This is for users who want to filter the amount of spam coming to their site, but are concerned about losing individuals who would be accessing their site through screen readers. Standard CAPTCHA methods completely eliminate any individuals who are blind, not to mention that more than half to time they are impossible to read by someone with perfect vision ;)

    HumanAuth should work fine controlling the number of invalid posts for most sites. There will always be sites that get large quantities of traffic that will make someone try to bypass this application to get their message across. Script kiddies who have nothing better to do might just do it for the challenge.

    Good news is that only brute force attacks (that I know of) will potentially work. As you stated, someone would have to write a script to hit this thing until it got in. It is true that they could try it again and again.

    We thought about this when we set it up to load randomly every time the app started. Grab three random correct images and put them in random squares, then fill in the rest with junk. Since the scripts only get three chances to get it right, then after the third incorrect attempt the user is redirected through PHP to another page. This means that each time they try to hack it again, they have to come back to the page again that has HumanAuth, which then generates a new random list for image loading. They can not use any pre-tested, failed locations from their last attempt since all that data has been removed from the page. They can not depend on the file names to be the same since they will also be reloaded with new images.

    We have a SourceForge project set up for this (http://sourceforge.net/projects/humanauth/) and we are always welcome to feedback on how to make it more secure without, of course, limiting human access. This is the biggest challenge.

    Thanks again for your comments :)

  8. Oli Says:

    I’m posting this reply to http://www.kittenauth.com/node/10 to try and keep the conversation running everywhere it exists =)

    The problem that you’re missing out on the math side is 1-in-84 random attempts ending in success is just not good enough. This is something I learn from the initial feedback from Bruce and the rest of the people that replied to my article on KittenAuth. When you have a botnet of 10,000 computers (a fairly middle-sized one) and you’re getting 1 spam message through ever 84 hits, a single wave of spamming from every computer will result in 119 messages.

    http://www.thepcspy.com/articles/security/improving_kittenauth

    I mention in there, with a 5*5 grid, with certain blocking after errors (as implemented in the PHP KAv2) and also changing how many “winning” images there are in the matrix, you get to 1-in-33,554,432. With the same botnet, they would be lucky if 1 message got through.

    On top of that, you’re giving out the “secret” information (eg: what’s in the picture) — the entire point of having the images is to utilise a person’s brain in a manner that it copes with much better than a computer — rendering the point of your images being there as useless.

    There are already (and have been for some time) information systems that can collate items into groups based on implicit properties of the items. Google Groups is one example.

    You’ve got to remember that in order to have a system like this, you’re going to need to make a database of items and their properties, so don’t think that making such a database is impossible.

    Scraping the words from your captcha’s HTML output and feeding them into such a system is a billion times less cpu-intensive than doing the full image comparison/recognition and therefore makes it unreasonably expensive to bother doing so to crack a captcha for profit.

    I suggest, if you want to go the way of group-properties, that you do just that, rather than trying to match a image-based and text-based technology together for the sake of standards.

  9. RSnake Says:

    Hi, Oli, I think you have a great point, but I think we have to break this problem down further. There are two applications for a CAPTCHA… one is to reduce annoyance (blog spam) and another is to completely block robotic activity. I think the 1:84 math explains that kitten auth as it was originally designed cannot stop all robotic activity. It seems like it would have a better liklihood of doing so with your enhancements, however.

    I think that is a good enhancement, however it doesn’t solve the porn proxy problem, and I think the standards are in place for a reason. Making a system that is only accessable by people who have the facilities to solve them is not just keeping out robots anymore, making it a failed CAPTCHA by definition (as it is not capable of telling the difference between a computer and a human).

    You may have already seen this but if not check out Jeremiah Grossman’s CAPTCHA evaluation criteria: http://www.webappsec.org/lists/websecurity/archive/2005-08/msg00059.html

  10. Oli Says:

    That’s a good link =)

    KAv2 only really fails on the last 2 items and I admit that. I think each of those items should not just be a pass or fail but weighted so some are more important than others…

    That being the case, I’d say that list is weighted (some blind people may disagree and they can sue me if they’re that upset) and therefore we (GigoIt and I) are both tackling the problem of usability over uber-security as a priority and that’s definately the way other captcha designers need to look at these things.

  11. RSnake Says:

    I wouldn’t take the blind issue that lightly actually… When you say they can sue you, you have to realize it’s not a matter of can, they have and could easily do so and win. They have been very successful in litigations.

    The uber-security portion of this is really the crux of the problem though. Let’s say I do set up a porn proxy to defeat your CAPTCHA. What have you now accomplished? You have cute kittens on your site. You have a potential lawsuit. You have no blind users and no non-english speaking users. And the clincher is you still have spam on your site.

    Uber-security aside, how can that be considered a gain? Usability is nice (btw, I am a customer experience advocate by profession) but if you turn of the usability for a small percentage of your users, you really have done yourself a disservice.

    You have three classifications of browsers in my opinion. The first (class 1) is where you must support them because they are the largest user base. This is the obvious one. The user experience must be nearly or exactly the same for these browsers. The second (class 2) is where you want most of the functionality to be the same but you are willing to put up with some loss of user experience because of the limitations of the browsers themselves. And then the third (class 3) is where you just don’t care - those users can rot in hell, but you should at least alert them that they need to use a modern browser to support the features they are attempting to use.

    In my mind, browsers like Lynx and Links, etc… fall into the second category - class 2. Class 2 just means that the functionality must be supported (alternate means are allowed but they have to exist). Lynx just happens to be a largely used browser for the blind (text to speech readers). I would be hesitant to just say forget them, because they are blind, because that is also forgetting users who use other hobbled browsers, or just want the convenience of using their favorite site through a remote shell, or otherwise.

    Search Engine Optimization works the same way as accessibility with the one exception of password protected areas. That makes sense to protect that area in a way that the search engine (a robot) cannot spider the content. But it does not make sense when it’s an actual user. It hurts your brand, and it’s a detriment to usability. I’m not saying CAPTCHAs aren’t a great idea, I’m just saying that they are seriously flawed if they are used as standalone devices. An alternate path must be created.

  12. GigoIt Says:

    I agree 100% with RSnake. This is too important of an issue to just let it go. We can affect the effect of CAPTCHA by listening to RSnakes argument and implementing it in future development as best we can.

    (double points for using affect and effect correctly in the same sentence)

    - GigoIt

  13. Jeroen Haan Says:

    To me your discussion really sounds paranoid.
    Do you only offer a contact form as a means of making contact?
    Really?

    Why don’t offer a printable form and have the user mail this paper traditionally?

    Or offer the blind a phone number which they can call to verify certain things?

    Together with a physical address and a fax number there is nothing to sue, right?
    At least that’s how it works in many European and Latin American countries where my company is actively playing a role in website development.

    Instead of making things more and more complicated we should look beyond the technical game we play with abusers and return to human to human verification.

    The costs for extra employees will be lower then a lawsuits and the time and money spend on captcha development and other technical issues.

    In my opinion the online form is an extra service only to save time on communication.
    The way we are dealing with the form now consumes more time then it saves…

    Last but not least, why don’t state very clearly above the form and in the Disclaimer that the company is not reliable for the accessibility of the form.
    Extra service….if you experience any problems, please call, fax, send a letter or visit any of our representatives.

    Instead of focussing on the problem we should look at the old and very easy solutions already there….

    Cheers,
    Jeroen Haan
    Website developer
    Netherlands, Brasil

  14. RSnake Says:

    You have it exactly right, Jeroen, the problem is that most companies don’t have these sorts of fallback mechanisms, but that would definitely solve the issue from a lawsuit perspective.

    However, I’m not sure you can remove your obligations for accessability simply by offering a legal disclaimer, though. I’m no lawyer but that really doesn’t sound like it would work. And you have to remember, if you make it significantly harder for the consumer (IE: requiring Fax machines that they don’t have, or telephone numbers to call if they are deaf) they still have a right to sue because it’s not truely accessable.

  15. Jeroen Haan Says:

    With all respect, I am laughing my pants off.

    Maybe we, here in “Holland” and in Brasil too, are very old fashioned and the government way behind the Internet community…
    Most companies have an office with a physical address.
    Ones that work at home have a PO Box.
    All have an email address that you can mail client side.
    And even consumers have an fax.
    Btw; FAX number’s are for people and companies that do have fax, not for the ones that have not… so that couldn’t be the problem or do I simply not understand the suing culture of the USA?

    That brings me to the next point:
    Why not mail the form with a mailto statement client side and leave the CAPTCHA out?
    And if you don’t want that, why not leave the headers blank while using the mail function on your server!?
    So when you ask your visitor to type his email address, you simply add it in the Message Body and not in the Header parameter! (or use your own email address in the Header…)
    The RFC of email simply forbids sending to email addresses supplied in the Subject or the Message body…

    Last but not least,
    Check if people use more then one @ in their email address and if the email field contains Line Feeds (new line) and Carriage Returns (return) and check the length of the field.
    If yes on one of these three checks, simply bring back the form and ask if they can check the errors.
    A spammer or hacker will simply go away and try somewhere else.

    You could also not use the mail function or mailto statement but insert the contents in a database or file and alert the webmaster.

    Plenty of solutions…

    Again, if you could be sued because your CAPTCHA, leave it out and:
    - Action = “mailto …” or
    - Don’t use the headers but store the senders address in the Message Body
    - Do good filtering and sent the results back to the user
    - Or don’t use the mail function, store it!

    Always filter, it will prevent high server loads and lot’s of junk mail in your mailbox, database or file!

    I hope this helps some developers and companies (print this and give it to your webmaster).

    Cheers,
    Jeroen Haan

  16. RSnake Says:

    I think you’re right. The United States is a very litigeous country by nature. I don’t think this has as much relevance for international companies unless they do business in the United States (at least not yet). As I’ve said before, alternative methods are good as long as they don’t discriminate in another way. Mail is probably the most accessable method, but it’s also very slow unless you have full time staff to support it. If your user has to wait 2-3 days to get a response you might be flirting with a lawsuit (here in the US). So the staff required to handle such users would be required.

    Anyway, if you aren’t at risk because your national laws don’t require conformity to the various accessibility standards, this conversation isn’t designed for you.

  17. Jeroen Haan Says:

    But I would like to help you :-)

    What about a simple email link?
    ;-)

    success!!

  18. Oli Says:

    Well I’m glad this has gone a bit further. Sorry for my late reply.

    Look I’m sure in the big corporate world, large companies can afford to hire someone to manually authenticate (via phone, or even standard mail — lol!) but why should the rest of the internet have to be bombarded by spam?

    I do 95% of the administrative work on ThePCSpy.com by myself these days… I do it around the rest of my life. How the hell could I afford the resources to counter for every living being on the planet… More importantly, when did it become my obligation?

    My site is given as-is. There’s no warranty. There’s no money-back guarantee. No cashback. No double-discount. Nothing but the words on my site. People aren’t paying for anything to read the years of work I’ve poured into it.

    I’m not pointing fun at blind users. On my site’s case, if they want to post without being CAPTCHA’d they sign up with a valid email address and they can post. If they don’t want to do that, that’s their choice.

    Sueing people for “discrimination” against blind in a circumstance like this is akin to sueing someone because they do not provide telepathic input boxes for brain-dead/hand-amputees. It’s silly.

    The same applies when you look at the captcha technologies used. There’s no reason to be forced into making 1 technology usable by all. Infact, that’s plainly quite stupid. The more ways you give something to be solved, the easier its going to be for something that you’re trying to filter out, passing the test.

    I’ve said from very near the beginning that KittenAuth is ONLY a text-captcha replacement. HumanAuth tries to be slightly more clever but at the end of the day you might as well save the bandwith and display the words, or better yet, display nothing.

    Therefore if you want to be covered by stupid laws (not that I’m saying blind people should be persecuted) you need to employ more than one system.

    Then you could ask, “well what’s the point if you’re going to have to use another system anyway?”

    Because KittenAuth is:
    - nicer to use
    - easier to use
    - faster to use

    As I’ve said here before, its not just about being harder to crack, its about being less stressful on the user. Traditional text CAPTCHAs are either completely crackable or people fail them too.

  19. Pablo Ximenes Says:

    Gentlemen and Ladies,

    I’m sorry, but I think kittenAuth cannot formally be considered a CAPTCHA. The (P) in the acronym stands for public, which is a reference to Kerckhoffs’ principle [http://en.wikipedia.org/wiki/Kerckhoffs’_principle ].

    Should an attacker acquire all knowledge (including databases) regarding the test, he/she should not be able to solve the test because of it. The solution of the test must be exclusively related to the solution of the hard Artificial Intelligence (AI) problem that is being presented. A hard AI Formally, breaking a CAPTCHA means advancing AI. Hard AI problem are those that AI community agree upon as hard to solve (open problems that will remain open for a while), much in the same sense number theory is for cryptography.

    [Luis von Ahn, Manuel Blum, Nicholas J. Hopper, and John Langford. CAPTCHA: using hard ai problems for security. In Advances in Cryptology, Eurocrypt 2003, volume 2656 of Springer Lecture Notes in Computer Science, pages 294–311, May 2003.]

    The concept behind CAPTCHAs is very good. The discussion here, I must add, is (or should be) more related to the feasibility of the principle is in current scenarios, since the proposed examples are not CAPTCHAs.

    Is it possible to build a CAPTCHA nowadays?

  20. RSnake Says:

    Hi, Pablo, thanks for writing.

    So are you saying that Kitten Auth is more a form of symmetric key cryptography that is highly deducible by humans and difficult (may be very difficult or may not depending on the algorithm) instead of an actual Turing test simply because not all the information is presented at the time the test was presented?

  21. Pablo Ximenes Says:

    Hi RSNake,

    I’m sorry I didn’t make myself more clear (I was in a hurry)!

    I meant exactly the opposite of what you’re asking.

    Since KittenAuth relies on on the secrecy of the database of pictures, it doesn’t respect Kerckhoffs’ principle.
    If an attacker had access to the databse of picture he could, for example, simply label all pictures and use a simple algorithm to compare the picture in the test against the ones he/she has.

    To a turing test to be cnsidered a CAPTCHA, it must respect Kerckhoffs’ principle, it must be (P)ublic.

  22. samanth Says:

    how do i get credit card numbers and pin codes that work