Am I missing something here, or would you also want your salt to contain special characters so that they wouldn't even be able to get the salted password with the smaller rainbow hashes? In other words, use "[more salt?]" as the prefix and perhaps "{booya!}" as a suffix ...

In case anyone is interested, here's how long it takes to generate a basic Rainbow Table on a modern spec PC:

--
rtgen lm alpha-numeric 1 7 0 2400 40000000 all

hash: LM, 8 chars, [A-Z0-9] = space 80,603,140,212
--

I'm getting about 110 seconds per every 100,000 hash values generated. The table size is 40,000,000 so total generation time will be 400 * 110 sec = 12.2 hours.

rtgen is definitely not multithreaded, so you might be able to run two (or more) instances on multicore machine and increase throughput, also.

Of course, if they happen to have physical access to your machine, no password could protect you from someone taking your HDD. I guess that's why you put servers under lock and key, huh?

Actually, the salt should depend on the user, like the hash being md5(password,md5(username)), so that a separate table is needed for each user.

/etc/passwd used a random salt (of just 12 bits) stored along with the hash, but that was primarily to avoid people with the same cleartext password have the same hash. /etc/passwd was world-readable (and still is, but it doesn't contain password hashed anymore).

Tom, that's true. The letter "a" would be a bad salt. the salt should be somewhat long and full of unusual characters for best effect.

It's also possible to use random per-row salts, as mentioned in the wikipedia article on Salt..

http://en.wikipedia.org/wiki/Salt_(cryptography)

I'm unclear how you can use a "random" salt for each password without storing it in the very same table row as the resulting hashed value, which seems to render the benefit of a salt moot to me.. I always thought of salt as a per-server secret.

Jeff Says: I'm unclear how you can use a "random" salt for each password without storing it in the very same table row as the resulting hashed value, which seems to render the benefit of a salt moot to me.. I always thought of salt as a per-server secret.

Yes, that is exactly what you do. Having a salt with ENTIRELY RANDOM makes it infeasable that the rainbow table attack would work. A static salt like "bob" or the username I can't see doing that.

If you read through the first Q/A of this there are more implementation details:
http://msdn.microsoft.com/msdnmag/issues/03/08/SecurityBriefs/

The code of figure 2 [the SaltedHash class] shows doing exactly what you said, storing the salt with the hash. Then to check that the password the user enters match

SHA1(stored salt, user entered password) == stored hash

When the user changes thieir password there isn't much reason to avoid changing the salt too [darn, that's another 20 bytes of writing sql server has to do...].

I'm afraid I somewhat missed the point. Wouldn't the rainbow table include also the hash of "deliciously-salty-password"? Sure, in this case you come up with a password that is not the actual password, but recovering the correct one should prove pretty easy: just try and remove some of the leading or trailing characters.
And, if you use a per-server salt, you could just find the salted passwords for two users and compare them to recover the salt.
Am I wrong?

gah, the above should've been:
SHA1(stored salt + user entered password) == stored hash

also I just ran across this, but it's in the evil VB:
http://channel9.msdn.com/wiki/default.aspx/SecurityWiki.SaltedHashCode2

@John Woodword > +1 Same for me, I don't get this salt thing ;)

John Said: And, if you use a per-server salt, you could just find the salted passwords for two users and compare them to recover the salt.

... You could, but I [as a hacker] would rather find which users have the same password, which would mean the same hash [but only if all users have the same salt].

[Though by the time I have the password hashes I could would probably have reasonable enough contact information to ask the users for thier passwords myself. I could offer them chocolate, or call in saying I was their IT guy and I need to do change a setting in their account or any number of other things. Jeff: You should get read "The Art of Deception: Controlling the Human Element of Security"]

Wouldn't the salt just be a human-readable post-fix on every single entry? Then all you'd need to do is compare 2 strings from the right until string[length-n] != string2[length-n], remove n chars from each hash, then compare with the rainbow table?

Seems like a once off cost of computing the post-fix, and a per-hash cost of removing the post-fix.

Or am I wrong?

Jeff, as far as I know, per-user salting would result in hacker's need to generate different rainbow tables for every user, as opposed to generating one rainbow table for database with known salt.

John: salt adds its length to the password, so if you make 14 characters long salt and hacker doesn't know it, those 64GB rainbow tables wouldn't decipher even one letter password.
If he does, he needs to generate rainbow tables tailored to the salt (a minor annoyance, I guess).

Jeff, what would be your solution to this problem?

If a hacker manager to get a chunk of my database passwords hashes, how hard would it be for him to get the salt password (function)?
the function have to be static, that's the whole point.
1. if it's hard coded, just putting the hand on the code is enough (and secret code is not my idea about good security).
2. if it's somehow "dynamic" (per application instance), the application itself need to be able to figure it out - so it will be available somehow to the running code. again - not very strong.

I think if a hacker got his/her hands on the passwords hashes we are already in deep shit.

From the wikipedia article (http://en.wikipedia.org/wiki/Salt_%28cryptography%29):

"Salts also help protect against rainbow tables as they, in effect, extend the length and potentially the complexity of the password. If the rainbow tables do not have passwords matching the length (e.g. 8 bytes password, and 2 bytes salt, is effectively a 10 byte password) and complexity (non-alphanumeric salt increases the complexity of strictly alphanumeric passwords) of the salted password, then the password will not be found. If found, one will have to remove the salt from the password before it can be used."

In the context of extending the length of the stored hash and preventing the obviousness of two identical passwords using a unique hash for each password can be done simply, as previously suggested, by appending the hash of the username or other such related constant.

> as previously suggested, by appending the hash of the username or other such related constant

You want hashes to be a prefix, not a suffix.

This makes sense. If an attacker obtained our passwords table, s/he would have no way of knowing that the salt "formula" is to hash the username and use that as a prefix for the password. Nor would s/he know the hash function we used for the username, either.

Those salting secrets are kept in the code, as Omry noted above. So the hacker would need the user/hashpass table *and* the code to attack the hashes with any hope of success.

> Jeff, as far as I know, per-user salting would result in hacker's need to generate different rainbow tables for every user.

Oh, right. The fact that the salt and the hash are plainly visible isn't a problem, because the attacker still has to generate (# of users) rainbow tables instead of a *single* rainbow table for the entire lot.

I still like the idea of hiding the salt "formula" in code rather than putting it in plain sight next to the hashed password -- that way, the attacker can't generate *any* rainbow tables at all unless they've managed to obtain both the user/hashpass table and the code itself.

Makes sense, thanks for adding that. I'm relatively new to cryptography.

I don't think you need a different rainbow table just because of a salt. Assuming you have a rainbow table that can recover [password] and [salted password] a rainbow attack will sort of work; the attacker would have to guess what salt has been added to your password.

If you're using a salt like aywa%@ADWw^ysj&&rmpod!npmgs then it becomes very difficult to generate a generalized rainbow table that can crack your password hashes...which now that I think about it is what people have meant.

So a salt is for making a password stronger. If everyone had passwords like aywa%@ADWw^ysj&&rmpod!npmgs then who would care about salt? :)

