4

This site suggests using 4 common English words as a password is no longer safe.

Apparently the top 5000 English words in any combination of 4 words can be hashed in 1.5 minutes at 7Thash/sec.

The article didn't mention the hashing algorithm - but this is worrying.

Can anyone validate what this article is saying? I have a feeling they were talking about straight MD5 hashes. Also, how long for all the English word combinations - not just the top 5000? I couldn't quite do the math but came up with 8.6×1020 combinations.. I don't know how long that'd work out at.. a long time at a guess?

forest
  • 65,613
  • 20
  • 208
  • 262
John Hunt
  • 161
  • 6
  • 1
    There is no definitive set of "all English words" to pick four from. – Οurous Jun 08 '18 at 09:33
  • 1
    For the sake of argument, let's say 171,476 words which is what google comes up with (I think that's "English words in use") – John Hunt Jun 08 '18 at 09:42
  • The funny thing is, nobody ever claimed 4 words is sufficient against this type of attack (offline hash-cracking attack). In fact the famous comic referenced in that article explicitly states that it doesn't apply to offline hash attacks. "Diceware" (which uses 7776-word dicts instead of 2000ish) *started* by recommending 5 words and now recommends 6. Easy solution to this "problem", then: Add. A. Word. – Ben Jun 13 '18 at 15:44
  • Side-note: I hate all these articles thinking they're clever by "debunking" the "correct horse battery staple" method which never seem to understand the method anyway, and almost inevitably end up recommending some lame security-through-obscurity scheme instead. This article is no exception. – Ben Jun 13 '18 at 15:46

1 Answers1

5

If you are choosing four items from a set of 171,476, you have a keyspace of 171,4764. 7 TH/s is 7×1012 per second, so 171,4764 / 7×1012 ≈ 1.24×108 seconds to search the entire keyspace. The average time will be half that. So at a "measly" 7 TH/s, this would take an average of 715 days.

Note that this only provides approximately log2(171,4764) ≈ 69.6 bits, which is worryingly small. A dedicated attacker can exceed 7 TH/s. Google publicly broke SHA-1, requiring only 263 operations. Doing 269.6 operations is a lot more, but certainly within reach of a powerful adversary.

So what if you are choosing from only 5000 words? 50004 / 7×1012 ≈ 89 seconds maximum, and an average of half of that. After all, it only provides 49 bits of security. Not good!

forest
  • 65,613
  • 20
  • 208
  • 262
  • What hashing algo are you basing this on? – John Hunt Jun 08 '18 at 10:01
  • 2
    @JohnHunt You specified 7 TH/s. If it's MD5 then we assume it's being cracked at 7 TH/s. If it's SHA-256 then we still assume it's being cracked at 7 TH/s. – forest Jun 08 '18 at 10:02
  • Good point. The article suggests this is the fastest GPU available - what algo would you say that is at 7TH/s? – John Hunt Jun 08 '18 at 10:07
  • 1
    Sounds like it could be MD5 or SHA-1 but still seems pretty high. Just two years ago, the fastest for MD5 was something like 200 GH/s and I doubt the speed increased by 35 times in two years). But remember, a dedicated attacker will be using a cluster of ASICs (consumer ones can regularly do 20+ TH/s for SHA-256), not a single high-end GPU. BTW, modern recommendations for diceware-based passwords usually give 12 words (from a 7,000 dictionary) to be ideal. – forest Jun 08 '18 at 10:08
  • Or an equivalent number of combinations from a larger dictionary (though I would argue that 7000^12 (10^46) is *extreme* overkill). A 10^27 equivalent (7000^7) - which is still beyond projected medium-term bruteforce capability for fast hashes like MD5 - gets you a word count (7) in the middle of the "5 to 9 things" that humans can retain short-term while memorizing. Increase the dictionary to still fit within most vocabularies (say, 30,000 words) and you can get it down to 6 words. See https://twitter.com/jmgosney/status/714599158229786625 for how to think about the math and the risk model. – Royce Williams Jun 08 '18 at 10:37
  • 1
    Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/78631/discussion-between-royce-williams-and-forest). – Royce Williams Jun 08 '18 at 10:53