I have been following online discussions centred around recent password leaks (LinkedIn, eHarmony, Last.fm) and it seems that there are still many developers who hold a very strong belief that salt values will make passwords safe.
Even if attacker would have the salt, the common rationalization seems to be that an attack isn't practically feasible, because it would take forever to go through 14 characters keyspace, and thus salt must be making things safe. One could say that developers are grasping at salt like a small child is grasping his teddy bear, trusting that it will keep all evil crackers at bay.
Unfortunately humans are generally not random number generators. A very nice piece of research from Francois Pesce provides compelling evidence of this.
What Francois is basically doing is that he is attacking a big password database, something like LinkedIn's, with a dictionary attack and then adding any cracked passwords to his dictionary for subsequent rounds. This automatically optimizes the attack against passwords that people tend to use for that particular service. And he is doing his experiment without using rainbow tables, which means that his experiment setup also covers situation where passwords would be salted but attacker has obtained salt values.
This is a very effective method of finding typical passwords that people tend to use, and then find additional permutations of those common passwords, thus picking all the low hanging fruits in the database.
Who cares that an attacker is unable to crack the 20 to 40% of accounts because of well chosen passwords if he is able to get 60 to 80% of your users' accounts?
So how to defend against this?
Normal users should never choose a password that contain words, long passphrases are a bit better, but they can also be surprisingly weak against a GPU assisted dictionary attack.
Because most of users will never use strong passwords,developers should switch to slow hash implementations and use unique salt value per user. But there seems to be surprising reluctance on switching to a slow hash, as developers fear that they will run out of CPU cycles if too many users try to authenticate at same time.
To counter the problem of too many valid users logging in at the same time, you can steal a page from the attackers' book. Calculate user password hash checks with a GPU, just like the enemy does.
For example, NVidia's CUDA platform is ideal for integrating into a password authentication server. Using CUDA, you get a level playing ground with your enemy. Even with a single CUDA capable card per password server, you can compute password hash checks in 1ms, so that the enemy will also need 1ms to try to crack that password, which means that instead of billions of attempts per second, an attacker will be limited to thousands of attempts per second.
Of course an attacker can get, let's say 100 CUDA or powerful ATI cards, but that would be prohibitively expensive and would provide such an attacker with only 100,000 attempts per second, not 230,000,000,000 attempts per second.
Unfortunately, there is no ready drop in integration of CUDA or ATI GPU support for web or other applications, but hey, that's what the open source and developer community is for.
I could not find an open source library for using CUDA in password authentication, but any of the open source cracking tools can be easily adapted. For example: http://code.google.com/p/pyrit/, which is intended for WPA/WPA2-PSK but could also be used to check passwords.
