Using Google to Crack Hashed Passwords

Clever:

…I thought it would be interesting to find out the account password. WordPress stores raw MD5 hashes in the user database…. As with any respectable hash function, it is believed to be computationally infeasible to discover the input of MD5 from an output. Instead, someone would have to try out all possible inputs until the correct output is discovered.

[…]

Instead, I asked Google. I found, for example, a genealogy page listing people with the surname “Anthony”, and an advert for a house, signing off “Please Call for showing. Thank you, Anthony”. And indeed, the MD5 hash of “Anthony” was the database entry for the attacker. I had discovered his password.

Tags: , , , , ,

Posted on November 23, 2007 at 6:07 AM • 41 Comments

Comments

Merovingian • November 23, 2007 7:13 AM

Hmm, if good passwords were chosen, it would be much harder to crack. For example, when using alphanumeric sequences for passwords.

Anonymous • November 23, 2007 7:31 AM

“if good passwords were chosen, it would be much harder to crack”

I wish I got a cent every time I read that.

blue byte • November 23, 2007 7:44 AM

@Thomas: “Those who don’t know their history are doomed to repeat it.” This is what happens when amateurs design security elements of the software.
BTW, does anybody know since when password salting is part of the Un*x password system?

Zygmunt Lozinski • November 23, 2007 7:54 AM

The usual reference for salted passwords on Unix is:

Robert Morris. Password security: A case history. Computer Science Technical Report 71, Bell Laboratories, Murray Hill, NJ, April 1978.

Steven J. Murdoch • November 23, 2007 8:00 AM

@Thomas

I can only assume the WordPress developers either didn’t know or didn’t care about salting. Until I posted this to BugTraq, my report about the problem was ignored for over two years. Fortunately it looks like being resolved soon:
http://trac.wordpress.org/ticket/2394

What is worse is that you don’t even need to brute-force the password to break in. Again, this was ignored until I posted it to BugTraq and only now something is being done:
http://www.lightbluetouchpaper.org/2007/11/20/wordpress-cookie-authentication-vulnerability/

greg • November 23, 2007 8:48 AM

With a password “Anthony” without salting, it would have fell to a dictionary attack quickly anyway.

Marcos • November 23, 2007 10:18 AM

It’s hard to think that such attack would break anything that a dictionary attack wouldn’t.

The ancient problem of choosing good passwods…

John Ridley • November 23, 2007 10:20 AM

@greg:
If a password is going to fall to a dictionary attack, salting won’t help. All that salting does is to defeat pre-built hash tables. I certainly do it when I implement password systems, but it doesn’t defend against simple passwords in any way.

Chris • November 23, 2007 11:34 AM

@Zygmunt

While password salting was known in the late ’70s, it wasn’t widely implemented until much later. According to Cliff Stoll’s book The Cuckoo’s Egg, most systems were still vulnerable to offline dictionary attacks in 1986. Stoll was a Unix sysadmin and he didn’t even know about the possibility until Robert Morris told him about it.

Cairnarvon • November 23, 2007 12:27 PM

There are plenty of MD5 lookup databases on the internets. The most interesting bit in this story is what a security nightmare WordPress’ authentication system is. A quick Google search also found this.
I use WordPress myself. I’m beginning to regret that now.

Esurnir • November 23, 2007 1:30 PM

