Using Google To Crack MD5 Passwords

stern writes "A security researcher at Cambridge was trying to figure out the password used by somebody who had hacked his Web site. He tried running a dictionary through the encryption hash function; no dice. Then he pasted the hacker's encrypted password into Google, and voila — there was his answer. Conclusion? Use no password that any other human being has ever used, or is ever likely to use, for any purpose. I think."

Comments

Salt

[porneL]

No, the conclusion is you should always use salted hashes.

Re:Salt

[networkBoy]

Not entirely.
That adds a "local salt" but... courtesy of possible hash collisions there is another password that may work equally well.
by having the login function add the salt a straight rainbow lookup is defeated (unless you pre-computed a rainbow with the salt). As admin he could still enter the salted MD5, find a suitable password without salt, disable salting, get in enable salting, change the password. BUT a "normal" hacker without access to the DB tools and salting function of the app, but in possession of the hash table (and even the salt to some extent) would be defeated. if the attacker had the salt and hash table then with enough time the will break you login through rainbow tables, but not before.
-nB

Re:Salt

[AKAImBatman]

Better solution:

http://passwordmaker.sourceforge.net/passwordmaker.html

One password for all sites, but a unqiue, "fscking crazy" password for all of them. You're welcome.

Re:Salt

[Garridan]

Because if somebody gets that file, they've got your password. This way, they'll have to hack your brain, as well as your computer, to get at your password.

Re:Salt

[Sangui5]

You're implying that salting on UNIX makes attacking the hash infeasible, this is simply not true.
Salting doesn't make breaking hashes infeasible, but it makes the attacker work harder, and makes certain highly efficient attacks infeasible.

There are only 4096 different combinations in the salting algorithm in crypt() will use which a brute forcer can easily iterate.
And I completely agree that 12 bits of salt is insufficient in a modern world. Which is why MacOS 10.4 and up uses 32 bits of salt, most Linux implementations use 48 bits of salt, and OpenBSD uses (a rather paranoid) 128 bits. Since it doesn't require any more effort from the user, and only a tiny amount of resources, there's no reason not to use a large salt.

Salting a known algorithm is almost pointless because as I just described salted passwords can be just as easily defeated if you know the mechanism
If you have the password hashes they you have the salt too. Either way, brute forcing one password is no harder. But it means you have to work harder to do a whole list of passwords, because each password has to be attacked individually.

Salting also makes precomputation (pre-built dictionaries and rainbow tables) infeasible. Every bit of salt in essence doubles the amount of storage for your precomputation attack. This is (partly) why a fairly effective set of rainbow tables for LANMAN hashes take only 500ish MB, NTLM hashes take 8.5 GB, but even for the old Unix crypt() it would take at least 2 TB. And don't even think about trying any precomputation attacks against OpenBSD; even if the user was stupid and restricted themselves to 5 digit alphanumeric passwords, your rainbow table would consume more storage than exists. Salting makes you attack each password individually, and keeps you from doing any work ahead of time.

this is why NT doesn't include salt.
NTLM doesn't include a salt because (1) MS is trying to maintain a semblance of backwards compatibility with some ill-designed challenge response authentication mechanisms, and (2) they haven't learned the lesson that salting is a valuable strategy to make attacking hashes more difficult.

Also salt was used on UNIX only because when shadow passwords didn't exist the system had to be protected against users that had the same password and could easily read the password file to compare.
That is one reason why salts were used for old Unix crypt(). The other was to make precomputed dictionary attacks harder, which is still a valid use. Today, the best reason to use a salted hash is to avoid rainbow tables.

Really, the modern reason to use a salt is to prevent the type of attack the original poster used, and to prevent rainbow table attacks. Both of these are good attack techniques, and salting completely moots them.

Re:Salt

[Sangui5]

You are correct that salting does not prevent nor make harder a brute force attack against one password.

It *does* breaks the Google attack, a precomputed dictionary, and rainbow tables, *even* if the attacker just wants *your* password.

Of these, rainbow tables is by far the most effective. Nobody computes their own rainbow tables. If I want to attack your hashed password, I'll download or buy a set of rainbow tables. Salting prevents this, because every salt value needs its own set of rainbow tables (or you have to include the salt rainbow table entries, which is approximately the same). Either way, using a 32-bit salt implies that to be equally effective, the total set of tables has to be 4 billion times larger. A 128 bit salt; well, you just can't create a set of rainbow tables for that. It just demolishes their effectiveness.

As you imply, there is a variant on salting which even makes plain brute forcing harder: don't store all of the salt. Of course this is (1) not widely deployed, and (2) imposes a high cost for legitimate use. Anyway, using repeated hash iterations is better, since you can't parallelize it.

