Salt (cryptography)
Encyclopedia
In cryptography
, a salt consists of random bit
s, 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 iteration
s 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.
used a password file
(
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.
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. 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.
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 attack
s 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.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a salt consists of random bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s, creating one of the inputs to a one-way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
. The other input is usually a password
Password
A password is a secret word or string of characters that is used for authentication, to prove identity or gain access to a resource . The password should be kept secret from those not allowed access....
or passphrase
Passphrase
A passphrase is a sequence of words or other text used to control access to a computer system, program or data. A passphrase is similar to a password in usage, but is generally longer for added security. Passphrases are often used to control both access to, and operation of, cryptographic programs...
. 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
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
. A salt can also be combined with a password by a key derivation function
Key derivation function
In cryptography, a key derivation function derives one or more secret keys from a secret value such as a master key or other known information such as a password or passphrase using a pseudo-random function...
such as PBKDF2
PBKDF2
PBKDF2 is a key derivation function that is part of RSA Laboratories' Public-Key Cryptography Standards series, specifically PKCS #5 v2.0, also published as Internet Engineering Task Force's RFC 2898...
to generate a key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
for use with a cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
or other cryptographic algorithm
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.
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 iteration
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
s to be used in generating the output (for key stretching).
Early Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
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
Cryptographic nonce
In security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
.
The benefit provided by using a salted password is making a lookup table assisted dictionary attack
Dictionary attack
In cryptanalysis and computer security, a dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by searching likely possibilities.-Technique:...
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
Rainbow table
A rainbow table is a precomputed table for reversing cryptographic hash functions, usually for cracking password hashes. Tables are usually used in recovering the plaintext password, up to a certain length consisting of a limited set of characters. It is a form of time-memory tradeoff, using less...
) 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 UnixUnix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
used a password file
Passwd (file)
In Unix-like operating systems the /etc/passwd file is a text-based database of information about users that may login to the system or other operating system user identities that own running processes....
(
/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 injectionSQL injection
A SQL injection is often used to attack the security of a website by inputting SQL statements in a web form to get a badly designed website in order to dump the database content to the attacker. SQL injection is a code injection technique that exploits a security vulnerability in a website's software...
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. 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 passwordShadow password
In computing, Unix-like operating systems use the shadow password database mechanism to increase the security level of passwords by restricting all but highly privileged users' access to encrypted password data...
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 attack
Dictionary attack
In cryptanalysis and computer security, a dictionary attack is a technique for defeating a cipher or authentication mechanism by trying to determine its decryption key or passphrase by searching likely possibilities.-Technique:...
s 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 crackingPassword crackingPassword cracking is the process of recovering passwords from data that has been stored in or transmitted by a computer system. A common approach is to repeatedly try guesses for the password...
- Cryptographic nonceCryptographic nonceIn security engineering, nonce is an arbitrary number used only once to sign a cryptographic communication. It is similar in spirit to a nonce word, hence the name. It is often a random or pseudo-random number issued in an authentication protocol to ensure that old communications cannot be reused...
- Initialization vectorInitialization vectorIn cryptography, an initialization vector is a fixed-size input to a cryptographic primitive that is typically required to be random or pseudorandom...
- Padding (cryptography)Padding (cryptography)-Classical cryptography:Official messages often start and end in predictable ways: My dear ambassador, Weather report, Sincerely yours, etc. The primary use of padding with classical ciphers is to prevent the cryptanalyst from using that predictability to find cribs that aid in breaking the...
, sometimes confused with salting - Rainbow tables