@Cairnarvon: And you know the funniest part ? Like google (see here http://www.tgdaily.com/content/view/34324/108/ ) that means that connecting to worldpress while in a public hotspot is giving away your cookies !

But don’t worry too much, the problem is that most “admin” website security are at least as “lax” as this. The only way to protect your website against attack is to secure the admin interface through ssl. Totaly, not just the auth prompt.

dragonfrog • November 23, 2007 2:30 PM

@ John Ridley

Salting has another benefit – it defeats massively parallel dictionary attacking – for a large password database, you have to calculate each hash, rather than calculate the hash once and just do a lookup.

David Donahue • November 23, 2007 4:15 PM

hmmm i wonder if it would be possible to create Google indexed web pages with hash values for dictionary plain texts for each salt value. It would be a huge set of static pages of course, but it would only have to be done once or does Salting truly defeat this class of attack?

If technique was valid it might be possible to leverage Google’s awesome indexing / database processing power to do your password cracking for you.

Or are the numbers just too large to create the required pages and convince Google to index them?

dragonfrog • November 23, 2007 5:51 PM

DNS seems like the better approach to quickly searchable rainbow tables – low bandwidth, quick, simple… So for example have records like

5f4dcc3b5aa765d61d8327deb882cf99.md5.rainbow.net

and

5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8.sha1.rainbow.net

both being CNAME records pointing to

password.plaintext.rainbow.net

Matthew Skala • November 23, 2007 7:46 PM

dragonfrog: insert a few dots in there and you can distribute it across multiple servers much more easily:

5baa.61e4.c9b9.3f3f.0682.250b.6cf8.331b.7ee6.8fd8.sha1.rainbow.net

scosol • November 24, 2007 1:47 AM

@ John Ridley

That’s not true at all- a proper salting setup will turn bad passwords in to good, and will reduce vulnerability down to the security of the salt information, and the predictability of the PRNG. If it’s not making sense, just think “per-instance random salt, combined randomly with supplied password”.

Zygmunt Lozinski • November 24, 2007 10:33 AM

@Chris

Interesting.

I’ve just gone back and checked the Seventh Edition Unix source for /usr/src/cmd/password.c, dated 10 Jan 1979, and it includes password salting. My guess it that various local maintainers / tuners of later Unix versions didn’t realize why the password salting was included and removed it. So I should check the BSD source tree (which is probably what Cliff Stoll was using).

SteveJ • November 24, 2007 11:17 AM

@scosol:

“a proper salting setup will turn bad passwords in to good, and will reduce vulnerability down to the security of the salt information”

How would the salt value have higher security than the hashed password?

If it’s stored on the server, then it’s just like the hashed password (indeed the salt is typically be stored along with the hashed password), and a bad password is still bad. Otherwise, the client has to provide it, in which case the password has been improved, but the extra random data isn’t “salt”, it’s part of the password.

Salt prevents pre-hashed dictionaries from being used to reduce the computation time of finding pre-images. It doesn’t do anything else. If your password is “password”, it will be brute-force cracked just as quickly, whether it’s salted or not, because you must assume that if the brute-forcer knows the hash of your password, then he knows the salt too.

Christoph Zurnieden • November 24, 2007 12:29 PM

a proper salting setup will turn bad passwords in to good

A proper password salting does a lot of good, but it doesn’t help much against dictionary attacks. It can slow them down if the salt is large enough, but only in O(n): if the salt has the same length as the password it may at most double the time to run a dictionary attack, if the salt has twice the length of the password, it may at most triple the time of the dictionary attack, and so on and so forth. You won’t even see any differences in runtime as long as the input is smaller than the input buffer of the hash function. You can try it yourself (tested on an older Debian installation):

#!/bin/sh
echo without salt;
time for i in cat /usr/share/dict/words; do echo $i|md5sum>/dev/null ;done
echo with the word as the salt;
time for i in cat /usr/share/dict/words; do echo $i$i|md5sum>/dev/null ;done
echo with 4 words as the salt;
time for i in cat /usr/share/dict/words; do echo $i$i$i$i$i|md5sum>/dev/null ;done
echo with 8 words as the salt;
time for i in cat /usr/share/dict/words; do echo $i$i$i$i$i$i$i$i$i|md5sum>/dev/null ;done
echo with 16 words as the salt;
time for i in cat /usr/share/dict/words; do echo $i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i|md5sum>/dev/null ;done
echo with 32 words as the salt;
time for i in cat /usr/share/dict/words; do echo $i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i$i|md5sum>/dev/null ;done

My dictionary has ~45,000 entries and the first two lines run in less than three minutes each on a single processor 1 Ghz machine. A modern multiprocessor/-core machine (depends if the hashing algorithm used is parallelizable and MD5 is) can run a dictionary attack with the help of a modest cracking dictionary of 3mio entries in less than 1 hour. That’s a very small time window to detect that /etc/shadow has been copied and to shut down that machine, isn’t it?
(see also: http://www.securityfocus.com/blogs/262)

The problems are the passwords itself, they shouldn’t ever leave the hands of the owner. The most obvious solution would be to use asymmetric encryption: key exchange -> sign a nonce -> encrypt it -> exchange&validate signature. It’s a kind of an extended HMAC (signing a nonce instead of a one-way hash) over SSL (encrypt it before exchanging). It is also obvious that this idea has a lot of pitfalls and other more practical drawbacks.
Oh, and it may be obvious to you and me, but not to the US-patent office, they happily patented a subset of that protocol (http://srp.stanford.edu/design.html, would need an extra level of SSL or similar to authenticate the authenticator). sigh

CZ

PS: Thomas Ptacek mentions that the design (including a salt) of Unix’ crypt(3) dates back to 1976 and cites http://www.usenix.org/events/usenix99/provos/provos_html/node9.html which itself cites
Robert Morris and Ken Thompson.
Password Security: A Case History.
Communications of the ACM, 22(11):594-597, November 1979.
I found a copy of that paper at http://cm.bell-labs.com/cm/cs/who/dmr/passwd.ps but didn’t find that number there, forgot who lent my copy of Wilkes’ “Time-sharing computer systems” and am not too old to have better things to do at a saturday evening 😉

CZ

Kadin2048 • November 24, 2007 12:33 PM

An interesting attack to be sure, but basically you’re just using Google as a library of prebuilt hash tables. This is a well-known attack vector, mitigated through the use of salts, as others have pointed out.

And if they weren’t using salts, then anyone could just generate a hash table on their local machine, and probably have a lot more of them than Google has in short order. (I suspect there are probably dictionaries around that have the MD5 hashes precomputed…I’ve never looked but it’s hard not to believe it’s been done already.) Google may have made it brainlessly trivial, but real attackers have been able to do this for a long, long time.

It’s just unfortunate that the WordPress developers didn’t decide to incorporate this into their software before an issue from 1978 came and bit them in the rear end.

Just another example of why you should try to be proactive instead of reactive, I suppose.

Dave • November 24, 2007 3:13 PM

Just thinking about the suggestion of putting every possible plaintext password on individual pages and letting Google index them, it would be rather interesting to see what pageranks certain pages ended up getting.

Traffic analysis of those pages could lead you to surmise interesting things about certain common passwords…

Paeniteo • November 26, 2007 3:20 AM

@Christoph Zurnieden: “A proper password salting does a lot of good, but it doesn’t help much against dictionary attacks. It can slow them down if the salt is large enough,”

It depends upon what salting you do. If it is a fixed value for the whole user database, you can run your dictionary attack against the whole database. This would just make pre-calculated rainbow tables useless.

If you use a per-user salt (say, the username, or the timestamp of the last password change), you will have to repeat the dictionary attack for every user account, which significantly reduces the success rate / speed.

antibozo • November 26, 2007 11:14 AM

Paeniteo> If you use a per-user salt (say, the username, or the timestamp of the last password change), you will have to repeat the dictionary attack for every user account, which significantly reduces the success rate / speed.

And in the case where you’re trying to crack a single password, this makes no difference at all.

Morgul • November 26, 2007 1:51 PM

While testing the methods mentioned here, I discovered this site:

http://www.md5oogle.com

It seems to make doing the google lookup much easier. I’ve tried it for several dictionary words, and it seems to work as well as the google method. (Except, it simply returns the word, not several search hits like google.)

Morgul • November 26, 2007 2:19 PM

@ bob

When you enter the md5 hash into google, you get search results that contain the word that generated that hash. Simply, you take the most commonly occuring word, and try that. That’s how he got ‘Anthony’

Anonymous • November 26, 2007 3:35 PM

I am only reporting this here as I assume you know who to send this info to:

Right now (started 11-26-07 11:30am CST)

Walmart.com is being redirected to:
http://a248.e.akamai.net/f/248/16813/7d/www.walmart.com

It also appears all transactions are following redirect.

Domain Name: AKAMAI.NET
218.57.11.112

Registrar: TUCOWS INC.
OrgName: Asia Pacific Network Information Centre
ReferralServer: whois://whois.apnic.net
NetRange: 218.0.0.0 – 218.255.255.255
CIDR: 218.0.0.0/8
NetName: APNIC4
NetHandle: NET-218-0-0-0-1

If my sites had all there traffic phished … I would “pull it”.

As of right now, wal-mart is not.

Is this a verified Hack?

When you “goole” “http://a248.e.akamai.net”

Results show similar sites that are phished.

I am hoping this is just a hosting company that is “very poor” at redirects and not a MAJOR phishing scam.

Christoph Zurnieden • November 26, 2007 6:33 PM

@Paeniteo If you use a per-user salt (say, the username, or the timestamp of the last password change), you will have to repeat the dictionary attack for every user account, which significantly reduces the success rate / speed.

The problem lies in “significantly”. The speed of a FPGA or moreso a piece of native hardware (100 or more for the price of a fast FPGA) dedicated to do the MD5/SHA hashing is very high. It is so high that it doesn’t matter much if you want a dictionary attack on one or on 100 passwords, the difference in runtime is neglectable.
And if you don’t want to spend money on it, just use your small 100.000 node botnet.

No, a salt doesn’t help against bad passwords, so don’t let a human choose a password.

CZ

Anonymous • November 29, 2007 6:34 AM

Is the Robert Morris from the “Password Security: A Case Study” the same one from the Morris worm?

Terry Cloth • November 29, 2007 5:20 PM

@Anonymous: “Is the Robert Morris from the “Password Security: A Case Study” the same one from the Morris worm?”

His father.

steve • December 26, 2007 12:01 PM

I think my girlfriend of 2 years is cheating she is on her emails all the time how can I crack her password ? She lives 100 miles away I know her secret email but not her password. I just want piece of mind, can you help or recomend a software package to buy.

Thanks for your help.

Ste

gajanan • January 29, 2008 3:30 AM

think my girlfriend of 2 years is cheating she is on her emails all the time how can I crack her password ? She lives 100 miles away I know her secret email but not her password. I just want piece of mind, can you help or recomend a software package to buy.

Thanks for your help.

sam

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.