On a related note, if your attacker knows your salt (or how it's generated) then it's not very effective. One could sort of alleviate this by basing the salt on privileged information which would only be available to processes with elevated credentials (I don't know off the top of my head whether there's anything per-user that only admin/root accounts can access.) I think that if your attacker has the ability to start admin/root processes you may as well give up. :)

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^ysj&&rmpod!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.

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.

http://reddit.com/info/usqe/comments/cuugl

> 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.

Can this be applied to the lattest/securest ways to encrypt passwords, like OpenBSD's blowfish (or twofish)?

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.

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?

Obviously salt doesn't protect you against rainbow tables (because rainbow tables are just memoized brute-forcing), but sufficient salting makes the attack infeasible. No-one has 100-character tables.

Where do I download that desktop background?

^.^

Actually the way you demonstrated on your blog would be a rather bad way of salting your passwords. When the password is broken by the rainbow crack deliciously-salty-{x} will show up in every password. What was offered in an above comment is a much better and more discouraging way of the MD5('deliciously-salty-' + MD5(password));

Now here's the thing, the real pro's don't need your fancy CD's and lots of memory to break an NTLM hash. That's already available on an "advanced distributed cracking system". Check out plain-text.info. And learn to crack an MD5 hash in under a second.

Now I would still consider your proposed method a bad way of storing password all together. Why should we store password hashed with common algorithm such as sha1, md5, and ntlm.

What I much prefer is using a modern asymetric encryption algorythm. Generate yourself a Public / Private Key, throw out the private key, and you've got yourself your very own encrypted password storage. Worried about password being the same, then you properly use the salt (or md5) of the users username against the password before encrypting.

Really really worried, then you generate a private key for each user, which get's stored seperately. Imagine the computing power needed to break that system with solely one piece of the picture. Then again, if you spend so much time designing password systems... don't forget to design suitable software that uses them ;)

As others have mentioned, salts have essentially two functions: 1) See to it that two users with the same password do not have the same hash value, and 2) Make the keyspace larger, so that brute-force cracking becomes infeasible.

That being said, for weak passwords that are, for instance, a variant of the username, or "password", "asdffdsa", "asdf123", or any common english dictionary word, the salts do not help much. For instance John the Ripper (a password cracker), is extremely fast when it comes to prepending the salt to dictionary words, hash them and comparing the result to the stored hash value. It will likely find many passwords that "normal people" use, in just a few seconds.

By the way, keeping the salting function as a secret is OK, as long as your security does not rely on it, i.e., if the attacker discovers the algorithm, your hashes should still be secure. Similarly, if an attacker discovers the algorithm, you may as well assume that all attackers have access to it from that point on.

Jeff: My 5 year old son wants your wallpaper! Where can I get it? q;-)

A quick google search turned up http://umbra.shmoo.com:6969/ as a bittorrent source for a 34GB (!) rainbow table. I'm sure you can find a lot of other tables for download within minutes.

Me again. I've just read that you can also use ophcrack to only extract the hashes and save/copy it for later (eg. more expensive cracking on your own machine at home?). There's even a website where you can submit a hash and it'll return the password within seconds (using a 1.1GB rainbow table): http://lasecwww.epfl.ch/~oechslin/projects/ophcrack/

LM hashes are enabled on my company's servers. They're set to completely random unrelated passwords, though. :tpg: It's no real deterrent, but it's cute. =D

Hi,
To the hello kitty fans
http://www.lexode.com/galerie/galerie/p/t/ptiteclo/113308897248.jpg

Hey Now Jeff,
I enjoyed reading another very interesting & informative post by you. You really surprised me when you stated the time it took to crack the passphrase.
Thx,
Catto

A lot of commenters are saying something along the lines of "with a salt, you can just remove the first N characters, why is that secure?" I'm not positive on this, but I believe that, when you hash an N letter word, it's not a letter to letter mapping. If the hash of ABC is XYZ, the hash of ZZZABC won't be 3 letters and then XYZ. Adding letters to the password changes the entire hash. That's why you can store the salt with the hashed password.

I had an interesting thought, when I read your line

"Passwords are never stored in plaintext. At least they shouldn't be, unless you're building the world's most insecure system using the world's most naïve programmers."

What would be more insecure: A system that uses name and password authentification but is easy to trick or a system that uses no authentification at all?

@Andreas Krey:
No, that is a bad idea. Either the attacker will get your private key (more likely scenario), or you should have secured the database in the same way you secured the key.

There's just no good reason not to use a hash.

Every time some article about encryption comes up on The Daily Worse Than Fuck or some computer blog, I am always horrified by the responses from software professionals. You guys need to stop underestimating the cost of a compromised password, and start reading Bruce Schneier's work.

@LOL:
Pull your head out of your ass. How large do you think the rainbow tables need to be when a SHA256 hash is used as the salt?

Heh, what's with the screenie? Did you lose a bet or something?

@Hinek:
A very interesting question, and one I have some experience with.

You'd think removing authentication would lower the bar for impersonation attacks, but also make people more suspicious of it happening. Unfortunately, in most cases you'd be overestimating the acuity of the users.

Seriously... people are dumb.

@Eam

I think Andreas Krey had a very good sugestion... You overelooked that he suggested to throw the private part of the key away!

This will give you a good one way function, since there is no way to recover the original without the (deleted) private key.

Also, storing the hash with the password does not make it insecure. It will shut down rainbow attacks on your passwords in quite an effective way. So the attacker has to rely on a brute force.

Mike H - Yes, adding the salt changes the resulting hash. They are talking about after it has been reversed.

"Password" might hash to "fghky" and "SaltPassword" might hash to "forkf".
If you reverse the hash for "fghky" you will get "Password" and for "forkf" "SaltPassword". If you don't know the salt, you don't know where the password begins. It could be that the salt is actually "SaltPass" and the password is "word".
But if you also have the hash "porkf" and you reverse that to "SaltPassfish" then you know that the salt is "SaltPass" and the actual passwords are "word" and "fish" respectively.

Someone feel free to correct me if I am wrong.

> I still like the idea of hiding the salt "formula" in code rather than putting it in plain sight next to the hashed password -- that way, the attacker can't generate *any* rainbow tables at all unless they've managed to obtain both the user/hashpass table and the code itself.

They don't necessarily need the code: if they can inject their own trial passwords into the system (they can log on as a user, and then later get the hash of their own password back) they may be well on their way to reverse engineering your "salt forumla", especially if it's trivial. The two suggestions above (Prepending a fixed string, or a username) are not particularly non-trivial. :)

eam: surely the only difference there is that instead of having to prepend dictionary words when generating the rainbow tables, you prepend the hash of dictionary words? The size of the table will be the same.

Jeff:

You must use a new, random salt for each password. If you don't, you're not salting; you're just creating a single, one-off hash function and using it across all of your passwords. An attacker need only pre-compute one dictionary to efficiently attack your entire password database.

For example, consider your proposed implementation:

hash = md5('deliciously-salty-' + password)
# store hash in user record; throw out password

Note that the only variable upon which the hash value is dependent is the password itself; the salt is constant. There is a one-to-one correspondence between password and hash. Thus the brute-force search space is still the space of passwords. Adding the one "salt" value has not expanded the search space at all.

