How secure is Asirra?

For a HIP/CAPTCHA, "secure" generally means that the most efficient way to get one ticket (i.e., credit to get one unit of service from the protected site) is for a human to solve one HIP challenge. A HIP is considered insecure if there is a way for an automated script to collect a large number of tickets without the commensurate human effort. Note that this definition also disqualifies attacks against a HIP that require computational effort as expensive as a paying a human to solve the HIP manually.

On this page, we will discuss various ways to attack Asirra, and analyze its security.

Attacks on "Adopt Me"

The most frequent question we get, by far, is: isn't the "adopt me" link a security hole, since the pet's information page at Petfinder.com describes it as being a cat or a dog? The answer: no. If you look carefully, you'll notice that the adopt-me links do not point directly at Petfinder.com. They point at the Asirra web service, which only provides a redirection to Petfinder.com after the challenge has been invalidated. If a script tries to solve a challenge after following an adopt-me link, it will be marked as a bot. In addition, we only allow users (and scripts) to follow one adopt-me link out of the 12 shown in the challenge.

We can also limit the number of redirections provided per IP address per day, to prevent adopt-me from becoming a vector for revealing large portions of the database.

Brute force attacks

Perhaps the most effective attack on Asirra is simple brute force: give a random solution to challenges until they succeed. If an attacker has no basis at all for a decision (i.e., 50% probability of success for every image), there is a 1/4096 chance of success for a 12-image HIP. This is a large enough slowdown that it becomes easy to detect and evade such an attack — if we see more than 500 failed HIPs from a single IP address in a single day, we put that IP into a "penalty box," scoring all HIPs as wrong until several hours elapse. This is a failure condition highly unlikely to be experienced by any normal use case, but limits a brute force to producing about one service ticket per 10 IP addresses controlled by the attacker per day. Further heuristics can be put in place if a large-scale botnet controlling thousands of distinct IPs executes a coordinated brute-force random guessing attack.

Image recognition attacks

While random guessing is the easiest form of attack, various forms of image recognition can allow an attacker to make guesses that are better than random. There is enormous diversity in our photo database (a wide variety of backgrounds, angles, poses, lighting, etc.), making accurate automatic classification difficult. In an informal poll, computer vision experts around MSR posited that a classifier with better than 60% accuracy would be difficult without a major advance in the state of the art.

A 60% classifier improves the guessing probability of a 12-image HIP from 1/4096 to 1/459. This would improve an attacker's yield to about one service ticket per IP address per day.

Attacks on the image database: manual database reconstruction

One way to attack an image-based HIP is to reconstruct its image database. For example, KittenAuth suffered from a database attack because its first implementation used only 42 images. A first, trivial attack computed a map of images' MD5 hashes to their classifictions. It is almost as easy to use a robust image comparitor function instead (e.g., based on color histograms), making the attack effective even if random noise is added to the photos before their presentation.

Asirra, in contrast, uses more than three million images. This makes it impractical to manually reconstruct our database. Months of human effort would be required, even classifying one image per second, 8 hours per day, 7 days per week. Plus, the image database continues to grow at the rate of approximately 10,000 images per day, meaning the entire database is expected to turn over approximately every 6 months. The effort expended reconstructing the database would likely be more efficiently spent solving HIPs directly.

Attacks on the image database: scraping Petfinder.com

Another possible attack vector is to automatically reconstruct the database by writing a script that repeatedly queries Petfinder.com. However, Petfinder's public interface only displays pets currently up for adoption, which represents less than 10% of the total database, making this attack ineffective. In addition, there is no efficient way to track database changes using Petfinder's public interface. The private API provided to MSR by Petfinder is not available to the public.

Attacks on the implementation

Many HIPs suffer from implementation weaknesses. For example, some allow a session ID authorized by a single successful HIP to be used to gain repeated access to a protected service.

To avoid such weaknesses, we've taken two approaches. First, we've made the Asirra server as conceptually simple as possible, so that we can verify its correctness via code review. (The web service is a total of about 500 lines of Python code.) Second, we designed the Asirra ticket redemption model to minimize the implementation burden on the webmaster. For example, we do not require sites that use Asirra to keep track of user sessions or any other form of state. Our example service is, in fact, completely stateless.