Passwords With a Grain of Salt

90% of time that I see hashed password in database, it is result of MD-5, SHA-1 or similar hash algorithm. While this does satisfy bare minimum requirements for password storage it is not enough.

Problem lies in “rainbow table” attacks. While checking password against all possible combinations seems difficult, it becomes easier once you get one big file with all those combinations pre-computed. Cracking password becomes just searching for already existing hash. Yes, amount of data is quite big (hundreds of gigabytes) but any personal computer can handle this easily.

All you need is to download pre-existing rainbow table and check all entries against your hash. I checked this against some passwords I had access to and success rate was near to 100%. It was very scary experience. Fortunately, there is easy solution - just introduce salt.

Salt consists of few random bytes appended to password (8 bytes seems like nice number). Our hashing function then becomes:

hash = SHA1(password + salt)

This simple step invalidates all precomputed rainbow tables. Even better, since salt differs between users, each user must be attacked separately. Time for cracking just got increased significantly.

Cost on implementation side is just having another field for storing salt. Cost of few additional bytes per user seems reasonable.