**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][1] for a some details.

The less-old NTLM is just [MD4][2] 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][3] 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][4] 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][5]). 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][6]. 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 _t<sup>2</sup>_ 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 2<sup>22</sup>); the corresponding CPU cost is down to about 2<sup>32</sup> 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 2<sup>67</sup>. 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 2<sup>77</sup> 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.)


  [1]: https://security.stackexchange.com/questions/2881/is-there-any-advantage-to-splitting-a-password/2883#2883
  [2]: http://tools.ietf.org/html/rfc1320
  [3]: http://exchangepedia.com/2007/01/what-is-the-real-maximum-password-length.html
  [4]: http://unicode.org/standard/WhatIsUnicode.html
  [5]: http://en.wikipedia.org/wiki/Dictionary_attack
  [6]: http://en.wikipedia.org/wiki/Rainbow_table