Hacker News Reader

Comment by quinndupont | Hacker News Reader

I just left a comment on the hashcat forum asking if anyone could offer a better back-of-the-napkin calculation of the real-world implications of this. My understanding is that we're still looking at something like 10^27 years of cracking to exhaust the password space.

Any (more clever) HNers care to offer a interpretation and calcuation?

View on HN

It depends on the size of the space your passwords are drawn from.

The dictionary files I have in /usr/share/dict/ have about half a million words. Mean length is 11 characters. And there are about 100 characters easily accessible on my keyboard (letters, numbers and common symbols).

Regular words, trying lower case, UPPER CASE or First Letter Capitalised. 3 * 0.5 million options = Half a second to search.

Same but with a two digit number before or after (e.g. Patio11): 2 * 100 * 3 * 0.5 million options = 100 seconds to search.

Single regular word with up to 4 standard keyboard characters before or after (e.g. Patio3&A@): 2 * 100^4 * 3 * 0.5 million = about 3.1 years to search.

Two regular words, same case options, with or without a space. (3 * 0.5 million)^2 * 2 = 17 days to search.

Single regular word, random capitalisation (e.g. paTIo) rough figure: 2^11 * 0.5 million = 6 minutes to search.

Single regular word, random capitalisation, 4 standard keyboard characters before or after (e.g. PaTio8#`¬): 2 * 100^4 * 2^11 * 0.5 million = 2163 years to search.

Four regular lower case words (e.g. correct battery horse staple): (0.5 million)^4 = 660000000 years to search.

Up to 10 letters or numbers, upper or lower case (e.g. nk7rFG9Ad9): 63^10 combinations = 10403 years to search.

Up to 8 letters or numbers, upper or lower case (e.g. Plfws0aX): 63^8 combinations = 2.6 years to search.

Assuming you could obtain the same 3M hashes/second on an Amazon EC2 cluster GPU instance (this isn't a given as they have nVidia GPUs instead of the ATI chip used in the test reported) 2.6 years of GPU time at the spot price of 35 cents an hour would cost $7976.85

Needless to say, if you had access to a whole load of people's 1password files, probably some of them would be following a weak password selection scheme and you'd break them within seconds. On the other hand, people with strong password selection schemes will still be safe.

PBKDF2 is salted, you can't attack multiple hashes with one computation.

Yes, to attack multiple files you'd have to do multiple computations.

However, if you can try all dictionary words in 0.5 seconds, you can try that against 172800 files in a day.

Of course you'd need a security breach that gave you access to multiple files too!

Like a breach on Dropbox, a company that 1Password has no control over?

Thanks for all the responses everyone! But, isn't the point of BKDF2-HMAC-SHA1 in 1Password that it's a 320 bit key, that he reduced down to only 160 bits? Unless I'm totally missing something here, it doesn't much matter if the password you are attacking is 6, or 7, or 8 or 50 characters long, you'll still need to attack all 160 bits, right? (Ignoring rainbow tables, or hashing on password dictionaries, etc., in other words, just brute force cracking). Am I being stupid?

It depends on how good your password is

"A user-selected eight-character password with numbers, mixed case, and symbols, reaches an estimated 30-bit strength, according to NIST" [1]

2^30/(3M attempts/s)=358s

A completely random 8-character password from a space of 64 characters (upper, lower, number + 2 symbols) is 48 bits:

3^48/(3M attempts/s) ~= 3 years

Multiply by 64^N for longer passwords (so >180 years for a 9 character password)

The reason for the difference is that user-selected passwords are (on average) not as good as random passwords.

[1]http://en.wikipedia.org/wiki/Password_cracking#Time_needed_f...

> 3^48/(3M attempts/s) ~= 3 years

But that's just with 2 GPU's! Any larger bitcoin miner has a few hundred (up to many more) of these graphics cards running. 100 GPUs would require only 20 days! Any larger entity could easily setup 1000 GPUs which cuts it down to 2 days, etc.

Probably there will be password cracking pools, similar to altcoin mining pools, which pay for your GPU resources in bitcoins.

They will need to do something with their rigs once mining gets too hard and the payouts too small.

Hmm, what's the opportunity cost (in terms of average BTC not mined) for doing 2^48 attempts?

It takes on average 2^54 hashes to discover a block at the current difficulty. So 2^48 attempts is 2^-6 (1.5%) of a block on average. A block is currently worth ~$2000, so 1.5% of that is ~$30

The real-world implications are one of the world's leading password cracking projects is able to test candidate password guesses 50% more efficiently than they would have otherwise.

This amounts to the loss of almost exactly 1 bit of security. Yes, really.

The first letter of my password is lowercase, not uppercase. There, that's how much it matters. 1 bit.

I'd suspect it's a problem for people who think that, since it uses $fancy_encryption_scheme_they_cant_pronounce_or_understand, they can just use a trivially easy password for a computer to guess. Utilizing encryption isn't helpful if your password is still just "password1". I'm not a cryptographer by any means, but my general understanding is that longer is better. Picking some random nonsense sentence like "Correct horse battery staple" and using it as your password, is better than using "p455w0rd!1".

There are multiple password cracking techniques. Under brute force longer is strictly better. However, there are sophisticated dictionary attack programs that are also seeded with leaked password lists and do a variety of clever substitutions to come up with many potential candidates from each base word. For that type of attack, a password like: passwordpasswordpasswordpassword may not be a great bet despite it's length.

However, I'd assume a password like:

thisisthepasswordthatiwilluseonhackernews

would still be relatively hard to crack?

Not if they run through a dictionary of common words and include the site name in that dictionary. (Common practice)

The search space grows exponentially with each additional word being added. With enough words, it gets infeasible to bruteforce.

@rorrr: You've been hellbanned for almost a month.

------------

His comment:

> It's nearly identical.

> There are around 170,000 english words (including all the obscure ones you've never heard and have no idea how to spell).

> Number of 4-word combinations:

    170,000^4 = 8.35 * 10^20

> Lowercase (26) + uppercase (26) + digits (10) + special characters (36) = 98 characters

   98^10 = 8.17 * 10^19

> An order of magnitude difference.

> And if they start bruteforcing with the simpler words (which you used in the example), there are only 5,000 - 10,000 of them, the number of your combinations drops dramatically:

    5,000^4 = 6.25 * 10^14

    10,000^4 = 10^16

> So unless you use very obscure words in your password, you are doing much worse than you think.

Well 2^48 ~= 2.8 x 10^14, so it's not as bad as you think for the simple words version (which is the same as 8 characters chosen from 64 choices)

> You've been hellbanned for almost a month

For good reason; please check someone's comment history before advising them of this.

Reply on news.ycombinator.com