Salt (cryptography)

In cryptography, a salt consists of random bits, creating one of the inputs to a one-way function. The other input is usually a password or passphrase. The output of the one-way function can be stored rather than the password, and still be used for authenticating users. The one-way function typically uses a cryptographic hash function. A salt can also be combined with a password by a key derivation function such as PBKDF2 to generate a key for use with a cipher or other cryptographic algorithm.

In a typical usage for password authentication, the salt is stored along with the output of the one-way function, sometimes along with the number of iterations to be used in generating the output (for key stretching).

Early Unix systems used a 12-bit salt, but modern implementations use larger lengths from 48 to 128 bits.

Salt is closely related to the concept of nonce.

The benefit provided by using a salted password is making a lookup table assisted dictionary attack against the stored values impractical, provided the salt is large enough. That is, an attacker would not be able to create a precomputed lookup table (i.e. a rainbow table) of hashed values (password + salt), because it would take too much space. A simple dictionary attack is still very possible, although much slower since it cannot be precomputed.

Unix implementations

Earlier versions of Unix used a password file (/etc/passwd) to store the hashes of salted passwords (passwords prepended with two-character random salts). Note that in these older versions of Unix, the salt was also stored in the passwd file (as cleartext) together with the hash of the salted password. The password file was publicly readable for all users of the system. It must be readable so that user-privileged software tools can find user names and other information. The security of passwords is therefore protected only by the one-way functions (enciphering or hashing) used for the purpose.

Early Unix implementations limited passwords to 8 characters and used a 12-bit salt, which allowed for 4,096 possible salt values. While 12 bits was sufficient for the '70s, by 2005 disk storage had become inexpensive, so much, that an attacker could pre-compute the hashes of millions of common passwords, including all 4,096 possible salt variations for each password, and store the precomputed values on a single hard drive. An attacker with a larger budget could build a disk farm with all 6-character passwords and the most common 7- and 8-character passwords stored in hashed form for all 4,096 possible salt values.

Web Application implementations

Many web applications store users' passwords as a hash in a database. Without salt, a successful SQL injection attack may yield easily crackable passwords. Because many users re-use passwords for multiple sites, salt is an important component of overall web application security.^[1] Some additional references for using salt to secure password hashes in specific languages (PHP, .Net, etc) can be found in the External Links section below.

Additional benefits

The modern shadow password system, in which password hashes and other security information is stored in a non-public file, somewhat mitigates these concerns. However, they remain relevant in multi-server installations which use centralized password management systems to "push" password or password hashes to multiple systems. In such installations, the root account on each individual system may be treated as less "trusted" than the administrators of the centralized password system, so it remains worthwhile to ensure that the security of the password hashing algorithm, including the generation of unique "salt" values, is adequate.

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. an 8-byte password, and 2-byte 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.

Salts also make dictionary attacks and brute-force attacks for cracking large number of passwords much slower (but not in the case of cracking just one password). Without salts, an attacker who is cracking many passwords at the same time only needs to hash each password guess once, and compare it to all the hashes. However, with salts, all the passwords will likely have different salts; so each guess must be hashed separately for each salt, which is much slower since hashing is generally computationally expensive.

Another (lesser) benefit of a salt is as follows: two users might choose the same string as their password, or the same user might choose to use the same password on two machines. Without a salt, this password would be stored as the same hash string in the password file. This would disclose the fact that the two accounts have the same password, allowing anyone who knows one of the account's passwords to access the other account. By salting the password hashes with two random characters, then odds are - even if two accounts use the same password - that no one can discover this by reading password files.

See also

• Password cracking
• Cryptographic nonce
• Initialization vector
• Padding (cryptography), sometimes confused with salting
• Rainbow tables

References

1. ^ "ISC Diary – Hashing Passwords". Dshield.org. http://www.dshield.org/diary.html?storyid=11110. Retrieved 2011-10-15. 

External links

• Morris, Robert; Thompson, Ken (1978-04-03). Password Security: A Case History. Murray Hill, NJ, USA: Bell Laboratories. http://cm.bell-labs.com/cm/cs/who/dmr/passwd.ps 
• Wille, Christoph (2004-01-05). "Storing Passwords - done right!". http://www.aspheute.com/english/20040105.asp. 
• Primer on Unix password structure
• OWASP discussion of hashing java with salt
• OWASP Cryptographic Cheat Sheet