The Proof-of-Work CAPTCHA: Prove you are a computer!

Copyright (c) 2013 by Joe Garcia-Montes. All Rights Reserved.
Patent Pending.
For more information about this technology please use this forum to contact the author.

Computers vs. Humans

The acronym CAPTCHA, which stands for (“Completely Automated Public Turing test to tell Computers and Humans Apart”) denotes a challenge-response test used to ensure that the response is generated by a human (von Ahn et al., 2003). A CAPTCHA is a kind of reverse Turing Test, in which a computer presents a user with some task that is considered to be easy for a human but very difficult for a computer.

The need to use CATPCHAs to ensure that the entity accessing the computer is a human arose because of extensive abuse of services such as Yahoo Mail, which were being subverted by intruders who would sign-up for thousands of e-mail accounts using “bots” or networks of compromised computers to send spam messages. The solution was to require the users to solve a CAPTCHA in order to open an account or perform some other activity.

CAPTCHAs in some form or another have now become commonplace: all the high-traffic volume sites, such as Ticketmaster, Facebook and Twitter have some type of CAPTCHA, and so do millions of smaller websites and most blogging sites.

In general, a CAPTCHA is simply some form of hard AI problem that is known to be both easy for humans but very difficult for computers. In fact, part of the incentive for developing these CAPTCHAs—aside from the desire to keep the spammers away—is the concept that, given a sufficiently hard AI problem, a CAPTCHA will either succeed in identifying the humans or, if it fails, it can only do so if there is some significant improvement in the state of the art in pattern recognition, be it either in recognizing characters, images or possibly spoken words (von Ahn et al., 2003).

The most common type of CAPTCHA uses distorted words, where a word is picked out of some dictionary, or simply some letters and digits chosen at random; the characters are then distorted or obscured in various ways, usually by applying some type of morphological transforms to the characters and then adding some type of background noise. The user is then presented with the distorted image and asked to type the word or characters that appear in the image.

With a properly designed CAPTCHA most humans will pass this test, but pattern recognition programs should find it extremely challenging.

Other types of CAPTCHAs have been developed. For example, ASIRRA (Elson et al., 2007) is an image-based CAPTCHA that presents the user with 12 pictures containing cats and dogs and asks the user to identify all the cats by clicking on them; some image CAPTCHAs such as those from Solve Media combine a form of advertising with the CAPTCHA.

The problems with CAPTCHAs

Unfortunately, the widespread use of CAPTCHAs has spawned an entire underground industry of CAPTCHA-solving software, services and user forums dedicated specifically to help spammers and other intruders to bypass the CAPTCHA authentication process.

The economic aspects of CAPTCHA-solving have been examined in detail by (Motoyama et al., 2010) who describe a complete CAPTCHA-solving ecosystem and the business model underlying these activities, complete with buyers, sellers, intermediaries and even specialized advertising venues.

