Slashdot Mirror
3D-Based CAPTCHAs Become a Reality
mateuscb writes "A new way of creating a CAPTCHA using 3D objects has become a reality. The idea was thought up independently by blogger Taylor Hayward and by the folks at YUNiTi.com. 'Similar to Hayward's idea, this new technology relies on our ability to identify objects in 3D instead of using alphanumeric characters. YUNiti's 3D Captcha, however, has three objects in the challenge and extends the list of images to any object, not limiting it to animals as in Hayward's idea. This increases the challenge's level of complication to prevent computers from successfully making the correct guesses.' I, for one, welcome the thought of not having to read more and more complex CAPTCHA. Lately, I've been having a hard time getting CAPTCHA to work the first time."
I want 4D CAPTCHAs, so even humans can't figure them out. Think... Hypercube... the CAPTCHA.
I've been having a hard time getting CAPTCHA to work the first time.
And the secondtime . And the third time. And the fourth. And the....
Let's see now. If the spammers and robot makers went outside, done something worthwhile and produced something the world badly needs (food) then this nonsense wouldn't exist, I could surf in peace and the starving millions would live a little longer. The very existence of CAPTCHA's proves the human race is badly in need of a reset.
Interesting, but in a previous /. discussion, I got convinced that there was no perfect captcha, since one can simply pay a group of underpaid workers (e.g. in poor country) to manually solve the captchas...
Animoog.org
You can easily generate new images by rotating the 3D model a bit, changing the lighting, colors, etc.
The Question and Answer images could be generated the same way. You have to constrain the camera a bit so it isn't "What kind of animal has this butt?", but other than that you have a very large space to grab from.
Still doesn't solve the "porn for captcha" hack, but this would tell humans and computers apart for a while.
If I have nothing to hide, don't search me
I dunno, there has been quite a bit of research done with image/object recognition. You could break this by not matching pictures directly but by seeing that the first one is a bunny (so look for a bunny in the list), the second one is a hammer, etc...
We need something different. Personally, I can't comprehend 2D captchas. I think I might be an android, pre-programmed with false memories of childhood.
This 3D technology will finally help me solve this existential issue.
(BRB, gotta go recharge)
A slashdotter who didn't build his own computer is like a Jedi who didn't build his own lightsaber.
Seems obvious to me. I can't believe people are making a big deal out of this, especially those who have ever worked with CAPTCHAs before.
What's next, an "innovation" because it plays a (readily recognizable to the target audience) music sample? Same idea you know.
And I bet blind people are driven baty with CAPTCHAS anyway, this just makes web pages even less accessible to them.
CAPTCHAs are among the best motivators for progress in AI research since DARPA began throwing gobs of money around. The question is, what will happen to online forums and social/financial networks when machines become indistinguishable from humans?
I never have had a problem with captcha except when trying to post on slashdot.
the use of thing-in-the-middle attacks that might be able to determine the images sent and whether a stream of returned text that named the image got yielded access to the content or the process the captcha was "protecting". Given enough monitoring of such traffic, i imagine it won't be long before computers (programmed by humans who WANT computers to think or interpret more like humans) can keep with humans and play chess using only relevant considerations of moves.
What might follow might be "Computers: The NEW Terrorists", where by laws meant to preserve the "domain" of humanity will promise certain death to humans who betray humanity to machines.
Or not...
Previously: "Linux... Toward the Sunrise..." Now: "Linux... Toward the-- No, now, part of Every Sunrise"
As is, this seems relatively easy to defeat and well within reach of available technology. The number of 3D models is rather low and they have a very clear silhouette and also a very distinct one for each models. So all one has to do is to search for the best matching silhouette.
The good thing however is that 3d models have enough flexibility so that one could conquer many attacks, adding background images and texture would make it much more difficult to get a clear silhouette and one could of course easily introduce many more models into the mix.
I wish CAPTCHAs came with more detailed directions. Specifically, is the system case sensitive? Are the tall ovals without a line running through them (or a dot) a zero or an O? Are capital I s visually distinct from lowercase L s?
How long before someone creates an autostereogram captcha?
To do something right, you often have to roll up your sleeves and get busy.
Or as an alternative, we could actually track down the people who continue to make the Internet a swamp, beat them within an inch of their lives, let them spend a hot humid summer in full body traction, and maybe not only wouldn't they do it again but others might not either.
And put it on YouTube afterwards.
"It's the height of ridiculousness to say for those 9 lines you get hundreds of millions."
For a moment I thought that credit was being given to Howard Tayler, not Taylor Heyward.
He'll just have to settle for being known as the inventor of the Ominous Hum.
Instead of making the text near impossible for people to read, or a 3d select a box deal, why can't they use a universally embeddable video format to play a short clip and underneath a question you have to answer? Or even easier, an animated .GIF picture that again has a question you must answer to something about the animated .GIF image?
It may still be easy for them to decode the GIF and figure it out, but it's at least harder to do than a simple text picture.
The only other option I see is send the captcha encrypted, and use a javascript or some other client side script that decodes the captcha and displays it. Maybe use the IP or some other "semi-random" number to encode the random captcha so it's harder to figure out exactly what the captcha is?
The problem with 3d images, and complex non text CAPTCHAs in general is image size. You need to have enough different images so that the computer can't just brute force it, and those images need to be big enough so the user can actually see it. by the time you fulfil these obligations the CAPTCHA is taking up a good 3/4 of a page.
A Magic the Gathering Article and Forum Aggregator
If you wanna post on my site, you better be prepared to solve the 5D hyper-hyper-cube!
This seems to fall into the same pit that normal CAPTCHAs have: the Blind. But, it will likely be dealt with in the same way.
The big problem with the current implementation is that it relies on Javascript, which has a whole host of problems from cross-browser compatibility to having Javascript enabled at all.
I imagine this won't be a problem for long, though. At worst, you basically put up all the arrays at once and stick them with radioboxes. The problem is that this becomes extremely cluttered and likely confusing. A simpler route, but one that would be easier for bots to break, is to just have the user check a box by each of the three items shown. This is easier because the bot can just do random selections and get about 10% through.
If this could be paired with words, then you can break it down to three easy drop-down boxes to name the items in order, but then you have to worry about having unique enough words that they don't get messed up. (For instance, consider a dinner knife: it could be a knife, a blade, or a utensil.)
The time is fast approaching when CAPTCHAs will be too difficult for entry by humans. The only logical solution is to start an open source project to create a program that will enter the required data for you. Without this, we are looking at a time when humans will be unable to access their email or post on a message board, and only spam bots will be left. (Come to think of it, given what I see in most of my email and most posts on message boards, are most humans already locked out?)
It's becoming more evident every day that the first cylon will be a Captcha solver.
It won't be too long before Captchas will be little reading comprehension tests like on a 3rd grade social studies test.
After that we'll just have to revert to empathic testing. Sadly those with Autistic Spectrum Disorders will no longer be able to use webmail.
Everyone has a great idea for a CAPTCHA, but very few people know what the hell is really going on. Remember that the machine doesn't need to solve the CAPTCHA every time, that machines are infinitely patient and have huge memories, and that another machine needs to make sure the human gave the right answer!
Ideas that won't work:
Really, it's very easy to think you've come up with a very clever CAPTCHA. When you think that, all you've done is stoked your ego and screwed yourself over. It's the same reason why we don't roll our own cryptography: CAPTCHA-making is a very hard problem, mainly because your problem space must be infinite (to avoid an attacking machine simply memorizing answers), the answers verifiable by a machine, but the problems not solvable by a machine.
How many questions can be checked by machines but not answered by them?
Not many; fewer every day. There are no questions that can't be answered by a computer (and which can be answered by a human mind). The Church-Turing thesis has some validity: the human mind is no more powerful than a turing machine, and ultimately, computers and our brains are equivalently computationally. There's nothing a computer can't solve: there are just things we haven't figured out yet.
Sadly - or perhaps fortunately, depending on how you plan to apply the technology - classification of 3d objects against a known library of objects is a mostly solved problem. There are a few ways to go about doing it, such as neural networks, boosting classifiers, or support vector machines, but you essentially train a set of classifiers against a bunch of known images of the 3d objects from different perspectives, and thereafter, it tells you what class of images best represents the image that you query it with.
The hard part here is training the classifiers. The training methods require you to know ahead of time what classes your training sets are supposed to be categorized in, which means that every time somebody adds a 3d object into their captcha, you would have to get enough sample images to train your classifier.
One could also potentially use several training images to reconstruct the 3d object, and then search over the possible rotations to see which one the query image matches.
Personally, I think the regular photographic captchas (i.e., "click on the Siamese cat") are a better idea.
Oh, and there are problems computers can't (easily) solve, but can verify. The problem is that human brains can't solve these problems either!
Before someone jumps in with "humans can solve the halting problem!" -- we really can't. There are problems that obviously halt, and programs that obviously don't. We can tell these apart, but so can computers. It's the complicated, borderline cases that trip up both people and computers.
Furthermore, there are important caveats to the halting problem: first, you can tell whether a program halts in a given time. You just run it and see whether it halts! Human beings do this all the time when debugging hanging programs. We use a good heuristic that says "if a program doesn't quit after a good long while, it probably won't quit at all." (And that holds in most cases.)
Second, the halting problem can be solved, via brute force if necessary, for a restricted-memory machine. Make the available memory size small enough and you can actually perform useful validation. The proof of the halting problems' unsolvability applies only to unrestricted turing machines.
A true turing machine has never been built, and can't exist in our universe. Every computer is a limited-memory approximation.
Isn't this (i.e. classifying 3d objects under rotation, distortion etc) already basically solved? It's the sort of thing you assign people MSc projects to do...
How dare you be so modest!! You conceited bastard!!
Because a computer doesn't mind trying thousands of times, even hundred of thousands of times until it hits a combination that works.
If Google really cared they would fix Android Chrome to reflow text, instead of discriminating
It's a Jackal!!!
The cool things is to have windows that bounce up and down like a good tits.
I don't understand. Aren't these 2D representations of 3D images? I may be ignorant and you could explain until you're blue, but I'm pretty certain that my monitor is incapable of displaying any 3 dimensional objects. You can't fool me; those are 2D images with some shading thrown in. The next image of the plane is the same image at a different angle with different shading. If I convert these images to 2 bit to remove the shading then spin them around, they will look very similar. I convert crap like this to 2 bit all the time to OCR it. Will this fool the Russians spreading malware? Enlighten me.
because a bot already has a one-in-nine success rate by selecting a model randomly. *facepalm*
Even if they can be trained to have a copy of the exact 3D models given (which are sure to increase in variety if not types), they still have to take a picture of it from every single angle, which I believe is 359^3 images, and then compare every single one (which is O(x^n) time, where x is the time for one image comparison).
Which hat did you pull those formulas out of? Taking a picture from "every 3d angle" (not a meaningful phrase anyway) is on the order of 360^2, not 359^3. Comparing an image to every image in a list is O(x*n), not O(x^n). Most importantly, any computer scientist worth his salt would not use such a naive brute force method; he would try to reconstruct the 3d model directly from the image, guessing depths based on shadows and lighting, then match that model against known models.
Pose increasingly difficult problems as captchas and wait for someone to create a program that solves it.
Porn and necessity are the parents of invention.
No really, make sure a real human is voting, and all that.
This issue is a bit more complicated than you think.
I'd like to see a bot that tries to recognize the 3D shapes and crashes (or loops infinitely) if you feed it an impossible triangle. :)
just add a pop-up, for your Grandma's pwned PC:
[pop-up dialog] - Want to speed up your computer? Click HERE and answer a few quick questions to optimize your computer!
Granny picks a few matches and goes along her merry way.
This issue is a bit more complicated than you think.
Big problem! What about the people that lost the use of one hand? There is a small thing called the Americans with Disabilities Act which you would violate. As it is, many capchas violate that law.
I am aware of a class action lawsuit being formed right now on just this issue.
3D recognition is a solveable problem. As someone else mentioned, there are machine learning techniques that work. Recognizing a 3D object from multiple angles is a very old AI problem, one that DoD-funded work was addressing as early as the 1960s. It's easier than 3D reconstruction from multiple 2D images, which is a commercially available technology.
I think we're reaching the end of the line on CAPCHAs. There's now overlap between the smarter vision programs and the dumber users.
So Jagex's Runescape MMORPG has had this for a couple of years in random events to defeat macros.
http://www.runescape.com/
www.rustylime.com
it uses pop references, eg: who is this, and a picture of homer simpson.
A more sophisticated proposal for 3-D CAPTCHA was first developed in 2004 and it is currently described at http://spamfizzle.com/CAPTCHA.aspx. This 3-D CAPTCHA was presented in abstract form at The Second International Workshop on Human Interactive Proofs HIP2005. Slashdot reported on this CAPTCHA in January of 2005 when it was described under the name Virtual Photographic CAPTCHA.
Spammers now hire the desperately poor and pay them to solve CAPTCHAs. Defeating that will involve either improving economic conditions in poor areas so that people won't be willing to do so any more, or writing a system more intelligent than humans.
One of these is difficult, the other will result in the Singularity. I'm hip with either.
The problem is that human brains can't solve these problems either!
Put up a picture of a small (say 7-15 "towns") traveling salesman problem [NP-hard] and randomly take out some of the routes. Ask the user questions about the incomplete network: For the shortest total distance, what would be the best town for town 4 to connect to? How about town 7?
It's trivial for a human to glance at a map and pick an obvious short distance. A computer wouldn't even know where to start. Of course, this is still subject to the "borrow humans to solve" situation, and *might* be subject to the 'finite set' rule cited by parent, although our technology is good enough for an app -- given the data -- to solve small ones like this (not quickly, however), and hold them for future use. (I don't think many spammers would have such an app interfaced to an inference engine, which is what would be necessary to non-humanly solve this.) Also this solution would violate the ADA, because the blind couldn't use it.
If you want to 3-D it, switch to the knapsack problem, which is also NP-hard: which of these objects can fit into this partially full knapsack? Same objections as above.
DNA is a Turing machine. You, however, being dynamic and emergent, are not.
what about a 3d catchphrase to guess. it would be entertaining also. That would be 4d in a way.
OUCH YOU'RE REALLY shouting VERY LOUD there!
You can get your message across in just plain text and a little bit of thought out spacing you know...
cheers.
As far as I understand, there is some limited automated captcha breaking, but most captcha's are broken by outsourcing them to foreign countries where people just look at them and send back the answer. If this is correct, then there is simply no way to make a good captcha.
These are easy to crack, because the same captcha recognition software can be used with just a few patches. This is because there is very little if any difference between recognizing a twisted and rotated letter and recognizing another "symbol" like an airplane or fork. From a technical point of view, they are all symbols, and only the domain increases, but not by many objects, I think. And these are easy to solve because it isn't about pixel matching, which the rotations presumably sabotage. It works the same way humans recognize a plane rotated a certain way: by matching on certain cognitive give aways. It is really much easier than an uninformed person would think it is, and typically you only need 3 or 4 such cognitive patterns.
For some time it will work. It will be deployed all over. The response will be that in Asia (South, South-East, East) in dark basements more people will get jobs and sit in front of flashing junk monitors for 1 buck a month to solve these and create databases. And the image analyzing programs will also improve which we can consider a good thing.. but will render these techniques also obsolete in time.
It doesn't appear to work without javascript. If it's acceptable to ignore the few percent of your target audience with script disabled, you may as well be using some form of hash cash.
They don't answer the question you want answered.
"Is it human" is a hard question, and sometimes even ambiguous.
A better question is, "How much is it [my site] worth to them [the user]?"
And that can be answered with either actual payment, or payment in time using message digest techniques:
Just have the client add random garbage to their submission until the md5 or sha or whatever is popular hash has a certain number of zeros, consecutive zeros, or an arbitrary string. Choose the number of bits you require so it takes non-trivial time to find. Obviously, you'll need more bits over the years due to moore's law. People with 10yr old machines will just have to put up with the extra wait or sign up for accounts or something.
Only botnets have any kind of resistance to this, and even they would be slowed down a *lot*. And if they used enough resources to get noticed by the owners, they'd be slowed down even more.
Is there a patent somewhere or something preventing this from popping up everywhere?
Can you be Even More Awesome?!
Lately, I've been having a hard time getting CAPTCHA to work the first time.
Same here. CAPTCHAs seem to be getting more and more annoying for actual humans.
And whose idea was it for ReCAPTCHA to include characters like "1/2" and "3/4"? I don't even know how to type those.
The best CAPTCHA I have seen was for Europython 2008.
- What computer langgueage is this conference about?
- In which town is the conferencce held?
- Who is the originator of the Python Programming language?
If you don't know the answers to these questions, you have no business at the conference.
If you don't have a tight topic like this, your best option is pictures as a CAPTCHA. What is in the picture? Handbag, donkey, ship, elephant.
The options are infinite, and until AI's develop real picture recognition, it will be foolproof, given enough variety in the pictures served.
It will provide great incetive to develop real picture recognition, which is a great side benefit.
I like the idea and the effort, but the technology behind Microsoft's PhotoSynth platform already makes this, well, pretty much crackable in about 30 seconds. Think about it: Photosynth builds associations between similar images and gathers enough information to build a 3d map of subject(s) of said images. All a bot has to do is gather enough pictures of enough views of the different models, and it's going to be able to calculate that picture x is another view of the fork and picture 7 is another view of the toilet.
Ed R.Zahurak
You know, oblivion keeps looking better every day.
When providing a picture or an 3D object as a captcha - in which LANGUAGE do you expect the users to answer?
Do you really believe that the whole world has to be fluent English (or whatever your native language might be) speakers to solve them? What about the whole rest of the world?
What about people who know what they see, but cant type in its name correctly? Is it a bunnie? A bonny? A buny? Or a bunny? Or is it a hare? A hair? Captcha solving is not meant to be an orthography test after all...
Think again and youll see - epic fail!
Hi,
We've (My workshop partner and I) created a (basis for a) 3D captcha:
the basic idea is having 3 human models look at different objects.
the challenge is to point at a certain body part of the model looking at a certain object.
I'm assuming a classifier will be able to solve this, but a simple complication of having to solve more than one challenge to gain access to the resource, should increase the difficulty exponentially.
for more details (and source code), see:
http://tau-itw.wikidot.com/project:3-d-captcha
Regards.
Omer.