High performance cracking beast built by Sagitta HPC, photo Jeremi Gosney
Nowadays, when you crack passwords from leaked databases (so called offline attacks) you don't use precomputed lookup tables, also known as rainbow tables. Generating these tables is time-consuming, and they contain a lot of records that don't correspond to how users are creating their passwords. With general-purpose computing on graphics processing units (GPGPU) now widely available, you rather use that for cracking passwords. Tools like hashcat or John the Ripper create so called candidate passwords on GPUs and compare them with available hashes. When the tool finds a match, it is marked as the original password. The chance that it would be a different password with the same hash, a hash collision, equals almost zero. Passwords are too short strings and use limited character sets. One GPU allows to generate billions of MD5 hashes per second. Users employ predictable methods when creating passwords, so we can generate only candidates that match those methods.
The most powerful graphics card you can buy today for password cracking is the NVIDIA GeForce GTX 1080 Ti. It can generate 31 billion MD5 hashes per second (GTX 1080 is about a fifth slower). When you're serious about password cracking, you want to use the Founders Edition, a reference card designed by the chip vendor. Reference design cards can operate 24/7 under full load, while “gaming”/OEM editions simply can't. You play games rather occasionally, a few hours a day, so these “gaming” cards can use cheaper and lower-quality components (the chip itself is the same, of course), which unfortunately is not projected much into the final price.
You can't get new GTX 1080 Ti Founders Edition anymore, so what about the cloud? Amazon AWS offers Elastic GPUs (which most probably can't be used for password cracking) and p2, p3, and g3 instances with the following cards (listed are the max models you can get, prices can vary, consult respective vendors for up-to-date prices):
Just to compare, Microsoft Azure offers the following machines with NVIDIA Tesla GPUs:
OVH offers only the following dedicated server:
Tesla GPUs are not powerful enough for some serious password cracking (except the new V100), when you compare them with GTX cards in MD5 benchmark:
The Mall.cz file hosted on Ulož.to contained 381 908 unique passwords. I've hashed them again with MD5 and tried re-cracking them back. Just wanted to see if it would be possible and how far I'd get. If passwords could be cracked rather fast, then it could have been hashes what leaked, not plain text, and somebody has cracked the passwords. So I've rented Tesla K80-based p2.16xlarge (Tesla V100-based P3 instances are available since October 2017, the events in this “story” happened in September), downloaded probably the two most famous word lists
phpbb.txt, and started cracking, essentially skipping the preparation phase. A pro-level password cracker would certainly not underestimate the preparation phase, wouldn't crack passwords on Amazon, but I didn't want to do it as a pro, for a reason. I've even used only standard hashcat-bundled rules for generating additional candidates and a I've built lists of Czech words, first and last names only after I've started cracking. I didn't even bother to build a list of Czech street names. A pro would prepare all of this in advance and would crack more passwords within the same time frame.
In addition to using those two already mentioned world lists, I've tried cracking passwords using the following techniques:
All these attacks can be customized and extended using rules. These can for example substitute characters with digits (
0 etc. so both
p4ssw0rd will be tested), change some letters to their upper-case variants, mix numbers or special characters in, duplicate words and so on, eventually producing bazillion of candidates.
I've cracked 165k passwords, cca. 43%, in 45 minutes. In 12 hours, I've cracked almost all of them, I was left with 935 passwords not cracked only because I wanted to go to sleep. I'm pretty confident that I'd get all of them if I'd keep the cracking running for a few more hours.
I've managed to crack even these passwords, which were not in any word list I've used:
JK52jarka– “jarka” is a short form of a Czech name
lockap7gia– “lock” + hmm, something
soyouitknow– four English words, “incorrect” order
str3ela9133– Czech word strela customized by rules + a number
Marketa19..– a name with an upper-cased first letter + a number + dots
Renik2510!!– similar, but with two exclamation marks, both well known patterns
15zdenek1973– “Zdeněk” is a Czech name
to neuhodnes– means “you won't guess it” in Czech (this is an exception, it was in the
natoneprijdes– three Czech words, no spaces, means “you won't find it”
čokoládamilka– “Milka chocolate” in Czech, the
rockyou.txtlist contains a variant without the accented characters –
kobylamamalybok– four Czech words, a palindrome actually
fm9fytmf7qkckct– first 15 characters of a Microsoft Office license key
asdfghjkl0123456789– a “keyboard walk” + a sequence
…and 380 961 more. Some of the not cracked passwords are:
carolinepassword2680?– a name + password + a number + a questionmark
passwordusuniversalis– two words with -us and -is suffixes
3681913234731michal– a number (actually a CD key for the Counter-Strike game) + a name (nope, not my password)
Qawsedqawsed11+– 2× a “keyboard walk” + a number + a plus sign
j4 n3v1m v073– ja nevim vole means “I don't know dude” in Czech, here with well-known substitutions
PyQ7z4XwBf1o9– first I though this was a computer-generated password, the strongest one in the leak, but smells like a password reuse, although the question is for how long has the password been known (no other Mall.cz passwords present on that site)
●●●●●●●●●●●– no idea how this password made it to the database, but I've managed to crack this 3-chars-longer variant anyway:
There's no single password-manager-generated password on the list of not cracked passwords, and all of them are similar to what has been cracked. So I think that the rest could be cracked too relatively quickly.
I think the passwords in the leak could have been hashed somehow. Cracking cryptographically salted SHA-1 (a hash Mall.cz has been using 2012–2016) would take much more time not only because the speed of generating SHA-1 hashes is three times slower, but also because the optimization of comparing one candidate with all the hashes can't be utilized, each hash uses a different salt. Some of the passwords stored using bcrypt hash (since 2016) could be cracked too, but just some weak ones like password (GTX 1080 Ti does 646 hashes/s for bcrypt with 210 iterations, Tesla V100 does 1707 hashes/s), but Mall.cz says that
most of the cracked passwords are from the period when we were using MD5.
Two tips to conclude with: