Making CAPTCHAs Even Harder With 3-D Models

Michael G. Kaplan writes "CAPTCHA (Completely Automated Public Turing Test to Tell Computers and Humans Apart) are commonly used to prevent computers from filling out web forms. Computer vision experts have been able to design programs to foil CAPTCHA with a high degree of success. I have designed a CAPTCHA that is based on the identification of attributes contained in an image generated by the grouping of easily recognized 3-D objects. I call this the Virtual Photographic CAPTCHA and it is likely to remain invulnerable to automated attack for many years to come. A novel anti-spam system necessitated its development."

Comments

Took a long time

[cmclean]

Decoding the 5-letter example in the article took waaay too long when compared to current techniques (i.e. 30 seconds as opposed to 3), regardless of how good it is at eliminating nonhuman respondants.
It seems a very good idea, but all that flicking back-and-forth of the eyes is to compute-intensive for my grey matter.

Why graphics?

[Skevin]

Do you know how many times things like this have required me to use some browser other than Lynx or Links? You're blatantly discriminating against us terminal users. Then we have to find someone running a GUI envoronment. Oh! The insensitivity!

Solomon Chang

This sucks.

[Sam H]

This proposal totally sucks. The goal of a CAPTCHA is not only to be extremely difficult for a computer, you also need to make it simple enough for the user. Most current implementations are considered extremely inaccessible, and if you have accessibility in mind, these 3D images are a huge step backwards. The utter vanity of it all is emphasised by its vulnerability to the porn site attack (offering porn to monkeys to crack CAPTCHAs). Be assured that I and other people will devote as much time as possible to eradicate moronic CAPTCHAs from the Internet.

Re:This is a bad thing for the blind.

[zobier]

Auditory CAPTCHAs

Problems with This System

[MidnightBrewer]

1. It uses a whitelist as a means of solving spam. The system claims to allow strangers to effectively email each other, but only after first forcing the user to jump through several hoops. Correspondence will be slowed, and many people may give up in irritation before they bother to send the mail a second time. Imagine a prospective employer who decides that it's not worth tracking down Joe Blow because the email didn't get through, or a university attempting to contact a student by email. This particular method of foiling spam eliminates one of the key benefits of email: easy correspondence with a fast response time.
2. Users have to maintain a database of trusted senders, as well as another database of recipients who trust them. This means extra data and the possibility of users accidentally falling off of each other's whitelists whenever somebody loses their address book.
3. It will generate too many bounced messages, thus increasing network overhead to a point where it really may not be much better than spam. It also requires transmission of graphics, which again increase system overhead, as well as extra computational time to generate said images and to register and process the responses.
4. The system claims it will benefit from server-side cooperation, instead of keeping the method purely client-side. This means that users have to rely on the benevolence of their ISP to keep the system updated and maintained.
5. The graphical images contain a fixed number of very easily discerned letters that can be combined to form "easily-remembered" words. Once the letters are extracted, they can be recombined into known sequences, first of common English words, then popular web slang, then even transcribed into 1337 for the heck of it. Shouldn't take long to hack that.
6. Sub-addresses? So you want to explain this one to my parents? "I know you picked out one, simple email address that you really like and will never have to change, but now I want you to pick out a new one. It might be a good idea to change it once every few months or so, too." The whole purpose of an address is to allow someone to have a unique identity that can be easily found.

Honestly, this particular system sounds like it relies more on sheer grunt work and the wasted time of its users to make it work, rather than any innovative computer programming.

Won't be cracked in ten years? Ha!

[808140]

This is the most ridiculous an overly complex CAPTCHA system I've ever seen. To make matters worse, it is actually very easy to crack, using current technology.

Let's look at his "LUCKY" example to see why. So he has a picture of the standing man, the flower, and the sitting man, and all over the picture, he has a series of glyphs. As these glyphs are not distorted, they are easily extracted -- the whole point of this system is that distortion based CAPTCHAs are relatively easy to defeat, so he doesn't bother. In his example, he has 26 glyphs, corresponding to A-Z, but in practice, it isn't important what the set is -- only that it is small and finite.

Once this set is extracted, we know that the "password" is some permutation of this set. Because the set of possible characters in an e-mail address is much smaller than the set of possible characters in an actual password (in particular, e-mail addresses are case insensitive), brute-force cracking of this password is much simpler than brute force cracking of a UNIX password, for example. But luckily for us, it's even easier than that.

In the e-mail, he includes this "decoder" list.

• The Leaf of the Flower
• The Body of the Sitting Man
• The Head of the Walking Man
• The Vase
• The Left Arm of the Sitting Man

Of course, it should be clear at this point that this list would be relatively easy to extract from the e-mail, and further, that it tells you the exact length of the password, reducing the number of permutations to check to (in this case) 11,881,376.

Furthermore, a little bit of extra logic could reduce this number still further by noticing repetitive patterns in the list. So if "The Leaf of the Flower" appears twice, we know that the letters in those two slots are the same. And if the glyph set is unique (ie, no glyph appears twice), then we can reduce the number of permutations to at most 7,893,600.

Now, that's still a fairly large number of permutations to check, and at one point, it probably would have been enough. However, computational power is free now, at least for spammers. And it doesn't take much. Here's a sample perl (!) program I ran on my Debian GNU/Linux laptop (1.2GHz Pentium M).

for $i (1 .. 26) {
for $j (1 .. 26) {
next if $i == $j;
for $k (1 .. 26) {
next if $i == $k || $j == $k;
for $l (1 .. 26) {
next if $l == $i || $l == $j || $l == $k;
for $m (1 .. 26) {
next if $m == $i || $m == $j || $m == $k || $m == $l;
print chr(97 + $i) . chr(97 + $j) . chr(97 + $k) . chr(97 + $l) . chr(97 + $m) . "\n";
} } } } }

This just prints out all the permutations; of course they still would need to be checked.

$ time perl -e ' ... program here ... '
real 0m26.109s
user 0m25.746s
sys 0m0.020s

Not very long on a modern computer, eh? And written in perl, too, not exactly the fastest programming language in the world. Now consider that spammers have access to just about infinite CPU and bandwidth, thanks to their army of zombie bots, and that both CPU power and bandwidth are likely to increase at a rather rapid rate in the next decade. Furthermore, this is a worst case scenario -- success in a brute force attack tends to occur somewhere in the middle, not towards the end, reducing the necessity to actually go through all the permutations.

You don't think they'd try to crack it?

Plus, by his own admission, e-mail addresses can be shared. What does this mean in this context? I don't even need to get the e-mail address encoded in the CAPTCHA! If I can get any working e-mail address, even one, I get through! So the more active he is, e-mail wise, the more likely I can randomly strike a hit in the first hundred or so tries.

On top of