In all of this answer, I am considering the problem of recovering the password (or an equivalent password) from a purloined hash, as stored in a server on which the attacker could gain read access.
The NTLM hash is weak, but not as weak as the older LM hash.
The older LM hash includes several capital weaknesses:
- Not case-sensitive.
- Limited to 14 characters.
- Splits the password in two 7-character halves which are hashed separately.
This last weakness allows for very efficient cracking (regardless of the care taken in choosing the password); see this answer for a some details.
The less-old NTLM is just MD4 computed over the password. This time, the password is case sensitive, and can be quite long. There is some dispute as to the real maximum password length which could apparently be up to 127 characters or so. Since MD4 is computed over UTF-16 encoding of the password, the whole range of Unicode could theoretically be used, but since the user needs to type the password regularly (and without visual feedback), using characters beyond the printable ASCII set is looking for trouble.
What is weak in NTLM hash is that it is unsalted, and that MD4 is fast (MD4 is also cryptographically broken in several ways, but not for raw preimage resistance as is used for password hashing; for that, MD4 is as robust as it ever was). MD4 is actually faster than MD5. A recent GPU will compute several billions of MD4 instances per second. This makes it easy for the attacker to explore vast sets of potential passwords (what is known as a dictionary attack). The only defense is to choose your passwords from an even vaster set.
Let's throw some maths at it: since NTLM is unsalted, a dedicated group of attacker might find it worthwhile to build a big rainbow table. There are various possible optimizations, but, as a rule, things would go like this:
- There is a security parameter, called t; that's the average length of a chain in the rainbow table.
- If the set of passwords covered by the table has size N, then the storage requirements are about 10*N/t bytes (10 bytes per sorted chain end is a reasonable estimate).
- Building the table entails a cost of about 1.7*N hash function invocations.
- Attacking one password with the table entails computing about t2 times the hash function, and making t lookups in the table.
If the table is split over a hundred mechanical hard disks, then about 10000 lookups can be done per second. If the attacker is really motivated, he might wish to spend one hour or so per password, which means a maximum t of 3600000 for the lookups (let's say 222); the corresponding CPU cost is down to about 232 hashes per second, which is feasible with a couple recent GPU. The hundred disks allow for 300 TB storage (I am talking about 3 TB disk, which are off-the-shelf today), which brings the possible N to about 267. That's rather huge, but technologically feasible. Our group of attackers could buy a hundred GPU (and a big air conditioning unit) and be done with computing that table within a few months.
So, in order to defeat our motivated adversaries, we need to choose passwords at random from a set bigger than their N. If our set of possible passwords has size more than 277 and our passwords are chosen randomly and uniformly in that set (i.e. the password entropy is 77 bits or more), then the attacker has only 1/1000 chance of cracking a given password with his table. This ought to be sufficient to dissuade him.
How do we get 77 bits of entropy ? If we restrict ourselves to letters (uppercase and lowercase) and digits, so that the password can be typed on arbitrary keyboards, then we can have a little less than 6 bits of entropy per character. Therefore, 13 characters are sufficient. Isn't it swell ? Only 13 ! No need to go to huge passphrases. But mind the small type: that's 13 totally random letters or digits. No question of letting a human choose these characters, or even generating a dozen passwords of 13 characters and letting him choose the one he likes best. You take the generator, you produce one password, and you learn it. The mental effort is the price of using an unsalted fast password hashing mechanism like NTLM.
(Of course, the attacker group described above is realistic. You may want to increase complexity a bit, so that your passwords will also be strong with regards to tomorrow's attackers; so make it 14 or 15 characters to be safer.)