Now consider true salting:

salt = generate_random_salt()
hash = md5(salt + password)
# store salt and hash in user record; throw out password

Now the hash value is dependent upon *two* variables: the random salt and the password. The brute-force search space has just been massively expanded (multiplicatively) by the size of the salt space, and (for large salt spaces) that's what makes precomputed-dictionary attacks infeasible.

In sum, if the size of your salt space is 1, you're not salting. To get significant benefits, you must use a large, randomly selected salt for each and every password.

Cheers. --Tom

OMG PONIES!

Just to resolve a couple of assumptions about the way md5 works, here are a few example usages of it.

password : 5f4dcc3b5aa765d61d8327deb882cf99
delicious-salty- : 1db9d25f47d9991dd6967d6c45077f9b
delicious-salty-password : f28e176a45f8b8f4b88eaf8f3152b057
passworddelicious-salty- : d7b27446c952e6b047ec895b90cab3b0
v3ryS3cur3p455w0rd : c6ddb34fd61e967c9821adee12240f26
delicious-salty-v3ryS3cur3p455w0rd : 76cc7274212ba88ce098842bfa734f4e
v3ryS3cur3p455w0rddelicious-salty- : 162e492cbb3f4dbc1f1bd8e6d28f79e5

If you compare these hashes, they will have very little in common.

Just getting the password stored as non-reversable hash is hard enough. The powers that be of software projects often want to be able to retrieve forgotten user passwords, security be damned.

In response to Tom Moertel, using a generate random salt function is exactly what you do using encrpytion. However, you also need a way to log into the system.

Please remember that in order to log in, the user submits their password to your service, and it does the exact same thing it did before.

salt = generate_random_salt()
hash = md5(salt + password)
# compare this hash to stored hash and if they are the same user is authentic.

Problem is, you need to use the same salt as before or no one will ever be able to log into your service.

Where generating this salt becomes very important is when setting up encrypted communications. Let say for example each time you set up your encryption, you use the same key, and encrypted communications always start with the same thing.

