Salt (cryptography)

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In cryptography, a salt comprises random bits that are used as one of the inputs to a key derivation function. The other input is usually a password or passphrase. The output of the key derivation function is stored as the encrypted version of the password. A salt can also be used as a part of a key in a cipher or other cryptographic algorithm. The key derivation function typically uses a cryptographic hash function. Sometimes the initialization vector, a previously-generated value, is used as the salt.

Salt data complicates dictionary attacks that use pre-encryption of dictionary entries: each bit of salt used doubles the amount of storage and computation required.

For best security, the salt value is kept secret, separate from the database. This provides an advantage when a password database is stolen, but the salt is not. To determine a password from a stolen hash, an attacker cannot simply try common passwords (such as English language words or names). Rather, they must calculate the hashes of random characters (at least for the portion of the input they know is the salt), which is much slower.

In some protocols, the salt is transmitted as cleartext with the encrypted data, sometimes along with the number of iterations used in generating the key (for key strengthening). Cryptographic protocols that use salts include SSL and Ciphersaber.

Early Unix systems used a 12-bit salt, but modern implementations use larger values.

Salt is closely related to the concept of nonce.

The benefit provided by using a salted password is that a simple dictionary attack against the encrypted values becomes impractical if the salt is large enough. That is, an attacker would not be able to create a rainbow table, a dictionary of encrypted values (password + salt), because it would either take too much time, or too much space. This would force the attacker to use the provided authentication mechanism (which "knows" the correct salt value).

Contents

[edit] Examples

Assume a user’s secret key is stolen and he is known to use one of 200,000 English words as his password. The system uses a 32-bit salt. The salted key is now the original password appended to this random 32-bit salt. Because of this salt, the attacker’s pre-calculated hashes are of no value. He must calculate the hash of each word with each of 232 (4,294,967,296) possible salts appended until a match is found. The total number of possible inputs can be obtained by multiplying the number of words in the dictionary with the number of possible salts:

2^{32} \times 200 000 = 8.58993459 \times 10^{14}

To complete a brute-force attack, the attacker must now compute about 800 trillion hashes, instead of only 200,000. Even though the password itself is known to be simple, the secret salt makes breaking the password radically more difficult.

[edit] Unix implementations

Earlier versions of Unix used a passwd file to store the hashes of salted passwords (passwords prepended with two-character random salts). Note that in these older versions of Unix, the salt is also stored in the passwd file (as cleartext) together with the hash of the salted password. The passwd file is publicly readable for all users of the system. It must be readable so user-privileged software tools can find user names and other information. The security of passwords is protected only by the obscuring 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 4096 possible salt values. While 12 bits was good enough for most purposes in the 1970s (although some expressed doubts even then), by 2005 disk storage had become cheap enough that an attacker can precompute the hashes of millions of common passwords, including all 4096 possible salt variations for each password, and store the precomputed values on a single portable hard drive. An attacker with a larger budget can build a disk farm with all 6 character passwords and the most common 7 and 8 character passwords stored in encrypted form, for all 4096 possible salts[1].

The modern shadow password system, in which password hashes and other security information are 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. 8 bytes password, and 2 bytes 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 usually very 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, even if two accounts use the same password, odds are that no one can discover this by reading passwd files.

[edit] See also

[edit] References

  1. ^ See Password cracking

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Salt_(cryptography)"
Personal tools