During a Q&A period at DEFCON this year, one member of the audience mentioned that we're using "fake salt" when concatenating a random value and a password before hashing. He defined "real salt" as something seen in the original Unix crypt implementation that changed how the algorithm ran, thus requiring different code to be used to crack each password and greatly troubling GPU attacks.
Is there any merit to the "real" and "fake" salt discussion?
The distinction is arbitrary. A salt-aware algorithm works by taking input data and scrambling it in various ways, and there is no method for inserting the salt which is more or less "fake" than any other.
Trying to devise a password processing algorithm which is efficient on a general purpose CPU but does not scale well on a GPU (or a custom FPGA or ASIC) is a real research topic. This is what scrypt is about, and arguably bcrypt already does a good job at it. The idea here is to use accesses in tables which are constantly modified; table access in RAM is something that general purpose CPU are good at, but which makes things difficult for GPU (they can do it, but not with as full parallelism as what is usually obtained with a GPU).
Yes, there is a valid distinction to be drawn; you would need a cryptologist to tell you how meaningful the difference is.
A "real salt" as you've described is used to "perturb the encryption algorithm". I vaguely understand that, but not well enough to describe properly. Suffice it to say that with a real salt, the original password text is enciphered but with different outputs depending on how the algorithm incorporates the salt input (the algorithm has (at least two) inputs, the salt and (separately) the original password text).
A "fake salt" involves modifying the original password text with the salt before enciphering it with the crypto algorithm. For example, if my password is "nezperce", and my salt is "qp", then the algorithm will be handed the modified password text "qpnezperce" to encode. If Alice also tries to use password "nezperce", but has salt "w4", then the algorithm will encode the modified password text "w4nezperce" for her. As a result, her enciphered hash will differ from mine, even though we're both using the same password.
Both methods provide the primary benefit of the salt; to ensure that the same password isn't always enciphered the same way. Using salts increases the difficulty of mounting a pre-computed hash attack (formerly I said dictionary or brute force attack, see comments).
I believe that there are other advantages to using a "real salt", such as increased computational overhead (which slows down attacks). But, again, you'd need someone with more crypto skill than I to know whether that's true or not.
I think the advantage of a "fake salt" is that it's easier to implement and requires less crypto savvy. I know that the place I've most commonly seen fake salts is web applications managing their own auth database.
As Thomas pointed out, the general notion of just applying the salt as a modification to the hashing algorithm really doesn't fundamentally gain you any added protection. It can require the attacker to adapt existing software and hardware attacks, but it can also get you in trouble if you don't really know what you're doing.
But they missed the other old innovation in the original paper on salting - what is normally called a "pepper": a custom key that is part of the implementation, and not stored along with the passwords. I reference the way that Morris and Thompson introduced that concept also in their seminal Unix paper in the discussion at Password Hashing add salt + pepper or is salt enough?
A pepper has the advantage that you can use it in conjunction with a salt, such that even if someone steals the password database (which does have the salts), they would also need to steal the pepper (perhaps incorporated into the application or the hashing library code or stored on a completely separate system) to crack the passwords. In many cases that won't be much harder, but in some cases it may be significantly harder.
Not familiar with the details of the original Unix crypt implementation. But that doesn't seem to really make sense to me. Especially considering what the purpose of salting passwords is in the first place. I think if using a salt changes your algorithm to make it 'stronger' then you're using the wrong algorithm in the first place.
I was also at the talk and I was the one that sat down with both of the cryptographers during the talk. The true salt compared to a fake salt really intrigued me. Now forgive me as I do not have my notes in front of me, but there is a vast difference in the security of true salt compared to a fake salt. A true salt alters the key as it goes into the block cipher, so not only is the plaintext (password) unique the key to determine how the iterations will take place is also unique. Now a fake salt just alters the plaintext (password) and the key remains the same. By adjusting the algorithm the true salt becomes exponentially harder to crack than a fake salt.
So lets use an example to describe this. In this example I will use an MD5 hash (I don't remember if you can use a true salt on MD5 though so don't flame me for this) with both a true salt and a fake salt. Now lets say that I am using CUDA-Multiforcer as my GPU password cracker. I would set to run against the standard MD5 to try and crack the password but since I salted the password it could run forever based on the salt (true or fake). Now part of the description that was given to me was the ability to crack the fake salt and how it just took a little bit longer to compute / crack by breaking the hash into pieces. I did not follow what they were saying so I could be way off base with that. Now lets assume that we were able to acquire the password salt (true of fake). Using a fake salt we just enter it into our password cracker and continue to brute force until we can match the hashes. Not very hard to do and will run fairly quickly.
Now if we were using a true salt it would be exponentially more difficult, and longer to crack the hashes. Using a true salt I would have to actually rewrite part of the CUDA-Multiforcer to use a true salt with the specific algorithm that was being used. Remember it changes the key in the cipher which means that it isn't just a simple text change, it is an algorithm change, so now I have to alter the code to do this. Okay, so now we have changed how the password cracker runs, we now run into a speed problem. With the changing of the key it now takes quite a bit longer for it to test each password, as it is now changing the iteration it uses for each brute forced password. They had both given me some examples of the difference in the speed, and I think with a fake salt it was around 1 million per second, and a true salt was around
The distinction between fake salt and real salt only makes a different if the hashing algorithms are hidden to the attacker. a "real salt" which determine a variation of the hashing algo in an open standard hashing algo would easily be implemented by a GPU/distributed attack, since all input are known to the attacker and hence the sub-algo can easily be determined ahead of time.
The early Unix hashing algo for passwords (As I recall it from Bell System V7) did NOT provide the algo for the password hashing -- it was the only part of the system for which you could only get the .o file, where universities were able to get the source code for everything else.
