I wrote BozoCrack to show why plain MD5 is a horrible way to hash passwords.
github.com
github.com
1) many developers don't use salts / HMAC
2) MD5 is popular
3) hashed passwords end up on Google
Any hashing function would have the same issues, simply because a hashing function is a mathematical function, so for any X from the domain of definition, H(X) will always have the same value, on every call. Therefore, if a hashing method is popular enough and developers don't salt their hashes, then hashes for common passwords will inevitably end up on Google. However, if you salt your hash calls with your own key, the hashes produced will be different from everybody else's.
The solution is to pick a better algorithm and learn how to use it securely. That probably won't happen unless all the ridiculous PHP 'security' tutorials are erased from the history of the internet and only correct methods are shown.
This is the answer to this question. You should bookmark it and share it with your peers when this question inevitably comes up on another thread.
If using MD5 is all you do, you'd still be
susceptible to brute force attacks.
Otherwise, demonstrate to me how you can find the passwords that relate to these hashes (all of them use the same salt):
23C206503ABD36FCB575FC8F12791CF0
D82BDB4160F60B657D6F994B553D2E63
0DA0572E042F822F91772F14269548E6
CB8BF6C16029400885F9A68A17576FA7
7CE4F679810409CF1477CF142B481EF9
> MD5 is a really fast hash to compute, salting or not.
As I said, it should be easy cracking those hashes right? Prove me wrong.
This is not how discussions in this topic work.
So if you're assuming a salt that can contain standard latin letters and digits and is 256 in length, that's 62^256 possible variations.
Do note that I'm not saying here that MD5_HMAC doesn't have flaws, but it definitely doesn't have the same flaws as MD5, cracking it ain't easy and I can't find a reference for an instance in which this was actually done.
And yes, a huge secret salt will help. Of course, if your source code is ever visible to anyone you'll have to lock all accounts.
I really don't get this argument that since MD5 is fast to compute, that's the reason it is vulnerable. That's not true, MD5 is vulnerable for other reasons, like collision attacks are possible, preimage vulnerabilities were demonstrated, huge rainbow tables are precalculated and so on and so forth.
However, HMAC_MD5 does not have the same vulnerabilities and increasing the size of the salt increases the time of a brute force attack exponentially. 62^256 is a freakishly big number and it doesn't matter much if you divide the work by 100,000 computation units. But if that makes you feel uncomfortable, you can always increase the salt to 1000 chars.
And I simply don't buy that we have enough computation power in this world to brute force something with 62^1000 computational complexity.
That said, I don't know how you would obtain a list of hashed passwords without also getting the associated list of salts (wouldn't they be in the same database?), so it is kind of a moot point. The different salts are intended to prevent against the ability to have a single rainbow table to crack every password in the database.
Instead, you need a table for each salt, which means that you basically have to brute force the entire database. This still doesn't really help if you are using something fast like MD5, as brute force solution will be possible with that algorithm. Which is why you want something reasonably slow.
Normally you have a global salt, somewhere in your source-code, which you combine with the per-user generated salt. It also doesn't have to be something obvious in the database (like a column named user_salt :)), you could just use something like HMAC_MD5(global_salt, email + username + joined_date) for each user.
Of course, this may seem like security by obscurity, but even in the case of SSH you keep your private key safe and as a business if you have both your database and your source-code compromised, you're fucked anyway.
The purpose of the salt is to defeat time/space tradeoff attacks by inflating the required space to the point of impracticality. ie. 20 bits of salt will increase the size of the rainbow table required a million times.
but yes, a hashed (global + immutable-user-specific) combination seems to be best practice.
Ignoring that, if someone got your database, you should assume they got your code. If you care about passwords not being lost, you use bcrypt or something similar.
The one and _only_ use of a salt is to prevent precomputation attacks (rainbow tables).
I mean, yeah, you could also have a password for that key, but then most people use ssh-agent because typing that key every single time is annoying, which means the password is somewhere in memory. Or you could just install a keylogger on it and wait for the user to login.
If the user's computer is compromised, a hacker could gain access to his SSH credentials. Isn't that still security by obscurity?
And if you gain access to the source-code and to the database, I'm pretty sure you'll end up in a position to modify that source-code anyway, thus finding user passwords by simply logging them somewhere.
Security is a complex topic and relying on the slowness of an algorithm like bcrypt doesn't make me feel any safer, as people can always come up with a faster bcrypt. Instead we should rely on computational complexity, because no matter what we do, unless quantum computers become a realy, there are limits to what we can compute when exponential complexity is involved.
Not if you passphrase-protect it.
">But isn't the SSH private key also stored in plain text?
no, passwording the key encrypts it
>I mean, yeah, you could also have a password for that key, but then most people use ssh-agent because typing that key every single time is annoying, which means the password is somewhere in memory. Or you could just install a keylogger on it and wait for the user to login.
ssh-agent does not expose the private key to clients requesting it, thats part of its design, you can however get a login session to whatever hosts it holds keys for.
> Isn't that still security by obscurity?
That is much more involved than a hit and run attack where you download the DB, and much more likely to be detected/detectable before any harm is done, via such things as IDS, or just plain not possible due to how a system is locked down (stuff like ssh gateways that are heavily secured, etc).
>Instead we should rely on computational complexity ... there are limits to what we can compute when exponential complexity is involved.
the point of bcrypt isnt JUST that it is slow, its that each step requires the data from the previous step, many thousands of times over, that makes it impossible to parallelize across many GPU cores or similar arangements, thats a huge part of the weakness of stuff like plain hashing/salting, its trivial to parallelize and to scale up that parellelization till you are generating billions, or even trillions of hashes a second, that approch is totally useless on bcrypt."
Quantum computing does not help with exponential problems in general.
You use a salt so that time/space tradeoff attacks are no longer viable. All you need to do is provide a few bits (say 20) of entropy to make them infeasable.
"Huge" being the key word here.
Try searching for the md5sums of arbitrary 8-character alphanumeric passwords. You won't find many results. 62^8 is a big number.
The currently available databases are surprisingly large, even if not in the scale of 62^8. Consider a random pick from decrypt.fr: "phytostrote972". It's far from a random string, but not exactly a trivial one either.
A HD 5870 can churn through MD5s at about 2.8 billion/sec - 62^8 inside 24 hours on a single unremarkable GPU.
8-character alphanumeric are the ones that are being offered today, it's only going to go up as GPUs get better and HD space/bandwidth increases.
Hence the current advice is to use "alongpassphraseasyourpassword" rather than "L33$Pa55wd"
Why? Is it not being hashed? I have a (possibly very wrong) inkling that a longer phrase might increase the chance of collision but even so, so many places enforce a strong password but force you to keep it short.
You need a fairly expensive SAN to pull 1Billion MD5 hashes/second just from the raw disk - nevermind the DB lookup.
The vulnerability is "not using a password hash construction", of which the best known are bcrypt and PBKDF2.
You could slap MD5 into PBKDF2 with a high iteration count and achieve comparable security. The problem is that devs often use a hash function a single time.
Password hash constructions do more than simply run the hash function multiple times.
We are, obviously, saying much the same thing.
Again: the key point here is, don't DIY this part of your application.
If you don't have a reasonable salt then you're vulnerable to time/space tradeoff attacks like rainbow tables/etc.
Also, in case you haven't used it. Scrypt is pretty damn awesome. It's designed to be memory hard, which makes it very hard to crack even with GPUs.
There's always a lot of whining and complaining about how {crappyhash} algorithm is bad and how salts don't matter but not a lot a of {dothisinstead}.
(Yes, md5 is 128 bits and might be possible if an entire country dedicated itself to the effort. Or an attack on its flaws could be used. But both these points are tangential to themouth's use of infinite.)
It did however get a password that I use regularly (though not anymore) which I though was pretty complex.
So, friends with "idiot" passwords 1. Their so called computer-expert mate (me) 0.
I'm not so smug anymore.
We inherited a system, without inheriting the administrator passwords, that we had to work on. It was a spaghetti mess, so creating a new account didn't seem obvious, and I wasn't sure how the passwords were hashed, but they did seem md5-like to me, so I googled one.
Turns out, 90% of them, including most of the admin passwords, were just four numeric characters, like 9678.
What's actually wrong with bcrypt that prevents people from using it? Is it not available on all platforms? Too computationally expensive?
wordlist = response.split(/\s+/)
(If I had a dollar for every time the 'emailaddress+foo@gmail.com' failed to validate....)
Can we find these people and just let them know?
I use MD5 all the time, just not for security.
That means they're both md5-hashed on the wire and in the database.
http://blog.jgc.org/2009/05/can-you-trust-37signals-with-you...
http://stackoverflow.com/questions/1581610/how-can-i-store-m...
I think we need more code examples of how to do things right, because that code is very, very wrong.
Shock and horror when geeks meet the real-world. Yes, I know.
Bozo's idea was to show that unsalted MD5 is, for most passwords, as bad as no encryption at all. An attack doesn't get much easier than a lookup table.
See this script more as a fun little hack rather than a "Formal proof". Thanks aparadja for sharing. That being said, using MD5 without salt is asking for trouble. I mean, I know security is usually just a time vs $ vs quality problem, but it costs almost nothing more to add a salt in front of the password. Why not do it?
Using SHA256 with a salt is asking for trouble.
Use bcrypt, scrypt, or PBKDF2. Do not DIY your password hash.
If somebody got read-level access to your password hashes, it follows (based purely on the assumption that any app with the rights to read the hash will probably have the right to change it when applicable) that one could simply overwrite the password hash with a new one that is already known, gain unauthorized access, and change the hash back to prevent the user from finding out. Unless you really need that password to crack multiple accounts that might be reusing it, it seems unnecessary. (And honestly I wouldn't care to implement these special password hashes just to protect extraneous accounts of my customers which I don't control)
edit I should clarify that while I agree that expensive compute time for password hashes helps prevent the ultimate compromise of a user's password, I find it a much more worrisome prospect that somebody got access to the database in the first place. To me, a person's password strength is almost irrelevant compared to the importance of preventing brute-force attacks on a login API or ensuring the integrity of the password database and db apps.
That being said, for those wishing to implement a bcrypt-type hash:
perl -le'print crypt("something", "\$2a\$random")'
They protect the (majority of) users that re-use passwords on multiple services, and, more importantly, they protect you from the PR shitstorm of having dumps of cracked passwords posted to Pastebin after a compromise.
Also, a note to anyone reading the above post, that is not how bcrypt works and is incredibly insecure.
1. http://www.postgresql.org/docs/current/static/pgcrypto.html
For instance, I've got lots of password with over 20 characters mixed with upper/lower cases with a few symbols in it. (i.e. Seems hard but: phzb0xis@mynickname.on.hackernews.com is already pretty long and hard to crack but still easy for me to type/remember), btw that is not my password ;) I wonder if I encrypt that with MD5.. Could it be contained in a rainbow table somewhere?
Your search - 822d6c6e12b26dd30161967354aa4302 - did not match any documents.
Edit: I'm trying to illustrate the general principle, that you shouldn't take any action thats visible outside your secure perimeter, that depends on knowledge of your password.
What you define as 'outside the perimeter' depends. In the case of your corporate systems, its probably everything outside the corporate network. In the case of your gmail password, its everything outside of [your computer, the SSL connection to google's auth servers, and those servers].
You shouldn't ever leak any information outside that perimeter, that reveals knowledge of your password.
Its generally pretty hard to steal the password hash; if you start revealing what your password hash is to someone doing passive analysis, you compromise a lot.
If its worth thinking about poisoning hashes to protect, then don't try and poison the hashes!
The first result when I searched the hash for superman (84d961568a65073a3bcf0eb216b2a576) was a link to a page titled literally "Google Hash: md5(superman) = 84d961568a65073a3bcf0eb216b2a576", the page is hosted at(http://www.nth-dimension.org.uk/utils/ghash.php), basically someone's gone through the trouble of making a rainbow table that's easily crawlable that makes this method of lookup via Google even easier.
The page has a description:
> Google Hash is a PoC implementation of an hash search engine using Google.
> Unlike other implementations, the aim here is to get Google to store the
> word and associated hash. We do this by putting them into the title where it
> will always be stored by Google's spider....
(Source: http://codahale.com/how-to-safely-store-a-password/)