views:

3461

answers:

8

I've always been curious... Which is better when salting a password for hashing: prefix, or postfix? Why? Or does it matter, so long as you salt?

To explain: We all (hopefully) know by now that we should salt a password before we hash it for storage in the database [Edit: So you can avoid things like what happened to Jeff Atwood recently]. Typically this is done by concatenating the salt with the password before passing it through the hashing algorithm. But the examples vary... Some examples prepend the salt before the password. Some examples add the salt after the password. I've even seen some that try to put the salt in the middle.

So which is the better method, and why? Is there a method that decreases the chance of a hash collision? My Googling hasn't turned up a decent analysis on the subject.

Edit: Great answers folks! I'm sorry I could only pick one answer. :)

+8  A: 

It shouldn't make any difference. The hash will be no more easily guessable wherever you put the salt. Hash collisions are both rare and unpredictable, by virtue of being intentionally non-linear. If it made a difference to the security, that would suggest a problem with the hashing, not the salting.

Phil H
Hash collisions depend on the size of the hash. Thanks to the birthday problem collisions are quite likely.
Georg
Only if you truncate the result. Anyway, I still stand by the point that it won't make a difference where the salt is, because the point of the hash is to make the relationship between input and output contain no patterns.
Phil H
+12  A: 

Prefix or suffix is irrelevant, it's only about adding some entropy and length to the password.

You should consider those three things:

  1. The salt has to be different for every password you store. (This is quite a common misunderstanding.)
  2. Use a cryptographically secure random number generator.
  3. Choose a long enough salt. Think about the birthday problem.

There's an excellent answer by Dave Sherohman to another question why you should use randomly generated salts instead of a user's name (or other personal data). If you follow those suggestions, it really doesn't matter where you put your salt in.

Georg
As a non-security guru, I don't really get point 1. Ishashed_pw = hash(canned_salt + login + password)sufficient, or do you need to store your salt along with the password? Any pointers to why?
wowest
I've added a link to an old question, read those answers. Basically, by not using a different random salt per password you're taking an unnecessary security risk, that might be a real problem in the future.
Georg
If you read his answer, he is saying you should use a random salt versus their username or other user data. Having one side wide random salt is still valid.
Samuel
Should be secure enough, unless you have a lot of users and a hacker creates a rainbow table, just for your site.
Georg
Yes, still very secure. You just might want it to be more secure so you could generate a salt for each user.
Samuel
Site-wide random salt is bad, since an attacker can precompute rainbow tables and grab your entire user database. If you don't understand this, please don't write login/security systems :) - you NEED per-user salts.
snemarch
Yes, per-user salt. Ideally, with per-user iterations stored (so you can increase the number of iterations used over time). Any decent framework will have this built-in. (.NET has PasswordDeriveBytes which will handle everything for you.)
MichaelGG
You don't need salts at all. You *should* have salts. And as to if you need per user salts, it all depends on the incentive for someone to compromise your user accounts. If there is a huge incentive, you need per user since it will be very costly to compromise all users.
Samuel
"You don't need salts at all" - heck, you don't need hashing at all, if you think you can keep your database secret ;-)
Steve Jessop
If you're designing any kind of security system, it's braindead not using per-user salt. *your* site might not be super-interesting, but consider users using the same password on multiple sites... trying to keep the database safe tends to fail :)
snemarch
@Samuel: I think that a single site-wide random salt is a mistake. Suppose an attacker is making a dictionary attack on your password file. If all use the same salt, he only needs to hash each word once, and check for matches. Salt per user means hash per user, and the attack is n times slower.
Steve Jessop
Salts don't protect against dictionary attacks, only against rainbow-tables. But he's right that it makes such an attack much slower.
Georg
+4  A: 

BCrypt hash if the platform has a provider. I love how you don't worry about creating the salts and you can make them even stronger if you want.

Samuel
As var as I know, BCrypt Hash needs salting, just like any other hashing scheme.
Jacco
+17  A: 

I think it's all semantics. Putting it before or after doesn't matter except against a very specific threat model.

The fact that it's there is supposed to defeat rainbow tables.

The threat model I alluded to would be the scenario where the adversary can have rainbow tables of common salts appended/prepended to the password. (Say the NSA) You're guessing they either have it appended or prepended but not both. That's silly, and it's a poor guess.

It'd be better to assume that they have the capacity to store these rainbow tables, but not, say, tables with strange salts interspersed in the middle of the password. In that narrow case, I would conjecture that interspersed would be best.

Like I said. It's semantics. Pick a different salt per password, a long salt, and include odd characters in it like symbols and ASCII codes: ©¤¡

