How long will it take to h@ck y3r Pa$$w0rd?

Ever been annoyed by those password policies that say “One digit, one uppercase, one lowercase” and then cap your password at, say 12 characters? Are those passwords secure these days, when cheap processing power is freely available ? A while ago I’ve stumbled upon an article where, among other info, some really interesting data was shared about how long it takes to crack standard crypto hashes used for password encryption in WLANs, web sites and operating systems. This prompted for a refresher in password security and brute-forcing performance. The numbers are worth sharing.

In the beginning…

In the article, the author tests his i7 3840QM 4×3.8 GHz Laptop CPU with aircrack-ng and gets ~4700 WPA hashes per second.

aircrack-ng -S
# 4713 k/s

Thus, we can run some basic calculations on how long will it take to crack some PSKs (based on the data harvested direct from the air!) on a modern laptop:

8-digit numeric [0-9] password 10^8 / 4700 / (3600) 5.91 hours
8-digit alphabetic non-mixed case [a-z] 26^8 / 4700 / (3600 * 24) 514 days
10-digit [0-9] 10^10 / 4700 / (3600 * 24) 24.6 days
10-digit [a-z] 26^10 / 4700 / (3600 * 24 * 365) 952 years
12-digit [0-9] 10^12 /4700 / (3600 * 24 * 365) 6.7 years
14-digit [0-9] 10^14 / 4700 / (3600 * 24 * 365) 674.6 years

The logic behind these calculations is very simple: for numeric password there are 10 possible values for a single digit: 0-9. For 8 digits that’s 10^8 possibilities, which we’re guessing at 4700 keys/sec.

Note that the analysis we’re doing here is not 100% correct. For example, the alphabetic passwords here are assumed to be completely random, which is rarely true, as most humans use dictionary words (with some caps and substitutions, like the “Pa$$w0rd” above). Turns out, that even with these additional safety measures, dictionary words are much weaker and get hacked A GREAT DEAL faster using proper tools (read about password entropy here). In addition, statistically, attacker needs to go through 50% of all possible combinations instead of 100% as we require. So, the numbers we’re looking at are guaranteed to score a hit, but statistically the hit should come much sooner.

Check your understanding: by standard, PSKs should be 8-63 digits and may contain any ASCII printable character (of which there are exactly 95). Calculate, how long will it take to hack a completely random minimal 8-digit WPA PSK.

Looks pretty safe, right? Well, that’s only if you have a laptop… 🙂

Revving up…

Now, let’s bring GPUs into play. One of the most popular tools for that use is oclHashcat and here are some stats from its home page (kilo/mega-hashes per second):

Hash Type AMD HD7970 nVidia GTX580 nVidia 750Ti 8x AMD R9 290X
MD5 8511 Mh/s 2807 Mh/s 3115 Mh/s 93720 Mh/s
SHA1 2722 Mh/s 868 Mh/s 1103 Mh/s 29976 Mh/s
SHA256 1120 Mh/s 355 Mh/s 406 Mh/s 12312 Mh/s
SHA512 416 Mh/s 104 Mh/s 92 Mh/s 4576 Mh/s
SHA-3(Keccak) 179 Mh/s 93 Mh/s 93 Mh/s 1872 Mh/s
LM 1374 Mh/s 447 Mh/s 428 Mh/s 13008 Mh/s
NTLM 16701 Mh/s 4256 Mh/s 5577 Mh/s 183528 Mh/s
WPA/WPA2 141 kh/s 48 kh/s 52 kh/s 1149 kh/s

Essentially, any GPU offers multiple times advantage vs high-range mobile CPU, which results in improved Hashes/$ (but not necessary Hashes/kWh) efficiency. What about adding SLI and CrossFire? Check the last column: 8xR290 setup shreds pretty much everything, including those NTLM hashes (local Windows account passwords).

