Monday, 17 December 2007

How not to choose a strong password

Microsoft have published a Password Checker which is intended to help determine your password strength as you type:

Interestingly the passphrase "microsoft lm hashes are insecure" is rated as Weak, whilst "Passw0rd" (with a zero instead of an o) is rated as Strong.

Nearly everyone uses Microsoft Windows at work and at home (yes, I know you use a Mac, but you're special!). I would guess the majority of serious Windows users will be running W2K or XP. And all of these will be compatible with LAN Manager - a Microsoft operating system that most organisations stopped using decades ago! This appears to be part of Microsoft’s desire to be “backwards compatible” with older systems (although Vista is no longer LAN Manager compatible by default).

Why is this compatibility with LAN Manager important? Well, it comes down to how your password is encrypted and stored. By default, Windows passwords are encrypted using two different algorithms: the LM algorithm (to retain compatibility with LAN Manager) and the NTLM algorithm (which is cryptographically stronger). The encrypted password is called a hash - and both types of hash are stored on your computer. The first problem with the LM hash is that it is in fact composed of two 7-character hashes. So if you were to choose a 10-character password, it would effectively appear to be a 7-character password and a 3-character password, reducing the number of permutations significantly. The second problem is that the LM algorithm coverts upper and lower case characters to all upper case, thus reducing the number of permutations even further. Finally LM hashes use a smaller set of symbols than NTLM - you might see where this is going ...

You might imagine that even a 7-character password is very difficult to crack. Indeed, if we were to try guessing every possible 7-character password using an automated tool, it might take something like a month to work through all the permutations, by which time you may well have changed your password (although Elcomsoft seemed to have changed the rules on this recently). However, most people choose something far simpler - perhaps the name of their partner with a number appended or some other word commonly found in a dictionary. An attacker with the right software can try most words from the English dictionary, a large selection of proper nouns, and all of these with one or two numbers appended in just a few seconds or minutes.

The traditional response to this is to encourage users to use complex passwords containing random letters, numbers and symbols. Such passwords are impossible for the average person to remember, resulting in other serious problems such as passwords written on post-it notes or under the keyboard where even inexperienced attackers can find them.

There is a threat far more important than dictionary-based attacks, one that requires a serious response to the problem of LM hashes - rainbow tables. Putting it simply, rainbow tables are lists of pre-computed hashes for a selection of passwords, making the process of guessing a password very fast indeed. The downside of rainbow tables is size - the longer the password you are trying to guess, the larger the tables need to be. However, the rainbow tables for most combinations of upper case letters, numbers and symbols for a password up to 7-characters long are only 64 GB in size - quite easy to store on a portable hard disk or even a USB key. This means that it becomes feasible to “recover” the password from a LM hash in seconds, no matter how complex the original password.

For some time it has been possible to “switch off” the backwards compatibility in Windows, but most people don’t know that this is possible, or even that it’s important to do so. In any event, even an 8-character NTLM hash is vulnerable to a rainbow table attack, albeit a very large set of rainbow tables for the attacker to generate (or download) and use.

So what’s the solution? When Windows 2000 was launched, the maximum length of a Windows password was increased from 14 characters to 127. Of course, this remains true for Windows XP and Windows Server 2003. One interesting side effect is that a Windows password longer than 14 characters no longer has an LM hash and thus is invulnerable to any LM attacks. The other effect is surprising for many people - the password can in fact be seen as a passphrase and thus simple to remember! A passphrase such as “If I won the lottery I would buy a Ferrari” is very easy to remember and all but impossible to crack by any of today’s tools. So, providing that your PC is running Windows 2000 or XP or Vista, you are free to choose an easy-to-remember, effectively uncrackable password. Simple, eh?

If you've read this far, you may be wondering why Microsoft's Password Checker doesn't reflect this ... so am I.