Also, I meant to link this earlier and forgot. A great summary of the Rainbow Crack in perspective with existing password cracking techniques:
Rainbow Crack – Not a New Street Drug
http://redmondmag.com/columns/print.asp?EditorialsID=736
If everyone had passwords like aywa%@ADWw^ysjrmpod!npmgs then who would care about salt?
We’d probably need aspirin from the headache of trying to remember our passwords, instead … 
I think that if your attacker has the ability to start admin/root processes you may as well give up
I think what we’re defending against here is the user/hashpass table getting remotely exposed-- certainly plausible. We are not defending against low-level, “run as root” type compromises.
Digital signiture’s work differently. A digital signature uses both public and private key’s to authenticate a message. Assymetric encryption uses two keys in relation to each other. So with a digital signature you make one key publicly available, and a second key you keep private. When you send an email (or anything you want signed) you take a hash of the message and encrypt it with your private key. Then when the recipient receives the message, they hash the message itself, and use your public key to decrypt the hash sent with the message. If they match the message is authentic. The idea being, if the message is altered in transit, whoever altered it won’t have the private key, and thus be unable to sign the message.
What I am suggesting is you use an encryption technique like your hashing function. Since something like an MD5 is an algorithm everyone uses, people can pre-compute every possible letter-number combination and it’s hashes. Then it becomes very easy to do a search based on the hash, and get a code that will generate the same hash. However, by using actual encryption, you get to dictate the key used for encryption, so pre-computation becomes impossible for this storage method.
This only leaves open a true crypto-analysis attack, where the attacker needs to try and compute your key based on a password they have injected and the results in the database. This is extremely hard (look at the RSA challenges posted above.) I don’t feel like looking it up, but it’s a magnitude of 4 or 5 years, and 60,000 computers to break a weak RSA key.
However, I think the true testimate, stop using administration practices that allow an attacked to take a copy of every username password. These databases should not be so easy to compromise. Stop throwing backup tapes in the garbage, or giving them away freely. Encryption is a stop gap measure, no encryption technology is designed to be fool proof, it is designed to keep information secure long enough, that when it is eventually broken, the information contained within is useless.
Wow:
http://blog.moertel.com/articles/2006/12/15/never-store-passwords-in-a-database
Reddit actually stored user passwords as plaintext in their DB, and part of the DB was exposed in December 2006.
The one excuse offered by a Reddit developer was “email me my password” functionality, which strikes me as pretty lame.
To Kevin Nisbet:
“Problem is, you need to use the same salt as before or no one will ever be able to log into your service.”
There is no problem. The salt that was originally used to hash the user’s password is stored in the user’s account record. (That’s why the comment in my example code says “store salt and hash in user record; throw out password.”) To authenticate a user, you simply grab the stored salt and use it to compute the hash of the newly supplied password. If that trial hash matches the stored hash, you know the supplied password was right. In sample code:
def is_password_right?(user_record, password)
trial_hash = md5(user_record.salt + password)
return (trial_hash == user_record.hash)
end
I want to make it clear that all of my comments, now and above, are meant to address the specific problem of offline dictionary attacks. That is, assuming that your user database will be stolen by an attacker, what can you do to make password discovery difficult? For this case, we’re not concerned about network traffic, only with what’s in the database.
Cheers. --Tom
The one excuse offered by a Reddit developer was “email me my password” functionality, which strikes me as pretty lame.
Indeed. Even if that was really wanted (instead of the usual new password procedure), they could store the passwords encrypted with a public key and use the corresponding private key only on the machine processing the password requests.
Regarding Kevin Nisbet’s more-recent comment:
“Since something like an MD5 is an algorithm everyone uses, people can pre-compute every possible letter-number combination and it’s hashes.”
They cannot pre-compute attack dictionaries if you combine each password with a randomly chosen salt, drawn from a massive salt space. The combined salt-password space becomes too large to generate dictionaries for. That’s the whole point of salting.
Cheers. --Tom
Can this be applied to the lattest/securest ways to encrypt passwords, like OpenBSD’s blowfish (or twofish)?
Sorry Tom Moertel,
I really must dispute the effectiveness of this technique. It is better than storing just the MD5, but I don’t think by much. The only advantage I see to this is you are extending the key length needed for precomputing hashes, which may be enough, but you also need to consider the long term viability of this system. How long will this be used, 5 years, 10 years?
It’s one of those, what happens when the cracker has the table, and the begining of every password just happens to begin with another column in your password table.
I would think that a highly improved version of this would be you atleast store the MD5(MD5(salt) + MD5(password)). This atleast means that you have a unique, semi pseudo salt, and the first pass of the rainbow table needs a key length of 64 characters. This process becomes even more efficient if you start muxing the hashes, say 3 characters from the salt, 3 from the password, then another 2 from salt, etc. But the question still poses, with the ease of which it is to break MD5 now, how will this system stand the test of time?
I can only assume you have this method in production, I’d be curious for you to try and submit it to Plain-text.info and see how long it takes them to break it. And also, at what level are you satisfied that as a worst case, the hacker has a botnet of computers at his disposal to run against your technique?
Basically, adding the salt you change the algorithm expected by the rainbow tables. But having a ‘secret’ algorithm is not the panacea either.
So what you need is a mathematically strong hashing algorithm (MD5) mixed with a secret algorithm.
I like using the username as salt but we should mix it in a way that is not plain-text readable after the rainbow attack.
Something like md5(f(username+password)) where f could be as simple as a XOR for example. Of course if this secret algorithm is not secret anymore, we are back to square one.
How about multiple salts?
Take the username, and md5 it. Append that. Next take the third byte of the username and the last byte of the entered password, and encrypt that too. If you want, you can use something else to encrypt that with. (I have no idea about md5 on something like that…)
Attach the first md5-username, then the entered password, then your encrypted second salt to the end. Using some obfuscation will also buy you time in the event that your source code is leaked. (It wouldn’t prevent the hacker, but it might make some of the lesser ones give up, and it’d at least slow down the better ones who’d need to take some time to reverse engineer what you did. The longer you have to realize that something was accessed that shouldn’t have been, the better your chances, in my opinion… just make sure it works right before you obfuscate!)
So, now we have an awful, complicated, nearly unguessable hash that we can still make when given a new password and the username without too much of a hassle.
Of course, I spend too long looking at the entries from the obfuscated C coding contest, so maybe my logic is off…
I guess I wasn’t clear in my last post: obviously you should encrypt after you’ve attached the parts…
“email me my password” functions are much better implemented as “email me a new password”. Thanks for this article, it will hopefully help my coworkers understand some of my code Although one problem with odd characters in passwords is password implementations that are broken for them (I use (alt-0176) or (alt-0174) sometimes because they’re easy to generate using the numeric keypad but have seen some funky errors in the past).
I’ve been a little surprised at how many websites are case-insensitive with passwords.
Actually, using a rainbow table would only make sense, if you could reuse it for more than one password.
So, even something as simple as MD5(username + password) would suffice (provided usernames are long enough, actually you would probably use something like MD5(MD5(username) + password) to make sure it addes enough length).
The reason for this is simply stated: A rainbow table is a simple brute-force attack which results are stored in a table. If you had to generate a new table for each username (and therefore for each password you intend to crack!) you could just ditch the table and do an oldfashioned brute force.
Another thing about salts: If someone recovers a given string “s” that allows MD5(s) == hash to be true, s is not necissarily the SAME string that was used to generate the hash in the first place!
Without using salts that would not be a problem (the remote mashine does not care at all, wether my cracked password is the same password that was originally used to create it’s hash), but since you probably (with extreme luck it could still happen) won’t get the original salt up front you cannot recover a password that generates this hash when the salt is added. The probability that a cracker recovers a “wrong” password from the hash increases with the length of the password…
For the sake of argument i now propose MD5(XOR(MD5(username), MD5(password))) - where MD5 can be replaced with any hashing algorithm of your choice, provided its hashs are long enough.
Need higher res background image!
It should probably be noted in this discussion that no salt will save you when it comes to Windows NT based passwords prior to Vista because they are limited length. As the post notes above, it’s basically a very insecure password system and is easily broken no matter what the password used is.
Regards
Fake
Are you guys retarded?
Salt does NOT protect you from rainbow table attacks and you don’t have to “create a rainbow table for every user”.
Just crack the salted hash, remove the salt, crack the remaining hash? Obviously this requires larger rainbow tables, but so do longer passwords.
The only thing a salt does is create two different salted hashes for the same password.
Also Ophcrack can’t crack “Fgpyyih804423” because it’s a weak password but because the hashing function is fucking useless.
Get a fucking clue, waste of time this blog.
There is no need to make the salt hidden information or use a particularly strong function for it (which is really a way of trying to hide the information).
For one thing, security by obscurity gets you nothing. Remember, people have to log in, possibly over an insecure medium. The way this has worked forever is that the server provides the salt and the client computes the hash of the salted password. The server then checks that against what it has.
In many scenarios, an eavesdropper can listen in and “steal” the salt. if you computed the salt with a hidden function, that computation would have to take place in the client for the client to pass a hashed, salted password back to the server. An attacker can open up a copy of the client software and presto! The salt calculation algorithm is there for the reading.
Random salts are the way to go. Their only purpose is to defeat dictionary attacks. Speaking of which, a Rainbow Table is a particular implementation of a Dictionary Attack. What a random salt does is make sure that you have to brute force any password you want to crack.
Nothing can make it harder than brute force calculating all the hashed values for (salt+password) strings up to a given length with a given character set.
Now about dictionary attacks. Say you have an incomplete dictionary, like just common words from an actual dictionary. Or let’s pick a really small dictionary, just words like “default” or “password” or “admin.”
Without any salt, you can generate hashes of your words and scan the database seeing if ANYONE has one of these passwords. In many cases, you don’t want a specific user cracked, just anyone.
With random salts, you must generate hashes containing every possible salt value for each of the words in your dictionary. The thing that adds security is the number of bits in the salt, not obfuscating the algorithm.
Per user salt: Store the lat time the user logged in, and append that to the password. Then the (stored, hashed and salty) password will change every time the user logs inn.
One thing though; the rainbow table is only useful if have access to the hashed password, right?