Schneier on Security
A blog covering security and security technology.
« UK Spends Billions to Force Rail Terrorists to Drive a Little Further |
| Friday Squid Blogging: Four-Meter-Long Squid Caught in Brazil »
November 23, 2007
Using Google to Crack Hashed Passwords
...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.
Posted on November 23, 2007 at 6:07 AM
• 41 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
Why doesn't WordPress salt the hashes?
Hmm, if good passwords were chosen, it would be much harder to crack. For example, when using alphanumeric sequences for passwords.
"if good passwords were chosen, it would be much harder to crack"
I wish I got a cent every time I read that.
@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?
"does anybody know since when password salting is part of the Un*x password system?"
I found a paper by Morris and Thompson from 1978, which mentions salting, so it must have been before then:
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.
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:
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:
With a password "Anthony" without salting, it would have fell to a dictionary attack quickly anyway.
It's hard to think that such attack would break anything that a dictionary attack wouldn't.
The ancient problem of choosing good passwods...
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.
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.
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.
@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.
@ 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.
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?
DNS seems like the better approach to quickly searchable rainbow tables - low bandwidth, quick, simple... So for example have records like
both being CNAME records pointing to
dragonfrog: insert a few dots in there and you can distribute it across multiple servers much more easily:
@ 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".
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).
"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.
> 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):
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*
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/... 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 ;-)
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.
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...
@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.
Im missing something. Where did he get "Anthony" ? (yes I rtfa'd)
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.
While testing the methods mentioned here, I discovered this site:
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.)
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'
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:
It also appears all transactions are following redirect.
Domain Name: AKAMAI.NET
Registrar: TUCOWS INC.
OrgName: Asia Pacific Network Information Centre
NetRange: 188.8.131.52 - 184.108.40.206
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.
@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.
Is the Robert Morris from the "Password Security: A Case Study" the same one from the Morris worm?
@Anonymous: "Is the Robert Morris from the "Password Security: A Case Study" the same one from the Morris worm?"
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.
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.
This is especially frightening considering there are a variety of decent online MD5 crackers, reverse lookups, that would be capable of cracking MD5 hashes. I recently developed a site to help prove this point. http://www.netmd5crack.com
You can use Google to crack hashes, but a large amount of hashes can be found by other online databases that specialise in MD5 cracking, thats why i created my site at http://www.hashhack.com , It's an online md5 cracker with over 20 million hashes and counting. Its worth a look
Adam @ http://www.HashHack.Com - The Online MD5 Cracker
Schneier.com is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc.