Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

How can I tell if a password has good enough entropy to prevent brute-forcing on a realistic timescale? For example, if I have the following password, how can I determine if it is strong enough to prevent brute forcing?

"?e&ye&ga!ruaa!na!e%ta!e%rc#Iod$woH"2245
share|improve this question
    
Does the attacker know the general structure of the password, e.g. only ASCII characters, digits only at the end, all lowercase letters, and almost alternating letters and special characters? –  Daniel Beck Apr 9 '11 at 8:42
    
not all lowercase ;) and no the attacker would not now the structure, it is based on a simple easy to remember sentence with some basic changes that are consistent. –  abdadooo22 Apr 9 '11 at 9:16
    
See also security.stackexchange.com/questions/6499/… –  ripper234 Jan 13 '12 at 8:13
    
Well now that you posted it here it is pretty easy to hack :). –  Brad Patton Oct 1 '12 at 17:54

4 Answers 4

From the Dropbox tech blog, this is the best article that I have seen recently, and even shows at an implementation on the theories discussed within. Please feel free to let me know if this is helpful in any way.

Another thing to keep in mind about security, is the idea expressed in this XKCD comic.

share|improve this answer
2  
Welcome to Super User! Here's a tip for ya: I would add a little more detail from the site, and impart knowledge to the OP. It's ok to hyperlink to a site, it's far better to hyperlink and then summarize. –  KronoS Jun 20 '12 at 19:21
1  
Excellent link. Lots of very useful and detailed analysis. I was going to pull the most useful stuff into an edit of your answer, but there is just too much good stuff. –  killermist Jun 20 '12 at 19:36
    
I would have added quite a few more links, but this was my first post and I was limited. Thanks! –  dmcgill50 Oct 1 '12 at 17:38

It depends how random your password is.

If you choose a password from the following list:

  • "?e&ye&ga!ruaa!na!e%ta!e%rc#Iod$woH"2245
  • aSBsb3ZlIHlvdSBLaXJzdGVuIFNoZWxieSBHdXllcg==

Then you have exactly 1 bit of entropy (it's either the first password, or the second).

That's when you read the XKCD comic that Dave linked.


But i can make some assumptions about your password:

"?e&ye&ga!ruaa!na!e%ta!e%rc#Iod$woH"2245  (40 characters)

It looks like you use an alphabet of:

  • uppercase A-Z (26 glyphs)
  • lowercase a-z (26 glyphs)
  • latin numerals 0-9 (10 glyphs)
  • limited set of punctuation (assuming the 30 symbols on a 101-key keyboard)

That totals to an alphabet of 92 characters.

Further assuming that all your passwords are 40 characters, that gives you:

92^40 = 3.56+E78

or 3.5 quinvigintillion possible passwords.

To convert that into bits you do:

ln(92^40) / ln(2) = 260.94 bits

That's assuming your attacker would have to brute-force the password.


If we only want information, then the number of bits is actually much lower, because you actually used a much shorter alphabet:

  original: "?e&ye&ga!ruaa!na!e%ta!e%rc#Iod$woH"2245
rearranged: aaaaacdeeeegnoorrtuwyHI2245""?&&!!!!%%#$
  alphabet: acdegnortuwyHI245"?&!%#$   (24 characters)

Performing the same calculation:

ln(24^40) / ln(2) = 183.4 bits

Realistically there's fewer bits of information there because i can see that every time you type an e it is followed by a symbol:

  • e&
  • e&
  • e%
  • e%

So we replace e& with the symbol h, and e% with the symbol i:

  original: "?hyhga!ruaa!na!ita!irc#Iod$woH"2245  (36 characters)
rearranged: aaaaacdghhiinoorrtuwyIH2245""?!!!!#$
  alphabet: acdghinortuwyIH2245"?!#$   (24 characters)

Which reduces the information content to:

ln(24^36) / ln(2) = 165 bits

And i noticed that every ! is preceeded by an a and followed by a letter:

  • a!r
  • a!n
  • a!e

Replacing a! with k:

  original: "?hyhgkruaknkitkirc#Iod$woH"2245  (32 characters)
  alphabet: acdghiknortuwyIH2245"?#$   (24 characters)

Reducing bits to ln(24^32)/ln(2) = 146.7.

That only reduces the bits required for encoding, as we figure out the information content of the message.

These tricks don't help an attacker, who can't generally assume all passwords have these known sequences.

But there are some heuristics that can be programmed into a key search algorithm. People trying to type randomly type the same things a lot. For example i often get a collision when randomly typing:

adfadsfadsf

along with 18,400 other google results.


My most secure password is 57-characters, with a 27-character alphabet (a-z, ), which comes in at 266 bits (ln(27^56) / ln(2) = 266.27).

On the other hand it is eleven words. There are about 2^11 common words in the english language. That gives:

(2^11)^11 = 2.66E36 passphrases => ln((2^11)^11)/ln(2) = 121 bits

Far less than the 266 bits that would be nievely assumed from random 57-character password.

i could add one bit if i chose between:

  • spaces between the words
  • nospacesbetweenthewords
share|improve this answer

There's a site that can give you an estimated entropy figure for a password input. For the above example it suggests ~210 bits.

enter image description here

You can get a very rough guess of how long it will take to crack on How Secure Is My Password.

It suggests it would take a standard desktop PC 2 vigintillion years to crack the password in your example.

enter image description here

A more detailed analysis of the password can be seen on The Password Meter.

share|improve this answer
    
long enough, i suspect ;) –  Journeyman Geek Apr 9 '11 at 9:03
1  
I saw both sites give misleading sense of security. I picked up a common dictionary word, repeated it again and again and "etropy" was increasing more than linearly, which is an absurd. –  user39559 Apr 12 '11 at 12:33
1  
Oh, I had missed the one in the middle. I like it much better, it's very good and at least they have a decent disclaimer. –  user39559 Apr 13 '11 at 20:23
    
+1 I learned a new word today. But I think I read the V word with an R somewhere ;-) –  Ellesa Jun 20 '12 at 19:26

Your question - "Is it strong enough to prevent brute force?"

The real answer - "no"

The useful answer - "Probably, at least for the foreseeable future"


What you should be asking:

I need to protect this type of data, which has requirements x and y, and sensitivity z for my company. Is this an appropriate level of entropy.

Okay, to be fair, 210 bits as @Gareth pointed out is likely to be fine for a long time, but that may be overkill, and there are good reasons not to go over the top on encryption if you don't need to.

share|improve this answer
1  
Note also a more recent xkcd: xkcd.com/936 If you're not constrained to 8 characters, there's no real need to subject yourself to trying to remember (or even retype) line noise. –  Dave Sherohman Aug 24 '11 at 9:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.