Commercial CAPTCHA-solvers come in two varieties: Automated Solvers and Human-Labor Solvers. The first group includes programs such as Captcha Sniper and Xrumer, which claim to solve most of the common types of CAPTCHAs with accuracies ranging from 27% to 100%. Human-Labor Solvers, such as the delightfully named “Death by Captcha” (http://www.deathbycaptcha.com) use workers in low-wage countries to “outsource” the task of solving the CAPTCHAs.

Figure 1 shows the pricing schedule of www.deathbycaptcha.com. Spammers can buy blocks of solved CAPTCHAS at these prices online—and please notice there are no volume discounts, a single CAPTCHA costs $0.00139 US to solve.

5k CAPTCHAs Only US$6.95 per package
10k CAPTCHAs Only US$13.90 per package
25k CAPTCHAs Only US$34.75 per package
50k CAPTCHAs Only US$69.50 per package
100k CAPTCHAs Only US$139.00 per package

Figure 1. The Death by Captcha pricing schedule

In the Human-Labor Solver scenario the CAPTCHA-solving service acts as an intermediary: the spammer “scrapes” the CAPTCHA images from the site being attacked and sends these to the CAPTCHA-solving service, which in turn forwards the image to one of possibly thousands of CAPTCHA-workers in low-wage countries; the CAPTCHA-solving worker then sends the words or letters required to solve the CAPTCHA back to the CAPTCHA-solving service which then forwards the solution back to the spammer.

CAPTCHA-solving software can be purchased at prices that range from $79 to $3,500, but judging from the comments in the spammer forums they seem to have very inconsistent performance. Human-Labor Solvers, on the other hand, have much higher accuracy—reasonably so, since the task is actually being done by a human—but also cost more, in that the purchaser has to pay for every thousand CAPTCHAs solved. However, competition among these Human-Labor Solvers has brought the price of these services down to as low as $1.00 US per thousand solved CAPTCHAs (Motoyama et al., 2010).

Can we defend against human CAPTCHA solvers?

The problem of defeating CAPTCHA-solving software might be amenable to some type of technical solution—we just need to find a really, really hard AI problem, providing that it is also one that is easy for humans. The problem of human CAPTCHA solvers, on the other hand, cannot be addressed by increasing the difficulty of the task—after all, CAPTCHA workers in low-wage countries are human—so if we were to increase the difficulty of the CAPTCHA until these human workers fail then the legitimate visitors of the web sites would also fail!

Clearly, any solution to the problem of human CAPTCHA solvers will have to be rooted on the economics of CAPTCHA solving, given that the very reason why CAPTCHA solving is a paying business in the first place is the existence of very large wage differentials between high-wage and low-wage countries. Motoyama et al. make this exact same point when they state that “we have argued that CAPTCHAs, while traditionally viewed as a technological impediment to an attacker, should more properly be regarded as an economic one” (Motoyama et.al., 2010, p.17).

Given the current architecture of the Internet, which is fully distributed worldwide, plus the fact that there are many jurisdictions in which spammers and hackers can operate with near-impunity, legal solutions to stop spammers seem very remote. There is very little that can be done to prevent spammers from hiring servers in spammer-friendly ISPs. Likewise, there is essentially nothing that can be done to prevent the spammers from visiting web sites, collecting the CAPTCHA images and sending them to the Human-Labor CAPTCHA solvers, and no practical way to stop these companies from forwarding the CAPTCHA images to their workers and then returning the solution to the spammer.

The only way to stop or reduce this activity is to find some type of “sand” to throw into the CAPTCHA-solving “gears”, and the only “gear” that we can identify and might have some way to gum up is the computing infrastructure required to go from the victim’s page to the spammer, from the spammer to the solving company, from the solving company to the human solvers and then back to the site being victimized.

As it is the case with any type of economic activity, if some fee or cost can be imposed into the system this will cause “friction” and, at the very least, slow down the velocity at which transactions are carried out, or if the friction can be made sufficiently high, then the velocity will go to zero.

Other than the cost of the human workers, CAPTCHA-solving—of any variety, human and otherwise—is bound by three hard constraints: bandwidth, computing power and time. Practical solutions to this problem need to come from “pushing” the spammers, solving companies and/or workers against these hard boundaries beyond the point where the cost of the spamming exceeds the economic benefit to at least one of these players.

The Proof-Of-Work CAPTCHA: Prove you are a Computer!

Proving that someone is human seems to be a regrettably easy task: if you are not human—or not human enough—to pass the test you can always enlist a human accomplice to take the test for you. Increasing the difficulty of the test cannot be done without driving all the humans away—including the legitimate users. Proving that you are a computer, though, is something that can be made arbitrarily hard.

One possible way out of the difficulties that we have outlined above is to separate the difficulty of solving the CAPTCHA from the work that is required to be performed. The CAPTCHA can still be one of the current solutions, distorted-characters, images, sounds or little videos—but should still be made be as hard as possible for a computer, obviously, because we want to stop the CAPTCHA-solving software—but easily solvable by humans. Additionally, though, we will require some other work to be performed, not by the user, but by the user’s computer and will make a proof that this work was performed mandatory. Other than the presence of the CAPTCHA, this is essentially the same concept used by electronic currencies such as BitCoin (Nakamoto, 2008).

Basically, for every CAPTCHA that we send the user we will also send a problem that needs to be solved by the user’s machine. The same code that is used to present the CAPTCHA to the user, which needs to run in the user’s browser, will also have a routine that executes to solve the problem and returns the results to the server. In this scenario, just solving the CAPTCHA is not enough: the response needs to include not only the solution to the CAPTCHA but the proof of work in order for it to be valid.

For example, we could use the same approach as in the BitCoin mining, in which the user is given a hash and asked to produce a number that, when hashed together with the incoming hash, will result in an output hash that is numerically smaller than the incoming hash. This is a task that can only be done by trying-out multiple values—there are no known shortcuts to calculating hash values when a strong cryptographic hash algorithm like SHA-256 is used. The difficulty of this task can be adjusted by selecting the value of the incoming hash, such as it is done in the BitCoin digital currency so that, on average, it will take some number of seconds to find this magical number.

The amount of work required to find the number should normally be set at or below the number of seconds it takes a human to read, interpret and type the solution to the CAPTCHA, to avoid penalizing the legitimate users. In the meanwhile, though, the user’s machine will have to calculate the appropriate hash, which needs to be sent to the server together with the solution to the CAPTCHA. Calculating this hash will force the user’s machine to perform some number of calculations, generally on the order of millions.

The reason why this approach may drive the spammers out of business is that the work will have to be done by somebody’s machine. In the case of the legitimate user, the machine doing the work is the one that they are using to access the web site, and the amount of computing power required can be adjusted so that is no great burden—in fact, users with modern machines might not even notice that something is being computed, and in any event they are required to solve only one hash problem per CAPTCHA, so for the legitimate users this calculation should not pose any major usability problems.

The spammer, on the other hand, is now faced with a very different situation: providing that this technology becomes widespread, practically every site they try to attack will require them to perform some number of computations, let’s say, for example, that we send them a hash problem that will require, on average, 30-40 seconds worth of computation. Now they will not only have to solve the CAPTCHA, either with a human-solving service or with CAPTCHA-solving software, but will also be forced to pay for the computing power required to calculate the hash for each and every CAPTCHA, and therefore to “spend” the computing time required to do the calculations, because the solution to the CAPTCHA image will not be accepted unless it is accompanied by the proof-of-work. Spammers are currently attacking many thousands of sites per hour—commercial lists of “profitable” spamming targets go into the hundreds of thousands of sites—but every target will now force them to spend perhaps 30-40 seconds worth of processing time.

If the spammer attempts to perform the computations either one of two things will happen: the spammer will have to own—or hire—a very large amount of computing power, which will increase their cost of solving CAPTCHAs, or the spammer will be able to attack fewer sites because of the computing power required, which will result in them sending much less spam, which will lower their income, hopefully to the point where the economic incentive to spam are removed as well.

Another possibility is that the CAPTCHA-solving companies, when faced with this problem, might respond by purchasing the necessary hardware and do the hash computations themselves. They would also have to modify their code to perform the calculations, but all this does is shift the cost from the individual spammer to the solving company, which will incur in much higher infrastructure costs, which will force them to raise the price that they charge for solving the CAPTCHAs. Given that these companies currently act as intermediaries between many thousands of spammers and the many thousands of workers and solve many millions of CAPTCHAs per day the additional cost may very well drive some of them out of business altogether.

A third possibility is that these CAPTCHA-solving companies might try to shift the computing requirements over to the worker’s computer—that is, they would continue acting as intermediaries, but now it is the worker’s computer the one that has to do the work and supply the proof-of-work, in addition to the solution to the CAPTCHA. The problem with this scenario is that now the worker’s machine will have to take the same number of seconds to do the work—beyond just solving the CAPTCHA—which will slow down the worker.

In this regard, we should also note that the practice in this industry is that when a CAPTCHA-solving company sends a CAPTCHA to a worker, it also gives the worker a certain number of seconds to solve the CAPTCHA, even to the extent that their worker interfaces tell the worker how many seconds he/she has left to solve the CAPTCHA. These companies measure not only the worker’s response time but also their accuracy, and will ruthlessly terminate any workers that are either too slow or who make too many mistakes, in what might be one of the worst examples or Taylorism ever.

CAPTCHA –solving companies even advertise their average response time and solving accuracy. For example, Death by Captcha displays these statistics for their visitors in real-time:

Average solving time 1 minute ago: 15 sec
5 minutes ago: 16 sec
15 minutes ago: 16 sec
Today's average accuracy rate: 95.3 %
(updated every minute)

If the CAPTCHA-solving companies attempted to offload the Proof-of-Work computations to their workers then their average solving time would go down, because the worker’s machines would not have sufficient capacity to perform the required calculations for multiple hashes simultaneously. From the numbers above we see that the average solving time was around 15 seconds, which is consistent with the results described by Motoyama et al. Forcing a 30 or 40 second Proof-of-Work calculation on the worker’s machine will have a substantial effect, as the hash cannot be returned to the spammer without the Proof-of-Work, or else it will be rejected.

Even if the worker’s software is modified so that the worker is allowed to solve multiple CAPTCHAs using several sessions while the hashes are being computed, their computer will now have to perform that much more work, so there will be a sharp limit to the number of CAPTCHAS that the worker can solve per hour, because of the limited amount of processing power at their disposal, which will slow down the rate at which they earn CAPTCHA-solving fees. If this rate can be lowered enough the workers will either make too little money and leave the CAPTCHA-solving business for more profitable occupations or else will have to be paid more money per CAPTCHA, which will increase the costs for everybody all along the chain.

There is also the possibility that a hacker can use a “botnet” which is a network of machines that have been compromised—perhaps by a virus or a Trojan—that acts under the control of the hacker. Conceivably, a botnet could be enlisted to do the hashing calculations while the human solvers deal with the CAPTCHA and then the solution to the CAPTCHA and the Proof-of-Work could be put back together and forwarded to the spammer. This solves the issue of forcing the human workers to spend too much of their computer’s power calculating the hashes, and does not require the CAPCHA-solving company to own the necessary hardware.

The problem with this scenario, though, is that botnets are not free. Botnets are expensive and large botnets are difficult to assemble—a hacker that “owns” such a botnet can rent it out, so the use of a botnet also has a cost, whether it be a direct cost or an opportunity cost in the form of the income that the hacker could receive from renting the botnet or by having it perform some other work. This cost would have to be passed to whoever is hiring the botnet, so somewhere along the chain there would be an increase in cost. In fact, for anybody that does not “own” a botnet, and which would therefore need to rent one the cost of renting the botnet is likely to be higher than the cost of hiring additional computers at some hosting center to do the hashing.

Finally, all the players in the chain could agree to split the work. For example, the spammer could calculate the first 1/3rd of the hashes; the CAPTCHA-solving company could allocate computer time to solve the next 1/3rd while the worker’s computer would be given the final 1/3rd of the hashes. This is similar to how BitCoin miner pools split the mining work among the members. Just as in BitCoin mining, and depending on how the code is written, either one or more of them will find an answer or there will be no answer, in which case the CAPTCHA will fail, but in most cases this type of work-sharing would produce a valid hash without unduly burdening any of the players.

For example, if we were to send the client a Proof-of-Work that requires, on average, 45 seconds of computation each player in the chain would agree to perform 15 seconds worth of computation, and would “split” the range of numbers that are tried in three parts so as to not duplicate the efforts. In most cases—but not all—one of the players in the chain will succeed in calculating a valid Proof-of-Work hash. A few hashing attempts will fail, and the spammer will in that case be forced to either re-send the CAPTCHA or abandon it. In any event, with this work-sharing scheme the spammer will still incur a 15-second penalty for every CAPTCHA, and so will the CAPTCHA-solving company and the CAPTCHA-solving worker. So far, this would be a tolerable amount of work for everybody, but … well, there are very, very few occasions in the lives of computer professionals when we are actually given the gift of messing around with spammers, but this is one of them—and spammer pain is such a good thing, it builds character!

First, we can force some pain—in the form of a time delay—into the spamming chain by simply tying the value of the initial hash to the correct answer to the CAPTCHA. Please note that this does not involve sending the correct answer to the CAPTCHA to the client. Rather, the hashing calculation needs to be performed on the initial hash value that we send, concatenated with the answer to the CAPTCHA—whatever it is. This forces the spammer to first have the CAPTCHA solved and then either calculate the Proof-of-Work or send it to someone to be calculated. With the average speed of the CAPTCHA-solving services being around 15 seconds this means an inevitable 15-second wait per CAPTCHA, plus the time it takes to perform the Proof-of-Work, which will slow down the spammer somewhat.

Second, there is no earthly reason why we always need to use the exact same hashing algorithm for every CAPTCHA we send. For one thing, the family of SHA hashes includes SHA-1, SHA-2 (SHA-224, SHA-256, SHA-384 and SHA-512), and we could send the client JavaScript code that uses any one of them. Better yet, the SHA family of hash functions uses some arbitrary constants—known in cryptography as “nothing up my sleeve numbers”—to compute the rounds. There is no reason why we need to use these exact numbers, though: we are not calculating industry-standard hashes that need to comply with the SHA standard, we are calculating our very own hashes, so it doesn’t matter if no one else could verify them. In fact, we can pick a different set of numbers for every CAPTCHA; so long as the code that we send to the client knows which numbers to use and we make the server-side code keep track of what was sent we can still verify the Proof-of-Work.

However, this will force the spammer to either collect and use the JavaScript code to perform the hashing or to—somehow—analyze the code that we sent him to pick out these constants. This would give us the additional opportunity of sending the client different versions of the client-side code with small differences but ones which will cause the spammers to either fail the Proof-of-Work calculation or to identify which version we are using.

What this countermeasure really does is make JavaScript the easiest way to compute the Proof-of-Work hash, as all the spammer has to do is collect the client-side code that we are sending and execute it in JavaScript, but spammers are really going to hate this, and for two good reasons: first, JavaScript is an interpreted language and it is pretty slow, and second, spamming tools in general, do not use a full browser per session. Anyone that needs to calculate millions and millions of SHA hashes is going to want to use a fast compiled language—definitely not JavaScript, and requiring a full browser will break many of the spamming tools in the market. Even if someone creates a special plug-in or utility to provide the full browsers this will add a considerable amount of overhead.

Finally, we can add a substantial amount of pain by using chained hashing: instead of a single hash we require the client to compute three consecutive hashes, for example, where each hash depends on the previous value. The difficulty of the hashes should be chosen so that the first hash in the chain is somewhat harder than the rest. In this scenario, the client has to return the “magical numbers” for all three hashes back to the server, and the server has to perform three verifications, but this is just a minor inconvenience when implementing the system.

For the spammer chain, though, this is a disaster, in that the second hash cannot be computed until the value of the first hash is found, because the second hash needs to start with the output of the first hash, and so on for every consecutive hash. Implementing any type of cooperative hash solving in this scenario will require that a series of packets be exchanged between the members of the chain, which will place further load on the systems.

The key point is that in any scenario somebody has to do the computations, whether this be the spammer, the solving company, the worker or a botnet there is now a cost in the form of the number of computations that have to be carried out that must be paid somewhere along the chain. So long as the computational cost can be set so that it exceeds the economic benefit of any of the players in the chain the chain will be broken, and the practice will either be stopped or severely curtailed.

The accessibility of CAPTCHAs

CAPTCHAs have been criticized for being difficult if not right down impossible to solve for users with disabilities (Yan & Ahmad, 2008). The blind cannot see the CAPTCHA images, and many users with visual impairments find it very difficult to solve CAPTCHAs because of all the noise and distortions.

Some CAPTCHA systems offer an alternative to the visual CAPTCHA in the form of an audio clip with the letters or digits that the user needs to listen to and then enter to solve the CAPTCHA. Unfortunately, the audio clip also needs to be distorted with some kind of noise, or otherwise the spammers would simply use some form of speech recognition software to defeat the CAPTCHA.

These audio clips have been criticized for being too hard to interpret. Yan & Ahmad (2008), for example, mention a demonstration of an audio CAPTCHA system used by the Microsoft Hotmail service that was found to be completely unintelligible by four journalists, all with normal hearing.

Ironically, some of the spammer comments in the spammer forums about audio CAPTCHAs seem to indicate that it is easier for automated CAPTCHA solving software to crack the CAPTCHA using the audio clips provided for the visually impaired users than by interpreting the CAPTCHA images.

In any event, users that are both blind and deaf will not be able to use the CAPTCHA at all. Some websites offer an alternative way of creating an account, such as placing a call to their customer service department to create the account for them. However, not every site offers this feature, so the deaf-blind are effectively shut out of many places on the Internet. Additionally, companies that do offer this service need to spend the time and money required to deal with these requests, so in the very best case not only will the disabled users be severely inconvenienced, but there will also be a cost for the company.

Using the Proof-Of-Work Concept to make CAPTCHAs Accessible

The solution described above is all well and good, and a very worthy and humane thing to do, but there seems to be a much simpler way to make the CAPTCHAs accessible to everyone: to the blind, to the deaf, to the blind-and-deaf and even to blind-deaf-mute paraplegics that use their mouths to control the mouse, and without requiring them to call customer service, pay any fees or even to use the type of service described above. In the Proof-of-Work CAPTCHA there is a 1-click solution to allow access by disabled users—actually by anyone, disabled or not—with no further effort on their part.

If we think about the economics of the Proof-of-Work concept for a moment, a website that accepts a CAPTCHA solution together with a valid Proof-of-Work value is also happily accepting the risk that the CAPTCHA has been solved by someone other than a legitimate user. The value of the CAPTCHA-plus-Work concept lies not in stopping every single spammer—that is not feasible—but in raising the cost of the average intrusion well above the economic value that the spammer receives.

The objective here is not really to identify humans—it is to keep the spammers away. It makes no difference whether that happens because the spammer’s software cannot solve the CAPTCHA or because the spammer stays away because the price of solving the CAPTCHA turns out to be too high to be done economically, the end result is exactly the same. If this is case then, why not simply set the computational and time cost for the disabled users much, much higher than the cost of the “regular” CAPTCHAs? For example, if we were to set the difficulty of the hashing problem to 30 seconds for a regular user, a disabled user could be asked to compute for 5 or 6 minutes, or perhaps even 10 minutes or some higher number—but without the CAPTCHA.

This delay would be a small inconvenience for the disabled users, as they would have to wait a few minutes to open an account, but it would certainly be preferable to having to place a call to the customer department, and it is something that can be easily implemented with a “Disabled Users Click Here” button; the user would then be told both in writing and in audio to please wait the required number of minutes while the calculations are being performed, perhaps with an explanation as to what is being done and some type of “pacifier” like music, but no CAPTCHA at all. Once the calculations are finished the user would then be allowed to create the account and proceed normally.

The reason why spammers would not be able to abuse this type of service is that a 5 or 10 minute wait—with the corresponding processor load in the form of millions and millions of hash calculations—would be considerably more expensive than solving the regular CAPTCHA plus Proof-of-Work using either a human solver or some automated system. This type of CAPTCHA-bypass method would have the advantages of not causing any calls to customer service or any additional costs to the website and of allowing disabled users full and easy access to the site—all that is required from them is to click a button and wait—while imposing only a reasonably small penalty on the disabled.

References

Elson, J., Douceur, J., Howell, J. & Saul, J.J. (2007). Asirra: A CAPTCHA that exploits interest-aligned manual image categorization. In Conference on Computer and Communications Security (CCS), 2007.
Golle, P. (2008). Machine Learning Attacks Against the ASIRRA CAPTCHA. In Proc. CCS 2008, ACM Press (2008), 535–542.

Kanich, C., Kreibich, C., Levchenko, K., Enright, B., Voelker, G.M., Paxson, V. & Savage, S. (2008). Spamalytics: an empirical analysis of spam marketing conversion. In CCS ’08, pages 3–14, New York, NY, USA, 2008. ACM.

Motoyama, M., Levchenko, K., Kanich, C., McCoy, D., Voelker, G.M. & Savage, S. (2010). Re: CAPTCHAs-Understanding CAPTCHA-Solving Services in an Economic Context. In Proceedings of the USENIX Security Symposium, Washington, D.C., August 2010.

Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system. Bitcoin.
Okamoto, T. (1995). An efficient divisible electronic cash scheme. Proc. Crypto, 1995.

von Ahn, L., Blum, M., Hopper, N. J. & Langford, J. (2003). Captcha: Using hard AI problems for security. In Advances in Cryptology - EUROCRYPT, 2003.

Yan, J. & El Ahmad, A.S. (2008). Usability of CAPTCHAs or usability issues in CAPTCHA design. SOUPS 2008: 44-52.