TL;DR
GOTCHAs (Generating panOptic Turing Tests to Tell Computers and Humans Apart) are a new class of interactive puzzles designed to neutralize offline dictionary attacks. By requiring users to match self-generated labels to computer-generated inkblots, the system ensures that even if a server is breached, an attacker cannot crack passwords without the prohibitively expensive help of a human-in-the-loop.
What Problem Does This Paper Address?
When a server is breached, attackers typically walk away with a database of password hashes. They then use powerful hardware (like GPUs) to run "offline dictionary attacks," testing millions of potential passwords per second against those hashes.
Standard defenses like salting or slow-hashing (BCRYPT) help, but they don't stop the automated nature of the attack. Traditional CAPTCHAs also fail in this scenario: if an attacker has breached the server, they likely have the random seeds used to generate the CAPTCHA, allowing them to solve it programmatically. The authors seek a "Human-Only Solvable Puzzle" (HOSP) that remains difficult for computers even when the generation algorithm and its random inputs are public knowledge.
Methods
The authors introduce the GOTCHA protocol. Unlike previous attempts at human-only puzzles, a GOTCHA involves human interaction during both the generation and authentication phases.
The Inkblot Construction
The paper proposes a specific implementation using randomly generated inkblots:
- Account Creation: The system uses a random seed (derived from the user's password) to generate $k$ unique inkblot images. The user is asked to provide a creative descriptive label for each image.
- Storage: The server stores the password hash and the user's labels in a shuffled order.
- Authentication: When the user logs in, the server regenerates the same $k$ inkblots. The user is presented with their own labels and must match each label to the correct image.
The security relies on the "Panoptic" property: even if the attacker knows the exact random bits used to draw the inkblot (Figure 1), they cannot easily predict what a human would name it or match a specific human's label back to the image without human-level artificial intelligence.
Datasets
The authors evaluated their construction through a two-phase user study:
- Participants: 70 users recruited via Amazon Mechanical Turk.
- Phase 1 (Creation): Users labeled 10 random inkblots.
- Phase 2 (Authentication): After a 10-day delay, 58 of those users returned to perform the matching task.
Additionally, the authors released an Open Challenge to the AI and security communities, providing five password-protected tuples and encouraging researchers to attempt to crack them using AI techniques.
Key Insights and Ideas
- Recognition vs. Recall: Previous "Inkblot" password systems failed because they required users to recall their exact phrase (e.g., typing "evil clown" exactly). GOTCHAs use recognition (matching the phrase to the image), which is a much easier cognitive task for humans.
- Economic Deterrence: The goal isn't necessarily to make a puzzle "unsolvable" for AI forever, but to make it so that the cost of a single password guess requires either a human's time or a massive AI computation. This makes bulk dictionary attacks economically unfeasible.
- Interaction as a Shield: By making the puzzle generation dependent on the user's initial input, the "correct" solution is unique to that user's imagination, creating a secret that exists only in the user's mind and is triggered by the image.
Key Results
- Usability: In the user study, 29% of participants correctly matched all 10 labels after 10 days. When the system allowed for a small margin of error (matching at least 5 out of 10), the success rate jumped to 69%.
- Speed: On average, it took users about 6.2 minutes to label 10 images initially and 4.5 minutes to perform the matching task during login.
- Security Trade-offs: The authors proved (Theorem 1) that a "conservative" adversary's success rate is strictly limited by the number of human queries they can afford. They suggest that servers can tune the "accuracy parameter" ($\alpha$) to balance user frustration against the computational work required by an attacker to brute-force the remaining permutations.
Limitations and Future Work
- Usability Barriers: A 29% perfect-match rate is low for a primary authentication method. The authors suggest GOTCHAs might be better suited as a voluntary "high-security" tier or for protecting extremely sensitive accounts (like online banking).
- Label Quality: The study found that simple labels (e.g., "mask") were often mismatched, while elaborate "stories" (e.g., "A happy guy on the ground, protecting himself from ticklers") were almost never forgotten. Future work could involve guiding users to create more distinct labels.
- Alternative Puzzles: The authors suggest exploring other human-centric tasks, such as ranking or rating movies and foods, which might be faster and more intuitive than labeling inkblots.
Summary updated