Episode 4: Humans Only

00:00:00
Broder: There was a procedure called add URL, where you would come to a search engine and you would say, you know, here is the pages I just made. But anyway we had this problem and, of course, there was spammers and there were people that were adding the same page millions of times and wrote little scripts to add their pages. So we had somehow to slow the spammers. And this is how we came up with the idea that we need a test to distinguish between spammers and humans.
00:00:46
Nat: That was Dr. Andrei Broder, the Chief Scientist at Yahoo!, discussing his time at Altavista in 1997, when he led the team that invented a little thing called CAPTCHA.
Alex: And CAPTCHAs are the subject of our program today. We’re going to be exploring the state of the art in CAPTCHA generation and circumvention
Nat: I’m Nat Friedman, reporting from the Bavarian capital of Munich.
Alex: And I’m Alex Graveley, reporting from sunny, cloudy, cold San Francisco.
Nat: And this is Hacker Medley, the podcast for curious hackers.
00:01:28
Nat: Let’s see here. Word verification. Type the characters you see in the picture below. Okay. C-O, I think that’s a U.
Alex: Wait, is this supposed to be a word or is this just letters?
Nat: I think it says [coralia]. Is that a word?
Alex: I don’t know.
Nat: I think it’s just sort of just random letters that are pronounceable. Okay. I think it’s C-O-U, and I think there’s an R like tucked in there and that’s, wait that might not be an A actually. I think that, yeah, that’s an A. And then this is either a B or an LE.
00:02:02
Alex: And here Nat is trying to solve a CAPTCHA, one of those squiggly word puzzles that you see all over the internet, where you have to type in the words that you see in order to enter a blog, comment or create a new mail account or even participate in an online poll.
Nat: The estimates are that we are, human beings as a species, are solving over 200 million CAPTCHAs every single day, but the very first CAPTCHA was implemented at AltaVista back in 1997. I interviewed Dr. Broder at his office in Santa Clara and asked him to tell us how it happened.
Broder: I think from the very beginning we had kind of an idea that the problem has to be some kind of a pattern recognition problem because this is one area where humans are much better than machines. And at some point it sort of started from, I think some lunch discussion and we were pointing out, someone was pointing out machines are not yet incredibly good at playing chess. How come humans cannot make so much computation are good at chess and it’s all about pattern recognition. So we knew that we need a pattern recognition problem. And then we came with this one.
00:03:07
Nat: How did you come up with the algorithm for distorting text?
Broder: That one is a lot easier to tell you how we decided what things are because actually I had a scanner at home, and scanners were not so cheap as today, and I had a scanner, and I believe was made by Brothers but I’m not 100% sure, and the scanner came with a manual and they also had some OCR software, which came with the scanner. And pretty much I looked in the manual and everything in the manual that they said it’s bad for OCR.
Andrei: We decided why don’t we make it. So one of the things that we’re saying, well it’s bad if the letters are misaligned, so we said okay they should be misaligned. And it’s bad if you use multiple fonts, so we said okay use multiple fonts. So it was all there.
00:04:07
Nat: That’s a pretty interesting story, huh?
Alex: Yeah, I love those old stories of like hacker epiphanies that solve really complex problems. The funny thing is that search engines today don’t even use this scheme anymore, they just use PageRank, which crawls the whole web. But instead, CAPTCHAs have turned out to be incredibly valuable for locking out spammers from pretty much all aspects of the internet.
Nat: You know, what’s kind of amazing to me is that these guys, this little team at AltaVista 12 years ago, they came up with this human detection technique and it’s pretty much exactly what we’re using today.
Alex: Yeah, I mean it looks pretty much the same to us but it is somewhat different, like the state-of-the-art has pushed these things towards being much harder for computers to solve.
00:04:54
Nat: Yeah, that’s true. I mean pattern recognition techniques and AI and computer vision have advanced a lot since then. And actually, that’s a good point, that kind of brings us to why Alex and I think CAPTCHAs are so interesting. That little image, that little rectangle of distorted text on your web browser, that is kind of like a window into the world of artificial intelligence and how it relates to human capabilities.
Alex: Yeah, and specifically it’s just like this really interesting set of problems which are sort of described in that they’re tests that computers can generate and grade the answer to but which they can’t themselves solve very easily but that humans can solve really quickly.
Nat: So here are the criteria. In order to be a viable CAPTCHA, a test has to be something that’s beyond the frontier of current artificial intelligence, but well within the capabilities of even really, really average people. So in a certain way, the set of all viable CAPTCHAs describes the ways in which people are still better and more capable than computers.
00:05:53
Alex: Yeah, and it shows you sort of the places where AI still has to grow and the limitations of what we can do, at least with regards to image recognition.
Nat: That’s a good point. But, of course, bad news is that AI is getting smarter and we’re not. So, you know, for the time being, at least when it comes to recognizing distorted text, we’re still well beyond computers but there’s no reason it’s going to stay that way stay forever.
Nat: Actually, Alex, by the way, the idea of CAPTCHA goes back to an earlier concept called a Turing Test.
Alex: I’ve heard of Turing Tests but it’s funny, I didn’t know that CAPTCHA stood for a Completely Automated Public Turing Test to tell Computers and Humans Apart, which is a pretty long acronym, but the important thing in there is that it is a form of Turing Tests. Nat maybe you can explain what that is?
Nat: Sure. So back in 1950 Alan Turing, the father of computing, wrote this really amazing paper called Computer Machinery and Intelligence. And what you have to understand is, in 1950 the transistor was only 3 years old. So computers were like really big, they were room sized, they were really loud and they didnít do very much. So it was in this world of fairly limited computer capabilities that Turing asked an enormous question, and the question was: “Can machines think?” And this is like a philosophical question, and in order to answer it you’d have to define what thinking is.
00:07:13
Alex: But I mean it’s interesting because people are just sort of sitting around with this big old computers waiting for punch cards to be processed and they had their heads in the clouds of these sort of abstract questions.
Nat: Right. Now instead of going in a total abstract route though, Turing devised, he invented a game, a very concrete game, which he called “The Imitation Game.” And the way people usually describe the game is, you have a person who’s a judge, and he’s communicating with someone else who’s in another room, who could be a computer or a human being and they’re talking through little text messages, like IM or something, and the question is: can the judge tell if he’s talking to a computer or a person?
00:07:50
Alex: That’s sort of what’s become the Turing test, which has been around so long at this point that it actually represents sort of this like unachievable holy grail of artificial intelligence. And it represents, if it ever gets solved it represents the point at which computers can really convincingly simulate the interactions between humans.
Nat: Yeah. Actually when I was a little kid my friends and I used to talk about the Turing Test, as you said like a kind of major milestone in artificial intelligence that we figured would have been solved by now. But I hadn’t actually read the paper until we started doing the research for the show and what I discovered is that what Turing actually wrote is different from what we just described. See in Turing’s original paper there’s three people, there’s a man, and a woman, and the judge, and they’re all in separate rooms, and the judge is trying to guess which is the man and which is the woman. And then what you do is you take either the man or the woman and you replace them with a computer, and the question is, does that change the judge’s accuracy from when he was talking with two humans?
00:08:51
Alex: Kind of a weird twist. And the computer actor in that specific scenario is like trying to trick the judge into thinking that the human is lying and it’s all very confusing. I still don’t fully understand why that question is posed in such an obscure and specific way but, you know, it’s Turing so chances are good that he was thinking about something that I’m not.
Nat: No question about that.
Alex: You know, it’s interesting because I think the Turing test is only hard to pass if you suspect you’re talking to a computer.
Nat: Yeah. Actually there’s a whole bunch of examples of people spending hours talking to even like really poorly implemented chat bots that don’t even put a delay in before they respond to someone’s IM or something like that. So they respond in a tenth of a second. And actually I found a really funny screenshot online, it turns out there’s a Russian chat bot that’s called cyber lover, and what it does is it goes into chat rooms and on IM and it poses as an attractive female and it enters IM conversations with men, and it kind of gradually convinces them through these faked human interactions to give up their personal information. And so the screenshot is of the dashboard for this chat bot and you can see all the men that it’s talking to and it reports as it gets their full name and their address and their credit card numbers and that sort of thing. We’ll have to put that up on the website.
00:10:21
Alex: I’m just going to go call Visa real quickly.
Nat: Getting back to the Turing test, though, there’s a bet on the site longbets.org, one of my favorite websites, between Mitch Kapor, who’s the founder of Lotus, and Ray Kurzweil, as to whether a computer will be able to pass a Turing test by 2029.
Alex: Yeah, and that’s the commonly understood concept of the Turing test, not the sort of gender guessing, gender faking one. Mitch Kapor is betting that computers won’t do it, which seems kind of negative to me, and Ray Kurzweil is betting that they will because his sort of whole singularity concept depends on it. And it’s a real bet. There’s $20,000 on the line.
00:11:04
Nat: So Alex, Turing posed this big question back in 1950, and then for 46 years, the AI community worked like crazy to try to build algorithms that could imitate human capabilities and even really simple uncontrolled situations. And they haven’t really quite got there. Actually I have a little blast from the past for you, Alex. Let’s listen to this.

