Password entropy

By Marcus Wilson 30/04/2014

As part of some 'NetSafe' training, I was shown this lovely xkcd cartoon .


Password entropy. That's a good way of putting it. The statistical mechanics definition of entropy would be k ln W, where k is Boltzmann's constant, W is the number of permutations possible, and ln is 'the natural logarithm'. Higher entropy, means more possibilities. Simply put, the longer the word is, the harder it is for a machine to guess. One doesn't need terribly long sequences before the possibilities become immense indeed. 

So then, how come just about everywhere where I need to use a password* requires me to include non-alphabetic characters, and, sometimes, non-numeric characters too, making it very hard to remember my passwords. Plus, we have passwords on so many different systems nowadays (if I felt I had the time I'd compile a list of how many different systems I have accounts and passwords on – I reckon it's of the order of one hundred) that it is inevitable that we start writing down passwords in an easy to access place – thus almost completely negating the point of them. 

Computer scientists, we need a better system…

*This includes the University of Waikato, whose site I am using for composing this blog entry. It demands a mix of letters, numbers and other symbols and for the password not to be based on a word. And these IT people who control the site are the ones pointing me towards the xkcd cartoon above…Sorry to get at you guys, but the discrepancy is rather obvious. 

0 Responses to “Password entropy”

  • hear, hear! There are some sites I don’t visit all that often, where I find I have to keep requesting a password re-set because I can’t remember the darn thing between visits 🙁

  • I find the opaqueness of some sites to be frustrating. Is my user name supposed to be my email, or the account name you gave me later on? Give me a hint please- does your page want an email or something else.

    Same problem with the passwords. Is this a site that required numbers as well as letters? Do I need some capitals or symbols. There is a sense of panic you get, looking at that blank box marked password, and you’re trying to second guess what their system was before you make too many mistakes and get locked out.

  • My Passwords reference document has about 90 entries, and is, you guessed it, password protected. I refer to it at least daily, sometimes more often. Some banks make life so passwordly difficult that one wonders why people continue to bank with them, especially those that require, nay, force, clients to regularly change their passwords! Needless to say, I don’t bank there.

  • What’s even worse is the realisation that you can’t remember the exact answer to your ‘security question’ – you know, the one you set up when you opened the account, especially for use when faced with a lock-out.

  • I actually don’t agree with this message. So first my knowledge of (Shannon) entropy is via a course I did on compression theory. The shannon entropy (calculated log base 2) corresponds to the expected number of bit required to compress each character.

    So let’s assume the letters are IID UAR. Then ‘correct horse battery staple’ is ~133 bits of entropy. Sounds pretty good right? But of course English letters aren’t distributed UAR so if you use the frequency of english letter to calculate Shannon entropy you find 4.18 bits per character so the string becomes ~117 bits of entropy. But here is the rub, you can use preceeding characters to adjust the probability of the letter you’re looking at. For example If I ask you what comes after the string ‘elepha’ it’s a different distribution to what comes after the string ‘sciblo’. When you include this English is thought to have only require about 1.2 bits/character and some compression algorithms can actually get about 1.4bits/character in which case the original sentence has only 33.6 bits of entropy.

    Then let’s return to ‘Tr0ub4dor&3’. If it was just ‘troubador’ we’d expect only 10.8 bits. However when your doing substitutions, even common ones, it requires extra bits *for each character* rather than what the comic would have you believe where it’s only the different character. So your options are lower or upper case or a number distributed more or less UAR then you need an extra 1.6 bits/character so ‘Tr0ub4dor’ would be 17.28 bits. Punctuation and a numeral (should you know in advance that’s all that’s needed) adds ~8 bits and so you’d expect ‘Tr0ub4dor&3′ to have at least 25 bits of entropy. Not as good as 33 but the difference isn’t as great as 28 to 44!

    But let’s say you use a random number generator to generate password. About how long would they need to be to obtain 50 bits of entropy?

    ~42 characters of English words/phrases
    ~15 numbers IID UAR
    ~11 lower case letters IID UAR
    ~9 upper/lower case letters IID UAR
    ~8 upper/lower case letters + number IID UAR
    ~7 characters chosen from your keyboard IID UAR

    I use the command

    cat /dev/urandom | tr -dc “[:print:]” |fold -w 10|head -n 10

    to generate 10 passwords of 10 charaters each according to the last distribution so I’m getting ~66 bits of entropy for that and for things I want to be especially secure I use 20 characters.

    Now you might be thinking how do I remember something like

    FM”+0M X53

    which is output of running it just now, which brings me to the second issue: write down your damn passwords! As security guru Bruce Schneier (who you should really follow if you are interested in this sort of thing) points out human being are *really* bad at coming up with secure passwords per site they have to log into, however they are quite good at keeping bits of paper (i.e. money) safe. So use a password generator to generate passwords, write them down and keep them safe on you. I have mine in a notebook and backed up on an encrypted USB drive in a safe place (in case the notebook ever goes missing) and change them all yearly. You can also take this one step further and leave off a character or swap the cases to what you actually use when entering in the password, just in case. The passwords you use often you do just end up remembering and, especially in NZ, you’re at far more risk of someone hacking your insecure password than you are of being pick pocketed and having the thief work out what the pages of random characters correspond to.