To make it simple we do an encrypt('helo other server, we'd like to establish encrypted communications'); which returns 4fc3d2. Now if everytime you set up this encryption, you do the same thing, the bytes you send over the network are also the same(4fc3d2). This is where your salting and IV (initialization vector) comes in. since then all you do first is encrypt(salt), then encrypt(handshake message), and the bytes sent over the line will always be different. This makes it much more difficult for a crypto-analyst to try and deduce what you are sending without decrypting any data.

This is why I proposed you use an actual encryption algorithm, and not just a hash. You want to take advantage of the fact that everytime you start encryption, with the same key, you always return the same result. Now you might want to pass your encryptor 128 or 256bytes to be more secure, this is where your hashes come in since you easily get a fixed length password from a mixed length password. So you simply do your md5/sha(password), then encrypt it against your private/public key pair with the pirvate key discarded. There is literally no way for your average attacker to decrypt these passwords.

The biggest worry from myself would be that with spammers and cracker's getting increased computational power through botnets, cryptoanalysis could become alot more prominent. Which is why I would also recommend you rotate the key's used ona yearly/monthly/daily basis, and force a password change yearly. (if you database is compromised, they have a copy of it, even if it takes 10 years to decrypt it.)

Check out the RSA Challenge: http://www.rsa.com/rsalabs/node.asp?id=2093 And see what using distributed computing can do to break these passwods.

I'm unclear as to how an 8.5 gig table contains 7 trillion hashes. Wouldn't it have to be at least 7 terabytes?

For anyone else not too familiar with public key encryption who is struggling to grasp Kevin Nisbet's ideas, I *think* it might be helpful to consider he's talking more about the digital signature concept rather than the traditional public key encryption. I *think*. Please correct me if I'm wrong.

Apparently only you can get away with having Hello Kitty on a freaking pony jumping over a freaking rainbow and super-geeky password intricacies in the same post! "Most impressive."

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.

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

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

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?

Need higher res background image!

Kevin Nisbet:

Thanks for your response. Please let me respond to your claims.

Regarding: "I really must dispute the effectiveness of this technique. It is better than storing just the MD5, but I don't think by much."

First, my using MD5 is merely a continuation of Jeff's examples from the original article. When you see MD5, please understand that it represents the hash function of your choice.

Second, the effectiveness of salting is not in dispute. It is a well-understood, well-studied method of making precomputed-dictionary attacks impractical. If you disagree on this point, please do some homework on salting before replying.

Third, salting does not make it impossible to mount offline attacks against a password database; rather, salting makes such attacks more costly because it forces each password to be attacked independently. That is, it raises the cost of a precomputed-dictionary attack on the entire database to the point where it exceeds a the cost of attempting to guess each password in the database individually.

Regarding: "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."

What happens is that the cracker is forced to guess each password individually, and that's if he can live with obtaining only *some* of the passwords in the database. If he wants to get them all, he must brute-force the ones he can't guess, and that's expensive.

You can't do better than that. If the cracker has your database, he most likely has everything else of value from your severs as well: your "hidden" keys, your "secret" hashing methods, your executable code to examine, if not your actual source code. Any bit of information your code had access to, the cracker now has. So, the only question that matters is, Given that the cracker has all the information you have, how hard is it for him to recover passwords? If the answer is that he must guess or brute-force every single password he wants, that's as good as it's going to get (for any password-based authentication system). You simply can't do better.

Regarding: "I would think that a highly improved version of this would be you atleast store the MD5(MD5(salt) + MD5(password))."

I'm sorry, but your new hash function adds no protection. The resulting hashed value depends only upon the salt and the password, the same as before. Remember, attackers are not trying to reverse your hash function; rather, they are searching its input space, and you haven't enlarged the input space.

Regarding: "I can only assume you have this method in production, ..."

Yes. And so does everybody else who understands that you can't do better than forcing the other guy to guess or brute-force every single password he wants to obtain.

Regarding: "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?"

Like I said, if the attacker can afford to brute-force a password, it's his. If he has the resources to brute-force the entire database, he can recover all of your passwords. That's just the way it is. There's nothing you or I can do about it.

Cheers. --Tom

This has turned into a really interesting discussion on encryption. I do realize this is largely employed (and use to be what I did), but there is no reason to simply follow the status quo.

The only reason I suggested the MD5(MD5(salt) + MD5(password)) was to use a 64 character key as input to the hash stored in the database, based on the examples floating around. But you're right in that just using a salt that matches or exceeds this total input would be just as good. And even better is a salt unique to each user, this was just a cheap way to get a long key off the top of my head. I'm moving towards using actual encryption algorithms for my own usage.

Regarding: "You can't do better than that. If the cracker has your database, he most likely has everything else of value from your severs as well"

This is an increidbly bad assumption, because this represents a complete failure of your system as a whole. There are many examples where solely the database is lost (SQL Injection, lost backups, incorrect access rights, etc) which do not neccassarily compromise the code used by these systems. If your database and services are operating on seperate servers, each server needs to be compromised individually, which depending on your architecture could be extremely easy or quite difficult. Now of course, when designing said system always assume the worst from a security standpoint.

The more the attacker knows about your system, the easier it'll be for him to break it en mass, don't leave any windows of opportunity open. I'm tired of hearing about security breaches en mass in the news.

@Heiko:
What you're describing, assuming the private key is completely unrecoverable, is functionally equivalent to a one-way hash. This is the solution I am suggesting (though a weird way of going about it). If the private key is somehow recoverable, you still have the same problem I am trying to address.

Also, I think you're confusing "hash" with "salt".

@Thom:
Indeed, but you have to do that for each individual user's salt. That makes the attack no better than a simple brute force against every user.

We're talking about avoiding quick large-scale attacks with pre-computed, conveniently-packaged tables.

Kevin Nisbet:

Regarding my comment that, "If the cracker has your database, he most likely has everything else of value from your severs as well," you wrote: "This is an increidbly bad assumption, because this represents a complete failure of your system as a whole."

What other assumption can you reasonably have? That, if you system is compromised, the attacker will get the database but not the secret key? Or that, he'll get the secret key but not the database? Or that he'll get the database and the key but not the code that tells him how to use the key to unlock the passwords in the database? These are the "bad assumptions." The only good assumption, the only assumption that lets you sleep soundly, is that the bad guys will be able to get any information that your system has access to. (Remember: a lot of bad guys are insiders.)

To look at it another way, if you can design your system so that your users' secrets are safe even under the assumption that the bad guys have all of the information your system does, you win -- and so do your users.

To go back to our running example, if (via salting) you can force an attacker who steals your user database to guess or brute-force each password he wants to discover -- and you can -- and if you can use a suitably expensive hash function (e.g., bcrypt) to prevent him from extracting all but the most-easily guessed passwords -- and you can -- and if you can offer this degree of security even when the attacker has *all* of the information that you do -- and you can -- why would you aim for anything less? What is the benefit to assuming that, if your system is broken, the bad guys aren't insiders or won't get everything they could?

Cheers. --Tom

These rainbow tables, are they pretty much just for MD5 hashes? I know a lot of people moved over to SHA hashes a long time ago (myself included for my projects), and last I heard such a table had not been constructed for it yet. Is that still the case?

>
lets say you add "THIS_IS_REALLY_LONG_ASFASD#$%$$%^ASDAS#$%$^&^$%734%F" To the beginning of the password. The hash table only does up to say 14 characters... The table size to store the hash of even the salt would be so large it would be easier to manually remove data from the HDD than to get the pwd.

Alex, the rainbow tables can be constructed for ANY hash. But it has to be predefined. The pre-packaged tables described in the actual article are for the LMNT hash function. But you can generate a table using any hash you wish. Jeff, in one of his comments, found that it'd take approximately 22 hours to generate a table of only alphanumerical values.

There's software freely available "rainbowcrack" that let's you generate these tables, AND.. if you want to google around.. you could download one constructed for the hash of your choice.

Anon - unless the cracker knew the salt in advance. If the maximum password length was only say, 10 chars long, then all the cracker would need to do is generate a table to a max of 10 chars, and just prefix each one with the salt. This would open up every single password to the cracker. Hence, why people are saying that each salt should be different. A new table would need to be generated for EACH password, assuming the cracker knew the salt of EACH user.

Storing the salt in each users record however, would give the cracker all the information he'd need. It'd be time costly to crack each one, but would you need more than one?

How would you go about generating a random salt for each user, yet allowing the system to recover the salt on logon, without having it available to a possible cracker if your database was exposed?

Nice Wikipedia article about this topic:
http://en.wikipedia.org/wiki/Key_strengthening
It's about hashing the password and the salt multiple times to make it harder to do a "simple" rainbow-table attack.

"I think Andreas Krey had a very good sugestion... You overelooked that he suggested to throw the private part of the key away!

This will give you a good one way function, since there is no way to recover the original without the (deleted) private key."

I don't think that using public-key encryption here (which is de facto precisely reversible) instead of hash-based encryption (which is essentially one-way) is the answer.

Consider the simple case of just adding a little "salt" to a password. Say, I start with password ABC, add "~!" to the start of it (like I said, simple!), and hash "~!ABC".

When the rainbow hash algorithm comes up against this as an unsalted password, it might come up with "~!ABC", but it more probably will come up with something wholly unresembling that original salt+password combination, like "XYZ$&". If he knew that the "salt" was in the first two letters, he'd use "Z$&" as the password, which wouldn't work (because the hash of ~!Z$& is not the same as the hash of ~!ABC). If he knew that the "salt" was "~!", then he'd still be nowhere unless he made a custom rainbow hash with the constraint of every passcode starting with "~!" (then he might come out the other side with "($&" as the password, but only if "~!($&" and "~!ABC" hashed out the same).

Now, IF WE HAD PUBLIC KEY ENCRYPTION, the above would not be true at all. Rainbow hash brute forcing would still work, although the stored length would be longer and so the hash would be significantly larger. But, it would ALWAYS come up with "~!ABC". So, if he de-hashes 10 passwords, the pattern of "~!" as a prefix will be blatantly obvious, and the "salt" completely useless. For every password yanked out of the algorithm, he'd just chop the "~!" and use that password for authentication.

Now, of course, the problem with the simple prefix (or simple algorithm creating the prefix) is that when it is known the hacker can just create a new rainbow hash with that prefix or algorithm as a constraint. The random salts make that more difficult. For instance, even if he knew that "~!" was the salt for this particular password and created his rainbow tables based on that, he wouldn't gain anything because the next row's salt is "#$" and so he'd need a new rainbow table, etc.

Personally, I am not a security professional, but I'd think that a combination of tactics would be the best. Start with a random seed (stored alongside the hash in the logins table). Add to that an algorithmic seed (an MD5 hash of the second, third, and fifth letters of the user id or something similar), which doesn't get stored in the database (so, to find this second salt the hacker would need access to the code in addition to the database). Then add on the password the user passed in.

As for the guy saying any such solution is insecure because you send it over to the user's browser as javascript ... why on earth would you send it over to the user's browser as javascript? Is there a reason why the single user's password shouldn't be sent (over SSL obviously) to the server for hashing in a controlled environment? Remember: IANASP, so treat me like a semi-retarded kindergartner in your answer :)

I already have the alpha-numeric-symbol14 rainbow tables and they work a treat :) Cracked our old domain with 70 users in 40 mins. Nice ;)

That's an interesting point about collisions Tom.
I'm still thoroughly confused over the proposed advantage of encryption over hashing.

Anon - "If the maximum password length was only say, 10 chars long, then all the cracker would need to do is generate a table to a max of 10 chars, and just prefix each one with the salt."

That's not how the hashing works. If the maximum password length was, for simplicity, 3, and I have a password of "die" and "pin" on their own they hash to "dp2" and "w2P" respectively. However, prepend a salt of "fi-" and they now hash to "pe3D34" and "lrZP2d". The salt is added *before* the hashing, meaning you can't just lop off the first x characters and then reverse that. "D34" doesn't reverse to "die" and "P2d" to "pin" but instead something completely different.