DR SBAITSO CLIP

Alex: Oh man, It’s my very first shrink.
Nat: I don’t know if you remember that from the sound blaster?
Alex: I totally do. It’s like one of those programs that were on the, it was one of the demos that came on the sound blaster install disc.
Nat: Yeah. And then they had one with the talking parrot. You remember that, too? It had a different voice?
Alex: I kind of remember the talking parrot. Can you simulate the voice for me?
00:11:52
Nat: I don’t think I could. So because computers were having so much trouble at even really simple human tasks, let alone actually imitating people in a human context, the conventional wisdom about AI has been, for decades, that AI is in a rut. But then in 1996, a researcher at the Weizmann Institute in Israel named Moni Naor, he looked at the situation and he saw an opportunity. He figured that the things that people could do that AI was still failing to do, he figured could be used by COMPUTERS to automatically tell computers and humans apart.
Alex: Moni’s paper is called “Verification of a human in the loop or Identification via the Turing Test.” And he had a bunch of really cool ideas, some kind of novel concepts for the kinds of puzzles that you could pose to humans to determine if they were in fact human.
Nat: Most of those puzzles you’ll see are kind of in the areas of like sensory processing, image recognition, that kind of thing. Actually I think we should just read a couple.
Alex: Alright, yeah. There’s one that was the Gender recognition, which is actually kind of difficult if you show a picture of a face determining whether or not it’s a male or a female.
00:12:56
Nat: I have trouble with that just in real life.
Alex: Me, too. I got hit the other day because of it. And there’s facial expression understanding, whether the person in the picture is happy or sad. And then there’s identifying body parts, which actually seems like a really difficult problem to me for computers to solve, being able to tell which, in a random picture, whether or not you can highlight the arm or the leg.
Nat: Hereís one I like, filling in words. Given a sentence where the subject has been deleted and a list of words, select one for the subject.
Alex: That’s kind of cool. Sort of text comprehension.
Nat: And he also here mentions handwriting understanding, which is actually pretty close to what CAPTCHAs ended up being.
Alex: And he mentions also speech recognition, which is used in audio CAPTCHAs today for blind people.
Nat: So I mean Moni’s paper gives us a pretty good inkling of what CAPTCHA could be, but he wrote the paper before CAPTCHA was actually invented. And a lot of these particular ideas, well they didn’t turn out to be that great.
00:13:54
Alex: Yeah, things like drawing a circle around a person in a scene or a person’s body part is actually kind of annoying to do in practice. And also things like guess the word that fits into the sentence you can do by, if you index a lot of web pages you can determine which sentences are common or which word structures are very common.
Nat: And actually whenever you have a test that doesn’t have very many choices, like for example a binary choice, like male or female, if you just write a script that guesses randomly you’re going to be right 50% of the time. So that’s a pretty good pass rate for a pretty short script. So you have to give the user like lots of binary choices, like five or ten or something like that, to make the random guessing pass rate low enough or whatever. But anyway, totally independently of this paper that Moni Naor’s wrote, you had the work that was going on at Altavista. So kind of industry and academia were converging on the same point.
00:14:48
Alex: Right. And a few years later at CMU, this totally awesome guy named Luis von Ahn and his professor Manuel Blum wrote a paper where they coined the term CAPTCHA and sort of formalized the whole concept. One thing that’s totally awesome in this paper and one of the reasons I like CAPTCHAs so much is that it points out that CAPTCHAs are pretty much a win-win situation, “either the CAPTCHA is not broken and there is a way to differentiate humans from computers, or the CAPTCHA is broken and a useful AI problem has been solved.”
Nat: Yeah, I love that, too. I think that’s really cool. So since 1996, 1997, the time when AltaVista invented CAPTCHA and thee papers, CAPTCHAs have become super wide spread. Millions are soles every day. And, by the way, the average CAPTCHA takes about 14 seconds to solve. So if you multiply that out that’s a lot of time that’s being spent by people solving CAPTCHAs every day. And with all this work being done, Luis von Ahn saw an opportunity, and with a couple of other people, founded a company called reCAPTCHA.
00:15:48
Ben Maurer: So my name is Ben Maurer. I’m one of the cofounders of reCAPTCHA and I’m responsible for the design of our API and for our infrastructure.
Ben: So people are solving 200 million CAPTCHAs a day, let’s say, and what they’re doing is they’re spending time doing something that by definition a computer can’t do. That’s automatically valuable because if we could give people a task that is useful then we’re getting something that we don’t otherwise have the ability to get. And so we said what can we do with all this, you know, with all this human computation power?
Alex: So just to cut in, in case you don’t know what reCAPTCHA is, you’ve probably seen these before: they’re the CAPTCHAs that have two words that you have to type, the words are usually in some kind of old or smudgy print face, and there’s maybe a line drawn through them.
Ben: And what we came up with is instead of having one word in the CAPTCHA we have two words and one of them is sort of a fake. It’s not part of the CAPTCHA it’s just a word that we don’t know what it is and we want you to tell us what it is and we do that to digitize books and newspapers and other content that computers can’t read.
00:17:00
Nat: So then what they do is they run two different OCRs over the text. Ben told me that they use a couple of commercial OCRs, and an open source one called Tesseract, which comes from Google, which is now considered pretty state of the art. And they identify words that the OCR software couldn’t recognize or doesn’t have a lot of confidence about. Ben explained it pretty well.
Ben: So OCRs are never 100% sure whether they’re right or not. But what we do is we take multiple OCR engines that use different algorithms and they tend to have failures that aren’t 100% correlated with each other. If they both agree then we sort of say we’re, it’s very likely that the word is correct. We use a few other signals such as, you know, does the word fit in this sentence? Like if you have, you know, one sentence we had in an old newspaper was that the motors ears were running down the street. And motor ears is something that just doesn’t occur in the English language and what happened is a C looked like an E to the OCR and we have the ability to say motor ears is a bigram that just doesn’t typically appear and it’s suspicious.
00:18:07
Nat: By the way, Alex, I thought it was nifty that they also use bigram probabilities to help identify which words the OCRs failed to recognize.
Alex: Yeah, I suspect that they’re using the one provided by Google where they have this huge bigram index, this big database you can download for a small fee, and it basically shows the occurrence of combination of words all over the web.
Nat: It makes sense actually also because Google ended up buying reCAPTCHA pretty recently.
Alex: Yeah. And reCAPTCHA has APIs in a whole bunch of languages. So it’s sort of a general-purpose CAPTCHA platform that you can just embed into your site. And these things are used everywhere, on Facebook, TicketMaster, Craigslist, wikipedia…everywhere..
Nat: Ben told, Alex, that reCAPTCHAs actually getting a whole lot of old books and newspapers transcribed.
00:18:55
Ben: We’ve done about, I think about 50 years worth of the New York Times already and currently reCAPTCHA users are solving 50 million CAPTCHAs a day
Nat: And by the way, Alex, The Times is paying reCAPTCHA for all that digitization work that they’re doing.
Alex: That’s pretty awesomely shrewd right there!
Nat: Definitely.
Alex: And they’re doing all this in pretty standard stuff with Python, nginx, and of a lot of intelligent hackery.
Nat: Actually with all that scale, solving 50 million CAPTCHAs a day, I asked Ben a little bit about the architecture, and specifically how do they store the CAPTCHAs on disk. Is it just on file per CAPTCHA image? And here’s what he saidÖ
Ben: Yeah, that was originally how things worked and that’s a pretty big disaster just because every time you serve a CAPTCHA then you end up doing a disk seek. And when you have a server that can serve a few thousand requests per second you can’t do a few thousand disk seeks per second. It’s just too slow.
Ben: And we found that one file per CAPTCHA, when we would get substantial load on the server the latency would become very high. So we actually use a custom file format to store the CAPTCHAs that allows us to load a bunch of CAPTCHAs into memory at once.
00:20:16
Alex: That’s great. That’s another one of those sort of problems that you only run into when you have really large amounts of scale.
Nat: Yeah, and it’s cool to peek under the covers of an operation like that..
Nat: Now, by the way, reCAPTCHA does just take the scanned word off the page and present it to you unmodified, they actually distort the word a little bit before you see it in the CAPTCHA.
Alex: Right, like I said, they maybe draw a line draw a line through it or they make it wavy. And recently they started using these like XOR blobs where they would sort of switch the foreground of the word with the background of the word for part of the word.
00:20:50
Nat: And the reason, Ben told me, that they do this is because, even though OCR software couldn’t recognize the word, you know, OCR software is not really designed to solve CAPTCHAs, it’s trying to get a balanced view of the document, so it might be possible to build an algorithm that could get enough CAPTCHAs right to be annoying. For example, Ben said that if you took a standard OCR software software and just tweaked it’s algorithm to use its second best guess for what the word could be instead of its best guess that might solve enough reCAPTCHAs to be a problem. So that’s why they add extra distortion just for extra safety.
Alex: Yeah, and everyone we’ve talked to has basically said the same thing, which is that reCAPTCHA is one of the toughest CAPTCHAs out there, which is important because you only need, say, 10% of CAPTCHAs solved by your bot to create thousands of fake Gmail accounts or get a lot of SPAM comments through. So the team at reCAPTCHA works really hard to make their CAPTCHAs as difficult to break as possible, while still trying to keep them easy for humans to solve.
Nat: And they’ve had a pretty good balance but CAPTCHA was not always as secure as it is now. And, Alex, there’s a funny story about that.
00:22:04
Nat: So back in the fall of 2004, Microsoft’s hotmail team, like most webmail services, one of their big concerns was SPAM, and specifically SPAMMERS using hotmail to send SPAM.
Alex: Yeah, and Nat, like every other webmail service on the planet, with the sort of first line of defense is to ask people that are creating a new account to solve a CAPTCHA.
Nat: So hotmail was depending on CAPTCHAs to protect them from SPAM. And they wanted to know: how safe are these things anyway? You know, hard would it really be to build an algorithm to break a CAPTCHA? So being Microsoft, of course, they have a really substantial research division right on campus. So they called up Microsoft Research and got in touch with a scientist in the division there named Kumar Chellapilla, who is a machine learning expert.
00:22:52
Kumar: Yeah, so my actual relationship with CAPTCHA comes from machine learning. So my actual PhD research work was on computational intelligence, and this is trying to build intelligent adversaries or agents that could act and train against humans.
Kumar: So these are models that you could train by giving it like input and output signal. And for some, for my PhD work I did mostly game playing like checkers and chess and so on.
Nat: When Kumar joined Microsoft Research, he did some work on OCR technology and handwriting recognition specifically for their tablet PC project.
Kumar: One of the common areas is signature analysis. How do you get a computer to look at two signatures and tell it to accept the signature or not? These are very, very hard problems.
Nat: And so Kumar sat down and he looked at the most prominent CAPTCHAs on the web from the biggest companies on the web at the time, and here’s what he found.
Kumar: And I was surprised. I have somewhat of an undergrad understanding of image processing, a doctorate level understanding in machine learning, and as I started applying some of these techniques, it was very easy to undo the challenges that were being put forth by the CAPTCHA. And I was so surprised at how quickly this happened, that we immediately, I think in November 2004, December 2004 there this famous machine learning conference called neural information processing systems then that was the first place where we presented a poster.
00:24:17
Kumar: And it was amazing. We had about half a dozen different CAPTCHAs that were provided by several different people in the industry and we could show that many of them you could break like one out of two, one out of four, two out of three.
Nat: Now, Alex, as it turns out, solving a CAPTCHA is something that actually breaks down into two separate problems: first is the problem of segmentation, and then comes the problem of recognition.
Alex: And I didn’t know this beforehand but segmentation is the process of breaking a picture of a word up into individual letters. And the recognition is then taking each one of those sort of subpictures and identifying which letter it represents.
Nat: And what Kumar quickly discovered was that recognizing the letters in most of the CAPTCHAs at the time was pretty easy.

