GOTCHA Challenge

We envision a rich interaction between the security community and the artificial intelligence community. To facilitate this interaction we present an open challenge to break our Inkblot-matching GOTCHA construction.

To set up the challenge we selected five random passwords Pw1,Pw2,Pw3,Pw4 and Pw5. Pw1,Pw2,Pw3 and Pw4 were chosen uniformly at random from the integer range [0,10⁷], and Pw5 was chosen uniformly at random from the integer range [0,10⁸]. We created accounts using each password. To simulate an offline dictionary attack --- resulting from a server breach --- we are releasing the password files associated with each account.

The password file for each account was generated by the function storePassword(int pwd, string [] labels). These password files are stored in the file PasswordFile.resx in the C# [Source Code]. We give the password file from account 1 as an example. The first line is a BCRYPT hash value, which is one of the required parameters for the function verifyPassword(int pwd, int[] permutation, string pwdHashBCrypt). The following lines are the labels we created for ten inkblot images I₁,…,I₁₀ --- stored in permuted order. The Inkblot images I₁,…,I₁₀ were generated by running generatePuzzles(Pw1). To verify that our password Pw1 is correct we would first run generatePuzzles(Pw1) to recover the Inkblot images I₁,…,I₁₀, and then we would match the labels below to recover the permutation --- the final required parameter for verifyPassword. For example, if we matched image I₁ with the eighth label “large steroid insect with big eyes” then we would set permutation[7] = 0.

Password File 1

$2a$15$kQllswv6yMGdRHbnPY6qzeH5m5uqTluGOKoUzj0tz6jlU.b8YN9DG

body builder lady with mustache and goofy in the center

stern old guy staring at me

grasshopper with big legs and wide-narrow head

cone headed king

large lady with fat face, mustache and bugs on stomach

big viking guy with freckles

really long face that looks like a nose

large steroid insect with big eyes

red eyed cow running towards me

warrior with pink necklace

Challenge: Break each password offline.

Approaches: One way to accomplish this goal would be to enumerate over every possible password guess pw’ and compare hash values for every possible permutation 𝛑:[10]-->[10]. However, the goal of this challenge is to see if Artificial Intelligence techniques can be applied to attack our GOTCHA construction. We intentionally selected our passwords from a smaller space to make the challenge more tractable for AI based attacks, but to discourage participants from trying to brute force over all password/permutation pairs we used the BCRYPT hash function with Level 15 --- a very expensive hash function --- to encrypt the passwords. Our implementation allows the Inkblot images to be generated very quickly from a password guess pw' so an AI program that can use the labels in the password file to distinguish between the correct Inkblots returned by generatePuzzles(Pw1) and incorrect Inkblots returned by generatePuzzles(pw’) would be able to quickly dismiss incorrect guesses. Similarly, an AI program which generates a small set of likely permutations for each password guess could allow an attacker to quickly dismiss incorrect guesses.

Challenge Results

Update: There was a bug in the original challenge which allowed attackers to find the passwords directly without solving any GOTCHA challenge. The culprit? I forgot to remove actual inkblot images from the debug folder. This allowed an attacker to directly verify a password guess by generating the corresponding Inkblot images and comparing them with the actual inkblot images that the user labeled. While this attack is easy to prevent (e.g., don’t save the original inkblot images), it does serve as a valuable reminder about the importance of operational security.

Credit: Thanks to Peter Kosinar and Ruxandra Olimid for pointing out this attack.

Fix: We have generated several new password challenges (I am not including the original Inkblot images this time!). Pw6,Pw7,Pw8 and Pw9 were chosen uniformly at random from the integer range [0,10⁷], and Pw10 was chosen uniformly at random from the integer range [0,10⁸].

(Challenges 6,7 and 10 have been released. Challenges 8 and 9 will be released soon!)

	Password	Winner	Institution	Date Solved
Example	123456	Harry Q. Bovik	Carnegie Mellon University	7/17/2013
Challenge 1	1258136	Peter Kosinar		11/10/2013
Challenge 2	9945047	Peter Kosinar		11/10/2013
Challenge 3	6868913	Peter Kosinar		11/10/2013
Challenge 4	6523034	Peter Kosinar		11/10/2013
Challenge 5	29157600	Ruxandra Olimid	Department of Computer Science, University of Bucharest, Romania	11/11/2013
Challenge 6	Unsolved	N/A	N/A	N/A
Challenge 7	Unsolved	N/A	N/A	N/A
Challenge 8	Unsolved	N/A	N/A	N/A
Challenge 9	Unsolved	N/A	N/A	N/A
Challenge 10	Unsolved	N/A	N/A	N/A