Actually, all you need is the password hashes. You don't even need to crack the password.

Example:
When you go to login to your server, you type your username and password into your machine and click 'submit'. Your machine sends a request to the server to login (no credentials are sent). The server responds with a nonce, (nonsense data/random garbage). Your PC takes the password you typed in and hashes it, then it uses the hash to encrypt the nonce it received from the server. It combines the encrypted nonce with the username and transmits it back to the server. The server does a lookup on the username, takes its private copy of your hashed password stored on the computer and uses that hash to decrypt the nonce it sent you, then compares the decrypted nonce to the nonce it sent out to you. If it matches, you typed in the correct password and your actual password is never sent across the network.

The weak spot is the hash. If I have gathered the hashes from the server, I do not need to go through the trouble of cracking them. I have written a custom login tool that all you do is type in the username. The program looks up the hashed password associated with the username and uses the hashed value to encrypt the nonce.

At this point, it doesn't matter if your password is 1 character or 14 random characters, if I have your hashes, you're toast. Cracking the passwords is simply an academic exercise at that point.

:)

Regards,
JRHelgeson

Is the geekwisdom meter meant to be taken seriously? head -c 8 /dev/urandom | uuenview -b produces a rating of "mediocre" and that's from 64 bits of pure entropy (well, PRNG entropy).

So, having read all this, what is the BEST method for password encryption? I don't think anything will be 100% secure, nothing ever is - you just make it as hard as possible.

Everyone's got to agree on something....the BEST and HARDEST method.

Besides, you can salt and hash all day long, but without add_slashes to stop sql injection...anyone can get your hashes, regardless and use the methods mentioned.

Would there be a point in using really long salts? Like 10k, 10m chars or worse? The time to authenticate a login request would not take that much longer, but generating a rainbow table would take a lot longer, wouldn't it?

one useful idea for non-us users is to use non-english alphabet characters that are on our keyboards, but not a USA one. Most of the online hash libraries do not include them.

ICR - in relation to:

Anon - "If the maximum password length was only say, 10 chars long, then all the cracker would need to do is generate a table to a max of 10 chars, and just prefix each one with the salt."

If you know the salt, say 'w4x' .. and the max length password is 3.. you generate a length table of 6 with $hash(w4x[XXX]).

The thing with Rainbow tables is that they are just a brute force attack with precomputed values but note if they have the hash value they can *always* produce the original input given enough time and resources.

So you have four ways of making your system more secure
1. make the password more complex so that the dehashing takes longer (either by forcing users to use a more complex password, or by adding a site wide salt)
2. add a salt so that the raw original value is useless (i.e. it's not the password, it's a value that the password can be computed from) , a simple non-random salt is obvious and can easily be removed
but MD5(MD5(salt) + MD5(password)) is much more difficult to de-salt
and a per-user salt very difficult to remove
3. protect your hashes (and salts)!
4. Use public key encryption, this makes calculating the password from the stored value practically impossible

md5_encrypt($plain_text, $password_e, $iv_len = 16)
{
$plain_text .= "\x13";
$n = strlen($plain_text);
if ($n % 16) $plain_text .= str_repeat("\0", 16 - ($n % 16));
$i = 0;
$enc_text = get_rnd_iv($iv_len);
$iv = substr($password_e ^ $enc_text, 0, 512);
while ($i < $n) {
$block = substr($plain_text, $i, 16) ^ pack('H*', md5($iv));
$enc_text .= $block;
$iv = substr($block . $iv, 0, 512) ^ $password_e;
$i += 16;
}
return base64_encode($enc_text);
}

/*------or ------*/

md5_decrypt($enc_text, $password_e, $iv_len = 16)
{
$enc_text = base64_decode($enc_text);
$n = strlen($enc_text);
$i = $iv_len;
$plain_text = '';
$iv = substr($password_e ^ substr($enc_text, 0, $iv_len), 0, 512);
while ($i < $n) {
$block = substr($enc_text, $i, 16);
$plain_text .= $block ^ pack('H*', md5($iv));
$iv = substr($block . $iv, 0, 512) ^ $password_e;
$i += 16;
}
return preg_replace('/\\x13\\x00*$/', '', $plain_text);
}

/*------Use----------*/
$plain_text = $password
$password_e = 'a39x909s09s9x00' // or something random
$enc_text = md5_encrypt($plain_text, $password_e)
$password_insert = $enc_text

http://www.owasp.org/index.php/Hashing_Java

For individual users, it is simple to protect yourself - use a password or pass phrase 15 characters or longer. Such a password cannot be stored in NTLM - you will receive a warning when changing to it that 'the password may not be compatible with older software such as Windows 98.' NTLMv2 passwords, which do not share this vulnerability, can be up to 128 characters in length.

So oddly, enough, "12 monkees type Shakespeare!" is more secure than "#hG0(;mjH3$=ZZ". And easier to remember.

after having read some of this, in particular PES's suggestion ("Would there be a point in using really long salts? Like 10k, 10m chars or worse? The time to authenticate a login request would not take that much longer, but generating a rainbow table would take a lot longer, wouldn't it?") and thinking a bit about some of the other issues, here's my suggestion for how to do it:

the string to be hashed:

faily-long-static-salt + username + username + username + .... + username + password + password + ... + password