[00:025:01]

Kumar: one of the problems we already solved by the time I started looking at CAPTCHAs was if you give me a single character, moderately distorted but not devastatingly distorted, then you sort of use your mouse or you point to the center of the character, I have techniques that can learn from that signal and basically give you the character that is there at that point.
Nat: The tool that Kumar was using was a special kind of neural network called a convolutional neural network.

Actually, why don’t we start off and tell people what neural networks are.

Alex: Yeah, sure. Neural networks are this sort of pretty widely-used technique in AI that’s been around for a really long time. And the basic idea is that you have these neuron-like elements that have inputs and outputs and the inputs and outputs are sort of arranged with inputs going into other neurons and outputs going into other neurons. So for a given neuron each input has its own weight, which multiplies the input value. The neuron adds up those weighted inputs, and if it’s greater than a certain threshold then the neuron fires, meaning that it sends a signal to its output. And the output signals of all these neurons sort of propagate through the network until you get the “answer” on a specific set of output neurons.
00:26:15
Nat: Exactly. So the basic idea for convolutional neural networks came from an experiment that was done back in 1959 by these two guys, David Hubel and Torsten Wiesel. What they did was they took a cat, and they put it under anesthesia. And then they inserted some electrodes directly into the cat’s visual cortex. And they opened its eyes and flashed different patterns of light and dark lines in front of the cat. And what they found was really interesting, they found that some neurons in the cats visual cortex fired rapidly in response to lines at one angle, and some neurons fired rapidly in response to lines at a different angle. So there was some angle sensitivity to different groups of neurons. And there were other neurons in the visual cortex that were totally angle-independent.
00:26:57
Nat: So what happened subsequent to that is, you know, this was obviously a pretty big result in neurology but some computer scientists got a hold of it and what they realized is they could take neural nets and they could arrange them like a cats visual cortex was arranged. So the lowest level you’d have neurons which are recognizing simple features in the image, like corners, edges at a certain angle or end points in certain regions of the image. And then there would be subsequent layers, which are usually called the hidden layers, in the neural network, and these subsequent layers would sort of combine those basic features to detect higher-order characteristics or features in the image. And if you have enough of those and the right kind you can start to recognize even really distorted letters or objects or things like that. So it turns out that this special type of network, this convolutional neural network, which is sort of roughly based on the way vision works in mammals, is really good at image recognition.
00:27:53
Nat: Specifically, these networks were really good at recognizing handwriting. And so when Kumar got assigned the whole CAPTCHA project he’d already been through Tablet PC and he had all this handwriting recognition experience and therefore he had this really powerful image recognition tool at his disposal. And when he took this thing and he pointed it at the state of the art CAPTCHAs on the web it just blew them away.
Kumar: So four out of five characters I’d be able to recognize correctly or certainly nine out of ten. So that was sort of like, that was the platform for almost all of my techniques. I would try to reduce every CAPTCHA I saw out there with some ad hoc processing down to a place where I could just give it maybe like five or ten locations where I thought characters were and then this system would, it’s not free because you have to label like thousands and thousands of these laboriously but it’s a very automatable technique.
Nat: So, Alex, with the recognition problem solved, for Kumar breaking CAPTCHAs basically came down to just identify the locations of the letters. And this is the segmentation problem. And in the CAPTCHAs that existed on the web in 2004, segmentation was actually not that hard. Kumar explained to me how he solved from Ticket Masters CAPTCHA.
00:29:01
Kumar: They were exclusively using these grids of slanted lines. They were almost regular but not exactly. They would tilt a little bit between the different parallel lines in the grid, but their text was always horizontal so, and the text was always thicker than the grid. So if you did some blurring the background lines would blend into the background and then the words will stay up in the front.
Kumar: So if you had the word hello on a white piece of paper, hello being typed in black, and then you could get a stat of that page to this connected components algorithm, and what it will do is it will take, it will start at one of the black pixels, let’s say the H, it would grow that by looking at the neighboring black pixels and it will slowly grow it into the letter H. Then once it has reached the edge of H it will no longer blend into the background so it will remove that letter H as a character. And you can repeat this iteratively until you get all the characters. So that’s another one where I think the Ticket Master one was reduced down to one of those and then we could build that out. Register.com also had a similar one. The very early MSN Hotmail one also did not have enough arcs, so some of the characters would not even be touching so you could easily eliminate those.
00:30:23
Nat: So what do you do when the characters are touching?
Kumar: So if this island analogy works, you can think of everything in the background is a big ocean because it’s relatively flat and there’s these islands sticking out. You could grow the islands, let’s say there’s more sedimentation and the land mass kinda moves out into the water, then if two islands are very close to each other then they may grow and they may connect each other. So that allows you to sort of connect things. And that’s usually like a growing operation standard image processing, things like halos and so on you can add to objects that way.
00:30:56
Kumar: You can also do erosion, which is the opposite. You remove pixels that are very close to the edge of the character, so in the same island sense, you’re losing, because part of the island is eroding into the ocean and so that way you can separate two characters that are connected. So if you have two, let’s say you have two O’s that are connected by a thin line, unless for a simple suggestion the O’s are more like filled in circles, then as you erode the circles are relatively in all directions, so they may become smaller circles still filled in, but the line that’s connecting the two circles would slowly get to a point where once it becomes really thin, one pixel wide, another step of erosion would just completely cause the connected pixels to go away. And now you’ve broken two O’s connected by a line into two O’s. And once they’re separated you can then do the opposite. You can now start to grow them back. And so if you do something like the four steps of erosion followed by four steps of growing you would lose every line or anything that was thinner than four pixels wide.
Kumar: And so that’s like a common, you erode to just make them disconnected, then you grow them back so that pieces of character that provide the erosion connect back.
00:32:13
Alex: That’s a totally awesome description, but I suspect in practice it’s a lot more nuanced and probably required a PhD to understand what the hell’s going on.
Nat: Well actually the paper’s pretty well written. It’s pretty accessible. We’ll put a link on our website if you want to check it out. But what he basically said in the paper was: recognizing distorted characters is solved. If you want to make CAPTCHAs really hard, lean on the segmentation problem because identifying the locations of the characters is really surprisingly hard if you do things like make them touch or don’t just do totally trivial things to your CAPTCHA. So the best CAPTCHAs on the web today have adapted to pose really harder segmentation problems.
Alex: It seems so weird to me that image recognition can, you know, identify a letter, it just can’t figure out where it is.
00:33:00
Nat: I know, right? It’s not intuitive at all. Now actually, even though a lot of these issues were pointed out five years ago in Kumar’s paper, and Google and Microsoft and Yahoo and reCAPTCHA now have really good CAPTCHAs that are hard for computers to break, a lot of the CAPTCHAs that you find on the web and in the wild, and you and I have both run into these, they still mostly pose a recognition problem and not a segmentation problem. Actually, I asked Dr. Broder about this, and here’s what he said.
Broder: You know, I see some CAPTCHAs that clearly are very hard for humans to solve but in fact they don’t introduce any difficulty for computers whatsoever. They are simply creating some extra annoyance for humans without getting any quality. I mean people have to realize what are the hard problems and what are not the hard problems. And some of the CAPTCHAs are totally silly and I’m sure that you can use them as an exercise in any course in pattern recognition and people will solve them.
00:34:08
00:34:19
Alex: If you look around the web today you can find like little Python scripts or other little programs that you can run to break some of the weaker CAPTCHAs out there.
Nat: And, Alex, actually I have a little treat for us. I did some googling and I found a university student in Northern England who wrote a particularly cool CAPTCHA solver.
Shaun: Well, my name is Shaun Friedle and I’m the author of Megaupload auto-fill CAPTCHA, which is a GreaseMonkey script for Firefox which auto completes the CAPTCHA on megaupload.
Alex: Woah! That’s such a great hack, right? Like this guy decided to start solving CAPTCHAs in the browser using Javascript.
00:34:55
Nat: Yeah, I mean this is the definition of like a good hack basically. I mean what Shaun Friedle did is he wrote a GreaseMonkey script that solves just this one particular CAPTCHA, on a site called Megaupload, which I’ve never heard of before but apparently is like one of those websites like rapidshare where you can upload a file and people can download it. And they use CAPTCHA to protect the download link from bots. And I asked Shaun how he got into this, what motivated him to do this in the first place.
Shaun: And then I came across a farm thread on the user scripts to [our] site. Someone else was asking if it was possible to decode the reCAPTCHA script in using a GreaseMonkey script and all of these people were saying no that’s stupid, there’s no way you will be able to do it, that’s impossible.
Nat: And so you took that as a challenge, huh?
Shaun: Yeah, I thought well I don’t know if it’s really possible in the reCAPTCHA, I thought well I can probably try and do that just in GreaseMonkey purely in JavaScript on the megaupload CAPTCHA. And at that time I had done no image processing in JavaScript. In fact, I ran about 100 types in JavaScript before that point so I’m not really a JavaScript programmer. So I started researching whether it was possible and I found out using the canvas functionality in HTML 5 you could do some image processing and eventually built it from there and managed implementing the entire thing in JavaScript.
00:36:19
Alex: I actually hadn’t heard of anybody doing sort of external image processing using Javascript and CANVAS like that.
Nat: Yeah, actually Sean was really humble and he said he’d never done any image processing in Javascript before. But I think like almost no one had ever done image processing in Javascript before he wrote this hack. And then it ended up on John Resnick’s blog, who is the author of [J Quarry] and a lot of people found it pretty interesting. That’s actually how I found out about it. But it does seem like a technique that could be useful lots of different places. Anyway, Shaun had also previously read this game programming book, and learned about neural networks from that, and so he implemented a neural network in Javascript, and then he manually trained it by typing in a whole bunch of CAPTCHAs himself to recognize the megaupload CAPTCHA.
00:37:02
Alex: And his script still works?
Nat: Yeah. He told me it can solve the Megaupload CAPTCHA in about 200 milliseconds.
Alex: That’s not bad. I think it’s a neat hack because it’s not necessarily anything novel research wise but doing it all in Javascript inside the browser and being a novice. It just seems like really educational.
Nat: We asked everyone who has been a CAPTCHA like what they think when they run into CAPTCHAs on the web and he said the thing he thinks is that about 60% of the CAPTCHAs he encounters he could probably hack with his GreaseMonkey script with a few hours of modifications. And of course he’s talking about the CAPTCHAs, not the big company CAPTCHAs but the ones that don’t pose really hard segmentation problems.
Alex: Yeah, and that totally goes against my original thinking when we started this podcast, which is that the way you can be sure that a CAPTCHA works is by writing your own because you’ll be able to sort of hide anonymously on the internet because people won’t spend time solving your particular CAPTCHA. But it turns out that, you know, unless you’re kind of tracking the leading edge in image recognition technology, like reCAPTCHA is, you’re CAPTCHAs are probably going to end up really, really trivial to solve.
00:38:12
Nat: And you’re kind of right on one count though, Alex, which is that if you’re site is really tiny and nobody cares about it they’re not going to try to bother to break your CAPCHA anyway. But the cool thing with reCAPTCHA of course is that they’re going to always keep up with the latest attacks. It’s like a platform that’s always going to evolve with the attackers.

Now we’ve been talking about some pretty sophisticated ways of attacking CAPTCHA. But there’s one very easy way to break a CAPTCHA we haven’t mentioned yet.

Alex: Is this the sort of legendary porn attack that I’ve always heard about?
Nat: Well that’s one. Why don’t we talk about it first?
Alex: Yeah, so I always heard that, like there’s always been this rumor that porn sites would stick CAPTCHAs up in front of people who wanted to look at porn images and they would have to solve the CAPTCHA in order to move on and see the pornographic image. And that CAPTCHA they solved would then be forwarded along to some script that was creating an email account or posting a comment.
00:39:07
Nat: This is like exactly the kind of story that’s designed to just be spread all over the internet because it involves like a cool hack and pornography. But it turns out it’s not really an issue. The volume of CAPTCHAs that would be solved by this technique is just too low to actually make a dent. And it’s not really a very competitive thing for a port site to do: for every one site that issues CAPTCHAs in front of their images, there are a thousand that won’t. So it doesn’t add up economically. There is another way that humans can be used to break CAPTCHAs that is actually is a bit more of an issue.
Alex: Oh is the sort of like CAPTCHA Farm things in India with lots of people solving CAPTCHAs.
Nat: They actually prefer the term “CAPTCHA bypass service.”