Source Code

The source code for the challenge was written in the C# programming language [Source Code].

In particular there are three methods to take note of: generatePuzzles, verifyPassword and storePassword. The source code for these functions is found in the file GOTCHA_Challenge.cs.

/// <summary>

/// Generates n Inkblot puzzles of using the password pwd

/// as a source of randomness.

/// <param name="pwd">The password provides the source of

/// randomness.</param>

/// <param name="width">Width of the Inkblot Puzzle

/// (use width = 500)</param>

/// <param name="height">Height of the Inkblot Puzzle

/// (use height = 500)</param>

/// <param name="n">Number of Inkblot Puzzles to Generate

/// (use n = 10)</param>

/// <returns>An array of Inkblot images</returns>

/// </summary>

public static Bitmap[] generatePuzzles(int pwd, int width=500, int height=500, int n=10)

/// <summary>

/// Verifies whether or not the password pwd is correct.

/// <param name="pwd">The password to verify</param>

/// <param name="permutation">The solution to the Inkblot

/// matching challenge</param>

/// <param name="pwdHashBCrypt">The BCRYPT hash value of the original

/// password and permutation</param>

/// <returns>True if pwd is correct, otherwise false.</returns>

/// </summary>

public static Boolean verifyPassword(int pwd, int[] permutation, string pwdHashBCrypt)

/// <summary>

/// Hashes the password pwd. Before the password is hashed a random permutation

/// is generated and appended to the password. The hash value is stored in the

/// returned value along with the labels (in permuted order).

/// <param name="pwd">The password</param>

/// <param name="labels"> The human's labels for the Inkblot images returned

/// by generatePuzzles(500,500,10,pwd)</param>

/// <returns>

/// A string s, whose first line contains the BCRYPT hash of pwd with the

/// permutation appended. The labels are stored on the following lines

/// in permuted order.

/// </returns>

/// </summary>

public static string storePassword(int pwd, string [] labels)

Example

The project file also contains the two forms: Create_Account and Authenticate. The password files in PasswordFile.resx were generated using the form Create_Account, and the form Authenticate is used to validate a password guess.

To provide a concrete example we used the Create Account form to create an example account with the password Pw0 = 123456. After entering the password 123456 we clicked on Generate Puzzles to generate ten inkblot images I₁,…,I₁₀ using the function generatePuzzles(123456), and we created labels for each Inkblot image. In non-permuted order the labels for the ten Inkblot images are:

1. lady with pink bowtie and purple mustache (Inkblot1.jpg)

2. ugly narrow eyed person puckering up for a kiss (Inkblot2.jpg)

3. bees on top fling towards each other, big U in the middle (Inkblot3.jpg)

4. robot on a skateboard like thing (Inkblot4.jpg)

5. square faced guy with big nose and short yellow hair fuzz (Inkblot5.jpg)

6. hulk guy with tiny boxing gloves through the waist (Inkblot6.jpg)

7. The letter H (Inkblot7.jpg)

8. lipstick on a lady who takes steroids (Inkblot8.jpg)

9. linebacker with mustache and yellow nose (Inkblot9.jpg)

10.little birdies facing eachother on the bottom and little bees flying away from eachother on top (Inkblot10.jpg)

We then clicked on the Generate Password File button to generate the following password file --- by running storePassword(123456, new string []{“lady with pink bowtie and purple mustache”,…,”little birdies facing eachother on the bottom and little bees flying away from eachother on top”}).

Example Password File

$2a$15$mxBNEQ16k5bUgIvRr/JXOuGMzY9ymiJU.S4TX196mXOCLt4mY1Wbm

lipstick on a lady who takes steroids

linebacker with mustache and yellow nose

hulk guy with tiny boxing gloves through the waist

bees on top fling towards each other, big U in the middle

little birdies facing eachother on the bottom and little bees flying away from eachother on top

robot on a skateboard like thing

lady with pink bowtie and purple mustache

The letter H

square faced guy with big nose and short yellow hair fuzz

ugly narrow eyed person puckering up for a kiss

To authenticate the user would use the form Authenticate. We first select the account “Example (pw is 123456)”, enter the password 123456, and click Generate Puzzles. Finally, the user would match the labels with the appropriate Inkblots and click Check Password. The computer uses the matching to recover the permutation (int [] permutation = {7,8,5,2,9,3,0,6,4,1}), and verify that the password and matching are correct --- by running verifyPassword(123456, new int[]{7,8,5,2,9,3,0,6,4,1}, “$2a$15$mxBNEQ16k5bUgIvRr/JXOuGMzY9ymiJU.S4TX196mXOCLt4mY1Wbm”).