Tom Ritter
"common salts" - so the threat model is so specific, it assumes you're smart enough to salt, but not smart enough to use randomly-generated salts? ;-)
Steve Jessop
@onebyone, damn! He's discovered my salt of 'passwordsalt'!
Samuel
@Samuel: I don't know about you guys, but we use '12345' for our salt. :)
Randolpho
@onebyone valid. I really meant "common" as "all salts under length X in characterset Y" where X, Y are reasonable; say 20 chars and alphanumeric upper/lowercase. Extendable to say all hexadecimal strings under length Z (say 160) since I think a rainbow table of hashed hashes would be useful..
Tom Ritter
@Randolpho: Hey, that's my salt, too! What're the odds?
Adrien
And make sure the salt is non-predictable/Random : http://stackoverflow.com/questions/1645161/salt-generation-and-open-source-software/1645190#1645190
Jacco
+3  A: 

Inserting the salt an arbitrary number of characters into the password is the least expected case, and therefore the most "secure" socially, but it's really not very significant in the general case as long as you're using long, unique-per-password strings for salts.

cookiecaper
+4  A: 

If using a cryptographically secure hash, it shouldn't matter whether you pre- or postfix; a point of hashing is that a single bit change in the source data (no matter where) should produce a different hash.

What is important, though, is using long salts, generating them with a proper cryptographic PRNG, and having per-user salts. Storing the per-user salts in your database is not a security issue, using a site-wide hash is.

snemarch
+5  A: 

Hypothetical threat model:

The attacker has 'rainbow tables' consisting not of the hashes of dictionary words, but of the state of the hash computation just before finalising the hash calculation.

It could then be cheaper to brute-force a password file entry with postfix salt than prefix salt: for each dictionary word in turn you would load the state, add the salt bytes into the hash, and then finalise it. With prefixed salt there would be nothing in common between the calculations for each dictionary word.

I assume of course that the hash computation uses the bytes in order, but that's not uncommon. If the hash were reverse-order, you'd want postfix salt, but I don't know that any normal hash does that. Crucially, the threat doesn't apply if the hash computation works on blocks so large that the trial passwords don't fit in one, because then you couldn't usefully do a part-computation using a dictionary word. "Proper" cryptographic hashes like MD5 and SHA-anything fall into this category, so I don't think it's a practical concern.

I just made up this threat model - I don't actually know what experts say on the subject, except that on page 52 of 'Applied Cryptography' Schneier arguably implies that salt should be prefixed, since he describes it as 'a simple attempt at an initialization vector'.

The hypothetical 'rainbow table' might of course be much bigger than a regular one, and the attack much slower than a regular reverse-hash lookup. But it would be some linear factor faster than a regular brute force. Since regular brute forcing does in practice crack "weak" passwords in achievable time, an improved brute force would change the definition of "weak", raising the bar for how good your passwords need to be.

Steve Jessop
+1 for good thinking. Probably not ever a practical issue, since it's probably unlikely passwords would end up on a block boundary (1024 bits for SHA512, right?).
MichaelGG
Yep, I was just editing because I thought of the same thing as you did regarding blocks. All depends what hash you use, and I don't know enough off the top of my head to conduct a review of all known hash algorithms...
Steve Jessop
... looks like any of the sensible hashes you might use, have block sizes so enormous that bad passwords won't fit in one. I'll edit accordingly.
Steve Jessop
Most hash algorithms use several rounds, which defeats your attack.
Georg
Yes, the more I think about it, the more this is a silly threat model: it doesn't apply to any sensible password salting/hashing scheme, wherever you put the salt.
Steve Jessop
gs, the rounds aren't over the entire input, otherwise you'd never be able to hash large files (80 passes over 1GB? um, no.)
MichaelGG
onebyone, in contexts of passwords, yea, not much of a threat. In general though, you might look for exactly this kind of weakness in a hash. If you know a certain sequence will reset the internal state, you can modify the start of a file, "reset" the hash, then let it hash the rest.
MichaelGG
+2  A: 

First of all, the term "rainbow table" is consistently misused. A "rainbow" table is just a particular kind of lookup table, one that allows a particular kind of data compression on the keys. By trading computation for space, a lookup table that would take 1000 TB can be compressed a thousand times so that it can be stored on a smaller drive drive.

You should be worried about hash to password lookup tables, rainbow or otherwise.

@onebyone.livejournal.com:

The attacker has 'rainbow tables' consisting not of the hashes of dictionary words, but of the state of the hash computation just before finalising the hash calculation.

It could then be cheaper to brute-force a password file entry with postfix salt than prefix salt: for each dictionary word in turn you would load the state, add the salt bytes into the hash, and then finalise it. With prefixed salt there would be nothing in common between the calculations for each dictionary word.

For a simple hash function that scans linearly through the input string, such as a simple linear congruential generator, this is a practical attack. But a cryptographically secure hash function is deliberately designed to have multiple rounds, each of which uses all the bits of the input string, so that computing the internal state just prior to the addition of the salt is not meaningful after the first round. For example, SHA-1 has 80 rounds.

Moreover password hashing algorithms like PBKDF compose their hash function multiple times (it is recommended to iterate PBKDF-2 a minimum of 1000 times, each iteration applying SHA-1 twice) making this attack doubly impractical.

You should double check the description of rounds. The rounds are on a per chunk basis, not the entire message. (Otherwise, hashing streaming data would require rewinding again and again.) But using iterations does prevent the problem onebyone mentions.
MichaelGG