Passwords revisited

After having generated pre-shared secret keys for IPsec VPNs, as recommended by the NSA, I wondered how “secure” the keys themselves actually were. The NSA specifically mentions the use of “large, high entropy, pre-shared keys”. Quite some time ago I wrote two posts about passwords, passphrases and a very crude and naive, home brewn, exhaustive search algorithm a.k.a. brute force tool. Now, digging a little further, but this time more into the topic of password strength, I came across appendix A of NIST SP-800-63-2. From my earlier searches I remembered this page, which lines up nicely with SP-800-63 appendix A.1, and the math behind it is not that difficult (yay!) As it turns out, this all here is pretty much on Wikipedia’s page on password strength, but this post is my 2 cents on this subject, including an offline random key generator that runs in your web browser. To calculate the strength of a password as ‘entropy’, all that is needed is:

  1. The length of the generated passwords’ characters (l)
  2. The length of the character pools’ unique characters, or alphabet (b)

Entropy (H) is calculated as:

H = log2 (b^l)

This can be rewritten as:

H = l * log2(b)

…Which then is:

H = l * ( log(b) / log(2) )

Now that, is perfectly possible to do in any programming language. Since I’ve been using javascript to generate the pre-shared keys for IPsec VPN gateways, I wrote a strong password generator that includes the strength of the generated password in entropy here.

According to theory, the resulting entropy (H) is the average number of binary digits required per letter of the original language. And since bits are either 0 or 1, H bits means 2^H possible combinations.

Since calculating the entropy is fairly constant, NIST SP 800-63-2 has done some of the calculations in table A-1. And although this is said to be “at best a very crude estimate”, I’ve used it to verify the calculated entropy of a random password by the generator and seems to work pretty much ok, but without the calculation of bonuses as part of entropy estimate guessing. This would probably mean that the entropy calculated as I’ve done in the generator is the best achievable for the given pool of characters to choose from. Since the entropy is a general statistical value for all the passwords generated for this particular length and alphabet, it isn’t of much use to compare different generated passwords that were generated with the same length and alphabet. Instead, to compare the strength of the generated passwords, I estimated the time needed to brute force a generated password based on the number of its unique characters. For example, if you would have a password of 3 characters, then the password AAA would be guessable in 1 guess; as there’s no point in shuffling one and the same A around, AAB in 3, ABC in 6. So, the more unique characters were used, the higher the entropy of that particular generated password would be, since the alphabet used was slightly larger than others. More unique characters, more combinations that the attacker needs to check. That assumes that the attacker knows quite a lot: how long the password is *and* also knowns exactly which characters were used in it. I’ve added a ‘threshold’ value which acts as a minimum requirement for the number of unique characters in a generated password. Here are some presets:

Characters used Password length Guesses per second Url
4 digit pin-code 4 100
http://bjvb.nl/strongpassword.php?l=4&n=25&s=0123456789
[a-z] 12 100 http://bjvb.nl/strongpassword.php?l=12&n=25&t=0&s=abcdefghijklmnopqrstuvwxyz
[a-z][0-9] 12 100 http://bjvb.nl/strongpassword.php?l=12&n=25&t=0&s=abcdefghijklmnopqrstuvwxyz0123456789
[a-z][0-9] 12 1000000 http://bjvb.nl/strongpassword.php?l=12&n=25&t=0&g=1000000&s=abcdefghijklmnopqrstuvwxyz0123456789
[a-z][A-Z][0-9] 12 100 http://bjvb.nl/strongpassword.php?l=12&n=25&t=0&s=abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
Or, really strong
[a-z][A-Z][0-9][punct] 96 1000000000000 http://bjvb.nl/strongpassword.php?l=96&n=50&g=1000000000000

 

Epilogue

Making a password generator that produces passwords based on the rules given by NIST goes way beyond my awful little hackery in javascript.  There’s a market for secure passwords as authentication based on passwords will probably be with us for the next few decades.

Please note that passwords or keys that are generated using javascript assume that javascript is capable of true randomness, which of course it is not. Because these passwords are hideously complex, you probably won’t be able to remember them. There are two possible solutions to this: a) use a password manager, b) write them down. Option a is very convenient, but is an “all eggs in a basket” or “winner takes all” risk-scenario. If you truly need to protect secrets, I’d favor option b here. Provided that you write it down only once, and store it in your wallet. This is not scalable, and will require thought on what is a secret and what isn’t 😉

From a more practical point; This is what I would use if I needed a pre-shared key for a VPN; short enough to write down and nearly impossible to memorize for the average human being:

http://bjvb.nl/strongpassword.php?l=32&t=29&g=145000000000

The number of guesses per second (g) in that URL is based on real life brute force power as described here. Actual time taken for brute force to complete as reported with a generated password  is still a guess, because true password recovery tools like john perform a lot of clever tricks to guess passwords which the javascript generator doesn’t use. It appears that there are quite a number of websites that try to estimate how much time would be needed to crack a password. They’re all different and none of them explain exactly how to calculate such estimations. The default number of guesses in the generator (100) is based on my personal experience with john and hydra, but simple brute forcing without hashing is a lot faster. If you toy around with the generator, you’ll notice that password strength largely depends on the number of unique characters; Some 12 character long passwords can be guessed in 7 days, while others in that same pool would take 2 years, both based on 100000 guesses per second.

Online brute force attacks are slow, not very likely to be more than 100 per second. Offline attacks are a lot faster (>> 100), but require a copy of the password database and knowledge of its internal structure; Usually some one-way function or hash is used to ‘encrypt’ the password stored in it. So that an attacker would have to ‘hash’ a password, which is all of course way beyond the javascript generator. More sophisticated hackers would use dedicated hardware to crank up the guessing attempts quite a bit. As a defender, in this particular case, additional computational tricks or using a computational expensive hashing algorithm may actually make sense to slow down brute force attacks. An easy solution to implement this in code could be to hash a password a thousand times over. This could – of course – frustrate users who make typo’s or don’t remember their passwords as logging on to a system using this would be sluggish. Doing so may also introduce operational issues if not carefully applied; Excessive (ab)use may lead to a denial of service situation. There are other solutions to this, scrypt, captcha’s, wait cycles, etcetera.

If you’d like some more hands-on experience cracking passwords, I can highly recommend Kali, containing all tools needed including the ultimate and awesome nmap and Metasploitable. Be sure to build an isolated hack-lab first!

This entry was posted in Crypto, IT Security and tagged , , , . Bookmark the permalink.