and this is the good bit (possibly -- looking to see if it is in fact a good idea): use more than one hash algorithm, two or three different hash algorithms, and store each of the hash results. using several different hash algorithms will stop pretty much entirely any possibility of a collision string working for the attacker -- so they must find the *actual* string which was used rather than one which results in the same hash value (which is the problem, I think, with PES's suggestion possibly).

i don't know. this is all most head jarring. maybe a long input string like the one i've described above doesn't make much difference?; that information is in the code, and once known, doesn't help. generating a 100 hash values from input strings of 10,000 characters long costs much the same as generating a 100 hash values from input strings of 5 characters long. making the input string long in the way i and PES was suggesting doesn't increase the number of possible input strings really -- it shifts them but doesn't increase them. yup, so my post was a complete waste of time i think.

And crack xls files? :P

Ernest Schuetz

Using a server-wide salt value for all passwords is akin to wrapping your bullet-resistant glass in cellophane. You've just taken a reasonably strong, industry-standard security measure and wrapped it in the naivest possible form of security, the good ole' hard-coded password.

Random salts are intended to prevent a dictionary attack. Nothing more, nothing less. To accomplish this, as well as the side benefit of defeating rainbow tables, they do not need to private or cryptographically strong. It also does not matter if the salt is appended, prepended, or randomly distributed within the original password, as long as the process is repeatable. The point is, if two users have the same password (something crackers frequently try to make use of), they won't have the same hash. And if someone wants to run a dictionary or even a brute-force attack, they now have to re-run it for every single user.

Most importantly, if you've secured your database properly and your hacker does NOT have direct access to every password, then they may try to sniff the password over a network, and assuming your security takes replays into account, a random salt makes the sniffed hash much more difficult to use. I suppose a constant, hard-coded salt provides some security here - unless the hacker happens to be a disgruntled ex-employee who knows what it is, which is actually the most common cause of espionage.

By all means, secure your salts too if you're paranoid. Put them in a separate table or a separate database or even a separate server. Or even better, use a nonce, or a much stronger scheme like Kerberos. It can't hurt. But a global hard-coded shared secret is no substitute for a random salt. It's a feel-good measure, effectively useless and bordering on superstition, but enough for someone to give himself a pat on the back for being more secure.

If you want to be really clever about your salts, then don't just stick them at the beginning or end; use an algorithm that distributes the salt characters within the original password in a way that's dependent on the password itself. That way, a 10-character salt is essentially useless to anyone who doesn't know the distribution algorithm. You'll get all the benefits of secrecy without sacrificing the security itself.

I agree with Aaron G,

I always salt the password with something more than a default salt or a salt based off of the username or password, (as someone suggested).

You need to base your salts off of something that is NOT also stored with the password data. Such as the users Browser + the current time in India. OR even better, make a salt formula that changes over time AND uses random stuff like the time.

Personally, I use a custom encryption/decryption algorithm which spits out a base_64 encoded string that was created by applying an internal key. After which it is hashed with a salt taken from a piece of data found in all user rows, (ie first 3 letters of their username) but doesn't by itself indicate it is to be used as a the salt.

Even if the bad guys are able to figure out the salting method used and rainbow crack a users password, they end up with a base64 encoded string wrapping an extensive encryption algorithm. Forcing them to have to figure out how to reverse engineer my custom encryption algorithm before they have a usable password.

The source of the class I wrote to handle this process is also encrypted so that will need to be deciphered before they could use it to help reverse engineer the encryption. The method used to encrypt the source is completely different.

Basically, it is going to take someone a really long time, per each password, to crack my users passwords, even if they are sitting on my terminal logged in as root.

Layers of security, that's what it is all about.

so what if you were to both salt the password (before and after) and pick, say, 15 letters that get replaced by different symbols?

so, username hotch, password 46hh78iuan would enter into the database (pre-hash) with password "hot-46%%78i*)@-ch"

so, h is replaced by %, u by *, a by ), n by @, first 3 letters of username are put before pass, remainder of username is put after... this seems like it would be nearly impossible to crack, especially if the hacker doesn't know the scheme. for even more security you could have the replacement characters determined by some function of the username, or even a function of, say 3 characters of the username, so that your chosen characters are replaced by 3 different characters based on a cypher which would make my 9-char alphanumeric pass into a 25 char extended pass BEFORE including the prefix/suffix salt, with that included we're up to 32char.

or, why not build your own hash from scratch?

the real question is, what kind of impact would these security schemes have on your server?

OMG PONIES!
No seriously, where do I get that desktop wallpaper? :-)

Hi all, when referring to NTLM hashes, there's no need to crack the hash to obtain the cleartext password if you want to use those hashes to connect to services using NTLM authentication.

You can use this tool:

http://oss.coresecurity.com/projects/pshtoolkit.htm

and use the hashes directly on your windows machine, impersonating
the user whose hashes you've stolen. Then, outbound network connections will be authenticated using the hashes you just changed in memory using the tool mentioned above.
There's no need to install a 4GB table, or crack the password if you have the hash(es) of the password and want to connect to a service that uses NTLM authentication.

More info an attack scenarios possible with the tools are detailed here:

http://oss.coresecurity.com/pshtoolkit/doc/index.html

"Forcing them to have to figure out how to reverse engineer my custom encryption algorithm before they have a usable password."

99% of all custom encryption systems are worthlessly insecure. Until it's peer-reviewed, it's a very, very bad idea to trust it. How do you know, for example, that your algorithm doesn't /decrease/ password entropy? Are you *sure* it's reversible?

I think the concept of a "salt" is being extended and over used from its original intended purpose.

Salts were originaly created so that a user couldn't make their password say "password" and then compare their hashed password against EVERYBODY elses and see how many folks used that same one.

Thats all it should do.

Now a by product of the Salt is that the password is a little longer, but you can accomplish this much easier by making the original password longer.

Precomputed lookups can be very easily foiled by simply making the password longer. For every extra digit added you are increasing the number of permutations by 100X and it doesn't take that many digits to render Rainbow redundant. Jeff's mentioned passphrases and that will be the next evolution in passwords.

In the end we are going to be carrying our ID's on a physical device such as a mag card or USB drive or just forgo that entirely and use a biometric method such as a thumbprint reader. Public/Private keys will be the future and Rainbow cracker will be obsolete.

The simple prefixing or sufixing of the real password with a salt relitivly pointless. The only function it serves is to increase the character length of the password.

In the scenario where this type of attack can occur the attacker A: has access to your live DB or B: attacker has a many stolen hashes C: attacker has only one stolen hash.

In A you are already screwed.
In B and C you have a bigger problem and are only trying to delay the attacker long enough that the hashes they have are not valuable.

If the attacker has multiple hashes a prefix/suffix salt does no good. Because after the attacke cracks two hashes:
abc$12Password
abc$123IlikePoneys

it is clear what the salt was. It is what is common between them: abc$123.

