14

I generally use GnuPG for encrypting my files and as far as I know its strength ultimately depends on the passphrase I use. So, I would like to know: how can I mathematically calculate how secure my password is? How do I know whether my password is safe or not?

greatwolf
  • 189
  • 1
  • 10
user774025
  • 257
  • 1
  • 3
  • There has been a good discussion on password strength http://security.stackexchange.com/questions/6095/xkcd-936-short-complex-password-or-long-dictionary-passphrase you can have a read – Ali Ahmad Dec 25 '12 at 17:46

3 Answers3

13

The strength of a password is, exactly, a measure of what it could have been. The technical term for cryptographers is "entropy". The rough idea is the following: there is a set of "possible passwords" -- the passwords that you could choose. The attacker will try the passwords from that set. The attacker will be defeated if the set is large enough, because the larger the set, the longer it will take the attacker to hit the right password (on average).

For instance, if your passwords are sequence of 9 decimal digits, then the set of possible passwords has size, exactly, one billion (109). If you choose your password at random in that set, then, on average, the attacker will have to try half of the set before trying yours, so 500 millions.

Thinking about a big bag of possible passwords from which you choose, at random and uniformly, works as long as you really pick the password at random and uniformly. That's easy to do with a computer, very hard with a brain: the jelly which you keep inside your skull is remarkably good at a lot of tasks (such as image recognition), but not at randomness.

The important point to understand is that password strength comes from the password generation process. A given password is not strong "by itself". That's where "password meters" totally fail. A "password meter" sees only the password you type, not how you chose it. If you prefer, a password meter site will tell you how much time it would take an attacker to guess the password, assuming the site is the attacker, and knows nothing else about you. That's not completely realistic: your enemy knows you, much better than a lambda site on the Web. He is after you, specifically, and he must be assumed to be smart.

So, to estimate your password strength:

  1. If you generated the password in your head, then try again: it is weak. From now on, I assume that you produce the password with a random generator (a computer with /dev/urandom, some dice, coins flipped... the choice is large).

  2. Compute the size of the set of possible passwords, depending on your generation algorithm. For instance, if you use a 20-sided die to generate symbols (letters from A to T), and you launch the die 8 times, then the set of possible passwords has size 208 = 25600000000.

  3. Estimate how many passwords the attacker may possibly "try". This is where the encryption details matter. GnuPG follows the OpenPGP format in which passwords are converted to keys through a hashing process which is intrinsically slow, in a configurable way (see section 3.7.1.3 of RFC 4880). This is expensive both for you, and for the attacker. The attacker has several computers which are bigger than yours, so he will be able to try a lot of passwords, but not ludicrously many. As a rule of thumb, consider that the attacker can try no more than one million passwords per second.

  4. From the two previous steps, compute how much time it will take for the attacker, on average, to crack your password. On average, he will have to explore half of the set of possible passwords. With the numbers above (8 symbols from a 20-symbol alphabet, one million password guesses per second), you find 12800 seconds, i.e. a bit more than 3.5 hours. That's not much for comfort... but each additional symbol multiplies the attacker effort by 20. So 10 symbols with your D20 bring the attack time to about two months, at which point the attacker ought to declare that it is "not worth the effort" (which is your goal).

Hence the rules for strong passwords:

  • Don't trust your brain. Generate the password with a computer or dice.
  • Accept the generation result. Don't generate passwords until you find one which seems "easy to remember".
  • Stick to symbols which are easy to type. In particular, a sequence of lowercase letters is easy on a smartphone. Mixing cases, digits and punctuation symbols makes the password usage frustrating.
  • Use sufficiently many symbols so that the set of possible passwords is large enough. This depends on how well (or how badly) the encryption system hashes the password into a key. Unless the encryption system is tremendously incompetent (in which case you should not use it at all), 12 or 13 letters will be enough (do the math !).

In the famous XKCD password comic, the author suggests taking a list of 2048 "common words", and then selecting four such words (at random, with dice): the four words, concatenated, will be the password. The set of possible passwords then has size 20484 = 17592186044416, which is quite good. The point of the author is that such passwords are easy to remember (whatever the four words you obtain, you will find a corresponding "story"). Personally, I prefer shorter passwords which are just random letters (my brain, being that of a mammal, is bad at randomness, but it is quite good at remembering strings of symbols).

The key to remembering a password is to type it daily.

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
3

http://www.passwordmeter.com/

For security reasons, don't enter your real password, but an approximation, for example, if your password is asl6234FDS, type ajk0175MAF. Strong password has a score of 100%.

Matrix
  • 3,988
  • 14
  • 25
  • Thank you for the link. But I would like to know a method so that I can calculate it myself. – user774025 Dec 25 '12 at 13:46
  • Look at the rate column. Also, it's JavaScript, so you can look at the source code. – Matrix Dec 25 '12 at 14:27
  • `BadPassword12` gets 83%, this is a good tool and gives a nice breakdown, but scores a little too highly imo. – lynks Dec 27 '12 at 13:24
  • 2
    That tool is really bad. It wants you to use special characters, is all. [Special characters don't make a password better](http://security.stackexchange.com/questions/6095/xkcd-936-short-complex-password-or-long-dictionary-passphrase/6096#6096). – Gilles 'SO- stop being evil' Jun 19 '13 at 22:59
2

To calculate how strong your password is by yourself you must first understand how a an attacker might 'crack' it. There are three main ways:

  1. Dictionary attacks
  2. Hash Tables
  3. Brute forcing

Now assuming your password is 'strong' (i.e. is random long and uses lower case, upper case numbers and symbols), then the attacker should be limited to brute force attacks, so I will limit my answer to this.

Brute Forcing means that the attacker will try every possible password. To keep things simple let's say your password is only 1 char long, and only uses lowercase alpha chars (i.e. the alphabet). This means that the attacker would start at a, then b, c, d, ... z. Now there is 26 letters in the alphabet, which means if you only have a password 1 char long and lower case, they must make 26 guesses (and on average they should crack the password halfway i.e. 13 guesses). By introducing uppercase you double this, (i.e. it will on average take the attacker 26 guesses, or in other words, it will take the attacker twice as long). Adding numbers and symbols will also increase the number of guesses, and hence the length of time needed to crack the password.

By adding a second character (i.e. a 2 char long password), the amount of passwords the attacker has to guess is exponentially increased.Once again to keep things simple let's study a binary password (i.e. it can only have 2 chars 0, or 1):

For a 1 char password the possibilities are:

  • 0
  • 1

This is 2 passwords, for a password of length 2 the possibilities are:

  • 0
  • 1
  • 00
  • 01
  • 10
  • 11

There is now 6 possibilities.

Therefore to calculate password complexity you need to consider two things:

  1. The amount of different chars used (upper, lower numbers, and symbols)
  2. The length of of chars used.
schroeder
  • 123,438
  • 55
  • 284
  • 319
meowcat
  • 1,349
  • 1
  • 6
  • 16