Researchers use inkblots to make safer passwords

Have you ever looked up at the sky and thought that a passing cloud looked like a spaceship or a cat, or maybe even a knight riding a horse off into battle? Often, inkblots have the same effect. Carnegie Mellon computer science graduate student Jeremiah Blocki and his advisors Manuel Blum, the Bruce Nelson professor of computer science, and Anupam Datta, associate professor in the computer science and electrical and computer engineering departments, have developed a new password security system that uses inkblots as a second line of defense to prevent hackers from discovering lists of passwords.

This password system is creatively named GOTCHA, which stands for Generating panOptic Turing Tests to Tell Computers and Humans Apart. “The key word to focus on here is ‘panoptic,’ ” Blocki said. “Panopticon refers to this specific architectural structure. You could think of a prison, for example, where the guards want to be able to monitor all of the prisoners without walking around. The basic architectural layout is this curved prison with the guard in the center, where he can look into any of the prison cells at any time. Basically, ‘panoptic’ refers to a world without privacy.”

The basics of password security is that when an individual creates a username and a password, the server will store that username along with a cryptographic hash of the password. When the user signs on at a later time and types in his or her password, the server will check if the hash of the given password matches the saved hash.

The problem is that this system proves unsafe in a situation where a hacker has already breached the server and can see the saved hashes of the passwords. “The thing about the hash function is that if an adversary guesses your password, then it’s very easy to compute the hash and match against what’s on the file. So it is very easy to verify guesses,” Datta said. Unfortunately, many people pick very simple passwords, such as “12345,” which has led to entire lists of passwords at companies such as Sony, Gawker, LinkedIn, Zappos, and Adobe to be compromised.

GOTCHA works differently. When a user creates an account, after they give their username and password to the server, it will give the user 10 randomly generated inkblots. The user must then assign labels to each of these inkblots, describing the pictures that they make with phrases such as “evil clown” or “a smiling Ms. Frizzle.”

“What the server now stores,” Blocki explained, “is not just the hash of the password, but the hash of the password with a permutation appended to it.” Each time the user wants to sign in now, he must enter the username and password and then successfully match the inkblots to their descriptions.

“So let’s say that the user has 10 inkblots. Then there are 10 factorial ways to match these labels to the inkblots. Now, an adversary that wants to use a brute force attack must simultaneously guess the password and the permutation. So essentially what we’re doing here is we’re expanding the amount of effort that an adversary needs to use to attack a password by a factor of about 3.5 million,” Blocki said.

Another key point that makes GOTCHA so effective is that in order to match inkblots to their correct labels, an adversary would have to have a human’s help, which is more expensive than having a computer continuously try guesses.

To test if users could reliably remember their inkblot descriptions, 70 people were hired through Mechanical Turk, a crowdsourcing Internet marketplace that uses human intelligence to complete tasks, and were asked to describe 10 inkblots with interesting labels. Ten days later, they were asked to match these labels with the inkblots. The study showed that of the 58 individuals who participated in the second part, one-third matched all of their inkblots correctly and more than two-thirds got half right.

Blocki stated that a similar study would probably be conducted again with adjusted financial incentives to garner more accurate data. The study also suggested that instead of requiring that all 10 labels be matched successfully, an approximate matching should also be accepted.

Another change to the GOTCHA system that may be implemented would allow the user to ask for a new inkblot picture when creating a password. This way, the inkblots that don’t resonate with users can be discarded so that they can use more memorable inkblots.

The developers of GOTCHA invite members of the Carnegie Mellon community to attempt to breach their new password system in the GOTCHA Challenge, which can be found online. Any artificial intelligence technique that can break their system would have to be truly remarkable, because as simple as describing random inkblots may seem, it has opened the doors to a new era of password security.