Latest News

April 22, 2017
Alan Kaminsky published a paper in the Cryptology ePrint Archive.

Additional Information

Parallel Computing:

Cryptography:

 

Organizations

 

RIT Links

 

Password Cracking Challenge

The Idea — Generating Passwords with the XKCD Method — Hashing the Passwords — The Password Digests — The Challenge — The Reward — History

The Idea

Randall Munroe, author of the xkcd webcomic, came up with a method for choosing hard-to-crack passwords, popularly known as the XKCD Method. Munroe famously generated the password “correct horse battery staple” using this method. I’ve heard many people—including eminent security pundit Bruce Schneier, as well as some of my students—claim that password crackers “are on to this trick” and would have no trouble cracking such passwords. Others, including myself, assert that such passwords are indeed hard to crack.

To settle the question, I have inaugurated this Password Cracking Challenge. I challenge you to crack several passwords generated by the XKCD Method, as described below.

My goals for the Password Cracking Challenge are to determine how strong XKCD Method passwords really are; to assess the state of the art of password cracking; and to stimulate research into new password cracking methods.

Generating Passwords with the XKCD Method

Here is how I generated each password in the Challenge.

  1. Start with a list of 65536 English words. Here is the word list I used:
    words.txt
  2. Decide how many words long you want the password to be. Suppose I want N = 4 words in the password.
  3. Go to random.org and have them generate N random integers, each in the range 0 through 65535. Suppose the integers are 12675, 45700, 59341, and 37008.
  4. Take the words at indexes 12675, 45700, 59341, and 37008 in the word list, in that order, as the password. (Words in the list are indexed starting at 0.) Result:
    kowtowing pensiones needily vignettes

It's crucial to use a true random number source (like random.org) to pick the words—a point seemingly missed by some of the XKCD Method's critics. Also, it’s possible for the same word to appear more than once in the password.

Hashing the Passwords

A web site would (or should) never store its users’ passwords in the clear. Rather, the web site stores the digests of the passwords, computed by a cryptographic hash function. Here is how I computed the digest of each password in the Challenge.

  1. Concatenate the words of the password together. No spaces between the words.
  2. Convert the resulting string to a sequence of bytes using UTF-8 encoding.
  3. Compute the SHA-512 digest of the resulting byte sequence.

Here is a Java program to compute the password digest:
HashPassword.java

The SHA-512 digest of the password “kowtowing pensiones needily vignettes”, in hexadecimal, is

04CB93886540D27F7168F84970D3D3E1DAC5270DB96D32735110F387DFC304B5 62351BB83AB60155C0612EB4000FB40047C468129838FFE50EF0749A41A0B637

The Password Digests

Here are the SHA-512 digests, in hexadecimal, of passwords with various numbers of words generated as described above.

4 words:

BA85E7AF9CA665527C29C649D3A2EDE0528E721375840095C12020CF99E3536D 3775335E2033A375EED1FA1BD3E77A0FFD95125566DD15E53CF4834839F14A80

5 words:

552E0722749CA32E0EFEA4938B112C64AECD7DDEF2E55DD011757A010EFE7676 77AC4E8DE3B0DCD8EF0D1BA27B11050AC79F8B8EAA5A39708B3562079427ACAA

6 words:

5D677A90E2C203E9A16C6D9F16E22D8333B1E127413DE5F0466D240A4E076D47 C02C3456330A07266033E2C3642A177DE56126EE6EE00B3B02F4A06C4FBC2DF5

7 words:

282B179EE523C9D4296DBF94D69E1E04EB61B2C7995C32CD5D78751BAD724D14 C9CDFB9D0C2EBA1387CDFF7A8E1009C6BDE4E0486237BB396C337628FF009011

8 words:

A41CFD9A907CC677740959E862CC0DABA4958E44BCBC961ECACCECCB8471BF46 2F62FF260391419BAF5B366099F936A173028DB3F15F9E2F72DFFD1D9A0CFF38

After computing the digests, I discarded the passwords and the random numbers used to generate them. I myself no longer have any idea what the passwords are.

The Challenge

Your challenge is to crack the above password digests—that is, find the original passwords. This is what a hacker who stole a web site’s password digest database would have to do.

You may use any technique, any hardware, and any software you wish. You can verify that you have found the correct password by computing its SHA-512 digest and checking that it matches the digest listed above.

The Reward

I will list, on this web page, the name of the first person or group to succeed in cracking each of the password digests. I will also make a donation to Habitat for Humanity for each cracked password. The donation amounts for each password are:
4 words — $64.00
5 words — $80.00
6 words — $96.00
7 words — $112.00
8 words — $128.00

To claim the reward, you must:

  1. Write a paper, following accepted academic research paper standards, listing the correct password and describing how you found the password. The paper must describe, in detail, the hardware you used, the software you used, and the amount of time it took to crack the password. The paper must include a link to the publicly available, free software licensed, source code for the software you used.
  2. Publish the paper in a research conference, a research journal, or the Cryptology ePrint Archive.
  3. Send me a citation or link to the published paper. (See my contact information.)

I will withhold the reward if in my judgment the paper does not adequately describe how you found the password or if the source code is not publicly available and free software licensed.

Your personal reward will be the eternal glory of being the first to crack one of the passwords; a publication to add to your resume; and the satisfaction of knowing a worthy cause has benefited as a result of your efforts.

History

July 5, 2014 — Password Cracking Challenge inaugurated.