Let’s calculate how long will it take someone, who managed to steal your laptop, to recover a local Windows password “Pa$$w0rd!” that matches standard corporate complexity requirements:

  • [0-9 a-z A-z !@#$%^&*] = 70 chars in total, so the overall number of combinations is 70^9
  • 70^9 / (183528 * 10^6) ~= 2.5 days on 8xR290 setup. For 10-digit password that’s half a year, and for 8-digit – that’s 52 minutes.

And that’s a single PC. What about racking and stacking? 10 of those PCs will get that 10-digit password in 2.5 weeks or faster.

Want to go further?

Think of the latest crypto-craze on the planet: BitCoin. BitCoin mining is essentially cracking Double SHA-256 hashes (~5 times slower than SHA1), trying to find a very specific one. With every BitCoin mined, the difficulty to mine another one increases. Thus, currently, it is nearly impossible to achieve economically viable results w/o specialized equipment. Check this out: those guys are claiming TeraHash (1 000 000 000 000) per second per stack! Looks scary? Well, how about this?!  5.5TH/s for <$2500 single unit! 

Let’s go back to our initial exercise and populate the table with some additional brute-forcing methods for two most popular hash types. Anything longer than 1000 years is marked with ‘~’. You can create such a table yourself in Excel, using oclHashcat performance table for comparative results.

Core i7 3840QM

8xR290X

5.5TH/s BTC miner

Password

Complexity
(total variations)

SHA1

WPA

SHA1

WPA

SHA1

WPA

8-digit numeric [0-9]

10^8

1s

6h

<0.1s

66s

<0.1s

0.2s

10-digit numeric

10^10

1.7m

24.6d

0.8s

2h

<0.1s

18.5s

12-digit numeric

10^12

2.9h

6.7y

80s

7.6d

0.1s

30m

14-digit numeric

10^14

12.1d

674.7y

2.2h

2.1y

9.1s

2.1d

16-digit numeric

10^16

3.3y

~

9.3d

208y

15.2m

214d

20-digit numeric

10^20

~

~

254y

~

105d

~

8-digit  [a-z]

26^8

36.4m

1.4y

17s

1.6d

<0.1s

6.4m

10-digit …

26^10

17.1d

~

3.1h

2.9y

13s

3d

14-digit …

26^14

~

~

164y

~

67.9d

~

16-digit …

26^16

~

~

~

~

126y

~

8-digit ASCII printed [95 chars]

95^8

2.2y

~

<0.1s

138.4y

10.1m

142d

10-digit …

95^10

~

~

152.5y

~

63d

~

12-digit …

95^12

~

~

~

~

~

~

14-digit …

95^14

~

~

~

~

~

~

You can clearly see how those extra 4000 SHA1 hashing operations in WPA’s PBKDF2 function tremendously increase the strength of the hash, when everything else is just shredded by the specialized hardware. What if you rack&stack those and use them for password cracking? How long will those passwords last now? 🙂 Anyway,  using 16-digit passwords one can still be pretty safe even w/o using the special characters.

Taking ‘further’ further?

One disadvantage to all these methods is that you have to buy the gear and pay for the electricity bill. Or do you?

First of all, there is Cloud. Services like CloudCracker  will do everything for you, but for a fee (they use Amazon EC2). Or you can use Amazon EC2 yourself. Here are some stats from Amazon EC2 using two types of instances (from the initial article).

g2.2xlarge (32-core CPU) = 22000 k/s
cc2.8xlarge (1xnVidia Tesla + 8-core CPU) = 14000 k/s

Looks unimpressive after that 5.5TH miner? Why not use a botnet! These may contain millions of devices, which, even at 1K hashes/s will do a very good job of cracking anything. Does not necessarily have to be a PC.

And finally, why not combine the above? I absolutely urge you to check this article out – the researchers have built a “cloud botnet” out of free/trial offering of disk space and computing power available from DropBox, Google, Heroku and the like. Zero bills for hardware and electricity – full profit. Full video from the BlackHat Conference here.

So, here you go.

I leave it up to you to evaluate your own security, but here are my outtakes:

Strength is in the length. Changing from alphabetic (26 items) to ASCII printed (95 items) makes your password 95/26 ~= 3.5 times harder to crack (per symbol), and equally harder to remember. Adding just one more alphabetic character makes it 26 times harder to crack, and no more difficult to remember. Thus, password policies should stop pressing our brains with w@cky $yMb0l$ and just say “20+ letter phrase that is not a direct quote (think of 4-6 random words)”. Or at least do like the guys at Stanford did:

Pass-Stanford

In general, anything below 8 digits is a giveaway now, and anything (expect numbers) above 14 digits is more or less safe. But with the growth of processing power multiplied by the botnet size you never know, so I’d add a couple more digits.

Working round the limitations: sometimes we have to deal with legacy systems and client devices that allow numbers only, don’t allow special characters or (God forbid) impose those ridiculous password length limits. Time to be creative: 26-digit number string is still pretty safe (unless is contains your phone number, twice), and even 10-digit password may still be a pretty tough nut to crack if it’s completely random (using random number generators and password managers). Otherwise – send this article to whoever forces to use those systems and ask them if they have $$$ to cover for the damages 🙂

When evaluating a new system, ask how the passwords are stored: MD5 and SHA1 are no longer secure. SHA2, scrypt or anything else that intentionally slows down brute forcing will make the attack cost-inefficient: a 10 ASCII printed character password secured with MD5 is hacked within 21 days, the same WPA key takes 3500 years. Anything that stores passwords unsalted is hacked much faster due to rainbow tables. WPA PMK is derived from PSK and ESSID. Guess if rainbow tables already exist for most standard network names such as “linksys”, “sky”, “home”, “BThomeHub###” etc? 🙂

Be safe!

Advertisements

2 thoughts on “How long will it take to h@ck y3r Pa$$w0rd?

    1. Well, yes. I focused in sheer dumb brute force scenario. Regardless, your only salvation is length. And unsalted MD5… give it. couple more years and they will call it “as good as XOR” 😉

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s