The GOTCHA is a sort of CAPTCHA designed to stop dictionary attacks on password hashes. It's new and it might have more uses in security than just being better password protection. 

Researchers from Carnegie Mellon think that they have a possible solution to the growing problem of password hacking - but first let's look at the exact problem the GOTCHA is designed to solve. 

Passwords aren't generally stored on a computer system. Instead the password p is hashed using a cryptographic hash function h(p). This give a number that is stored somewhere in the system. When the user logs on they provide the password p' which the system then uses to work out the hash h(p'). If this is equal to the stored hash value then the correct password has been submitted - if not then the user needs to try again. 

The big problem with this approach is that the file storing the hash values is often easy to steal. With the hash file a bad guy can get your password back by computing the inverse of the hash function on your hash value. However, this isn't easy because it is in the nature of hash functions that finding their inverse is very hard. In practice, what usually happens is that the password is found by trying different test passwords from a dictionary in the hash function until a match is achieved. This is the traditional dictionary attack on the hash code file - and while it can be made more sophisticated this the basic idea. Once the bad guy has your password they can log in to the site and any other site you use the same password for.

One way to make a password more secure it to use a salt - a random value. When you set your password for the first time the operating system generated a random number, the salt, s and adds it to your password. The system then computes h(p,s) and stores the salt along with the hash. When you present your password p' the system looks up the salt value, s, adds it to p' and works out h(p',s) and if it is the same hash value as stored the user is in. 

A salt makes it harder for a dictionary attack because the bad guy has to compute each guess with each salt. If the salt wasn't present then you could try h("password") and look though the file to see if anyone was stupid enough to use password as a password. With a salt you have to compute h("password",s) for each salt in the file - a lot more work. 

Now we have GOTCHA, which sort of adds a user-generated salt to the password that makes it much, much more difficult for the attacker because the system doesn't store the extra salt - the user generates it each time. Jeremiah Blocki, Manuel Blum and Anupam Datta expect us to believe that the acronym Generating panOptic Turing tests to tell Computers and Humans Apart, i.e. GOTCHA, just happened but it is a clever idea. 

What you have to do extra is to have a set of problems that can be generated based on the password and easily solved by a human but not so easily by a computer. This is the difficult part, but they suggest inkblot patterns. The computer generates ten inkblot patterns based on the password - the same user password combination always generates the same pattern. Then the user is asked to make up phrases for each inkblot pattern - for the one below it might be "Evil clown". 

The computer then generates a permutation of the inkblots, e.g. P=321456709 means inkblot 3, then 2, then 1 then 4 and so on.  Next the machine computes a hash with a salt and the permutation as an extra salt. That is, it computes h(p,s,P) and stores the hash, the salt and the phrases the user assigned in the permuted order. Notice it doesn't store the permuted order P. 

So far so good - but how does the user log on?

When the user logs with the correct password they are shown the ten inkblots in the standard order and the phrases they applied to them in the permuted order. All the user has to do is match the phrases to the inkblots and the machine can use this to work out the permutation P. Using this and the salt. the machine can then compute h(p',s,P) and if this gives the stored hash value the user is allowed in.

Now consider what happens if the user gives the wrong password p'' - in this case they don't even get to see the correct inkblots and so have no chance of guessing the permutation. Even if they did the hash would fail because the password is wrong.

What if the user isn't quite sure of which phrase goes with which inkblot? 

To make the task slightly easier and more robust, the algorithm can be set to try the permutation that the user supplied and a number of permutations that are close  - the more close permutations that are tried the easier, but less secure, the log in.

Now suppose the bad guy gets the hash file - how easy is it to guess the correct password? The only data available is the hash value, the salt and the permuted list of phrases. Now when a dictionary attack is tried the attacker has to try to assign the phrases to the generated inkblots - not an easy task even if the password is correct.

The only alternative way is to try h(p',s,P) for all possible passwords and all possible permutations... and with the permutation being a ten-digit number this is a lot of possibilities to test.

So convinced are the inventors, that their idea is a good one, they have thrown down a challenge to the AI community.

They provide a file with a set of hashes, salts and permuted phrases. They even provide the algorithm that generates the inkblots and all you have to do is crack the hash and recover the password. 

It sounds difficult to me and I guess that's entirely the point.

So the next time you log on you might just have to reveal the innermost dark secrets of your soul as you conduct a Rorschach test to see an evil clown or something much worse - is there anything worse - in the inkblots on the screen.