I recently came across a number of sources that suggest that cracking Windows user account passwords is easy by examining their password hashes.
I understand that these hashes are stored in the SAM file in two formats: LM and NTLM. LM is unsecure (and since Vista, a meaningful one isn’t stored, right?). However, NTLM is also cryptographically weak, and can also be broken disturbingly quickly.
In any case, even with what I would consider “strong” passwords, I have seen them cracked in a matter of a few minutes–simply by rebooting the computer into Linux from a flash drive, and then running a program that extracts passwords from the hashes. This seems to me to be a huge vulnerability.
About the only thing I was able to find online about preventing this was to use a longer password, so as to guarantee that the weaker LM hash isn’t meaningful–but NTLM is still weak.
Anyone know how to protect against these sort of attacks?
There’s a few things to consider here. Three algorithms have been used by Microsoft for the accounts database on windows systems:
LM (LAN Manager)
NTLM (NT LAN Manager)
NTLMv2 (NT LAN Manager version 2)
V2 is the current standard in the more recent versions of the operating system. An attacker with physical access to your system can pretty easily dump the contents of the SAM (Security Accounts Manager) database for all local accounts and then use something like Ophcrack (http://ophcrack.sourceforge.net ) to run rainbow table attacks against the hashed values.
However, you need determine what the actual risk is: the attacker is able to crack the password and/or the attacker is able to access the system. This is important because it’s not necessary to crack the password (guess it’s value) in order to compromise the system. Many other tools simply replace the hash in the SAM database with something chosen by the attacker. This compromises the system, but not necessarily the password itself. Whole disk encryption solves both problems as a first line of defense: your attacker is unable to mount the volume in whatever tool they’re using to muck around in the SAM database. If you go this route a lot of commercial vendors offer solutions. Truecrypt (http://www.truecrypt.org/) offers a superb free program. Bitlocker or any OS-integrated encryption solution is pretty much worthless since they are readily susceptible to cold boot attacks.
One of the newer solutions are self-encrypting drives that require a boot into their own firmware for access.
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 severalbillions 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 about10*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 Nto 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.)