If the attacker only has one hash it only delays for a while. If the cracked hash is (*&%6ILikePoneys76

The attacker has it's safe to assume that ILikePoneys is part of the password. Leaving less then 7! likely combinations.

Salting by rehashing the original hash will increase the time to crack, but only by double. If the hashes are cracked and they look like giberish, it's safe to assume they were rehashed. So rerun the cracking tool and if the subsiquent cracked hashes are things like:
Admin0%$IlikePoneys
frankzappa%$YellowSnow

you immediatly know the formula is username + '%$' + password.

Correction:
If you rehash the attacker may see this after the first run:
Admin0%$987sgdsdfsd
frankzappa%$08hadsghhd6

Then will just need to strip the part that is different to crack.

The algorithm is located and executed by my brain. God creates the best encryption.

Is the password database on Windows open for reading by everyone?

What are the scenarios that Rainbow Hash Cracking is relevant for -- just insiders with admin privilege? I know, you want to prevent that as well -- I'm just missing context for this discussion.

PS I haven't dealt with this topic since giving up Alpha/VMS admin back in 1992, so forgive me if this is a really dumb question...
(I'm mostly reading Jeff's blog for the excellent UI topics).

In the interest of password security and salting, I'll add my own form of locking down passwords. Might be hackable still, but it's gotta be a pain.

pw = md5(password)
add salt by either shuffling the result of the hash or taking some of the characters and adding them to the front and back
then for more salt do
if pw.length < X
loop that takes the odd characters and appends them to the end of the hash till it's X characters long, if it hits the end of the hashed string before getting to X length go again using the even characters
stored pw = md5(md5(user name)+md5(looped pw))

X is however long you want it to be, obviously the higher X is, the bigger the password is going to be, and the more difficult it is to use something like the rainbow tables.

I would personally love to see the work it'd take to reverse the hash into its password, especially if the hacker doesn't have the prior knowledge about the special double-salting. About the only hope to break it in a reasonable amount of time is a lucky brute force attack.

Then again, maybe I'm crazy :P

When you push a cookie with a random MD5 hash on a client after verifying username and password with the database, clients can securely identify with that hash until expiry. The hash and IP address are checked on every request, the hash can not be generated again, or guessed, or ripped thru a hack and used from another client.

Any system with algorythms will be cracked, and sooner than we expect. Security must be brought back to the physical location of the client. Even using a plaintext password (sentence) of 12 or 15 characters in your system is allready much better than average, and not to difficult for the users, who are always right and always know best. We (specialists) are here to make their lives easy.

Isn't the definition of a hash an algorithm that produces a standard-length output from variable length inputs, making it essentially irreversible in the standard sense of plugging in the output and getting back the input?
The advantage of rainbow tables, it sounds like, is that because the hashes have been pre-calculated, I could look up a given output and get a list of all the possible inputs that would yield that combination. If I were using this as a password cracking tool, I'd still have to try each of those combinations (which might be many or few).
So adding salt to my inputs would significantly complicate (and/or slow down) rainbow table computations, but doesn't increase the security of the hashing algorithm itself.
Nested hashes according to some secret algorithm/plan/pattern can make hash outputs useless to a would-be cracker only as long as they don't know the pattern and hashing algorithsms that you've used.

I have run into an several apps that "pre-salt" their password. It is fairly obvious that this has been done when you look at the list of passwords and see the same "X11C13E" or whatever at the beginning of the password.

The one app I had lost the password and was able to get into the app by just updating the table to X11C13E and drop the other 15 characters. I now had a blank password.

I would suggest a pre-salt based off something else in the table such as create date or the user id.

Wow, I've never seen so many people who don't understand salt talk about it.

Salt is random. It won't be the same between two different users.

It is effective against a rainbow hash because a rainbow hash cannot possibly include every combination.

Let's assume the windows password is limited to A-Z 0-9. No lowercase, no special characters. Let's also assume the password is 7 characters long. This is a pretty poor password by anyone's reckoning.

But there are 36^7 different passwords encoded by this. That would take a 1.2 terabyte rainbow file to store all combinations. Now we add a measly 2 character salt that is completely random, and you now need a 16 petabyte rainbow file.

With the 2 character salt, even a password of "password" would need 1296 different entries in the rainbow file to handle all the possible hashes of "password" plus salt. You can see how the salt increases the size of the required rainbow file exponentially.

The number of clueless & partly-clueless posts is smirk inducing. The number of people who don't realize that there is no character-per character correspondence between the input and output to a cryptographically strong hash is way too high.

Ok...

The rainbow Attack is used to compare "a List" of hashed passwords against a known list of hashes.

Basically the rainbow-table is the solution to the function

MD5(secret) -> Hash

Now you are able to look up a result and retrieve the secret needed to generate the result. It takes a "fair" amount of work to generate such a table.

If you change the function to include a salt, then you would be forced to generate a new table for each salt. That means a "plain old" brute force would be much more adequate, since it would stop once the password is retrieved, and no more CPU power would be wasted on generating new hashes...

The reason for a hash is to make those precomputed lists "invalid". And its achieving that exactly.

Also the "insane" memory requirements for the rainbow table would be gone, and the whole problem would be raw cpu power.

The suggestion with the "public key, without a private counterpart" is a completely different aproach. It introduces a NEW FORMULA into the mix. There is no precomputed solution table for your public key. Its safe to hand it out, and without the private part, there is "no known" way to reverse it... Heck... you can even hash the password, and then one-way encrypt it symetrically...

Hope this makes sense... :)

Ok, enough of this sillyness

You keep the salt string in an encrypted file on the server.

In Windows you use the user key and machine key to encrypt it - so only this machine and the user IIS is running under can unencrypt it.

That way no user can unencrypt it, and if it is copied to another machine it cant unencrypt it.

Next step

Pick the salt such (I am using C#)

String salt = "Hey user {0} ThIs_is a pretty %@%^*&)*() strong salt for the PaSsWoRd {1}";
String Salted = String.Format(salt, UserId, Password);

You can also break the hash into parts - you decide how many, where and what lengths, then sprinkle those parts into the salt.

Remember this isn't cryptography - it is hashing - you just need a secure way to store and verify passwords. The above is plenty secure.

Pick a salt based on the text of a book - use a whole page of text - a good page from The Amateur Emigrant by Robert Louis Stevenson with the hash sprinkled among the text will work nicely.

Store the SHA512 (space is cheap) value of that and it will NEVER be rainbowed.

Also you never hold the password pass that point - you store the SHA512 hash - you compare the SHA512 hash.

Never use unencrypted cookies. Bad, bad developer. Best is to store a hash on the users machine - use the hash to lookup the users session data. This hash can be based on time given out, users IP address, anything you want to lock it down, but use a nice salt for it too.

String salt = "This is a salt string for a cookie created at {0} for the user {1} at IP address {2}."

Where {0} is date time and {1} is the user name and lastly {2} is the users IP address.

Again, it is best to use a large salt. (Larger than the example). IP addresses can be shared - so you need to think of other properties to add. Think of all the data you get from a browser.

This isn't rocket science people, basic security 101.

DeveloperJoe: Encrypt-hash is a useful security measure but I don't see the advantage of using custom encryption. Unless you're working in a military sector and have access to bleeding-edge cryptographic tools, I guarantee that your hand-rolled algorithm is much weaker than an industry standard like AES or 3DES or Blowfish. In order to crack one of those schemes, a hacker must first know which one you used, as well as the private key; if he's able to get all of that information in addition to your password database, I think you're long past the point where the secrecy of your encryption algorithm can protect you.

brian: That is precisely the point of a random, per-user hash. There are no commonalities to be found after cracking two hashes or n hashes, nor is there any consistent scheme to guess. A cracker HAS to alter his dictionary/hash function for EVERY record.

Ix: Hashing multiple times actually weakens your hash because it raises the probability of collisions. You're using a "clever" obfuscation, but your hash is still derived solely from the user name and password, which ultimately is just security by obscurity and adds no value beyond what's offered by just a simple one-time hash. The point of a random salt is that there is no predictable pattern; the information is very little help to a hacker. You can gain a tiny amount of additional security by obfuscating the way in which salts are *used*, as I mentioned above, but they still have to be random. If you're substituting any deterministic algorithm for randomness, you're just making the system LESS secure.

All of these bizarre security implementations amount to a pointless waste of time. It takes about 30 seconds to write 3 lines of C# code to generate a random salt. If you're generating a whole bunch of them at once and really need crypto-strong salts, another 10 lines or so and a couple more minutes will give you that. How many costly dev-hours have been spent on designing, coding, and testing these pseudo-salts, when it would have taken just a few minutes to put together something much more effective?

Incidentally, I'm betting that a lot of people here are web developers, and if you are, then there's already a system for dealing with packet sniffers. It's called SSL. It takes an hour or so and a couple of hundred bucks to deploy. Less, if you don't mind looking like a cheapskate. Look into it, folks.

This article was featured over at slashdot, nice one Jeff.

I'd like a quick question answered..
If the salt is generated completely randomly for each password, how is the user supposed to log in if the system can't recreate the same salt at logon? It'd need to be a static function that changes based on user input.

"If the salt is generated completely randomly for each password, how is the user supposed to log in if the system can't recreate the same salt at logon?"

The salt is stored plaintext. Usually just prepended to the beginning of the resulting hash.

The salt doesn't need to be secret at all.

brian:

"If the attacker has multiple hashes a prefix/suffix salt does no good. Because after the attacke cracks two hashes:
abc$12Password
abc$123IlikePoneys"

This is where you are wrong. There are other reasons to have a per-password seed (which doesn't depend on the password), but this is not one of them. What you'll get when you crack the hash is not "abc$12Password", but "()#$!@# D@#$" that just happens to hash to the same value.

Again: HASHES ARE BY DESIGN NOT REVERSIBLE. Multiple password+salt combinations will lead to the same hash. This is, in fact, why rainbow hashes work: you don't need to map each and every possible password of each and every possible length to its stored hash, you just need *one* of the possible passwords for each possible stored hash, which is many orders of magnitude smaller in scope!

If you reverse-hash 1000 passwords which all share the same seed, it is still unlikely that the seed will be "obvious". Depending on the specific hash algorithm, there could be a million possible "solutions" to each particular hash, and so chances are you won't even *hit* the salt in those 1,000 solutions!

Consider the simple ASCII checksum hash (which of course wouldn't be used in a security setting I'd hope, but which illustrates the point): "abc" and "cab" and "aad" and "daa" all have the same hash value. In that particular hashing algorithm, "saltpassword" might be the original salted password, and "passsaltword" might be the solution for one of the hashes, or even "psassbwolsd" (the two words intermingled and the "a" and "t" shifted to "b" and "s"). It's unlikely you'd be able to deduce that putting "pawwsord" into the algorithm will validate your login there.

Why not interleave the salt with the password ...

so salted_password = (salt_character_1 + password_character_1 ... + salt_character_n + password_character_n)

When length(salt) <> length(password), repeat the characters of either the salt or the password (whichever is shorter) until length(salt) == length(password).

It seems like this approach would make it impossible to discern patterns in the hashes, and thereby determining what the salt is.

Oh well, probably is very naive, and won't work; but just my $0.02.

How to make passwords (more) secure:

1) Use two different hashing algorithms, this renders collision attacks useless. For example, use MD5 and SHA1 and make sure both hashes match the user's input for a successful login.
2) Generate two random salts containing at least one special character of at least eight characters long for each user. Apply one to the MD5 and one to the SHA1. It's okay to store these in the database.
3) Apply a static, site-wide salt to the password, make this at least 8 characters long. Store this password in a protected directory in the application, not the database.
4) Run the password through their respective algorithms many times, at least 1000. This makes the act of generating a rainbow table extremely expensive on the attacker.