MD5 Lookup Site & Names

[eldavojohn]

For those of you who missed it in the article, the has was:

20f1aeb7819d7858684c898d1e98c1bb And sure enough, if you read the comments to the blog, there is a site called http://md5.rednoize.com/ that reveals that the hash is "Anthony." So although Google helped, there appears to be resources online for it (if you don't have your own Rainbow Table mega database).

He could have discovered this if he had used a database complete with names, something I don't think would have been too difficult for him.

This Google search idea is kind of moot if the user uses some very basic password construction such as what I've commented on before. Also, as the blog mentions, this discussion is worthless if WordPress used salting which is related to nonces used in security engineering. I think that stuff has been around for, what about five years now? Wake up WordPress!

Re:MD5 Lookup Site & Names

[Ossifer]

md5oogle.com (http://md5oogle.com) is what you want...

I wouldn't be too alarmed.

[morgan_greywolf]

Most MD5 password hashes, such as those used in *nix, are salted, and hence secure from this sort of vulnerability. That Wordpress uses unsalted MD5 sums to store passwords boggles my mind. It shows that the developers know even less about cryptography than I do. That's scary.

Re:Don't panic!

[roguetrick]

You never have used rainbow tables have you? You're in for a rude awakening.

5 years?

[Junta]

Try decades! The good old days of Unix even had salts (even if they were just two bytes)

Been there. Done that.

[this great guy]

I have personally been using Google this way for a while. This is the first thing I do when I encounter a passwd hash during a pentest. This is a technique that works very well especially for hashes produced by random apps that you have no idea what hashing algorithm they use. It works well not because the public passwd hash databases indexed by Google are large (they are not), but because they are very diverse, both in term of number of algorithms (MD5(), MD5(uppercase()), SHA1(), etc) and in terms of number of hash formats (hexadecimal value, decimal value, base64, etc).

And above all, it only takes 2 sec to perform the Google search.

"Not quite right" to parent and grandparent

[abb3w]

Admittedly, both salting and complex passwords increase the size of the database involved. However, there's no reason one couldn't generate those databases as well. In fact, one of the Google results is for an on-line Password hash database. So, all a group of hackers has to do is put the thing online in some manner of distributed storage, and wait for Google to index all the pages for 'em.

Fortunately, the problem grows exponentially with the number of allowable characters. Unfortunately, so does Google's headaches. I suspect Google will take some "don't be evil" measures on this shortly, if only to keep their Data Storage department from needing to give Earth a second moon....

Credibility?

[MarkLewis]

Am I the only one who thinks that a "security researcher" whose site gets hacked and is about as credible as an accountant who fails an audit?

And for his sake I really hope that he knew about rainbow tables and just decided for some indecipherable reason not to mention that they are far more effective for password cracking than Google searches.

And who submitted this story to Slashdot with the sensational summary about "any password used by anybody, ever" being vulnerable to Google searches? That's an easy enough claim to completely debunk by taking MD5 hashes of several passwords and sampling which ones come back. Let's see:

92259762923b4e79d2073ecb03217462 (hash for 'july2007') - Nothing
6e933f3054f533c63dd59479ca9f4b6f (hash for 'hello_world') - Nothing
2c6c8ab6ba8b9c98a1939450eb4089ed (hash for 'abc123') - Google found this one as an md5 example
6a51f1fe97bdebece7652842a0e2351e (hash for 'pickles') - Nothing
5eaaf94141c371ce96675aa6445003c4 (hash for 'happy') - Nothing

So basically not even common words get picked up by Google, much less "any password used by anybody else, ever".

Re:Credibility?

[dgym]

Your strings have newlines in them, maybe you meant:
echo -n happy | md5sum

most password fields don't accept newlines, so trying without them:
3e652df0f1332cfc9df779d49667defc - still nothing
99b1ff8f11781541f7f89f9bd41c4a17 - still nothing
e99a18c428cb38d5f260853678922e03 - abc123
fd03204cfdc557b0f0d134773ae6fff5 - obscure, it finds a flash app on a site called pickles and things
56ab24c15b72a457069c5ea42fcfc640 - happy

So it is still not that much of a problem, but at least happy is on the list.
I wonder if negative outlook words are more or less secure?

Re:Credibility?

[etinin]

Perhaps it's due to Slashdot, but all of the hashes you generated are present on http://md5.rednoize.com/, so the previous claim that hashes of common words don't exist in the internet might not be quite true.

Hash DBs have been around for years.

[smitth1276]

Like GData. That has been around since the summer of 2005.