What stupid linkbait. Cracking LM-hashed passwords is about as interesting as .1 + .2 != .3 in ieee754. Can we at least change the headline to something like "Newsflash: SSDs faster than spinning platters"?
Yes, the main problem with the article is that they never mention LM. The page they link to too. Only from the "14 characters" we get the idea that they crack LM hashes:
"To address the security weaknesses inherent in LM encryption, Microsoft introduced the NTLM algorithm with Windows NT 3.1."
That's 17 years old news, that LM is weak.
Still what most people unfamiliar with the topic don't know is that LM hashes of your passwords can still be present on your Windows machine, default "for compatibility reason."
For some posts the value might be the HN discussion following them, and not the post itself. And as usual when people whine about stuff they don't find interesting, all I have to say is: you < all HN users
The rainbow tables are an implementation of a form of time-memory tradeoff attack using a refined hash reduction algorithm based on the work of Martin Hellman (of Diffie-Hellman fame) - http://en.wikipedia.org/wiki/Rainbow_table
Basically Ophcrack uses optimised hash chains to speed things up. The precomputed hashes are generated with a specific character set. This works particularly well for unsalted algorithms that support limited character sets such as LM. LM splits the password into two on the 7 character boundary, capitalises it and only supports a subset of printable characters. Also it's unsalted, so while more computationally expensive than NTLM it's actually easier to crack. Rainbow tables for LM can be downloaded from freerainbowtables.net and are about 30-40Gb.
NTLM on the other hand supports unicode and very long password lengths. Most rainbow tables are mixalpha, or alphanumeric but short length. Our mixalphanum with symbols rainbow table set goes up to 14 characters and is about just under a terabyte. This is more difficult to put on SSDs cheaply.
Your best bet to protecting from rainbow tables is to use a character not referenced in commonly available sets in your password as you inevitably otherwise reach the limits of security vs usability with exceptionally long characters. As I use british keyboards, I generally recommend the £ symbol (British pound) or accent over a vowel. The Euro symbol is also good if you're staying in Europe.
Also, using a hash (such as bcrypt) that can be made arbitrarily expensive. With a cost of 14, it takes this computer four seconds of CPU time per attempt to hash each password. While merely annoying for one user, that would really slow down rainbow table creation.
You are correct. However, pursuant to the use of NTLM or LM, neither of which are salted non-US ASCII characters are about as good as you can get without ridiculously long passwords.
For anything else, ready salted is definitely the best crypto flavour.
Having said that, a few years ago I co-ordinated a distributed effort to create rainbow tables for standard Oracle database accounts. Oracle's crypto mechanism uses the username as a salt. It meant that we had to generate different (but small as the algorithm was crap) tables for DBSNMP,SYSTEM etc. The same applies to WPA-PSK - don't use a common SSID in the Church of Wifi tables.
I guess the moral of the story is that salting alone won't get you out of the woods. You need to think very carefully when it comes to crypto, and get as many second opinions as you can.
You say "definitely the best crypto flavor" as if you knew. But you don't, because no serious system designer cares about rainbow tables. Unix solved this problem in the nineteen seventies. Real system designers care about incremental crackers, of the sort used since the 1980's to harvest thousands of passwords from compromised Unix boxes, of the sort that forced Unix systems in the 1990's to adopt "shadowed" password files.
The solution to that threat, the real threat, is scrypt, bcrypt, or PBKDF2 --- the "adaptive" hashes that can be tuned to trade a marginal increase in defender cost for an untenable increase in attacker cost.
Are you saying that we should ignore rainbow tables? I appreciate that you know way more about crypto than I do, but I think you're working from the standpoint that people know how to do things the right way, as opposed to the real world situation where people very clearly don't (e.g. NTLM, Oracle being 'Unbreakable', iPhone screen lock security mechanisms).
For as long as there's people using unsalted MD5 hashes in their PHP applications, Rainbow Tables are a real threat.
> Unix solved [the problem of rainbow tables] in the nineteen seventies.
> incremental crackers [were used to] harvest thousands of passwords [and] forced Unix systems in the 1990's to adopt "shadowed" password files.
As someone who is interested in security but has not spent significant time studying it, I'd be interested to hear more about this. How did Unix solve the rainbow table issue? What is an incremental cracker and how does it relate to shadowed password files? (I'm familiar with the latter but not the former, and a Google search generates more noise than signal without more keywords to go on.)
The original Unix crypt(3) password scheme invented (and coined the term for) salts.
Incremental password crackers, like John the Ripper and Crack, take a single password hash, and an actual dictionary, and hash each entry in the dictionary looking for a match. They take days to run instead of seconds, and until people started wanting to break into Windows boxes, they were the only way people cracked passwords.
They don't take days to run. The other week I cracked around 16,000 LM hashes with EDPR in about 6 hours.
Incremental crackers have improved substantially over the past few years primarily due to the introduction of GPU programming (in some cases algorithms port easily, in other cases they need some work first to be optimal on a GPU), easier distributed programming and rainbow tables. There's some interesting projects that use GPU technology to optimise the rainbow table reduction function (see http://www.cryptohaze.com/ for an example). As GPU technology improves and as hardware becomes cheaper and more powerful these technologies bring capabilities previously limited to three-lettered agencies into the commercial and home space.
It's disabled by default on Vista and 7 (AFAIK, it was on my Windows 7 build, and I don't think that was me) but is enabled by default on Windows XP. You can find out how to disable it here: http://support.microsoft.com/kb/299656
I am not familiar with windows password scheme but it would be crazy if windows just relied on the hash. Few *nix machines that I deal with have 128 bit salt + password.
Even wifi-wpa, blackberry and iphones are doing password strengthening to make brute force method more challenging.
As most of us are familiar with, most vulnerable part of the security is us human beings picking the passwords. Underneath algorithms(hashing) are pretty well devised and solid when used properly.
If the salt is short (username, email address, phone number, user id, etc.) then this becomes much more of a serious attack, specifically if the salt+password combination is less than 14 characters.
What difference does it make? With a different salt for each password, that info is going to have to be stored in the database anyway, so does it matter much if its a random string or a piece of user info? They still have to precompute tables for each possible salt, unless you're using email as the salt and all your users happen to have the same email address.
Storing the dynamic salt in the same database together with the user's password hash still doesn't tell you HOW the salt is applied or HOW the product has been digested. This requires insight into the login procedure of the application, and this is where the strength of the salt lies. Adding on this security can be done by storing users' salts somewhere else instead of keeping them in the same table and db as the hashes.
My personal method is to work with two salts; one static half (just for the added entropy) kept with the login code, and one dynamic half (always random - not computed from user input) kept in a separate database, away from the hashes. This forces the attacker to acquire not just the database with the hashes, but also the database with the salts, AND the application's login code, in order to get anywhere.
This is silly. The purpose of a salt (what real cryptographers call a nonce) is simply to make it infeasible to precompute tables. Store it in the open, in the most convenient place possible; don't jump through hoops so you can pretend you're getting more security than you are.
If you really cared about the security of your passwords, you'd use scrypt, bcrypt, or PBKDF2, all of which are markedly more secure than "salted" anything.
Hmm... not quite. The word "salt" is always used in the context of KDFs. I'm not entirely certain how I'd define the difference between a salt and a nonce, but they feel like subtly different concepts to me.
If you really cared about the security of your passwords, you'd use scrypt, bcrypt, or PBKDF2, all of which are markedly more secure than "salted" anything.
Well, to be fair, scrypt, bcrypt, and PBKDF2 all use salts too. :-)
Let's be absolutely clear that it is not a clever new use of "salts" that makes PBKDF2, scrypt, or bcrypt more secure; the advantage is in adaptive hashing.
KDFs are a bit of a back-alley in crypto research, and that's the only place the term exists. The argument devolves to whether nonces really are a concept distinct from salts. I'd attempt to win the argument by citing nonces used in ways similar to salts in other crypto protocol settings (there are many).
If you look at PBKDF2, the only reason they call it a "salt" is because they're referring back to the original Unix work, where the term originated.
One way to slice this particular apple is to say that "salt" is a conventional systems design term, and nonce is a cryptosystems term.
This business of calling out "salt" vs. "nonce" as a crypto shibboleth though --- am I just being pedantic? No. Read generalist programmers writing about their idiosyncratic "salt" schemes --- "1/8th of the salt is stored on non-writeable media! 1/4th of it is encrypted with an AES key! 1/2 is stored in the database but XOR's against my mother's maiden name!" --- regardless of the three (3) papers you can cite by real security people using the term, in reality, people talking about "salts" are almost invariably distorting and tangling themselves up in silliness when they really ought to be taking PBKDF2 off the shelf and getting on with their lives.
KDFs are a bit of a back-alley in crypto research, and that's the only place the term exists.
The term 'salt' also appears in the definition of the PSS signing scheme. And in the HAIFA hash framework. And in some disk encryption schemes.
in reality, people talking about "salts" are almost invariably distorting and tangling themselves up in silliness when they really ought to be taking PBKDF2 off the shelf and getting on with their lives.
Sure. But I maintain that 'salt' is a good word whose reputation has been ruined by the idiots who use it, rather than being inherently a bad word. :-)
If they're really just using 80GB on the SSD (as the linked-to article suggests), why not just use a server with 128GB of RAM and avoid writing to disk altogether?
I'm not entirely sure which algorithm is used in WinXP for password hashing, but it might still be an LM hash, which has some security flaws. All lower-case characters are converted into upper case characters and the 14-byte password (cannot be longer) is divided into two 7-byte passwords, which can be cracked alone (sort of).
So, 300 billion passwords per second is still a very impressive load, but the keyspace for WinXP passwords is somewhat limited, which would also explain why 80 GB of rainbow tables are sufficient.
Microsoft developed NTLM because LM sucked and made it the default in Windows XP. However, for backwards compatibility, it also hashed the passwords to LM, so, well, you can crack them just as easily.
From Vista onwards, I think, LM is no longer used.
23GB of ram on EC2 is 1.60 an hour. Spin up 10 for $16.00. I think most hackers can afford that and it gives them enough computing power to match an 80GB SSD, I would say.
This is a perfect example of what can you do with RAM that is one order of magnitude bigger than what you can normally afford in regular computers.
It would be interesting to see if the effort that is spent writing programs to load stuff from disk and avoiding seeks gets redirected to solve other problems.
I believe it's not accidental that all passwords that they crack in the demo are 14 characters or less, that can mean that they attack the hashes which are always possible to crack, the speedup they claim is 100 (they simply increased tables from 8 GB to 80 GB and put them on SSD) but e.g. 1000 seconds before was also very fast for somebody who just needed to gain access to one target.
It's not accidental, because LM only supports passwords up to 14 chars. What's worse, is that they are two 7-character passwords, which you can crack separately, basically making cracking the entire LM keyspace trivial. I think there are rainbow tables that cover all of it (I have a few but they don't contain symbols, I don't think).
I thought the same thing. "With a big dictionary we can lookup easy passwords. With a bigger dictionary and a faster hard drive we can lookup complex passwords!" Is that all that's happening here or am I missing something?
Because saying something is "cracked" because it's in data-set A is worthless. The answer to your question is encoded in the technique of your choice in Pi. It's also because this "crack" is so ridiculously easily negated - salt your hashes. It's an amateur thing that everyone should be doing.
There's no cracking going on here, just short-cutted brute-force attacks.
Considering that most password are shorter than 14 characters, everyone implementing hashed passwords without a random salt could just store them as plain text. The rainbow table for the most common passwords (names, cities, pet names etc.) would fit in less than 1GB and would probably yield a very high success rate. There's no need to use complex passwords to prove that hashes without proper salting are bound to fail.
Can you give an example of what you meant? I understand variable length and random characters for each different accounts? (Sorry, I'm not a native English speaker).
Start with the assumption that the "bad guys" will have access to your entire database, and source code. From there, how do you protect the security of your users' passwords?
As computers get faster in every aspect the ability to crack naively implemented hashes grows greatly, to the point where, as we've seen, 14 character random passwords protected by a one way hash can be cracked in very little time.
Using a static salt across all accounts saves you a little, because it means that in order to crack those hashed passwords it will be necessary to re-do all the pre-computed hashes. That takes a lot of time and resources, but once done every vulnerable password (which today means any password less than 14 characters, no matter how secure) can be cracked.
By using a good per-account salt it then requires a brute force attack for every account. Which makes any requirements you've instated on minimum password "strength" all the more effective.
If, however, you use too short of a salt, or a silly "salt" such as phone number or userid or first name or some such then your salt becomes much less worthwhile. As pre-computed rainbow tables grow, as hardware gets faster eventually you get to the point where you can crack passwords along with naive salts quite readily. Phone number + 8 character password is just 18 characters, it's really only a matter of time before rainbow tables are capable of cracking 18 characters directly, and then using phone numbers as a "salt" is meaningless, because attackers can crack the password+salt directly.
What's better is to use a very long and random salt for each and every password (random length doesn't help that much). In this way any pre-computed hashes are worthless, because it's extraordinarily unlikely that any significant subset of all of the possible salt + password combinations have been covered.
The idea is to try to force Kerberos authentication only. I can't find any tips on forcing it explicitly (even through group policies) but perhaps there's a firewall method to disable any [NT]LM auth and only allow Kerberos auth. I think some specific services may only allow NTLM (such as Telnet) and some services (such as IIS) may have to explicitly be configured to use Kerberos.
(edit) I should mention that I am not an expert on configuring Windows domains or their authentication (obviously) but according to some random guy I asked in IRC, if the SPN is set on a calling ID for a given service, Kerberos will always be used (or attempted anyway) and enabling TCP instead of UDP for the communication may help it get through firewalls etc (and solve some other login-related problems with UDP attempts). However, I think NTLM is the only one that can get through all manner of proxies, firewalls, etc (for IIS for example).
BTW, don't confuse hashes with authentication protocols. There is no such thing as an "NTLMv2 hash". NTLMv2 is an authentication protocol, and NTLM and LM are authentication protocos too. There is the LM hash and the LM authentication protocol dependent on it, of which both is insecure, but are two different things.
The details are interesting (although completely obvious), but the article is really stupid, as it assumes everyone uses unsalted passwords and MD5 to create hashes. Duh.
This submission and frankly most of the comments on this HN thread are disturbing. There is a severe lack of understanding of NTLM and the purpose of even hashing, let alone salting, a password... strange.