If you follow these steps you will have a password system that:
- Is immune to collisions
- Requires the attacker to get your database and your application code. At this point you probably have more to worry about than passwords being discovered.
- Forces the attacker to spend considerable resources cracking the password. Each user's password will be at least 16 + minimum password length (suggested at least 6) characters long. Generating a rainbow table going 22 characters with special symbols included will take forever. On top of this, the attacker spends 1000 times as long as it takes normally to generate this rainbow table because of your iterations. 1000 times a 22 character length rainbow table is not a quick process.
- Needs a new table for each user.

I love people. They whinge about the "sillyness" and then propose convoluted techniques for generating a 512-bit salt which are guaranteed to be less random (and thus less useful) than simply grabbing 512 bits out of your nearest cryptographically acceptable random number generator. (Building a cryptographically acceptable random number generator is hard, but no amount of hashing text and mucking around with XOR will do the job.)

FYI if you're using C, then rand() does not count. If you're using a web framework, consider carefully checking how it generates its random numbers.

Encryption - the only topic that beats religion and politics for inspiring the ignorant to claim to be geniuses. ;)

Noted security researcher MC Frontalot claims that one simply can't hide secrets from the future with math, although you can try. Maybe he's right.

One trick for making up long, complicated, but easy-to-remember passwords is to use a (fake) email address. This gives a long password a familiar mnemonic structure which can lend itself very naturally to a larger mnemonic scheme. The password even includes a few non-alphanumerics (@ and .) pretty much for free, as far as human memory consumption goes.

"WinstonSmith@Room101.com," for example, gets top scores on the GeekWisdom and Microsoft password testers. It's much too long for currently-practical rainbow tables to work on. But its pretty easy to remember, and its a lot easier to type than the line-noise a random password generator puts out.

Am I the only poster wondering why you have a Hello Kitty & Rainbow background?

Hi Rah-

We store the salt with each user record in the database, this makes each Salt different. When a user registers, they get a unique ID which we store locally on thier machine and use it to pull the right database record. We then use the salt along with the user's typed in password to generate the password hash and compare that versus the hash that is stored in the database.

If we can't find the user, we treat them as a new user and register them. Of course if the user reformats thier machine or logs in on a different machine, then they would have to re-register.

Anyways, that is how we store different Salt on a per user record basis.

N

Justin:

"1) Use two different hashing algorithms, this renders collision attacks useless. For example, use MD5 and SHA1 and make sure both hashes match the user's input for a successful login."

Isn't this functionally identical to just doubling the length of your MD5 hash? I mean, either way the number of theoretical collisions goes down by about the same amount, right? Why complicate things further?

If you store my hashed but non-salted password in your system and a cracker gets hold of the hash, they can now log in as me in other systems that also forgets to salt, using custom login tools that send the hash directly (without asking for the password to turn into that hash), under the (very good) assumption that I am using the same password elsewhere.

That's why you should please not forget to salt.

/Mats

Re: Tom Dibble

I suppose you could use md5 twice as long as they had different salts, or differed somewhere along the process of encrypting them. I prefer MD5 and SHA1, but your mileage may vary.

Another trick an admin could use to obfuscate a password in a database is to create two hashes and combine them in a way that looks like a single md5 hash. The only way to know the hashing function is to get the application code.

I think the moral of the story is simply do not use just a straight hash for protection. A salt and a few iterations is enough to deter all but the most persistent attackers as long as your application code doesn't become known.

(appending)

...also assuming that it is the same hashing algorithm in use on those other systems of course.

Also, if the cracker gets my unsalted hash from some sloppy system, they can brute-force/dictionáry attack it to find an input that gives the correct hash (as noted by other commenters, the chances that hit will in fact be my password are small) and then just use that password to log into other sloppy (unsalted) systems where sloppy old I have used the same password - without even using a custom login tool.

This is the reason why a salt can't be replaced by a longer password - even with a longer password you still need the salt to prevent the cracker from impersonating the (sloppy) user on other systems.

/Mats

/Mats

Haven't read all the comments, someone may have already pointed this out... If I am remembering correctly, the purpose of the salt is to combat a dictionary attack checking the stored pw hash against a list of hashes for commonly used passwords.

Tom
You miss the point. The cases that an attacker would use this method, are cases where the attacker has access to the hashed passwords. Having a list opens up the ability to compare various 'reversed' or 'cracked' or whatever passwords to each other. If a salt is not random, then i would think it would become apparent.